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.

REFERENCES

• 1: G. Hardin, "The Tragedy of the Commons," Science, Vol. 162, No. 3859, pp. 1243--1248, December 1968.
• 2: L. Blazevic, L. Buttyán, S. Capkun, S. Giordano, J. P. Hubaux, and J.-Y. Le Boudec, "Self-Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes," IEEE Communications Magazine, vol. 39, no. 6, pp. 166--174, June 2001.
• 3: S. Zhong, J. Chen, and Y. R. Yang, "Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad Hoc Networks," in Proc. of IEEE Infocom 2003, San Francisco, CA, USA, April 2003, pp. 1987--1997.
• 4: Q. He, D. Wu and P. Khosla, "SORI: A Secure and Objective Reputation-based Incentive Scheme for Ad hoc Networks," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC2004), Atlanta, GA, USA, March 2004, pp. 825--830.
• 5: R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan, "Sustaining Cooperation in Multihop Wireless Networks," in Proc. second USENIX Symposium on Networked System Design and Implementation (NSDI 05), Boston, MA, USA, May 2005.
• 6: ISO/IEC and IEEE Draft International Standards, "Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications," ISO/IEC 8802-11, IEEE P802.11/D10, Jan. 1999.
• 7: F. A. Tobagi and L. Kleinrock, "Packet Switching in Radio Channels: Part II - The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution," IEEE Transactions on Communications, vol. COM-23, no. 12, pp. 1417--1433, 1975.
• 8: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 9: F. Milan, J. J. Jaramillo and R. Srikant, "Performance Analysis of Reputation-Based Mechanisms for Multihop Wireless Networks," in Proc. of 40th Conference on Information Sciences and Systems (CISS 2006), Princeton, NJ, USA, March, 2006
• 10: R. Axelrod, "The Emergence of Cooperation among Egoists," The American Political Science Review, vol. 75, no. 2, pp. 306--318, June 1981.
• 11: Mark Felegyhazi , Jean-Pierre Hubaux , Levente Buttyan, Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.5, p.463-476, May 2006 [doi>10.1109/TMC.2006.68]
• 12: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 13: R. Anderson and M. Kuhn, "Tamper resistance - a cautionary note," in Proc. Second USENIX Workshop on Electronic Commerce, Oakland, CA, Nov. 1996, pp. 1--11.
• 14: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 15: V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao, "Cooperation in wireless ad hoc networks," in Proc. IEEE INFOCOM 2003, vol. 2, San Francisco, CA, Mar./Apr. 2003, pp. 808--817.
• 16: R. Axelrod, "On Six Advances in Cooperation Theory," in Analyse & Kritik - Special Edition on the Evolution of Cooperation, Vol. 22, Stuttgart, Germany, 2000
• 17: S. Bansal and M. Baker, "Observation-based Cooperation Enforcement in Ad Hoc Networks," Tech. Rep., Stanford University, CA, July 2003.
• 18: M. Tamer Refaei , Vivek Srivastava , Luiz DaSilva , Mohamed Eltoweissy, A Reputation-based Mechanism for Isolating Selfish Nodes in Ad Hoc Networks, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.3-11, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.7]
• 19: D. Fudenberg and J. Tirole, "Game Theory," MIT Press, Cambridge, MA, USA, 1991.
• 20: J. Wu and R. Axelrod, "How to Cope with Noise in the Iterated Prisoner's Dilemma," The Journal of Conflict Resolution, vol. 39, no. 1, pp. 183--189, March 1995.
• 21: Y. E. Sagduyu and A. Ephremides, "Some Optimization Trade-Offs in Wireless Network Coding," in Proc. of 40th Conference on Information Sciences and Systems (CISS 2006), Princeton, NJ, USA, March 2006
• 22: J. A. Silvester and L. Kleinrock, "On the Capacity of Multihop Slotted ALOHA Networks with Regular Structure," IEEE Transactions on Communications, vol. COM-31, no. 8, pp. 974--982, 1983.
• 23: P. Gupta and P. R. Kumar, "The Capacity of Wireless Networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.3 Network Operations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems