A game approach for multi-channel allocation in multi-hop wireless networks

ABSTRACT

Channel allocation was extensively investigated in the framework of cellular networks, but it was rarely studied in the wireless ad-hoc networks, especially in the multi-hop ad-hoc networks. In this paper, we study the competitive multi-radio channel allocation problem in multi-hop wireless networks in detail. We model the channel allocation problem as a static cooperative game, in which some players collaborate to achieve high date rate. We propose the min-max coalition-proof Nash equilibrium (MMCPNE) channel allocation scheme in the game, which is aiming to max the achieved date rates of communication links. We study the existence of MMCPNE and prove the necessary conditions for MMCPNE. Furthermore, we propose several algorithms that enable the selfish players to converge to MMCPNE. Simulation results show that MMCPNE outperforms CPNE and NE schemes in terms of achieved data rates of the multi-hop links due to cooperation gain.

REFERENCES

• 1: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 2: M. Schwartz. Mobile Wireless Communications. Cambridge Univ. Press, 2005.
• 3: M. Felegyhazi, M. Cagalj, S. S. Bidokhti, etc. Non-cooperative Multi-radio Channel Allocation in Wireless Networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '07), March 13-17 2007.
• 4: J. van den Heuvel , R. A. Leese , M. A. Shepherd, Graph labeling and radio channel assignment, Journal of Graph Theory, v.29 n.4, p.263-283, December 1998 [doi>10.1002/(SICI)1097-0118(199812)29:4<>1.0.CO;2-A]
• 5: I. Katzela and M. Naghshineh. Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey. IEEE Personal Communications, 3(3):10--31, Jun 1996.
• 6: Hac A and Z. Chen. Hybrid channel allocation in wireless networks. In Proceedings of the IEEE Conference on Vehicular Technology Conference (VTC '99), 50(4):2329--2333, Sept. 1999.
• 7: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 8: A. Raniwala and T. C. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '05), March 13-17 2005.
• 9: Mo Li , Yunhao Liu, Rendered path: range-free localization in anisotropic sensor networks with holes, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287861]
• 10: Mo Li , Yunhao Liu, Underground structure monitoring with wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236370]
• 11: Arunesh Mishra , Suman Banerjee , William Arbaugh, Weighted coloring based channel assignment for WLANs, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.3, July 2005 [doi>10.1145/1094549.1094554]
• 12: 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]
• 13: M. Cagalj, S. Ganeriwal, I. Aad, etc. On selfish behavior in CSMA/CA networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '05), March 13-17 2005.
• 14: Jerzy Konorski, Multiple Access in Ad-Hoc Wireless LANs with Noncooperative Stations, Proceedings of the Second International IFIP-TC6 Networking Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; and Mobile and Wireless Communications, p.1141-1146, May 19-24, 2002
• 15: A. B. MacKenzie and S. B. Wicker. Stability of multipacket slotted aloha with selfish users and perfect information. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '03), March 30-April 3 2003.
• 16: Ming-Yang Kao , Xiang-Yang Li , WeiZhao Wang, Towards truthful mechanisms for binary demand games: a general framework, Proceedings of the 6th ACM conference on Electronic commerce, p.213-222, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064032]
• 17: Magnús M. Halldórsson , Joseph Y. Halpern , Li (Erran) Li , Vahab S. Mirrokni, On spectrum sharing games, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011783]
• 18: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks, p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 19: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communication, 18(3), March 2000.
• 20: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 21: B. D. Bernheim, B. Peleg, and M. D. Whinston. Coalition-proof Nash equilibria: I concepts. Journal of Economic Theory, 42(1), June 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Theory

Keywords:
channel allocation, game theory, multi-radio, nash equilibria