无线网络中DEEC协议的改进

黄晓峰，刘广钟

(上海海事大学 信息工程学院，上海201306)

当今社会，无线传感器网络已经出现在社会的各种角落，智慧城市的提出更是为无线传感器网络提供了更大的发展空间。无线传感器网络WSN(Wireless Sensor Network)是由大量的传感器节点组成的一种网络，无需固定基础设施的支持，具有快速展开、抗毁性强、自组织、动态拓扑和能量受限等特点[1]。由于节点能量有限并且对其充电非常困难，因此设计路由算法时应该着重于延长网络的生存周期、提高网络的有效性，避免网络断裂，保证负载均衡。目前对于无线网络路由算法的研究发现，基于分簇的层次路由有很强的扩展性，多跳传输的路由方式可以均衡节点的能量的负载[2-3]。

针对这些协议的不足，本文提出了一种负载均衡的无线传感器网络路由改进算法IDEEC。通过在簇头选择阶段，综合考虑节点的剩余能量以及节点周围的密度，保证簇的均匀分布。

1 相关研究

1.1 Leach算法的分析

Leach算法的基本思想是减少节点与基站的直接通信，并通过数据融合降低通信能量的损耗。Leach算法是周期性执行的，分为分簇阶段和稳定阶段。在分簇阶段，节点会产生一个 0与 1之间的随机数，并与 T(n)进行比较，如果该随机数小于T(n)，则广播为簇头。非簇头节点收到广播后，选择最近的节点加入，当簇头节点收到加入数据包后，再将该表广播发给簇内成员节点。没有加入任何簇的节点直接与基站通信。在稳定阶段，簇内成员节点将采集的数据传送给簇头节点，簇头节点进行数据融合后发送给基站。当稳定阶段完成了第一轮的数据传输后，重新进入到分簇阶段。Leach算法延长了整个网络的生存周期。

1.2 DEEC算法分析

DEEC算法[4]是针对Leach算法的改进，考虑了节点的初始和剩余能量，增加了网络的生存周期。考虑到网络的异构性，数据传输节点的能量不可能都相同，因此每个节点成为簇头的概率就不同。节点成为簇头的概率pi与改进的阈值 T（n）的关系如下：

其中，si为节点，i∈[1，n]。

[5]对DEEC分簇算法进行改进。由于在数据传输阶段，簇头节点间没有考虑传输跳数，因此可能会造成大的传输延迟。但是跳数缩小时，多跳传输中选择下一簇头时没有考虑到剩余能量，同时一旦能量的消耗过大，节点就不足以继续多跳传输。

1.3 网络模型

本路由算法中的无线传感器网络为n个节点随机分布在M×M区域内。节点集合表示为S={s1，…，sn}，同时网络有以下特点：

(1)本网络拓扑结构为静态的，节点和基站节点的位置都不会随时间改变。

(2)传感器节点的初始能量相同，每个节点具有唯一的ID号。

(3)传感器节点可以自己调节无线的发送功率。

1.4 IDEEC算法中的相关参数

在无线传感器网络中，主要根据网络的生存时间和负载平衡程度来判定分簇路由算法的好坏。在分簇路由算法中，每轮中簇的覆盖节点的平均程度会影响网络的生存周期。

1.5 能量消耗模型

本文中统一采用与Leach算法相同的无线通信能量消耗模型，能量消耗公式是一阶无线电模型[6]。节点发送l bit数据所消耗的能量由发射损耗和功率放大损耗两部分组成：

2 改进的路由协议

综合以上协议的不足，提出了一种高效的分簇路由算法，通过引入能量阈值和簇头的通信范围，防止簇内成员被选成簇头节点。

本路由算法采用与Leach算法相同的机制，每个周期依然分为分簇阶段和稳定阶段。在分簇阶段，普通成员节点首先计算出成为簇头的概率pi，然后随机产生[0，1]之间的随机数，并与门限阈值T(si)进行比较，如果大于门限阈值则成为候选簇头。计算节点的剩余能量并与能量阈值Ethr比较，其中能量阈值为：

式中Einitial为节点的初始能量。当候选簇头的剩余能量大于Ethr，才能成为簇头。通过引入能量阈值，可以防止较低能量的节点成为簇头，造成网络中数据的丢失和重新选举簇头的开销。为了使簇分布更加均匀，引入了覆盖半径Rc。Rc代表了整个网络每个簇的覆盖距离，计算公式为：

成为簇头的节点广播消息，当节点收到该消息后计算与该簇头的距离，如果小于通信半径r，则改变节点的类型为簇的候选成员节点，以防止簇内的节点进行簇头选举，保证簇能够尽量覆盖所有的网络。当簇头选择完成后，进行簇的形成，簇头节点广播数据包，该数据包包括簇头的ID和簇头的能量，非簇头节点收到数据包后选择就近的簇头加入，没有加入到簇的节点则直接与基站通信。

完成分簇后，进入到数据信息传输阶段，本算法中将采用两种方法来进行传递。当簇头节点的平均能量较大时，采用最小路由数传递数据，保证节点在最小时延下到达sink节点。但同时能量消耗的也较快，会导致网络的生存周期较短，所以当节点能量达到门限值后，将采用最短距离来进行簇头间的下一跳路由的选择，这样将能延长整个网络的生存周期。

在最小路由[7]传递数据时，定义一个距离 β，其值与d0相同，簇头节点按照同样的功率传递广播数据包，数据包中包含节点的ID号、剩余能量以及离基站的距离。其他簇头节点收到数据包后，比较与自己之间的距离，当节点离基站距离小于β时，则选作下一跳，这样保证了节点能够直接地传输数据到基站，减小了传送时延，但这种方式也加快了节点能量的消耗，为了使负载平衡，引入能量门限值 E1，当节点能量低于E1时，进行最短路径传输，节点通过选择离自己最近的簇头进行数据传输。这样既保证了传输时延短，同时也能使网络的生存周期加长。其中E1为簇头的平均能量大小。

3 仿真结果

对本文提出的协议进行性能测试，同时选择了Leach算法和DEEC算法进行仿真结果的比较。假定无线传感器网络是随机布置在一个二维的平面区域，节点的位置部署是随机选择的，基站位于节点正上方。三种算法的效率如图1所示。

图1中，整个网络的生存周期明显增长，第一个死亡节点出现的时间较晚。把第一死亡节点出现的时间作为网络性能的检验条件，生存周期的性能相对于Leach和DEEC协议分别提高了大约50%和30%，这是因为Leach和DEEC算法中由于随机选择簇头节点，节点的分布不均匀，造成第一个死亡节点先出现，其中虽然DEEC考虑到了剩余能量的选择，但是对于簇的分布没有进行考虑。

比较图1中的数据传输效率，可以看出IDEEC算法的数据传输效率大大高于另外两种算法。

如果从整个网络的死亡节点出现的时间分析，则生存周期的性能相对于Leach和DEEC路由算法分别提高了大约30%和25%，由此可见整个网络的生存周期得到了很大的提升。同时从图1(b)中的传输效率可以看出改进的路由算法的数据传输量很大，很大程度上提高了网络的传输效率。

图2显示了路由算法每轮形成的簇的数目，在前1 500轮时，形成的簇的数目较大，这是因为在1 500轮已经产生了第一死亡节点，网络的簇的数目受到了影响，从图中的趋势可以看出，改进的DEEC协议产生的簇的数目较以前稳定，这是由于引入均匀分簇的原因，所以整个簇的数目较稳定，不会受到巨大的波动。

在无线传感器网络的分簇协议中，簇的形成以及数据传输的选择方式直接影响着无线传感器网络的性能。正是基于以上问题，本文中的路由算法对现有的算法进行了改进，引入均匀分簇和传输负载均衡。根据仿真结果，本算法综合考虑了网络分布均匀及节点传输阶段传输时延的问题，提高了网络路由算法的生存周期。

参考文献

[1]孙利民.无线传感器网络[M].北京：清华大学出版社，2005.

[2]AKKAYA K，YOUNIS M.A survey on routing protocols for wireless sensor networks[J].AdHoc Networks，2005，3(5)：325-349.

[3]郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].北京：人民邮电出版社，2005.

[4]QING L，ZHU Q X，WANG M W.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Computer Communications，2006，17(3)：481-489.

[5]Liu Feng，Zhang Dengyi.Clustering routing protocol based on local optimization for wireless sensor networks consumer electronics[C].Dalian：2012 2nd International Conference，2012.

[6]刘玉华，赵永锋，许凯华，等.无线传感器网络 LEACH协议的改进[J].计算机工程与应用，2010，46(17)：117-120.

[7]杨云，李斌，高峰，等.无线传感器网络簇内优化的最小跳数路由算法[J].计算机应用与软件，2010，27(2)：31-33，46.