Cooperative packet relaying model for wireless ad hoc networks

ABSTRACT

In wireless ad hoc networks such as mobile ad hoc networks and sensor networks, most of the functions (routing, mobility management, and security) must rely on cooperation between nodes. Every node in these networks is both end host (it generates its own data and routing traffic) and infrastructure (it forwards traffic for others), but rational nodes have no incentive to cooperatively forward traffic for others, since this kind of forwarding is not costless. Thus, we are motivated to use game theory to analyze cooperative mechanisms, and derive incentive strategies enforcing cooperation in forwarding. Unlike traditional approaches, in this paper, we introduce a novel and interdisciplinary simulation-based analysis scheme to the networking community in game-theoretic settings. Moreover, we investigate noise models and show some counterintuitive simulation results in presence of noise.

REFERENCES

• 1: G. Hardin. The Tragedy of the Commons. In Science, Vol. 162, No. 3859, pp. 1243--1248, December 1968.
• 2: 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]
• 3: 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]
• 4: Tirthankar Ghosh , Niki Pissinou , Kami Makki, Towards designing a trusted routing solution in mobile ad hoc networks, Mobile Networks and Applications, v.10 n.6, p.985-995, December 2005 [doi>10.1007/s11036-005-4454-4]
• 5: 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 (WCNC'04), Atlanta, GA, USA, March 2004.
• 6: 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]
• 7: 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
• 8: 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.
• 9: B. Raghavan and A. C. Snoeren. Priority forwarding in ad hoc networks with self-interested parties. In Proc. Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, 2003.
• 10: V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao. Cooperation in wireless ad hoc networks. In Proc. IEEE Infocom 2003, San Francisco, CA, March 2003.
• 11: Z. Fang and B. Bensaou. Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In Proc. IEEE Infocom 2004, Hong Kong, China, March 2004.
• 12: V. Srivastava, J. Neel, A. B. MacKenzie, R. Menon, L. A. DaSilva, J. E. Hicks, J. H. Reed, and R. P. Gilles. Using game theory to analyze wireless ad hoc networks. In IEEE Communications Surveys and Tutorials, vol. 7, pp. 46--56, 2005.
• 13: L. A. DaSilva and V. Srivastava. Node Participation in Ad-hoc and Peer-to-peer Networks: A Game-theoretic Formulation. In Proc. Workshop on Games and Emergent Behavior in Distributed Computing Environments, September 18, 2004, Birmingham, U.K.
• 14: 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]
• 15: Sheng Zhong , Li (Erran) Li , Yanbin Grace Liu , Yang (Richard) Yang, On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080841]
• 16: Weizhao Wang , Stephan Eidenbenz , Yu Wang , Xiang-Yang Li, OURS: optimal unicast routing systems in non-cooperative wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161134]
• 17: R. Axelrod and W. D. Hamilton. The evolution of cooperation. In Science, 211: 1390--1396, 1981.
• 18: G. J. Mailath and L. Samuelson. Repeated Games and Reputations: Long-Run Relationships. Oxford University Press, 2006.
• 19: Lu Yan , Stephen Hailes , Licia Capra, Analysis of Packet Relaying Models and Incentive Strategies in Wireless Ad Hoc Networks with Game Theory, Proceedings of the 22nd International Conference on Advanced Information Networking and Applications (aina 2008), p.1062-1069, March 25-28, 2008 [doi>10.1109/AINA.2008.28]
• 20: L. Yan and S. Hailes. Designing incentive packet relaying strategies for wireless ad hoc networks with game theory. In Proc. IFIP Conference on Wireless Sensors and Actor Networks (WSAN'08), Ottawa, Canada, 2008.
• 21: R. Axelrod. The evolution of cooperation. New York, 1984.
• 22: X. Yao and P. J. Darwen. An Experimental Study of N-Person Iterated Prisoner's Dilemma Game. In Informatica, 18:435--450, 1994.
• 23: J. Wu, R. Axelrod. How to Cope with Noise in the Iterated Prisoner's Dilemma. In Journal of Conflict Resolution, vol. 39, no. 1, pp. 183--189, March, 1995.
• 24: R. Hoffman. Twenty years on: The evolution of cooperation revisited. In Journal of Artificial Societies and Simulations, 3(2), 2000.
• 25: J. Bendor, R. M. Kramer, S. Stout. When in Doubt...: Cooperation in a Noisy Prisoner's Dilemma. In Journal of Conflict Resolution, 12 (35): pp. 691--719, 1991.
• 26: J. Bendor. Uncertainty and the Evolution of Cooperation. In Journal of Conflict Resolution, 12(37): pp. 709--734, 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Economics, Experimentation

Keywords:
cooperative, game theory, incentive, noise, packet forwarding, packet relaying, strategy, wireless ad hoc networks