左岑

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

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

左岑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 網(wǎng)絡(luò)模型

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

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

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

3 基于FOA算法的路由算法設(shè)計(jì)

3.1路由算法思想

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

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

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

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

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

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

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

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

3.3 適應(yīng)度函數(shù)

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

3.4 路由算法流程

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

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

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

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

Step 4：若Iteration

Step 5：當(dāng)適應(yīng)度最小時(shí)，其對(duì)應(yīng)的最佳路徑作為優(yōu)化結(jié)果。

4 實(shí)驗(yàn)分析

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

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

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

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

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

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

5 結(jié)論

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

[1]白樂強(qiáng),孫晶晶,楊晰.基于鄰居表的ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法[J].計(jì)算機(jī)工程與設(shè)計(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]孫正鳳,井娥林,竇如鳳.基于改進(jìn)ZigBee路由算法的智能家居控制系統(tǒng)[J].電子器件,2016(1):199-204

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

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

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

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

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

[9]李蘭英,劉昌東.一種無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的改進(jìn)算法[J].哈爾濱理工大學(xué)學(xué)報(bào),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-),女,實(shí)驗(yàn)師,本科,主要研究方向?yàn)檐浖こ?、?jì)算機(jī)技術(shù).E-mail:cencen132456@163.com