Minimizing broadcast latency in ad hoc wireless networks

ABSTRACT

Network wide broadcasting in ad-hoc wireless networks provides important control and route establishment functionality for a number of unicast and multicast protocols. In broadcasting, a source node sends the same message to all the nodes in the network. Broadcasting based on Minimum Connected Dominating Set (MCDS) is a frequently used approach to reduce the communication overhead. A set of connected nodes in a graph is a connected dominating set, if all the nodes in the graph are either in the set or neighbors of nodes in the set. MCDS is such a set with minimum cardinality. Several broadcasting algorithms in adhoc wireless networks based on neighborhood information use MCDSs. This approach minimizes the total number of transmissions in broadcasting process but it does not guarantee minimum broadcast latency. Minimum latency broadcast is NPhard for ad-hoc wireless network [1]. A proper collision-free broadcast scheduling among nodes in MCDS will minimize the broadcast latency. In this paper, we propose a collision-free broadcast scheduling algorithm to minimize the broadcast latency for a given network with the number of transmissions equal to cardinality of MCDS.

REFERENCES

• 1: 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]
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 3: Guha S., Khuller S. Approximation Algorithms for Connected Dominating Sets. Algorithmica 1998, pp 374--387.
• 4: 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]
• 5: Wei Lou , Jie Wu, On Reducing Broadcast Redundancy in Ad Hoc Wireless Networks, Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS'03) - Track 9, p.305.2, January 06-09, 2003

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations

General Terms:
Algorithms

Keywords:
broadcasting, minimum connected dominating set, scheduling