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 end a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc wireless networks. Our objective is to minimize the latency and the number of retransmission in the broadcast. We show that minimum latency broadcasting i NP-hard for ad hoc wireless networks. We also present a simple and 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 retransmission are within O(1)times their respective optimal values. Our algorithm and analysis extends to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithm perform much better in practice than the analytical guarantee provided for the worst case.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: Cheng, X., Huang, X., Li, D., and Du, D.-Z. Polynomial-time approximation scheme for minimum connected dominating set in a hoc wireless networks.Tech. rep.
• 6: 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]
• 7: Chlamtac, I., and Kutten, S. On broadcasting in radio networks-problem analysis and protocol design. IEEE Transactions on Communications 33, 12 (1985), 1240--1246.
• 8: I. Chlamtac , S. Kutten, Tree-based broadcasting in multihop radio networks, IEEE Transactions on Computers, v.36 n.10, p.1209-1223, Oct. 1987 [doi>10.1109/TC.1987.1676861]
• 9: 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]
• 10: 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]
• 11: Das, B., and Bharghavan, V. Routing in ad-hoc networks using minimum connected dominating sets. In ICC(1) (1997), pp.376--380.
• 12: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 13: Michael Elkin , Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509972]
• 14: Guha, S., and Khuller, S. Approximation algorithms for connected dominating sets. Algorithmica (1998),374--387.
• 15: 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]
• 16: Hung, P.-K., Sheu, J.-P., and Hsu, C.-S. Scheduling of broadcasts in multihop wireless networks. In European Wireless (2002).
• 17: Jetcheva, J., Hu, Y., Maltz, D., and Johnson, D. A simple protocol for multicast and broadcast in mobile ad hoc networks, July 2001.
• 18: 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
• 19: 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]
• 20: Marathe, M.V., Breu, H., HuntIII, H.B., Ravi, S.S., and Rosenkrantz, D. J. Simple heuristics for unit disk graphs. Networks 25 (1995), 59--68.
• 21: 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]
• 22: Peng, W., and Lu, X. Efficient broadcast in mobile a hoc networks using connected dominating sets. Journal of Software - Beijing, China (1999).
• 23: Peng, W., and Lu, X. Ahbp: An efficient broadcast protocol for mobile adhoc networks. Journal of Science and Technology - Beijing, China (2000).
• 24: 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
• 25: Qayyum, A., Viennot, L., and Laouiti, A. Multipoint relaying: An efficient technique for ?ooding in mobile wireless networks. Tech. Rep. Research Report RR-3898, INRIA, Feb. 2000.
• 26: 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]
• 27: Sucec, J., and Marsic, I. An efficient distributed network-wide broadcast algorithm for mobile adhoc networks. Tech.rep., Rutgers University, September 2000.
• 28: Wan, P.-J., Alzoubi, K., and Frieder, O. Distributed construction of connnected dominating set in wireless ad hoc networks. In IEEE INFOCOM (2002).
• 29: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance, Theory

Keywords:
NP-hardness, ad hoc networks, approximation algorithms, broadcasting