Network Support for Distributed Sensing Applications

Investigators: Gustavo de Veciana , Ari Arapostathis and Margarida Jacome
Graduate Students: Seung Jun Baek, Xun Su, Alexander Zemlianov
Support: This project is supported by the National Science Foundation Grant ECS 0225448
A Problem in Distributed Compression and Routing : What is the best (minimum energy requirements) way to arrange distributed aggregation/compression and routing of sensor data in large scale sensor network?
Picture of Voronoi tesselation Picture of Johnson Mehl tesselation
Our project seeks to look at network support for sensing applications drawing on spatio-temporal data from large scale sensor networks that have wireless capability to forward the data they gather. A large collection of sensors would generate large amounts of information, and thus the question of how to arrange such activities arises. We studied a scalable hierarchical arrangement of sensors, with dedicated aggregation nodes and distributed sinks, with a view on collecting large amounts of spatio-temporal data from a field of sensors. Our objective was to devise an optimal organization that minimizes the traffic load and thus energy consumed over the network. We have shown that the optimal structure involves spatial clustering of sensors around aggregation points, based on induced Johnson-Mehl tessellation, rather than a Voronoi tessellation. The figures below represent these two organizations for aggregation points (red dots) and sinks (black dots). On the left is show the proximity based organization, i.e., a sensor at a given location in space would relay its traffic to the closest aggregation point, which would compress it and forward to the closest sink -- this arrangement can be viewed in terms of Voronoi cells (shown in blue) associated with each aggregation point and sink (shown with dotted lines). The figure on the right shows the energy optimal organization. The cells with hyperbolic facets are typical of Johnson-Mehl tessellations.
Picture of per location energy contours Picture of aggreagate energy contours
Minimizing the overall energy consumption in a large scale sensor network is a reasonable objective, yet we are exploring, the related problem of maximizing the network lifetime, i.e., the time until one of the sensors runs out of energy or the time until a constraint on coverage of the field is violated. In order to achieve this one must be able to balance the energy burden that various nodes in the system will see. The figure on the left shows the energy burden associated with data generated from possible sensor locations --red is high while blue is low cost to bring this data to an eventual sink. The figure on the right shows instead the overall energy burden of each spatial location assuming for simplicity straight line routing. As can be seen in both figures, and in particular on the right, the spatial energy burden is quite uneven. Dealing with this problem is our current task.

Representative Publications _____________________

Spatial Energy Balancing through Proactive Multipath Routing in Wireless Multihop Networks.
S.-J. Baek and Gustavo de Veciana,   IEEE/ACM Transactions on Networking, 15(1):93-104,Feb 2007.
A scalable model for energy load balancing in large-scale sensor networks.
S.-J. Baek and G. de Veciana.   In Proc. Spaswin 2006 , pages 1-10, April 2006.
Capacity of Ad hoc Networks with Infrastructure Support
A. Zemlianov, and G. de Veciana,   IEEE Journal of Selected Areas of Communications Vol. 23, No. 3, 657-667, March 2005.
Minimizing energy consumption in large-scale sensor networks through distributed
data compression and hierarchical aggregation.

S.-J. Baek and G. de Veciana and X. Su,   IEEE JSAC Special Issue on Fundamental performance limits of wireless sensor networks Vol. 22, No. 6, 1130-1140, August 2004.