基于改进的FCM聚类的WSNs协议*

邓 鹏， 苏 娟

(湖南大学 电气与信息工程学院，湖南 长沙 410082)

0 引 言

如何在无线传感器网络(wireless sensor networks,WSNs)工作过程中节省能源,最大化网络的生命周期,是WSNs重要的研究课题之一[1]。文献[2]提出一种能量均衡自适应分簇算法,将节点当前的能量作为重要考虑因素,对簇头进行自适应选择。文献[3]提出一种基于粒子群优化(particle swarm optimization,PSO) 的WSNs双簇头分簇算法,该算法将选择出的主副簇头分配不同的任务,使节点达到了能量负载均匀分布。但两文献均存在簇头随机分布、直接与基站通信,使簇头间的能耗分布不均等问题。

针对以上问题，本文利用模糊C均值(fuzzy—C means，FCM)聚类及WSNs双簇头分簇路由算法的优点,提出了基于遗传优化的FCM聚类分簇与最小树的WSNs路由协议(genetic optimization FCM clustering and minimum tree,GOFCMT)。通过遗传算法优化FCM使聚类算法跳出局部最优,更合理的生成簇类。采用簇内双簇头策略:主簇头接收融合簇内节点数据并发送给副簇头;副簇头接收主簇头数据并向基站发送数据,均衡簇头能耗,运用近优最小汇聚树算法生成副簇头与基站的通信路径,使得节点能耗更均衡、网络生命周期更长。

1 系统模型

假设N个传感器节点随机分布在M×M区域内,基站处于该区域之外,其他基本假设如下:1)基站位置信息已知；2)所有随机分布的节点皆为静态节点；3)每个节点有独立的ID号和相同的初始能量Eo；4)节点未配置GPS,但在网络初始化阶段,节点可以根据RSSI值计算自身与基站的距离；5)节点可以根据自身与基站的距离调整传输半径。

节点无线传输的能耗模型采用一阶无线电模型[4]，每k比特数据传输距离d所需要的能耗ETx(k,d)和接收该数据的能耗ERx(k)为

(1)

ERx(k)=kEel

(2)

2 GOFCMT

本文借鉴低功耗自适应集簇分层型协议(low-energy adaptive clustering hierarchy protocol，LEACH)的分层思想，同时针对LEACH存在随机选择簇头,簇头节点分布不均,造成簇内数据传输时能量利用效率低等缺点, 提出了GOFCMT。

2.1 遗传算法优化FCM聚类算法

利用遗传算法优化FCM,使FCM跳出局部最优[5]。遗传算法优化FCM聚类算法(genetic algorithm optimization FCM clustering algorithm，GAFCM)流程如图1。

图1 GAFCM流程

2.2 簇类的建立和数据传输

根据式(3)和式(4)在每个簇类里选择节点作为主副簇头:

1)选择主簇头:因为主簇头的任务是接收融合簇内普通节点发送的数据,所以需要考虑与簇内其他普通节点之间距离;同时也要考虑自身剩余的能量。

2)决定副簇头节点：主要考虑副簇头与基站的距离,以及副簇头自身的剩余能量[6]。文献[6]提出在选择主副簇头时的适应函数f1和f2如下

f1=αg1+βg2,f2=εg1+δg3，α+β=1,ε+δ=1

(3)

(4)

式中g1为节点ni的能量，使选择的主副簇头具有较多的能量,g2为簇内节点到主簇头节点平均距离的倒数，使主簇头到簇内节点之间的平均距离最小，m为簇内节点的个数，CH为主簇头;d(ni,CH)为节点ni到主簇头节点的距离，g3为副簇头节点到基站距离的倒数， 使副簇头到基站节点的距离最小BS为基站，d(ni,BS)为节点ni到基站节点的距离。通过α和β可以调节g1和g2两个因素在适应值函数f1中所占的比重,通过ε和δ可以调节g1和g3两个因素在适应值函数f2中所占的比重。

2.3 近优最小汇集树思想

选出的副簇头代表本簇类,簇类抽象为副簇头节点,将节点相连接,且节点间的能量花费作为边权重Cost(i,j),构造出一个具有权重的连通图,即G=(V,E),V为副簇头节点和基站集合,E为簇头间数据传输的权重Cost(i,j)。其计算如式(5)所示,其考虑了副簇头间的发送能量消耗、接收能量消耗、当前剩余能量以及簇头所代表的簇类规模大小,使得权重计算更加合理。

节点能否成为数据转发节点,则取决于其Cost(i,j)值，当Cost(i,j)值越大时,数据转发的概率越低[8]

(5)

式中d(i,j)为副簇头i和j之间的距离，ETx(l,d(i,j))为副簇头i向副簇头j发送数据消耗的能量，ERx为副簇头j接收副簇头i的数据消耗的能量，ec为副簇头当前剩余能量，a,b,c(a+b+c=1)为(0,1)之间的常量，用于调整右式中前后两项的权重，S为副簇头i所代表的聚类规模大小。

路由选择算法综合考虑了副簇头节点剩余能量、簇头节点之间以及簇头与基站之间的距离、簇的规模大小,使数据传输路径更加的合理,能量消耗更加均衡,提高了WSNs的健壮性,延长了网络生存周期。

3 仿真与性能评估

本文为了研究基站在相同的位置下LEACH、基于K-means聚类的能耗均衡路由算法(a balanced energy consumption routing algorithm based on K-means,KBECRA)和GOFCMT算法的性能差异,在MATLAB 2010b中进行了模拟,通过仿真网络的生命周期和能量消耗来验证改进的算法的网络性能。

在模拟参数设置为区域大小为200 m×200 m内，节点数为200个，汇聚节点Sink位置为(250 m，250 m),初始能量为0.5 J，数据包长度为4 000 bit，Eel为5×10-8J,ξfs为10-11J，ξmp为1.3×10-15J，每融合比特电路能耗EDA为5×10-9J，rc为25，d0为87 m[9]。权重参数取以下值：a=0.5,b=0.3,c=0.2,δ=0.6,ε=0.4,β=0.4,α=0.6。

3.1 GAFCM算法和FCM算法目标值对比

图2为2种算法在不同轮生成聚类的目标函数值J。可知，未优化的FCM算法的J值随着轮数的变化而变化,非常不稳定,使得FCM更容易收敛到局部最优解,所产生的聚类非最优,导致聚类的耗能未达到最佳,缩短网络的生命周期; GOFCMT算法的J值一直非常平稳,每轮均能到达最优目标值,当网络节点量大时GOFCMT优势更加明显，使得产生的聚类为最优,聚类的耗能达到最佳,延长网络的生命周期。

图2 2算法适应值对比

3.2 网络生命周期对比

图3为LEACH，KBECRA和GOFAR算法中WSNs生命周期对比。

图3 算法生命周期对比

可知GOFCMT的优势得到充分的体现,其首个节点死亡的时间和10 %的节点死亡的时间都远远迟于 LEACH和KBECRA,这是因为簇头和基站之间的通信距离加大,簇头单次的通信能量损耗也随之加大,而GOFCMT将通信能耗分散给最小树上的簇头,减少了由此产生的影响，另外,从第1个节点死亡到10 %节点死亡的时间跨度表明网络的能量使用高效。

3.3 能量消耗对比

图4 为GOFCMT，KBECRA和LEACH的能量消耗，可知, GOFCMT节省了网络中通信的能量消耗且使能量均匀消耗,和 KBECRA，LEACH相比,具有很明显的节能优势。

图4 算法能量消耗

4 结 论

本文提出GOFCMT,通过FCM聚类算法进行分簇,在簇内则根据不同的适应值选择主副簇头,簇间由近优最小汇聚树实现簇间多跳，较好地平衡了网络的能量负载,从而达到了延长网络生命周期的效果,仿真实验证明算法具有较好的性能,能达到预期效果。