SIA OpenIR  > 工业控制网络与系统研究室
Delay constrained relay node placement in two-tiered wireless sensor networks: A set-covering-based algorithm
Ma CF(马超凡); Liang W(梁炜); Zheng M(郑萌)
Department工业控制网络与系统研究室
Source PublicationJournal of Network and Computer Applications
ISSN1084-8045
2017
Volume93Pages:76-90
Indexed BySCI ; EI
EI Accession number20172303731714
WOS IDWOS:000407659700006
Contribution Rank1
Funding OrganizationNatural Natural Science Foundation of China under grant 61673371 and 71661147005, Youth Innovation Promotion Association, CAS (2015157) and the 201511417008), Open Project of Beijing Key Laboratory of Information Service Engineering (ZK20201402).
KeywordWireless Sensor Networks Set Cover Delay Relay Node Placement Approximation Algorithm
AbstractAs 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.
Language英语
WOS HeadingsScience & Technology ; Technology
WOS SubjectComputer Science, Hardware & Architecture ; Computer Science, Interdisciplinary Applications ; Computer Science, Software Engineering
WOS Research AreaComputer Science
Citation statistics
Cited Times:5[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.sia.cn/handle/173321/20503
Collection工业控制网络与系统研究室
Corresponding AuthorLiang W(梁炜); Zheng M(郑萌)
Affiliation1.Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
2.State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
3.Key Laboratory of Networked Control Systems, Sehnyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
4.The University of Chinese Academy of Sciences, Beijing 100049, China
Recommended Citation
GB/T 7714
Ma CF,Liang W,Zheng M. 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 Ma CF,Liang W,&Zheng M.(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 Ma CF,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.
Files in This Item: Download All
File Name/Size DocType Version Access License
Delay constrained re(2476KB)期刊论文作者接受稿开放获取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: Delay constrained relay node placement in two-tiered 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.