中国科学院沈阳自动化研究所机构知识库
Advanced  
SIA OpenIR  > 工业控制网络与系统研究室  > 期刊论文
题名: 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 sensor networks ; Delay constraint ; Relay node placement ; Shortest path tree ; Approximation algorithm
刊名: Wireless Personal Communications
ISSN号: 0929-6212
出版日期: 2016
页码: 1-20
产权排序: 1
项目资助者: Natural Science Foundation of China under Grant 61304263, 61673371 and 71602124, and Liaoning Provincial Natural Science Foundation of China under Grant 2014020081.
摘要: 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.
语种: 英语
内容类型: 期刊论文
URI标识: http://ir.sia.cn/handle/173321/19236
Appears in Collections:工业控制网络与系统研究室_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
PSH_ A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks.pdf(1490KB)期刊论文作者接受稿开放获取View Download

Recommended Citation:
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.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[马超凡]'s Articles
[梁炜]'s Articles
[郑萌]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[马超凡]‘s Articles
[梁炜]‘s Articles
[郑萌]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
文件名: PSH_ A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

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

 

 

Valid XHTML 1.0!
Copyright © 2007-2016  中国科学院沈阳自动化研究所 - Feedback
Powered by CSpace