Truthful multicast routing in selfish wireless networks

ABSTRACT

In wireless networks, it is often assumed that each individual wireless terminal will faithfully follow the prescribed protocols without any deviation-- except, perhaps, for a few faulty or malicious ones. Wireless terminals, when owned by individual users, will likely do what is the most beneficial to their owners, i.e., act "selfishly". Therefore, an algorithm or protocol intended for selfish wireless networks must be designed.In this paper, we specifically study how to conduct efficient multicast routing in selfish wireless networks. We assume that each wireless terminal or communication link will incur a cost when it transits some data. Traditionally, the VCG mechanism has been the only method to design protocols so that each selfish agent will follow the protocols for its own interest to maximize its benefit. The main contributions of this paper are two-folds. First, for each of the widely used multicast structures, we show that the VCG based mechanism does not guarantee that the selfish terminals will follow the protocol. Second, we design the first multicast protocols without using VCG mechanism such that each agent maximizes its profit when it truthfully reports its cost.Extensive simulations are conducted to study the practical performances of the proposed protocols regarding the actual network cost and total payment.

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: 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: 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).
• 4: 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]
• 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: Clarke, E. H. Multipart pricing of public goods. Public Choice (1971), 17--33.
• 7: 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]
• 8: 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]
• 9: Green, J., and Laffont, J. J. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica (1977), 427--438.
• 10: Groves, T. Incentives in teams. Econometrica (1973), 617--631.
• 11: Sudipto Guha , Samir Khuller, Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, p.54-65, December 17-19, 1998
• 12: 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).
• 13: Philip Klein , R. Ravi, A Nearly best-possible approximation algorithm for node-weighted Steiner trees, Brown University, Providence, RI, 1992
• 14: 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]
• 15: 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]
• 16: 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]
• 17: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 18: 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 (EW2002) (2002).
• 19: Srinivasan, V., Nuggehalli, P., Chiasserini, C. F., and Rao, R. R. Cooperation in wireless ad hoc wireless networks. In IEEE Infocom (2003).
• 20: Takahashi, H., and Matsuyama, A. An approximate solution for the steiner problem in graphs. Math .Jap. 24 (1980), 573--577.
• 21: Vickrey, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance (1961), 8--37.
• 22: Wang, W., and Li, X.-Y. Truthful low-cost unicast in selfish wireless networks. In 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN) of IPDPS 2004 (2004).
• 23: Wang, W., Li, X.-Y., and Sun, Z. Design multicast protocols for non-cooperative networks, 2004. Submitted for publication.
• 24: Zhong, S., Li, L., Liu, Y., and Yang, Y. R. On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks --- an integrated approach using game theoretical and cryptographic techniques. Tech. Rep. YALEU/DCS/TR-1286, Yale University, Computer Science Department, 2004.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
mechanism design, pricing, selfish, wireless ad hoc networks