热门
A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks
文献类型：期刊论文
| 作者 | Ma CF(马超凡) ; Liang W(梁炜); Zheng M(郑萌); Sharif, Hamid
|
| 刊名 | IEEE SENSORS JOURNAL
 |
| 出版日期 | 2016 |
| 卷号 | 16期号:2页码:515-528 |
| 关键词 | Wireless sensor networks relay node placement geometric disc cover network connectivity approximation algorithm |
| ISSN号 | 1530-437X |
| 产权排序 | 1 |
| 通讯作者 | 马超凡 |
| 中文摘要 | 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 |
| 收录类别 | SCI ; EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000367260500030 |
| 源URL | [http://ir.sia.cn/handle/173321/18739]  |
| 专题 | 沈阳自动化研究所_工业控制网络与系统研究室 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。