DARWIN: distributed and adaptive reputation mechanism for wireless ad-hoc networks

ABSTRACT

Mobile ad-hoc networks are deployed under the assumption that participating nodes are willing to forward other nodes' packets. In reputation-based mechanisms cooperation is induced by means of a threat of partial or total disconnection from the network if a node is non-cooperative; however packet collisions and interference may make cooperative nodes appear selfish sometimes. In this paper we use a simple network model to first study the performance of some proposed reputation strategies and then present a new mechanism that we call DARWIN (Distributed and Adaptive Reputation mechanism for WIreless ad-hoc Networks). The idea is to avoid a retaliation situation after a node has been falsely perceived as selfish so cooperation can be restored quickly. We prove that our strategy is robust to imperfect measurements, is collusion-resistant and can achieve full cooperation among nodes.

REFERENCES

• 1: Luzi Anderegg , Stephan Eidenbenz, Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939011]
• 2: R. Axelrod. The emergence of cooperation among egoists. The American Political Science Review, 75(2):306--318, June 1981.
• 3: S. Bansal and M. Baker. Observation-based cooperation enforcement in ad hoc networks. Technical report, Stanford University, Stanford, CA, July 2003.
• 4: R. Boyd. Mistakes allow evolutionary stability in the repeated prisoner's dilemma game. Journal of Theoretical Biology, 136(1):47--56, Jan. 1989.
• 5: 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]
• 6: Levente Buttyán , Jean-Pierre Hubaux, Enforcing service availability in mobile ad-hoc WANs, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 7: 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]
• 8: J. Crowcroft, R. Gibbens, F. Kelly, and S. Östring. Modelling incentives for collaboration in mobile ad hoc networks. In Proc. WiOpt '03, France, Mar. 2003.
• 9: D. Fudenberg and J. Tirole. Game Theory. The MIT Press, Cambridge, MA, Aug. 1991.
• 10: Q. He, D. Wu, and P. Khosla. SORI: A secure and objective reputation-based incentive scheme for ad-hoc networks. In Proc. IEEE Wireless Communications and Networking Conference (WCNC '04), volume 2, pages 825--830, Atlanta, GA, Mar. 2004.
• 11: Ratul Mahajan , Maya Rodrig , David Wetherall , John Zahorjan, Sustaining cooperation in multi-hop wireless networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.231-244, May 02-04, 2005
• 12: 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]
• 13: Pietro Michiardi , Refik Molva, Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks, Proceedings of the IFIP TC6/TC11 Sixth Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security, p.107-121, September 26-27, 2002
• 14: P. Michiardi and R. Molva. Analysis of coalition formation and cooperation strategies in mobile ad hoc networks. Ad Hoc Networks, 3(2):193--219, Mar. 2005.
• 15: Fabio Milan , Juan José Jaramillo , R. Srikant, Achieving cooperation in multihop wireless networks of selfish nodes, Proceeding from the 2006 workshop on Game theory for communications and networks, October 14-14, 2006, Pisa, Italy [doi>10.1145/1190195.1190197]
• 16: J. Mundinger and J.-Y. Le Boudec. The impact of liars on reputation in social networks. In Proc. of Social Network Analysis: Advances and Empirical Applications Forum, Oxford, UK, July 2005.
• 17: 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]
• 18: V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao. Energy efficiency of ad hoc wireless networks with selfish users. In Proc. European Wireless Conference, Florence, Italy, Feb. 2002.
• 19: V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao. Cooperation in wireless ad hoc networks. In Proc. IEEE INFOCOM '03, volume 2, pages 808--817, San Francisco, CA, Mar./Apr. 2003.
• 20: R. Sugden. The Economics of Rights, Cooperation and Welfare. Blackwell Publishing, 1986.
• 21: J. Wu and R. Axelrod. How to cope with noise in the iterated prisoner's dilemma. The Journal of Conflict Resolution, 39(1):183--189, Mar. 1995.
• 22: S. Zhong, J. Chen, and Y. R. Yang. Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks. In Proc. IEEE INFOCOM '03, volume 3, pages 1987--1997, San Francisco, CA, Mar./Apr. 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks; Wireless communication; Distributed networks

General Terms:
Algorithms, Design, Security, Theory

Keywords:
ad hoc networks, game theory, reputation mechanisms, wireless networks