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

Abstract

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
DOIs
StatePublished - Dec 1 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
Volume199

Other

Other2006 Workshop on Game Theory for Communications and Networks
CountryItaly
CityPisa
Period10/14/0610/14/06

Fingerprint

Wireless networks
Network routing
Throughput
Costs

ASJC Scopus subject areas

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

Cite this

Milan, F., Jaramillo, J. J., & Srikant, R. (2006). Achieving cooperation in multihop wireless networks of selfish nodes. In Proceeding from the 2006 Workshop on Game Theory for Communications and Networks [1190197] (ACM International Conference Proceeding Series; Vol. 199). https://doi.org/10.1145/1190195.1190197

Achieving cooperation in multihop wireless networks of selfish nodes. / Milan, Fabio; Jaramillo, Juan José; Srikant, R.

Proceeding from the 2006 Workshop on Game Theory for Communications and Networks. 2006. 1190197 (ACM International Conference Proceeding Series; Vol. 199).

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

Milan, F, Jaramillo, JJ & Srikant, R 2006, Achieving cooperation in multihop wireless networks of selfish nodes. in Proceeding from the 2006 Workshop on Game Theory for Communications and Networks., 1190197, ACM International Conference Proceeding Series, vol. 199, 2006 Workshop on Game Theory for Communications and Networks, Pisa, Italy, 10/14/06. https://doi.org/10.1145/1190195.1190197
Milan F, Jaramillo JJ, Srikant R. Achieving cooperation in multihop wireless networks of selfish nodes. In Proceeding from the 2006 Workshop on Game Theory for Communications and Networks. 2006. 1190197. (ACM International Conference Proceeding Series). https://doi.org/10.1145/1190195.1190197
Milan, Fabio ; Jaramillo, Juan José ; Srikant, R. / Achieving cooperation in multihop wireless networks of selfish nodes. Proceeding from the 2006 Workshop on Game Theory for Communications and Networks. 2006. (ACM International Conference Proceeding Series).
@inproceedings{4e8989c5f7e14d3a8d60f38e679d0f87,
title = "Achieving cooperation in multihop wireless networks of selfish nodes",
abstract = "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.",
author = "Fabio Milan and Jaramillo, {Juan Jos{\'e}} and R. Srikant",
year = "2006",
month = "12",
day = "1",
doi = "10.1145/1190195.1190197",
language = "English (US)",
isbn = "159593507X",
series = "ACM International Conference Proceeding Series",
booktitle = "Proceeding from the 2006 Workshop on Game Theory for Communications and Networks",

}

TY - GEN

T1 - Achieving cooperation in multihop wireless networks of selfish nodes

AU - Milan, Fabio

AU - Jaramillo, Juan José

AU - Srikant, R.

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34748884356&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34748884356&partnerID=8YFLogxK

U2 - 10.1145/1190195.1190197

DO - 10.1145/1190195.1190197

M3 - Conference contribution

AN - SCOPUS:34748884356

SN - 159593507X

SN - 9781595935076

T3 - ACM International Conference Proceeding Series

BT - Proceeding from the 2006 Workshop on Game Theory for Communications and Networks

ER -