|
|
|
Approximation algorithm for constructing data
aggregation trees for wireless sensor networks |
| Deying LI1,Qinghua ZHU1,Jiannong CAO2, |
| 1.Key Laboratory
of Data Engineering and Knowledge Engineering, School of Information,
Renmin University of China, Beijing 100872, China; 2.Internet and Mobile
Computing Lab, Department of Computing, Hong Kong Polytechnic University,
Hong Kong, China; |
|
|
|
|
Abstract This paper considers the problem of constructing data aggregation trees in wireless sensor networks (WSNs) for a group of sensor nodes to send collected information to a single sink node. The data aggregation tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data aggregation tree is to minimize the number of non-source nodes to be included in the tree so as to save energies. We prove that the data aggregation tree problem is NP-hard and then propose an approximation algorithm with a performance ratio of four and a greedy algorithm. We also give a distributed version of the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithms. The results show that the proposed algorithms can find a tree of a good approximation to the optimal tree and has a high degree of scalability.
|
| Keywords
WSNs
data aggregation tree
approximation algorithm
distributed algorithm
|
|
Issue Date: 05 December 2009
|
|
|
Culler D, Estrin D, Srivastava M. Overview of sensor networks. Computer, 2004, 37(8): 41―49
doi: 10.1109/MC.2004.93
|
|
Chong C-Y, Kumar S P. Sensor networks: evolution,opportunities, and challenges. In: Proceedingsof the IEEE, 2003, 91(8): 1247―1256
doi: 10.1109/JPROC.2003.814918
|
|
Goel A, Estrin D. Simultaneous optimiationfor concave costs: single sink aggregation or single source buy-at-bulk. In: Proceedings of the 14th ACM-SIAM Symposiumon Discrete Algorithms. 2003, 499―505
|
|
Karl H, Lobbers M, Neberg T. A data aggregation framework for wireless sensor networks. Technical report TKN-03-016, TelecommunicationNetwork Group, Technical University Berlin, Sept. 2003
|
|
Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: a scalable and robust communicationparadigm for sensor networks. In: Proceedingsof the 6th Annual ACM/IEEE International Conference on Mobile Computingand Networking (MOBICOM’00). Boston, MA, 2000, 56―67
|
|
Yu Y, Krishnamachari B, Prasanna V K. Energy-latency tradeoffs for data gathering in wirelesssensor networks. In: Proceedings of the23rd Conference of IEEE Communication Society (INFOCOM’04). Hong Kong, 2004, 255―266
|
|
Schurgers C, Aberhorne O, Srivastava M B. Modulation scaling for energy-aware communication systems. In: Proceedings of International Symposium on LowPower Electronics and Design (ISLPED’01). Huntington Beach, CA, 2001, 96―99
|
|
Prabhakar B, Uysal-Biyikoglu E, Gamal A E. Energy-efficient transmission over awireless link via lazy packet scheduling. In: Proceedings of the 20th Conference of IEEE Communication Society(INFOCOM’ 01). 2001, 386―394
|
|
Intanagonwiwat C, Estrin D, Govindan R, et al. Impact of network density on data aggregationin wireless sensor networks, In: Proceedingsof the 22nd International Conference on Distributed Computing Systems(ICDCS’02). Austria, 2002, 457―458
|
|
Kalpakis K, Dasgupta K, Namjoshi P. Efficient algorithms for maximum lifetime data gatheringand aggregation in wireless sensor networks. The International Journal of Computer and Telecommunications Networking, 2003, 42(6): 697―716
|
|
Wu Y, Fahmy S, Shroff N. On the construction of a maximum-lifetime data gatheringtree in sensor networks: NP-completeness and approximation algorithm. In: Proceedings of the 26rd Conference of IEEECommunication Society (INFOCOM’08). 2008, 356―360
|
|
Ding M, Cheng X, Xue G. Aggregation tree construction in sensor networks. In: Proceedings of IEEE VTC’03. 2003, 2168―2172
|
|
Du H, Hu H, Jia X, Energy efficient routing and scheduling for real timedata aggregation in wireless sensor networks. Computer Communications, 2006, 29(17): 3527―3535
doi: 10.1016/j.comcom.2006.01.032
|
|
Luo H, Liu Y, Das K. Routing correlated data with fusion cost in wirelesssensor networks. IEEE Trans. on MobileComputing, 2006, 5(11): 1620―1632
doi: 10.1109/TMC.2006.171
|
|
Li D, Liu Q, Jia X, et al. Energy efficient multicast routing in ad hocnetworks. Computer Commuinations, 2007, 30: 3746―3756
doi: 10.1016/j.comcom.2007.09.003
|
|
Chen X, Hu X, Zhu J. Minimum data aggregation time problem in wireless sensornetworks. In: Proceedings of 1st int’lConferenve on Mobile Ad-hoc and Sensor Networks-MSN05. 2005, 133―142
|
|
Huang S, Wan P-J, Vu C T, et al. Nearly constant approximation for data aggregationscheduling in wireless sensor networks. In: Proceedings of the 26rd Conference of IEEE Communication Society(INFOCOM’ 07). 2007, 366―372
|
|
Li D, Cao J, Liu M, et al. Construction of optimal data aggregation treesfor wireless sensor networks. In: Proceedingsof ICCCN06. 2006, 475―480
|
|
Garey M, Johnson D. The rectilinear steiner treeis NP-complete. SIAM Journal on AppliedMathematics, 1997, 32(4): 826―834
doi: 10.1137/0132071
|
|
Chen D, Du D, Hu X, et al. Approximateins for steiner trees with minimumnumber of steiner points. Theoretical ComputerScience, 2001, 262: 83―99
doi: 10.1016/S0304-3975(00)00182-1
|
|
Mandoiu I, Zelikovsky A. A note on the MST heuristicfor bounded edge-length steiner trees with minimum number of steinerpoints. Information Processing Letters, 2000, 75(4): 165―167
doi: 10.1016/S0020-0190(00)00095-8
|
|
Awerbuch B. Optimaldistributed algorithms for minimum-weight spanning tree, counting,leader election and related problems. In: Proceedings of 19th ACM Symp. on Theory of Computing, ACM, New York. 1987, 230―240
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
