基于果蝇优化算法的最短路径路由优化

左岑

重庆电子工程职业学院,重庆401331

基于果蝇优化算法的最短路径路由优化

左岑

重庆电子工程职业学院,重庆401331

针对传统算法无法高效地解决网络路由最优化选择的问题，将FOA算法引入最短路径路由优化问题，应用FOA算法的快速寻优能力，在保证路径最短和能耗最低的情况下，实现路由路径的最优化选择。选择死亡节点数目、网络能耗和端到端时延三个指标作为路由优化结果的评价指标，实验结果表明，本文算法均优于改进算法和经典算法，效果较好，可以进一步进行推广和应用。

果蝇优化算法;最短路径;路由算法;网络模型

随着计算机技术和网络技术的发展，尤其是移动Adhoc网络和Internet互联网络的极速发展，路由优化成为通信网络和计算机网络领域的重要研究课题。由于其在多受限情况下是一个NP-C组合优化问题，而最短路径问题是路由优化计算应用领域的热点研究问题和重点问题，传统方法如Floyd算法、Dijstra算法解决该问题虽然能够在多项式时间内较好地解决最短路径问题，但是针对实时通信环境、QoS要求和高动态的拓扑结构的网络要求下，需要同时找到一条最短路径或次最短路径当作路由方案的选择和评价依据[1]。果蝇优化算法[2]（Fruit Fly Optimization Algorithm，FOA）是模拟果蝇觅食所衍生出来的一种新的群智能算法。该算法目前已被应用于科学研究、工程应用以及数据挖掘和优化领域。该算法相对于其他智能算法如遗传算法、粒子群算法、蚁群算法和鱼群算法等，具有控制参数少、收敛速度快和计算简单的优点。由于FOA算法提出的时间相对其他算法较晚，针对该算法的研究目前国内外还处于初级阶段，因此对其进行理论应用研究具有很高的价值。截止目前，FOA算法还未被应用于路由优化研究，因此本文结合FOA算法的快速收敛能力用于求解最短路径路由优化问题具有重要的理论价值和现实意义。

1 果蝇优化算法

与其他群智能算法一样，FOA算法寻优过程具有一定随机性，其将味道浓度函数作为适应度判定函数，其算法流程如下[2]：

Step 1：对算法参数进行初始化，popsize代表的是果蝇的群体大小，Iteration代表的是最大迭代次数，果蝇初始位置为X_begin、Y_begin；

Step 2：依据公式（1）和（2），实现果蝇个体寻优方向和距离的计算；

其中，xi和yi表示果蝇个体的位置，Value表示果蝇的搜索距离；

Step 3：计算果蝇个体的味道浓度，根据公式（3）和公式（4）计算果蝇个体距离原点的距离di，在此基础上，计算果蝇个体的味道浓度；

Step 4：在味道浓度计算公式（4）的基础上，依据公式（5）计算FOA算法的适应度函数；

Step 5：迭代寻找果蝇群体的最佳（适应度函数值）味道浓度值，用Smellb表示，以及其对应的最佳位置xb和yb；

Step 6：记录并保留果蝇最佳位置和最佳味道浓度Smellbest=Smellb，令X_begin=xb，Y_begin=yb，向最优适应度函数值所位于的方向搜索；

Step 7：重复Step 2-Step 5，假设计算得到的味道浓度比之前迭代的味道浓度高，就转向step 6；反之，则返回Step 2-Step 5。

2 网络模型

研究最短路径路由问题，首先需构建出数学模型。为了便于问题的解决，通过构建出一个带权值的图表示路由网络，其可以表示为G(N，E)，其中N表示路由网络的节点，E表示路由网络的链接边，即通信链路。链路(i，j)的代价用Cij，代价矩阵用C=[Cij]，S，D分别表示源节点和目的节点，Iij表示每个链路的连接，定义如下[3]：

如果Iij=1，Ijk=1，则Iik=1，最短路径问题可转化为求最小值优化问题，目标函数可表示如下：

其中，公式（9）主要保证源节点和目的节点之间的路径达到最短[4]。

3 基于FOA算法的路由算法设计

3.1路由算法思想

由图1可知，A节点向B节点发送数据，数据发送之后选择最短路径3、6、11，在长时间负荷工作之后，路由网络会大量消耗整个网络路径C节点或D节点的能量。若此时C节点死亡，则链路3、5、6会受到极大影响；若此时D节点死亡，则链路6、10、11会受影响；上述情况的出现，导致网络质量的大幅度下降和网络能耗的上升。假如C节点在能量比其他节点低的时候，选择路径1、4、8、10、11；假如D节点在能量比其他节点低的时候，选择路径1、3、5、9、12；当C节点和D节点能量均处于较低状态时，选择路径1、2、7、12，此时C节点和D节点得到保护，那么A节点向B节点传输数据的压力得到有效分担。当其它节点能量较高时，C节点和D节点重新参与网络工作。

图1 路由结构示意图Fig.1Theschematicstructureofrouter

3.2 FOA多路径寻优路由算法

根据上述路由算法，整个路由网络的能量水平可由网络中的节点剩余能量和网络剩余能量比进行表征。在路由网络中，由于邻居节点是网络数据的转发对象，所以在进行路由网络路径的优化时，需要考虑邻居节点能量水平因素。网络节点的剩余能量、邻居节点的平均能量以及节点的平均剩余能量可分别由En、Enb和Eave进行表征。在此基础上，单个节点能量f可由公式（10）进行表示[5]：

其中，α，β表示影响因子，由于优先考虑节点剩余能量水平，那么0<β<α，将其倒数用来衡量能量平衡代价，可由公式（11）表示：

其中，fn(i=1，2，3，…，n)分别表示路由路径中第i个节点的能量平衡函数值，fi表示能量平衡代价。已知En(i=1，2，3…，n)表示第i个节点的剩余能量，则能耗代价可由1/Ei进行表示。针对网络路径优化，其能耗代价满足如下条件[6]：

在能耗代价的基础上，节点的能量平衡比如公式（13）所示：

节点能量安全平衡比Vsafe=e，0

3.3 适应度函数

针对路由路径最短问题，结合公式（7）和公式（14），其适应度函数可由公式（15）表示：

3.4 路由算法流程

初始化时，随机产生一定数量的种群，计算每个种群所对应的fitness，寻找种群中适应度fitness的最小值，然后根据FOA算法规则更新果蝇群体的速度和位置。当适应度最小时，其对应的最佳路径作为优化结果，其算法流程如下：

Step 1：初始化果蝇群体位置和算法参数；

Step 2：计算每个种群所对应的fitness，将个体历史最优值和群体历史最优值比较；若优于个体或群体历史最优值，则保留当前值的位置，同时更新个体或群体历史最优值，反之，则保留上一个历史最优值；

Step 3：更新果蝇位置和搜索方向；

Step 4：若Iteration

Step 5：当适应度最小时，其对应的最佳路径作为优化结果。

4 实验分析

为了验证本文算法的有效性和可靠性，分别将经典路由算法[8]、改进算法[9]和本文算法进行对比。设定网络覆盖面积为200 m×200 m，在设定的区域面积内随机生成100个固定节点，数据包长度为80个字节，CBR数据信息源为50个，路由网络中所有节点的初始能量等于5 J，网络中簇树参数Lm=3，Cm=Rm=4，节点数据发送功率等于0.6 w，数据接收功率等于0.3 w，模拟时间长度等于1200 s。本文所提出算法的参数为：ε=0.2，α=10，β=5，λ=1，μ=2，改进算法参数为：α=0.5，β=0.25，γ=0.1，μ=10，n=2，K=0.2。网络节点分布如图2所示，其中0节点为协调器节点。由图3可知，随着数据传输时间的推进，出现死亡节点的个数不断增加，其中改进算法和本文算法出现死亡节点的数量均比经典算法少，而本文算法出现死亡节点的数目又是低于改进算法的死亡节点数目。改进算法虽然可以保护能量偏低的节点和减少RREQ，但是此方法容易产生死亡节点，主要因为其路径选择的单一特性所致。在保证减少RREQ的条件下，本文提出的算法可以实现路由网络路径的动态选择，在保证路径最短的情况下，保证整个网络负荷均衡化，推迟死亡节点出现的时间，提升整个网络的生存寿命。

图2 网络节点图Fig.2 Chart for the network nodes

图3 死亡节点数目变化图Fig.3 Chart for the number of death nodes

图4 网络消耗能量图Fig.4 Chart for the network energy consumption

图5 网络时延图Fig.5 Chart for the network delay

由图4可知，随着时间的推移，在起初的400 s内，对于经典算法，其网络能耗急速增加，之后网络能耗趋于平稳，主要因为是死亡节点数量的增加所致。对于改进算法，其不仅可以实现网络路径的最优选择，同时可以最大程度地降低RREQ的泛洪，网络能耗低于经典算法。由图3已知，本文算法的死亡节点数目最少，在此基础上，整个网络有更多固定节点参与网络通信工作，此时整个网络的工作效率最高，网络能耗低于经典算法和改进算法的网络能耗，效果最好。由图5可知，在起初的400 s内，由于算法自身不存在相应的优化机制，因此经典算法的端到端时延较小，之后整个网络中死亡节点数量随着时间的增加而增加，导致其时延高于改进算法和本文算法。本文算法根据网络能量和路径的大小进行动态选择，在保证均衡负载的情况下，实现路由的最优化选择。

5 结论

针对传统算法无法高效地解决网络路由最优化选择的问题，将FOA算法引入最短路径路由优化问题，应用FOA算法的快速寻优能力，在保证路径最短和能耗最低的情况下，实现路由路径的最优化选择。实验结果表明，本文算法在死亡节点数目、网络能耗和端到端时延评价指标上，均优于改进算法和经典算法，效果较好，可以进行推广应用。

[1]白乐强,孙晶晶,杨晰.基于邻居表的ZigBee网络树路由改进算法[J].计算机工程与设计,2015(5):3204-3208

[2]Wen-Tsao Pan.A new fruit fly optimization algorithm:Taking the financial distress model as an example[J]. Knowledge-Based Systems,2012(26):69-74

[3]孙正凤,井娥林,窦如凤.基于改进ZigBee路由算法的智能家居控制系统[J].电子器件,2016(1):199-204

[4]尹星,吴国新,董永强,等.基于扩展邻居发现协议的嵌套移动网络路由优化方案[J].通信学报,2015,36(4):58-69

[5]那勇,田美燕,李燕,等.基于改进蚁群算法的无线传感器网络路由[J].激光杂志,2015(2):127-130

[6]余杰,李强,李莎莎,等.基于混合双层模型的DHT网络路由表快照算法[J].计算机科学,2015,42(1):11-16

[7]陶强,黄友锐,凌六一,等.基于改进蚁群算法的水下传感器网络路由策略[J].微电子学与计算机,2015,32(5):59-62

[8]马学森,曹政,韩江洪,等.改进蚁群算法的无线传感器网络路由优化与路径恢复算法[J].电子测量与仪器学报,2015,29(9):1320-1327

[9]李兰英,刘昌东.一种无线传感器网络路由协议LEACH的改进算法[J].哈尔滨理工大学学报,2015,20(2):75-79

The Route Optimization of the Shortest Path with Fruit Fly Optimization Algorithm

ZUO Cen
Chongqing College of Electronic Engineering,Chongqing 401331,China

For traditional algorithms cannot efficiently solve network routing optimization problem,the FOA algorithm is introduced into the shortest path routing optimization problem,FOA algorithm is applied to the rapid searching ability,in ensuring the shortest path and minimum energy consumption situation,the optimal routing path choice.Death number of nodes and the network energy consumption and the end to end delay three indicators as the routing optimization,the evaluation index selection.Experimental results show that the proposed algorithm is better than those of the improved algorithm and the classical algorithm,the effect is better,thus proving the validity and reliability of the algorithm for further promotion and application.

Fruit Fly OptimizationAlgorithm;Shortest Path;Router Algorithm;Network Model

TP391.1

A

1000-2324(2016)06-0932-04

2016-08-08

2016-09-28

左岑(1986-),女,实验师,本科,主要研究方向为软件工程、计算机技术.E-mail:cencen132456@163.com