Efficient multicasting for delay tolerant networks using graph indexing

摘要: In Delay Tolerant Networks (DTNs), end-to-end connectivity between nodes does not always occur due to limited radio coverage, node mobility and other factors. Remote communication may assist in guaranteeing delivery. However, it has a considerable cost, and consequently, minimizing it is an important task. For multicast routing, the problem is NP-hard, and naive approaches are infeasible on large problem instances. In this paper we define the problem of minimizing the remote communication cost for multicast in DTNs. Our formulation handles the realistic scenario in which a data source is continuously updated and nodes need to receive recent versions of data. We analyze the problem in the case of scheduled trajectories and known traffic demands, and propose a solution based on a novel graph indexing system. We also present an adaptive extension that can work with limited knowledge of node mobility …