期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2015
卷号：2015
DOI：10.1155/2015/120812
出版社：Hindawi Publishing Corporation
摘要：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 , where is an estimate of the number of links.
