Overhearing-aware modified Dijkstra's algorithm for multicasting over multi-hop wireless networks
Rami D. Halloush · International Journal of Communication Networks and Distributed Systems · 2016
In multicasting, there is a need to efficiently specify the paths connecting a source node to the different destination nodes. A common method to achieve that is to use a shortest-path tree (SPT) algorithm, such as Dijkstra%s algorithm. A multicasting application, however, that is intended for a multi-hop wireless network should be designed in a way that considers the characteristics of such network. One important characteristic is overhearing, which means that a transmission from one node could be heard by many nodes other than the intended receiver. We propose modifying Dijkstra%s algorithm to take advantage of overhearing. As opposed to the conventional Dijkstra%s algorithm where path costs used to build an SPT remain fixed during the course of the algorithm, we propose estimating the overhearing opportunities at each iteration of the algorithm and modifying path costs accordingly. Simulation results demonstrate up to 68% throughput enhancement over the conventional Dijkstra's algorithm.