On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques

ABSTRACT

In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games---the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result---there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol consisting of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost (ie, its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.

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: H. Balakrishnan and R. Katz. Explicit loss notification and wireless web performance. In Proceedings of IEEE Globecom Internet Mini-Conference, 1998.
• 3: S. Buchegger and J.-Y. 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, 2002.
• 4: 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]
• 5: 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
• 6: L. Buttyan and J. P. Hubaux. Stimulating cooperation in self-organizing mobile ad hoc networks. ACM Journal for Mobile Networks (MONET), special issue on Mobile Ad Hoc Networks, summer 2002.
• 7: M. Cagalj, S. Ganeriwal, I. Aad, and J. P. Hubaux. On selfish behavior in csma/ca networks. In Proceedings of IEEE INFOCOM, Miami, Florida, USA, March 2005.
• 8: Cisco Systems Inc. Data sheet for cisco aironet, 2004.
• 9: E. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 10: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 11: 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]
• 12: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 13: 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]
• 14: J. Feigenbaum and S. Shenker. Incentives and Internet algorithms. Tutorial given at PODC 2003. Available at http://www.cs.yale.edu/~jf/PODC03.ppt, July 2003.
• 15: M. Felegyhazi, L. Buttyan, and J. P. Hubaux. Equilibrium analysis of packet forwarding strategies in wireless ad hoc networks -- the static case. In Proceedings of Personal Wireless Communications (PWC), Venice, Italy, 2003.
• 16: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical Report UCLA/CSD-TR 02-0013, Computer Science Department, UCLA, July 2002.
• 17: GloMoSim. http://pcl.cs.ucla.edu/projects/glomosim/.
• 18: Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989467]
• 19: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 20: T. Groves. Incentives in teams. Econometrica, 41:617--663, 1973.
• 21: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 22: Elgan Huang , Jon Crowcroft , Ian Wassell, Rethinking incentives for mobile ad hoc networks, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016532]
• 23: M. Jakobsson. Ripping coins for a fair exchange. In Advances in cryptology, EUROCRYPT, 1995.
• 24: M. Jakobsson, J. P. Hubaux, and L. Buttyan. A micropayment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of Financial Crypto, La Guadeloupe, Jan. 2003.
• 25: Almudena Konrad , Ben Y. Zhao , Anthony D. Joseph , Reiner Ludwig, A Markov-based channel model algorithm for wireless networks, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.28-36, July 2001, Rome, Italy [doi>10.1145/381591.381602]
• 26: D. M. Kreps. Game Theory and Economic Modeling. Oxford Press, 1991.
• 27: Yi-Bing Lin , Jason Yi-Bing Lin, Wireless and Mobile Network Architectures, John Wiley & Sons, Inc., New York, NY, 2000
• 28: 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]
• 29: Ratul Mahajan , Maya Rodrig , David Wetherall , John Zahorjan, Experiences applying game theory to system design, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016531]
• 30: 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]
• 31: 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
• 32: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 33: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166--196, 2001.
• 34: M. J. Osborne and A. Rubenstein. A Course in Game Theory. The MIT Press, 1994.
• 35: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 36: C. Perkins. Ad Hoc Networking. Addison-Wesley, 2000.
• 37: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 38: Indrajit Ray , Indrakshi Ray, Fair exchange in E-commerce, ACM SIGecom Exchanges, v.3 n.2, p.9-17, Spring, 2002 [doi>10.1145/844340.844345]
• 39: 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]
• 40: V. Srinivasan, P. Nuggehalli, C.-F. Chiasserini, and R. Rao. Cooperation in wireless ad hoc networks. In Proceedings of IEEE INFOCOM, San Francisco, CA, Apr. 2003.
• 41: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 42: C.K. -K Toh, Ad Hoc Wireless Networks: Protocols and Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 43: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 44: WeiZhao Wang , Xiang-Yang Li , Yu Wang, Truthful multicast routing in selfish wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023745]
• 45: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 46: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 47: S. Zhong, J. Chen, and Y. R. Yang. Sprite, a simple, cheat-proof, credit-based system for mobile ad-hoc networks. In Proceedings of IEEE INFOCOM, San Francisco, CA, Apr. 2003.

INDEX TERMS

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

General Terms:
Algorithms, Design, Economics, Security

Keywords:
game theory, incentives, mechanism design, security, wireless ad-hoc network