Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction. (English) Zbl 1414.05277
Summary: The present work deals with the problem of efficiently assigning Wi-Fi channels in a real-world scenario, the Polytechnic School of the University of Alcalá. We first use proximity graphs to model the whole problem as an instance of spectrum graph coloring, we further obtain a simplified model using edge contraction, and we finally use simulated annealing to look for a coloring which optimizes the network throughput. As the main result, we show that the solutions we obtain outperform the de facto standard for Wi-Fi channel assignment, both in terms of network throughput and of computation time.
MSC:
| 05C90 | Applications of graph theory |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 94A40 | Channel models (including quantum) in information and communication theory |
| 90C27 | Combinatorial optimization |
Keywords:
graph coloring; edge contraction; frequency assignment; Wi-Fi channels; spectrum coloring; simulated annealingSoftware:
CALMAReferences:
| [1] | Aardal, K. I.; van Hoesel, S. P.M.; Koster, A. M.C. A.; Mannino, C.; Sassano, A., Models and solution techniques for frequency assignment problems, Ann. Oper. Res., 153, 1, 79-129 (2007) · Zbl 1157.90005 |
| [2] | Achanta, M., Method and apparatus for least congested channel scan for wireless access points (2004), U.S. Patent Application No. 10/959,446 |
| [3] | Araujo, J.; Bermond, J.-C.; Giroire, F.; Havet, F.; Mazauric, D.; Modrzejewski, R., Weighted improper colouring, J. Discrete Algorithms, 16, 53-66 (2012) · Zbl 1257.05035 |
| [4] | Bar-Yehuda, R.; Polevoy, G.; Rawitz, D., Bandwidth allocation in cellular networks with multiple interferences, Discrete Appl. Math., 194, 23-36 (2015) · Zbl 1366.90033 |
| [5] | A. Bazzi, On uncoordinated multi user multi RAT combining. in: Proceedings of the IEEE Vehicular Technology Conference, VTC Fall, San Francisco (CA), USA, 5-8 Sept. 2011, pp. 1-6.; A. Bazzi, On uncoordinated multi user multi RAT combining. in: Proceedings of the IEEE Vehicular Technology Conference, VTC Fall, San Francisco (CA), USA, 5-8 Sept. 2011, pp. 1-6. |
| [6] | Bodlaender, H. L.; Kloks, T.; Tan, R. B.; van Leeuwen, J., \( \lambda \)-coloring of graphs, (Lecture Notes in Computer Science, vol. 1770 (2000), Springer), 395-406 · Zbl 0982.05050 |
| [7] | Chieochan, S.; Hossain, E.; Diamond, J., Channel assignment schemes for infrastructure-based 802.11 WLANs: A survey, IEEE Commun. Surv. Tutor., 12, 1, 124-136 (2010) |
| [8] | de Castro, N.; Garrido-Vizuete, M. A.; Robles, R.; Villar-Liñán, M. T., Contrast in greyscales of graphs (2016), arXiv:1612.07527 · Zbl 1437.05071 |
| [9] | E. de la Hoz, J.M. Gimenez-Guzman, I. Marsa-Maestre, L. Cruz-Piris, D. Orden, A distributed multi-agent approach to reactive network resilience. in: S. Das, E. Durfee, K. Larson, and M. Winikoff (Eds.), in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 2017 pp. 1044-1053.; E. de la Hoz, J.M. Gimenez-Guzman, I. Marsa-Maestre, L. Cruz-Piris, D. Orden, A distributed multi-agent approach to reactive network resilience. in: S. Das, E. Durfee, K. Larson, and M. Winikoff (Eds.), in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 2017 pp. 1044-1053. |
| [10] | de la Hoz, E.; Gimenez-Guzman, J. M.; Marsa-Maestre, I.; Orden, D., Automated negotiation for resource assignment in wireless surveillance sensor networks, Sensors, 15, 11, 29547-29568 (2015) |
| [11] | E. de la Hoz, I. Marsa-Maestre, J.M. Gimenez-Guzman, D. Orden, M. Klein, Multi-agent nonlinear negotiation for Wi-Fi channel assignment. in: S. Das, E. Durfee, K. Larson, and M. Winikoff (Eds.), in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 2017, pp.1035-1043.; E. de la Hoz, I. Marsa-Maestre, J.M. Gimenez-Guzman, D. Orden, M. Klein, Multi-agent nonlinear negotiation for Wi-Fi channel assignment. in: S. Das, E. Durfee, K. Larson, and M. Winikoff (Eds.), in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 2017, pp.1035-1043. |
| [12] | Duque-Antón, M., Constructing efficient simulated annealing algorithms, Discrete Appl. Math., 77, 2, 139-159 (1997) · Zbl 0881.90104 |
| [13] | Gastineau, N., Dichotomies properties on computational complexity of \(S\)-packing coloring problems, Discrete Math., 338, 6, 1029-1041 (2015) · Zbl 1371.05080 |
| [14] | J.M. Gimenez-Guzman, I. Marsa-Maestre, D. Orden, E. de la Hoz, T. Ito, On the goodness of using orthogonal channels in WLAN IEEE 80211 in realistic scenarios. Wireless Communications and Mobile Computing (2018), in press.; J.M. Gimenez-Guzman, I. Marsa-Maestre, D. Orden, E. de la Hoz, T. Ito, On the goodness of using orthogonal channels in WLAN IEEE 80211 in realistic scenarios. Wireless Communications and Mobile Computing (2018), in press. |
| [15] | Goddard, W.; Hedetniemi, S. M.; Hedetniemi, S. T.; Harris, J. M.; Douglas, D. F., Broadcast chromatic numbers of graphs, Ars Combinatorica, 86, 33-50 (2008) · Zbl 1224.05172 |
| [16] | D.B. Green, A.S. Obaidat, An accurate line of sight propagation performance model for ad-hoc 802.11 wireless LAN (WLAN) devices. in: Communications, 2002. ICC 2002. IEEE International Conference on, vol. 5, 2002, pp. 3424-3428.; D.B. Green, A.S. Obaidat, An accurate line of sight propagation performance model for ad-hoc 802.11 wireless LAN (WLAN) devices. in: Communications, 2002. ICC 2002. IEEE International Conference on, vol. 5, 2002, pp. 3424-3428. |
| [17] | Griggs, J. R.; Král, D., Graph labellings with variable weights, a survey, Discrete Appl. Math., 157, 12, 2646-2658 (2009) · Zbl 1211.05145 |
| [18] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671 (1983) · Zbl 1225.90162 |
| [19] | Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks (2010), Springer-Verlag · Zbl 1181.68008 |
| [20] | I. Marsa-Maestre, E. de la Hoz, J.M. Gimenez-Guzman, D. Orden, M. Klein, Nonlinear negotiation approaches for complex-network optimization: a study inspired by Wi-Fi channel assignment. Group Decision and Negotiation, in press.; I. Marsa-Maestre, E. de la Hoz, J.M. Gimenez-Guzman, D. Orden, M. Klein, Nonlinear negotiation approaches for complex-network optimization: a study inspired by Wi-Fi channel assignment. Group Decision and Negotiation, in press. |
| [21] | S.W.K. Ng, T.H. Szymanski, Interference measurements in an 80211n Wireless Mesh Network testbed. in: Proceeding of the IEEE CCECE Conference, Apr. 2012, pp. 1-6.; S.W.K. Ng, T.H. Szymanski, Interference measurements in an 80211n Wireless Mesh Network testbed. in: Proceeding of the IEEE CCECE Conference, Apr. 2012, pp. 1-6. |
| [22] | Orden, D.; Marsá-Maestre, I.; Giménez-Guzmán, J. M.; de la Hoz, E., Spectrum graph coloring and applications to Wi-Fi channel assignment, Symmetry, 10, 3, 65 (2018) · Zbl 1392.05106 |
| [23] | A. Raschellá, F. Bouhafs, M. Seyedebrahimi, M. Mackay, Q. Shi, A centralized framework for smart access point selection based on the Fittingness Factor, in: 23rd IEEE International Conference on Telecommunications, ICT, 2016, pp. 1-5.; A. Raschellá, F. Bouhafs, M. Seyedebrahimi, M. Mackay, Q. Shi, A centralized framework for smart access point selection based on the Fittingness Factor, in: 23rd IEEE International Conference on Telecommunications, ICT, 2016, pp. 1-5. |
| [24] | Roberts, F. S., \(T\)-colorings of graphs: Recent results and open problems, Discrete Math., 93, 2-3, 229-245 (1991) · Zbl 0751.05042 |
| [25] | Sharp, A., Distance coloring, (Lecture Notes in Computer Science, vol. 4698 (2007), Springer), 510-521 · Zbl 1151.05319 |
| [26] | Tragos, E. Z.; Zeadally, S.; Fragkiadakis, A.; A, Vasilios spectrum assignment in cognitive radio networks: a comprehensive survey, IEEE Commun. Surv. Tutor., 15, 3, 1108-1135 (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
