Indexing Based Multi-Level Clustering Routing Algorithm in Public Transportation Delay Tolerant Networks

In the wireless networks which consist of vehicles of the public transportation system, the topology changes rapidly and the links between nodes connect intermittently due to the high mobility. It is a classic application scenario of delay tolerant networks (DTN). The characteristic of node in the public transportation system determines that its mobility (such as time and path) follows a special rule. Based on this characteristic, an abstract topology of DTN is presented and a new communication efficiency weight is defined. It can provide more accurate evaluation standard for describing the communication capability between nodes pair than before. By computing the communication efficiency weight of nodes, the nodes which have similar mobility model can be recognized. An indexing-based multi-level clustering algorithm is proposed to cluster the nodes which have stronger communication capability with each other. A novel DTN routing algorithm is designed on this cluster construction, in which the cluster information of each node can provide reference for the routing algorithm to forward packets when two nodes encounter. Experiments based on the pre-cluster information prove that the proposed routing algorithm is more efficient than other DTN routings used in the high speed public transportation system.