Authors: Stojmenović, Ivan
Seddigh, Mahtab
Žunić, Joviša 
Title: Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks
Journal: IEEE Transactions on Parallel and Distributed Systems
Volume: 13
Issue: 1
First page: 14
Last page: 25
Issue Date: 1-Jan-2002
Rank: M21
ISSN: 1045-9219
DOI: 10.1109/71.980024
In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for broadcasting task is measured experimentally. Dominating sets based broadcasting, enhanced by neighbor elimination scheme and highest degree key, provides reliable broadcast with ≤ 53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with ≤48 percent for ≤3,≤ 40 percent for d≥10, and ≤20 percent for d≥25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings.
Keywords: Broadcasting | Clustering | Distributed algorithms | Dominating sets | Wireless networks
Publisher: IEEE

Show full item record


checked on May 17, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.