A Distributed Shortest-Path Routing Algorithm for Transportation Systems

摘要

This paper presents an algorithm based on Dijkstra's algorithm and the distributed Bellman-Ford algorithm (DBF) for path planning in transportation systems, where distributed algorithms are needed to work along with Wireless Sensor Networks. In our algorithm, each node in the network runs Dijkstra's algorithm on the topology it perceived, which we distinguish from the whole topology by giving the name the perceived map, to construct its shortest-path tree, and through exchanging messages with its neighbors it can renew the perceived map. As every node keeps receiving messages for a predefined time and link-costs in a traffic environment often vary moderately, this algorithm can perform well when more than one link changes its cost at the same time.