TY - GEN
T1 - A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model
AU - Xu, Xiao Hua
AU - Tang, Shao Jie
PY - 2009/5/18
Y1 - 2009/5/18
N2 - Link scheduling is crucial in improving the throughput in wireless networks and it has been widely studied under various interference models. In this paper, we study the link scheduling problem under physical interference model where all senders of the links transmit at a given power P and a link can transmit successfully if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR) at the corresponding receiver is at least a certain threshold. The link scheduling problem is to find a maximum "independent set" (MIS) of links, i.e., the maximum number of links that can transmit successfully in one time-slot, given a set of input links. This problem has been shown to be NP-hard [10]. Here we propose the first link scheduling algorithm with a constant approximation ratio for arbitrary background noise N ≥ 0. When each link l has a weight w(l) > 0, we propose a method for weighted MIS with approximation ratio [Math Equation] is the Euclidean length of a link l.
AB - Link scheduling is crucial in improving the throughput in wireless networks and it has been widely studied under various interference models. In this paper, we study the link scheduling problem under physical interference model where all senders of the links transmit at a given power P and a link can transmit successfully if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR) at the corresponding receiver is at least a certain threshold. The link scheduling problem is to find a maximum "independent set" (MIS) of links, i.e., the maximum number of links that can transmit successfully in one time-slot, given a set of input links. This problem has been shown to be NP-hard [10]. Here we propose the first link scheduling algorithm with a constant approximation ratio for arbitrary background noise N ≥ 0. When each link l has a weight w(l) > 0, we propose a method for weighted MIS with approximation ratio [Math Equation] is the Euclidean length of a link l.
KW - Approximation algorithm
KW - Independent set
KW - Link scheduling
KW - Physical interference model
UR - https://www.scopus.com/pages/publications/70450206413
U2 - 10.1145/1540343.1540347
DO - 10.1145/1540343.1540347
M3 - Conference contribution
AN - SCOPUS:70450206413
SN - 9781605585239
T3 - FOWANC'09 - Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing, Co-located with MobiHoc'09
SP - 13
EP - 20
BT - FOWANC'09 - Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing, Co-located with MobiHoc'09
PB - Association for Computing Machinery (ACM)
T2 - 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing, FOWANC 2009, Co-located with MobiHoc 2009
Y2 - 18 May 2009 through 18 May 2009
ER -