Hidden information and actions in multi-hop wireless ad hoc networks

ABSTRACT

For multi-hop ad hoc networks formed by individually owned nodes, the endpoints can only observe whether or not the end-to-end transaction was successful or not, but not the individual actions of intermediate nodes. Consequently, in the absence of properly designed incentive schemes, rational (i.e., selfish) intermediate nodes may choose to forward data packets at a very low priority or simply drop the packets at all, and it could put the blame on the unreliable wireless channel. Using a principal-agent model, we propose several efficient methods that can eliminate the hidden actions under hidden information in multi-hop wireless networks with high probability. We design several algorithmic mechanisms for a number of routing scenarios such that each selfish agent will maximize its utility (i.e., profit) when it truthfully declares its type (i.e., cost and its actions) and it truthfully follows its declared actions. Our simulations show that the payment by our mechanisms is only slightly larger than the actual cost incurred by all intermediate nodes.

REFERENCES

• 1: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 2: 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]
• 3: 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
• 4: Suman Banerjee , Archan Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513818]
• 5: Blazevic, L., Buttyan, L., Capkun, S., Giordano, S., Hubaux, J. P., and Boudec, J. Y. L. Self-organization in mobile ad-hoc networks: the approach of terminodes. IEEE Communications Magazine 39, 6 (June 2001).
• 6: Buchegger, S., and Boudec, J.-Y. L. A robust reputation system for p2p and mobile ad-hoc networks. In Second Workshop on the Economics of Peer-to-Peer Systems, with ACM Sigcomm (2004).
• 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: Calinescu, G. Bounding the payment of approximate truthful mechanisms. In ISAAC (2004), pp. 221--233.
• 10: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 11: Clarke, E. H. Multipart pricing of public goods. Public Choice (1971), 17--33.
• 12: Qunfeng Dong , Suman Banerjee , Micah Adler , Archan Misra, Minimum energy reliable paths using unreliable wireless links, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062744]
• 13: Edith Elkind , Amit Sahai , Ken Steiglitz, Frugality in path auctions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 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: Feldman, M., and Chuang, J. Hidden-action in multi-hop routing. In Second Workshop on the Economics of Peer-to-Peer Systems, in conjunction with ACM Sigcomm (2004).
• 16: Michal Feldman , John Chuang , Ion Stoica , Scott Shenker, Hidden-action in multi-hop routing, Proceedings of the 6th ACM conference on Electronic commerce, p.117-126, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064022]
• 17: Felegyhazi, M., Buttyan, L., and Hubaux, J. Equilibrium analysis of packet forwarding strategies in wireless ad hoc networks - the static case. In Personal Wireless Communications, (2003).
• 18: Groves, T. Incentives in teams. Econometrica (1973), 617--631.
• 19: Hershberger, J., and Suri, S. Vickrey pricing in network routing: Fast payment computation. In IEEE Symp. on Foundations of Computer Science (FOCS) (2001), pp. 252--259.
• 20: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 21: Jakobsson, M., Hubaux, J.-P., and Buttyan, L. A micro-payment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of Financial Cryptography (2003).
• 22: Anna R. Karlin , David Kempe , Tami Tamir, Beyond VCG: Frugality of Truthful Mechanisms, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.615-626, October 23-25, 2005 [doi>10.1109/SFCS.2005.25]
• 23: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 24: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Algorithmic aspects of capacity in wireless networks, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 25: Aurel A. Lazar , Ariel Orda , Dimitrios E. Pendarakis, Virtual path bandwidth allocation in multiuser networks, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.861-871, Dec. 1997 [doi>10.1109/90.650145]
• 26: Liang, B., and Haas, Z. J. Virtual backbone generation and maintenance in ad hoc network mobility management. In Proc. of IEEE INFOCOM (2000), vol. 3, pp. 1293--1302.
• 27: 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]
• 28: Nicole Immorlica , David Karger , Evdokia Nikolova , Rahul Sami, First-price path auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.203-212, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064031]
• 29: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 30: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 31: Ariel Orda , Nahum Shimkin, Incentive Pricing in Multi-Class Communication Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.659, April 09-11, 1997
• 32: Osborne, M. J., and Rubinstein, A. A course in game theory. The MIT Press, 2002.
• 33: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 34: 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]
• 35: Sinha, P., Sivakumar, R., and Bharghavan, V. Cedar: Core extraction distributed ad hoc routing algorithm. IEEE Journal on Selected Areas in Communications 17, 8 (August 1999), 1454--1465.
• 36: Srinivasan, V., Nuggehalli, P., Chiasserini, C. F., and Rao, R. R. Energy efficiency of ad hoc wireless networks with selfish users. In European Wireless Conference (2002).
• 37: Srinivasan, V., Nuggehalli, P., Chiasserini, C. F., and Rao, R. R. Cooperation in wireless ad hoc wireless networks. In IEEE INFOCOM (2003).
• 38: 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
• 39: Vickrey, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance (1961), 8--37.
• 40: Weizhao Wang , Xiang-Yang Li, Low-Cost Routing in Selfish and Rational Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.5, p.596-607, May 2006 [doi>10.1109/TMC.2006.66]
• 41: Wang, W., and Li, X.-Y. Nash equilibrium, dominant strategies in routing. In Workshop for Internet and Network Economics (2005).
• 42: 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]
• 43: Chih-Wei Yi , Peng-Jun Wan, Probabilistic aspects of wireless ad hoc networks, Illinois Institute of Technology, Chicago, IL, 2005
• 44: Zhong, S., Chen, J., and Yang, Y. SPRITE: A simple, cheat-proof, credit-based system for mobile ad hoc networks. In IEEE INFOCOM (2003).
• 45: 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]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
ad hoc networks, hidden action, hidden-information, selfish, truthful mechanism