Scheduling wireless links in the physical interference model by fractional edge coloring
Preprint
Abstract
We consider the problem of scheduling the links of wireless mesh networks for capacity maximization in the physical interference model. We represent such a network by an undirected graph $G$, with vertices standing for network nodes and edges for links. We define network capacity to be $1/\chi'^*_\mathrm{phys}(G)$, where $\chi'^*_\mathrm{phys}(G)$ is a novel edge-chromatic indicator of $G$, one that modifies the notion of $G$'s fractional chromatic index. This index asks that the edges of $G$ be covered by matchings in a certain optimal way. The new indicator does the same, but requires additionally that the matchings used be all feasible in the sense of the physical interference model. Sometimes the resulting optimal covering of $G$'s edge set by feasible matchings is simply a partition of the edge set. In such cases, the index $\chi'^*_\mathrm{phys}(G)$ becomes the particular case that we denote by $\chi'_\mathrm{phys}(G)$, a similar modification of $G$'s well-known chromatic index. We formulate the exact computation of $\chi'^*_\mathrm{phys}(G)$ as a linear programming problem, which we solve for an extensive collection of random geometric graphs used to instantiate networks in the physical interference model. We have found that, depending on node density (number of nodes per unit deployment area), often $G$ is such that $\chi'^*_\mathrm{phys}(G)<\chi'_\mathrm{phys}(G)$. This bespeaks the possibility of increased network capacity by virtue of simply defining it so that edges are colored in the fractional, rather than the integer, sense.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Scheduling wireless links by vertex multicoloring in the physical interference modelComputer Networks, 2016
- An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph modelsJournal of Combinatorial Optimization, 2015
- Scheduling links for heavy traffic on interfering routes in wireless mesh networksComputer Networks, 2012
- REUSE: A combined routing and link scheduling mechanism for wireless mesh networksComputer Communications, 2011
- Routing, scheduling and channel assignment in Wireless Mesh Networks: Optimization models and algorithmsAd Hoc Networks, 2010
- Joint bandwidth allocation, element assignment and scheduling for wireless mesh networks with MIMO linksComputer Communications, 2008
- Models and solution techniques for frequency assignment problemsAnnals of Operations Research, 2007
- On the wireless local area network design problem with performance guaranteesComputer Networks, 2005
- Optimum positioning of base stations for cellular radio networksWireless Networks, 2000
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981