Distance-sensitivity
as a tool for scalable information delivery in networked dynamical systems
Supplying system-wide state
information at high rates is a fundamental problem in several large scale
networked systems. Examples include location tracking in mobile ad-hoc and
sensor networks, decentralized control of spatially distributed systems, and
safety and navigation control in vehicular networks. While all of these
applications would benefit from network wide state information supplied at high
rates and low latency, achieving all-all broadcast using a contention-prone
wireless network is challenging. In fact, the required communication at each
node is expected to grow as O(Np),
where N is the number of nodes and p is the source broadcast rate, causing the
channel capacity to be exceeded very soon in terms of N and p.
Distance-sensitivity can be used
to address this concern and increase the scaling limits of the system. The idea
in distance-sensitivity is to supply information to each node with
progressively increasing spatial and temporal error with distance. In other
words information about farther regions is supplied at higher intervals and
larger spatial compression. By doing so, the information broadcast can scale to
a much higher network size and source broadcast rate. The rationale behind
exploiting distance-sensitivity is that for many applications, information
distance-sensitive precision is actually sufficient. In the past, we have shown
this in the context of pursuit control systems and currently we are exploring
this idea in the context of vehicular safety and navigation control
applications.
|
|
Fig. 1:
Impact of network size: VCAST vs non
distance-sensitive forwarding. (a) Maximum staleness vs
pair-wise vehicular distance: p=10Hz at 225 nodes (b) Maximum staleness vs pair-wise vehicular distance: p=10Hz at 625 nodes
To highlight the impact of
distance-sensitivity, we implemented a basic distance-sensitive forwarding
scheme (VCAST) in the context of vehicular systems in which information about
vehicles is forwarded at a rate that decreases linearly with distance. By using
this scheme, the average communication cost at each node is bounded by O(pN0.5). At the same time the maximum staleness
in information is bounded by O(d2) where d
is the inter-node distance. We evaluated this scheme using simulations in ns-3
and compared it with non distance-sensitive approaches. The following results
highlight the impact.
In Fig.1(a), we show the maximum
staleness as a function of inter-vehicular distance for p=10Hz at a network
size of 225 nodes for both VCAST as well as non distance-sensitive forwarding,
i.e. information about all vehicles is forwarded at the source broadcast rate
by every node. Here, we observe that the non distance-sensitive scheme is able
to keep staleness low at all distances and the growth is linear with distance.
On the other hand, VCAST has low staleness at small distances while the
staleness is observed to grow as $O(d2)$ at
higher distances, as expected. However, at a network size of 625 (see Fig.1(b)), the non distance-sensitive approaches show much
higher staleness even at smaller distances.
However, VCAST is able to maintain low staleness at small distances
while the staleness is observed to grow as $O(d2)$
at higher distances. Information within $400$m is obtained at lower than 300ms
using VCAST while it takes about 3 seconds in the case of a non
distance-sensitive approach. The reason is that as the number of nodes
increases, the channel contention increases at a much higher rate in the non
distance-sensitive forwarding. This causes message losses and consequently an
increase in staleness. The average communication cost is quantified in Fig. 3.
By reducing channel contention, VCAST is able to achieve scalability in number
of nodes.
In Fig.2, we
show the maximum staleness as a function of inter-vehicular distance for
$p=10Hz$ at a network size of $225$, $400$, $625$ and $784$ nodes for VCAST. We
observe that staleness values are preserved at corresponding inter-vehicular
distances, irrespective of network size.
Fig. 2:
Maximum staleness vs pair-wise vehicular distance for
VCAST: p=10Hz, network sizes of 225, 400, 625 and 784 vehicles, Communication
range 100m: Note that staleness values are preserved at corresponding
inter-vehicular distances, irrespective of network size.
In Fig.3 we
show the number of vehicular records transmitted per second by every node for
varying network sizes and highlights the
significantly lower message complexity in VCAST which reduces the contention
even as network size grows. As seen in Fig3, the average communication cost
only appears to grow as O(N0.5) with
network size.
Fig. 3:
Comparison of message complexity: VCAST vs non distance-sensitive
forwarding. (a) Number of vehicular records transmitted per second per node at
different network sizes for p=10Hz and range 100m.
Publications
in this area:
o
V.
Kulathumani, Y. Fallah and
R. Moparthi, “VCAST: Scalable dissemination of vehicular information
with distance-sensitive precision”, International Journal of
Distributed Sensor Networks, 2013 (to
appear)
o
V. Kulathumani, Y. Fallah, “VCAST: A scalable
traffic information service with distance-sensitive precision”, IEEE
Vehicular Technology Conference, 2012
o V. Kulathumani, A. Arora and S. Ramagiri, “Pursuit
Control over Wireless Sensor Networks using Distance Sensitivity Properties”,
Accepted for Publication in IEEE Transactions on Automatic Control, Special
Issue on Wireless Sensor Actuator Networks, 56(10), pp.2473—2478, 2011 Extended
version
o
V. Kulathumani, M. Demirbas, A. Arora, M. Sridharan, Trail:
A Distance Sensitive Network Protocol for Distributed Object Tracking ,
EWSN 2007, ACM TOSN
o Hui Cao, Emre Ertin, Vinodkrishnan Kulathumani et al., Differential Games in Large Scale Sensor Actuator Networks , IPSN'06.
o V. Kulathumani and A. Arora, Distance Sensitive
Snapshots in Wireless Sensor Networks, International
Conference on Principles of Distributed Systems (OPODIS), 2007
o V. Kulathumani, A. Arora, Aspects of Distance Sensitive Design of Wireless
Sensor Networks, IEEE Workshop on Spatial Computing, Venice, Italy,
2008