1st International ICST Workshop on Game Theory for Networks

Research Article

Achieving Cooperation in Multihop Wireless Networks of Selfish Nodes

  • @INPROCEEDINGS{10.1145/1190195.1190197,
        author={Fabio  Milan and Juan Jose  Jaramillo and R. Srikant},
        title={Achieving Cooperation in Multihop Wireless Networks of Selfish Nodes},
        proceedings={1st International ICST Workshop on Game Theory for Networks},
  • Fabio Milan
    Juan Jose Jaramillo
    R. Srikant
    Year: 2012
    Achieving Cooperation in Multihop Wireless Networks of Selfish Nodes
    DOI: 10.1145/1190195.1190197
Fabio Milan1,*, Juan Jose Jaramillo2,*, R. Srikant2,*
  • 1: Dipartimento di Elettronica, Politecnico di Torino, Turin, Italy
  • 2: Coordinated Science Laboratory, Dept. of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign
*Contact email: fabio.milan@polito.it, jjjarami@uiuc.edu, rsrikant@uiuc.edu


In a multihop wireless network, routing a packet from source to destination requires cooperation among nodes. If nodes are selfish, reputation-based mechanisms can be used to sustain cooperation without resorting to a central authority. Within a hop-by-hop reputation-based mechanism, every node listens to its relaying neighbors, and the misbehaving ones are punished by dropping a fraction of their packets, according to a Tit-for-tat strategy. Packet collisions may prevent a node from recognizing a correct transmission, distorting the evaluated reputation. Therefore, even if all the nodes are willing to cooperate, the retaliation triggered by a perceived defection may eventually lead to zero throughput. A classical solution to this problem is to add a tolerance threshold to the pure Tit-for-tat strategy, so that a limited number of defections will not be punished. In this paper, we propose a game-theoretic model to study the impact of collisions on a hop-by-hop reputation-based mechanism for regular networks with uniform random traffic. Our results show that the Nash Equilibrium of a Generous Tit-for-tat strategy is cooperative for any admissible load, if the nodes are sufficiently far-sighted, or equivalently if the value for a packet to the nodes is sufficiently high with respect to the transmission cost. We also study two more severe punishment schemes, namely One-step Trigger and Grim Trigger, that can achieve cooperation under milder conditions.