Wireless link scheduling under a graded SINR interference model

In this paper, we revisit the wireless link scheduling prob-lem under a graded version of the SINR interference model. Unlike the traditional thresholded version of the SINR model, the graded SINR model allows use of “im-perfect links”, where communication is still possible, al-though with degraded performance (in terms of data rate or PRR). Throughput benefits when graded SINR model is used instead of thresholded SINR model to schedule transmissions have recently been shown in an experimen-tal testbed. Here, we formally define the wireless link scheduling problem under the graded SINR model, where we impose an additional constraint on the minimum qual-ity of the usable links, (expressed as an SNR threshold βQ). Then, we present an approximation algorithm for this problem, which is shown to be within a constant fac-tor from optimal. We also present a more practical greedy algorithm, whose performance bounds are not known, but which is shown through simulation to have much better average performance than the approximation algorithm. Furthermore, we investigate, through both simulation and implementation on an experimental testbed, the tradeoff between the minimum link quality threshold βQ and the resulting network throughput.