Fractional wireless link scheduling and polynomial approximate capacity regions of wireless networks
Wan, Peng-Jun . 2017
Fractional Link scheduling is one of the most fundamental problems in wireless networks. The prevailing approach for shortest fractional link scheduling is based on a reduction to the maximum-weighted independent set problem, which itself may not admit efficient approximation algorithms. In addition, except for the wireless networks under the protocol interference model, none of the existing scheduling algorithms can produce a link schedule with explicit upper bounds on its length in terms of the link demands. As the result, the polynomial approximate capacity regions in these networks remain blank. This paper develops a purely combinatorial paradigm for fractional link scheduling in wireless networks. In addition to the superior efficiency, it is able to provide explicit upper bounds on the lengths of the produced link schedule. By exploiting these upper bounds, polynomial approximate capacity regions are derived. The effectiveness of this new paradigm is demonstrated by its applications in wireless networks under the physical interference model and wireless MIMO networks under the protocol interference model.
Linear interference alignment (LIA) is one of the key interference mitigation techniques to enhance the wireless MIMO network capacity. The generic LIA feasibility amounts to whether or not a well…
Multi-packet reception (MPR) technology provides a means of boosting wireless network capacity without requiring additional spectrum. It has received widespread attention over the past two decades…
Fractional Link scheduling is one of the most fundamental problems in wireless networks. The prevailing approach for shortest fractional link scheduling is based on a reduction to the maximum-…