Tree-on-DAG for Data Aggregation in Sensor Networks

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.

Authors:

• Prakash G L
• Thejaswini M
• S H Manjula
• K R Venugopal
• L M Patnaik

Keywords:

• Aggregation
• Packet Merging
• Query Processing.

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.