Abstract:
Many broadcasting protocols for ad-hoc wireless networks perform poorly in situations when network
becomes untrusted. In real environment, any node can be unavailable or be unable to receive broadcast
packet or to forward the received packet for many reasons. To improve the reliability of broadcasting in
the face of limited trustworthiness of nodes, multicover dominant pruning (MDP) [2] covers its 2-hop
neighbors multiple times. Here, as the total number of transmissions (forward nodes) is generally used as
the cost criterion for broadcasting, MDP costs too much redundancy. In this paper, we propose three
better fault-tolerant approximation algorithms: multicover total dominant pruning, multicover partial
dominant pruning and multicover improved dominant pruning. All these algorithms not only utilize 2-hop
neighborhood information more effectively to reduce redundant transmissions but also significantly
improve the reachability of nodes in an unreliable ad-hoc wireless network. Extensive simulation
experiments have been conducted to evaluate the efficiency of the proposed heuristics. Performance
analysis shows that the proposed heuristics significantly outperforms the multicover dominant pruning
broadcasting algorithm.
