Tree-on-DAG for Data Aggregation in Sensor Networks

Authors: Prakash G L, Thejaswini M, S H Manjula, K R Venugopal, L M Patnaik

Abstract:

Computing and maintaining network structures for efficient data aggregation incurs high overhead for dynamic events where the set of nodes sensing an event changes with time. Moreover, structured approaches are sensitive to the waiting time that is used by nodes to wait for packets from their children before forwarding the packet to the sink. An optimal routing and data aggregation scheme for wireless sensor networks is proposed in this paper. We propose Tree on DAG (ToD), a semistructured approach that uses Dynamic Forwarding on an implicitly constructed structure composed of multiple shortest path trees to support network scalability. The key principle behind ToD is that adjacent nodes in a graph will have low stretch in one of these trees in ToD, thus resulting in early aggregation of packets. Based on simulations on a 2,000-node Mica2- based network, we conclude that efficient aggregation in large-scale networks can be achieved by our semistructured approach.

Keywords: Aggregation, Packet Merging, Query Processing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060491

References:

[1] K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, "Protocols for selforganization of a wireless sensor network," IEEE Communication, vol. 7, pp. 16-27, oct. 2007.
[2] M. Ding, X. Cheng, and G. Xue, "Aggregation Tree Construction in Sensor Networks," in Proc. 58th IEEE Vehicular Technology Conf. (VTC 03), vol. 4, pp. 2168-2172, Oct. 2003.
[3] S. Lindsey, C. Raghavendra, and K.M. Sivalingam, "Aggregation Tree Construction in Sensor Networks," in Data Gathering Algorithms in Sensor Networks Using Energy Metrics, vol. 13, pp. 924-935, Sept. 2002.
[4] R. Cristescu and M. Vetterli, "Power Efficient Gathering of Correlated Data: Optimization, NP-Completeness and Heuristics," in Summaries of MobiHoc 2003 Posters, vol. 7, pp. 31-32, July 2003.
[5] A. Goel and D. Estrin, "Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk," in Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), 2003.
[6] N. Alon, R.M. Karp, D. Peleg, and D. West, "A Graph Theoretic Game and Its Application to the K-Server Problem," in SIAM J. Computing, vol. 24, 1995.
[7] K.W. Fan, S. Liu, and P. Sinha, "On the Potential of Structure-Free Data Aggregation in Sensor Networks," in Proc. IEEE INFOCOM 06, Apr 2006.
[8] Krishanamachari, Estrin D., Wicker S, "The Impact of Data Aggregation in Wireless Sensor Networks," in IEEE Confernece on Distributed Comput- ing systems Workshop, 2002.
[9] Weisong Shi, Sivakumar Sellamuthu, Kewei Sha and Loren Schwiebert, "Query Agent: A General Query Processing Tool for Sensor Networks," in IEEE Conference on Parallel Computing Workshop, September 2004.
[10] S. Chatterjea, P. Havinga, "A Dyanamic Data Aggregation Scheme for Wireless Sensor Networks," ProRISC, Veldhoven, The Netherlands, 26- 27 November 2003.