Minimizing broadcast latency and redundancy in ad hoc networks

ABSTRACT

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within O(1) times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.

REFERENCES

• 1: 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]
• 2: 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]
• 3: J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson, "A simple protocol for multicast and broadcast in mobile ad hoc networks," IETF MANET Working Group, Internet draft, 2001.
• 4: Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998 [doi>10.1023/A:1019045801829]
• 5: B. Das, R. Sivakumar, and V. Bharghavan, "Routing in ad hoc networks using a virtual backbone," in Proc. 6th Int. Comput. Commun. and Netw. Conf., 1997, pp. 1-20.
• 6: B. Das and V. Bharghavan, "Routing in ad hoc networks using minimum connected dominating sets," in Proc. IEEE Int. Commun. Conf., 1997, vol. 1, pp. 376-380.
• 7: D. Lichtenstein, "Planar formulae and their uses," SIAM J. Comput., vol. 11, pp. 329-343, 1982.
• 8: 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]
• 9: Peng-Jun Wan , Khaled M. Alzoubi , Ophir Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.141-149, April 2004 [doi>10.1023/B:MONE.0000013625.87793.13]
• 10: X. Cheng, X. Huang, D. Li, and D.-Z. Du, "Polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks," Networks, vol. 42, no. 4, pp. 202-208, 2003.
• 11: M. V. Marathe, H. Breu, H. B. Hunt, III, S. S. Ravi, and D. J. Rosenkrantz, "Simple heuristics for unit disk graphs," Networks, vol. 25, pp. 59-68, 1995.
• 12: Hyojun Lim , Chongkwon Kim, Multicast tree construction and flooding in wireless ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346865]
• 13: Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 14: A. Qayyum, L. Viennot, and A. Laouiti, "Multipoint relaying: An efficient technique for flooding in mobile wireless networks," INRIA, Le Chesnay, France, Tech. Res. Rep. RR-3898, Feb. 2000.
• 15: W. Peng and X.-C. Lu, "AHBP: An efficient broadcast protocol for mobile ad hoc networks," J. Comput. Sci. Technol., vol. 16, no. 2, pp. 114-125, 2001.
• 16: J. Sucec and I. Marsic, "An efficient distributed network-wide broadcast algorithm for mobile ad hoc networks," Rutgers Univ., New Brunswick, NJ, Tech. Rep., 2000.
• 17: W. Peng and X. Lu, "Efficient broadcast in mobile ad hoc networks using connected dominating sets," J. Softw., vol. 12, no. 4, pp. 529-536, 2001.
• 18: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 19: L. Orecchia , A. Panconesi , C. Petrioli , A. Vitaletti, Localized techniques for broadcasting in wireless sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022638]
• 20: Hussein F. Salama , Douglas S. Reeves , Yannis Viniotis, The Delay-Constrained Minimum Spanning Tree Problem, Proceedings of the 2nd IEEE Symposium on Computers and Communications (ISCC '97), p.699, July 01-03, 1997
• 21: I. Chlamtac and S. Kutten, "On broadcasting in radio networks--Problem analysis and protocol design," IEEE Trans. Commun., vol. COM-33, no. 12, pp. 1240-1246, Dec. 1985.
• 22: 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]
• 23: Stefano Basagni , Imrich Chlamtac , Danilo Bruschi, A mobility-transparent deterministic broadcast mechanism for ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.799-807, Dec. 1999 [doi>10.1109/90.811446]
• 24: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 25: Bogdan S. Chlebus , Leszek Gasieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in ad hoc radio networks, Distributed Computing, v.15 n.1, p.27-38, January 2002 [doi>10.1007/s446-002-8028-1]
• 26: Jang-Ping Sheu , Pei-Kai Hung , Chih-Shun Hsu, Scheduling of broadcasts in multihop wireless networks, The handbook of ad hoc wireless networks, CRC Press, Inc., Boca Raton, FL, 2003
• 27: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]
• 28: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 29: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 30: Danilo Bruschi , Massimiliano Del Pinto, Lower bounds for the broadcast problem in mobile radio networks, Distributed Computing, v.10 n.3, p.129-135, April 1997 [doi>10.1007/s004460050030]
• 31: Dariusz R. Kowalski , Andrzej Pelc, Deterministic Broadcasting Time in Radio Networks of Unknown Topology, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.63-72, November 16-19, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Design, Performance

Keywords:
ad hoc networking, approximation algorithms, broadcast algorithms, wireless scheduling