Set-covering-based algorithm for delay constrained relay node placement in Wireless Sensor Networks

CORC > 沈阳自动化研究所 > 中国科学院沈阳自动化研究所 > 工业控制网络与系统研究室

	Set-covering-based algorithm for delay constrained relay node placement in Wireless Sensor Networks
	Ma CF(马超凡); Liang W(梁炜); Zheng M(郑萌)
	2016
会议名称	2016 IEEE International Conference on Communications, ICC 2016
会议日期	May 22-27, 2016
会议地点	Kuala Lumpur, Malaysia
页码	1-6
通讯作者	梁炜
中文摘要	As Wireless Sensor Networks (WSNs) are widely used in time-critical applications, e.g., factory automation and smart grid, the importance of Delay Constrained Relay Node Placement (DCRNP) problem is becoming increasingly noticeable. This paper proposes a Set-Covering-based Approximation (SCA) algorithm to solve the DCRNP problem. The SCA deploys relay nodes by levels from the sink to sensor nodes. To avoid the limitation suffering by existing algorithms and ensure a polynomial time complexity, SCA employs a novel approach to formulate the deployment of relay nodes at each level as the set covering problem subject to delay constraints, and based on the classic greedy-set-covering algorithm, a set of relay nodes are placed to connect the nodes (sensor nodes and relay nodes) that are already connected to the sink. Since delay constraints are met at each level, all the sensor nodes will be connected to the sink via feasible paths fulfilling delay constraints. In addition, the elaborated analysis of the time complexity and the approximation ratio of the SCA algorithm is given out. Extensive simulations show that SCA can significantly save deployed relay nodes in comparison to existing algorithms.
收录类别	EI ; CPCI（ISTP）
产权排序	1
会议录	2016 IEEE International Conference on Communications, ICC 2016
会议录出版者	IEEE
会议录出版地	Piscataway, NJ, USA
语种	英语
ISSN号	1550-3607
ISBN号	978-1-4799-6664-6
WOS记录号	WOS:000390993202009
内容类型	会议论文
源URL	[http://ir.sia.cn/handle/173321/18843]
专题	沈阳自动化研究所_工业控制网络与系统研究室
推荐引用方式 GB/T 7714	Ma CF,Liang W,Zheng M. Set-covering-based algorithm for delay constrained relay node placement in Wireless Sensor Networks[C]. 见:2016 IEEE International Conference on Communications, ICC 2016. Kuala Lumpur, Malaysia. May 22-27, 2016.