基于LEACH协议的改进路由算法*

柳 平,陈 欢,石中华,吕金风

(汕头大学电子工程系,广东汕头 515063)

随着传感技术、嵌入式技术以及低功耗无线通信技术的发展,生产具备感应、无线通信以及信息处理能力的微型无线传感器已成为可能.这些传感器节点之间通过相互协作,将其监测和感应的多种环境信息(如温度和湿度等)传送到基站进行处理,无线传感器网络广泛应用在国防军事、救急和环境监测等领域[1-2].与无线移动自组网不同,无线传感器网络一般具有较大的节点密度且没有IP地址,同时由于受到成本和体积等原因限制,无线传感器节点的处理能力低并且无线带宽以及电池容量等资源匮乏.在大多数应用中,传感器节点被部署后就无法对其充电,这使得如何提高网络生存时间成为无线传感器网络研究主要方向之一.

1 LEACH协议

LEACH[3](Low Energy Adaptive Clustering Hierarchy)是一种分层路由协议,它的基本思想是网络周期地选择簇头节点,将整个网络的负载平均分配到每个节点,普通节点按照就近原则加入到相应的簇头.簇内节点将感知数据发送到簇头,簇头节点收集所有簇内节点发送来的数据并进行处理,最后簇头将处理后数据直接传送到基站.

LEACH协议每个周期(轮)由初始化和稳定工作两个阶段组成.在初始化阶段时,网络随机选择节点作为簇头,成为簇头的节点向网络广播其成为簇头消息,普通节点接收到该消息后,根据就近原则判断应该选择哪个簇头,然后向该簇头发送加入消息.在稳定工作阶段,簇内节点把监测到数据发送到簇头,簇头对数据进行处理后直接发送到基站.本周期内任务完成后,马上进入下一个周期.

簇头选择是 LEACH协议关键,具体方法如下:每个传感器节点选择[0,1]之间的一个随机数,如果产生随机数值小于阈值T(n)[3],那么这个传感器节点就成为簇头.整个网络选出的期望簇头个数为

2 ECHT协议

图1 每轮时隙图Fig.1 Time slot at each round

LEACH协议及改进协议[4-5]采用周期地随机选择簇头,避免了簇头过度消耗能量,同时簇头利用数据融合技术减少了网络数据通信量.但由于簇头直接与基站通信,对于比较大的网络,将消耗较多能量,而且动态分簇有带来额外开销.针对以上问题,本文提出了一种基于时间均匀分簇混合路由协议(ECHT).

在网络建立阶段,基站需要用足够大的发送功率向全网络广播信息.网络中节点根据基站的发送功率计算出到基站的近似距离,利用此距离可以调节向基站发送数据所需的发送功率.ECHT协议包括分簇和数据传输两个阶段,分簇阶段又可以分为簇头选择和簇的形成两部分,数据传输阶段也分为簇内数据传输和簇头间数据传输.为了使簇内信息进行交流,该协议引入了簇内信息交流阶段.它们在每一轮中有对应时隙,如图1所示.

2.1 簇头选择

在无线传感器网络中,当每轮进行簇头选择时,首先传感器节点根据剩余能量计算出其广播成为簇头的CLUSTER-HEAD-MSG消息的时间,其表达式为

式中:T1为在每轮中簇头选择时间;Ei表示节点i剩余能量;Ea,Emin和Emax分别表示上一轮节点i所在簇内的平均剩余能量、最小剩余能量和最大剩余能量.ni∈(0,1)随机数,用于避让相同剩余能量节点广播消息引起的冲突.

在每轮簇头选择时,所有节点按照自身竞选时间来广播CLUSTER-HEAD-MSG消息.因此,剩余能量高的节点,先广播该消息,它的广播半径是为竞争半径,如式(3)所示.

其中A为监测区域的面积,k为期望簇头的个数.

当普通节点接收到CLUSTER-HEAD-MSG消息后,将不广播其消息并记录发送节点的信息.当簇头接收到CLUSTER-HEAD-MSG消息后,不做任何处理.经过时间T1后,网络中簇头全部选出.

2.2 簇的形成

簇头选择完成后,如果普通节点只接收到一个簇头发送来的CLUSTER-HEAD MSG 消息,就选择该簇头.如果接收到多个簇头发送来的CLUSTER-HEAD MSG 消息,就选择簇内通信代价最小亦即接收信号强度最大的簇头.当普通节点选择其簇头后,就发送加入JOIN-CLUSTER-MAG消息通知该簇头.簇头接收到该消息后,进行构建TDMA调度表并将它发送给簇内所有节点,确保簇内所有节点发送数据没有碰撞,同时可以让节点除了自身工作时间外进入休眠,节省节点能量.

2.3 数据传输

在簇头间传输数据之前,基站构建 TDMA调度表并发送给网络中每一个簇头,TDMA调度表规定远离基站的簇头先发送数据,靠近基站簇头后发送并转发数据,因此,这可以避免簇头多次转发其它簇头发来的数据.

首先簇头收集从簇内成员节点发送来数据,并进行数据融合,然后把数据发送给中继簇头或基站.中继簇头只是简单转发来自其它簇头的数据,而不能进行数据融合.

在簇头间传输数据开始时,每个簇头以相同的功率向全网络广播NODE-STATE MSG 消息,它包含簇头的ID、当前剩余能量和到基站的距离.如果簇头i收到由簇头j广播一条消息NODE-STATEMSG,计算出两者距离.ECHT协议定义簇头的中继簇头集合

采用无线通信能量消耗模型[3],发送数据能量消耗与距离的平方或4次方成比.簇头i从中继簇头集合选择簇头作为下一跳,如果选择离自己近的簇头作为下一跳,可以减少簇头i的能量消耗,但会使得靠近基站的簇头转发更多其它簇头发送来的数据,消耗更多能量.如果选择离自己较远簇头作为下一跳,可以减少靠近基站的簇头转发其它簇头发送来的数据量,但是会增加簇头i能量消耗.综上所述,本文定义了一个转发代价函数f(i,j),如式(5),表示簇头i把中继簇头集合的簇头j作为下一跳代价.

式中:Ei是簇头i的剩余能量;Ej是簇头j的剩余能量;w∈[0,1]是代价函数权值;Eij是簇头i发送L比特数据(它包括簇头i产生数据和转发其它簇头数据)到簇头j能量消耗;dij是簇头i与簇头j之间距离;EjBS是簇头j发送L+k比特数据(包括接收簇头i发送L比特数据和簇头j本身产生数据)到簇头基站(基站)能量消耗;是基站与簇头j之间距离;ER是簇头j接收簇头i发送L比特数据消耗能量.

当簇头j属于簇头i中继簇头集合,代价函数第一部分表示采取多跳通信代价,选择与自己距离最短的簇头作为下一跳,第二部分表示单跳通信代价,选择离基站最近簇头作为下一跳,通过调节w来权衡多跳和单跳通信,当w=1时,簇头i选择最近簇头作为下一跳.当w=0时,簇头i选择基站作为下一跳.总之,簇头i从中继簇头集合和基站中选择其转发代价函数最小的簇头作为下一跳.

在簇头间传输数据结束后,该协议进入簇内信息交流阶段,各簇内成员节点把自身剩余能量信息发送到簇头,簇头接收该信息并计算出簇内平均剩余能量Ea、最小剩余能量Emin和最大剩余能量Emax,然后向簇内广播一条CLUSTER ENERGY-MSG消息,它包含

3 仿真及结果分析

3.1 仿真模型和参数

在仿真环境中,400个无线传感器节点随机分布在200m×200m二维平面区域内,基站(基站)位于(100,250)的位置,图2所示为无线传感器节点在监测区域中的分布图.仿真时所使用参数设置见表1.

表1 仿真参数Tab.1 Simulation param eters

图2 无线传感器节点随机分布图Fig.2 Wirelesssensor node random distribu tion

图3 仿真流程图Fig.3 Simulation flow figure

3.2 实验仿真步骤

在实验过程中,通过上述的无线传感网络模型分别使用LEACH协议与ECHT协议进行仿真,大致的仿真流程如图3所示.

如图3所示,实验包含了主循环,该循环进行了包括了2.3数据传输中提到的簇集内数据传输开销、簇头间数据传输开销等的计算,计算开销的依据是传输不同数据包、不同传送距离是能量的消耗.一个节点由于产生能量消耗,当能量耗完时死亡,整个主循环通过判断是否全部节点死亡来确定继续与否.在循环中记录的信息包括第一个死亡的节点,最后一个死亡的节点,以及簇头的情况.依据上述的仿真流程,分别对两种协议 LEACH、ECHT进行仿真,记录结果并进行比对,从而获得协议算法的优劣.

3.3 实验结果分析

图4 各种协议生成簇头分布F ig.4 C luster head distribu tion for various protocol

簇头在网络中的分布将会很大程度影响网络性能,如果簇头在网络中分布均匀,网络覆盖率将提高,同时减少网络能量消耗.否则,网络覆盖率降低,网络能量消耗增加.从每种分簇协议的模拟过程中随机选取一轮,观察每种分簇协议产生簇头在网络中分布情况,如图4所示. LEACH协议生成簇头分布不均匀,而ECHT协议产生的簇头在网络中分布均匀,原因是LEACH协议采用随机数与阈值的机制产生簇头,没有考虑簇头之间的距离.ECHT协议通过网络节点竞争半径进行局部竞争,使得簇头分布均匀.

在网络拓扑固定情况下,一个稳定的分簇协议应该产生比较一致的簇头,优化网络的能量消耗.图5是每种分簇协议在整个网络周期中生成相同簇头数目的轮数对比,从图中可以看出,每种协议生成的簇头数目都有一个期望值,也是协议在此仿真环境下最优的簇头数目.ECHT协议产生的簇头数量稳定,LEACH产生簇头数量的波动范围最大,这是因为LEACH协议单纯采用随机概率与阈值的机制产生簇头,因此簇头数量变化比较明显.ECHT协议簇头数量变化比较集中,该协议采用了局部区域竞争的方法,有效地控制了协议所生成的簇头数量.总的来说,ECHT协议产生的簇头数量比较稳定,可靠性较好.

网络生命周期定义为网络中出现第一个节点死亡的时间[6],还可以定义为网络中大部分节点死亡的时间.网络节点死亡可能导致基站对于监测区域判断准确性下降,因此,本文把网络生命周期定义为网络中第一个节点死亡的时间,它是评价网络性能的重要指标之一.

图6是LEACH和ECHT协议网络生命周期比较,从图中可以看出,ECHT协议的网络生命周期长,LEACH协议短.原因是ECHT协议采用时间驱动簇头选择,可以降低消息复杂度和节省节点能量.从第一个节点死亡到最后死亡节点的时间跨度可以反映网络中节点能量均衡情况,跨度越短说明网络能量利用率越高效,ECHT协议跨度短,LEACH跨度大.原因是ECHT协议选出剩余能量较高的节点作为簇头,而LEACH协议随机产生簇头,没有考虑节点剩余能量,可能选出的簇头能量低,这样会加速节点死亡.

图5 各种协议簇头数量对比Fig.5 The number of cluster head com parison for various protocol

图6 网络生命周期Fig.6 Netw ork lifetime

4 结 论

针对LEACH协议的不足,提出了一种基于时间均匀分簇混合路由协议,该协议采用了时间驱动簇头选择方法和混合通信机制,降低了算法消息复杂度,它具有以下特点:①该分簇路由协议算法稳定,所生成簇的数目波动小;②能有效均衡网络中节点的能量消耗,延长网络生命周期.

[1] Estrin D,Girod L,PottieG,et al.Instrumenting the World with Wireless Sensor Networks[C].In:Proc.of the Int'l Con f.on Acoustics,Speech,and Signal Processing(ICASSP 2001),2001.

[2] Pottie G J,KaiserWJ.Wireless integrated network sensors[J].Communications of the ACM,2000,43(5):51-58.

[3] Heinzelman WR,Chand rakasanA P,Balak rishnan H.An application specific protocol architecture for wirelessm icrosensor networks[J].IEEE Trans on Wireless Communic-ations,2002,1(4):660-670.

[4] Lu Tao,Zhu Qingxin,Zhang Luqiao.An Improvement for LEACH Algorithm in Wireless Sensor Network[C].Industrial Electronics and Applications(ICIEA),2010 the 5th IEEE Conference on.,2010:1811-1814.

[5] 廖明华,张华,王东.基于LEACH协议的簇头选举改进算法[J].计算机工程,2011,37(7):112-114.

Liao Minghua,Zhang Hua,Wang Dong.Improved cluster-head election algorithm based on LEACH p rotocol[J].Computer Engineering,2011,37(7):112-114.(in Chinese)

[6] Chang JH,Tassiulas L.Maximum lifetime routing in wireles sensor netw orks[J].IEEE/ACMTrans.on Netw orking, 2004,12(4):609-619.