Mathematical analysis of self-pruning and a new dynamic probabilistic broadcast for MANETs

Self-pruning broadcasting algorithm exploits neighbor knowledge to reduce redundant retransmissions in mobile ad hoc wireless networks (MANETs). Although in self-pruning, only a subset of nodes forward the message based on certain forwarding rule, it belongs to one of the reliable broadcasting algorithm category where a broadcast message is guaranteed (at least algorithmically) to reach all the nodes in the network. In this paper, we develop an analytical model to determine expected number of forwarding nodes required to complete a broadcast in self-pruning algorithm. The derived expression is a function of various network parameters (such as, network density and distance between nodes) and radio transceiver parameters (such as transmission range). Moreover, the developed mathematical expression provides us a better understanding of the highly complex packet forwarding pattern of self-pruning algorithm and valuable insight to design a new broadcasting heuristic. The proposed new heuristic is a dynamic probabilistic broadcast where rebroadcast probability of each node is dynamically determined from a developed mathematical expression. Extensive simulation experiments have been conducted to validate the accuracy of the analytical model, as well as, to evaluate the efficiency of the proposed heuristic. Performance analysis shows that the proposed heuristic outperforms the static probabilistic broadcasting algorithm and an existing solution proposed by Bahadili.