A New Scheduling Algorithm for Reducing Data Aggregation Latency in Wireless Sensor Networks

Meirui Ren, Longjiang Guo, Jinbao Li

.

DOI: 10.4236/ijcns.2010.38091                

Abstract

Existing works on data aggregation in wireless sensor networks (WSNs) usually use a single channel which results in a long latency due to high interference, especially in high-density networks. Therefore, data aggre- gation is a fundamental yet time-consuming task in WSNs. We present an improved algorithm to reduce data aggregation latency. Our algorithm has a latency bound of 16R + Δ – 11, where Δ is the maximum degree and R is the network radius. We prove that our algorithm has smaller latency than the algorithm in [1]. The simulation results show that our algorithm has much better performance in practice than previous works.

Keywords

Reducing Latency, Wireless Sensor Networks, Scheduling Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. C.-H. Huang, P.-J. Wan, C. T. Vu, Y. S. Li and F. Yao, “Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor Networks,” Proceedings of 26th IEEE International Conference on Computer Communications, Anchorage, 6-12 May 2007, pp. 366- 372.
[2]	X. J. Chen, X. D. Hu and J. M. Zhu, “Minimum Data Aggregation Time Problem in Wireless Sensor Networks,” Proceedings of 1st International Conference on Mobile Ad-Hoc and Sensor Networks, Lecture Notes in Computer Science, Wuhan, Vol. 3794, 13-15 December 2005, pp. 133-142.
[3]	V. Annamalai, S. K. S. Gupta and L. Schwiebert, “On Tree-Based Convergecasting in Wireless Sensor Networks,” Proceedings of IEEE Wireless Communications and Networking, New Orleans, Vol. 3, 20 March 2003, pp. 1942-1947.
[4]	S. Upadhyayula, V. Annamalai and S. K. S. Gupta, “A Low Latency and Energy-Efficient Algorithm for Convergecast in Wireless Sensor Networks,” Proceedings of IEEE Global Telecommunications Conference, San Francisco, Vol. 6, 1-5 December 2003, pp. 3525-3530.
[5]	H. J. Wu, Q. Luo and W. W. Xue, “Distributed Cross- Layer Scheduling for in-Network Sensor Query Processing,” Proceedings of 4th Annual IEEE International Conference on Pervasive Computing and Communications, Pisa, Vol. 10, 13-17 March 2006, pp. 180-189.
[6]	O. Chipara, C. Y. Lu and J. Stankovic, “Dynamic Conflict-Free Query Scheduling for Wireless Sensor Networks,” Proceedings of 14th IEEE International Conference on Network Protocols, Santa Barbara, 12-15 November 2006, pp. 321-331.
[7]	Y. Yu, B. Krishnamachari and V. K. Prasanna, “Energy-Latency Trade-Offs for Data Gathering in Wireless Sensor Networks,” Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, 7-11 March 2004, pp. 1-12.
[8]	Q. F. Huang and Y. Zhang, “Radial Coordination for Convergecast in Wireless Sensor Networks,” Proceedings of 29th Annual IEEE International Conference on Local Computer Networks, Tampa, 16-18 November 2004, pp. 542-549.
[9]	H. W. Zhang, A. Arora, Y.-R. Choi and M. G. Gouda, “Reliable Bursty Convergecast in Wireless Sensor Networks,” Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Urbana-Champaign, 25-28 May 2005, pp. 266-276.
[10]	B. Krishnamachari, D. Estrin and S. B. Wicker, “The Impact of Data Aggregation in Wireless Sensor Networks,” Proceedings of the 22nd International Conference on Distributed Computing Systems, Vienna, 2-5 July 2002, pp. 575-578.
[11]	C. Intanagonwiwat, D. Estrin, R. Govindan and J. Heidemann, “Impact of Network Density on Data Aggregation in Wireless Sensor Networks,” Proceedings of the 22nd International Conference on Distributed Computing Systems, Vienna, 2-5 July 2002, pp. 457-472.
[12]	A. Kesselman and D. Kowalski, “Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks,” Proceedings of 2nd International Conference on Wireless on Demand Network Systems and Service, St. Moritz, 19-21 January 2005, pp. 1-6.
[13]	R. A. Brualdi, “Introductory Combinatorics,” 3rd Edition, Prentice Hall, Upper Saddle River, 1999, pp. 27-34.