×

Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks. (English) Zbl 1181.90061

Summary: 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.

MSC:

90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

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 · Zbl 0963.68079 · doi:10.1137/S0097539798347906
[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 · Zbl 1192.68891
[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 · Zbl 1094.68515
[4] Elkin M, Kortsarz G. Approximation algorithm for directed telephone multicast problem. Lecture Notes in Computer Science, 2003, 2719: 212–223 · Zbl 1039.68511 · doi:10.1007/3-540-45061-0_19
[5] Gaber I, Mansour Y. Broadcast in radio networks. In: Proceedings of the 6-th ACM-SIAM Symposium on Discrete Algorithms. 1995, 577–585 · Zbl 0851.68007
[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. New York: W. H. Freeman and Company, 1979 · Zbl 0411.68039
[8] Kyasanur P, Vaidya N. Routing and interface assignment in multi-channel wireless networks. In: Proceedings of the 3rd IEEE Wireless Communications and Networking Conference, Vol 4. 2005, 2051–2056 · doi:10.1109/WCNC.2005.1424834
[9] Pelc A. Broadcasting in radio networks. In: Stojmenovic I, ed. Handbook of Wireless Networks and Mobile Computing. New York: John Wiley and Sons, Inc, 2002, 509–528
[10] Raghavendra C S, Sivalingam K M, Znati T. Wireless Sensor Networks. Dordrecht: Kluwer Academic Publishers, 2004 · Zbl 1107.68333
[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 · Zbl 0604.52005
[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 · doi:10.1007/11599463_62
[15] Zhu J, Chen X, Hu X. Minimum multicast time problem in wireless sensor networks. Lecture Nodes in Computer Sciences, 2006, 4138: 490–501 · doi:10.1007/11814856_47
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.