基于CS优化的双簇头分簇路由算法研究

徐艮凤， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)

基于CS优化的双簇头分簇路由算法研究

徐艮凤， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)

为了减少无线传感器网络(WSNs)分簇路由中簇头的能量消耗，提出了一种基于布谷鸟搜索(CS)优化的双簇头分簇路由算法。CS通过采用节点的剩余能量和节点之间的位置关系来构造适应值函数并选举出最优双簇头。其中，主簇头将数据进行融合，副簇头将融合的数据发送给基站，缓解了以往单簇头同时负责数据融合和传输的双重压力，使得整体能耗在各个节点的分配更均衡。仿真实验表明：与LEACH算法、粒子群优化(PSO)算法相比，CS算法在减小网络能耗以及延长网络生存周期上更具优势。

无线传感器网络； 分簇路由算法； 布谷鸟搜索算法； 数据融合

0 引 言

无线传感器网络 ( wireless sensor networks,WSNs)是由在空间上相互离散的各类传感器相互协作构成的传感器网络系统,使得分布于不同场所的数量庞大的传感器之间能够实现更加有效、可靠的通信[1]。无线传感器网络工作时,由于本身能量有限,且不能够对能量进行补充,导致其应用受到了较大的限制。在这种背景下,延长网络生存周期己经成为了一个研究的重点。

LEACH算法中，簇头根据节点随机产生的随机数是否小于阈值产生，虽然可以避免连续成为簇头，但过多的分簇以及分布不均衡会导致节点过早死亡。文献[2，3]在LEACH分簇算法基础上，采用了粒子群优化(PSO)算法选择最优簇头。算法中，簇头需要采集、融合以及转发数据，耗能过快，导致节点过早死亡。文献[4]采用了PSO算法选择双簇头，通过主、副簇头分工工作有效减轻了单簇头的负载，但簇头的能量利用率不高。

本文在LEACH算法基础上，将簇头个数设置为存活节点个数的5 %，并采用布谷鸟搜索(cuckoo search,CS)算法选择最优的双簇头，主簇头负责收集和融合簇内的数据，并将数据转发给副簇头，副簇头再将数据发送给基站，从而降低了单簇头的能耗，使得节点能耗更均衡。

1 CS算法

CS算法，也叫杜鹃搜索算法，由剑桥大学Yang X S教授和Deb S教授于2009年提出的一种新兴启发算法[5～7]。研究发现，CS算法获取的全局最优解要比其他的优化算法更有效。

CS算法是模拟布谷鸟觅食而提出来的,布谷鸟随机游走的方式下，下一步的行动取决于两个因素：1)当前的位置(状态);2)过渡到下一个位置的概率。整个过程基于以下3个理想化状态:1)布谷鸟每次只产一个卵，并随机选择鸟巢孵化；2)在随机选择的一组鸟巢中，最好的鸟巢将会保留到下一代；3) 可利用的鸟巢数量n是固定的，一个鸟巢的主人发现一个外来鸟蛋的概率Pa∈[0，1]。在这3个理想状态的基础上，布谷鸟寻巢的路径和位置的更新公式如下

(1)

Levy(β)～u=t-β，1<β≤3

(2)

2 基于CS优化分簇路由算法

优化的分簇路由算法在LEACH算法基础上采用CS算法，根据节点的剩余能量和节点之间的位置关系来构造适应值函数，选取主簇头和副簇头，分别负责融合和传输。

2.1 簇建立阶段

传统的LEACH算法选择簇头是随机选择一个0～1的数与阈值T(n)进行比较，若小于T(n)则选取为簇头。由于未考虑节点的能量以及簇头个数，可能导致能量低的节点成为簇头，为了避免该问题，阈值公式修改如下

(3)

p(n)=p×n×S(n).E/Et

(4)

式中p(n)为被选为簇头的概率；r为当前循环的轮数；G为最近1/p轮被选为簇头的节点集合；S(n).E为当前节点的能量；Et为所有初始节点的总能量。

算法中，与传统LEACH算法筛选簇头的方法一致，但定义了簇头个数为存活节点总个数的5 %，有效避免了簇范围过大或过小。

2.2 主、副簇头的选择

在分簇完成后，CS算法构造了两个关于节点剩余能量和节点之间位置关系的适应值函数，分别用来选取主簇头和副簇头。将建立的n个簇范围分别代入算法中，选取出n对主、副簇头。为了使CS算法适合该研究环境，需对原CS算法中的位置更新式(1)进行改进，并采用合适的适应值函数。

(5)

(6)

则

(7)

主簇头的主要任务为收集并融合簇内数据，并将数据发送给副簇头，因此,需要较高的能量以及该节点距离簇内节点的平均距离越小越好。主簇头的选取采用以下适应值函数

(8)

式中δ和1-δ分别为节点能量影响因子和节点平均距离倒数的影响因子，δ∈[0,1]；k为簇内节点数；E(c)为主簇头c的能量；E(i)为节点i的能量；ditoc为节点i到簇头c的能量；f1为主簇头能量占簇内节点的比例；f2为簇内节点到主簇头平均距离的倒数。

副簇头的主要任务是将主簇头发送的数据转发至基站，因此，需要较高的能量以及该节点距离基站的距离越小越好。副簇头的选取采用以下适应值函数

(9)

式中 γ和1-γ分别为节点能量影响因子和节点距离影响因子，γ∈[0,1]；g1为副簇头能量占簇内节点的比例；g2为副簇头到基站的距离占簇内节点到基站的距离和的比例。

2.3 CS优化的双簇头选取的具体步骤

算法的主簇头选取具体步骤如下：

1)初始化鸟巢数n，Pa及最大迭代次数Nmax。

3)利用式(8)计算出适应值f(i)。

7)副簇头的选取具体步骤与主簇头类似。

3 算法仿真与分析

3.1 仿真环境

采用Matlab仿真平台。100个传感器节点随机分布在100m×100m的网络中，基站坐标位于(50，75),节点的初始能量为E0×(1+rand)，E0为0.5J，控制包大小为100B，数据包大小为4kB,εfs=10pJ/(bit·m2),εamp=0.001 3pJ/(bit·m4),Etx=Erx=Eelec=50nJ/bit,EDA=5nJ/(bit·signal)。

3.2 仿真结果

为了分析本文算法的性能，将本文算法与LEACH算法以及PSO_DH算法[4]进行仿真比较，以不同轮数中存活节点数、网络总能耗、数据到基站传输量为评价标准。

图1为网络生命周期的比较。以第一个节点死亡时间作为网络的生命周期，通过仿真实验可以看出:本文算法第一个死亡节点的轮数为1 623轮;LEACH算法为174轮;PSO_DH算法为1 607轮。相对LEACH算法、PSO_DH算法具有更长的网络生命周期。

图1 网络生命周期比较

图2为网络总能耗的比较。从图中可以看出，本文算法相对LEACH算法能耗明显减少，较优于PSO_DH算法的总能耗。

图2 网络总能耗比较

图3为数据到基站传输量的比较。从图中可以看出：在运行800轮时，本文算法中数据到基站的传输量明显低于LEACH算法。并且，随着运行轮数的增加，LEACH算法在运行1039轮时，网络中节点全部死亡。然而本文算法中数据到基站的传输量明显低于PSO-DH算法。由此可见，采用CS优化算法在簇头进行数据融合的效果好于LEACH算法和PSO-DH算法。

图3 数据到基站传输量比较

4 结束语

针对WSNs中分簇路由的不足，提出了基于CS优化的双簇头分簇路由算法，通过仿真实验证明算法较PSO优化算法及经典LEACH算法具有更好的性能。新的分簇路由算法采用CS算法选取主簇头和副簇头，分别负责融合和传输。比之以往单簇头同时负责数据融合和传输的双重压力，整体能耗在各个节点的分配更均衡，从而延长了整个网络的生命周期。

[1] 刘奇奇,张曦煌.基于萤火虫算法的无线传感器网络的分簇路由协议[J].传感器与微系统,2015,34(9):114-116.

[2] 刘志坤,刘 忠,李朝旭.基于混沌粒子群优化的无线传感器网络分簇协议[J].传感技术学报,2011(10):1459-1463.

[3] 梁 英,于海斌,曾 鹏.应用PSO优化基于分簇的无线传感器网络路由协议[J]. 控制与决策,2006(4):453-456,461.

[4] 韩冬雪,张瑞华,刘丹华.基于PSO的无线传感器网络双簇头分簇算法[J].计算机工程,2010(10):100-102.

[5]YangXS,DebS.CuckoosearchviaLevyflights[C]∥2009WorldCongressonNature&BiologicallyInspiredComputing,NaBIC2009,IEEE,2009:210-214.

[6] 兰少锋,刘 升.布谷鸟搜索算法研究综述[J].计算机工程与设计,2015(4)：1063-1067.

[7] 王 旭,张曦煌.基于布谷鸟搜索算法的无线传感器网络改进路由协议[J].传感器与微系统,2016,35(7):45-47.

张曦煌，男，教授，主要从事无线传感网、嵌入式系统、计算机网络、图形与图像处理、计算机分布式控制与智能控制等研究工作。

Research on dual-cluster heads clustering routing algorithm based on CS optimization

XU Gen-feng, ZHANG Xi-huang

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

In order to reduce the energy consumption of cluster head in wireless sensor networks(WSNs)clustering routing,a dual-cluster heads clustering routing algorithm based on cuckoo search(CS)optimization is proposed.The CS algorithm construct fitness function by using residual energy of nodes and relationship of position between nodes and elects optimal dual-cluster heads.In which,the main cluster head fuse data and the vice cluster head sends the fused data to the base station.It relieves dual pressure of data fusion and transmission beared by single cluster head in the past,so that distribution of the overall energy consumption in each node is more balanced. Simulation experiment show that compared with LEACH algorithm,PSO optimization algorithm,CS algorithm has more advantages in reducing network energy consumption and prolonging network lifetime.

wireless sensor networks (WSNs); clustering routing algorithm; cuckoo search (CS) algorithm; data fusion

10.13873/J.1000—9787(2017)09—0136—03

2016—08—17

TP 391

A

1000—9787(2017)09—0136—03

徐艮凤(1990-)，女，硕士研究生，主要研究方向为无线传感器网络、嵌入式系统、计算机网络，E—mail:2467933944@qq.com。