LEA CH路由协议的改进

吴丽君黄河清

(华东理工大学信息与工程学院，上海200237)

1.引言

无线传感器网络(WSN，Wireless Sensor Network)是微机电系统(MEMS)、片上系统(SOC)、计算机技术、网络技术、嵌入式系统、通信技术、微机电技术、分布式信息处理技术和传感器技术等多种领域技术于一体的新型获取和处理信息的传感网络，并随着这些技术的飞速发展和日益成熟，出现了更小、更廉价、更低能量、更灵活的嵌入式系统的并具有感知能力、计算能力、无线通信能力和控制功能的无线传感器网络[1]。

无线传感器网络在军用和民用方面具有极高的使用价值，可以在大范围内用于收集、处理、监测和发布极其复杂的环境数据，但在现实使用过程中存在着一些不可避免的约束。无线传感器网络在实际应用中传感器节点需要量大，要求单价便宜，所以一般体积微小，通常携带的能量十分有限的电池。而且无线传感器网络节点往往被部署在偏远地区或环境恶劣的危险区域。因此，如何在不影响功能的前提下，尽可能地延长网络的生命时间成为无线传感器网络软硬件设计的核心问题，也是当前国内外研究机构关注的焦点问题[2]。

目前，基于节能的策略的考虑已经出现各种各样的协议。按照网络的拓扑结构，可以分为平面路由协议和分层路由协议。在分层路由协议中，群首选择的合理性很大程度上决定网络的功耗，网络的生命周期的长短。目前分层路由协议中的群首选择算法主要集中式和分布式两种基本算法。集中式群首选择算法要求基站获得传感器网络全局信息，然后由基站选取群首，再广播当选群首的节点ID。分布式群首选择算法则是由每个节点独立运行群首选择算法，然后自行决定自己是否当选为群首。无线传感器网络中基于分层的典型层次型路由算法有：LEACH[3]、HEED[4]、TEEN[5]等。TEEN和LEACH的实现机理非常相似，只是前者是响应型的，而后者是主动型。主动型传感器网络会持续不间断地监测周围的物质现象，并以恒定速率发送监测数据；而响应型传感器网络只是在被观测变量发生突变时才进行数据传送。

LEACH协议是第一个针对无线传感器网络特点提出的分布式层次路由协议，其后一些分层协议大多是在其基础一种延伸，所以本文选择经典的研究对象LEACH协议，提出一种融合的节点密度控制群首选择算法，该算法是对LEACH算法的改进，在选取群首的时候，除了考虑节点轮流成为群首的问题，考虑节点的剩余能量，同时考虑节点的密度，使得分布密度越大、剩余能量越高的节点较其它节点成为群首的可能性更高。NS2仿真实验表明，新算法能比LEACH算法更有效地降低网络的能量消耗，均衡网络能耗水平，从而可进一步提高传感器网络的生命周期。

2.LEACH协议

2.1 协议的基本原理

在LEACH中，各个节点自组织成为群，每个群内有一个群首。所有非群首节点将自己的数据发送给群首；群首节点接受所有分群节点发送来的数据，然后对数据进行处理，最后将数据发送给远端的基站，由分析可知群首消耗的能量多于非群首节点。假如群首节点固定然后一直不变，那么群首节点将很快消耗掉自己的能量。群首节点一旦把自己的能量消耗掉，就停止工作，那么其群内所有节点也会和整个网络失去通信。因此LEACH采用群首位置随机轮换机制，让各个节点轮流的成为群首，这样避免网络中因群首能量消耗过快而死亡。

在初始化阶段，群首是通过下面的机制产生的。传感器节点生成0，1之间的随机数，如果大于阈值T，则选该节点为群首。T的计算方法如下：

N为网络中节点总数，k为群首的数量，Gi(t)为i节点时刻在近几个轮中(r⊕(N/k))作为群首的标志函数，由分析可知只有满足节点最近不是群首，其能量多于最近刚刚担任过群首的节点。由于经过N/k个循环后，所有节点都有一次机会成为群首，在随后的循环中全部符合群首的条件。

2.2 LEACH优缺点分析

由LEACH协议的运行过程可以知道，群首自适应地随机选取，每个节点机会相等，在不同的轮中，由不同的节点去充当群首，把网络的负载基本均匀地分布在整个网络中，把远距离通信的负荷基本均衡分配给网络中的节点，有利于均衡节点的能量消耗，且不需要上层控制或一些全网信息，实现起来也比较容易。但是群首选择是随机的，节点担任群首是严格等概率的，群首的选择不考虑节点的剩余能量，由于群首要收集并融合群内信息并直接与基站通信，所以一旦出现能量较低的节点为群首，其能量很快耗尽，这样不利于均衡网络能量，缩短了网络的生命周期。网络中的节点自组织形成群，节点选择与之通信能耗最小的群首而加入这个群，而不考虑群的负载程度，这样很可能出现一些不均衡的分群方案，将会导致各个群中的节点数量严重不均衡，由分析可知群首选择算法存在不利延长网络生命周期的因素，在下章本文提出改进的群首选择算法。

3.加权群首选择算法

3.1 网络模型假设

(1)①节点在需要之时具有足够的功率将数据发送给基站；②节点可以根据需要改变发射功率的大小；③节点总有数据发送给用户且相互接近的节点具有相关数据；④节点一旦布置好就不能移动；⑤基站为位置远离传感器收集数据区域，假设其能量充足，不考虑其能量的消耗；⑥每个节点可以感知其剩余能量，邻居节点信息；⑦所有节点的初始能量相同而其有限；⑧无线电信号在各个方向上能量消耗相同；由于无线硬件技术和低功耗的计算技术的发展和进步，这些假设是合理的。

(2)传输模型：节点将l bit的数据传输距离d耗能为：

接受一条消息的耗能为：

数据融合消耗能量：

其中，ETx(l，d)表示发送端的能量消耗；ERx(l)表示接收端的能量消耗；Eelec表示发射电路消耗的能量；εfs和εmp放大器的系数；d0临界距离。

3.2 节点密度调节函数

由前文分析可知为了使是每个群的负载基本平衡，延长网络的生命周期，在选择群首时，要尽可能使得密集分布区域中的节点应比稀疏分布区域中的节点具有更大当选为群首的概率，使得密集分布区域比稀疏分布区域具有更多群首，使得每个群中成员节点数目大致相同。因此，本节将在LEACH算法的式(3)中引入一个密度调节函数H(i)，通过密度调节函数H(i)可以使得分布密度越大的节点有更多机会成为群首。其中：密度调节函数的定义采取文献[6]的定义方式：

其中Nodedensity(i)表示节点的邻居节点个数。显然可知Nodedensity(i)越大，H(i)就越接近1，这样节点i成为群首的概率就越大。

节点的邻居节点个数为文献[7]定义方式：

R为节点i的通讯半径。节点可通过改变发射功率来控制其通信半径，进而改变其邻居节点个数。N为网络中现有节点数量。

3.3 剩余能量调节函数

由于在LEACH中，阈值Ti(t)的选取未考虑群首的概率与它的剩余能量之间的关系，这使得选出的群首可能剩余能量很小，这样很快死亡，从而它所管理的整个群在很长一段时间内都处于失效状态。尽管节点轮流当选为群首，但它并不没有很好把网络的全部能量平均到每个节点上，因此引入剩余能量调节函数如下：

Ei_curent为节点i的当前能量，Eaveraget为节点当前具备的平均能量，由公式可知节点的剩余能量越大，Z(i)越大，成为群首的概率越大。Eaveraget=Ecurrent_totalt/Network_adlive，Network_adlive表示实时的网络存活节点总数，Ecurrent_totalt为网络当前的全部能量。

3.4 加权群首选择算法

本文是在选择群首算法上不仅考虑节点剩余能量，也要考虑节点分布密度，希望节点的剩余能量多，节点分布越密集的节点有更大的概率成为群首，但在两个因素的权衡中，往往会出现矛盾的一面，所以引入权重因子w且，得Ti(t)改进为：

w的具体取值，根据多次实验结果决定取得最佳效果的值。

3.5 仿真实验和结果分析

在仿真实验中，采用100个节点的网络，节点随机分布在(x=0，y=0)和(x=100，y=100)之间，基站位于(x=50，y=175)。信道带宽设为1Mb/s，每条消息的长度为500B，各种分组分组头均长为25B。计算R=37.5，Eelec=50nJ/bit，εmp=0.0013pJ/bit/m2，εfs=10pJ/bit/m4，Einital=2J，Efuse=5nJ/bit/signal，d0=87.5，选择w(1，0，0.5，0.2，0.8)进行比较实验，仿真时间为700s。

由节点存活仿真结果图1可以知道没有改进的LEACH的生命时间为460s左右。改进后LEACH生命时间对应w(1；0；0.5；0.2；0.8)为600s，570s，490s，530s，620s。网络的生命时间有所延长。其中当w=0时，就是只用H(i)密度调整函数有效时，生命时间延长了18.75%。w=1延长了30.43%。有公式(7)可以知道，在选择群首时，节点的剩余能量要比节点分布情况占更大的比重，果然当w=0.8时权衡了节点的剩余能量和节点的分布能量，这时网络的生命时间延长了37%左右。说明本改进方案不仅理论是可行的，仿真也证明了是有效的，可以延长网络的生命时间。由仿真结果图2基站节点接收数据包数可知改进后的协议不影响数据的传输量，反而提供数据的吞吐量。节点消耗总能量结果图3可知改进后的协议单位时间消化的能量少于改进前。说明了改进后的LEACH协议性能得到了改善。

[1]Zhang Xihuang，Xu Wenbo.A New FlowBased Fast Handover Method for Mobile IPv6network with route optirIlization[J].Computer Comunication.2007，(12)

[2]汪益民，吴建国.浅析无线传感器网络节能策略[J].电脑知识与术.2008，4(4)：867-868.

[3]Heinzelman W，Chandrakasan A，Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].Wireless Communications.2002，4(1)：660-670

[4]Younis O，Fahmy S.Distributed clustering in adhoc sensor networks a hybrid，energy-efficient approach[C].The 23th Joint Conf on IEEE Computer and Communications Societies[J].2002，629-640

[5]Manjeshwar A.Agrawal D T.A routing protocol for enhanced efficiency in wireless sensor networks[C].The 15th International Parallel and Distributed Processing Symposium.2001，2009-2015

[6]贺智勇，龙陈锋，尹乾.传感器网络中基于节点密度的分布式成簇算法[J].计算机应用与件，2008，25(12)：20-21.

[7]乔俊峰，刘三阳，曹祥宇.无线传感器网络中基于节点密度的簇算法[J].计算机科学，2009，36(12)：46-49.