Shortest Link Scheduling Algorithms in Wireless Networks Under the SINR Model

This paper considers the shortest link scheduling problem in wireless networks under the signal-to-interferenceplus-noise ratio(SINR) model.We propose an O(log(l max /l min ))approximation algorithm called shortest link scheduling with power control (SLSPC) with oblivious power assignment and an O(l...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on vehicular technology 2017-03, Vol.66 (3), p.2643-2657
Main Authors: Jiguo Yu, Baogui Huang, Xiuzhen Cheng, Atiquzzaman, Mohammed
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Approximation
Approximation algorithms
Computer simulation
Feasibility studies
Interference
Mathematical analysis
Mathematical models
Numerical analysis
Numerical models
Oblivious power assignment
physical interference model
Power control
Production scheduling
Scheduling
shortest link scheduling (SLS)
Signal to noise ratio
signal-to-interference-plus-noise ratio (SINR)
State of the art
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the shortest link scheduling problem in wireless networks under the signal-to-interferenceplus-noise ratio(SINR) model.We propose an O(log(l max /l min ))approximation algorithm called shortest link scheduling with power control (SLSPC) with oblivious power assignment and an O(log 1+φ (l max /l min )-approximation algorithm called shortest link scheduling with uniform or mean power assignment (SLSUM) with uniform or mean power control, where φ > 0 is a constant serving as a regulatory factor for slight transmit power adjustment, and where l max and l min denote the lengths of the longest and shortest links, respectively. We conduct a rigorous theoretical performance analysis to analyze the feasibility and approximation factors of the proposed algorithms. We also carry out an extensive comparison-based simulation study, whose results indicate that the performances of SLSPC and SLSUM are superior over the state of the art as the set of the so-called "black and gray" links, which are difficult to schedule and should be sequentially scheduled, is completely removed by adjusting the transmit power appropriately via φ. Our numerical analysis demonstrates that the approximation ratios of our algorithms are tighter than the best known ratios.
ISSN:0018-9545
1939-9359
DOI:10.1109/TVT.2016.2580379