Scheduling Wireless Links in the Physical Interference Model by Fractional Edge Coloring
- 20 December 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Wireless Communications Letters
- Vol. 9 (4) , 528-532
Abstract
We consider the link scheduling problem in wireless mesh networks for capacity maximization. Unlike all previous approaches, ours views capacity in terms of covering a graph’s edges by matchings that are feasible in the sense of the physical interference model, thus leading to a novel fractional edge-chromatic indicator of the graph. Network capacity is then defined as a function of this indicator, whose exact computation can be formulated as a linear programming problem. Solving this problem for an extensive collection of random geometric graphs that instantiate networks in the physical interference model reveals that, depending on node density, often a network admits increased capacity by virtue of simply scheduling links based on fractional, rather than integer, edge coloring. This settles a heretofore unaddressed issue in the physical interference model.Keywords
All Related Versions
Funding Information
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro
This publication has 16 references indexed in Scilit:
- New Algorithms for Maximum Weight Matching and a Decomposition TheoremMathematics of Operations Research, 2017
- Scheduling wireless links by vertex multicoloring in the physical interference modelComputer Networks, 2016
- Algorithms for Wireless CapacityIEEE/ACM Transactions on Networking, 2013
- Joint scheduling and power control for multicasting in cellular wireless networksEURASIP Journal on Wireless Communications and Networking, 2012
- Scheduling links for heavy traffic on interfering routes in wireless mesh networksComputer Networks, 2012
- Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints2008
- Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks2006
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- Link scheduling in polynomial timeIEEE Transactions on Information Theory, 1988
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981