标题: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
通讯作者:Yu, Jiguo
作者机构:[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
出版年:2016
卷:32
期:4
页码:1052-1067
DOI:10.1007/s10878-015-9908-4
关键词: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.
收录类别:CPCI-S;EI;SCOPUS;SCIE
WOS核心被引频次:1
Scopus被引频次:2
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84930365044&doi=10.1007%2fs10878-015-9908-4&partnerID=40&md5=0fad7070b5ccb0cb13f997f61f644947
TOP