Delay constrained relay node placement in two-tiered wireless sensor networks: A set-covering-based algorithm | |
Liang W(梁炜); Zheng M(郑萌); Ma CF(马超凡) | |
刊名 | Journal of Network and Computer Applications |
2017 | |
卷号 | 93页码:76-90 |
关键词 | Wireless Sensor Networks Set cover Delay Relay node placement Approximation algorithm |
ISSN号 | 1084-8045 |
通讯作者 | Liang W(梁炜) ; Zheng M(郑萌) |
产权排序 | 1 |
中文摘要 | 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. Considering the benefits in terms of energy efficiency and scalability brought by the two-tiered topology, this paper studies the DCRNP problem in two-tiered WSNs. To address the NP-hardness, a Two-phase Set-Covering-based Algorithm (TSCA) is proposed to approximately solve this problem. To be specific, in the first phase, a Connectivity-aware Covering Algorithm (CCA) places Relay Nodes (RNs) to fully cover distributed sensor nodes with respect to delay constraints, and meanwhile CCA tries to reduce the number of connected components in the topology constructed in this phase so as to save the RNs deployed to build network connectivity. In the second phase, the network connectivity is built in obedience to delay constraints by a Set-Covering-based Algorithm (SCA) through an iterative manner, which formulates the deployment of RNs at each iteration as the set covering problem and solves this problem using a classic set covering algorithm. In addition, the elaborated analysis of time complexity and approximation ratio of the proposed algorithms is given out. Finally, extensive simulations demonstrate that TSCA can significantly save deployed RNs in comparison to existing algorithms. |
WOS标题词 | Science & Technology ; Technology |
类目[WOS] | Computer Science, Hardware & Architecture ; Computer Science, Interdisciplinary Applications ; Computer Science, Software Engineering |
研究领域[WOS] | Computer Science |
收录类别 | SCI ; EI |
语种 | 英语 |
WOS记录号 | WOS:000407659700006 |
内容类型 | 期刊论文 |
源URL | [http://ir.sia.cn/handle/173321/20503] |
专题 | 沈阳自动化研究所_工业控制网络与系统研究室 |
作者单位 | 1.The University of Chinese Academy of Sciences, Beijing 100049, China 2.Key Laboratory of Networked Control Systems, Sehnyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China 3.State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China 4.Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China |
推荐引用方式 GB/T 7714 | Liang W,Zheng M,Ma CF. Delay constrained relay node placement in two-tiered wireless sensor networks: A set-covering-based algorithm[J]. Journal of Network and Computer Applications,2017,93:76-90. |
APA | Liang W,Zheng M,&Ma CF.(2017).Delay constrained relay node placement in two-tiered wireless sensor networks: A set-covering-based algorithm.Journal of Network and Computer Applications,93,76-90. |
MLA | Liang W,et al."Delay constrained relay node placement in two-tiered wireless sensor networks: A set-covering-based algorithm".Journal of Network and Computer Applications 93(2017):76-90. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论