Shankar M Banik
Sridhar Radhakrishnan
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.
- Gandhi R., Parthasarathy S., Mishra A. Minimizing Broadcast Latency and Redundancy in Ad-Hoc Networks. In Proceeding of 4th ACM MobiHoc 2003, pp 222--232. Google Scholar
Digital Library
- Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1978. Google ScholarDigital Library
- Guha S., Khuller S. Approximation Algorithms for Connected Dominating Sets. Algorithmica 1998, pp 374--387. Google ScholarDigital Library
- Stojmenovic et. al., Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks. IEEE Transactions on Parallel and Distributed Systems, Vol. 12, No. 12, December 2001, pp 1--12. Google ScholarDigital Library
- Lou W., Wu J. On Reducing Broadcast Redundancy in Adhoc Wireless Networks. In Proceedings of the 36th Hawaii International Conference on System Sciences, 2003, pp 305--314. Google ScholarDigital Library
Index Terms
- Minimizing broadcast latency in ad hoc wireless networks
Recommendations
Flooding in wireless ad hoc networks
In an ad hoc network, each host assumes the role of a router and relays packets toward final destinations. This paper studies efficient routing mechanisms for packet flooding in ad hoc wireless networks. Because a packet is broadcast to all neighboring ...
Reducing Broadcast Redundancy in Wireless Ad-Hoc Networks with Implicit Coordination Among Forwarding Nodes
Broadcasting is the process of sending a packet from a node to all other nodes in a network. In wireless ad-hoc networks, broadcasting might involve forwardings from intermediate nodes known as forwarding nodes because some nodes could be located ...
An Adjusted Counter-Based Broadcast Scheme for Mobile Ad Hoc Networks
UKSIM '08: Proceedings of the Tenth International Conference on Computer Modeling and SimulationBroadcasting is a fundamental and frequently usedoperation in mobile ad hoc networks (MANETs) wherea source node diffuses a message to all other nodes inthe networks. Flooding, the process in which eachnode retransmits every uniquely received ...
Comments