一种基于地理位置的无线传感器网络路由算法

肖 达,肖明波

(1.诺基亚通信系统技术(北京)有限公司杭州研发中心, 浙江 杭州 310052; 2.杭州电子科技大学通信工程学院, 浙江 杭州 310018)

一种基于地理位置的无线传感器网络路由算法

肖 达1,肖明波2

(1.诺基亚通信系统技术(北京)有限公司杭州研发中心, 浙江 杭州 310052; 2.杭州电子科技大学通信工程学院, 浙江 杭州 310018)

针对基于地理位置信息的不同节点密度算法 (GLIDND)在能量有效性上的不足，为无线传感器网络提出了一种改进的基于地理位置信息的不同节点密度算法Enhanced-GLIDND.该算法从如下几个方面对GLIDND算法进行了改进:(1)根据能耗比在不同区域撒布不同密度的备用节点；(2)簇头的更替采用消息通知机制；(3)簇间蚁群路由算法将下一跳节点所在簇的累计能耗作为影响因子.仿真试验将Enhanced-GLIDND与EEF，GLIDND，LEACH和BCDCP算法作比较.结果表明，Enhanced-GLIDND算法在网络生命周期和能量有效性上都明显优于其他各算法.

无线传感器网络；不同节点密度；簇；网络生命周期

无线传感器网络被认为是21世纪最重要的技术之一，它将对人类未来的生活方式产生巨大影响.麻省理工学院的《技术评论》杂志(Technology Review)[1]评出了对人类未来生活产生深远影响的十大新兴技术,无线传感器网络位于这十种新技术之首.无线传感器网络是一种无基础设施的无线网络，它综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术,能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对这些数据进行处理，获得详尽而准确的信息，将其传送到需要这些信息的用户.

在无线传感器网络中，一般由一个或多个节点充当数据汇聚点(BS节点)网络中传感器节点收集的数据，通过多跳的方式传送到BS节点，BS节点将融合后的数据通过有线或无线的方式传送给观察者.在通信方式上，无线电、红外、声波等多种无线通信技术的发展为微传感器间通信提供了多种选择，尤其是以IEEE802.15.4为代表的短距离无线电通信标准的出现，为无线传感器网络的发展奠定了坚实的基础.

作为当今信息领域新的研究热点，无线传感器网络涉及多学科交叉的研究领域，有很多相关的技术有待研究，例如：网络拓扑控制、网络协议、定位技术、数据融合.而网络拓扑控制具有最重要的意义.通过拓扑控制，自动生成良好的网络拓扑结构，能够提高路由协议和MAC协议的效率，可为数据融合、时间同步和目标定位等很多方面奠定基础，有利于节省节点的能量，从而延长网络生命周期.所以，拓扑控制是无线传感器网络研究的核心技术之一.

本论文主要从层次型网络拓扑组织这个方面展开研究，对经典层次型拓扑组织算法LEACH[2]，BCDCP[3]进行深入分析，并针对我们之前提出的GLIDND算法的不足之处，提出一种改进的GLIDND层次型网络拓扑组织算法Enhanced-GLIDND.

1 GLIDND路由算法

无线传感器网络的节能路由算法往往都希望将能耗和负载均衡结合得尽可能完美.在层次型拓扑结构组织这个方向上，最早出现的一个算法就是LEACH算法.LEACH定义了“轮”(Round)的概念，每一轮存在初始化阶段和稳定阶段两个状态.初始化阶段是簇头的形成阶段.每个节点决定在当前“轮”中是否成为簇头，成为簇头的概率是一个建议的固定值，需要根据网络中节点的数目而定.在初始化阶段，每一个节点在0到1中选取一个随机数，如果这个随机数小于这一“轮”所设定的门限值Thresh，那么这个节点就成为簇头.在随机产生出簇头后，成为簇头的节点再向网络广播分簇信息，告知其他节点产生了一个新的簇头.其他节点接收到分簇消息后，根据信号强度来选择它要加入的簇群，并通知相应的簇头.这样在初始化阶段，就构成了以多个簇头为核心的簇群.各簇群中的节点通过TDMA方式与簇头进行通信.在稳定阶段，节点持续采集监测数据，传给簇头.簇头先对从各节点接收来的数据进行必要的数据融合处理，再将数据包转发给BS节点.LEACH算法能够相应地延长网络生命周期，但是该算法还存在很多不足的地方，如每次建立簇的过程会产生一定的额外开销，能量有效性较低；簇头选举的随机性使得簇头在地理位置上的分布不均匀；以及在大规模网络中，由于功率限制，节点并不一定能单跳向BS发送数据等.因此该算法还需要进一步完善和改进.目前，已经有很多学者在LEACH算法基础上提出了改进算法.

BCDCP算法针对LEACH算法的簇头节点分布不均匀的特性，在建立簇的过程中，于大于平均能量的节点中，选出两个相距最远的节点，作为簇头，将整个网络分为两个子簇，然后将子簇分割成更小的簇，直至分割到BS节点规定的簇头数目为止[3].这种分簇算法虽然保证了簇头节点在地理位置上分布的大致均匀，但是每轮的成簇开销非常大.针对LEACH算法单跳和BS节点通信的弊端，在簇间路由的问题上，BCDCP协议用多跳路由机制将数据传送给基站.路径的选择是先通过最小生成树算法[4]将所有簇头节点连通，然后随机选择一个簇头节点作为最终将数据传给基站的节点.随机选择簇头传递数据给基站有一定的合理性，因为太频繁地利用距离基站近的节点作为数据到达基站前的最后一跳，会严重消耗距离基站较近的节点的能量.因此，BCDCP算法的随机选择簇头传递数据给BS节点，将能耗平均地分配给了所有簇头节点.但是，这种簇间路由算法虽然将能耗在所有簇头节点间平均化了，但是在能量的有效性上不敢恭维.如果最远离BS节点的簇头被选为所有簇头节点汇聚数据到达BS节点前的最后一跳，那么能量的有效性还不如LEACH算法中簇头节点单跳与BS节点通信.

针对这两种典型的层次结构路由协议存在的问题，我们曾经提出一种更优的层次结构路由算法GLIDND[5].该算法借鉴GAF算法按虚拟单元格划分簇的思想[6]，将监测区域划分成若干固定的逻辑区域，形成一个个虚拟的网格(簇).并提出了“层”(level)(图1)的概念，把划分完单元格的距离BS节点垂直距离相同的一行单元格定义为一“层”.每一个簇内，根据剩余能量和地理位置信息选举出簇头，这就保证了簇头分布的均匀性.只有在簇头的能量低于某个阈值时，才需要更换簇头.这就避免了每“轮”成簇时的大量广播信息所消耗的能量.簇间路由采用一种改进的蚁群算法[7]，节点间距和节点剩余能量将作为两个主要的影响因素.这就保证了在蚁群算法收敛到最优路径以后，不会过度地使用某条路径而导致某些簇头节点因能量快速耗尽而对整个网络造成影响.达到了在同一“层”不同簇之间的负载平衡.但是，邻近BS节点的簇头，因为转发了大量数据，消耗了过多能量，而成为“热区”[8].距离BS越近，转发数据消耗的能量越多，于是，GLIDND算法根据划分逻辑区域后各区域能耗的大小，也可理解为距离BS节点的远近来决定备用节点密度的方法来解决热区问题.但是，GLIDND算法仍然存在若干缺点：

虚拟单元格分簇的思想保证了簇头分布的大致均匀性，但是，在每一个簇内，根据剩余能量和地理位置信息选举簇头的方案在中心位置簇头节点能量消耗过多而被轮换时，不得不选举出非中心位置的传感器节点作为簇头，降低了能量有效性.这种在单个簇内轮换簇头的方式是在以牺牲能量有效性换取负载均衡.

在每一个簇内，只有在簇头节点的能量低于某一阈值时，此簇才需要更通过选举方式更换簇头节点，一定程度上降低了LEACH，BCDCP算法每轮成簇时的广播开销.但是，通过选举方式更换簇头仍然需要大量的广播开销.

根据各区域距离BS节点的远近，在不同“层”撒布不同密度的备用节点的方案在一定程度上解决了“热区”问题.但是，在每一个区域，节点主要能耗实际上都集中在地理位置偏中心的簇头节点，而不是整个簇.于是，在同一“层”的整个区域内均匀地撒布备用节点是不够明智的.

簇间路由采用以下一跳簇头节点剩余能量和节点间距为影响因子的蚁群算法来均衡同一“层”不同簇之间的负载，容易出现偏差.比方说某簇头节点有两个邻居簇头节点可以作为下一跳，A节点的剩余能量为30%，B节点的剩余能量为80%，GLIDND算法很可能选取B节点作为下一跳.然而，B节点虽然剩余能量更多，它可能是因为本簇能量消耗过快而被重新选举出的第N(N>1)个簇头，A节点很可能是因为本簇能量消耗过慢还不曾被替换过的第一个簇头.所以，下一跳簇头节点剩余能量这一个影响因子并没有真实反映各簇的真实负载.

针对GLIDND算法的以上不足，我们提出了一种改进的GLIDND算法Enhanced-GLIDND.改进的GLIDND算法可以归纳为以下四个部分.

在第一“轮”循环开始时，首先，将这个传感区域进行划分，这个行为只出现在第一“轮”，以后的循环过程不会再对传感区域进行划分.其次，将GLIDND算法中在不同区域撒布不同密度备用节点的思想细化.根据对不同“层”之间簇头节点的能耗比预计，在不同“层”各簇的中心区域撒布不同密度的备用节点，同一“层”内各簇的中心区域备用节点密度相同.每一个簇内，根据簇头节点和单个非簇头节点的能耗比预计，在非中心区域给予非簇头节点相应数目的备用节点补给.Enhanced-GLIDND算法这种比GLIDND更加细化的撒布不同密度的备用节点的方案将能量有效性和纵向负载均衡结合得更好.

在第一“轮”循环进行区域划分之后便开始确立簇头，建立簇、簇头多跳路径.确立簇头时，综合考虑了节点剩余能量以及地理位置信息.建立簇头多跳路径的过程中，蚁群算法以邻居节点所在簇的累计能耗和节点间距作为影响因子.Enhanced-GLIDND算法选取簇间路由的影响因子更真实反映了不同簇的能耗，有效地均衡了横向负载.

第二“轮”后，每“轮”循环开始时，如果上一“轮”的簇头节点在上“轮”结束时的能量低于阈值0.2E0，此节点将发送一个消息通知距离它最近的节点(备用节点或簇内节点)作为新的簇头.该新簇头将其位置和能量等基本信息广播，簇内非簇头节点收到此广播报文后与新簇头协调TDMA调度.邻居簇头节点收到此广播报文后，据此更新簇间路由.选择下一跳的过程同第一“轮”一致.否则，不需要重新确立簇头.Enhanced-GLIDND算法由当前簇头节点消息通知距离最近的邻居节点作为新簇头的方案节省了GLIDND算法重新选举簇头所需要发送的大量广播包.

在每“轮”循环中，当簇头、簇头多跳路径以及TDMA调度均确定下来之后，节点便可以进行数据传输了.簇内的成员节点根据TDMA调度，在自己所在时隙内向簇头发送数据，簇头按照多跳路径的方向发送数据，直至将数据发送给BS节点.

2 改进的GLIDND算法

2.1传感区域的划分

改进的GLIDND算法Enhanced-GLIDND在区域划分上与GLIDND算法完全一致.根据GLIDND算法的设计思想，在进行分簇之前需要将整个传感区域进行划分，从传感器的计算能力和能量局限性考虑，Enhanced-GLIDND算法将划分区域任务交给了BS节点，首先传感区域内的传感器节点需要将自己的地理位置信息发送给BS节点，BS节点收集到这些信息之后进行统一划分.最后，BS节点再将划分之后的结果广播给传感区域内的各个传感器节点，给所有传感器节点分配对应的Cluster ID(簇ID).下面介绍具体的区域划分过程.这里仅考虑一般的网络情况，即BS在整个传感区域之外，并且距离整个传感区域比较远的位置，如图1所示.

图1 Enhanced-GLIDND算法拓扑图

这里我们先假设节点传输距离为R，为保证任意相邻单元格可以互相通信，必须满足：

R2>(2r)2+(2r)2

(1)

图2 传输距离的设定

接下来我们将说明划分出多少个区域数才能达到能量的最优利用，以及如何在不同区域撒布不同密度的备用节点.

2.2最优区域个数和不同区域备用节点密度的确定

将目标区域划分成一个个小的逻辑区域可以缩小数据通信距离，提高能效.同时各个区域并行运行成簇算法，也使网络响应速度得以提高.但是，区域数量的多少直接影响簇的数量和大小，根据目标区域面积、节点数量等参数来优化区域数量是提高系统整体性能的必然要求.

设有N个节点布置在面积为M*M的正方形目标区域中，目标区域被划分为m2个逻辑小区域，平均每个区域节点数为N/m2个.主要的能量消耗包括：每个簇头接收簇成员的数据，数据融合，发送数据给邻居簇头(Ech)；成员节点发送数据给簇头(Enon-CH)；各簇头的路由能耗(Ech-ch).

根据Enhanced-GLIDND算法中区域划分的思想，最靠近BS的一组簇头(level=m)，将收集到的本簇内的数据融合后直接发送给BS.其他簇头(level

Ech=

(2)

=

式中：

Eelec：发送电路和接收电路消耗的能量；

EDA：节点进行数据融合消耗的能量；

εfs：自由空间衰减信道模式放大指数；

εmp：多径衰减信道模式放大指数；

dCH-CH:簇头节点间距；

dtoBS: 簇头节点到基站的距离；

M：区域边长；

N：节点个数；

m：最优“层”数；

各簇的主要能耗都集中在位于中心区域的簇头，大部分备用节点的补给也集中在中心区域，于是，我们认为dCH-CH=r, 设dtoCH表示簇成员节点到簇头的通信距离，则每个簇内节点和本簇簇头的通信能耗为

Enon-CH=βEelec+βεfsd2to-CH

(3)

E(d2to-CH)=∬(x2+y2)ρ(x,y)dxdy

(4)

图3 单个簇内节点分布

因此，一个簇内的能耗为

(5)

令Ecluster=

路由能耗表示为Ech-ch, 对于level=m的簇头，将收到的包转发给BS，对于level

(6)

各簇头的路由能耗Ech-ch主要指簇头接收邻居簇头的数据并转发给路由方向的邻居簇头的能耗.鉴于所有簇头的数据包的最后一跳都是由level=m的区域内的簇头转发给BS，我们将每个簇头产生的数据包被转发的次数计为n+1(n=1,2…m-1)的形式.level=1的区域内簇头产生的数据包经过(m-2)+1次转发到达BS，level=2的区域内簇头产生的数据包经过(m-3)+1次转发到达BS，……，level=m-1的区域内簇头产生的数据包经过0+1次转发到达BS，level=m的区域内簇头产生的数据包不需要被转发，因此，不需要消耗转发能量.

因为每一“层”有m个簇，于是，在监测区域(level

于是，系统总能耗

Etotal=m*Ecluster1+(m2-m)*Ecluster2+hop_e*Ech-ch1+hop_i*Ech-ch2

(7)

(8)

(9)

由(8)(9)两式，我们可以得到使得总能耗最小的m解.下面，我们来看看如何撒布备用节点.这是Enhanced-GLIDND算法的最核心之处.

表1 一“轮”内各节点的能耗

由表1可知，每一“轮”，非簇头节点的主要能耗用于向簇头节点发送一个βbit的报文，因此，不同“层”各簇内非簇头节点的总能耗基本是一致的.不同“层”的能耗差异主要体现在簇头节点，簇头节点的能耗决定了簇头被替换的速率.因此，备用节点在不同“层”各簇中心区域的撒布密度应当以不同“层”之间簇头的能耗比为依据.撒布在不同“层”各簇中心区域的备用节点的密度比为：

ρlevel=m:ρlevel=m-1:…:ρlevel=1=Ech1+(m-1)Ech-ch1：Ech2+(m-2)Ech-ch2:…Ech2

(10)

当然，我们也不能将所有备用节点都撒布在中心区域为簇头节点作备份，如果当中心区域仍然有若干备用节点未被激活，而非中心区域的非簇头节点却已经开始死亡，我们是不能收集到整个检测区域的完整而有效的信息的.于是，我们根据一“轮”内单个非簇头节点和簇头节点的能耗比决定在每个非簇头节点周围撒布备用节点的密度.以第一“层”为例：

ρnon-CH:ρlevel=1=Enon-CH:Ech2

(11)

根据(11)式，我们不难知道如何在非中心区域的那些非簇头节点周围撒布备用节点.

2.3确立簇头及簇头多跳路径阶段

2.3.1 确立簇头

由于第一“轮”和其他“轮”在确立簇头的方式上有所差别，所以需要分开介绍.为方便说明，我们假设簇头节点个数为k.Enhanced-GLIDND算法首轮确立簇头的方式与GLIDND算法一致.

首轮：

步骤1:因为在首“轮”，所有节点能量都相等，都具有簇头竞选资格.于是，所有节点将自身基本信息(ID，Cluster ID，能量，坐标，status)广播出去，互通基本信息并宣布自己具有簇头竞争资格，备用节点进入休眠状态.

步骤2: 依据簇内能耗最小原则，BS根据每个网格(簇)内具有竞争簇头资格的非备用节点发出的信息分别计算出各竞争节点到簇内其他节点的距离平方和S2.

步骤3：BS在每个网格(簇)内选出S2最小的节点，将这些节点的k个节点的基本信息(ID ，Cluster ID，能量，坐标, status)在一个数据包里广播出去.传感器节点将接收到的广播包中的ID逐一与自己比较，若有一个与自己的ID相同，则将status设置为cl_head，并根据其他k-1个簇头的基本信息更新邻居簇头节点列表.无一相同则将status设置为cl_nonhead.

步骤 4：这一步是成簇最后的关键一步.本算法采用同LEACH算法一样的TDMA机制，簇头节点给每个簇内节点分配一个时间片，节点会按照时间片的先后顺序来发送数据给簇头.

Enhanced-GLIDND算法在第二“轮”之后的簇头确立方式是一个对GLIDND算法的主要改进点.

第二“轮”后：

步骤1: 对于任意一个簇，当簇头节点的剩余能量大于阈值0.2E0时，不需要更换簇头.否则，发送一个消息通知距离其最近且剩余能量最多的邻居节点(备用节点或簇内节点)，这个节点成为新的簇头，将status置为cl_head并将自身基本信息(ID，Cluster ID，能量，坐标，status)广播出去.

步骤2: 收到此广播包的邻居簇头节点据此更新路由表.

步骤 3：簇头节点给每个簇内节点分配一个时间片，节点会按照时间片的先后顺序来发送数据给簇头.当某个非簇头节点的能量小于0.01E0时，它向最近的status为backup的节点发送一个激活消息，收到激活消息的备用节点将status置为cl_nonhead.并向邻居节点广播自身信息.

该方案确立簇头的方式省去了GLIDND算法更换簇头节点时，与BS通信产生的大量报文.本质上也选取了地理位置最优且剩余能量最多的节点作为簇头，极大地提高了能量有效性.

2.3.2 簇头多跳路径阶段

Enhanced-GLIDND算法中，簇头多跳路径也是对GLIDND算法簇头路由的一个重要改进.在GLIDND算法中，剩余能量都初始化为E0，链路信息素浓度都初始化为τij(0)(τij(0)为常数).

下面的公式表示形成的或更新的簇头与簇头间的信息素浓度：

τij←(1-ρ)τij+a*energeα+lβ

(12)

式中ρ表示信息素的挥发程度，a，α表示节点剩余能量在信息素中所占的比重，l是簇头间距，β表示节点间距离在信息素中所占的比重.从该公式我们可以发现，从整个数据传输过程来看，路径的选择不仅考虑历史经验，算法提供的新的启发信息也在发挥作用.和蚁群算法一样，路径上的信息素会随着时间的推移有一定量的挥发.所以上面的公式是由两部分组成的.第一部分是实现一段时间内的信息素的挥发，初始时信息素浓度为0，则挥发量也为0.第二部分是启发信息，主要是根据与邻居簇头的距离以及邻居簇头的剩余能量来计算簇头间的信息素浓度，信息素越大，被选择作为下一跳的概率越大.因此，在选择下一跳时，不仅要考虑是否是最短距离发送，还要折中考虑簇头节点的能量.式中的参数，也和蚁群算法一样，一般是通过实验获得，而无严格的数学理论支持.

然而，当前簇头节点的剩余能量并未反应出此簇头节点所在簇的真实负载，剩余能量多的簇头节点所在簇的能耗速率很可能大于剩余能量少的簇头节点所在簇的能耗速率.蚁群算法选路的目的是为了实现网络的横向负载均衡，因此，当前簇头节点的剩余能量并不适合作为蚁群算法的影响因子来实现横向负载均衡.Enhanced-GLIDND算法以下一跳可选簇头节点所在簇的累计能耗作为蚁群算法的影响因子，真实反映了各簇的负载.

(13)

式中a，α表示累计能耗在信息素中所占的比重，energe表示该簇头节点所在簇的累计能耗,其他各变量含义与式(12)一致.

当某个簇头要发送数据时，根据路由表中相邻簇头的信息素浓度，计算出各个相邻簇头被选择的概率.下面的公式表示簇头到相邻簇头概率：

(14)

式中，N表示下一跳的可选区域.

3 仿真试验

3.1仿真环境

LEACH算法是一种经典的层次型无线传感器网络路由协议，目前许多层次型的路由协议都是在LEACH的基础上提出的，例如BCDCP算法.本论文研究Enhanced-GLIDND算法的性能，我们采用与文献[9]中LEACH算法相类似的仿真条件将Enhanced-GLIDND算法与GLIDND，LEACH,BCDCP，EEF(Energy Efficient Routing Algorithm)[10]算法进行了仿真和对比分析.

仿真条件：对于Enhanced-GLIDND算法，在100*100的正方形区域内随机均匀撒布100个节点，备用节点的数目若干，在这里我们取备用节点总数为100.根据表2中的仿真参数和式(8),(9)确定最优簇的个数为m = 2;于是，最优簇个数为4.再根据仿真参数和式(10)(11):ρlevel=2:ρlevel=1:ρnon-CH=28.56∶22.4∶1,ρnon-CH取距离中心簇头最远的簇内节点计算.我们发现，当处于level=2的簇的中心簇头节点已经被消耗将近29个，level=1的簇的中心簇头节点被消耗将近23个时，距离中心最远的非簇头节点才刚刚开始死亡，其他距离中心更近的节点当然具备更多能量.于是，我们在level=2的簇中心位置撒布28个节点，level=1的簇中心位置撒布22个节点.BS节点，位于(50，175).每个无线传感器节点的初始能量为0.5J，能量阈值为0.005J.对于LEACH，BCDCP及EEF算法，我们在正方形区域内随机均匀的撒布100个节点，100个备用节点.EEF算法随机选举10个节点作为簇头节点.GLIDND算法按照论文[5]的方法在不同“层”均匀撒布不同密度的备用节点.仿真参数如表2所示：

表2 仿真参数设置

3.2结果分析

3.2.1 平均能量消耗

图4 每“轮”(round)平均能量消耗比较

从图4中我们可以看到，LEACH算法在1800“轮”左右耗尽网络能量，BCDCP算法的平均能耗较LEACH有所减小，在2000“轮”左右才耗尽能量.GLIDND算法的平均能耗较BCDCP算法又有所减少，在2000“轮”左右时仍然有少许剩余.EEF算法在2000“轮”时，节点平均剩余能量大约为0.116J(23%).而Enhanced-GLIDND算法在平均能耗方面明显优于其他四种算法，在2000“轮”时节点平均能量剩余0.18J(36%).

这表明BCDCP算法较LEACH而言，簇头以多跳向BS传递数据的方式减小了能耗，在一定程度上延长了网络生命周期.GLIDND算法相对于LEACH和BCDCP而言，以固定成簇的方式避免了每“轮”成簇时大量广播包的能量开销.簇间路由方面，以BS为根节点构造路由树的方式，使得簇头向BS传递数据的最后一跳总是在距离BS最近区域的簇头，这种方式又比BCDCP算法更加节能.

EEF算法固定簇头的方式，相对于LEACH，BCDCP而言，省去了每“轮”成簇的广播包开销，相对于GLIDND，省去了更换簇头时选举簇头的开销.根据可选下一跳簇头的剩余能量、簇头间距，可选前驱和后继数目四个参数来决定簇间路由的方式，也远比LEACH和BCDCP节能.

Enhanced-GLIDND算法以消息激活的机制更换新簇头,省去了GLIDND算法需要更换簇头时的广播开销. 簇间路由以各簇的累计能耗作为蚁群算法的影响因子,更加真实地反映了网络的负载.改进的蚁群算法也更好地均衡了横向负载，避免了GLIDND算法中蚁群算法因为选取下一跳簇头节点剩余能量作为影响因子而对网络横向负载做出的误判和因此产生的能量浪费.撒布的备用节点主要集中在中心区域,这种尽可能让中心区域节点成为簇头的方式,极大地减小了网络平均能耗，也避免了EEF算法因为部分节点不在簇头节点的无线传输范围内，借用接力节点传输数据而造成的能量损耗.

3.2.2 存活节点个数

从图5中我们可以看到，LEACH在进行到第1200“轮”左右时，几乎已无节点存活，而BCDCP算法依然有5个左右的节点，这就说明相对于LEACH，BCDCP算法在一定程度上延长了整个网络生命周期.这主要是因为BCDCP算法在簇头选举阶段就通过选举节点能量足够大的节点作为簇头，从而使得低能量节点能够延长它们的生命周期.此外，在簇间路由方面，根据MST(Minimum Spanning Tree)算法采用多跳的方式向BS发送数据，避免了单一簇头节点因能耗过大而过早死亡.GLIDND算法在1200“轮”左右时，仍然有60个左右的节点.这是因为GLIDND算法采用基于地理位置固定划分簇的方式减少了每“轮”成簇的开销，在簇头选举的方式上继承了BCDCP算法的簇内能耗最小的思想，将节点剩余能量和地理位置信息都考虑在内.在簇间路由方面，以BS为根节点构造由簇头向BS发送数据的路由树，减小了整个网络的总能耗，对于由此而产生的“热区”问题，提出了一种根据每一“轮”能耗的大小，在不同区域撒布不同数目备用节点的思想，极大地将能耗纵向平均化，延长了网络生命周期.并且利用一种改进的蚁群算法，将簇头节点的剩余能量加入信息素浓度的计算中，这样，选择下一跳节点时，通过一定概率选择能量较大的节点，从而避免了单一节点因能量消耗过大而过早死亡.EEF算法在1200“轮”左右，有70个存活节点.在2000“轮”时仍然有40个节点.这说明EEF算法固定簇头的方式较 GLIDND算法减少了更新簇头时的广播能耗，略微延长了节点寿命.

Enhanced-GLIDND算法在1200“轮”左右时,仍然有124个节点,在2000“轮”时仍然有50个节点,节点死亡速率也比较稳定.这是因为相对于EEF，GLIDND算法,以消息通知的机制更换新簇头, 将大部分备用节点撒布在各簇中心区域从而使簇头长期保持在簇中心的方式,极大地节省了各节点能耗,延长了各节点的寿命.

图5 每“轮”(round)存活节点个数比较

3.2.3 能量有效性

无线传感器网络的能量有效性是指该网络在一定的能量条件下感知到的信息量.能量有效性是无线传感器网络的重要性能指标.到目前为止，无线传感器网络的能量有效性还没有被模型化和量化，还不具有被普遍接受的标准，需要深入研究.一般是以单位能耗内BS收到数据包的多少作为评价能量有效性的指标.定义：效率=BS收到数据包的个数/总能量消耗.我们的实验中，对于不同算法，因为分簇数目以及簇间路由方式的不同，BS节点在一“轮”内收到的数据包的个数也不相同.然而，不论一“轮”内收到多少数据包，都是对整个区域的一次信息收集，获得的信息量是相同的.于是，对于四种算法，我们都认为一“轮”内BS节点收到的数据包是1.

图6 一定能耗下BS收到的数据包

在图6中，我们发现，在全网能量耗尽时，LEACH算法中，BS收到了1800个左右的数据包.BCDCP算法中，BS收到2000个左右的数据包，将效率提高了11%.GLIDND算法中，BS收到2200个左右的数据包，又将BCDCP算法的效率提高了10%.EEF算法中，BS收到2500个左右的数据包，略微提高了GLIDND算法的效率.Enhanced-GLIDND算法中，BS最后收到2700个左右的数据包，在能量有效性上明显优于其他算法.

Enhanced-GLIDND算法的另一个巨大优势：因为有大量备用节点集中在中心区域，在前1600“轮”左右，中心区域的簇头节点即使因为能量耗尽而死亡也有足够的备用节点，非中心区域的簇内节点也基本没有因为能量耗尽而死亡.所以，Enhanced-GLIDND算法中，BS在前1600“轮”左右收集到的是覆盖范围最全的信息.GLIDND算法备用节点在每“层”内均匀分布，LEACH，BCDCP，EEF算法备用节点在整个区域均匀分布，于是，在200-400“轮”有多个节点死亡后，这几种算法中，BS收集到的数据包所包含的信息往往都不能覆盖整个区域.

4 结论

本文针对不同密度备用节点算法(GLIDND)的局限性，提出了一种改进的GLIDND算法Enhanced-GLIDND.仿真证明，与各经典算法相比，新算法有效地减小了网络平均能耗，延长了网络生命周期，并提高了能量有效性.

[1]Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine,2002,(8),102-114.

[2]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[A]. Proceedings of the Hawaii International Conference on System Sciences[C]. San Francisco: IEEE Computer Society, 2000: 3005-3014.

[3]Muruganathan S D, Ma D C F, Bhasin R I, et al. A centralized energy-efficient routing protocol for wireless sensor networks[J]. IEEE Radio Communication,2005,(3): S8-13.

[4]Shen H. Finding the k most vital edges with respect to minimum spanning tree[A]. Proceedings of the IEEE National Aerospace and Electronics Conference[C]. 1997,(5):255-262.

[5]肖达. 一种基于地理位置的无线传感器网络路由节能算法研究[D]. 厦门：厦门大学硕士学位论文,2009.

[6]Xu Y, Heide J, Estrin D. Geography-informed energy conservation for ad hoc routing[A]. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking[C]. Rome, Italy: ACM, 2001:70-84.

[7]杨波. 基于蚁群算法的无线传感器网络路由算法研究[D]. 西安：西安电子科技大学硕士学位论文,2008.

[8]李成法,陈贵海,叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,(1):27-36.

[9]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展[J].软件学报,2003,(10):1717-1727.

[10]Kumar S, Kuila P, Jana P. Energy efficient routing algorithm for wireless sensor networks: A distributed approach[A].Proceedings of the International Conference on Communication and Computing Systems[C].2016:207-213.

AWirelessSensorNetworksRoutingProtocolBasedonGeographicalLocation

XIAO Da1, XIAO Mingbo2

(1. Hangzhou Technical Center, Nokia Solutions and Networks System Technology (Beijing) Co., Ltd, Hangzhou Zhejiang 310052, China; 2. College of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China)

In order to overcome the deficiencies of Different Nodes Density based on Geographical Location Information (GLIDND) algorithm in energy efficiency, this paper proposed an innovative Wireless Sensor Network (WSN) routing protocol Enhanced-GLIDND, which improves GLIDND in three aspects: (1) Sowing different density backup nodes at different location according to the energy consumption rate; (2) Choosing a new cluster head node by message notification scheme; (3)Selecting the next hop for a cluster head node by taking the accumulated energy consumption of the cluster in which the next hop cluster head is located as an influence factor. Simulation experiments evaluated Enhanced-GLIDND against EEF, GLIDND, LEACH and BCDCP, and the result shows that Enhanced-GLIDND outperforms any other algorithm in terms of the energy efficiency and the lifecycle of the whole network.

wireless sensor networks; different nodes density; cluster; lifecycle of network

TP393

A

1008-4681(2017)05-0024-09

2017-07-05

国家自然科学基金(批准号：30900328)资助项目；杭州电子科技大学启动基金(批准号：KYS085612006)资助项目.

肖达(1983— )，男，江西上饶人，诺基亚通信系统技术(北京)有限公司杭州研发中心工程师，硕士.研究方向：物联网、车辆自组织网络、无线传感器网络.肖明波(1971— )，男，湖南沅江人，杭州电子科技大学通信工程学院教授，博士.研究方向：无线网络资源管理与优化、无线网络跨层设计、QOS技术等.

(责任编校：晴川)