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