A geometric routing protocol in disruption tolerant network

Abstract

We describe a novel geometric localised routing protocol in disruption (delay) tolerant network (DTN). Although DTNs do not guarantee the connectivity of the network all the time, geometric location information could still be used to make routing decisions in a store-and-forward way. Geometric planar spanners, especially local Delaunay triangulation (LDT) can also be used in DTNs to provide a good routing graph with constant stretch factor and shorter paths during communications. In this work, we design local distributed solutions to extract spanning trees from LDT graphs from source to destination. Our protocol resorts to flooding packets along trees with high probability of being delivered without significant delays. Through experimentation, we have shown that the proposed routing protocol achieves higher delivery ratios with lower delays and limited storage requirements than the benchmark epidemic routing protocol.

Keywords:

• routing
• disruption tolerant network
• Delaunay triangulation
• spanner
• local algorithm