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!
|
| _version_ | 1850228658744066048 |
|---|---|
| author | Zi-Ao Zhou Chang-Geng Li |
| author_facet | Zi-Ao Zhou Chang-Geng Li |
| author_sort | Zi-Ao Zhou |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-25819ec4fa484690ae4873af1fb39f41 |
| institution | OA Journals |
| issn | 1550-1477 |
| language | English |
| publishDate | 2015-07-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-25819ec4fa484690ae4873af1fb39f412025-08-20T02:04:27ZengWileyInternational Journal of Distributed Sensor Networks1550-14772015-07-011110.1155/2015/120812120812Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference ModelZi-Ao ZhouChang-Geng LiA 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.https://doi.org/10.1155/2015/120812 |
| spellingShingle | Zi-Ao Zhou Chang-Geng Li Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model International Journal of Distributed Sensor Networks |
| title | Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model |
| title_full | Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model |
| title_fullStr | Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model |
| title_full_unstemmed | Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model |
| title_short | Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model |
| title_sort | approximation algorithms for maximum link scheduling under sinr based interference model |
| url | https://doi.org/10.1155/2015/120812 |
| work_keys_str_mv | AT ziaozhou approximationalgorithmsformaximumlinkschedulingundersinrbasedinterferencemodel AT changgengli approximationalgorithmsformaximumlinkschedulingundersinrbasedinterferencemodel |