Efficient Broadcasting in Wireless Sensor Networks

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.

Authors:

• Min Kyung An
• Hyuk Cho

Keywords:

• Broadcast
• collision-free
• directional antenna
• approximation
• wireless sensor networks.

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.