基于多级分簇的拓扑重构算法的研究

2016-11-21石文玉

长春师范大学学报 2016年8期

关键词：网络拓扑刚性电磁

石文玉

(安徽新华学院信息工程学院，安徽合肥 230087)

基于多级分簇的拓扑重构算法的研究

石文玉

(安徽新华学院信息工程学院，安徽合肥 230087)

针对大规模分布式的无线传感器网络的特殊应用场景，由于复杂电磁环境等因素导致传感器节点拓扑结构易受到破坏，本文在满足网络的连通性和鲁棒性的基础上，提出了一种多级分簇的拓扑结构，当拓扑结构遭到破坏后立刻恢复拓扑实现拓扑重构。仿真实验表明，该算法相在保持原算法特性的基础上可以有效延长网络的生命周期。

无线传感器网络；分簇；拓扑重构

无线传感器网络WSNs(Wireless Sensor Networks)[1]目前已被广泛应用于各个领域，而其相关技术问题也因应用场景的不同而被提出。无线传感器网络被应用于森林环境监测中，森林环境复杂多变，包括山体环境的差异、森林气候的变化、复杂的电磁环境及各种自然灾害都会对节点的无线通信信道造成干扰或者破坏。

网络拓扑(Network Topology)是指网络中各节点之间的特定的物理关系，即真实的或逻辑的排列方式[2]。对于无线传感器网络的节点构造的特点来说，节点一旦被撒布很难再回收，节点一般是依靠电池进行供电的，在早期拓扑设计时，算法让每个节点与基站直接通信是非常耗电的、不现实的，因此构建一个良好的网络拓扑结构对无线传感器网络节能来说非常重要。

1 问题描述

在复杂的电磁环境中，无线传感器网络拓扑极易受到破坏，其被破坏后如何快速恢复拓扑显得尤为重要。石文玉[3]提出了一种基于非均匀虚拟网格划分的拓扑重构算法(TCUVG算法)，根据传感器节点所在地理位置区域电磁环境的复杂度不同划分为若干个全覆盖且不重叠的正方形区域。通过数据分析表明，在电磁环境越复杂的区域，节点的无线通信就越容易受到干扰，因此电磁环境复杂度越高的地方矩形区域面积越小，簇头节点数量越多，相对“死亡”概率越小。在拓扑重构算法中根据快速性原则提出了备用节点的选举公式，将主参数在其簇的上下跳簇头节点所在通信范围内的普通节点优先选为备用簇头节点。该算法简单，在计算备用簇头节点时对网络资源消耗较小。但该算法存在以下问题：(1)簇树状型初始拓扑搭建时使用非均匀虚拟网格划分的方法来进行簇的划分，矩形区域较大的簇头节点的压力过大；(2)在备用簇头选举时，为了满足快速恢复拓扑，要求备用簇头节点尽可能在上下跳节点的通信范围之内，选举概率较低。

本文在TCUVG算法的基础上，针对上述问题提出了一种多级分簇拓扑重构算法TCUVG-MH。该算法在快速恢复拓扑的基础上，在电磁环境复杂度较高的地方，采用多级分簇的方式来完成粗头节点的分级，通过多个簇头节点之间生成最小刚性图。

2 图论基础知识描述

刚性图，即在保证各边长度不变的情况下，一个图不会发生形变，否则称为可变形图。若刚性图的任意一条边被删除都会导致图形可变，则此图称为最小刚性图，如图1所示。

图1 可变形图、刚性图、最小刚性图图示

图2 三级分簇式拓扑

如图1所示，最小刚性图中每个顶点至少有两条相邻边[4]，因此最小刚性图用于网络拓扑中具有较小的通行复杂度和较强的鲁棒性。通过最小刚性图建立网络拓扑可以有效地均衡负载，形成有效的最优路径，从而减少链路能量消耗，延长网络的生存时间。

Tay and whitely[5]证明了下面两个引理。

(1)

则子矩阵对应的边和N个顶点构成了最小刚性图。

引理2 若G′(v′,ε′)是刚性图G(v,ε)的一个子图，由其它刚性图的子图G″(v″,ε″)替代得到的图仍是刚性的。

3 TCUVG-MH算法

本文在TCUVG设计的网络应用场景的基础上，提出了一种三级分簇式的拓扑重构算法，该算法中拓扑结构包含簇头节点(CH)、二级簇头节点(SCH)、普通成员节点(Node)，如图2所示。

如2图所示，根据三级分簇拓扑结构，在电磁环境复杂度较低的区域进行分级，其中普通节点收集其检测区域的信息，子簇头节点SCH汇聚其子簇所有节点信息并传输给簇头节点CH，最后簇头节点按照最小刚性图原则生成链路进行通信。

在复杂电磁环境中，在满足拓扑快速重建的基础上节约能耗，算法的核心内容如下：

第一，根据节点所处环境的电磁环境的复杂度的不同将网络用非均匀虚拟网格划分为若干个矩形区域。这样保证了电磁环境复杂的区域簇头节点数量相对多，从而减少簇头通信被破坏的几率。

第二，对电磁环境复杂度最低的区域，即矩形区域划分最大的区域按照三级分簇拓扑算法进行分级。(a)将簇内节点当前剩余能量进行排序；(b)选择其中能量最高的节点作为CH，再选择次能量较高的M个节点作为SCH。此方法可以在一个网格内通过子簇头分担簇头节点的任务，有效避免了簇头节点的大能耗问题，保证了网络负载的均衡，达到延长网络生存时间的目的。

第三，备用簇头节点的选举，在TCUVG-MH算法中设置三个参数：节点的通信范围、剩余能量、子簇头通信范围。

判断节点是否能称为备用簇头节点的判决式为

(2)

其中，ei,j为节点剩余能量，α的数值由(3)(4)判定。

首先，根据主参数判断节点是否在其所在簇的上下跳簇头节点的通信范围内。

(3)

(4)

当(3)(4)同时成立时，α=1，否则α=0。

当α=0时，根据上述思想判断节点是否在子簇簇头节点的通信范围内。

(5)

(6)

当(5)(6)同时成立时，有β=1，否则β=0。节点的drr最大时，该节点担任备用簇头节点。

在数据包中增加一个信息位SBCL(standby cluster head)，信息位的数值为0或1。SBCL=1时表明该节点的drr数值最大为备用簇头节点，其它节点的SBCL=0。

根据最小刚性图的方法，簇头节点CH之间进行拓扑优化，该拓扑保证簇头节点都是2-连通的。根据引理2，当簇头节点需要更换时不需要重新生成拓扑，只需在簇内找到一个新的簇头节点代替原簇头节点，这样可以保证新的拓扑能是最小刚性图。

在数据传输阶段，簇头节点在固定的时隙向基站发送数据包，若基站在某一时隙未收到其所在网格的数据包，则立刻通知备用簇头节点担任簇头。

4 仿真实验及分析

本文使用Matlab软件根据文献[3]中的参数对TCUVG-MH算法进行大规模网络的仿真实验，在1000×1000 m2的范围内随即撒布n个节点(n=1500,2000,2500,3000)，节点传输最大半径为200m，传输的初始能量为0.5J，Eelec为50nJ，εfs为10pj/(bit·m2)，εmp为0.0013pj/(bit·m4)。

通过表1可以看出，网络中备用簇头的选举概率随着网络规模的增大而增大，且由于在网格中添加了多级的簇头节点，使得TCUVG-MH算法比原算法的选举概率要大。

表1 网格中备用簇头选举概率

本文提出的TCUVG-MH算法在TCUVG算法满足快速拓扑重构的基础上，提出了多级分簇的初始拓扑构建，子簇簇头节点的出现使得网格中备用簇头节点的选举概率大大增加，基于最小刚性图构建簇头节点之间的通信链路，簇头节点之间至少是2-连通，当网络通信中断时，上述两个举措大大降低了网络的拓扑重构时间，如图3所示。在多级分簇思想中，提出了子簇簇头的选举，其大大降低了簇头节点的能量损耗，均衡了网络负载，延长了网络生存时间，如图4所示。

图3 网络死亡时网络拓扑重构时间

图4 网络生存时间

5 结语

本文中算法设计目标为快速拓扑重构，针对TCUVG算法的不足提出了一种基于最小刚性图的多级分簇的拓扑重构算法，分级中选举的子簇簇头节点可以增大备用簇头节点的选举概率，缩短拓扑重构的时间。同时为了避免在非均匀虚拟网格划分时，矩形区域大的簇中簇头节点因能耗过大而过早死亡从而导致整个网络的生存时间短，子簇簇头分担簇头节点的负载延长了网络的生存时间。仿真结果表明，TCUVG-MH算法适用于大规模网络且具有较好的优化效果。

[1]Tubaishat M,Madria S.Sensor Networks:AnOverview[J].IEEE Potentials,2003,22(2):20-23.

[2]Wikipedia.Network topology[EB/OL].(2016-01-01)[2016-02-03]. http://en.wikipedia.org/wiki/Network_topology.

[3]石文玉,鹿建银.基于非均匀虚拟网格的无线传感器网络拓扑重构算法[J].赤峰学院学报:自然科学版,2014，189(30):20-22.

[4]Luo X Y,Li S B,Guan X P.Automatic generation of min-weighted persistent formations[J].Chinese Physics B, 2009, 18(8):3104-3114.

[5]Tay T S,Whiteley W.Generating isostaticframeworks[J].Structure Topology,1985(11):21-69.

Research on Multi-layer Hierarchical Clustering Topology Construction Algorithm

SHI Wen-yu

(School of Information Engineering, Anhui Xinhua University, Hefei Anhui 230087, China)

A multi-layer hierarchical clustering topology for large-scale distributed wireless sensor networks is presented. This algorithm is proposed based on keeping good connectivity and robustness because that topology is easily damaged in complex environment. The results show that this algorithm can increase the lifetime of network based on keeping the original features.

wireless sensor networks; clustering; topology reconstruction