Fault tolerant optimized broadcast for wireless ad-hoc networks

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.