Research ArticleOpen AccessGoogle Scholar indexed
Reliable Multi-path Routing in Selfish Networks with Hidden Information and Actions
Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
- 1 Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
- 2 Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
- 3 Departmentof Electronic Engineering, City University of Hong Kong, Hong Kong SAR, China
Journal of Software Engineering and Applications·Volume 05 (2013)·Pages 30–35·Published 17 January 2013·DOI10.4236/jsea.2012.512B007
Copy link · social · email
Abstract
In this paper, we propose a novel game-theoretical solution to the multi-path routing problem in wireless ad hoc networks comprising selfish nodes with hidden information and actions. By incorporating a suitable traffic allocation policy, the proposed mechanism results in Nash equilibria where each node honestly reveals its true cost, and forwarding subgame perfect equilibrium in which each node does provide forwarding service with its declared service reliability. Based on the generalised second price auction, this mechanism effectively alleviates the over-payment of the well-known VCG mechanism. The effectiveness of this mechanism will be shown through simulations.
KeywordsWireless ad hoc networknon-cooperative networkshidden informationhidden actionmechanism designGSP auction.
- B. Edelman, M. Ostrovsky, M. Schwarz, T. D. Fudenberg, L. Kaplow, R. Lee, P. Milgrom, M. Niederle, and A. Pakes, “Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords”, American Economic Review, Vol. 97, 2005.
- J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, “A BGP-based mechanism for lowest-cost routing”, Proceedings of the twenty-?rst annual symposium on Principles of distributed computing, 2002, pp. 173–182.
- M. Feldman, J. Chuang, I. Stoica, and S. Shenker, “Hidden-action in multi-hop routing”, Pro-ceedings of the 6th ACM conference on Electronic com-merce, EC ’05, 2005, pp. 117–126.
- D. Karger and E. Nikolova, “On the expected VCG overpayment in large networks”, Proceedings of45th IEEE Conference on Decision and Control, December 2006, pp. 2831–2836.
- X.-Y. Li, Y. Wu, P. Xu, G. Chen, and M. Li, “Hidden information and actions in multi-hop wireless ad hoc networks”, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, MobiHoc ’08, 2008, pp. 283–292.
- H. Liu and B. Krishnamachari, “A price-based reliable routing game in wireless networks”, Proceedings of the 2006 workshop on Game theory for communications and networks, GameNets ’06, 2006.
- M. Osborne and A. Rubinstein, “A course in game theory”, The MIT Press, 1994.
- X. Su, S. Chan, and G. Peng, “Auction in multi-path multi-hop routing”, IEEE Communications Letters, Vol. 13, No. 2, 2009, pp.154–156.
- X. Su, S. Chan, and G. Peng, “Genera-lized second price auction in multi-path routing with selfish nodes”, Proceedings of the IEEE GLOBECOM, 2009, pp. 3413–3418.
- K. Talwar, “The price of truth: Frugality in truthful mechanisms”, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, 2003, pp. 608–619.
- H. R. Varian, “Position auctions”,International Journal of Industrial Organization, Vol. 25, No. 6, 2007, pp. 1163–1178.
- W. Wang, S. Eidenbenz, Y. Wang, and X.-Y. Li, “OURS: optimal unicast routing systems in non-cooperative wireless networks”, Proceedings of the 12th annual international conference on Mobile computing and networking, MobiCom ’06, 2006, pp. 402–413.
- W. Wang and X.-Y. Li, “Low-cost routing in selfish and rational wireless ad hoc networks”, IEEE Transactions on Mobile Computing, Vol. 5, May 2006, pp. 596–607.