SIA OpenIR  > 工业控制网络与系统研究室
A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks
Ma CF(马超凡); Liang W(梁炜); Zheng M(郑萌); Sharif, Hamid
Department工业控制网络与系统研究室
Source PublicationIEEE SENSORS JOURNAL
ISSN1530-437X
2016
Volume16Issue:2Pages:515-528
Indexed BySCI ; EI
EI Accession number20161402177849
WOS IDWOS:000367260500030
Contribution Rank1
Funding OrganizationNatural 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
KeywordWireless Sensor Networks Relay Node Placement Geometric Disc Cover Network Connectivity Approximation Algorithm
Abstract

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.

Language英语
WOS KeywordSteiner Points ; Minimum Number ; Survivability ; Requirements ; Packing ; Design ; Set
Citation statistics
Document Type期刊论文
Identifierhttp://ir.sia.cn/handle/173321/18739
Collection工业控制网络与系统研究室
Corresponding AuthorLiang W(梁炜); Zheng M(郑萌)
Affiliation1.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
Recommended Citation
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.
Files in This Item: Download All
File Name/Size DocType Version Access License
A Connectivity-Aware(3167KB)期刊论文作者接受稿开放获取ODC PDDLView Download
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Ma CF(马超凡)]'s Articles
[Liang W(梁炜)]'s Articles
[Zheng M(郑萌)]'s Articles
Baidu academic
Similar articles in Baidu academic
[Ma CF(马超凡)]'s Articles
[Liang W(梁炜)]'s Articles
[Zheng M(郑萌)]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Ma CF(马超凡)]'s Articles
[Liang W(梁炜)]'s Articles
[Zheng M(郑萌)]'s Articles
Terms of Use
No data!
Social Bookmark/Share
File name: A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks.pdf
Format: Adobe PDF
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.