Approach-and-Roam (AaR): A Geographic Routing Scheme for Delay/Disruption Tolerant Networks

• Published in: IEEE transactions on vehicular technology 2014-01, Vol.63 (1), p.266-281
• Main Authors: Yue Cao, Zhili Sun, Cruickshank, Haitham, Fang Yao
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Applied sciences; Bandwidth; Computer networks; Delay; Delay/disruption-tolerant networks (DTNs); Delays; Density; Design. Technologies. Operation analysis. Testing; Electronics; Exact sciences and technology; Extraterrestrial measurements; geographic routing; Integrated circuits; Messages; Network topologies; Networks; Nickel; nodal mobility; Organization and planning of networks (techniques and equipments); Real time; Replication; Routing; Routing (telecommunications); Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices; sparse networks; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Transmission and modulation (techniques and equipments)
• ISSN: 0018-9545; 1939-9359
• DOI: 10.1109/TVT.2013.2272547

Considering that delay/disruption-tolerant networks (DTNs) suffer from a large variation of network topology, geographic routing is an alternative scheme that utilizes real-time geographic information instead of network topology information. However, the real-time geographic information of mobile destination is likely unavailable due to sparse network density. With this in mind, we propose a geographic routing scheme by relying on historical geographic information to estimate the movement range of destination. The idea is to make efficient message replication toward this estimated range via the proposed Approach Phase to reduce routing overhead. Meanwhile, the effective message replication within this range is guaranteed via the proposed Roam Phase to increase the message delivery ratio. We further propose a novel scheme to handle the local maximum problem for geographic routing in sparse networks. Simulation results obtained assuming the maps of three real world cities, namely, Helsinki, Finland; Karlsruhe, Germany; and Manhattan, New York City, USA, show an advantage of the proposed Approach-and-Roam (AaR) over the compared algorithms in terms of delivery ratio, average delivery latency, and overhead ratio.