A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Abstract

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

References

1. IEEE 802.11b standard, standards.ieee.org/getieee802/download/ 802.11b-1999.pdf.
2. IEEE 802.11a standard, standards.ieee.org/getieee802/download/ 802.11a-1999.pdf.
3. Aardal, K. I., van Hoesel, S. P. M., Koster, A. M. C. A., Mannino, C., & Sassano, A. (2003). Models and solution techniques for frequency assignment problems. 4OR: A Quarterly Journal of Operations Research, 1(4), 261-317.
4. Riihijarvi, J., Petrova, M., Mahonen, P., & de Almeida Barbosa, J. (2006). Performance evaluation of automatic channel assignment mechanism for IEEE 802.11 based on graph colouring. In Proceedings of the 17th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '06), September 2006, pp. 1-5.
5. Leung, K., & Kim, B.-J. (2003). Frequency assignment for IEEE 802.11 wireless networks. In Proceedings of the 58th IEEE Vehicular Technology Conference (VTC '03), vol. 3, Oct 2003, pp. 1422-1426.
6. Mishra, A., Banerjee, S., & Arbaugh, W. (2005). Weighted coloring based channel assignment for WLANs. ACM SIGMOBILE Mobile Computing and Communications Review, 9(3), 19-31.
7. Alicherry, M., Bhatia, R., & Li, L. E. (2002). Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks. In Proceedings of the 11th International Conference on Mobile Computing and Networking (MOBICOM '05), Aug 2002, pp. 58-72.
8. Shin, M., Lee, S., & Kim, Y. (2006). Distributed channel assignment for multi-radio wireless networks. In Proceedings of the 3rd IEEE International Conference on Mobile, Ad Hoc and Sensor Systems (MASS '06), October 2006, pp. 417-426.
9. Li, N., Hou, J., & Sha, L. (2003). Design and analysis of an MST-based topology control algorithm. In Proceedings of the 22nd IEEE International Conference on Computer Communications (INFOCOM '03), vol. 3, March 2003, pp. 1702-1712.
10. Das, A., Alazemi, H., Vijaykumar, R., & Roy, S. (2005). Optimization models for fixed channel assignment in wireless mesh networks with multiple radios. In Proceedings of the 2nd IEEE Communication Society Conference on Sensor and Ad Hoc Communications and Networks (SECON '05), September 2005, pp. 463-474.
11. Cagalj, M., Ganeriwal, S., Aad, I., & Hubaux, J.-P. (2005). On selfish behaviour in CSMA/CA networks. In Proceedings of the 24th IEEE Conference on Computer Communications (INFOCOM'05), vol. 4, March 2005, pp. 2513-2524.
12. Konorski, J. (2002). Multiple access in ad-hoc wireless LANs with noncooperative stations. In Proceedings of the 2nd International Conference on Networking of the IFIP Technical Committee on Communication Systems (TC6), May 2002, pp. 1141-1146.
13. MacKenzie A. B., & Wicker, S. B. (2003). Stability of multipacket slotted aloha with selfish users and perfect information. In Proceedings of the 22nd IEEE International Conference on Computer Communications (INFOCOM '03), vol. 3, April 2003, pp. 1583-1590.
14. Halldorsson, M. M., Halpern, J. Y., & Li, L. E. (2004). On spectrum sharing games. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC' 04), July 2004, pp. 107-114.
15. Wu, F., Zhong, S., & Qiao, C. (2008). Globally optimal channel assignment for non-cooperative wireless networks. In Proceedings of the 27th International IEEE Conference on Computer Communications (INFOCOM '08), April 2008, pp. 1543-1551.
16. Nie, N., & Comaniciu, C. (2005). Adaptive channel allocation spectrum etiquette for cognitive radio networks. In Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN '05), Nov 2005, pp. 269-278.
17. Felegyhazi, M., Cagalj, M., Bidokhti, S. S., & Hubaux, J.-P. (2007). Non-cooperative multi-radio channel allocation in wireless networks. In Proceedings of the 26th International IEEE Conference on Computer Communications (INFOCOM '07), March 2007, pp. 1442-1450.
18. Gao, L., & Wang, X. (2008). A game approach for multichannel allocation in multi-hop wireless networks. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '08), May 2008, pp. 303-312.
19. Gupta, R., Musacchio, J., & Walranda, J. (2007). Sufficient rate constraints for QoS flows in ad-hoc networks. Ad Hoc Networks, vol. 5, no. 4, pp. 429-443, May 2007.
20. Luo, H., Lu, S., & Bhargavan, V. (2000). A new model for packet scheduling in multihop wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), August 2000, pp. 76-86.
21. Jain, K., Padhye, J., Padmanabhan, V. N., & Qiu, L. (2003). Impact of interference on multi-hop wireless network performance. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM '03), September 2003, pp. 66-80.
22. Osborne M. J., & Rubinstein, A. (1994). A Course in Game Theory. Cambridge: MIT Press.
23. Bianchi, G. (2000). Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3), 535-547.
24. IEEE standard for wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. (1997). P802.11.
25. Koutsoupias, E., & Papadimitriou, C. H. (1993). Worst-case equilibria. In Proceedings of the 16th Annual Conference in Theoretical Aspects of Computer Science, vol. 1563, Lecture Notes in Computer Science, 1999, pp. 404-413.
26. Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (1995). Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS '95), October 1995, pp. 322-331.
27. Littlestone, N., & Warmuth, M. K. (1994). The weighted majority algorithm. Information and Computation, 108(2), 212-261.
28. Freund, Y., & Schapire, R. (1995). A decision-theoretic generalization of on-line learning and an application to boosting. In Proceedings of the 2nd European Conference on Computational Learning Theory (EuroCOLT '95), May 1995, pp. 23-37.
29. The Stanford GraphBase: A Platform for Combinatorial Computing, http://www-cs-faculty.stanford.edu/knuth/sgb.html.
30. Phillips, G., Shenker, S., & Tangmunarunkit, H. (1999). Scaling of multicast trees: Comments on the Chuang-Sirbu scaling law. In Proceedings of the ACM Annual Conference of the Special Interet Group on Data Communication (ACM SIGCOMM'99), pp. 41-51.
31. Greenwald, A., & Jafari, A. (2003). A class of no-regret algorithms and game-theoretic equilibria. In Proceedings of the 16th Annual Conference on Learning Theory (COLT 2003), August 2003, pp. 1-11.
32. Lim, J. G., Chou, C. T., & Jha, S. (2007). Non-cooperative coexistence of co-located independent wireless mesh networks. In Proceedings of the 4th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2007), October 2007, pp. 1-9.
33. Cesa-Bianchi, N., Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge: Cambridge University Press.
34. Young, P. (2004). Strategic Learning and its limits. Oxford: Oxford University Press.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography

• Theory of computation

  • Computational complexity and cryptography

    • Communication complexity