An Evolutionary Multi-player Game Model for Two-Hop Routing in Delay Tolerant Networks

Delay-tolerant networks (DTN) are sparse mobile ad hoc networks where contemporaneous end-to-end path is typically not available. Therefore, nodes act as relays for each other to enable data delivery. The cooperation among mobile nodes however can be hindered by selfish users. Incentive schemes are inevitably introduced to regulate the behavior of DTN users. The motivation of this paper is to seek conditions under which cooperators can survive, and even prevail in DTN without incentives. We study the formation of cooperation in DTN routing following an Evolutionary Game Theory (EGT) approach. In particular, the two-hop routing protocol is assumed to be adopted which applies to a large class of DTN routing schemes. We first formulate the two-hop DTN routing as a multi-player game. Using the concept of Evolutionarily Stable Strategy (ESS), we show that defection always dominates cooperation when the population is infinite and well-mixed. Recent developments in evolutionary biology reveal that in finite and structured populations such as graphs, cooperation is nevertheless promoted. We derive a sufficient condition for cooperators to be favored over defectors on K-regular graph. Simulation results validate our theoretical finding, and prove that cooperation indeed can prevail in DTN routing games without incentives.