基于CS算法的LEACH极值双簇首分簇方法

吴 慧, 张 品

(杭州电子科技大学 通信工程学院,浙江 杭州 310018)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)中传感器节点在数据传输过程中存在能量有限的问题,设计出一种降低传感器能量消耗的路由算法至关重要[1,2]。

LEACH协议是WSNs中典型的分簇协议[3],以“轮”为周期进行数据传输,每“轮”分为两个阶段,第一个阶段是成簇过程,每个节点产生一个0～1之间的随机数,并与预先定义好的阈值T(n)进行比较,若产生的随机数小于T(n),成为簇首,否则成为普通节点。簇首广播成簇消息(包括自身的ID和建簇信息),普通节点根据接收信号强度(received signal strength indication,RSSI)加入合适的簇中,感知、收集和预处理监测信息并与簇首直接通信；簇首需要对簇内的节点分配数据传输时的时隙并融合发送来的数据,等到全部节点都加入到某一个簇中,第一阶段结束。阈值T(n)定义：当n∈Gr时,T(n)=p/{1-p[r×mod(1/p)]};当n∉Gr时,T(n)=0。其中,p为全网中的簇首数与全部节点的比值,r为当前经历的轮数,Gr为前r-1轮未被选为簇首的节点集合。第二阶段是数据传输阶段,普通节点在规定的时间内将收集到的数据直接传输给簇首,不在规定传输时间内则进入休眠状态,簇首等收集完全部数据后再将数据传送给基站[4,5]。虽LEACH算法以循环方式选举簇首平衡了网络负载,但未考虑节点自身的任何因素使得簇首选举不合理,单跳通信使得距离较远的节点需要消耗大量的能量甚至出现数据无法到达的情况。

目前针对WSNs中节点的数据传输方式,先后提出了许多改进算法,文献[6]中不再采用随机方式选举簇首,而是加入了当前节点的剩余能量来丰富簇首选举公式,使得产生的簇首更加准确,但仍不够完善；文献[7]构造了基于最小生成树的数据传输路由,虽然可以有效均衡能量消耗,但需要对网络进行消息遍历,对能量有过高要求；文献[8]利用粒子群算法优化簇间路由,根据每个节点发送能耗和接收能耗来选择中继节点,减少了能量消耗,但粒子群算法搜索速度较慢,且容易陷入局部最优解；文献[9]改善了原有LEACH协议的分簇方式,均匀各个簇内节点的个数,设置簇内节点阈值数,防止簇的不规则导致节点能耗不均,出现能量空洞,但会在建簇过程中花费较长时间,且簇首在管理控制上消耗不必要的能量；文献[10]将节点能量因素引入簇首选举公式中,数据传输采用簇间多跳方式,当前簇首选择距离自己最近的簇首作为下一跳转发节点,但每轮每个节点会形成单一固定路由而出现节点能耗不均。

本文考虑到上述算法的缺点,提出一种基于布谷鸟搜索(cuckoo search,CS)的改进LEACH算法。首先采用LEACH算法来选择簇首,引入了节点到基站之间的距离,节点当前的剩余能量两个参考因素,并在节点入簇后选出两个极值簇,实施双簇首机制,根据不同的耗能情况建立不同的副簇首选举标准,最后簇首通过高效的布谷鸟搜索算法来优化到基站的数据传输路由。

1 能量模型

传感器节点发送数据耗能[11～14]公式如下

(1)

接收数据消耗的能量

ER(M,d)=M×Eelec

(2)

簇首融合数据时消耗的能量

Emix=C×M×EDA

(3)

式中EDA为融合系数,C为簇内全部的节点个数。

2 基于CS算法的改进LEACH算法

2.1 簇首选举

为避免因原始LEACH簇首随机选举公式带来的簇首分布不均匀,现引入节点剩余能量因素和距离因素,有

(4)

式中Ei为节点i当前的剩余能量,E0为节点的初始能量,dmax为所有节点中到基站最远的距离,dmin为所有节点中到基站最近的距离,di,BS为节点i到基站的距离。

2.2 极值双簇首机制

为避免造成单一簇首的能量过载,簇中引入极值双簇首机制。但为保证簇首数目的最佳性,不是每个簇都需要选举副簇首来分担主簇首的部分功能,仅对于簇内节点数最多的簇(文中以Area1表示)以及其簇内的簇首离基站最远的簇(文中以Area2表示)引入该机制。主簇首的选举通过式(4)的阈值公式实现,而副簇首的选择由不同函数来实现。由于两个簇的主簇首耗能方式的差异,使得副簇首的选择考虑的因素也不同,为Area1定义副簇首选举的能量函数

(5)

同时，为Area2定义副簇首的距离函数

fi=1/di,BS

(6)

其中，fi越大,选为副簇首的概率越高,副簇首也会参与后续数据的转发。

2.3 簇间多跳路由

原有的单跳传输使得距离较远的簇首在传输数据时发生数据失真,甚至低于接收的阈值功率而无法恢复数据的完整性,多跳通信方式可以很好地解决此问题。根据CS算法选择数据传输的下一个簇首节点。

CS算法是在2009年时英国剑桥大学学者Yang X S教授和Deb S提出的一种智能优化算法,其思想最初来源于大自然中布谷鸟寻找鸟窝的行为,常用来求解最优解的问题[15,16]。为模拟CS算法,理想化规定[17,18]：

1)每个布谷鸟一次只产一个蛋,并且随机选择鸟窝来放置鸟蛋；2)随机选择的一组鸟窝中,将最好的鸟窝保留到下一代；3)鸟巢数量一定,鸟巢的主人发现陌生鸟蛋的概率为,一旦鸟蛋被主人发现,丢弃鸟蛋或摧毁鸟巢。

(7)

(8)

(9)

μ～N(0,1)

(10)

v～N(0,1)

(11)

(12)

每次的飞行之后,在更新的鸟巢位置上若无法找到真实环境部署的传感器节点,则按照“就近原则”映射到最近的节点,gbest对应的映射节点是被选择的转发簇首,每个鸟巢的满意函数F与鸟巢的好坏成正比,鸟巢的满意函数在传感器网络中类似于节点性能函数,从选择最佳转发节点的角度出发性能函数由两个因素综合考虑,其中之一涉及到节点的剩余能量,剩余能量越多,说明节点存活时间还长,有足够能力转发数据,另一个则考虑到节点的距离,如图1,d1与d2的和越趋于d3,节点消耗的能量越少,适合作为转发节点[14],其表达式为

图1 距离关系

(13)

式中Ei为节点i当前的剩余能量,allowk为候选簇首节点的集合,di,BS为候选节点i与基站之间的距离,dcurrent,i为当前簇首与候选簇首i之间的距离。

式(5)表明节点剩余能量越多,距离当前节点越近,距离基站越近,选为中继节点的概率越大。

2.4 改进算法设计

算法流程图如图2所示,算法过程只考虑到每轮均有数据传输的情况。

图2 算法流程图

3 算法仿真与结果分析

使用MATLAB软件进行实验仿真,假设传感网络区域是一个200 m×200 m的正方形,随机部署100个节点,用○表示,基站位置固定,坐标为(100,160)m,用*表示,具体分布如图3所示。

图3 节点分布

实验参数设置如下：节点初始能量E0为0.5 J,发送电路和接收电路消耗的能量Eelec为50 nJ/bit,多径衰落模型放大倍数εmp为0.001 3 pJ/(bit·m4),自由空间模型放大系数εfs为100 pJ/(bit·m2),数据融合系数EDA为5 nJ/bit,最大轮数rmax为1 500,每个传感器节点发送的控制数据大小m为200 bit,每个传感器节点发送的数据大小M为4 000 bit,步长控制量α为0.001,β为1.5。

为了验证算法的有效性,本文从网络中节点死亡个数、网络剩余能量和节点存活率三个方面进行算法性能的评价,对本文中的仿真数据进行了50次实验求平均得到数据及仿真结果如图4所示。

图4(a)是LEACH协议,文献[10]提出的算法和本文算法的网络死亡节点数与轮数的关系图,网络节点的死亡数的多少能够直观的判断该网络工作的时间,随着轮数的增加,每个节点不断耗尽自身能量直到死亡。从图中可以看出在本文算法中,第一个节点在869轮出现死亡,相比于LEACH算法和文献[10]算法延长了近1倍的轮数。出现上述情况一方面是副簇首分担了部分主簇首的任务,使得降低了主簇首的能耗速度,另一方面是候选簇首均有相同的机会竞争簇间路由中的转发节点,避免了“能量空洞”现象,一定程度上提升了网络质量。

图4(b)为LEACH协议,文献[10]算法和本文算法的网络剩余能量与轮数的关系图,随着轮数的增加,网络中剩余能量越少。本算法的生命周期为1364轮,较LEACH算法和文献[10]算法分别提高了48.26 %和21.89 %,更好的节约了能量消耗,延长了网络的实际可用时间。

图4(c)为三种算法下不同节点存活率下的轮数(时间)折线图,在每个节点存活率下,本文算法的节点存活数都比其他两种算法要多,且仍旧保持变化的平缓,均衡能耗,保持网络的稳定性。

图4 仿真实验结果

4 结 论

本文提出了基于CS算法的LEACH协议的极值双簇首分簇算法,考虑能量因素和距离因素选择簇首,确保簇首的最佳性,并在节点数最多以及簇首距离基站最远的两个极值簇内根据不同的耗能原因建立副簇首的选举标准,并参与后续数据的转发,引入收敛速度快,搜索效率高的CS算法建立起当前节点到基站之间的传输路径。通过仿真实验比较不同算法,证明了本算法能达到很好的节能效果,均衡簇间负载,改善了无线传感网络一直以来的能量瓶颈问题。