A Markov Routing Algorithm for Mobile DTNs based on Spatio-Temporal Modeling of Human Movement Data

摘要

Store-carry-forward communication, which is set as the heart of all routing protocols for mobile disruption-tolerant networks (DTNs), exploits nodes' mobility to bring messages closer to their destinations by exchanging messages across mobile nodes when they meet in close proximity. Understanding the subtle characteristics of human mobility leads to better service and application provisioning for mobile DTNs. We use GPS traces collected from multiple mobile users to empirically study different aspects of human mobility. Various Markov models (first, second and third-order) are estimated from users' mobility data. Based on empirical evidence, second-order Markov models are deemed sufficient to estimate mobile users' future locations accurately. These Markov models permit the design of a new routing algorithm for mobile DTNs capable of more efficiently routing data objects to their destination locations. The relay selection in this routing algorithm is based on mobile users' absorption times to the destination location. Simulations show that the proposed routing algorithm consumes less energy than legacy epidemic routing algorithms without excessive transmission delays.