基于非均匀虚拟网格的无线传感器网络拓扑重构算法

石文玉，鹿建银

（安徽新华学院 信息工程学院，安徽 合肥 230031）

基于非均匀虚拟网格的无线传感器网络拓扑重构算法

石文玉，鹿建银

（安徽新华学院 信息工程学院，安徽 合肥 230031）

拓扑控制是无线传感器网络研究中一个十分重要的技术问题.根据无线传感器网络的通信特点，本文提出了一种采用基于网络空间非均匀虚拟网格的方式，旨在复杂环境中无线通信遭到破坏时如何快速重建拓扑的方法.仿真结果表明，与传统算法相比，该算法在通信突然中断的情况下可以快速恢复拓扑，并且该算法更适用于大规模网络.

拓扑控制；无线传感器网络；拓扑重构

无线传感器网络（WSN，wireless sensor network）是一种特殊的Adhoc网络，由一组低成本、体积小、多功能的传感器节点通过自组织方式组成.传感器节点间相互协作感知、采集和处理其覆盖区域内感知对象的信息，并对其进行处理，发布给观察者[1,2].传感器网络具有易部署、自组织、高容错、可靠性等特点，在诸多领域应用前景广阔.

无线传感器网络（WSN）是由部署在监测区域内大量微型传感器节点组成，通过无线通信方式形成一种多跳的、自组织的网络.其主要目的是通过集成化的微型传感器协作地对监测区域进行实时监测、感知和采集受控对象的状态数据，如温度、光强度、噪声、压力、运动物体大小、速度和方向等，这些数据通过无线方式被发送并传送到用户终端.

1 问题描述

网络拓扑（network topology）是指网络中各成员之间特定的物理的即真实的、或逻辑的即虚拟的排列方式[3].在无线传感器网络中，要想每个节点都能与基站直接通信是不实际的，那么构建一个好的网络结构，实现终端节点采集的数据通过多跳的方式传送到基站是非常重要的.

无线传感器网络的基本特点是对基础设施要求低，节点携带的能量有限，无线通信易受干扰.无线传感器网络技术被广泛应用于社会生活的各个角落，例如在军事、科学研究、生产等领域，其社会价值巨大.而此项技术经常被应用于例如工业控制、地理环境、边境复杂通信信号覆盖等多种复杂环境下.在上述复杂环境中，网络的动态拓扑易经常发生变化，如何重新迅速建立新的拓扑显得尤为重要.

本文提出了一种WSN基于非均匀虚拟网格划分的拓扑重构算法，旨在于网络某个或部分节点的通信遭到破坏后，在短时间内迅速恢复拓扑.

2 非均匀虚拟网格划分

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

3 拓扑重构算法描述

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

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

3.2 当簇头节点的通信中断时，由于簇头节点所承担网络通信任务的特殊性，将会导致整个簇内的数据无法得到实时的处理和转发，而且会导致链路中需要经过此簇头进行数据转发的簇的数据无法得到及时的转发.此情况对于整个网络的数据传输都有着很大的影响.

因此，簇头节点通信中断后，如何重新快速建立链路是本文算法的核心内容.

具体算法如下：

（1）簇头节点对簇内数据进行处理，向基站进行转发，在簇头向基站发送的数据包中加上一个信息位ngrid，即其所在网格的编号，此数值唯一且不变.

（2）簇内成员节点将采集到的数据向簇头发送，在此数据包上增加一个信息位SBCL（standbyclusterhead），该信息位数值为0或1.数值为1时，表示为节点为当前备用簇头节点；数值为0时，表示节点不是当前备用簇头节点.

（3）备用簇头节点的选择主要依据首选和备选两个参数.首选参数是节点是否在当前簇头所在链路中上下跳节点的通信范围内，若在此通信范围内则作为备用节点之一，首选参数即是SBCL数值；备选参数是节点当前剩余的能量，当满足主参数时，拥有剩余能量多的节点优先当选.由于本算法的首要目的是快速重构链路，因此在满足快速的前提下，再考虑节点的能耗问题.

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

Drr判决式中α的数值由式3-2、3-3决定.

节点位置信息表示为(xij,yij)，根据主参数首先判断节点是否在其所在簇上下跳簇头节点的通信范围内：

其中，(xi2j2-yi2j2)表示为当前可能成为新簇头节点的位置坐标，(xi1j1,yi1j1)表示为上一跳簇头节点的位置坐标，(xi3j3,yi3j3)表示为下一跳簇头节点的位置坐标，i1≠i2≠i3且j1≠j2≠j3

当式3-2、3-3同时成立时，α=1；否则α=0；

节点的drr最大时，该节点担任备用簇头节点.

在选举备用簇头的判决式中，根据通信半径范围的选举备用簇头时会出现三种情况：

第一种情况：簇内成员节点中有满足α=1的节点，则在这些节点中根据判决式3-1选出能量最高的节点作为备用节点.

第二种情况：簇内成员节点中没有能满足α=1的节点，即如果所有的节点α=0，此时根据式3-3为此簇选择能够直接与上一跳簇头节点通信的备用簇头.当式3-3成立时，γ=1；否则γ=0.

此情况下，在满足γ=1的簇内成员节点中选择能量最高的节点作为备用簇头节点.

下一跳簇头由于上一跳簇头的失效而失去了可以转发数据的链路，此时，为下一跳的簇头选择新的备用链路来完成其数据的实时转发.具体方法是：当为当前簇头选择出备用簇头之后，通知下一跳簇头选择备用链路，下一跳簇头在一跳范围内寻找一个最近的簇头当做其备用的转发簇头.

第三种情况：所有簇内成员节点无法满足式3-3时，即节点的γ=0，则此簇内重新按照初始拓扑建立时竞选簇头的法则选择备用簇头，并在一跳范围内为自己选择备用链路.与第二种情况相同，并通知下一跳簇头选择备用链路.

（4）簇头节点在固定的时隙间都会向基站发送一条含有其网格信息的数据包，若基站在某一时隙没有收到该网格簇头节点发送来的数据包，则判断该簇头节点通信中断，即刻发送数据包通知该网格中备用的簇头节点担任簇头.

（5）若备用簇头节点或者选择的备用链路的簇头节点也失效，则重新选择簇头，并搭建链路.

4 仿真场景设计

为了简化仿真模型，将仿真场景中电磁情况按照复杂度分为三个等级：

（1）电磁环境最简单（即对无线通信干扰破坏最小）的为Ⅰ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅠ

（2）电磁环境较复杂（即对无线通信干扰破坏程度较大）的为Ⅱ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅡ

（3）电磁环境最复杂（即对无线通信干扰破坏最大）的为Ⅲ级，假设在此环境下节点通信遭到干扰或者破坏的概率为：PⅢ

在已有的分簇算法中，对网络初始拓扑的设计一般有：mesh型，即每个CH到BS为一跳，如LEACH算法；最短路径树，如Dijkstra算法[44]；多跳链路，如DAEA算法等.

本文设计一种局部树状的多跳链路，具体定义如下：链路中簇头与簇头之间距离为一跳；每个簇头只与离其最近的两个簇头相连作为上一跳簇头节点和下一跳簇头节点；当簇头节点是位于电磁环境为Ⅲ级时，此簇头节点作为其所在链路的终端簇头节点，在此簇头周围若存在位于同等级环境的簇头节点亦可以申请加入其上一跳簇头，即局部树状拓扑结构产生，如图4-1所示.

图4-1 局部树状多跳链路示意图

假设链路的跳数限制为10跳，通过仿真计算，本文设计的拓扑结构在复杂电磁环境中通信中断的概率较小，更适用于此环境下无线传感器网络的应用.

5 仿真结果及分析

MATLAB仿真软件模拟TCUVG算法中的网络环境，在仿真实验中布置了1000*1000的网络环境，用非均匀虚拟网格对整个网络进行划分，以区别监测区域电磁环境的不同，再随机布撒N个节点，节点一旦布撒则不再移动.如图5-1所示.

图5-1 节点数为1000的网络初始拓朴

表5-1是对节点数分别为：1500、2000、2500、3000时，整个网络中能够找到备用簇头的网格的概率，式5-1：

其中，nsbch为选举的备用簇头的数量，ngrid为整个网络中网格数

表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-2中，当节点密度高比节点密度低的网络重构时间增加是由于：当节点密度高时，簇头节点到达基站的链路数目会增多，这样簇头节点通信失败后，基站判断收到数据包延时会加大，通知备用簇头时间会加大，增加了拓扑重构的时间.图5-3可以看出，当节点密度增大时，整个网络的备用簇头的选择概率很大，因此，整个网络中用于拓扑重构的时间大大降低.

6 结束语

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

〔1〕Akyildiz I F, Weilian S, Sankarasubramaniam Y, et al.A Survey on Sensor Networks [C].IEEE Communications Magazine,2002,40(8):102-11.

〔2〕Tilak S, Abu-Ghazaleh NB, Heinzelman W.A Taxonomy of Wireless Micro-sensor Network Models [C].Mobile Computing and Communications Review, 2002, 1(2):1-8.

〔3〕http://en.wikipedia.org/wiki/Network_topology[OL].

〔4〕石文玉,高飞.复杂电磁环境对跨境民族影响研究[J].云南民族大学学报：自然科学版，2012,21（S1）：36-38.

TP393

A

1673-260X（2014）03-0020-03

物联网下的IPv4-IPv6过渡技术的研究(2011zr011)；省级质量工程项目“IT服务外包应用型人才培养模式创新实验区”[教高〔2009〕9号]；IT服务外包示范实验实训中心(2011sysxx01)；省级质量工程项目“IT服务外包示范实习实训中心”（皖教秘高〔2011〕66号）；安徽新华学院校级重点学科建设资金项目(zdfcx201101)