Articulation Node Based Routing in delay tolerant networks
Li Ding, Bo Gu, Xiaoyan Hong, Brandon J. Dixon · 2009
Routing in delay tolerant networks (DTNs) is a challenging problem in networking research. Existing DTN routing solutions have used many approaches to increase the success rate of message delivery, such as meeting probabilities between nodes, packet replication and flooding. One important feature of these protocols is using local connection information to find the “best” path with high likelihood to deliver a packet. In this paper, we propose a new routing protocol called ANBR (Articulation Node Based Routing). From a global view, a general disconnected network can have many small instantaneously clustered mobile nodes. Mobility allows nodes carrying messages to deliver them to other clusters. Selecting appropriate nodes to carry and deliver messages becomes important in order to reduce message delay and overhead. The proposed ANBR tackles this issue by utilizing articulation nodes among a local sub-graph formed by including all neighbors of two “meeting” nodes. Articulation nodes are the articulation points or cut vertices of this local sub-graph, and by definition are the nodes, whose removal will disconnect the graph. Thus, these articulation nodes are more likely to be able to deliver messages outside the local cluster. Packets will be buffered in these nodes and forwarded to other articulation nodes when they meet. The process repeats until messages reach their destinations. We evaluate our algorithm by using real world data from the MIT reality mining project. The simulation results show that ANBR algorithm performs better than related protocols in terms of delivery rate and efficiency.