PSH: A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks
文献类型：期刊论文
| 作者 | Ma CF(马超凡) ; Liang W(梁炜); Zheng M(郑萌)
|
| 刊名 | Wireless Personal Communications
 |
| 出版日期 | 2016 |
| 页码 | 1-20 |
| 关键词 | Wireless sensor networks Delay constraint Relay node placement Shortest path tree Approximation algorithm |
| ISSN号 | 0929-6212 |
| 产权排序 | 1 |
| 通讯作者 | 梁炜 ; 郑萌 |
| 中文摘要 | Delay constrained relay node placement (DCRNP) problem minimizes the quantity of deployed relays that are employed to build at least one path between the sink and each sensor, while guaranteeing that the delay constraints for the built paths are fulfilled. Published literature only focus on the DCRNP problem in single-tiered wireless sensor networks (WSNs). Considering the benefits in terms of network scalability and energy consumption by the two-tiered network topology, this paper studies the DCRNP problem in two-tiered WSNs and proposes a pruning-and-substitution-based-heuristic (PSH) algorithm to solve the DCRNP problem. PSH consists of two phases, i.e., the covering phase and the connecting phase. In the covering phase, a shortest-path-based algorithm (SPA) is proposed to deploy relays at a subset of predetermined deployment locations such that each sensor is covered by at least one relay, meanwhile ensuring the obedience of delay constraints. Then, in the connecting phase, a tree-based connecting algorithm (TCA) is proposed to build the high-tier network connectivity. TCA first builds a shortest path tree to connect the relays deployed by SPA to the sink, and then, saves the deployed relays by gradually pruning or substituting them by the relays placed at the locations that several feasible paths pass through. The time complexity and the approximation ratio of this work are explicitly analyzed and extensive simulations are implemented to demonstrate its effectiveness. |
| 收录类别 | EI |
| 语种 | 英语 |
| 源URL | [http://ir.sia.cn/handle/173321/19236]  |
| 专题 | 沈阳自动化研究所_工业控制网络与系统研究室 |
| 推荐引用方式 GB/T 7714 | Ma CF,Liang W,Zheng M. PSH: A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks[J]. Wireless Personal Communications,2016:1-20. |
| APA | Ma CF,Liang W,&Zheng M.(2016).PSH: A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks.Wireless Personal Communications,1-20. |
| MLA | Ma CF,et al."PSH: A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks".Wireless Personal Communications (2016):1-20. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。