A Novel Shortest Path Routing Algorithm for Wireless Data Collection in Transportation Networks

Abstract

This paper presents a heuristic solution to the shortest path routing problem in a road network where source and target locations are defined in a continuous plane. The problem arises when a wireless mobile entity is required to communicate with wireless nodes deployed apart from each other with a distance greater than their communication range and the mobility is limited with the transportation network layout. The goal is constructing a route which minimizes the mobility cost. Travelling salesman problem (TSP) is a classic discrete optimization problem to identify optimal routes between particular cities. Unlike TSP, our problem defines a neighborhood based on the node location and wireless communication range and seeks the optimal path between the neighborhoods. This paper defines mobility cost in terms of distance and delay separately. However, based on the defined cost function, the solution is applicable to other metrics as well including energy consumption.