Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction

DOI10.1016/J.DAM.2018.12.009MaRDI QIDQ2420428zbMATH OpenOpenAlexWikidataFDO

Authors David Orden, Ivan Marsa-Maestre, Jose Manuel Gimenez-Guzman, Enrique de la Hoz, Ana Álvarez-Suárez

Publication date 6 June 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.06832

zbMATH Keywords

edge contractionfrequency assignmentgraph coloringsimulated annealingspectrum coloringWi-Fi channels

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90) Combinatorial optimization (90C27) Channel models (including quantum) in information and communication theory (94A40)

Abstract: 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'a. 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.

Recommendations

• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Soft Edge Coloring
• A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
• Channel Dependent Interference and Decentralized Colouring
• Models and approximation algorithms for channel assignment in radio networks

Cites work

• \(T\)-colorings of graphs: recent results and open problems
• Bandwidth allocation in cellular networks with multiple interferences
• Broadcast chromatic numbers of graphs
• Constructing efficient simulated annealing algorithms
• Contrast in greyscales of graphs
• Dichotomies properties on computational complexity of S-packing coloring problems
• Distance Coloring
• Graph labellings with variable weights, a survey
• Graphs and algorithms in communication networks. Studies in broadband, optical, wireless and ad hoc networks
• scientific article; zbMATH DE number 1500531 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems
• Optimization by simulated annealing
• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Weighted improper colouring

Cited in

(4)

• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Contrast in greyscales of graphs
• A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
• Towards more efficient local search for weighted graph coloring problem in massive graphs

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420428)