基于果蠅優(yōu)化算法的最短路徑路由優(yōu)化

左岑

重慶電子工程職業(yè)學院,重慶401331

基于果蠅優(yōu)化算法的最短路徑路由優(yōu)化

左岑

重慶電子工程職業(yè)學院,重慶401331

針對傳統(tǒng)算法無法高效地解決網(wǎng)絡路由最優(yōu)化選擇的問題，將FOA算法引入最短路徑路由優(yōu)化問題，應用FOA算法的快速尋優(yōu)能力，在保證路徑最短和能耗最低的情況下，實現(xiàn)路由路徑的最優(yōu)化選擇。選擇死亡節(jié)點數(shù)目、網(wǎng)絡能耗和端到端時延三個指標作為路由優(yōu)化結(jié)果的評價指標，實驗結(jié)果表明，本文算法均優(yōu)于改進算法和經(jīng)典算法，效果較好，可以進一步進行推廣和應用。

果蠅優(yōu)化算法;最短路徑;路由算法;網(wǎng)絡模型

隨著計算機技術和網(wǎng)絡技術的發(fā)展，尤其是移動Adhoc網(wǎng)絡和Internet互聯(lián)網(wǎng)絡的極速發(fā)展，路由優(yōu)化成為通信網(wǎng)絡和計算機網(wǎng)絡領域的重要研究課題。由于其在多受限情況下是一個NP-C組合優(yōu)化問題，而最短路徑問題是路由優(yōu)化計算應用領域的熱點研究問題和重點問題，傳統(tǒng)方法如Floyd算法、Dijstra算法解決該問題雖然能夠在多項式時間內(nèi)較好地解決最短路徑問題，但是針對實時通信環(huán)境、QoS要求和高動態(tài)的拓撲結(jié)構的網(wǎng)絡要求下，需要同時找到一條最短路徑或次最短路徑當作路由方案的選擇和評價依據(jù)[1]。果蠅優(yōu)化算法[2]（Fruit Fly Optimization Algorithm，F(xiàn)OA）是模擬果蠅覓食所衍生出來的一種新的群智能算法。該算法目前已被應用于科學研究、工程應用以及數(shù)據(jù)挖掘和優(yōu)化領域。該算法相對于其他智能算法如遺傳算法、粒子群算法、蟻群算法和魚群算法等，具有控制參數(shù)少、收斂速度快和計算簡單的優(yōu)點。由于FOA算法提出的時間相對其他算法較晚，針對該算法的研究目前國內(nèi)外還處于初級階段，因此對其進行理論應用研究具有很高的價值。截止目前，F(xiàn)OA算法還未被應用于路由優(yōu)化研究，因此本文結(jié)合FOA算法的快速收斂能力用于求解最短路徑路由優(yōu)化問題具有重要的理論價值和現(xiàn)實意義。

1 果蠅優(yōu)化算法

與其他群智能算法一樣，F(xiàn)OA算法尋優(yōu)過程具有一定隨機性，其將味道濃度函數(shù)作為適應度判定函數(shù)，其算法流程如下[2]：

Step 1：對算法參數(shù)進行初始化，popsize代表的是果蠅的群體大小，Iteration代表的是最大迭代次數(shù)，果蠅初始位置為X_begin、Y_begin；

Step 2：依據(jù)公式（1）和（2），實現(xiàn)果蠅個體尋優(yōu)方向和距離的計算；

其中，xi和yi表示果蠅個體的位置，Value表示果蠅的搜索距離；

Step 3：計算果蠅個體的味道濃度，根據(jù)公式（3）和公式（4）計算果蠅個體距離原點的距離di，在此基礎上，計算果蠅個體的味道濃度；

Step 4：在味道濃度計算公式（4）的基礎上，依據(jù)公式（5）計算FOA算法的適應度函數(shù)；

Step 5：迭代尋找果蠅群體的最佳（適應度函數(shù)值）味道濃度值，用Smellb表示，以及其對應的最佳位置xb和yb；

Step 6：記錄并保留果蠅最佳位置和最佳味道濃度Smellbest=Smellb，令X_begin=xb，Y_begin=yb，向最優(yōu)適應度函數(shù)值所位于的方向搜索；

Step 7：重復Step 2-Step 5，假設計算得到的味道濃度比之前迭代的味道濃度高，就轉(zhuǎn)向step 6；反之，則返回Step 2-Step 5。

2 網(wǎng)絡模型

研究最短路徑路由問題，首先需構建出數(shù)學模型。為了便于問題的解決，通過構建出一個帶權值的圖表示路由網(wǎng)絡，其可以表示為G(N，E)，其中N表示路由網(wǎng)絡的節(jié)點，E表示路由網(wǎng)絡的鏈接邊，即通信鏈路。鏈路(i，j)的代價用Cij，代價矩陣用C=[Cij]，S，D分別表示源節(jié)點和目的節(jié)點，Iij表示每個鏈路的連接，定義如下[3]：

如果Iij=1，Ijk=1，則Iik=1，最短路徑問題可轉(zhuǎn)化為求最小值優(yōu)化問題，目標函數(shù)可表示如下：

其中，公式（9）主要保證源節(jié)點和目的節(jié)點之間的路徑達到最短[4]。

3 基于FOA算法的路由算法設計

3.1路由算法思想

由圖1可知，A節(jié)點向B節(jié)點發(fā)送數(shù)據(jù)，數(shù)據(jù)發(fā)送之后選擇最短路徑3、6、11，在長時間負荷工作之后，路由網(wǎng)絡會大量消耗整個網(wǎng)絡路徑C節(jié)點或D節(jié)點的能量。若此時C節(jié)點死亡，則鏈路3、5、6會受到極大影響；若此時D節(jié)點死亡，則鏈路6、10、11會受影響；上述情況的出現(xiàn)，導致網(wǎng)絡質(zhì)量的大幅度下降和網(wǎng)絡能耗的上升。假如C節(jié)點在能量比其他節(jié)點低的時候，選擇路徑1、4、8、10、11；假如D節(jié)點在能量比其他節(jié)點低的時候，選擇路徑1、3、5、9、12；當C節(jié)點和D節(jié)點能量均處于較低狀態(tài)時，選擇路徑1、2、7、12，此時C節(jié)點和D節(jié)點得到保護，那么A節(jié)點向B節(jié)點傳輸數(shù)據(jù)的壓力得到有效分擔。當其它節(jié)點能量較高時，C節(jié)點和D節(jié)點重新參與網(wǎng)絡工作。

圖1 路由結(jié)構示意圖Fig.1Theschematicstructureofrouter

3.2 FOA多路徑尋優(yōu)路由算法

根據(jù)上述路由算法，整個路由網(wǎng)絡的能量水平可由網(wǎng)絡中的節(jié)點剩余能量和網(wǎng)絡剩余能量比進行表征。在路由網(wǎng)絡中，由于鄰居節(jié)點是網(wǎng)絡數(shù)據(jù)的轉(zhuǎn)發(fā)對象，所以在進行路由網(wǎng)絡路徑的優(yōu)化時，需要考慮鄰居節(jié)點能量水平因素。網(wǎng)絡節(jié)點的剩余能量、鄰居節(jié)點的平均能量以及節(jié)點的平均剩余能量可分別由En、Enb和Eave進行表征。在此基礎上，單個節(jié)點能量f可由公式（10）進行表示[5]：

其中，α，β表示影響因子，由于優(yōu)先考慮節(jié)點剩余能量水平，那么0<β<α，將其倒數(shù)用來衡量能量平衡代價，可由公式（11）表示：

其中，fn(i=1，2，3，…，n)分別表示路由路徑中第i個節(jié)點的能量平衡函數(shù)值，fi表示能量平衡代價。已知En(i=1，2，3…，n)表示第i個節(jié)點的剩余能量，則能耗代價可由1/Ei進行表示。針對網(wǎng)絡路徑優(yōu)化，其能耗代價滿足如下條件[6]：

在能耗代價的基礎上，節(jié)點的能量平衡比如公式（13）所示：

節(jié)點能量安全平衡比Vsafe=e，0

3.3 適應度函數(shù)

針對路由路徑最短問題，結(jié)合公式（7）和公式（14），其適應度函數(shù)可由公式（15）表示：

3.4 路由算法流程

初始化時，隨機產(chǎn)生一定數(shù)量的種群，計算每個種群所對應的fitness，尋找種群中適應度fitness的最小值，然后根據(jù)FOA算法規(guī)則更新果蠅群體的速度和位置。當適應度最小時，其對應的最佳路徑作為優(yōu)化結(jié)果，其算法流程如下：

Step 1：初始化果蠅群體位置和算法參數(shù)；

Step 2：計算每個種群所對應的fitness，將個體歷史最優(yōu)值和群體歷史最優(yōu)值比較；若優(yōu)于個體或群體歷史最優(yōu)值，則保留當前值的位置，同時更新個體或群體歷史最優(yōu)值，反之，則保留上一個歷史最優(yōu)值；

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

Step 4：若Iteration

Step 5：當適應度最小時，其對應的最佳路徑作為優(yōu)化結(jié)果。

4 實驗分析

為了驗證本文算法的有效性和可靠性，分別將經(jīng)典路由算法[8]、改進算法[9]和本文算法進行對比。設定網(wǎng)絡覆蓋面積為200 m×200 m，在設定的區(qū)域面積內(nèi)隨機生成100個固定節(jié)點，數(shù)據(jù)包長度為80個字節(jié)，CBR數(shù)據(jù)信息源為50個，路由網(wǎng)絡中所有節(jié)點的初始能量等于5 J，網(wǎng)絡中簇樹參數(shù)Lm=3，Cm=Rm=4，節(jié)點數(shù)據(jù)發(fā)送功率等于0.6 w，數(shù)據(jù)接收功率等于0.3 w，模擬時間長度等于1200 s。本文所提出算法的參數(shù)為：ε=0.2，α=10，β=5，λ=1，μ=2，改進算法參數(shù)為：α=0.5，β=0.25，γ=0.1，μ=10，n=2，K=0.2。網(wǎng)絡節(jié)點分布如圖2所示，其中0節(jié)點為協(xié)調(diào)器節(jié)點。由圖3可知，隨著數(shù)據(jù)傳輸時間的推進，出現(xiàn)死亡節(jié)點的個數(shù)不斷增加，其中改進算法和本文算法出現(xiàn)死亡節(jié)點的數(shù)量均比經(jīng)典算法少，而本文算法出現(xiàn)死亡節(jié)點的數(shù)目又是低于改進算法的死亡節(jié)點數(shù)目。改進算法雖然可以保護能量偏低的節(jié)點和減少RREQ，但是此方法容易產(chǎn)生死亡節(jié)點，主要因為其路徑選擇的單一特性所致。在保證減少RREQ的條件下，本文提出的算法可以實現(xiàn)路由網(wǎng)絡路徑的動態(tài)選擇，在保證路徑最短的情況下，保證整個網(wǎng)絡負荷均衡化，推遲死亡節(jié)點出現(xiàn)的時間，提升整個網(wǎng)絡的生存壽命。

圖2 網(wǎng)絡節(jié)點圖Fig.2 Chart for the network nodes

圖3 死亡節(jié)點數(shù)目變化圖Fig.3 Chart for the number of death nodes

圖4 網(wǎng)絡消耗能量圖Fig.4 Chart for the network energy consumption

圖5 網(wǎng)絡時延圖Fig.5 Chart for the network delay

由圖4可知，隨著時間的推移，在起初的400 s內(nèi)，對于經(jīng)典算法，其網(wǎng)絡能耗急速增加，之后網(wǎng)絡能耗趨于平穩(wěn)，主要因為是死亡節(jié)點數(shù)量的增加所致。對于改進算法，其不僅可以實現(xiàn)網(wǎng)絡路徑的最優(yōu)選擇，同時可以最大程度地降低RREQ的泛洪，網(wǎng)絡能耗低于經(jīng)典算法。由圖3已知，本文算法的死亡節(jié)點數(shù)目最少，在此基礎上，整個網(wǎng)絡有更多固定節(jié)點參與網(wǎng)絡通信工作，此時整個網(wǎng)絡的工作效率最高，網(wǎng)絡能耗低于經(jīng)典算法和改進算法的網(wǎng)絡能耗，效果最好。由圖5可知，在起初的400 s內(nèi)，由于算法自身不存在相應的優(yōu)化機制，因此經(jīng)典算法的端到端時延較小，之后整個網(wǎng)絡中死亡節(jié)點數(shù)量隨著時間的增加而增加，導致其時延高于改進算法和本文算法。本文算法根據(jù)網(wǎng)絡能量和路徑的大小進行動態(tài)選擇，在保證均衡負載的情況下，實現(xiàn)路由的最優(yōu)化選擇。

5 結(jié)論

針對傳統(tǒng)算法無法高效地解決網(wǎng)絡路由最優(yōu)化選擇的問題，將FOA算法引入最短路徑路由優(yōu)化問題，應用FOA算法的快速尋優(yōu)能力，在保證路徑最短和能耗最低的情況下，實現(xiàn)路由路徑的最優(yōu)化選擇。實驗結(jié)果表明，本文算法在死亡節(jié)點數(shù)目、網(wǎng)絡能耗和端到端時延評價指標上，均優(yōu)于改進算法和經(jīng)典算法，效果較好，可以進行推廣應用。

[1]白樂強,孫晶晶,楊晰.基于鄰居表的ZigBee網(wǎng)絡樹路由改進算法[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路由算法的智能家居控制系統(tǒng)[J].電子器件,2016(1):199-204

[4]尹星,吳國新,董永強,等.基于擴展鄰居發(fā)現(xiàn)協(xié)議的嵌套移動網(wǎng)絡路由優(yōu)化方案[J].通信學報,2015,36(4):58-69

[5]那勇,田美燕,李燕,等.基于改進蟻群算法的無線傳感器網(wǎng)絡路由[J].激光雜志,2015(2):127-130

[6]余杰,李強,李莎莎,等.基于混合雙層模型的DHT網(wǎng)絡路由表快照算法[J].計算機科學,2015,42(1):11-16

[7]陶強,黃友銳,凌六一,等.基于改進蟻群算法的水下傳感器網(wǎng)絡路由策略[J].微電子學與計算機,2015,32(5):59-62

[8]馬學森,曹政,韓江洪,等.改進蟻群算法的無線傳感器網(wǎng)絡路由優(yōu)化與路徑恢復算法[J].電子測量與儀器學報,2015,29(9):1320-1327

[9]李蘭英,劉昌東.一種無線傳感器網(wǎng)絡路由協(xié)議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