SIA OpenIR  > 工业控制网络与系统研究室
A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks
Ma CF(马超凡); Liang W(梁炜); Zheng M(郑萌); Sharif, Hamid
作者部门工业控制网络与系统研究室
关键词Wireless Sensor Networks Relay Node Placement Geometric Disc Cover Network Connectivity Approximation Algorithm
发表期刊IEEE SENSORS JOURNAL
ISSN1530-437X
2016
卷号16期号:2页码:515-528
收录类别SCI ; EI
EI收录号20161402177849
WOS记录号WOS:000367260500030
产权排序1
资助机构Natural Science Foundation of China [61233007, 61172145] ; Cross-Disciplinary Collaborative Teams Program for Science, Technology and Innovation entitled Network and System Technologies for Safety Monitoring and Information Interacting in Smart Grid through the Chinese Academy of Sciences
摘要

In two-tiered wireless sensor networks (WSNs), relay node placement is one of the key factors impacting the network energy consumption and the system overhead. In this paper, a novel connectivity-aware approximation algorithm for relay node placement in the WSNs is proposed to offer a major step forward in saving system overhead. In particular, a unique local search approximation algorithm (LSAA) is introduced to solve the relay node single cover (RNSC) problem. In this proposed LSAA approach, the sensor nodes are allocated into groups and then a local set cover (SC) for each group is achieved by a local search algorithm. The union set of all the local SCs constitutes a SC of the RNSC problem. The approximation ratio and the time complexity of the LSAA are analyzed by rigorous proof. In addition, the LSAA approach has been extended to solve the relay node double cover problem. Then, a relay location selection algorithm (RLSA) is proposed to utilize the resulting SC from the LSAA in combining RLSA with the minimum spanning tree heuristic to build the high-tier connectivity. As the RLSA searches for a nearest location to the sink node for each relay node, the high-tier network built by the RLSA becomes denser than that by existing works. As a result, the number of added relay nodes for building the connectivity of the high-tier WSN can be significantly saved. Simulation results clearly demonstrate that the proposed LSAA outperforms the approaches reported in literature and the RLSA-based algorithm can noticeably save relay nodes newly deployed for the high-tier connectivity.

语种英语
关键词[WOS]Steiner Points ; Minimum Number ; Survivability ; Requirements ; Packing ; Design ; Set
引用统计
被引频次:16[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.sia.cn/handle/173321/18739
专题工业控制网络与系统研究室
通讯作者Liang W(梁炜); Zheng M(郑萌)
作者单位1.Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang, China
2.University of Chinese Academy of Sciences, Beijing, China
3.Department of Computer and Electronics Engineering, University of Nebraska-Lincoln, Omaha, NE, United States
推荐引用方式
GB/T 7714
Ma CF,Liang W,Zheng M,et al. A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks[J]. IEEE SENSORS JOURNAL,2016,16(2):515-528.
APA Ma CF,Liang W,Zheng M,&Sharif, Hamid.(2016).A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks.IEEE SENSORS JOURNAL,16(2),515-528.
MLA Ma CF,et al."A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks".IEEE SENSORS JOURNAL 16.2(2016):515-528.
条目包含的文件 下载所有文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
A Connectivity-Aware(3167KB)期刊论文作者接受稿开放获取ODC PDDL浏览 下载
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Ma CF(马超凡)]的文章
[Liang W(梁炜)]的文章
[Zheng M(郑萌)]的文章
百度学术
百度学术中相似的文章
[Ma CF(马超凡)]的文章
[Liang W(梁炜)]的文章
[Zheng M(郑萌)]的文章
必应学术
必应学术中相似的文章
[Ma CF(马超凡)]的文章
[Liang W(梁炜)]的文章
[Zheng M(郑萌)]的文章
相关权益政策
暂无数据
收藏/分享
文件名: A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。