Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model
A fundamental problem in wireless networks is the maximum link scheduling (MLS) problem. In this problem, interference is a key issue and past researchers have shown that determining reception using Signal-to-Interference plus Noise Ratio (SINR) is more realistic than graph-based interference models...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-07-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2015/120812 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A fundamental problem in wireless networks is the maximum link scheduling (MLS) problem. In this problem, interference is a key issue and past researchers have shown that determining reception using Signal-to-Interference plus Noise Ratio (SINR) is more realistic than graph-based interference models. Unfortunately, the MLS problem has been proven to be NP-hard for SINR interference models. To date, several approximation algorithms have been proposed to solve MLS under the SINR-based interference model. However, most of these works do not have either an approximation bound or a distributed version. To this end, we present a novel scheduling method with a constant approximation ratio which is much simpler and only 1/28 of it in past research. The improvement of constant ϕ also offers a better MLS set. In addition, based on our centralized method, we present a polynomial time, randomized, distributed algorithm, which only requires estimates of the number of links, and maximum and minimum link lengths. We prove its correctness and show that it can compute a MLS with time complexity of O ( lo g 2 n ) , where n is an estimate of the number of links. |
|---|---|
| ISSN: | 1550-1477 |