An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment and rate adjustment? We propose the first framework for approximation algorithms in the physical model of wireless interference that addresses these questions in full. The approximations obtained are at most doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement (or better). A key contribution is showing that the complex interference relationship of the physical model can be simplified, at a small cost, into a novel type of amenable conflict graphs. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.
Gupta and Kumar introduced the SINR model of interference communication in their influential paper @cite_28 . Moscibroda and Wattenhofer @cite_19 initiated worst-case analysis of scheduling problems in networks of arbitrary topology, which is also the setting of interest in this paper. There is a huge literature on wireless scheduling problems, but we focus here on algorithms with performance guarantees.
@cite_28 @cite_19
2111209182 2116021438 2039533850 2154570806
In this paper, we consider the classical problem of link scheduling in wireless networks under an accurate interference model, in which correct packet reception at a receiver node depends on the signa-to-interference-plus-noise ratio (SINR). While most previous work on wireless networks has addressed the scheduling problem using simplistic graph-based or distance-based interference models, a few recent papers have investigated scheduling with SINR-based interference models. However, these papers have either used approximations to the SINR model or have ignored important aspects of the problem. We study the problem of wireless link scheduling under the exact SINR model and present the first known true approximation algorithms for transmission scheduling under the exact model. We also introduce an algorithm with a proven approximation bound with respect to the length of the optimal schedule under primary interference. As an aside, our study identifies a class of "difficult to schedule" links, which hinder the derivation of tighter approximation bounds. Furthermore, we characterize conditions under which scheduling under SINR-based interference is within a constant factor from optimal under primary interference, which implies that secondary interference only degrades performance by a constant factor in these situations. In this paper, we revisit the problem of determining the minimum-length schedule that satisfies certain traffic demands in a wireless network. Traditional approaches for the determination of minimum-length schedules are based on a collision channel model, in which neighboring transmissions cause destructive interference if and only if they are within the "interference region" of the receiving nodes. By contrast, we adopt here a more realistic model for the physical layer by requiring that a threshold be exceeded by the signal-to-interference-plus-noise ratio (SINR) for a transmission to be successful. We present a novel formulation of the problem that incorporates various power and rate adaptation schemes while seamlessly integrating the generation of "matchings" (i.e., sets of links that can be activated simultaneously) by taking into consideration the SINR constraints at the receivers. For the formulated problem, we propose a column-generation-based solution method and show that it theoretically converges to a globally optimal solution, with a potential advantage of not having to enumerate all the feasible matchings a priori. We also discuss the influence of power control, spatial reuse, and variable transmission rates on network performance. Furthermore, we include aspects of the routing problem and provide computational results for our proposed column-generation-based solution procedure. We study the problem of distributed scheduling in multi-hop MIMO networks. We first develop a MIMO-pipe" model that provides the upper layers a set of rates and SINR requirements, which capture the rate-reliability tradeoff in MIMO communications. The main thrust of this study is then dedicated to developing CSMA-based MIMO-pipe scheduling under the SINR model. We choose the SINR model over the extensively studied matching or protocol-based interference models because it more naturally captures the impact of interference in wireless networks. The coupling among the links caused by the interference makes the problem of devising distributed scheduling algorithms particularly challenging. To that end, we explore CSMA-based MIMO-pipe scheduling, from two perspectives. First, we consider an idealized continuous time CSMA network. We propose a dual-band approach in which control messages are exchanged instantaneously over a channel separate from the data channel, and show that CSMA-based scheduling can achieve throughput optimality under the SINR model. Next, we consider a discrete time CSMA network. To tackle the challenge due to the coupling caused by interference, we propose a conservative" scheduling algorithm in which more stringent SINR constraints are imposed based on the MIMO-pipe model. We show that this suboptimal distributed scheduling can achieve an efficiency ratio bounded from below. Many published algorithms used for scheduling transmissions in packet radio networks are based on finding maximal independent sets in an underlying graph. Such algorithms are developed under the assumptions of variations of the protocol interference model, which does not take the aggregated effect of interference into consideration. We provide a probabilistic analysis for the throughput performance of such graph based scheduling algorithms under the physical interference model. We show that in many scenarios a significant portion of transmissions scheduled based on the protocol interference model result in unacceptable signal-to-interference and noise ratio (SINR) at intended receivers. Our analytical as well as simulation results indicate that, counter intuitively, maximization of the cardinality of independent sets does not necessarily increase the throughput of a network. We introduce the truncated graph based scheduling algorithm (TGSA) that provides probabilistic guarantees for the throughput performance of the network.