标题：An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models
作者：Wang, Cui; Yu, Jiguo; Yu, Dongxiao; Huang, Baogui; Yu, Shanshan
作者机构：[Wang, Cui; Yu, Jiguo; Huang, Baogui] Qufu Normal Univ, Sch Informat Sci & Engn, Rizhao 276826, Shandong, Peoples R China.; [Yu, Dongxiao] Univ Hong 更多
会议名称：20th International Conference on Computing and Combinatorics (COCOON)
会议日期：AUG 04-06, 2014
来源：JOURNAL OF COMBINATORIAL OPTIMIZATION
关键词：Wireless network; Shortest link scheduling; Approximation algorithm;; Hypergraph model; SINR
摘要：Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701-1712, 2010]. For the average scheduling length of is 1 / m of GOW*, where is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm to that of GOW* are , and , respectively. Where () is a constant called the SNR diversity of an instance G.