Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements

doi:10.1109/JSYST.2018.2838072

	Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements
	Ma, Chaofan 1; Liang, Wei 2,3; Zheng, Meng 2,3; Yang, Bo 4
	2019-09-01
发表期刊	IEEE SYSTEMS JOURNAL
ISSN	1932-8184
卷号	13 期号:3 页码:2570-2581
摘要	Wireless sensor networks are gradually employed in many applications that require reliable and real-time data transmission. As hop count is an important factor affecting end-to-end delay and reliability, we investigate the hop constrained relay node placement (HCRNP) problem in this paper. First, to achieve connectivity requirement, we study the connected HCRNP problem. Then, to design survivable network topologies against node failures, we study the 2-connected HCRNP problem. Correspondingly, two polynomial-time algorithms: cover-based 1-connected node placement (C1NP) and cover-based 2-connected node placement (C2NP) are proposed, respectively, to address the above two problems. Through rigorous analysis, we show that 1) C1NP has an approximation ratio better than existing algorithms for the connected HCRNP problem (i.e., O(1) for special settings and O(ln n) for arbitrary settings, where n is the number of SNs) and 2) C2NP is the first algorithm that can provide an explicit performance guarantee for the 2-connected HCRNP problem, i.e., whenever C2NP finds a feasible solution, the ratio of this solution to the optimal solution is guaranteed to be O(ln n). Finally, we verify the effectiveness of the proposed algorithms through extensive simulations.
关键词	Approximation algorithm quality of service relay node placement (RNP) set cover wireless sensor networks (WSNs)
DOI	10.1109/JSYST.2018.2838072
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2017YFE0101300] ; Natural Science Foundation of China[61673371] ; Natural Science Foundation of China[71661147005] ; Youth Innovation Promotion Association, Chinese Academy of Sciences[2015157]
WOS研究方向	Computer Science ; Engineering ; Operations Research & Management Science ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Operations Research & Management Science ; Telecommunications
WOS记录号	WOS:000482628500048
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：21[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4748
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liang, Wei; Zheng, Meng
作者单位	1.Zhongyuan Univ Technol, Software Coll, Zhengzhou 450007, Henan, Peoples R China 2.Chinese Acad Sci, State Key Lab Robot, Shenyang 110016, Liaoning, Peoples R China 3.Chinese Acad Sci, Key Lab Networked Control Syst, Shenyang 110016, Liaoning, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Ma, Chaofan,Liang, Wei,Zheng, Meng,et al. Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements[J]. IEEE SYSTEMS JOURNAL,2019,13(3):2570-2581.
APA	Ma, Chaofan,Liang, Wei,Zheng, Meng,&Yang, Bo.(2019).Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements.IEEE SYSTEMS JOURNAL,13(3),2570-2581.
MLA	Ma, Chaofan,et al."Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements".IEEE SYSTEMS JOURNAL 13.3(2019):2570-2581.