SIA OpenIR  > 工业控制网络与系统研究室
Delay Constrained Relay Node Placement in Wireless Sensor Networks: A Subtree-and-Mergence-based Approach
Ma CF(马超凡); Liang W(梁炜); Zheng M(郑萌)
Department工业控制网络与系统研究室
Source PublicationMobile Networks and Applications
ISSN1383-469X
2018
Volume23Issue:5Pages:1220–1232
Indexed BySCI ; EI
EI Accession number20170803360409
WOS IDWOS:000450361100010
Contribution Rank1
Funding OrganizationNatural Science Foundation of China under grant 61673371 and 71661147005, Youth Innovation Promotion Association, CAS (2015157) and the Program project of Beijing Municipal Education Commission (KM 201511417008), open project of Beijing Key Laboratory of Information Service Engineering (Zk20201402)
KeywordWireless Sensor Networks Delay Constraint Relay Node Placement Shortest Path Tree Approximationalgorithm
Abstract

Wireless Sensor Networks (WSNs) are applied in many time-critical applications, e.g., industrial automation and smart grid. This highlights the importance of Delay Constrained Relay Node Placement (DCRNP) problem that builds a path fulfilling a specified delay constraint between each sensor and the sink by using a minimum number of relays. Due to the NP-hardness of the DCRNP problem, in this paper, a polynomial time Subtree-and-Mergence-based Algorithm (SMA) is proposed to approximately solve the DCRNP problem. First, a shortest path tree rooted at the sink and connecting all sensors is built to check the feasibility of the DCRNP problem. If the DCRNP problem is feasible, then the paths of this tree are progressively merged at some relays, which are not limited to those relays lying in the originally the originally built shortest path tree, to save deployed relays while maintaining the obedience of delay constraints. With the repetition of this mergence, the number of deployed relays is gradually reduced. Furthermore, the approximation ratio and the time complexity of the proposed SMA are elaborately analyzed. Finally, extensive simulations are conducted to demonstrate the effectiveness of this work. Simulation results show that SMA can significantly save deployed relays comparing with existing algorithms.

Language英语
Citation statistics
Document Type期刊论文
Identifierhttp://ir.sia.cn/handle/173321/20226
Collection工业控制网络与系统研究室
Corresponding AuthorLiang W(梁炜); Zheng M(郑萌)
Affiliation1.Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China
2.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 Wireless Sensor Networks: A Subtree-and-Mergence-based Approach[J]. Mobile Networks and Applications,2018,23(5):1220–1232.
APA Ma CF,Liang W,&Zheng M.(2018).Delay Constrained Relay Node Placement in Wireless Sensor Networks: A Subtree-and-Mergence-based Approach.Mobile Networks and Applications,23(5),1220–1232.
MLA Ma CF,et al."Delay Constrained Relay Node Placement in Wireless Sensor Networks: A Subtree-and-Mergence-based Approach".Mobile Networks and Applications 23.5(2018):1220–1232.
Files in This Item: Download All
File Name/Size DocType Version Access License
Delay constrained re(2981KB)期刊论文作者接受稿开放获取CC BY-NC-SAView 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 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.