Efficient Broadcasting in Wireless Sensor Networks

Authors: Min Kyung An, Hyuk Cho

Abstract:

In this paper, we study the Minimum Latency Broadcast Scheduling (MLBS) problem in wireless sensor networks (WSNs). The main issue of the MLBS problem is to compute schedules with the minimum number of timeslots such that a base station can broadcast data to all other sensor nodes with no collisions. Unlike existing works that utilize the traditional omni-directional WSNs, we target the directional WSNs where nodes can collaboratively determine and orientate their antenna directions. We first develop a 7-approximation algorithm, adopting directional WSNs. Our ratio is currently the best, to the best of our knowledge. We then validate the performance of the proposed algorithm through simulation.

Keywords: Broadcast, collision-free, directional antenna, approximation, wireless sensor networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124913

References:

[1] R. Gandhi, S. Parthasarathy, and A. Mishra, “Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks,” in MobiHoc, 2003, pp. 222–232.
[2] R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks,” IEEE/ACM Trans. Netw., vol. 16, no. 4, pp. 840–851, 2008.
[3] A. Dessmark and A. Pelc, “Tradeoffs Between Knowledge and Time of Communication in Geometric Radio Networks,” in Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 2001, pp. 59–66.
[4] S. C.-H. Huang, P.-J. Wan, X. Jia, and H. Du, “Low-Latency Broadcast Scheduling in Ad Hoc Networks,” in WASA, 2006, pp. 527–538.
[5] S. C.-H. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang, “Minimum-Latency Broadcast Scheduling in Wireless Ad Hoc Networks,” in INFOCOM, 2007, pp. 733–739.
[6] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum Latency Gossiping in Wireless Sensor Networks,” in Proceedings of the International Conference on Wireless Networks (ICWN), 2012, pp. 406–412.
[7] S. C. Huang, P. Wan, J. Deng, and Y. S. Han, “Broadcast Scheduling in Interference Environment,” IEEE Trans. Mob. Comput., vol. 7, no. 11, pp. 1338–1348, 2008.
[8] K. Krzywdzinski, “Fast Construction of Broadcast Scheduling and Gossiping in Dynamic Ad Hoc Networks,” in IMCSIT, 2010, pp. 879–884.
[9] R. Gandhi, Y.-A. Kim, S. Lee, J. Ryu, and P.-J. Wan, “Approximation Algorithms for Data Broadcast in Wireless Networks,” in INFOCOM, 2009, pp. 2681–2685.
[10] R. Gandhi, Y. Kim, S. Lee, J. Ryu, and P. Wan, “Approximation Algorithms for Data Broadcast in Wireless Networks,” IEEE Trans. Mob. Comput., vol. 11, no. 7, pp. 1237–1248, 2012.
[11] R. Ramanathan, “On the Performance of Ad Hoc Networks with Beamforming Antennas,” in MobiHoc, 2001, pp. 95 – 105.
[12] S. Roy, Y. C. Hu, D. Peroulis, and X.-Y. Li, “Minimum-Energy Broadcast Using Practical Directional Antennas in All-Wireless Networks,” in INFOCOM, 2006.
[13] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen., “Minimum Latency Aggregation Scheduling in Interference-Aware 3-Dimensional WSNs,” in International Conference on Wireless Networks (ICWN), 2013.
[14] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009.
[15] X. Li, X. Xu, S. Wang, S. Tang, G. Dai, J. Zhao, and Y. Qi, “Efficient Data Aggregation in Multi-hop Wireless Sensor Networks under Physical Interference Model,” in IEEE MASS, 2009, pp. 353–362.
[16] P. Wan, K. M. Alzoubi, and O. Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” in INFOCOM, 2002, pp. 1597 – 1604.