Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks

In self-organizing ad hoc networks, all the networking functions rely on the contribution of the participants. As a basic example, nodes have to forward packets for each other in order to enable multi-hop communication. In recent years, incentive mechanisms have been proposed to give nodes incentive to cooperate, especially in packet forwarding. However, the need for these mechanisms was not formally justified. In this paper, we address the problem of whether cooperation can exist without incentive mechanisms. We propose a model based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. We prove theorems about the equilibrium conditions for both cooperative and non-cooperative strategies. We perform simulations to estimate the probability that the conditions for a cooperative equilibrium hold in randomly generated network scenarios. As the problem is involved, we deliberately restrict ourselves to a static configuration. We conclude that in static ad hoc networks - where the relationships between the nodes are likely to be stable - cooperation needs to be encouraged. forwarding. However, the need for these mechanisms was not formally justified. In this paper, we address the problem of whether cooperation can exist \emph{without} incentive mechanisms. We propose a model based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. We prove theorems about the equilibrium conditions for both cooperative and non-cooperative strategies. We perform simulations to estimate the probability that the conditions for a cooperative equilibrium hold in randomly generated network scenarios. As the problem is involved, we deliberately restrict ourselves to a static configuration. We conclude that in static ad hoc networks -- where the relationships between the nodes are likely to be stable -- cooperation needs to be encouraged.