A∗ algorithm-based initial route construction for mobile relay on WSN

Energy consumption is the most crucial issue in Wireless Sensor Network (WSN). Mobile relay is one of the techniques for saving the energy in WSN. In mobile relay, initial route construction determines the sequence of relaying nodes, which is provided to mobile relay algorithms. Several methods have been proposed for determining the initial route for mobile relay in WSN. We have proposed Battery-Aware Initial Route construction by Dijkstra´s Algorithm (BAIR-D). BAIR-D employs Dijkstra´s algorithm to find the initial route. It takes into account node´s battery level into the cost function, such that this algorithm avoids using node with low battery levels. We have implemented this method in a centralized fashion. However, from a scalability point of view, the initial route construction should be performed distributedly In this paper, we present a new initial route construction based on A-star algorithm, which is referred as BAIR-A*. Unlike BAIR-D, BAIR-A* is suitable for distributed implementation, because the method can significantly reduce the communication needed for initial route construction. We also present the distributed algorithm of BAIR-A*. We demonstrate the effectiveness of BAIR-A by using numerical simulations.