Achieving cooperation in multihop wireless networks of selfish nodes

Fabio Milan, Juan José Jaramillo, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceeding from the 2006 Workshop on Game Theory for Communications and Networks
StatePublished - 2006
Event2006 Workshop on Game Theory for Communications and Networks - Pisa, Italy
Duration: Oct 14 2006Oct 14 2006

Publication series

NameACM International Conference Proceeding Series


Other2006 Workshop on Game Theory for Communications and Networks

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Achieving cooperation in multihop wireless networks of selfish nodes'. Together they form a unique fingerprint.

Cite this