基于多簇点简化的K容错能量均衡拓扑控制方案

摘要：针对异构监测传感器网络结构，设计了一个容错拓扑控制方案，在可以减少网络冗余的同时，兼顾了网络的稳定性，并且保证生成拓扑具有最小的能量消耗。该方案首先将异构监测传感器网络简化为同构传感器网络以简化计算，然后根据节点的位置信息，建立各监测节点到簇节点的能量消耗最小，并且可以保证K容错的K连通子图。该方案在保证传感器网络K连通的前提下，可以最大限度减少传感器网络中的冗余路径，且可以较好地均衡无线传感器网络能耗，延长网络生命周期。
关键词：异构无线传感器网络；客错拓扑控制；能量均衡；多簇点简化

0 引言
在无线传感器网络拓扑控制算法的研究中，利用简化冗余路径可以降低通信干扰，减少能量消耗，并且延长网络生存期。但是，以路径简化为主要方法的拓扑控制必定带来网络的健壮性下降。因此，在无线传感器网络拓扑控制研究中，需要考虑具有容错特性的拓扑控制问题。如何建立能够在当K-1个节点失效时，仍然具有连通性的无线传感器网络拓扑结构，是近年来研究的一个热点问题。
近年来，很多学者开展了关于容错拓扑近似算法的研究。如维持网络K连通的全局近似算法FGSS和局部近似算法FLSS。但是由于这两种算法不停地对比网络路径和判断网络是否达到K连通，开销较大。文献以同构网络为对象，提出了CBTC(a)算法。该算法中当a=2π／3K条件满足时，可使原网络的生成子图保持K连通性。文献对随机分布无线传感器网络节点的发射半径与形成K连通图的概率关系进行了分析，并提出Yp,K结构能够使生成K连通子图保持原拓扑的K连通性。文献提出了集中式和分布式算法K-UPVCS，但是该算法产生的拓扑结构极易产生回路而造成网络不能够连通。
本文在异构无线传感器网络模型上，提出了一种基于多簇点简化的K容错能量均衡拓扑控制方案。该方案在保证传感器网络K连通的前提下；可最大限度减少传感器网络中的冗余路径，且可以较好地均衡无线传感器的网络能耗。

1 异构无线传感器网络模型
定义异构无线传感器网络，V表示传感器网络中的节点集合，E表示节点之间的通信路径集合。传感器网络中包括三类节点：监测节点、接力节点和簇节点。设该传感器网络中，有N个用于信息监测的传感器节点Vs，该类节点用于采集监测区域内的信息，并将信息发送到邻居节点，且承担转发其他节点数据的任务；为了使监测区域内保持网络连通，布署了R个用于数据接力节点Vr，接力节点负责信息的转发。监测节点采集到的数据经多跳转发最终传送到簇节点Vc，簇节点一方面接收簇内的信息，同时参与簇之间的信息转发，设簇节点个数为M。在该无线传感器网络模型中，有V=Vs∪Vr∪Vc。

2 基于多簇点简化的K容错能量均衡拓扑控制方案
本文提出了一个K容错能量均衡拓扑控制方案。首先，为了简化运算，该方案将多簇点异构传感器网络简化为单簇点网络，简化后的网络连通性与简化前相同，且路径保持能量最小；然后，在简化后的网络结构上，提出了一个K-MST算法，根据节点的位置信息，建立各监测节点到簇节点的最小能耗的K连通网络。
2．1 异构传感器网络多簇点简化
首先对异构传感器网络模型进行化简。已知一个多簇点网络，包括N个监测节点和M个簇节点，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。如果1≤i≤N，则节点ni为监测节点；当Ni≤N+M时，ni为簇节点。

式中：表示在节点，ni的最大发射范围Rmax(ni)内，该节点到邻居节点的路径；dist(ni，nj)是节点，ni和nj之间的欧氏距离。由节点能量消耗模型可以算出路径上数据传输需消耗节点能量值cost(ni，nj)。异构传感器网络多簇点简化到单簇点的步骤描述如下：
步骤1：简化节点V→Vr，使Vr={n1，n2，…，nN，nN+1}，即将M个簇节点简化为1个节点nN+1，记为簇节点nroot，监测节点不变。