Title: Overhearing-aware modified Dijkstra's algorithm for multicasting over multi-hop wireless networks

Authors: Rami Halloush

Addresses: Telecommunications Engineering Department, Hijjawi Faculty for Engineering Technology, Yarmouk University, 21163, Irbid, Jordan

Abstract: 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.

Keywords: multi-hop wireless networks; MWNs; network coding; network simulation; multicasting; overhearing awareness; Dijkstra algorithm; shortest-path tree; SPT; simulation.

DOI: 10.1504/IJCNDS.2016.076651

International Journal of Communication Networks and Distributed Systems, 2016 Vol.16 No.3, pp.240 - 260

Received: 27 Apr 2015
Accepted: 14 Nov 2015

Published online: 18 May 2016 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article