一种改进Delaunay三角剖分的辅助节点算法研究摘要：以无线传感器网络辅助节点为主要研究对象，利用Delaunay三角剖分技术获得网络节点的基础上，在传感器网络检测的目标区域内含有一些覆盖盲点的情况下，提出了一种能量有效的传感器网络辅助节点配置算法。利用模拟仿真试验表明，与原算法相比，该算法在网络覆盖率及算法运行时间等方面更具一定的优势。关键词：辅助节点;无线传感器网络;Delaunay三角剖分;覆盖盲点：TP393文献标识码：A：1009-3044（2019）14-0025-021引言无线传感器网络由大量传感器节点组成，通常它们被密集地布置在要测量的环境中来获取所需的数据信息。传感器节点配置是无线传感器网络研究的核心问题之一。无线传感器节点被广泛应用于一些场景信息监测中，为了提高无线传感器网络的灵活性，延长网络的生命周期，文献[1]运用Delaunay三角剖分的策略定义了节点之间的邻接关系，并且可以通过Delaunay三角剖分快速获取节点的邻接节点。文献[2]和文献[3]使用启发式连通支配集算法思想来选择活跃节点。文献[4]使用Voronic划分的减量构造将部分覆盖冗余节点转入能耗较低的睡眠状态，在能量效率、网络声明周期等方面得到了改进。本文在Delaunay三角剖分的连通算法基础上，提出了一种改进的辅助节点算法（CCV），该算法选择一些节点辅助覆盖构成连通网络，其中覆盖节点和辅助节点都为活跃节点。改进算法在网络覆盖率及算法运行时间优于原算法。2輔助节点构造改进算法的Voronoi划分Vor（R2，C）（如图1（a）），构造覆盖集C的Delaunay三角剖分Del（C）（如图1（b））。使用算法BFS遍历图Del（C）中所有长度不超过Rt的边，获得覆盖集C所有的连通覆盖子集，即每个连通覆盖子集内的任意两节点之间存在一条由覆盖节点组成的连通路径，如图1（b）的实线所示;用Ci表示第i个连通覆盖子集，每个覆盖子集Ci抽象为虚拟节点vi，将覆盖集C转换为一个虚拟节点集V。如图1（b）所示的图Del（C），转换后的虚拟节点集V为{v1，v2，v3，v4，v5}。若V仅有一个虚拟节点，则覆盖集C构成连通网络;否则，按照如下步骤选择辅助节点。第一步：依据CCV算法的Voronoi划分Vor（R2，S）和通信半径Rt，构造初始网络的UnitDelaunay三角剖分UDel（S），如图2所示。对图UDel（S）的任意边uv，按照公式cost（u，v）=||uv||a/max（eu，ev）b计算通信代价，其中max（eu，ev）表示节点u和v中剩余能量最大值，指数a和b为非负整数。第二步：若UDG图为连通图，则UDel图为UDG图的连通子图。将图UDel（S）的每个连通覆盖子集Ci抽象为虚拟节点vi，删除连接节点集Ci中两节点的边;当节点u?Ci与节点集Ci的m（?1）个节点连接时，保留通信代价最小的边连接节点u和虚拟节点vi。经过上述操作后，图UDel（S）变换为一个连通加权图，记为wUDel（S）。第三步：Del图一个连通图，但一些边的长度超过Rt。将图Del（C）的每个连通覆盖子集Ci抽象为虚拟节点vi，删除连接节点集Ci中两节点的边（即长度不超过Rt的边）;任意虚拟节点vi和vj，图Del（C）存在m（?1）条边连接覆盖集Ci和Cj，保留一条边连接虚拟节点vi和vj，将节点vi和vj在图wUDel（S）中的最短路径Path（vi，vj）上的通信代价作为该边的权值。经过上述操作后，图Del（C）变换为一个连通加权图Del（V），如图3（a）所示。第四步：使用Kruskal算法构造Del（V）的最小生成树Tree（V），每条边对应的最短路径上的节点即为辅助覆盖集C构成网络的节点，如图3（b）所示。3实验仿真分析为了评估算法性能，本文用C++实现算法与文献CVT+MST，其中算法CVT求解CVT覆盖节点、算法MST求解MST网关节点。运行环境为P2.0GHzCPU与2G内存;实验场景如下：给定感知半径Rs，在目标区域1000×1000内随机部署n个互不重叠的传感器节点。理论上，覆盖节点数量将与传感半径Rs有关，辅助覆盖节点构成连通网络的节点数量将与通信半径Rt有关;为此，本文将针对不同的Rt/Rs值，统计评估活跃节点的数量、剩余能量和发射功率以及算法执行时间等指标。3.1活跃节点的数量1）网络覆盖率是指所有网络覆盖目标区域的面积比率。在目标区域内随机部署1000～2000个节点，初始网络的覆盖率如图×所示;当Rs=50时，初始网络...