WSN中基于梯度和粒子群优化算法的分级簇算法

阎新芳，严晶晶，冯　岩

(郑州大学 信息工程学院，河南 郑州 450001)



WSN中基于梯度和粒子群优化算法的分级簇算法

阎新芳，严晶晶，冯岩

(郑州大学 信息工程学院，河南 郑州 450001)

摘要：为均衡网络中节点的能量消耗，提出一种分级簇算法——GPHCA.该算法采用双簇头模式，利用粒子群优化算法搜寻能量大且到簇成员平均距离小的两个节点作为主簇头和副簇头，将簇头负担均衡到了两个节点上；在网关的选择上，同时考虑能量和转发路径的总距离，使最终选择的网关在能量和时延上得到均衡.仿真结果表明，GPHCA算法能有效延长网络的生命周期.

关键词：无线传感器网络；梯度；粒子群算法；GPHCA；双簇头

0引言

无线传感器网络中节点能量有限且不易补充[1]，所以降低网络能量消耗成为传感网路由协议的首要设计目标.相对于平面路由协议来说，分层路由协议有效节省了能量且可扩展性好[2-4].基于分级簇的拓扑结构作为分层路由的基础[5-7]，能有效减少网络的冗余信息，降低节点的能量负担，因此受到广泛关注.

文献[8-9]提出了一种基于梯度的分级簇算法(energy-aware topology control protocol based on gradient, ETBG)，建立了网络中节点到达基站的最小跳数，但是簇内紧凑性不够，且对网关节点能量考虑不足.文献[10]提出一种新的基于粒子群优化的双簇头分簇路由算法(a new dual-cluster heads clustering routing algorithm based on particle swarm optimization,DHCR)，利用粒子群算法(particle swarm optimization,PSO)进行簇头优化，但是采用随机的方式进行初始分簇，簇的可控性不高，其副簇头虽减轻了主簇头的负担，但效果不明显.因此，为均衡节点的能耗，笔者提出一种基于梯度和粒子群优化算法的分级簇算法(gradient and particle swarm optimization based hierarchical cluster algorithm, GPHCA)，并在簇内引入新的双簇头模式，从而提高网络生命周期.该算法采用分布式与集中式结合的方式，节点初步分簇后将信息发送至基站，在基站对簇头及路径进行优化，因此，优化部分并不消耗节点的能量.

1问题描述

笔者采用和文献[9]相同的网络模型和能量模型，节点的发射半径可调.由能耗公式可知，信息发送的能耗和距离呈指数关系，影响不可忽视.故在簇头优化阶段，需要解决的主要问题即是选择剩余能量大且相对处于簇中心的节点作为簇头，以减少簇成员发送信息的耗能.构建数学模型如下：

(1)

fCH-2=max{d(CH,ni)/R}.

(2)

fCH=αfCH-1+βfCH-2.

(3)

在簇间数据传输阶段要保证簇头的下一跳节点在有较多能量的同时还要处于合适的位置，故主要优化目标设定如下：

frout-1=Eaver/E(ni) .

(4)

frout-2=[d(CH,ni)+d(ni,BS)]/R0.

(5)

frout=αfrout-1+βfrout-2.

(6)

式中：K是簇内节点个数；E(CH)和E(ni)分别是簇头和节点i的剩余能量；d(CH,ni)和d(ni,BS)分别是节点i到簇头和基站的距离；R是节点的通信半径；R0是网络中心到基站的距离，引入目的是使fCH-1和fCH-2、frout-1和frout-2在同一数量级；Eaver是所有节点的平均剩余能量；α和β是权重，且α+β=1.fCH-1是能量因子，其值越小表示簇头剩余能量越大；fCH-2是距离因子，其值越小表示簇越紧凑.所以，fCH值越小，节点越适合做簇头.frout-1越小，簇头下一跳节点的剩余能量越大；frout-2越小，簇头经过下一跳节点到达基站的总距离越小，能耗也越小，所以frout值越小，节点越适合做网关.

2粒子群算法简介

粒子群优化算法[11-12]是一种基于群体智能的寻优算法.每一个粒子i都有一个速度vi和位置xi.对于需要优化的问题，定义一个适应度函数，粒子到达新的位置后计算当前的适应度函数值，并以此判断当前解的优劣.粒子跟踪个体极值pi和全局极值pg对其速度和位置进行更新，不断向最优解靠近，更新方式如下：

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

c2r2[pgj(t)-xij(t)].

(7)

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

(8)

式中：ω为惯性权重，代表对当前速度继承的多少；c1和c2为学习因子，分别表示粒子对个体和整个群体知识的认识；r1和r2为(0,1)的随机正数.

3基于PSO的分簇路由算法

3.1初步分簇

在分簇之前先按文献[9]的方式以基站为圆心根据节点通信半径将整个网络划分成一个梯度场，然后采用ETBG算法进行初步分簇并选举临时簇头，临时簇头将所有节点及分簇信息发送至基站.

3.2簇头优化

假设簇内有K个节点，x表示实际坐标.当粒子搜索完簇内所有节点或者达到最大迭代次数的时候算法收敛.具体步骤如下.

(1)初始化N个粒子，确定其位置x、速度v，并将其移动到距离最近的节点位置.

(2)每个粒子以公式(3)作为适应度函数，计算当前位置的适应度函数值，即将当前位置节点设为簇头时的fCH函数值，并将其和当前位置节点号保存在个体极值pi中，将所有个体极值中fCH函数值最小的存入全局极值pg，将fCH值第二小的存入全局次优值ps.

(3)按公式(7)、(8)更新粒子的速度v和位置x，然后计算每个粒子在新位置上的fCH值，并将其与pi比较，若优于pi，则将当前位置节点更新为pi.选出pi中的最优值，将其与全局极值pg和全局次优值ps比较，将最优的保存为pg，次优的保存为ps.

(4)判断是否达到收敛条件，如果没有则转到步骤(3).

(5)将最后输出的全局极值pg所在的节点设为当前簇的主簇头，全局次优值ps所在的节点设为副簇头，完成簇头优化.

3.3形成簇树

由于在数据传输阶段主副簇头是分开工作的，故需要两条路径来维持簇间信息的传输，路径选择的规则相同.在基站运行PSO算法，分别针对主副簇头按以下步骤形成簇树.

(1)将梯度为1的簇头和网关的下一跳节点直接设为BS，将其余簇头和网关邻居中梯度比其小的节点放入其nexthops集合作为搜寻范围，没有梯度比其小的则将同梯度邻居节点放入nexthops.

(2)将每个nexthops中能量最大的簇头设为下一跳节点；没有簇头的则以nexthops为搜索范围，以公式(6)为适应度函数，运行粒子群算法，具体规则同3.2，将输出的全局极值pg所在的节点设为下一跳节点即网关节点.

(3)查询是否所有的簇头和网关都有了确定的下一跳节点，如果是，算法结束，簇树形成；如果不是，跳回步骤(1).

簇树建立之后，基站保存全网的路由信息，然后将其广播给所有节点.收到信息后，主副簇头分别保存自己的成员节点和下一跳节点信息，为各成员节点分配TDMA传输时隙，而普通节点则只保存自己的主簇头、副簇头和TDMA时隙信息，避免存储资源浪费.

3.4数据传输方案

经过路由建立阶段，整个网络建立了主副两条路径，它们共同分担一轮的数据采集工作.在数据传输过程中，网络预先设定每轮的数据传输次数times和主簇头的工作比例coef.前coef*times次数据传输中，主簇头负责簇内信息的收集、融合和转发.然后，主簇头退化成普通节点，副簇头继任簇头完成剩余的数据传输.数据传输达到预设次数后该轮结束，网络将进行重新分簇开始下一轮.

4性能分析

假设在100 m×100 m的检测区域内随机抛洒100个节点，每个节点的通信半径R设为30 m，初始能量5 J，ω=0.9，c1=c2=2.

定义第一个节点死亡时采集的数据总轮数为网络的生命周期.假设times=1 000次，coef=0.6，β=0.6，从实验中随机选取30轮取均值，对GPHCA与ETBG和EBUCP 3种算法进行对比分析.

图1是节点密度N对3种算法生命周期的影响，GPHCA算法在节点密度水平处于中度水平时，优势很大.主要原因是节点密度适中时，GPHCA算法能更好的控制簇头能量和簇的紧凑性，有优化的网关，且用双簇头模式将簇头任务分配给了两个节点，故其生命周期明显优于另两个算法.节点密度过大时，前两种算法的簇规模增大，故簇头负担加大，而DHCR算法簇规模变化不大，故生命周期稳定但是都不长.

图1　不同N下的生命周期对比

图2是簇头采集一轮数据的平均能耗.DHCR算法的副簇头的作用相当于ETBG中的网关节点，故相比之下，GPHCA算法的双簇头模式更有效地分担了簇头负担.

图2　簇头采集一轮数据的平均能耗

图3是通信半径R对3种算法生命周期的影响.DHCR算法的通信半径仅用于使簇头分散开来，故其生命周期对R不敏感.当R较小时，GPHCA算法有效延长了网络的生命周期，但是当R较大时优势退化.主要原因是当R增加时，节点可以通信的邻居增多，簇的平均半径增大，簇头负担加重，主簇头任期未满就已死亡，故无法发挥双簇头模式的优势.因此，适当地降低节点的发射半径，采取多跳传输模式更有利于延长生命周期.

图3　不同R下的生命周期对比

GPHCA算法的效果受主簇头工作比例coef的影响，如图4所示.在coef=0.55时，生命周期达到最大，这主要是因为主簇头比副簇头有更好的综合适应度值，故其承担略多的任务时，更有利于延长整网的生命周期.

图4　coef对网络生命周期的影响

粒子群算法为随机初始化算法，其结果有一定波动性，对30次不同节点密度下的实验结果求方差，结果如表1所示.GPHCA算法针对单个簇进行单独优化且有副簇头辅助工作，故当某次PSO优化结果不理想时，影响被控制在半个times以内，所以生命周期的波动不超过500次.

表1　GPHCA算法生命周期的方差

5结论

提出了一种基于梯度和粒子群优化算法的分级簇算法，该算法利用适应度函数将剩余能量和节点到簇头以及基站的距离结合起来，通过粒子群的搜寻找出最佳的节点分任主副簇头和网关，通过适当调节节点的通信半径、主簇头工作比例和数据采集频次等参数，有效降低了簇头的平均能耗，优化了网关节点，均衡了节点能耗.在数据传输阶段，采用双簇头轮换的模式，一次分簇即可生成两条路径，在减小簇头节点负担的同时避免了频繁分簇带来的能量消耗，有效延长了网络的生命周期.

参考文献：

[1]AKKAYA K, YOUNIS M. A survey on routing protocols for wireless sensor networks [J]. Ad hoc networks, 2005, 3(3): 325-349.

[2]CHANG D, CHO K, CHOI N, et al. A probabilistic and opportunistic flooding algorithm in wireless sensor networks [J]. Computer communications, 2012, 35(4): 500-506.

[3]INTANAGONWIWAT C, GOVINDAN R, ESTRIN D, et al. Directed diffusion for wireless sensor networking[J].IEEE/ACM transactions on networking, 2003, 11(1): 2-16.

[4]KUILA P, JANA P. Energy efficient clustering and routing algorithms for wireless sensor networks: particle swarm optimization approach [J]. Engineering applications of artificial intelligence, 2014(33): 127- 140.

[5]WU Y,LIU W B.Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks [J]. IET wireless sensor systems,2013,3(2):112-118.

[6]阎新芳,张汉,李良,等. WSN中基于负载均衡的EAMCT-G 优化算法[J]. 天津大学学报, 2012, 45(8): 735-739.

[7]阎新芳,王晓晓,严晶晶,等. 基于Q学习的无线传感网分簇拓扑控制算法[J]. 郑州大学学报(工学版), 2015, 36(2): 85-88.

[8]阎新芳,段磊,李腾. 无线传感网中基于梯度的拓扑控制算法[J]. 计算机工程与应用, 2011, 47(2): 95-98.

[9]王志龙. 无线传感器网络中基于ETBG算法的分簇拓扑控制研究[D]. 郑州:郑州大学信息工程学院, 2011.5.

[10]解志斌,于谦,沈斌,等. 一种新的基于粒子群优化的双簇头分簇路由算法[J]. 传感技术学报, 2013, 26(8): 1135-1139.

[11]MA D X, MA J, XU P M. An adaptive assistant-aided clustering protocol for WSNs using Niching Particle Swarm Optimization [C]//Proceedings of the IEEE international conference on software engineering and service sciences. Washington: IEEE Computer Society, 2013: 648-651.

[12]KHALIL B, DRISS E. Particle swarm optimization based clustering in Wireless Sensor Networks: The effectiveness of distance altering [C]// Proceedings of 2012 international conference on complex systems. Washington: IEEE Computer Society, 2012: 1-4．

Gradient and Particle Swarm Optimization Based Hierarchical Cluster Algorithm in WSN

YAN Xinfang, YAN Jingjing, FENG Yan

(School of Information Engineering，Zhengzhou University，Zhengzhou 450001，China)

Abstract:A hierarchical clustering algorithm was proposed to balance the nodes’ energy consumption in the network. A mode of double cluster heads was adopted to select two cluster heads with sufficient remaining energy and small average distances to the cluster members using particle swarm optimization algorithm. The burden of one cluster head was shared by these two nodes. As for the gateways, the residual energy and the total distance of forwarding path was considered to make sure that the final chosen gateways get well balance between energy and delay.The simulation results show that the GPHCA algorithm can effectively prolong the network lifetime.

Key words:wireless sensor networks; gradient; particle swarm optimization; GPHCA; double cluster heads

中图分类号：TP393

文献标志码：A

doi:10.3969/j.issn.1671-6833.201505017

作者简介:阎新芳(1958—)，女，河南嵩县人，郑州大学教授，博士，主要从事无线传感网等方面研究，E-mail:iexfyan@zzu.edu.cn.

基金项目：河南省科技厅基础与前沿研究计划资助项目(152300410023)

收稿日期:2015-05-08；

修订日期：2015-11-05

文章编号:1671-6833(2016)02-0033-04

引用本文：阎新芳，严晶晶，冯岩.WSN中基于梯度和粒子群优化算法的分级簇算法[J].郑州大学学报(工学版)，2016，37(2)：33-36．