Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

Abstract

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.

Keywords

broadcast schedule / approximation algorithm / wireless sensor network / unit disk graph

References

[1] Bar-Noy A., Guha S., Naor J., Schieber B. Message multicasting in heterogeneous networks. SIAM Journal on Computing, 2000, 30(2): 347-358.

[2] Elkin M, Kortsarz G. A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. In: Proceedings of the 34-th ACM Annual Symposium on Theory of Computing. 2002, 438–447

[3] Elkin M, Kortsarz G. Sublogarithmic approximation algorithm for the undirected telephone broadcast problem: a path out of a jungle. In: Proceedings of the 14-th Annual ACM-SCIM Symposium on Discrete Algorithms. 2003, 76–85

[4] Elkin M., Kortsarz G. Approximation algorithm for directed telephone multicast problem. Lecture Notes in Computer Science, 2003, 2719: 212-223.

[5] Gaber I, Mansour Y. Broadcast in radio networks. In: Proceedings of the 6-th ACM-SIAM Symposium on Discrete Algorithms. 1995, 577–585

[6] Gandhi R, Parthasarathy S, Mishra A. Minimizing broadcasting latency and redundancy in ad hoc networks. In: Proceedings of the 4-th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2003, 222–231

[7] Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness, 1979, New York: W. H. Freeman and Company.

[8] Kyasanur P., Vaidya N. Routing and interface assignment in multi-channel wireless networks. Proceedings of the 3rd IEEE Wireless Communications and Networking Conference, 2005, 4: 2051-2056.

[9] Pelc A. Stojmenovic I. Broadcasting in radio networks. Handbook of Wireless Networks and Mobile Computing, 2002, New York: John Wiley and Sons, Inc, 509-528.

[10] Raghavendra C. S., Sivalingam K. M., Znati T. Wireless Sensor Networks, 2004, Dordrecht: Kluwer Academic Publishers

[11] Ravi R. Rapid rumor ramification: approximating the minimum broadcast time. In: Proceedings of the 35-th IEEE Annual Symposium on Foundations of Computer Science. 1994, 202–213

[12] Shang W, Wan P, Hu X. Approximation algorithm for minimal convergecast time problem in wireless sensor networks. Acta Mathematicae Applicatae Sinica (to appear)

[13] Wegner G. Uber endliche Kreispackungen in der Ebene. Studia Sci Math Hungar, 1986, 21: 1-28.

[14] Xu L., Xiang Y., Shi M. On the problem of channel assignment for multi-NIC multihop wireless networks. Lecture Notes in Computer Sciences, 2005, 3794: 633-642.

[15] Zhu J., Chen X., Hu X. Minimum multicast time problem in wireless sensor networks. Lecture Nodes in Computer Sciences, 2006, 4138: 490-501.

[16] Zhu J, Shang W, Hu X. New algorithm for minimum multicast time problem in wireless sensor networks. In: Proceedings of the 5-th IEEE Wireless Communications and Networking Conference, 2007