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.
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: