Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks

doi:10.1016/j.comnet.2018.01.014

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks
	Xu, Chaonong 2; Ma, Kaichi 2; Xu, Yongjun 1
刊名	COMPUTER NETWORKS
	2018-03-14
卷号	133 页码:120-129
关键词	Successive interference cancellation Backbone networks Realtime Uplink scheduling Complexity
ISSN号	1389-1286
DOI	10.1016/j.comnet.2018.01.014
英文摘要	Relative to the networks with multiple independent sinks, in backbone -assisted networks, multiple sinks are connected together with high-speed wirelines. So, by exchanging decoded signals of User Equipments (UEs) among sinks through the backbones, more interferences to undecoded signals could be cancelled further. Thus, potential optimization rooms for reducing access delays are provided. In this paper, we study the problem of minimum uplink scheduling for Backbone-Assisted Successive Interference Cancellation-based Wireless Networks (BASICWNs), so as to reduce the mean access delays of UEs. We formulate the problem, and prove that it is NP-Complete by presenting a reduction from the partition problem. We further propose a polynomial-time heuristic algorithm based on the greedy strategy that as many UEs as possible are simultaneously scheduled in one slot. Experimental results show, relative to that with multiple independent sinks, the uplink frame length of BASICWNs is reduced by 48% with the heuristic algorithm proposed, and the performance is virtually very close to the optimum. (C) 2018 Elsevier B.V. All rights reserved.
资助项目	Science Foundation of China University of Petroleum, Beijing[ZX20150089] ; National Natural Science Foundation of China[61702487]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000428009900009
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/5747]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xu, Chaonong
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.China Univ Petr, Beijing Key Lab Petr Data Min, Beijing 102249, Peoples R China
推荐引用方式 GB/T 7714	Xu, Chaonong,Ma, Kaichi,Xu, Yongjun. Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks[J]. COMPUTER NETWORKS,2018,133:120-129.
APA	Xu, Chaonong,Ma, Kaichi,&Xu, Yongjun.(2018).Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks.COMPUTER NETWORKS,133,120-129.
MLA	Xu, Chaonong,et al."Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks".COMPUTER NETWORKS 133(2018):120-129.