基于四边形斯坦纳树的无线传感器网络连通恢复

被引：37

作者：

陈洪生 ^{[1
,2
]}

石柯 ^{[1
]}

机构：

[1] 华中科技大学计算机科学与技术学院

[2] 湖北科技学院计算机科学与技术学院

来源：

计算机学报 | 2014年 / 37卷 / 02期

关键词：

无线传感器网络; 连通恢复; 四边形斯坦纳树; 启发式算法; 拓扑结构;

D O I：

暂无

中图分类号：

TP212.9 [传感器的应用]; TN929.5 [移动通信];

学科分类号：

080804 [电力电子与电力传动]; 140102 [集成电路设计与设计自动化];

摘要：

在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.

引用

页码：457 / 469

页数：13

共 4 条

[1]

Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks[J] Muhammad Imran;Mohamed Younis;Abas Md Said;Halabi Hasbullah Journal of Network and Computer Applications 2011,

[2]

Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation[J] Fatih Senel;Mohamed Younis Computer Communications 2011,

[3]

Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J] Sookyoung Lee;Mohamed Younis Journal of Parallel and Distributed Computing 2010,

[4]

最小网络[M] 越民义; 编著上海科学技术出版社 2006,

← 1 →