An improved algorithm for delay constrained relay node deployment in wireless sensor networks

作     者：Zhang, Qian Yao, Haiqing Zheng, Chaoqun Lian, Jie 

作者机构：Shanghai Maritime Univ Inst Logist Sci & Engn Shanghai Peoples R China Shanghai Maritime Univ Inst Logist Sci & Engn 1550 Haigang Ave Shanghai 201306 Peoples R China 

出 版 物：《TRANSACTIONS OF THE INSTITUTE OF MEASUREMENT AND CONTROL》 (Trans Inst Meas Control)

年 卷 期：2022年

核心收录：

学科分类：08[工学] 080401[工学-精密仪器及机械] 0804[工学-仪器科学与技术] 0811[工学-控制科学与工程] 081102[工学-检测技术与自动化装置] 

基　　金：Science and Technology Commission of Shanghai Municipality 

主　　题：Delay constrained relay node deployment wireless sensor networks 

摘      要：Given that Delay Constrained Relay Node Placement (DCRNP) problem is getting more and more attention in time-critical domains, this paper proposes an Improved Greedy-based Selection Algorithm (IGSA) to tackle such problem under delay and budget constraints. IGSA first employs communication cost matrix and Dijkstra s algorithm to detect whether the problem is solvable, then selects the amount and locations of deployed relay nodes (RNs) layer by layer by continuously calling the greedy coverage algorithm until all sensors have a feasible path to the sink under a preset delay constraint, and finally removes redundant RNs to reach the approximate optimal solution. Extensive simulations show that our approach can save 15%-30% of deployed RNs than the Two-phase Set-Covering-based Algorithm (TSCA), which is the state-of-the-art algorithm for the DCRNP problem, only with a slight sacrifice of solving time. Meanwhile, Ad Hoc On-Demand Distance Vector (AODV) routing protocol is applied to further examine the performance of the deployment results solved by TSCA and IGSA, respectively. Results show that every RN deployed by IGSA is involved in data forwarding, while IGSA deploys leisure RNs which do not participate in the data forwarding. Besides, compared with TSCA, the network formed by IGSA has lower network delay in the data transmission process, and the energy consumption of the central node and throughput of the two topologies are almost at the same level.