正六边形分区的混合差分进化萤火虫路由算法

刘宏，何鸿燊

（江西理工大学 电气工程与自动化学院，江西 赣州341000）

0 引言

无线传感器网络中使用合理的路由协议能够显著地均衡网络的能量负载，提升各个传感器节点的能量利用率，延迟节点死亡时刻进而使网络的整体存活周期得到延长。目前，群体智能算法在路由协议中应用广泛并且取得了很好的能耗优化效果。S-PSO将一种基于正弦调整的粒子群算法应用于路由协议中的簇头选举部分中，有效降低了能量的消耗速度，在一定程度上缓解和改善了“热点区域”的问题，但没有优化簇间传输部分；文献[3]提出一种基于人工蜂群算法的分簇路由协议，通过考虑剩余能量和节点位置筛选簇头节点，延长了网络寿命，保证了网络通信质量，但各簇头采用贪婪策略仅根据距离轮流选择离自己最近的簇内节点建立路由，导致簇间数据传输的能耗过大；NWOA-CT将一种非线性收敛因子的鲸鱼算法引入至协议，调节收缩概率，优化簇头选举步骤；文献[5]通过果蝇算法对簇头规划函数进行求解，找出最优分簇后在数据传输过程中应用贪婪算法，保证了簇头分布的合理性；文献[6]为了平衡粒子群算法的局部搜索能力和全局搜索能力，对算法的惯性系数和学习因子进行改进，找到最优分簇方案。

基于此设计一种正六边形分区的混合差分进化萤火虫路由算法（Hybrid Differential Evolutionary Firefly Routing Algorithm Based on Hexagonal Partition，HDEFA-HP）。算法首先对网络划分虚拟正六边形网格，在每个网格中分别遍历选出剩余能量最大的节点作备选簇头；引入混合差分进化萤火虫算法，对萤火虫算法引入差分进化算法中的变异和交叉操作，改善局部搜索能力、提高收敛速度，在备选簇头中考虑剩余能量、簇内位置和与Sink节点的距离三个因素，根据最优簇头数筛选最优的簇头集合；然后各节点利用非连续性CSMA协议广播ADV消息，普通节点根据间距和簇头剩余能量选择簇头节点入簇；在数据传输部分，簇头节点在本簇建立TDMA调度单跳收集簇内数据；最后综合考虑通信距离和剩余能量选择合理的中继节点进行簇间多跳传输。

1 模型与假设

对无线传感器网络做出如下5个假设：

1）网络中有个传感器随机散布在边长为的正方形监测区域里。

2）节点部署之后都是静止的，不随时间的变化而移动。

3）节点的初始能量相同，与此同时它们都具有唯一地址和ID。

4）节点都具有通信模块，可以和基站直接通信。

5）节点能量耗尽则死亡。

协议中选用一阶无线电能耗模型：多径衰减模型和自由空间模型对所消耗的能量进行计算，两种模型的选取方式依赖于发送节点和接收节点之间通信距离的大小，当通信距离小于阈值时使用自由空间模型，反之，则使用多径衰减模型计算。通信距离为，节点发送bit数据消费的能量具体描述如下：

节点接收bit数据消耗的能量为：

2 正六边形分区的混合差分进化萤火虫路由算法

2.1 簇头选举

2.1.1 初步网格划分

图1 虚拟网格划分

图2 节点坐标与网格编码

确定节点(,)处网格编码的伪代码描述如下：

输入：正六边形边长；节点坐标(,)

输出：节点(,)所在网格编码(,)

=3*2；=sqrt(3)2；=int()；=int()；=-(*)；=-(*)

if(+)%2==0

if+≤(-)+(-)

节点所在网格编码为(,)

else

节点所在网格编码为(+1,+1)

end if

else

if(-)+≤(-)+

节点所在网格编码为(+1,)

else

节点所在网格的编码为(,+1)

end if

end if

在每个网格内，以格内节点平均剩余能量作为能量阈值，将各个节点的剩余能量与能量阈值进行比较，选出剩余能量最大的节点标记为备选簇头；然后，在所有备选簇头集合中使用混合差分进化萤火虫算法进一步选择最优节点担任簇头。

2.1.2 参数初始化

首先应用文献[11]推导出最优簇头数目为：

式中：为Sink节点与最外层正六边形中心点的距离；为数据融合率（DAR），本文取0.5。

在备选簇头中生成初始种群，对每个备选簇头根据所属网格编码由内层向外层顺时针以自然数重新命名ID，最优簇头数作为萤火虫个体的维数，萤火虫个体定义为ID由小到大的排序。对应关系如表1所示。

表1 对应关系

2.1.3 混合差分进化萤火虫算法

萤火虫算法（Firefly Algorithm，FA）是亮度高的萤火虫自己进行随机移动，亮度低的萤火虫则朝着亮度最高的萤火虫位置进行移动的一种智能仿生算法，通过模仿萤火虫之间因个体的亮度而相互吸引，找出最优位置的个体。

该算法做出如下3个假设：

1）假定所有萤火虫都不分辨雌雄，都可以通过亮度吸引其他萤火虫；

2）随着萤火虫个体之间距离的增加，个体亮度和吸引度会逐渐降低，而亮度低的萤火虫受到亮度高的个体的招引而移动；

3）萤火虫的亮度定义为：I=(x)，其中，(x)为设计的目标函数。

萤火虫算法在搜索过程中的重要参数分别定义为：

萤火虫个体对相对的亮度表达式为：

式中：表示个体在=0处的亮度值；表示光吸系数。

r表示萤火虫，的间距，采用欧氏距离计算，表达式为：

式中：在维空间中第个萤火虫的位置为x=(x,x,…,x)，x表示个体的第个分量。

萤火虫之间的吸引度表达式为：

式中表示萤火虫之间最大相互吸引度。

萤火虫个体受亮度更大的个体吸引而进行的位置更新公式如下：

差分进化算法（Differential Evolution Algorithm，DE）包含四个步骤：初始化种群、变异、交叉和选择。

首先初始化种群个体，表达式为：

式中：=1,2,…,；rand[0,1]为0～1之间的随机数；和分别为第个分量的上限和下限。

rand/1：

best/1：

式中：，，分别为1～np之间不等于随机选择的整数；x为当前迭代次数下最好目标函数值对应的最佳个体向量；为（0，1]的缩放因子，通过实验，本文取=0.8。

式中：CR为交叉控制参数；为[1，]内的随机整数。

选择操作通过比较实验个体和目标个体的函数值，选择更优的个体作为新的个体向量：

由于变异算子和交叉算子的存在，将DE与FA混合可以使萤火虫算法具备摆脱局部最优的能力，提高种群多样性，避免过早收敛，获得较强的鲁棒性。引入变异算子和交叉算子的混合差分进化萤火虫算法（Hybrid Differential Evolutionary Firefly Algorithm，HDEFA）的描述如下：

1）在萤火虫算法运行之后，判断当前种群的平均亮度和最大亮度的差距= |-1|，本文设定精度=10；

3）当＜，此时搜索空间缩小，由best/1策略的差分进化算法改进萤火虫算法，此时位置更新的第三项可直接忽略，引入变异算子后新的位置更新公式如下：

4）进行交叉操作，确保在设定范围内得到实验个体；

5）进行选择操作，保留目标函数值更优的个体。

2.1.4 目标函数

簇头的选举应每次考虑节点的剩余能量、簇内密度以及与簇间位置三个重要因素，预定分簇个，设计目标函数如下：

1）节点剩余能量因子

式中：(CH)为待选簇头节点当前剩下的能量；为节点的初始能量。

2）簇内节点密度因子

式中：为节点与待选簇头监测半径内节点个数；|Cluster|为待选簇头本簇中节点个数。

3）簇间位置因子

式中(CH,Sink)为待选簇头到Sink节点之间的距离。

综上所述，目标函数的设计如下：

式中：，，为权重参数，满足++=1，权重参数的大小决定3个评价因子对簇头选举的影响程度，根据实际应用环境进行取值，本文，，分别取值为0.5，0.3，0.2。

由此得出基于混合差分进化萤火虫算法的簇头选举流程图如图3所示。

图3 簇头选举流程图

2.2 节点入簇

簇头节点采用非连续性CSMA协议广播ADV信息，ADV信息的内容有：簇头节点的ID编号、该簇头的剩余能量大小以及该簇头与Sink节点的间距大小。

入簇过程描述如下：

簇头首先向网络播送Head_Msg信息，如果普通节点只收到一条Head_Msg信息：此情况下，普通节点向此簇头节点回传含有自己序号的Join_OK(n)信息，加入收到广播的簇头所在簇；如果普通节点收到两条或两条以上Head_Msg信息：此情况下，节点通过比较距离和簇头剩余能量，如果簇头的距离相同，则选择剩余能量更大的进行入簇，向此簇头节点回传Join_OK(n)信息，并向其他簇头节点发送Ref_Msg消息拒绝入簇。

2.3 数据传输

在HDEFA-HP协议中，若簇头与Sink节点之间的距离小于或等于临界距离，簇头将数据直接传输给Sink节点；若簇头与Sink节点的距离大于，簇头则在里层的簇头中选取中继节点，将数据多跳传输给Sink节点。中继节点由式（20）设计的中继选举函数综合考虑与Sink节点的通信距离和剩余能量进行选择。

式中：(CH,CH)表示簇头到簇头的距离；(CH,Sink)表 示 簇 头到Sink节 点 的 距 离；(CH,Sink)表示簇头到Sink的距离；(CH)表示簇头的剩余能量；表示初始能量；可调节权重系数∈[0,1]。中继选举函数的值越小，表示该簇头节点更适合当选中继节点，本文设置的值为0.3。

3 仿真结果与分析

实验采用Matlab软件进行仿真，分别从存活节点数、能量消耗、接收数据包量三个方面对本协议进行评估，将本文的HDEFA-HP算法与文献[14]基于粒子群的分簇路由算法（PSO-ECHS）、文献[15]基于萤火虫算法的路由算法（FARW）进行对比。设置参数如表2所示。

表2 仿真参数设置

图4表示传感器网络初始化阶段，100个节点随机分布在边界为100 m的正方形区域内，Sink节点放置在中心位置，对区域进行六边形网格划分后，筛选出每个网格内剩余能量最大的节点作为备选簇头节点。

图4 正六边形网格初始化

图5表示三种协议在仿真中节点存活的状况，其中，PSO-ECHS算法由于在数据传输阶段未对LEACH算法做出改进，仍由簇头直接单跳传输数据至Sink节点，距离Sink节点远的节点能耗比距离近的更大，网络负载不均衡，所以最早出现死亡节点，在第725轮就开始出现第一个节点死亡的现象，到第1 261轮所有节点死亡完毕；文献[15]的FARW算法在选择簇头时未对分簇进行优化，数据传输阶段未考虑萤火虫算法的求解精度问题，出现死亡节点的轮数仅次于PSO-ECHS算法，在第825轮出现第一个节点死亡，到1 242轮所有节点死亡完毕；而HDEFA-HP算法经过975轮第一个节点开始死亡，直至1 422轮节点全部死亡。以所有节点死亡的轮数作为协议的生命周期，通过对比可知：HDEFA-HP协议较PSO-ECHS算法延长了约12.8%的生命周期；较FARW算法延长了约14.5%的生命周期。

图5 存活节点数

图6为仿真中全网剩余能量的状况。FARW算法能量消耗的最快，在1 242轮全网剩余能量被消耗至零；PSO-ECHS算法次之，在1 261轮耗尽全网能量；由于HDEFA-HP算法能够避免选择能量过低的节点作为簇头，进行高效率的簇内数据传输，在找出最优簇头后，根据与Sink节点的距离，综合考虑节点的距离指标与能量指标，选择合理的中继转发节点转发数据，建立传输路径，数据沿着适宜的路径进行簇间传输，防止能量产生不必要的损失，所以剩余能量下降较慢，直至1 422轮才耗尽全部能量。

图6 剩余能量

图7仿真了Sink节点接收数据包的情况。随着轮数的增加，由于PSO-ECHS算法对数据传输阶段未做出改进，HDEFA-HP算法在全部节点死亡之后所传输的数据包量约为PSO-ECHS算法的1.22倍，约为FARW算法的1.15倍。通过对比可知，由于HDEFA-HP算法在选举簇头环节时已经考虑了待选的簇头节点与Sink节点的距离，同时在数据传输部分综合考虑了路径中待选节点的剩余能量因素和距离因素，相比PSO-ECHS算法与FARW算法能够形成适宜的路径以传输数据包，避免了传输过程中数据包的丢失，所以在仿真结果中Sink节点接收到的数据包量最大。

图7 接收数据包量

4 结语

基于混合差分进化萤火虫路由算法，在簇头选举中首先划分网络，初步选出剩余能量高的节点作为备选簇头，通过衡量待选簇头节点的剩余能量、簇内节点密度以及与Sink节点的间距，选举出适宜的簇头节点，延长簇头节点的存活时间；综合考虑路径中待选节点的距离指标和能量指标，将合适的中继节点分配给距离Sink节点较远的簇头。实验结果表明，HDEFA-HP算法性能优于PSO-ECHS算法与FARW算法，在网络中较为准确地选举簇头，降低不适宜节点当选簇头导致的死亡率，延长了整体网络的运行时间，均衡了整体网络节点的能量损耗。