基于模糊密度峰聚类和PSO的WSN能量均衡算法

张 勇,吕黎明

(江苏海洋大学计算机工程学院,江苏连云港 222000)

1 引言

在能源有限的无线传感器网络中,如何设计一种高效节能的路由算法,延长网络的生存周期,是WSN研究的关键[1]。针对这一问题,研究者提出了不同类型的路由算法延长WSN的生命周期。其中常用且有效的一种方式是聚类路由优化算法。通过将传感器节点聚类能够实现提高能源效率和网络的使用寿命,达到无线传感器网络高效节能的目的[2]。

WSN分簇路由协议中,最典型的是LEACH(Low Energy Adaptive Clustering Hierarchy)协议[3]。该算法引入轮的概念,每轮分为簇的建立和数据传输阶段,通过概率机制周期性选取簇头[4]。该算法研究的主要目的是通过减少能源消耗来提高WSN的寿命,虽然该协议有优点,但它的簇头选取策略无法保证簇头均匀分布在整个网络。SU L[5]对LEACH协议进行了优化,提出了一种基于LEACH-GAF算法的分簇路由协议。通过GAF算法在每轮开始时将所有节点划分成不同区域,然后应用LEACH算法的概率机制在每个区域内选择簇头。该算法虽然可以保证簇头分布的均匀,但无法保证选取最优簇头。崔小勇等人[6]提出基于遗传模拟退火算法,优化簇头到基站的传输路径,均衡节点的剩余能量,延长网络生存周期。

聚类协议被证明是实现WSN节约能量的有效方法,如何选择最优CH成为聚类算法的关键部分[7]。现有的聚类协议存在关于聚类结构的问题,这会对协议的聚类性能产生不利影响[8]。同时,由于传感器节点是随机部署在一定区域,节点的分配存在模糊性和不确定性。为了解决上述问题,本文提出了一种基于FDPC和PSO优化的无线传感器网络能量均衡路由算法(FDPC-PSO)。本研究的贡献总结如下:

1)采用的FDPC算法具有模糊分区的优势,可以提高聚类性能的灵活性,在处理集群的模糊性和不确定性方面提供了额外的潜力。

2)将数据传输路径的选择规划为NP完全问题,并采用PSO算法优化传输路径,提高能量利用率。

2 系统模型

在本节中,将介绍系统模型,包括网络模型和能量消耗模型。

2.1 网络模型和假设

本文研究的是由一个基站(BS)和200个传感器节点随机分布在100*100 m2区域内的静态传感器网络。传感器节点用S={s1,s2,…,sn}表示,传感器节点的位置信息表示为(xi,yi),1≤i≤n。引入无向图G(V,E)的概念,将簇头节点存入V中,簇头节点之间的链路由E存储。每个簇都由不同数量的成员节点和一个簇头构成,成员节点与簇头之间可以进行信息交流。每个簇头节点与基站的最短路径,将簇头节点通过粒子群算法构建成链,相互之间以多跳网络的形式进行数据传输。网络模型如图1所示。

图1 网络模型

对系统模型有如下假设:

·所有的传感器节点都是同质的。

·所有的传感器节点具有相同的初始能量且能量受限制。

·基站能量不受限制。

·基站记录传感器节点的位置信息。

·所有节点都随机部署在目标区域内,可以与基站建立连接。

2.2 能量消耗模型

在WSN中,传感器节点的能量消耗主要集中在信息的感知、处理以及节点之间的通信(接收和转发数据)等方面,其中节点之间进行数据的传输是最耗费能量的过程,由于信息的感知和处理过程与路由无关,因此文中只考虑通信过程产生的能量消耗。

文中采用Heinzelman等[9]提出的能耗模型。根据发送节点与接收节点之间的距离,分别使用自由空间(Efs)模型和多路径衰落信道(Emp)模型对信道进行建模。如果发送节点与接收节点之间的距离小于阈值d0,则根据自由空间模型(d2功率能耗),计算能量消耗;否则,使用多路径衰落模型(d4功率损耗),计算能量消耗。由于在不同的信道模型中,传输相同大小的数据所消耗的能量不同,因此能量消耗取决于发送节点与接收节点之间的距离。传输kbits的数据所消耗的能量为式(1)所示

(1)

传感器节点接收kbits数据所消耗的能量为

ERx=Eelec×k

(2)

因此,传感器节点进行数据通信所需要消耗的总能量为

ETR=ETx+ERx

(3)

此外,还需要对簇头节点能耗进行计算。簇头节点的能耗来源于三部分:接收簇中成员节点的数据所消耗的能量ER＿ch,融合数据所消耗的能量EF＿ch以及将融合后的数据传输到基站所需消耗的能量ET＿ch。

簇头节点接受来自簇中成员节点的数据所需要消耗的能量为

ER＿ch=m×k×Eelec

(4)

其中m表示该轮进行数据传输的成员节点数量。

簇头节点需要融合的数据来源于两部分:一部分是成员节点传来的数据,另一部分是簇头节点本身收集到的数据,共有m+1个节点的数据需要融合。因此簇头节点融合数据所需要消耗的能量为

EF＿ch=(m+1)×k×EDA

(5)

其中EDA为融合1bit数据所需要消耗的能量。

簇头节点将融合后的数据传输到基站所需消耗的能量为

(6)

所以,可以得到簇头节点进行数据通信的总能耗为

Ech=ER＿ch+EF＿ch+ET＿ch

=k×(2m+1)×(Eelex+EDA)

(7)

3 基于FDPC-PSO的分簇路由算法

为了提高能源效率,延长WSN的使用寿命,本文提出了一种高效的FDPC-PSO路由算法。该算法与Leach算法具有相同的框架结构,分轮数进行,每轮分为三个阶段:基于FDPC聚类阶段,簇头选择阶段以及数据传输阶段。第一阶段通过FDPC算法优化网络部署,将传感器节点分为不同的簇,在网络中以集群的形式部署传感器节点。第二阶段为簇头选取阶段。从第二轮开始,每轮运行前BS更新每个簇中节点的剩余能量并将其发送给簇头节点。簇头节点计算本簇中剩余能量均值Eavg,并将此值设置为选取候选节点的能量阈值。然后,计算候选节点当选簇头所需的能量消耗,能量消耗最少者,当选此轮的簇头。第三阶段为稳态阶段。采用PSO算法优化传输路径,将所有CH连接到一个链中,建立到BS最短通信路径。该方法缩短了总传输距离,有效地减少了能量消耗。

3.1 基于FDPC聚类

FDPC聚类方法是由Wang[10]对DPC算法的改进。在DPC框架的基础上,采用模糊算子和正S型函数计算密度峰值。模糊密度峰值的使用改进了DPC在划分集群的模糊性和不确定性等方面的不足。FDPC算法进行聚类的关键是求出最优的聚类中心。聚类中心应该同时具备两个特点:在某一区域内该节点密度最大和与其它密度大的节点之间的距离相对更远。针对以上两个特点,式(8)、(9)定义了模糊密度ρi和距离δi两个量。通过FDPC算法聚类的具体步骤如下

输入:包含n个节点的矩阵X,参数ω,最近邻的数量k,高斯核宽σ以及阈值T

步骤1:计算每个节点的模糊密度ρi。模糊密度计算公式ρi为

ρi=f(ϖ(xi,x1))⊗f(ϖ(xi,x2))⊗…⊗f(ϖ(xi,xk))

(8)

(9)

其中⊗为模糊算子,f(x)是关于ϖ(xi,xj)的正双射隶属函数,反映节点xi和xj之间的相似性,表达式如式(10)所示

ER＿ch=m×k×Eelec

(10)

步骤2:根据式(11)计算出节点与比其密度大的节点之间的距离δi。

(11)

步骤3:根据式(12)、(13),选出聚类中心。

γi=ρi·δi

(12)

(γi-γi+1)>T

(13)

T为事先给定的阈值。将γi降序排列,γi的值越大,越适合当选簇头。式(13)确定簇头的个数p,从降序序列中选取前p个节点组成簇头向量C={c1,c2…,cp}。

步骤4:划分簇。

聚类中心选取后,基于距离因素划分簇。详细过程如下:将ρi(i=1,2,…n)降序排列,得到降序排列下标序列qi(i=1,2…n)。在模糊密度大于xi的节点中,最接近xi的节点的编号定义为nqi,用来定义非簇头节点的归类属性。

(14)

所有节点标签为li。当lqi=-1时,通过lqi=lnqi更新li。每个节点会得到一个新的标签,此标签值就是非簇头节点所在簇的序号。

(15)

3.2 簇头选取

完成聚类阶段后,得到了首轮运行的簇头节点,在首轮运行后,部分节点的剩余能量发生变化。为了避免某些节点的过度使用,造成能量消耗不均,需要在每一轮运行前,根据节点剩余能量和相对距离动态更新簇头。基站向每个簇头发送簇中所有节点的剩余能量,簇头通过式(16)计算出该簇剩余能量均值Eavg,并将其设定为该簇阈值,此后每一轮都将进行此操作,动态调整阈值。若节点的剩余能量高于该阈值,将此节点设定为候选簇头(CCH)。对候选簇头采用下列方法进行簇头的选取:该方法主要考虑距离因素对能耗的影响,该距离包括CCH与簇中成员节点之间的距离以及与BS之间的距离。通过式(17),基站计算每个候选节点若当选簇头后,进行数据传输所需要消耗的总能量。能量消耗最少者,当选此轮运行的簇头。在CH选择过程结束后,BS将更新网络中的传感器节点剩余能量。

(16)

×ERch(xi)+EtoBS(xi→BS)

(17)

其中:Etoch(xj→xi)表示传感器节点xj将数据包发送到CCH(xi)所需要消耗的能量。

ERch(xi)表示CCHxi从传感器节点xj接收数据包所消耗的能量。

EtoBS(xi→BS)表示CCHxi向基站(BS)发送聚合数据包时所消耗的能量。

3.3 PSO优化路径

针对数据传输线路的随意性,导致能量利用率低这一问题,将簇头节点与基站之间的数据传输规划为TSP问题,并采用全局搜索能量强的PSO方法优化传输路径。将所有的簇头节点连接成链,规划出所有簇头节点与基站进行数据通信的最短路径。

1)PSO算法优化原理

PSO算法是模拟鸟群的捕食行为而智能建立的群体优化算法。PSO算法的优化原理可总结为:在每次迭代过程中,每个粒子将自身的局部优解(pBest)发送个群体,群体根据所有的pBest获取动态的全局最优解(gBest),通过式(18)和(19),每个粒子根据gBest和pBest调整自身的速度v和位置,并更新自身的pBest,循环此过程,直到满足终止条件。

vi(t+1)=wvi+c1rand(pBest(t)-xi(t))

+c2rand(gBest(t)-xi(t))

(18)

xi(t+1)=xi(t)+vi(t+1)

(19)

其中,c1和c2为局部和全局加速系数,设置其值为c1=c2=1.5,rand为[0-1]之间的随机数,w为惯性因子,w∈[wmin,wmax],用于表示粒子的寻优能力,可由式(20)表示。

(20)

其中,iter为当前迭代次数,itermax为最大的迭代次数。

2)传输路径优化

在无向图G(V,E)中,V=(c1,c2,…,cp)为每轮运行前选取的CH,设置CH为TSP的问题规模,E={(a,b):a,b∈V}表示所有CH之间链路,CH到基站的路径作为优化目标。粒子群的规模设置为100,最高迭代次数为200次。CHi和基站之间的最短路径为piB。当所有粒子完成它们的遍历,达到收敛条件后,在“Routing[]”中记录了所有粒子的路径,计算所有路径的长度,然后输出每个粒子最短路径piB。

PSO优化的算法流程如下所示:

步骤1:设置TSP问题的城市规模,以及PSO算法所需的参数。

步骤2:初始化粒子的速度和位置。

步骤3:计算适应度函数值,即CH到基站的距离。

步骤4:根据粒子的适应度函数值更新pBest和gBest。

步骤5:根据式(13)、(14),更新粒子的位置和速度。

步骤6:更新迭代次数并记录粒子的路径Routing。

步骤7:判断是否满足迭代终止条件,若满足,则执行步骤7,否则,重复步骤2-步骤4步。

步骤8:输出最短路径piB。

4 仿真结果

在本节中,对提出的FDPC-PSO算法进行模拟,并通过仿真结果来评估所提算法的性能。仿真软件为python 2019,运行设备为Lenovo 小新Air-14,Intel Core i5 1.00GHz,win10,内存为16G。在模拟实验中,将200个传感器节点随机部署在100x100 m2区域的无线传感器网络中。BS被部署在WSN区域的中心位置(50,50)处,如图2。网络节点在初始参数方面是相同的。实验所需其它参数见表1。考虑五个参数对算法的性能进行评估,包括第一个死亡节点、百分之五十节点死亡、全部节点死亡、网络生存时间以及网络的剩余能量。

表1 无线传感器网络模拟参数

图2 节点部署

4.1 基于网络生存周期的比较

FDPC-PSO、EE-LEACH和ACO-K-MEANS三种算法在每轮运行后剩余存活的节点数量如图3。从结果可以观察到,FDPC-PSO具有最长的生存周期。同时,FPDC-PSO算法的曲线下降是最缓慢的,意味着FDPC-PSO可以更好的分配能量使用,保证能耗平衡,均衡网络负载,保证能源效率的最大化。

图3 每轮的存活节点数

图4 (a)第一个节点死亡(b)百分之五十节点死亡(c)最后一个节点死亡

4.2 基于死亡节点数的比较

FDPC-PSO,EE-LEACH以及ACO-K-MEANS三种算法分别在第一个节点、百分之五十节点以及全部节点死亡所运行的轮数如图3。 通过图可以看出,FDPC-PSO在前百分之五十节点死亡与后百分之五十节点死亡运行时间大致相同。相比另外两种算法,死亡节点比较缓慢,可以达到均衡使用能量。此外,该算法具有更久的生存周期。EE-LEACH中,最后一个节点死亡出现在第4038轮,ACO-K-MEANS出现在第4124轮,而在FDPC-PSO中最后一个节点死亡出现在第4781轮。相比EE-LEACH和ACO-K-MEANS,分别提高了18.4%和15.9%。

4.3 基于剩余能量的比较

随着轮数的运行,网络的剩余能量情况如图5。可以看出,FDPC-PSO算法每轮运行的能耗低于其它两种算法。该算法可以有效的节省能量,能量性能得到提高,并延长网络生存周期。

图5 网络剩余能量

5 结论

在本文,提出了一种基于FDPC和PSO的无线传感器网络聚类路由算法。该算法首先通过FDPC聚类算法将WSN中的传感器节点划分为簇,并在每轮运行前,基于动态能量阈值和最小化能耗两因素更新簇头。将数据传输通路扩展到求解TSP问题,并采用PSO算法来确定网络中的路由路径,优化传输路径,减少不必要的能量消耗。在实验过程中,对第一个节点死亡、百分之五十节点死亡、最后一个节点死亡、总剩余能量以及总运行轮数进行分析。仿真结果表明,与EE-LEACH和PSO-K-MEANS相比,所提出的FDPC-PSO算法可以从能源效率、网络寿命和能耗等方面提高网络性能。