基于布谷鸟搜索算法的无线传感器网络改进路由协议

王 旭， 张曦煌

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

基于布谷鸟搜索算法的无线传感器网络改进路由协议

王 旭， 张曦煌

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

为了解决无线传感器网络(WSNs)能量消耗不均衡，网络生存时间短的问题，在研究了几种现有路由协议基础上，提出一种基于LEACH协议改进的簇间多跳路由协议。该协议引入能量因子、密度因子和距离因子,修正了LEACH协议的阈值函数，并结合布谷鸟搜索算法对簇头集合进行了优化，同时提出新的路由机制，在簇头采用多跳方式和Sink节点进行数据通信。模拟实验表明：相比于LEACH协议，提出的新协议可以有效地均衡网络节点能量，延长网络生命周期。

阈值函数； LEACH协议； 布谷鸟搜索算法； 多跳

0 引 言

由于无线传感器网络(WSNs)节点的电量受限，故延长网络的生命周期是目前无线传感器网络领域研究的主要问题。目前，相关研究人员已经提出多种路由协议，其中比较经典的路由协议有低能耗自适应聚类分级(low energy adaptive clustering hierarchy,LEACH)[1]协议，PEGASIS[2]协议等。

布谷鸟搜索算法是全局搜索性能较优秀的一种元启发式算法，采用相关的Levy飞行搜索机制。研究表明，布谷鸟搜索比其他群体优化算法更有效。

1 基于布谷鸟算法的新的改进协议

LEACH协议是无线传感器网络中最早提出的分层路由协议，其基本思想是通过随机循环地选择簇头节点，将网络的能耗平均分配到传感器节点上，提高网络存活时间。

LEACH协议采用的阈值方程由于是概率化的，很可能导致以下问题：低能量的节点可能会成为簇头节点，导致节点提前死亡；选举的簇头节点的数目不确定，若选举的簇头节点的数目小于最优节点数目，会导致网络消耗更多的能量，如果选举的簇头节点的数目大于最优节点数，网络消耗的能量将不会达到最优。

由于经典LEACH协议存在许多缺点，故有大量改进LEACH的研究[3～6]，这些工作在一定程度上改善网络存活时间。

本文通过研究已有几种协议的优缺点，提出一种基于布谷鸟算法的的改进多跳路由协议。

1.1 准备阶段

1.1.1 预优化阶段

本文提出一个备用簇头选举方程

Ci(t)=Yi(t)+RNi(t)

(1)

式中

Yi(t)=we×R(i,t)+wm×M(i,t)-wd×S(i,t)

(2)

式中 R(i,t)=E(i,t)/E0；E(i,t)为节点t轮时的剩余能量，E0为节点初始能量，R(i,t)为正因素;M(i,t)=Q(i,t)/Qmax,Q(i,t)普通节点密度，Qmax为最大密度，M(i,t)为正因素；S(i,t)=D(i,t)/Dmax，D(i,t)为节点到基站的距离，Dmax为最大距离，S(i,t)为负因素；we,wm,wd为权值因子，其中,we=0.7，wm=0.4，wd=0.1。

由于簇头选择的随机性，故还应该加上随机因子RNi(t)。

显然,剩余能量越大，节点密度越高，节点距离基站越近，成为簇头可能越高。

根据文献可知，最优簇头数为

(3)

1.1.2 簇头选举阶段

在簇头选举阶段，本文通过布谷鸟算法搜索(CS)算法[7,8]来对备用簇头集合进行优化，从而获得较好的簇头集合。

为了模拟布谷鸟寻窝的方式，首先，需要设定以下3个理想的状态：1)布谷鸟一次只产一个卵，并随机选择鸟窝来孵化;2)在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代;3)可利用的鸟窝数量是固定的，一个鸟窝的主人能发现一个外来鸟蛋的概率P∈[0,1]。

在这3个理想状态的基础上，布谷鸟寻窝的路径和位置更新公式如下

(4)

在无线传感器网络中，能耗是最关键的问题，本文提出的目标方程为

fmin(CH[Kopt])=(Ech,Eoc)

(5)

(6)

Eoc=∑∑(E(ch)E(oc)

(7)

式中 Ech为簇头剩余能量，Eoc为普通节点消耗能量。

通过上述算法选举出Kopt个节点充当簇头，并向所有节点广播簇头当选消息，节点根据所收到的信号强度决定加入哪个簇。

1.2 稳定阶段

根据能量模型可知，传输距离对能耗的影响很大，而在传统的LEACH协议中簇头融合数据后一般通过单跳和基站通信，将获取的数据传输给基站，这导致电量很大程度的浪费，故本文对节点的路由进行了改进。

如图1所示，可以将传感器节点覆盖区域想象成一个正方形区域，节点随机分布，可以将此区域分成3个区域：其中，普通区覆盖所有区域；对于开始阶段选出来的簇头集合，同样可以将簇头分为三类：路由簇头、普通簇头、中转簇头。

图1 节点区域划分Fig 1 Node region division

假如传感网区域为边长为a的正方形区域，则路由区所覆盖的面积百分比为

(8)

Route(mun)=Kopt×Bzz

(9)

路由簇头：根据式(8)和式(9)，选择处于路由区的Route(num)个簇头充当路由簇头，若处于路由区的簇头数目小于Route(num)，则从候补簇头中选择，路由簇头将普通节点和中转节点的数据传输给基站；中转簇头：若有簇头处于中转区，此簇头为中转簇头，中转簇头负责中转数据；普通簇头：除路由簇头和中转簇头外的其他簇头，将数据传输给路由簇头和中转簇头；

对于除路由簇头以外的所有簇头

(10)

Broadcast(i)={0.5d0,d0,…k(i)d0}

(11)

式中 Broadcast(i)为簇头向此区域广播的圆心半径范围，从而获得每个簇头的邻居簇头表

(12)

根据邻居簇头表中的簇头，分三种路由情况：

1)该簇头既有路由簇头也有中转簇头:将簇头数据按式(12)的比值分别传输给它们，传输给路由簇点的数据直接发送到基站，中转簇头节点的数据再循环路由。

2)该簇头邻居簇头表没有路由簇头:若邻居簇头表中没有路由簇头，则将数据按式(12)比值传输给中转簇头，然后再循环路由。

3)该簇头邻居簇头表没有中转簇头:若邻居簇头表中没有中转簇头，则将数据按式(12)比值传输给路由簇头。

2 仿真与结果分析

2.1 仿真环境

在200m×200m的正方形区域内，随机分布200个传感器节点，所有传感器节点能量有限，位置固定不变。仿真采用Matlab2010b模拟，仿真具体环境参数设置：基站坐标(100，250)m，初始能量0.5J，多路衰减模型的功率放大系数10pJ·bit-1·m-2，自由空间模型的功率放大系数0.001 3pJ·bit-1·m-2,发送、接收消耗能量50nJ·bit-1，数据包400bit,数据融合消耗能量5nJ·bit-1。

2.2 仿真结果

200个节点初始分布如图2。

图2 初始200个节点分布Fig 2 Initial distribution of 200 nodes

由于初始节点是随机生成的，为了减少误差，实验采用5组数据观察算法效果，5次运行结果如表1。

表1 随机5次算法运行结果Tab 1 Random 5 times running results of algorithm

如表2可以看出，第一个节点死亡时间大致在500～600轮。

表2 本文算法和LEACH算法比较Tab 2 Comparison of new algorithm and LEACH algorithm

表2和图3是本文算法和经典LEACH算法的比较，从中可以看出:新算法第一个节点死亡轮数为534轮，明显好于经典LEACH算法，且算法均衡全局网络能量，延长网络存活时间。

3 结束语

本文提出了基于分簇思想的新的算法，在两个层面上进行了改进，第一个是采用新的备用簇头选举方程，并结合布谷鸟搜索算法，避免经典LEACH算法阈值方程的缺陷，并选取最优簇头数，第二个改进是簇头的路由机制，簇头被分成三类簇头：路由簇头、中转簇头、普通簇头，通过不同半径的广播，簇头生成邻居簇头表，并根据相应公式将数据按比例传输。算法在一定程度上平衡网络能量，延长节点存活时间。

[1] Akyildiz I F,Sankarasubramaniam Y,Su W,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

[2] Stephanie Lmdsey,Cauligi S aghavendra.PEGASIS:Power efficient gathering in sensor information systems[C]∥Proceedings of IEEE Aerospace Conference，2002:1125-1130.

[3] 苏 淼,钱 海,王煦法.基于蚁群的无线传感器网络双簇头算法[J].计算机工程,2008,34(13):174-176.

[4] 王 进,邵玉斌,龙 华,等.基于能量和距离加权的WSNs簇头选择算法[J].传感器与微系统,2014,33(5):132-134.

[5] 郦元宏,张卫强,潘小龙.基于LEACH的能量节省路由协议的研究[J].通信系统与网络技术,2014，40(5):24-26.

[6] 韩 进,陈 树.受限节点的WSNs非均匀分簇算法应用研究[J].传感器与微系统,2014,33(2):19-22.

[7] 王小辉,李圣普,吕海莲.基于布谷鸟算法的WSNs节点定位研究[J].计算机技术与发展,2014(12):208-211.

[8] 郑巧燕,莫愿斌,刘付永,等.一种小规模多种群布谷鸟算法[J].计算机应用与软件,2014(10):278-280，317.

Improved routing protocol for WSNs based on CuckooSearch

WANG Xu, ZHANG Xi-huang

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

In order to solve problem of unbalanced energy consumption of wireless sensor networks(WSNs),and short lifetime of networks,on the basis of studies on several existing routing protocol based on LEACH protocol,propose an inter-cluster multi-hop routing protocol based on LEACH protocol.The protocol introduces energy factor,density factor and distance factor to correct threshold function for LEACH protocol and optimize cluster head set combined with CuckooSearch,and also propose a new routing mechanism,cluster head nodes communicate with Sink node by multi-hop mode.Simulation results show that,compared with LEACH protocol,the new proposed protocol can balance effectively energy consumption of network nodes,and prolong network lifecycle.

threshold function; LEACH protocol; CuckooSearch; multi-hop

10.13873/J.1000—9787(2016)07—0045—03

2015—10—15

TP 391

A

1000—9787(2016)07—0045—03

王 旭(1991-)，男，江苏泰州人，硕士研究生，主要研究方向为无线传感网络、云计算。