基于斯坦纳树和泰森多边形的连通恢复算法

• 作者: 张晶 张江 王茂秋
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 连通恢复 斯坦纳树 泰森多边形 备用节点移动
• 年，卷（期）: 2020,（8）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 1352-1358
• 页数: 7页
• 分类号: TP393
• 字数: 3740字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2020.08.004

摘要

针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法(CRAST).首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复.然后,用关键节点构建Delaunay三角网,通过Delau-nay三角网构建出整个无线传感器网络的泰森多边形拓扑结构.最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点.整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张晶	昆明理工大学信息工程与自动化学院	60	174	8.0	9.0
10	王茂秋	昆明理工大学信息工程与自动化学院	1	0	0.0	0.0