WANG Gang, DAI Xia. The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism[J]. Chinese Journal of Electronics, 2013, 22(3): 567-571.
Citation: WANG Gang, DAI Xia. The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism[J]. Chinese Journal of Electronics, 2013, 22(3): 567-571.

The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism

Funds:  This work is supported by the National Natural Science Foundation of China (No.60972007, No.61271194), and the National Basic Research Program of China (973 Program) (No.2010CB731800).
  • Received Date: 2012-04-01
  • Rev Recd Date: 2012-08-01
  • Publish Date: 2013-06-15
  • To emphasize the decisions of all users, and the total number of users sharing the same technique, we propose a novel Average cost sharing (ACS) pricing mechanism to study the game between Network coding (NC) and routing flows sharing a single link when users are price anticipating. We characterize the worst-case efficiency bounds of the game compared with the optimal (i.e., the Price of anarchy (PoA)), which can be as low as 4/9 when the number of routing users becomes sufficiently large. NC cannot improve the PoA significantly under ACS. However, to achieve a more efficient use of limited resources, this approach indicates the sharing users have a greater tendency to choose NC. However, the users will follow the majority users' choice of data transmission technique.
  • loading
  • Yingju Chen and Jiawei Zhang, “Design of price mechanisms for network resource allocation via price of anarchy”, Journal of Mathematical Programming, Series A and B, Vol.131, No.1-2, pp.333-364, 2012.
    Yufang Xi and Edmund M. Yeh, “Pricing, competition, and routing in relay networks”, Allerton'09 Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, USA, pp.507-514, 2009.
    Yufang Xi and Edmund M. Yeh, “Pricing, competition, and routing for selfish and strategic nodes in multi-hop relay networks”, in Proceedings of the IEEE Conference on Computer Communications (INFOCOM'08), Phoneix, Ariz, USA, pp.2137-2145, 2008.
    F.P. Kelly, A.K. Maulloo and D.K.H .Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, Journal of the Operational Research Society, Vol.49, No.3, pp.237-252, 1998.
    R. Ahlswede, N. Cai, S. Li and R. Yeung, “Network information flow”, IEEE Trans. on Information Theory, Vol.46, pp.12041216, 2000.
    Xiao Song, Wang Hui, Wu Chengke, “A new network coding design for reliable video multicast”, Chinese Journal of Electronics, Vol.20, No.2, pp.361-364, 2011.
    Guang Xuan, Fu Fangwei, “On random linear network coding for butterfly network”, Chinese Journal of Electronics, Vol.20, No.2, pp.283-286, 2011.
    X. Liang, “Matrix games in the multicast networks: maximum information ?ows with network switching”, IEEE Trans. on Information Theory, Vol.52, pp.2433-2466, 2006.
    Z. Li, “Cross-monotonic multicast”, Proc. of IEEE INFOCOM' 08, Phoenix, Ariz, USA, pp.1588-1596, 2008.
    X. Zhang and B. Li, “Dice: a game theoretic framework for wireless multipath network coding”, Proc. of ACM MobiHoc, Hong Kong, China, pp.293-302, 2008.
    A. Hamed Mohsenian-Rad, Jianwei Huang and Vincent W.S. Wong, “A game-theoretic analysis of inter-session network coding”, Proceedings of the 2009 IEEE International Conference on Communications, Dresden, Germany, pp.1690-1695, 2009.
    Amir-Hamed Mohsenian-Rad, Jianwei Huang, Vincent W.S. Wong and Robert Schober, “Bargaining and price-of-anarchy in repeated inter-session network coding games”, Proceedings of IEEE INFOCOM'10, San Diego, CA, USA, pp.1927-1935, 2010.
    Amir-Hamed Mohsenian-Rad, Jianwei Huang, Vincent W.S. Wong, “Inter-session network coding with strategic users: A game-theoretic analysis of network coding”, Submitted to IEEE Transactions on IT, 2009.
    Tansu Alpcan, Tamer Basar, “A game theoretic framework for congestion control in general topology networks”, Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, Nevada USA, pp.1218-1224, 2002.
    Ramesh Johari and John N. Tsitsiklis, “A scalable network resource allocation mechanism with bounded efficiency loss”, IEEE Journal on Selected Areas in Communications, Vol.24, No.5, pp.992-999, 2006.
    Vasilis Ntranos, “Cost sharing network routing game”, wwwbcf. usc.edu/~shanghua/teaching/Fall2010/cost sharing.pdf.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (287) PDF downloads(876) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return