Back to Search
Start Over
Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model.
- Source :
-
International Journal of Distributed Sensor Networks . 7/16/2015, Vol. 2015, p1-10. 10p. - Publication Year :
- 2015
-
Abstract
- 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(log2n), where n is an estimate of the number of links. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 15501329
- Volume :
- 2015
- Database :
- Academic Search Index
- Journal :
- International Journal of Distributed Sensor Networks
- Publication Type :
- Academic Journal
- Accession number :
- 109271983
- Full Text :
- https://doi.org/10.1155/2015/120812