An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks

ABSTRACT

Broadcast scheduling is a fundamental problem in wireless ad hoc networks. The objective of a broadcast schedule is to deliver a message from a given source to all other nodes in a minimum amount of time. At the same time, in order for the broadcast to proceed as predicted in the schedule, it must not contain parallel transmissions which can be conflicting based on the collision and interference parameters in the wireless network. Most existing work on this problem use a limited network model which accounts only for conflicts occurring inside the transmission ranges of the nodes. The broadcast schedules produced by these algorithms are likely to experience unpredictable delays when deployed in the network. This is because they do not take into consideration other important sources of conflict in parallel transmissions, namely the interference range and the carrier sensing range. In this paper we develop a conflict-aware network model, which uses these parameters to increase the probability of scheduling conflict-free transmissions, and thereby improve the reliability of the broadcast schedule. We present and prove correctness of a constant approximation algorithm for minimum-latency broadcast scheduling under this network model. We also present a greedy heuristic algorithm for the same problem. Experimental results are provided to evaluate the performance of our algorithms. In addition, the algorithms are analyzed to justify their performance trends.

REFERENCES

• 1: Z. Chen, C. Qiao, J. Xu, and T. Lee. A constant approximation algorithm for interference aware broadcast in wireless networks. In INFOCOM, pages 740--748, 2007.
• 2: I. Chlamtac and S. Kutten. On broadcasting in radio networks - Problem analysis and protocol design. IEEE Transactions on Communications, 33:1240--1246, dec 1985.
• 3: I. Chlamtac , S. Kutten, Tree-Based Broadcasting in Multihop Radio Networks, IEEE Transactions on Computers, v.36 n.10, p.1209-1223, October 1987 [doi>10.1109/TC.1987.1676861]
• 4: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 5: J. Deng, B. Liang, and P. Varshney. Tuning the carrier sensing range of ieee 802.11 mac. In GLOBECOM, pages 2987--2991, 2004.
• 6: Rajiv Gandhi , Srinivasan Parthasarathy , Arunesh Mishra, Minimizing broadcast latency and redundancy in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778442]
• 7: Leszek Gasieniec , David Peleg , Qin Xin, Faster communication in known topology radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073840]
• 8: Christopher Ho , Katia Obraczka , Gene Tsudik , Kumar Viswanath, Flooding for reliable multicast in multi-hop ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.64-71, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313291]
• 9: 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, pages 733--739, 2007.
• 10: J. Jercheva, Y. Hu, D. Maltz, and D. Johnson. A simple protocol for multicast and broadcast in mobile ad hoc networks, July 2002.
• 11: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 12: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 13: Xavier Gérard Viennot, A Strahler bijection between Dyck paths and planar trees, Discrete Mathematics, v.246 n.1-3, p.317-329, 6 March 2002 [doi>10.1016/S0012-365X(01)00265-5]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
approximation algorithm, broadcast scheduling, conflict-aware, wireless networks