Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks

• Published in: IEEE transactions on parallel and distributed systems 2002-01, Vol.13 (1), p.14-25
• Main Authors: Stojmenovic, I., Seddigh, M., Zunic, J.
• Format: Article
• Language: English
• Subjects: Algorithms; Broadcasting; Intelligent networks; Keys; Maintenance; Messages; Networks; Tasks; Wireless communication; Wireless networks
• ISSN: 1045-9219; 1558-2183
• 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 the 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 the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with /spl les/53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with