Constructing time-varying contact graphs for heterogeneous delay tolerant networks

Human mobility, hence the movement pattern of mobile devices, often confines to relatively local geographic areas. Such a movement pattern reduces the opportunities for a message to be disseminated to a more global geographical region using the encounter-based “store-carry-forward” routing approach. On the other hand, different local areas often overlap to cover the entire region. A feasible communication architecture to help message dissemination is to deploy static storage-and-communication devices at those overlapping areas to serve as relays between the local areas. In this paper, we introduce the method to derive the simulation model for this heterogeneous network from contact trace and GPS trace of buses. Our main focus is to model communication properties between the static nodes and the mobile nodes. Typically, they are time-varying link delays formed by a collection of multiple mobile nodes. We further use a Markovian model to describe the time dependency among link delays at each static nodes and use the states to develop a network model for simulation. In the paper, we present simulation results to validate the reproduction of the mobility with the original traces by comparing routing performance. We show that the proposed network model can be used for performance evaluations with inherited realistic. The contributions of this work reside in the reproducibility to the real world traces and its flexibility in configurations. Further, it is the first simulator that enables to produce contact graph for a heterogeneous network with time-varying link properties. Its ability goes beyond simply calculating encounter events, but is well suitable for protocol evaluation in opportunistic networks, mobile social networks and delay tolerant networks.