Application of Graph Theory in DTN Routing

Delay tolerant network is proposed as a solution for Interplanetary Networks to provide communication between base stations and the satellites. DTNs allow for information to be shared between nodes even in the presence of high delays, which are typical in spatial communications. Routing in delay tolerant networks is a challenging problem in networking research. The common issue of these environments consists in the absence of guarantees about the existence of continuous end-to-end paths between source and destination nodes. Several protocols have been developed to increase the success rate of message delivery, such as probability of meeting between nodes, packet replication and flooding. Important feature of these protocols is using local connection information to find the best path with high likelihood to deliver a message. From a global view, a general disconnected network can have many small clustered mobile nodes. Identifying relevant nodes to carry and deliver messages becomes important in order to reduce message delay and overhead ratio. The proposed method tackles this issue by utilizing articulation nodes among a local sub-graph formed by including all directly connected neighbors of two meeting nodes. Articulation nodes are the cut vertices of this local sub-graph, and their elimination will disconnect the connected subgraph. Packets will be stored in these nodes and forwarded when the connection is established. This process is repeated until messages reach their destinations. The experimental results show that the proposed algorithm performs better than related protocols in terms of delivery rate, overhead ratio and efficiency.