基于多簇点简化的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为监测节点；当N   
    式中：表示在节点，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，监测节点不变。[page]

    步骤2：简化路径，减化过程分为两个步骤。
    (1)保留N个监测节点之间的所有路径；
    (2)当监测节点ni和簇节点nj间只存在一条路径ni→nj(N+1≤j≤N+M)，令nroot<=nj且；当监测节点ni和多个簇节点间存在路径时，为了保证网络能量消耗最小，则保留该节点到簇节点的最小路径min(cost(ni，nj))，且使该簇节点变为nroot。
    在简化监测节点与簇节点路径时，若监测节点和多个簇节点间存在路径时，则保留监测节点到簇节点的最小路径。由此可见，如果网络原拓扑是K连通的，则简化后的拓扑仍为K连通且是能量消耗最小的单簇点拓扑结构。
2．2 K-MST拓扑控制算法
    K-MST拓扑控制算法中，有如下定义：
    定义1：定义节点ni的邻居节点为{nj|nj∈V，j≠i)；
    定义2：规定网络中的边有惟一权值。给定两条边(u1，v1)∈E和(u2，v2)∈E，dist(·，·)表示两个节点间的欧氏距离，则边的权值函数w：E→R满足：
   
    id(u1)表示节点u的序号，可以取其ID号或者MAC地址。这样可以保证在图Gr中的权值惟一，即使是权值相同的边(u，v)和(v，u)。
在异构监测无线传感器网络图中，任意监测节点与簇节点间生成K条不相交路径的算法分四步进行。
    步骤1：将多簇点网络简化为单簇点网络，即。
    步骤2：求网络的最小生成树，生成各监测节点至簇节点的能量消耗最小路径，将这些路径作为网络信息采集和传输的主路径，整个网络能量消耗最小。
    步骤3：将主路径断开，在条路径中求最小生成树可保证节点有两条路径和簇点连通。
    步骤4：重复步骤3，生成直至网络K连通，则保证网络的K连通子图为。

3 实验结果和性能分析
    构建1 000 m×1 000 m无线传感器网络仿真区域，网络中随机布置监测节点70～140个不等，令网络中监测节点最大发射半径为400 m，取簇节点个数N=3，首先对该网络进行多簇点简化，然后分别采用YG6,3算法、FLSS3算法以及本文提出的K-MST算法(K=3)进行保证每个节点至簇节点有3条不相关路径的拓扑控制，对每种算法分别进行50次仿真，将所得的节点平均度数和未进行拓扑控制节点平均度数进行比较，如图1所示。

[page]

    从图1可以看出，随着网络规模增大，未进行拓扑控制的网络节点平均度数由11．4增加到23．37，且增长速度很快。采用三种拓扑控制算法均将节点的度数进行了有效的控制，将平均度数减小到了16以下，这三种算法中，本文提出的K-MST算法将节点平均度数保证在2．8～2．94之间，比其他两种算法更多地减少了路径的冗余，较小的网络冗余减少了数据传输过程中的数据冲突耗，可延长能量有限的无线传感器网络工作寿命，又可较好地保证网络的连通性。
    采用YG6,3算法、FLSS3算法以及3-MST算法分别进行50次仿真，将生成拓扑结构中平均链路长度和未进行拓扑控制的平均链路长度进行比较，如图2所示。

    从图2可以看出，由于网络规模增大，采用三种拓扑控制算法所得的网络平均链路长度均呈下降趋势，采用3-MST算法得到的平均链路长度最小。这意味着在采用3-MST算法生成拓扑的路径上进行数据传输，比另外两种算法可以消耗更少的能量，从而延长网络寿命。

4 结论
    针对异构监测传感器网络结构，设计了一个优化的拓扑控制方案，在减少网络冗余的同时兼顾了网络的容错性，并且保证生成拓扑可以有效延长网络生存周期。该拓扑控制方案在保证传感器网络K连通的前提下，可以最大限度减少传感器网络中的冗余路径，可以较好地均衡无线传感器网络能耗，延长网络生命周期。