January 2002 | Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic
This paper proposes efficient broadcasting algorithms for wireless networks based on localized dominating sets and neighbor elimination. The key idea is to reduce communication overhead by using internal nodes (nodes in a dominating set) for rebroadcasting, which requires no additional communication overhead beyond maintaining neighbor positions. The algorithms use node degrees instead of node IDs as primary keys for selecting internal nodes, improving efficiency. A neighbor elimination scheme is introduced to avoid retransmitting messages to nodes that have already received them, reducing unnecessary rebroadcasts. Additionally, a retransmission after negative acknowledgments scheme is described to ensure reliable delivery. The proposed algorithms are reliable, significantly reduce rebroadcasts, and are localized and parameterless. Experimental results show that the proposed methods outperform existing ones in terms of reliability, rebroadcast savings, and communication overhead. The algorithms perform best for networks with average degrees above 4, achieving up to 53% node retransmissions for random unit graphs with 100 nodes. The methods are more efficient than clustering-based approaches, which suffer from high communication overhead for maintaining structure. The proposed algorithms are also more efficient than location-based methods in terms of rebroadcast savings. The algorithms are tested on random unit graphs and show high reachability (over 98.3%) and low latency. The impact of variable maximal backoff, message size, traffic, and mobility is also analyzed, showing that the proposed methods are robust and efficient under various conditions.This paper proposes efficient broadcasting algorithms for wireless networks based on localized dominating sets and neighbor elimination. The key idea is to reduce communication overhead by using internal nodes (nodes in a dominating set) for rebroadcasting, which requires no additional communication overhead beyond maintaining neighbor positions. The algorithms use node degrees instead of node IDs as primary keys for selecting internal nodes, improving efficiency. A neighbor elimination scheme is introduced to avoid retransmitting messages to nodes that have already received them, reducing unnecessary rebroadcasts. Additionally, a retransmission after negative acknowledgments scheme is described to ensure reliable delivery. The proposed algorithms are reliable, significantly reduce rebroadcasts, and are localized and parameterless. Experimental results show that the proposed methods outperform existing ones in terms of reliability, rebroadcast savings, and communication overhead. The algorithms perform best for networks with average degrees above 4, achieving up to 53% node retransmissions for random unit graphs with 100 nodes. The methods are more efficient than clustering-based approaches, which suffer from high communication overhead for maintaining structure. The proposed algorithms are also more efficient than location-based methods in terms of rebroadcast savings. The algorithms are tested on random unit graphs and show high reachability (over 98.3%) and low latency. The impact of variable maximal backoff, message size, traffic, and mobility is also analyzed, showing that the proposed methods are robust and efficient under various conditions.