Proposal of Fibonacci Heap in the Dijkstra Algorithm for Low-power Ad-hoc Mobile Transmissions

Abstract

Mobile devices have become indispensable to communication over the last decade. In a hypothetical scenario in which conventional forms of connection such as antennas and satellites are not available, other forms of information propagation must be used. Ad-hoc broadcasts are strategies for maintaining communication between devices in these situations, however, they require high transmission power. This article proposes the use of priority queues, such as the Fibonacci heap and the binary heap in the Dijkstra algorithm, in order to reduce its computational cost in the search for the smallest network route. From the limitation of the signal strength to reach the nearest device, our results obtained lower transmission power compared to the standard device settings. Simulations show that a fibonacci heap has higher performance than binary heap in networks with higher number of connections. This way, the implementation of the fibonacci heap brings improvements in the computational cost of the algorithm. In addition, we show that the calculation of the smallest route is directly connected to the choice of the path with the lowest transmission power.