门顺治,孙顺远,徐保国

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



基于PSO的无线传感器网络非均匀分簇双簇头路由算法*

门顺治,孙顺远,徐保国*

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

针对无线传感器网络中分簇路由算法簇头负载过重,同时也为了提高无线传感器网络的能量利用效率,提出了一种基于PSO的非均匀分簇双簇头路由算法。该算法首先通过候选簇头节点与基站距离的远近构造出几何规模不等的簇,然后根据簇的规模引进PSO优化算法最终选择出主簇头与副簇头。主簇头主要负责簇内节点数据的采集跟数据融合,副簇头主要完成簇内及簇间数据转发任务,实现数据的单跳与多跳传输。仿真结果表明,该算法有效的减少了簇头节点的能耗,在很大程度上均衡了整个网络的能耗,实现了网络生存周期的延长。

无线传感器网络;非均匀分簇;粒子群优化算法;双簇头

无线传感器网络WSN[1](Wireless Sensor Network)是由部署在监测区域内大量能量有限的微型传感器网络节点组成,通过无线通信的方式形成一个网络系统,其目的是协作感知、采集和处理网络覆盖地理区域内感知对象的信息,并发布给观察者。近年来,随着传感器技术、通信技术等技术的发展,WSN越来越广泛的应用于工业、农业、环境监测等方面。在WSN中,由于节点一般处于静止状态且电池难以更新,如何设计出一种节约节点能量、延长网络生存周期的无线路由算法是当前的热点之一[2-3]。

1 相关工作

1.1 分簇算法的论述

2000年Heinzelman W R等人提出的LEACH[4](Low-Energy Adaptive Clustering Hierarchy)算法是一种经典的低能量自适应分簇路由算法。在LEACH算法中,簇头节点跟基站采用的是单跳路由通信协议,离基站较远的簇头能量消耗过大而过早死亡,影响整个网络的生存周期,并且单跳传输不易于无线传感器网络的扩展。针对LEACH算法中离基站较远的簇头因发送数据能量消耗过多而过早死亡,文献[5]采用了一种多跳通信方式,但是由于距离基站较近的簇头承担着更多的数据转发任务而消耗过多能量,易形成“热区”。EECS[6]算法采用的是分布式工作方式,节点仅需局部信息即可完成分簇,并且分簇充分考虑到节点的剩余能量及簇首间的负载平衡。但由于簇首到汇聚节点仍采用单跳传输方式,无法从根本上解决热区问题。EEUC[7](Energy-Efficient Uneven Clustering)算法通过构造几何规模不等的簇来改善“热区”问题,但当簇规模过大时,簇头的选举不当也会使簇内节点的能量消耗过快,从而影响网络的生存周期。文献[8]是在LEACH分簇算法基础上,利用PSO优化一个比较理想的簇头来实现能耗较少,但由于簇头任务过重,易造成能耗过快消失,加速网络死亡。文献[9]提出了双簇头的方法,主簇头根据节点间的最大连通度和能量来选择,相对于单簇头,能有效减小簇头负载,但广播信息较多,能耗较大。

针对上述问题,本文提出了一种基于PSO的非均匀分簇双簇头路由算法(PSO-NUDC)。首先通过候选簇头节点与基站距离的远近构造出几何规模不等的簇,然后在规模较大的簇内采用PSO优化算法重新选择主副簇头,主簇头主要完成簇内节点数据的采集跟数据融合的任务,副簇头主要负责簇内及簇间数据转发,实现数据的多跳传输。

1.2 PSO算法

粒子群优化PSO(Particle Swarm Optimization)算法是由Eberhart博士和Kennedy博士提出,是一种模拟鸟类觅食的群智能优化算法。在算法中,每一个优化问题都是搜索空间一个粒子,所有的粒子都有一个被优化的函数决定的适应值,每一个粒子还有一个速度决定着他们的方向跟距离,粒子跟随当前的最优粒子在解空间中搜索,不停的改变自己的方向以及速度大小。在这个过程中,开始粒子比较分散,逐渐汇成一群,直到找到最优解[10-11]。

PSO优化算法将粒子群初始化为一组随机粒子(随机解),所有粒子在搜索空间中通过迭代找到最优解。在迭代过程中,粒子根据个体极值与全局极值不断调整自己的位置,不断更新。个体极值指的是一个是粒子本身找到的最优解,而全局极值为目前整个群体找到的最优解。通过找到两个极值后,粒子由式(1)～式(2)来更新自己的位置。

vij(t+1)=wvij(t)+c1r1[pij-xij(t)]+c2r2[pij-xij(t)]

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

其中,c1、c2为加速系数,用于控制粒子的运动速度;r1、r2是[0,1]里的随机数;w是权重系数,用于控制粒子历史值对当值的影响程度;vij(t)表示的是粒子i在第t次迭代过程中第j维的速度;xij(t)表示的是粒子i在第t次迭代过程中第j维的位置;pid(t)、pgd(t)分别为个体极值与全局极值。

2 PSO-NUDC算法

2.1 非均匀簇的建立阶段

LEACH算法将单个节点的状态作为簇头选择的度量标准,没有考虑剩余能量平衡问题,为了避免能量低的节点成为簇头,定义门限值τ如下:

(3)

式中,p是节点当选为簇头的概率,r为当前循环的轮数,En_max和E(ni)分别为节点的初始能量和当前能量,G是最近1/p轮当选为簇头的节点集合。从式(3)中可以看出,当选过的节点在接下来的1/p轮内不能成为簇头。网络初始化时,每一个普通节点都生成一个随机数μ(0<μ<1)。若μ<τ,则该节点成为候选簇头节点;非候选簇头节点将进入休眠状态,直至初始簇头竞选过程结束。同时,通过候选簇头节点设置的竞争范围Rc[12]来控制簇在网络中分布。距离基站越近的簇的几何半径越小,簇的个数越多,以解决“热区”问题,相反的,离基站越远的簇的几何半径也越大,簇的个数越小,以平衡网络节点能量。由此可见候选簇头节点的竞争半径与基站的距离成正比例关系。假设Si为一个候选簇头节点,其竞争半径Rc为

(4)

2.2 PSO优化主副簇头选取阶段

非均匀分簇阶段完成后,根据簇几何规模的大小引进PSO算法选取最终的主副簇头以减少算法的复杂度。设定一个门限制k,当簇半径大于门限值k时,将运用PSO选取最终的主副簇头;当簇半径小于门限值k时,初始主副簇头将直接转变为最终簇头。

为使原PSO适用于本问题,需将原PSO中的式(1)和式(2)进行改进,并得出一个合适的适应值函数fit(x)。

假设n个网络节点处于平面坐标内,网络节点i的位置xid和速度vid分别由x,y两个方向上的分量决定。所以式(1)被具体化为式(5)和式(6):

xxid(t)=xxid(t-1)+vxid(t)

(5)

xyid(t)=xyid(t-1)+vyid(t)

(6)

式(2)被具体化为式(7)和(8)

vxid(t)=wvxid(t-1)+c1r1[pid-xxid(t-1)]+
c2r2[pgd-xxid(t-1)]

(7)

vyid(t)=wvyid(t-1)+c1r1[pid-xyid(t-1)]+
c2r2[pgd-xyid(t-1)]

(8)

由于网络节点是离散分布的,由式(5)～式(6)计算所得出的位置无法一一映射到相应的实际节点,因此需要进行调整,xxid(t)∈{px1,px2,…,pxn},xyid(t)∈{py1,py2,…,pyn},其中pxi和pyi分别为簇内节点上的x分量与y分量。

设Δpxi是xxid(t)跟i节点上的x分量差的绝对值,Δpyi是xyid(t)跟i节点上的y分量差的绝对值:

Δpxi=|xxid(t)-pxi|

(9)

Δpyi=|xyid(t)-pyi|

(10)

则:

(11)

Δpk=min(Δp1,Δp2,…,Δpn)

(12)

可以得出第k个节点的位置同xid(t)最为接近,所以调整后的值为

xxid(t)≈pxk

(13)

xyid(t)≈pyk

(14)

即搜索点现在位于节点k的位置上。

适应值函数的确定是PSO算法中的一个重要的问题。适应值函数设定的理想程度直接决定了最终选取主副簇头的优劣。主簇头节点的适应值函数的确定要考虑两个方面,一方面是主簇头节点能量问题,这主要是主簇头节点负责数据收集跟转发任务,要比簇内节点消耗更多能量;另一方面是簇头节点离簇内节点的距离问题,由于主簇头节点主要负责收集簇内节点的信息,因此主簇头节点与簇内节点之间的平均距离越小越好。

考虑上述因素,可以采用下面的适应函数f:

f=ε×f1+(1-ε)f2

(15)

(16)

(17)

其中,m是簇内节点个数;E(ni)是节点ni的能量;f1是主簇头节点能量占簇内节点能量的多少;f2是簇内节点到主簇头的平均距离的倒数;di to H是节点i到主簇头的距离。

由此可见,f1表示是使主簇头具有更多的能量,而f2表示的是使主簇头到簇内节点的平均距离最小。而由ε可以调节适应函数f中f1和f2所占的比重。选择使f值最大的节点作为主簇头。

对于副簇头,其任务是将数据传输至基站,因此它不仅需要具有较高的能量,而且距离基站越近越好。基于以上原因,副簇头的选取应采用下面的适应值函数g:

g=λg1+(1-λ)g2

(18)

(19)

(20)

其中,g1与式(16)中f1一样,是指副簇头节点能量占簇内节点总能量的比例;dH to BS是副簇头到基站的距离;di to BS是节点i到基站的距离;g2则表示副簇头到基站的距离占簇内节点到基站距离总和的比例。g2越大则表示副簇头离基站也越近。由λ调节适应函数g中g1与g2所占比重,选择使g值最大的节点为副簇头。

簇内应用PSO优化算法选取主簇头流程图如图1所示,基本步骤如下:①初始化粒子群。在簇内随机初始化粒子i的位置xxid(t)、xyid(t)与速度vxid(t)、vyid(t),由式(9)～式(14)对粒子的位置进行调整;②由式(15)～式(17)得出适应值f,并且令粒子的个体极值pid=粒子当前位置,全局极值pgd=取得最大适应值的粒子的位置;③由式(5)～式(8)对每个粒子的位置xxid(t)、xyid(t)与速度vxid(t)、vyid(t)进行更新,并由式(9)～式(14)对粒子的位置进行调整;④由式(15)～式(17)得出各个粒子的适应值f,同时更新个体极值与全局极值;⑤重复步骤③～步骤④,直到达到最大的迭代次数为止,选择最优解对应的节点为主簇头;⑥根据副簇头适应值函数式,重复以上操作,选择最优解对应的节点为副簇头。

图1 基于PSO优化选择主簇头的流程

2.3 多跳传输

在数据传输阶段,副簇头接收来自主簇头的数据后,将根据自身离汇聚节点的距离选择单跳或多跳传输至基站。在数据传输开始阶段,每个副簇头向全网广播消息,包含其ID、当前剩余能量和距汇聚点的距离。副簇头Si收到副簇头Sj广播的消息后,可以计算出它们之间的近似距离。假设Si选择Sj作为数据转发副簇头,并且Sj直接将lbit数据传输给基站,采用文献[13]所提出的一阶无线通信能耗模型,根据能耗公式得:

(21)

(22)

其中,α可根据具体的应用环境进行设置;当Si选择剩余能量大于自身,并且到基站的通信开销低于Si的副簇头Sj为下一跳路由。各个副簇头从Wnext大于1的副簇头中选择权值最大的副簇头为下一跳节点,进而形成到基站的多跳路由路径,Wnext最大的节点将收集的监测数据传输给基站。如果副簇头找不到Wnext大于 1的下一跳节点,则该副簇头节点就直接与基站进行单跳数据传输。这样就形成了副簇头到基站的单跳与多跳相结合的路由路径。

3 仿真结果及分析

3.1 仿真环境

本文采用MATLAB仿真平台,如图2所示将200个传感器节点均匀散布在200 m×200 m网络中,基站位于0 m,100 m。每个节点的初始能量为0.5 J,控制包大小为100 byte,数据包大小为4000 byte,门限值τ为0.4,PSO优化算法的各参数为:ε=0.6,εfs=10 pJ/(b·m-2),εamp=0.0013 pJ/(b·m-4),λ=0.3,c1=c2=2,w=0.9,α=0.4,Eelec=50 nJ/bit。

图2 节点分布图

3.2 仿真结果及分析

为了对PSO-NUDC算法的有效性跟可用性进行评估,将其与文献[4]中的LEACH算法和文献[7]中的EEUC算法进行仿真对比,以不同轮中簇头节点的能耗之和、网络的生存周期和网络剩余总能量为评价标准。

图3为3种算法的簇头节点在不同轮中能耗之和的对比。为了减小实验的偶然性,在前50轮中每隔5轮进行一次能耗对比。从图(3)可以看出,PSO-NUDC算法的簇头节点能耗在0.01 J～0.05 J之间,并且较为平缓,远远好于EEUC与LEACH算法。这主要是由于PSO-NUDC算法根据簇头的任务不同,选取最优主簇头负责数据的收集与融合,最优副簇头通过多跳负责数据的转发,有效的减轻了簇头负载,而LEACH算法的簇头是随机产生,并且采用单跳与基站传输数据,离基站较远的簇头由于能量消耗过大会导致过早死亡。

图3 每轮簇头能耗总和比较

网络的生存周期是衡量传感器网络质量的一个重要指标,本文以第1个节点死亡时间作为网络生命周期的评价标准。由图4可以看出,LEACH算法第1个节点死亡出现在第147轮,EEUC算法出现在第324轮,PSO-NUDC算法出现在第564轮。其中,PSO-NUDC算法与LEACH算法和EEUC算法相比,网络生存周期分别延长了41.7 %和24 %。这是因为PSO-NUDC算法中非均匀簇的建立以及最优主副簇头的不同分工可以更有效的均衡簇内和簇间的能耗。

图4 网络剩余存活节点数

图5 网络总能耗

较小的坡度表示了总能量消耗的较慢跟较长的生存周期,由图5可以看出,PSO-NUDC算法的坡度明显小于其余两种。在第400轮时,PSO-NUDC算法的剩余能量比较LEACH算法与EEUC算法分别增加了39.58 %和15.52 %。非均匀簇的建立以及利用PSO选择最优主副簇头能够更好的提高整个网络的能量使用效率。

通过MATLAB仿真与LEACH算法、EEUC算法相比可以看出,PSO-NUDC算法能够更好的提高能量使用效率,显著的延长网络的生存周期。

4 结论

针对WSN网络中分簇路由算法的不足,本文提出了一种基于PSO的非均匀分簇双簇头路由算法。该算法通过MATLAB仿真实验与其他算法比较表明,PSO-NUDC算法较好的改善了“热区”问题,副簇头的存在减轻了主簇头的能量消耗,更好的均衡了整个网络的能量能耗,延长网络的生存周期。但是在一些比较小的簇里面,没有必要设置副簇头。因此今后的重点是研究簇头数目的弹性设置问题以及算法中各参数的选择对结果的影响问题。

[1] 彭力. 无线传感器网络技术[M]. 北京:冶金工业出版社,2011:1-5.

[2]唐勇,周明天,张欣. 无线传感器网络路由协议研究进展[J]. 软件学报,2006,17(3):410-421.

[3]宫鹏. 无线传感器网络技术环境应用进展[J]. 遥感学报,2010,14(2):387-388.

[4]Heinzelman W,Chandrakasan A,Balakrishnan H. Energy Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences. Maui:IEEE Inc,2000:3005-3014.

[5]陆立芳,闫建国. 无线传感器网络路由协议的优化设计[J]. 计算机仿真,2010,27(12):125-128.

[6]Ye Mao,Li Chengfa,Chen Guihai,et al. EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]//Proceedings of 24th IEEE International Performance Computing and Communi-cations Conference(IPCCC). Phoenix,USA:IEEE Inc,2005:535-540.

[7]李成法,陈贵海,叶懋,等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报,2007,30(1):27-36.

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

[9]徐丹丹,章勇. 一种基于最大连通度的双簇头分簇算法[J]. 传感技术学报,2008,21(11):1909-1912.

[10]蒋畅江,石为人,向敏,等. 基于PSO的无线传感器网络节能分簇协议[J]. 计算机工程,2010,36(8):15-17.

[11]苏炳均,李林. 粒子群优化的无线传感器网络仿真研究[J]. 计算机仿真,2010,27(9):150-152.

[12]邹杰,史长琼,姬文燕. 基于粒子群优化的非均匀分簇路由算法[J]. 计算机应用,2012,32(1):131-133.

[13]Heinzelman W R. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,4(1):660-670.

门顺治(1988-)男,山东烟台人,硕士研究生,研究方向为计算机控制,传感器网络应用;

孙顺远(1984-),男,博士研究生,主要从事计算机控制,无线传感网络应用方面研究;

徐保国(1951-)男,教授,博士生导师,主要研究方向为过程控制、智能仪表及现场总线网络等。

WirelessSensorNetworksNon-UniformClusteringandDclusterHeadsRoutingAlgorithmBasedonPSO*

MENShunzhi,SUNShunyuan,XUBaoguo*

(School of IOT Engineering,JiangNan University,WuXi Jiangsu 214122,China)

Because cluster heads of clustering routing algorithm have heave load in wireless sensor network(WSN),and in order to improve the energy efficiency in WSN,this paper proposes non-uniform clustering and double cluster heads routing algorithm based on PSO. Firstly,the proposed algorithm construct clusters with different geometric sizes according to the distance from the base station,then introduce PSO optimization algorithm according to the size of the cluster. The main cluster head is responsible for collecting the node data and data fusion,the deputy cluster heads is mainly completed the tasks of forwarding data between cluster and cluster,and the deputy cluster achieve multiple hop transmission of data. The simulation results show that the algorithm is effective to reduce the energy consumption of cluster head nodes,balance the energy consumption of the entire network in a large part,and prolong the life cycle of network.

Wireless Sensor Network(WSN);non-uniform clustering routing;Particle Swarm Optimization(PSO)algorithm;double cluster heads

项目来源:国家自然科学基金项目(21206053,21276111);中国博士后基金项目(2012M511678)

2014-04-16修改日期:2014-07-30

10.3969/j.issn.1004-1699.2014.09.022

TP393

:A

:1004-1699(2014)09-1281-06