无线传感器网络拓扑重构算法概述

1非均匀虚拟网格划分

无线传感器网络节点通过无线信道进行通信，在复杂环境下尤其是复杂电磁环境下，其通信极易扰甚至中断.节点所处的地理位置的不同，其所处环境的电磁环境由于非人为因素（地形环境）和人为因素（各种无线电业务）而不同[4].依据网络应用场景的各个地理位置区域电磁环境复杂度的不同将网络划分为若干个大小不同、相邻、不重叠且对网络能够全覆盖的正方形区域.电磁环境越复杂的地区，被划分的网格面积越小，而电磁环境相对较简单的区域，网格的面积越大.网络中的簇分别在每个网格中产生，这样非均匀的网格划分就可以使得在电磁环境简单的的区域簇的数量少，在电磁环境复杂的区域簇的数量多，这样可以相对减小处于复杂电磁环境下簇通信被破坏的几率.

2拓扑重构算法描述

分簇算法中，节点有两种不同角色：一种为簇头节点，负责整个簇内信息的收集和数据的处理以及簇间转发，管理或者控制簇内成员节点；一种为簇内普通节点，负责采集其所在监测区域内的数据.由于簇内普通节点与簇头节点所承担任务不同，其通信中断后对网络通讯造成的影响如下：

2.1簇内普通节点的通信受到干扰或者破坏时，节点通信中断，会导致其监测区域内的数据不能被实时采集.干扰消失后，通信重新恢复继续监测；若此节点的通信永久中断，则可人工或者机械重新布撒新的节点.可见，此类节点的通信中断对其所在的簇或者整个网络的影响是非常小的.

2.2当簇头节点的通信中断时，由于簇头节点所承担网络通信任务的特殊性，将会导致整个簇内的数据无法得到实时的处理和转发，而且会导致链路中需要经过此簇头进行数据转发的簇的数据无法得到及时的转发.此情况对于整个网络的数据传输都有着很大的影响.因此，簇头节点通信中断后，如何重新快速建立链路是本文算法的核心内容.具体算法如下：（1）簇头节点对簇内数据进行处理，向基站进行转发，在簇头向基站发送的数据包中加上一个信息位ngrid，即其所在网格的编号，此数值唯一且不变.（2）簇内成员节点将采集到的数据向簇头发送，在此数据包上增加一个信息位SBCL（standbyclusterhead），该信息位数值为0或1.数值为1时，表示为节点为当前备用簇头节点；数值为0时，表示节点不是当前备用簇头节点.（3）备用簇头节点的选择主要依据首选和备选两个参数.首选参数是节点是否在当前簇头所在链路中上下跳节点的通信范围内，若在此通信范围内则作为备用节点之一，首选参数即是SBCL数值；备选参数是节点当前剩余的能量，当满足主参数时，拥有剩余能量多的节点优先当选.由于本算法的首要目的是快速重构链路，因此在满足快速的前提下，再考虑节点的能耗问题.

3仿真场景设计

为了简化仿真模型，将仿真场景中电磁情况按照复杂度分为三个等级：（1）电磁环境最简单（即对无线通信干扰破坏最小）的为Ⅰ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅠ（2）电磁环境较复杂（即对无线通信干扰破坏程度较大）的为Ⅱ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅡ（3）电磁环境最复杂（即对无线通信干扰破坏最大）的为Ⅲ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅢ在已有的分簇算法中，对网络初始拓扑的设计一般有：mesh型，即每个CH到BS为一跳，如LEACH算法；最短路径树，如Dijkstra算法[44]；多跳链路，如DAEA算法等.本文设计一种局部树状的多跳链路，具体定义如下：链路中簇头与簇头之间距离为一跳；每个簇头只与离其最近的两个簇头相连作为上一跳簇头节点和下一跳簇头节点；当簇头节点是位于电磁环境为Ⅲ级时，此簇头节点作为其所在链路的终端簇头节点，在此簇头周围若存在位于同等级环境的簇头节点亦可以申请加入其上一跳簇头，即局部树状拓扑结构产生，如图4-1所示.假设链路的跳数限制为10跳，通过仿真计算，本文设计的拓扑结构在复杂电磁环境中通信中断的概率较小，更适用于此环境下无线传感器网络的应用.

4仿真结果及分析

MATLAB仿真软件模拟TCUVG算法中的网络环境，在仿真实验中布置了1000*1000的网络环境，用非均匀虚拟网格对整个网络进行划分，以区别监测区域电磁环境的不同，再随机布撒N个节点，节点一旦布撒则不再移动.如图5-1所示.通过表5-1可以看出，网络中备用簇头的选举概率随着网络的节点数的增大而增大，当网络规模一定时，节点数的增大表示节点的密度增大，此时根据式3-1选择到的备用簇头的概率也会增大.这样选择的备用簇头可以满足快速拓扑重构的条件，大大降低用于重新选举簇头节点和重新构建链路的时间.网络中节点由于其所处的电磁环境不同，按照复杂电磁环境场景设计中对节点失效后通信中断的概率设计，并对簇头节点通信中断后，网络重新构建拓扑，恢复通信所需的时间计算，对网络的拓扑重构时间进行计算，结果如图5-2、5-3所示.图5-2是TCUVG协议在节点为1500至3500之间的簇头平均重构时间，当节点数在1500-3500之间时，TCUVG协议是传统重构协议所用死亡时间的50%-63%，可以看出，TCUVG协议大大提高了用于拓扑重构的时间.本文定义：当网络中50%的节点死忙时，则整个网络死亡.在网络死亡前，整个网络中簇头节点用于拓扑重构的时间的统计，如图5-3.由于本算法中，提前对网络进行固定的分簇并且选举备用簇头，使得网络中簇头节点通信中断后不用再耗费时间用于分簇和簇头选举，备用簇头可以直接用于网络通信，此方法大大降低了网络用于拓扑重构的时间，仿真结果图也证明了这点.图5-2中，当节点密度高比节点密度低的网络重构时间增加是由于：当节点密度高时，簇头节点到达基站的链路数目会增多，这样簇头节点通信失败后，基站判断收到数据包延时会加大，通知备用簇头时间会加大，增加了拓扑重构的时间.图5-3可以看出，当节点密度增大时，整个网络的备用簇头的选择概率很大，因此，整个网络中用于拓扑重构的时间大大降低.

5结束语

本文设计了一种无线传感器网络应用在复杂环境下旨在快速恢复链路通信的基于非均匀虚拟网络的拓扑控制算法，并对算法进行了仿真分析，结果表明，与传统算法相比，本文设计的TCUVG算法在大规模无线传感器网络应用中拓扑重构时间大大降低.

作者：石文玉 鹿建银 单位：安徽新华学院 信息工程学院