WSN中基于离散人工鱼群的分簇拓扑优化算法

阎新芳，张晓丹，严晶晶，冯 岩

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

WSN中基于离散人工鱼群的分簇拓扑优化算法

阎新芳，张晓丹，严晶晶，冯 岩

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

针对无线传感器网络中的HCAGG未综合考虑邻居节点的距离和能量分布，离簇首节点较远而能量较少的节点易成为盲节点的问题，提出一种分级簇算法.该算法引入新的综合权值计算方式，利用离散人工鱼群算法快速遍历到满足成员节点距其越远能量越多，反之越少的新簇头，降低了盲节点出现的概率.仿真结果表明，该算法有助于均衡节点能量，能有效延长网络生存期.

WSN；分簇拓扑优化；离散人工鱼群；HCAGG；均衡节点能量

0 引言

无线传感器网络(wireless sensor network, WSN)是由大量传感器节点通过自组织方式构成的无线网络.节点一次性播洒后，能量通常不可再生.因此，降低网络能量消耗，延长网络生存期，成为WSN路由协议的首要设计目标[1-2].分簇路由功耗低，易于维护扩展，已成为WSN路由协议的研究热点[3-4].而分簇拓扑结构[5-7]的设计是分簇路由的关键.在分簇拓扑结构设计中，簇头节点的选举对降低网络能量消耗，延长网络生存期起着至关重要的作用.

文献[8]提出一种基于梯度的有网关的分簇拓扑算法(hierarchical clustering algorithm based on gradient with gateway，HCAGG)，该算法引入剩余能量和到邻居节点的平均距离构造权值并引入自适应系数动态调节二者所占比重.但是未考虑邻居节点能量与到簇头节点距离的关系，使簇内远离簇头节点而能量较低的邻居节点能量过早耗尽而成为盲节点.文献[9]提出一种粒子群优化的无线传感器网络协议，该协议综合考虑了节点的剩余能量以及邻居节点的距离和能量分布问题，并利用粒子群算法的思想快速寻优，具有一定均衡簇内能量消耗，延长网络生存期的作用.但是该协议选举出的簇头节点更侧重于邻居节点距离和能量分布，节点本身剩余能量对簇头选举的影响不大.而簇头节点的能量消耗最大，簇头节点有可能成为新的盲节点.

因此，为更好地均衡簇内节点能量消耗，笔者提出一种基于离散人工鱼群的分簇拓扑优化算法(hierarchical clustering topology optimization based on discrete artificial fish swarm，HCTO-DAFS).该算法采用分布式与集中式相结合的方式，按照HCAGG算法初步分簇后，临时簇头将节点及分簇信息发送至基站，由基站利用离散人工鱼群优化(discrete artificial fish swarm optimization,DAFSO)算法对簇头进行优化.

1 模型建立和问题描述

笔者采用和文献[8]相同的网络模型和能量模型来计算节点能耗.由能量模型可知：邻居节点发送信息的能耗与距离呈指数关系，而簇头节点负责接收邻居节点信息并将融合后的信息以一跳或多跳的形式传递给基站，能量消耗较大，故在簇头优化阶段，簇头节点的选举要兼顾节点剩余能量和邻居节点能量分布问题，使选出的簇头节点具有较多的剩余能量，同时满足距其越远的邻居节点具有较多的能量，反之较少.因此，结合剩余能量定义一种新节点坐标X1i(eixi，eiyi)，新节点坐标使节点的能量、距离信息一体化.对综合权值构建数学模型如下：

(1)

其中，

(2)

(3)

式中：E0为传感器节点的初始能量；ei为第r轮的剩余能量；m为传感器节点Xi的邻居节点个数；a、b为动态权系数，a在区间(0.5，1)之间单调递增，随着信息采集轮数的增加，剩余能量在簇头选举中占的比重越来越大.

同时为保证网络的连通性，候选簇头节点满足与簇内其他任一成员节点的距离小于通信半径R,即若Xi(xi，yi)为候选簇头，Xj(xj,yj)为Xi的邻居节点，则

|Xi-Xj|

(4)

2 AFSO算法概述

2.1 AFSO算法基本思想

在一片水域中，鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方.在迭代过程中,鱼群通过与周围环境进行信息交互选择觅食、群聚、追尾、随机某一种行为不断调整自己的位置，从而逐渐聚集到极值点的周围[10-11].全局最优的极值点有两种表现形式：①全局最优的极值点周围通常聚集较多的人工鱼；②在寻优过程中，跟踪记录当前最优个体的状态，以公告的形式不断更新全局最优解.

2.2 人工鱼行为描述

设人工鱼位置为Xi，人工鱼所在位置的食物浓度(即所求问题的适应度函数值)表示为Yi=f(Xi),visual表示人工鱼的感知距离，δ为拥挤度因子，n为人工鱼Xi邻域内的伙伴数.

1)觅食行为.设当前人工鱼为Xi，在其感知范围内随机选择另一人工鱼Xj，若Yi

2)群聚行为.设当前人工鱼为Xi，探索当前邻域内伙伴的中心位置Xc，如果Yc >δ·Yi,表明Xc处有较多的食物并且不太拥挤，则朝伙伴Xc方向前进一步，否则执行觅食行为.

3)追尾行为.设当前人工鱼为Xi，探索当前邻域内伙伴中Yj最大的伙伴为Xj，若Yj >δ·Yi，表明Xj处具有较高的食物浓度并且不太拥挤，则向Xj方向移动一步，否则执行觅食行为.

4)随机行为.在视野范围内随机选择一个状态向该方向移动.

人工鱼Xi根据周围环境，选择执行觅食、群聚、追尾、随机某一行为，并对位置进行更新，不断向最优解靠近，更新方式如下：

Xi(t+1)=Xi(t)+r[Xj(t)-Xi(t)]，

(5)

式中：r为(0,1)的随机数.

3 基于DAFS的分簇拓扑优化

3.1 算法描述

基于DAFS的分簇拓扑优化算法在HCAGG分簇的基础上，利用DAFSO算法综合邻居节点的距离和能量信息优化选择簇首，最后获得最新分簇.

1)簇的初步形成阶段.此阶段按照HCAGG算法初步分簇并选举临时簇头.所有节点及分簇信息通过临时簇头发送给基站.

2)利用DAFSO算法优化簇首阶段.由于传感器节点的分布是离散的，人工鱼的位置信息无法一一映射到传感器节点上，因此提出一种离散人工鱼群算法，具体定义如下：

设某一区域内有M个传感器节点，定义节点状态信息：1代表节点已经被人工鱼探索过；0代表节点未被探索过.随机抛洒N(N≤M)条人工鱼，定义人工鱼的位置为距离自己最近且未被探索过的节点的坐标,从而实现人工鱼与离散节点的一一对应.如果所有节点均被探索过或达到最大迭代次数，则搜索结束，具体步骤如下：

①初始化N条人工鱼，确定其位置,并将其移动到最近且未被探索过的节点位置.

②每条人工鱼按照式(1)计算其适应度函数.

③人工鱼根据周围环境信息选择执行觅食、追尾、群聚、随机某一行为，并按式(5)更新人工鱼位置信息.算法设置一个公告板，每条人工鱼执行完某一行为后与当前公告板上最优的食物浓度值进行比较，如果优于公告板上的食物浓度值，则在公告板上更新当前最优的食物浓度值及当前最优节点.

④判断是否达到搜索结束条件，如果没有，则转至步骤3)，否则搜索结束，执行步骤5).

⑤将搜索结束后公告板上节点设为簇头，完成簇头优化.

3)簇树形成阶段.参照HCAGG生成簇树的方法，建立一个基于梯度的带有网关的多级簇树.

3.2 特例分析

假设在100 m×100 m的二维坐标平面内随机抛洒20个节点，基站位置在(50,0)，节点初始能量为0.5 J,通信半径R=40 m，visual=20，δ=0.618.随机运行10次，取一次做特例分析.

如图1(a)为HCAGG的分簇效果图，图1(b)为采用本文算法优化后的分簇效果图.其中方节点表示簇头节点，圆节点代表簇成员节点.

图1 算法改进前后的分簇对比图Fig. 1 Comparison chart before and after algorithm optimization

如图1(a)所示，部分距离簇头节点较远的成员节点能量较小，这些节点易因为能量过早耗尽而成为盲节点.例如簇头节点5所在簇中，簇成员节点13易成为盲节点.经过优化后，如图(b)所示，重新选择20号节点作为簇头节点.图(b)与图(a)对比可以看出：图(b)产生的簇头节点满足离簇头节点较近的邻居节点能量较小，离簇头节点较远的邻居节点能量较大，簇内能耗比较均衡.

4 性能分析

定义从算法开始运行到第一个节点死亡时所采集的数据总轮数为网络生存期.

4.1 通信半径对生存期的影响

在簇头轮换频率为1 000轮/次的情况下进行仿真.已知当前网络连通所需的最小通信半径Rmin=35 m,在通信半径为35～70 m区间每隔5 m取一个点，每个点取10次仿真的平均值.则在不同通信半径下，优化算法HCTO-DAFS、HCAGG和文献[9]中提出的PSO算法的生存期，如图2所示.

图2 通信半径对网络生存期的影响Fig.2 The effection of communication radius to lifetime

由图2可以看出，3种算法的生存期都是随着通信半径的增大而减小，这是因为随着R的增大，节点间进行信息交互的能耗增加,同时簇成员节点数增加，簇头节点负担加大.由此可知，在保持网络连通情况下，减小节点发射半径可以延长网络的生存期.但在通信半径相同时，优化算法由于更好地均衡了簇内能耗，故生存期明显优于另两种算法.

4.2 簇头轮换频率对生存期的影响

在通信半径设为40 m时，加入簇头轮换策略对算法进行仿真.每个点取10次仿真平均值.则不同簇头轮换频率下，HCTO-DAFS算法、HCAGG和文献[9]中提出的PSO算法的生存期如图3所示.

图3 簇头轮换频率对网络生存期的影响 Fig. 3 The effection of rotation frequency of cluster head on lifetime

由图3可以看出，3种算法的生存期都随着簇头轮换频率呈现先增加后减小的趋势.因此，合理设置簇头节点轮换频率可以延长网络生存期.而在簇头轮换频率相同时，当簇头轮换频率小于4 000轮/次时，优化算法HCTO-DAFS更好地均衡了网络能耗，优化后的生存期较另两种算法有明显的优势.但是当簇头轮换频率大于4 000轮/次时，优化算法HCTO-DAFS均衡簇内能量消耗效果不明显且簇头负担过重容易成为新的盲节点,相比之下PSO算法具有一定的优势.

5 结论

笔者提出了一种基于离散人工鱼群的WSN分簇拓扑优化算法，该算法在HCAGG算法的基础上提出一种充分考虑簇内邻居节点的能量和距离信息的新的综合权值计算方法，使新选出的簇头节点满足邻居节点距其越远能量越多，反之则能量少，这样使簇内能量消耗更加均衡.同时把基本人工鱼群优化算法改造成适合WSN特点的DAFSO算法，采用分布式与集中式相结合的方式并利用DAFSO思想直接由基站获取最优簇头节点，实现了无线传感器网络的分簇优化，从而有效延长了WSN的生存期.

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

[2] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks: a survey[J]. IEEE wireless communication, 2004, 11(6): 6-28.

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

[4] MAMMU A S K, SHARMA A, HERNANDEZ U, et al. A novel cluster-based energy efficient routing in wireless sensor networks[C]//Proceeding of 27th IEEE international conference on advanced information networking and application. Barcelona: IEEE conference, 2013: 41-47.

[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] AN N, YAN X F, ZHU Y F, et al. A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks[C] ∥Proceeding of IET international communication conference on wireless mobile and sensor networks. Shanghai: IET conference, 2007: 462-465.

[8] 古晓辉.无线传感器网络基于梯度的分级簇算法研究[D]. 郑州: 郑州大学信息工程学院, 2013.

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

[10]ZHOU Y, LIU B. Two novel swarm intelligence clustering analysis methods[C]∥Proceeding of The fifth international conference on natural computation. Tianjin: IEEE conference, 2009: 497-501.

[11]李晓磊.一种新型的智能优化方法—人工鱼群算法[D].浙江: 浙江大学信息科学与工程学院, 2003.

A Hierarchical Clustering Topology Optimization Algorithm Based on DAFS in WSN

YAN Xinfang, ZHANG Xiaodan, YAN Jingjing, FENG Yan

(School of Information and Engineering, Zhengzhou University, Zhengzhou 450001, China)

To solve the problem in HCAGG that the nodes far away from the cluster head had less energy, and were are prone to be blind nodes, a Hierarchical Clustering Topology Optimization based on Discrete Artificial Fish Swarm (HCTO-DAFS) was proposed. The HCTO-DAFS introduced a new comprehensive weights and acquired the new cluster heads.The member nodes would have more energy when they were away from the cluster head. The DAFS could reduce the probability of blind nodes.Simulation experiments demonstrated that this algorithm could efficiently balance the nodes’ energy and prolong the network’s lifetime.

WSN; DAFS; hierarchical clustering topology optimization; HCAGG; balance the nodes’ energy

2016-11-30；

2016-12-25

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

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

1671-6833(2017)04-0069-04

TP393

A

10.13705/j.issn.1671-6833.2017.01.020