Truthful multipath routing for ad hoc networks with selfish nodes

ABSTRACT

Multiple path routing protocols are shown to be performance-effective alternatives over single-path routing for ad hoc networks. They provide better resistance to link breakage and load balancing. However, these protocols typically assume a cooperative network setting. In practice nodes in an ad hoc network may behave selfishly and may not be willing to forward packets for other nodes freely. One way to stimulate nodes' cooperation is to reimburse forwarding nodes according to their cost such that these nodes get enough incentive. However, selfish nodes may cheat over their cost to maximize their payoff. This necessitates the need for a truthful protocol which maximizes a node's payoff only when it reveals its true cost. In this paper, we present GTMR, a generic mechanism to transform any table-driven multipath routing protocol into a truthful one, and prove that it guarantees truthfulness. Further, we present TMRP - a truthful multipath routing protocol based on AOMDV protocol as an instance of GTMR. A prominent feature of TMRP is that it incurs only 2n control packets for a route discovery and does not require new types of control messages over AOMDV. To the best of our knowledge, this is the lowest overhead incurred for any truthful routing protocols. TMRP can also achieve load balancing without compromising truthfulness. We conduct an extensive simulation study to evaluate the performance of TMRP. Simulation results show that TMRP provides high packet delivery ratio and has low overhead and low end-to-end delay without compromising the overpayment to the nodes.

REFERENCES

• [1]: http://pcl.cs.ucla.edu/projects/glomosim/
• [2]: Aliprantis, Charalambos D. and Chakrabarti, Subir K., Games and Decision Making. 2000. Oxford University Press.
• [3]: 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]
• [4]: Rendong Bai , Mukesh Singhal, DOA: DSR over AODV Routing for Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.10, p.1403-1416, October 2006 [doi>10.1109/TMC.2006.150]
• [5]: S. Buchegger, J.Y. Le-Boudec, Nodes bearing grudges: Towards routing security, fairness, and robustness in mobile ad hoc networks, in: Proceedings of EUROMICRO-PDP'02, 2002
• [6]: 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]
• [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]: 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
• [9]: Jianfeng Cai, Udo Pooch, Play alone or together-truthful and efficient routing in wireless ad hoc networks with selfish nodes, in: Proceeding of MASS'04, 2004
• [10]: Kai Chen , Klara Nahrstedt, iPass: An Incentive Compatible Auction Scheme to Enable Packet Forwarding Service in MANET, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.534-542, March 24-26, 2004
• [11]: J. Crowcroft, R. Gibbens, F. Kelly, S. Ostring, Modelling incentives for collaboration in mobile ad hoc networks, in: Proceedings of WiOpt'03
• [12]: http://www.stanford.edu/yl314/ape/paper.ps
• [13]: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• [14]: Johnson, David B. and Maltz, David A., Dynamic source routing in ad hoc wireless networks. Mobile Computing. 153-181.
• [15]: Haiyun Luo , Ramachandran Ramjee , Prasun Sinha , Li (Erran) Li , Songwu Lu, UCAN: a unified cellular and ad-hoc network architecture, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939021]
• [16]: M.K. Marina, S.R. Das, Ad hoc on-demand multipath distance vector (aomdv) routing, in: Proceedings of ICNP'01, 2001
• [17]: 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]
• [18]: Pietro Michiardi, Refik Molva, Prevention of denial of service attacks and selfishness in mobile ad hoc networks, January 2002, Research Report RR-02-063
• [19]: P. Michiardi, R. Molva, A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks, in: Proceedings of WiOpt'03
• [20]: Hugo Miranda, Luis Rodrigues, Preventing selfishness in open mobile ad hoc networks, in: Proceedings of 7th CaberNet Radicals Workshop, October 2002
• [21]: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• [22]: K. Paul, D. Westhoff, Context aware detection of selfish nodes in dsr based ad-hoc networks, in: Proceedings of IEEE VTC'02, 2002
• [23]: C. Perkins, Ad-hoc on-demand distance vector routing, Nov 1997, In Internet draft RFC
• [24]: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• [25]: J. Raju, J. Garcia-Luna-Aceves, A new approach to on-demand loop-free multipath routing, in: Proceedings of IEEE ICCCN'99, 1999
• [26]: Naouel Ben Salem , Levente Buttyán , Jean-Pierre Hubaux , Markus Jakobsson, A charging and rewarding scheme for packet forwarding in multi-hop cellular networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778418]
• [27]: V. Srinivasan, P. Nuggehalli, C. Chiasserini, R. Rao, Cooperation in wireless ad hoc networks, in: Proceedings of IEEE Infocom'03, 2003
• [28]: Tracy, Camp, Boleng, Jeff and Davies, Vanessa, A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications. v2 i5. 483-502.
• [29]: Yongwei Wang, Venkata C. Giruka, Mukesh Singhal, A fair distributed solution for selfish node problem in mobile ad hoc networks, in: Proceedings of ADHOCNOW'04, 2004
• [30]: 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]
• [31]: S. Zhong, Y.R. Yang, J. Chen, Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks, in: Proceedings of Infocom'03, Mar 2003

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
Multipath routing, Nodes cooperation and ad hoc networks, Selfish nodes, Truthfulness