Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents

ABSTRACT

We introduce a game-theoretic setting for routing in a mobile ad hoc network that consists of greedy, selfish agents who accept payments for forwarding data for other agents if the payments cover their individual costs incurred by forwarding data. In this setting, we propose Ad hoc-VCG, a reactive routing protocol that achieves the design objectives of truthfulness (i.e., it is in the agents' best interest to reveal their true costs for forwarding data) and cost-efficiency (i.e., it guarantees that routing is done along the most cost-efficient path) in a game-theoretic sense by paying to the intermediate nodes a premium over their actual costs for forwarding data packets. We show that the total overpayment (i.e., the sum of all premiums paid) is relatively small by giving a theoretical upper bound and by providing experimental evidence. Our routing protocol implements a variation of the well-known mechanism by Vickrey, Clarke, and Groves in a mobile network setting. Finally, we analyze a very natural routing protocol that is an adaptation of the Packet Purse Model [8] with auctions in our setting and show that, unfortunately, it does not achieve cost-efficiency or truthfulness.

REFERENCES

• 1: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 3: M. Baker, E. Fratkin, D. Guitierrez, T. Li, Y.Liu, V. Vijayaraghavan; Ad hoc Participation Economy; May 2001.
• 4: Sonja Buchegger , Jean Ives Le Boundec, Coopertive Routing in Mobile Ad-hoc Networks: Current Efforts Against Malice and Selfishness, Informatik bewegt: Informatik 2002 - 32. Jahrestagung der Gesellschaft für Informatik e.v. (GI), p.513-517, September 30-October 03, 2002
• 5: S. Buchegger, J. Le Boudec; Nodes Bearing Grudges: Towards Routing Security, Fairness, and Robustness in Mobile Ad Hoc Networks; in: Proceedings of the Tenth Euromicro Workshop on Parallel, Distributed and Network-based Processing, pp. 403 - 410, IEEE Computer Society, 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, 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: L. Buttyan and J. Hubaux; Nuglets: a virtual currency to stimulate cooperation in self-organized ad hoc networks; in: Technical Report EPFL, DSC, 2001.
• 9: 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]
• 10: Pierpaolo Bergamo , Alessandra Giovanardi , Andrea Travasoni , Daniela Maniezzo , Gianluca Mazzini , Michele Zorzi, Distributed power control for energy efficient routing in ad hoc networks, Wireless Networks, v.10 n.1, p.29-42, January 2004 [doi>10.1023/A:1026236712926]
• 11: E. Clarke; Multipart Pricing of Public Goods; in: Public Choice 11, pp. 17--33, 1971.
• 12: Sheetalkumar Doshi , Shweta Bhandare , Timothy X Brown, An on-demand minimum energy routing protocol for a wireless ad hoc network, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.3, July 2002 [doi>10.1145/581291.581300]
• 13: Stephan Eidenbenz , V. S. Anil Kumar , Sibylle Zust, Equilibria in topology control games for ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.2-11, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941081]
• 14: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 15: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 16: J. Green and J. Laffont; Incentives in Public Decision Making; in: Studies in Public Economies, vol. 1, North Holland, Amsterdam, pp. 65--78, 1979.
• 17: T. Groves; Incentives in Teams; in: Econometrica 41, pp.617--663, 1973.
• 18: Rahul Garg , Vijay Kumar , Atri Rudra , Akshat Verma, Coalitional games on graphs: core structure, substitutes and frugality, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779982]
• 19: M. Jakobsson, J.P. Hubaux, L. Buttyan; A micro-payment scheme encouraging collaboration in multi-hop cellular networks; In: Proceedings of Financial Crypto 2003, La Guadeloupe, January 2003.
• 20: Stephanie Lindsey , Krishna M. Sivalingam , Cauligi S. Raghavendra, Power optimization in routing protocols for wireless and mobile networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 21: 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]
• 22: A. Mas-Colell, M. Whinston, J. Green; Microeconomic Theory; Oxford University Press, New York, 1995.
• 23: P. Michiardi, R. Molva; Game theoretic analysis of security in mobile ad hoc networks; Research Report No. RR-02-070, Institut Eurecom, 2002.
• 24: 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
• 25: Dov Monderer , Moshe Tennenholtz, Distributed games: from mechanisms to protocols, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.32-37, July 18-22, 1999, Orlando, Florida, United States
• 26: N. Nisan, A. Ronen; Algorithmic mechanism design; in: Games and Economic Behavior 35, pp. 166--196, 2001.
• 27: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 28: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 29: Tim Roughgarden, How unfair is optimal routing?, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.203-204, January 06-08, 2002, San Francisco, California
• 30: J. Shneidman, D.C. Parkes, M. Seltzer; Overcoming Rational Manipulations in Distributed Mechanism Implementations; Harvard Technical Report TR-12-03, 2003.
• 31: V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, R.R. Rao; Energy Efficiency of Ad Hoc Wireless Networks with Selfish Users; in: European Wireless conference, EW 2002.
• 32: Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003
• 33: Yu-Chee Tseng , Wen-Hua Liao , Shih-Lin Wu, Mobile ad hoc networks and routing protocols, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 34: W. Vickrey; Counterspeculation, auctions, and competitive sealed tenders; in: Journal of Finance 16, pp. 8--37, 1961.
• 35: S. Zhong, Yang Richard Yang, J. Chen; Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad-hoc Networks; in: Proceedings of INFOCOM 2003, pp. 1987--1997, March 2003.

INDEX TERMS

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

General Terms:
Algorithms, Economics, Performance

Keywords:
VCG mechanism, ad hoc networks, energy efficiency, game theory, mechanism design, routing, selfish agents