一種基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略

屈 巍, 趙 晶, 洪 洋

(1. 沈陽師范大學 科信軟件學院, 沈陽 110034;2. 巴斯大學 科學學院, 巴斯 BA27AY)

?

一種基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略

屈 巍1, 趙 晶1, 洪 洋2

(1. 沈陽師范大學 科信軟件學院, 沈陽 110034;2. 巴斯大學 科學學院, 巴斯 BA27AY)

針對無線傳感器網(wǎng)絡中尋找最優(yōu)路徑的問題,考慮網(wǎng)絡的節(jié)能需求,提出了一種基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略。蟻群算法在進行過一段時間后,受轉(zhuǎn)移概率公式影響易于陷入局部最優(yōu)解,因此在提出的基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略中設計了動態(tài)狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則,合理的增加了新節(jié)點的搜索概率,從而達到快速有效的尋找全局最優(yōu)解的目的;此外,基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略設計了獎罰機制,進一步節(jié)省搜索時間的同時增加最優(yōu)路徑搜索概率,極大的延長了網(wǎng)絡生存時間。仿真實驗及分析表明,通過動態(tài)狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則及獎懲機制的動態(tài)調(diào)整極大的增加了全局最優(yōu)解的搜索概率,快速有效地實現(xiàn)了全局最優(yōu)解的獲得,節(jié)省了節(jié)點能量消耗,有利于延長網(wǎng)絡生存時間。

無線傳感器網(wǎng)絡; 蟻群算法; 狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則; 獎懲機制

0 引 言

無線傳感器網(wǎng)絡由大量具有感知能力、計算能力和通信能力的傳感器節(jié)點以自組織的方式構成,被廣泛的應用于軍事及民用領域[1-3]。由于一般工作在無人值守的監(jiān)控環(huán)境中,網(wǎng)絡節(jié)點電池更換成本較高,因此無線傳感器網(wǎng)絡的路由設計更多關注于節(jié)點能量消耗的最小化[4-9]。出于這些原因,節(jié)點在較短的時間內(nèi)找到最短的路徑進行通信不僅利于有效降低節(jié)點能耗、延長網(wǎng)絡生存時間,也大大提高了無線傳感器網(wǎng)絡的工作效率,這是目前傳感器網(wǎng)絡路由設計的一個重要研究方向。由Dorigo M等在1991年首次提出的蟻群算法成為解決此問題的一類典型研究方法,近年來受到廣泛研究[10-13]。蟻群算法就是模擬螞蟻群體覓食行為,后繼螞蟻通過判斷前繼螞蟻留下信息素濃度來選擇路徑。每只螞蟻根據(jù)自己周圍的局部環(huán)境做出反應并影響于自己周圍,單只螞蟻的行為是隨機的,但整個蟻群可以通過自組織過程形成高度有序的群體行為。相同路徑上走過的螞蟻越多,積累的信息量越大,該路徑就越容易被選擇;信息量會隨著走過時間而揮發(fā),走過的時間越久,信息量越小,被選擇的概率也就越小。基本蟻群算法就是基于這種自適應機制,使得蟻群算法不需要對所求問題的每一方面都詳細認知,而達到從無序到有序的演化。應用在無線傳感器網(wǎng)絡中,節(jié)點不需要對全局節(jié)點位置有全部的了解,只需要保存它附近的節(jié)點路由,就可以實現(xiàn)整個網(wǎng)絡的最佳路徑尋徑。這大大減少了節(jié)點的通信負擔,也節(jié)省了節(jié)點的能量消耗。但基本蟻群算法在實際應用中出現(xiàn)了收斂較快和易于陷入局部最優(yōu)解的問題,導致全局最優(yōu)解被忽視[14-15]。本文提出了一種基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略,通過動態(tài)狀態(tài)轉(zhuǎn)移規(guī)則的設計,合理的增加了新節(jié)點的搜索概率,快速的實現(xiàn)了全局最優(yōu)解的獲得;通過獎懲機制的合理設計,進一步節(jié)省了搜索時間的同時增加了最優(yōu)路徑搜索概率,極大的延長了網(wǎng)絡生存時間。

1 基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略

1.1 相關假設

傳感器網(wǎng)絡隨機部署于二維矩形平面內(nèi),使用全向天線,節(jié)點的通信半徑為Rc,節(jié)點感知半徑為Rs且Rc=2Rs,從而保證了網(wǎng)絡的連通性[16]。若節(jié)點i與節(jié)點j之間的歐式距離d(i,j)滿足d(i,j)≤Rc,則i和j互為鄰居節(jié)點,可進行直接通信。

1.2 狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則

1.2.1 蟻群優(yōu)化前期概率模型

(1)

(2)

其中: α為信息式因子, 反映螞蟻在運動過程中積累的信息素對于指導蟻群搜索過程中所占有的重要程度; β為期望啟發(fā)式因子, 反映在指導蟻群搜索過程中啟發(fā)式信息所占有的重要程度; ηik(t)為啟發(fā)函數(shù), dij表示2個鄰居節(jié)點之間的距離, 該啟發(fā)函數(shù)用于表示螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的期望程度。

為避免殘留信息素過多淹沒啟發(fā)信息的情況出現(xiàn),當m螞蟻完成對所有n個節(jié)點的遍歷后,需要對殘留信息進行更新。t+tn時刻在路徑(i,j)上的信息量調(diào)整如公式(3)所示。

(3)

其中:ρ為信息素揮發(fā)系數(shù), 1-ρ為信息素殘留因子,為防止信息無限積累,ρ的取值范圍為[0,1)。Δτij(t)為本次循環(huán)中路徑(i,j)上的信息素增量,初始時取為0即,Δτij(t)=0。Δτij,k(t)為第k只螞蟻在本次循環(huán)中t時刻殘留在路徑(i,j)上的信息量,則有

(4)

其中:Q為信息素強度;Lk為第k只螞蟻在本次循環(huán)中走過的所有路徑的長度和。

1.2.2 蟻群優(yōu)化后期概率調(diào)整規(guī)則

蟻群算法在進行過一段時間后,受轉(zhuǎn)移概率公式影響易于陷入局部最優(yōu)解。所以,在算法進行一段時間后,應該采取動態(tài)擴大轉(zhuǎn)移概率的方法,以便擴大搜索空間,增加找到更優(yōu)解的幾率。

狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則首先設計平衡參數(shù)q0,以此來平衡“探索”新路徑和“利用”己有信息之間的相對重要程度。當q>q0時進行新路徑的探索,當q

首先,算法開始運行時,主要以信息素作為選路參考。迭代NC次后,為了防止陷入局部最優(yōu)解,改變q0值,并設計隨機函數(shù)rad()產(chǎn)生一個隨機數(shù)滿足rand(min(pij)≤rad≤max(pij)),當pij≥rad時,節(jié)點i選擇下一跳節(jié)點j從而開辟新路徑,擴大搜索空間,防止算法陷入局部優(yōu)化。最后,主要以信息素為參考,再次改變q0值,直到運行結束。

接下來,在α和β方面,狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則設計了動態(tài)調(diào)整,可以有針對性的解決算法易陷入局部最優(yōu)解的問題。具體地,α反映螞蟻在運動過程中積累的信息素在指導蟻群搜索過程中的重要程度,α取值不易過大,否則容易導致局部正反饋作用較強,從而導致算法出現(xiàn)收斂過早的現(xiàn)象。

β則反映在指導蟻群搜索過程中的距離的重要程度。β值越大,螞蟻在局部點上選擇局部最短路徑的可能性越大,算法極易快速收斂于局部最優(yōu),換言之,極易陷入局部最優(yōu)。

所以,狀態(tài)轉(zhuǎn)移優(yōu)化規(guī)則設計了根據(jù)迭代所在的階段,動態(tài)調(diào)整α和β的機制,調(diào)整如下:

1) 依據(jù)迭代所在階段來初始化q0、α和β的值。并采用隨機函數(shù)rad()產(chǎn)生一個隨機數(shù)賦值給q,且滿足0≤q≤1,初始化模型如公式(5)所示。其中,N0為第一階段迭代次數(shù),N1為第二階段迭代次數(shù),Nc為當前迭代次數(shù),Nc_max為最大迭代次數(shù),U、U0、U1為時變q0的值。

(5)

2) 當q>q0時,節(jié)點i在待選節(jié)點集合j[]中隨機選擇下一跳節(jié)點,從而開辟新路徑,擴大搜索空間;否則,依據(jù)狀態(tài)轉(zhuǎn)移概率與下一跳由信息素濃度決定。狀態(tài)轉(zhuǎn)移概率調(diào)整模型如公式(6)。

(6)

式中Ln是節(jié)點n的鄰居節(jié)點數(shù)。

1.3 獎懲機制

蟻群算法在進行信息素更新時,走過的路徑上的信息素會得到一定程度的加強,同時信息素會隨著時間的推移不斷揮發(fā),因此蟻群算法容易受到早期發(fā)現(xiàn)解的影響而陷入局部最優(yōu)。考慮到以上問題,基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略設計了獎罰機制,獎勵與懲罰規(guī)則如下:

1) 當前迭代t=1時,信息素濃度正常更新,即節(jié)點間的Δτij(t)在原來基礎上進行獎勵,即:

(7)

2) 當前迭代t≥2時,記錄從開始到上一次為止所有迭代中最短路徑長度Lall_best,依據(jù)路徑長度對信息素濃度實施獎懲。如果當前螞蟻路徑長度Lnow≤Lave[NC](Lave[NC]為當前迭代所有路徑平均長度),則節(jié)點間的Δτij(t)按照公式(7)進行獎勵;如果當前螞蟻路徑長度Lnow>Lave[NC],則節(jié)點間的Δτij(t)在原來基礎上公式(8)進行懲罰;如果當前螞蟻路徑長度Lnow≤Lall_best,則節(jié)點間的Δτij(t)在原來基礎上按照公式(9)進行獎勵。

(8)

(9)

其中:L(ant)為當前螞蟻在一個迭代里走完的路徑總長;Ck為懲罰參數(shù);Cbest為獎勵參數(shù)。

1.4 蟻群優(yōu)化動態(tài)選擇策略實施步驟

Step 1 確定起始節(jié)點S(非信標節(jié)點),通過信標節(jié)點到未知節(jié)點的跳數(shù)矩陣找到距離未知節(jié)點S最近的一個信標節(jié)點D,記錄它們之間的跳數(shù)為S_hop,并將禁忌表Tabu[]中第一個節(jié)點賦值為S,Tabu[]記錄m只螞蟻按次序走過的節(jié)點編號。

Step2 NC初始值設置為1,并進行第NC次迭代。

Step 3 第m只螞蟻尋徑開始(m初始值設置為1),禁忌表目前已走過的跳數(shù)Tc初始設置為1。

Step4 螞蟻從節(jié)點S開始,將當前已訪問的節(jié)點放入visited[]中,且初始將visited[]置為目前Tabu[]中第m行1到Tc列的節(jié)點的下標。

Step 5 在S的可通信范圍內(nèi)的節(jié)點中,把與信標節(jié)點D之間的跳數(shù)小于S_hop的節(jié)點索引下標放入J_tmp[]中。

Step6 在J_tmp[]中選出與S跳數(shù)差值最大的節(jié)點索引,即最靠近信標節(jié)點D的節(jié)點索引下標放入j[]中,作為待跳節(jié)點的索引。

Step 7 進行蟻群優(yōu)化的后期概論模型調(diào)整,依據(jù)公式(5)判斷此時的迭代次數(shù)是處于初步、中間還是結束階段。依據(jù)所在階段來初始化q0,α和β的值。采用隨機函數(shù)rad()產(chǎn)生一個隨機數(shù)賦值給q,且滿足0≤q≤1。

Step8 當q>q0時,節(jié)點的狀態(tài)轉(zhuǎn)移概率p均一樣,即在j []中隨機選擇下一跳節(jié)點;否則,依據(jù)狀態(tài)轉(zhuǎn)移調(diào)整概率公式(6)進行,即下一跳由信息素濃度大小決定。選好的下一跳放入to_visit中,再將to_visit放入Tabu[]第m行的第Tc++列中。

Step 9 判斷to_visit是否為信標節(jié)點D。若不是,將to_visit置為S,回到步驟4;若是,將m+1置為m,回到步驟3。

Step10 所有螞蟻尋徑結束,算出每只螞蟻路徑總長L(ant)。

Step 11 記錄本次迭代的最佳路徑長度,放在L_best[]中。記錄本次最佳路徑,放在R_best[]中。記錄本次平均路徑長度,放在L_ave[]中。

Step12 重置本次迭代中的信息素變化矩陣Δτij(t)。

Step 13 在搜索過程中,將發(fā)現(xiàn)的路徑與本次迭代平均路徑長度和以往最優(yōu)解進行比較,如果優(yōu)于以往最優(yōu)解則分別進行不同的獎勵,否則進行一定的懲罰。判斷當NC=1時,信息素濃度按照公式(7)正常更新,在原先基礎上進行獎勵;否則,記錄從開始到上一次為止所有迭代中最短路徑長度Lall_best,依據(jù)路徑長度對信息素濃度實施獎懲。如果當前螞蟻路徑長度Lnow≤Lave[NC](Lave[NC]為當前迭代所有路徑平均長度),則節(jié)點間的Δτij(t)按照公式(7)進行獎勵;如果當前螞蟻路徑長度Lnow>Lave[NC],則節(jié)點間的Δτij(t)在原來基礎上按照公式(8)進行懲罰;如果當前螞蟻路徑長度Lnow≤Lall_best,則節(jié)點間的Δτij(t)在原來基礎上按照公式(9)進行獎勵。

Step14 依據(jù)信息素更新公式更新信息素矩陣Δτij(t)。

Step 15 禁忌表Tabu[]清零。將NC+1置為NC。

Step16 判斷NC是不是大于NC_max。若不是,回到步驟2;若是,迭代結束。

2 仿真實驗

2.1 實驗數(shù)據(jù)

采用MATLAB為仿真平臺,對所設計的蟻群優(yōu)化動態(tài)路由選擇策略下的節(jié)點路徑選擇性能進行驗證,仿真實驗中各參數(shù)取值如表1所示。

表1 參數(shù)設置

2.2 蟻群優(yōu)化動態(tài)選擇策略與原算法的仿真性能對比

仿真實驗中對于蟻群優(yōu)化動態(tài)選擇策略與原蟻群算法采用一致的節(jié)點分布、相同的起始源節(jié)點和終點信標節(jié)點。在相同的起始原點與終點信標之間進行路徑搜尋,進行了10次獨立的隨機拓撲實驗,分別考察了“最終最佳路徑長度”“NC次迭代最佳路徑平均長度”和“第一次找到最佳路徑的迭代次數(shù)”的性能,并針對性能展開重點分析。

表2 最終最佳路徑長度性能

表3 第一次找到最佳路徑的迭代次數(shù)性能

表4 NC次迭代最佳路徑平均長度性能

由表2可知,每次實驗采用蟻群優(yōu)化動態(tài)選擇策略獲得的最終最佳路徑長度都保持為49.471 3,而原蟻群算法獲得的最終最佳路徑長度波動較大,可見蟻群優(yōu)化動態(tài)選擇策略在最終最佳路徑長度方面獲得全局最優(yōu)解的性能較穩(wěn)定。

圖1 NC次迭代中最佳路徑平均長度與最終最佳路徑長度差別性能

由表3可知,原蟻群算法在10次隨機實驗下找到最優(yōu)路徑的最短迭代次數(shù)為10.3,蟻群優(yōu)化動態(tài)選擇策略則為3,可見蟻群優(yōu)化動態(tài)選擇策略可以在更短的迭代次數(shù)內(nèi)找到最優(yōu)解,極大地縮短了搜尋路徑的時間,從而有效地降低節(jié)點能耗,有利于延長網(wǎng)絡生存時間。

由表2及表4可知,2種算法在NC次迭代中最佳路徑平均長度與最終最佳路徑長度相比均有差距,從具體數(shù)值上進行比較,原蟻群算法獲得的差距較大,約為1.616 9,采用蟻群優(yōu)化動態(tài)選擇策略獲得的差距較微小,為0.211,性能比較具體如圖1所示,采用蟻群優(yōu)化動態(tài)選擇策略獲得的差距微小約為原蟻群算法下獲得差距的13%。

3 結 語

本文以避免陷入局部最優(yōu)解、加快搜索速度為優(yōu)化目標,研究了無線傳感器網(wǎng)絡中尋找最優(yōu)路徑的問題,提出了一種基于蟻群優(yōu)化的動態(tài)節(jié)能路由選擇策略,并對其進行了理論分析與實驗驗證。仿真實驗表明,該策略通過動態(tài)狀態(tài)轉(zhuǎn)移規(guī)則,有效的增加了新節(jié)點的搜索概率,實現(xiàn)了快速有效的尋找全局最優(yōu)解的目的;通過獎懲機制的設計,節(jié)省時間同時進一步增加了最優(yōu)路徑搜索概率,有效的降耗,延長了網(wǎng)絡的生存時間。

[ 1 ]QU Wei, LIN Hai, WANG Jinkuan. A dynamic energy-efficient routing scheme in Wireless Sensor Networks[J]. ICIC-EL ,2014,8(11):3113-3119.

[ 2 ]KARIMI M, NAJI H R. Optimize cluster-head selection in wireless sensor networks using genetic algorithm and harmony search algorithm[C]∥20th Iranian Conference on Electrical Engineering, 2012:706-710.

[ 3 ]張國印,唐濱,孫建國,等. 面向內(nèi)容中心網(wǎng)絡基于分布均勻度的蟻群路由策略[J]. 通信學報, 2015,36(6):1-12.

[ 4 ]曲大鵬,王興偉,黃敏. 移動對等網(wǎng)絡中的感知蟻群路由算法[J]. 計算機學報, 2013,36(7):1456-1464.

[ 5 ]AL-ALI R, RANA O, WALKER D W, et al. G-QoSM: grid service discovery using QoS properties[J]. China J Comput, Comput Inf, 2012,21(4):363-382.

[ 6 ]陳志泊,徐孝成. 一種改進的基于跳數(shù)的無線傳感器網(wǎng)絡路由算法[J]. 計算機科學, 2013,40(4):83-85.

[ 7 ]AMALDI E, CAPONE M, FILIPPINI I. Design of wireless sensor networks for mobile target detection[J]. IEEE/ACM Transactions on, 2012,20(3):784-797.

[ 8 ]KARABOGA D, OKDEM S, OZTURK C. Cluster based wireless sensor network routing using artificial bee colony algorithm[J]. Wireless Networks, 2012,18(7):847-860.

[ 9 ]OKDEM S, OZTURK C, KARABOGA D. A comparative study on differential evolution based routing implementations for wireless sensor networks[C]∥Innovations in Intelligent Systems and Applications(INISTA), 2012 International Symposium on, 2012:1-5.

[10]COLORNI A, DORIGO M, MANIEZZO V, et al. Distributed optimization by ant colonies[C]∥Proceedings of European Conference on Artificial Life,1991:134-142.

[11]梁華為,陳萬明,李帥,等. 一種無線傳感器網(wǎng)絡蟻群優(yōu)化路由算法[J]. 傳感技術學報, 2007,20(11):2450-2455.

[12]李領治,鄭洪源,丁秋林. 一種基于改進蟻群算法的選播路由算法[J]. 電子與信息學報, 2007,29(2): 340-344.

[13]朱思峰,劉方.柴爭義. 一種基于蟻群優(yōu)化的無線傳感器網(wǎng)絡路由算法[J]. 北京理工大學學報, 2010,30(11):1295-1300.

[14]楊新峰,劉克成. 基于改進蟻群算法的WSN路徑優(yōu)化[J]. 計算機與現(xiàn)代化, 2012,6(6):102-105.

[15]吳慶洪,張穎,馬宗民. 蟻群算法綜述[J]. 微計算機信息, 2011,27(3):1-5.

[16]屈巍,李喆. 無線傳感器網(wǎng)絡中一種分布式冗余檢測算法[J]. 小型微型計算機系統(tǒng), 2010,31(4):577-582.

A dynamic energy-saving routing strategy based on ant colony optimization in wireless sensor networks

QUWei1,ZHAOJing1,HONGYang2

(1. Software College, Shenyang Normal University, Shenyang 110034, China; 2. Department of Science, University of Bath, Bath BA27AY，The United Kingdom of Great Britain and Northern Ireland)

Focus on the problem of finding the optimal path in wireless sensor networks(WSN), and energy saving requirement, a dynamic energy-saving routing strategy based on ant colony optimization(ACO) was proposed . Because of being influenced by the transition probability formula，the algorithm of ACO is easy to fall into local optimal solution after running for a period of time. Thus, in this paper, our strategy designs the optimization rule of dynamic state transformation, which increases the search probability of the new node, so as to achieve the purpose of searching the global optimal solution quickly and effectively.In addition, our strategy introduces the mechanism of rewards and penalties, which further saves the search time and increase the probability of optimal path search, and prolongs the network survival time greatly. Simulation and theoretical analysis showed that the searching probability of a global for the optimal solution is increased by dynamic adjustment of the dynamic state transition rule and the mechanism of rewards and punishments, and the global optimal solution is obtained quickly and effectively. Furthermore the energy consumption of the nodes is saved, and will extend the lifetime of network greatly.

Wireless sensor networks(WSN); ant colony optimization(ACO); optimization rule of dynamic state transformation; the mechanism of rewards and penalties

2015-11-23。

國家自然科學基金資助項目(61403073)。

屈 巍(1982-),女,遼寧鐵嶺人,沈陽師范大學講師,博士。

1673-5862(2016)02-0234-06

TP393

A

10.3969/ j.issn.1673-5862.2016.02.022