王勇智,范 欽,戴 華,李武勁

(湖南理工學院 信息科學與工程學院,湖南 岳陽 414006)

0 引言

1 基于鯨魚優(yōu)化的多路徑路由發(fā)現(xiàn)算法

1.1 網(wǎng)絡模型

用無向加權連通圖G=(V,E)表示網(wǎng)絡,其中V為網(wǎng)絡中節(jié)點的集合,E為網(wǎng)絡中節(jié)點之間的網(wǎng)絡鏈路的集合,v∈V表示圖中的節(jié)點,e=(i,j)∈E表示節(jié)點vi與vj之間的有效鏈路.定義Psd為源節(jié)點vs∈V到目標節(jié)點vd∈{V-{vs}}之間的有效路徑的集合,pi∈Psd是該路徑集合中的第i條有效路徑.假定候選有效路徑數(shù)目為N,則有Psd={p1,p2,p3,…,pN}.

1.2 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法(WOA)是Mirjalili和Lewis在2016年提出的一種元啟發(fā)優(yōu)化算法,該算法基于座頭鯨的狩獵行為,將優(yōu)化求解的問題劃分為泡泡網(wǎng)攻擊(Bubble-net attacking)以及搜索獵物(Searching for prey)兩個過程[1].每只鯨魚的位置代表一個可行解,在D維解空間中其位置為Xsd=(x1,x2,x3,…,xD),其中xj∈Xsd表示源節(jié)點到目標節(jié)點的一條有效路徑.結(jié)合傳統(tǒng)WOA算法,移動自組網(wǎng)絡的多路徑路由發(fā)現(xiàn)優(yōu)化模型由泡泡網(wǎng)攻擊與搜索獵物兩個子模型組成.

(1) 泡泡網(wǎng)攻擊

收縮包圍機制:在鯨魚優(yōu)化算法中,所有鯨魚根據(jù)獵物的位置更新自己的位置:

其中t表示當前路由發(fā)現(xiàn)的迭代,→表示當前迭代的位置向量,而表示截至當前迭代的局部最優(yōu)解.和是系數(shù)向量,且

其中隨著迭代過程的推進由2遞減到0,和為[0,1]上的隨機向量.通過降低式(3)中的值,可實現(xiàn)收縮包圍的行為.假設為[-1,1]上的隨機向量,則可定義當前鯨魚的新位置為其原始位置與獵物位置之間的任意位置.

目前，關于測繪監(jiān)理的國家統(tǒng)一法規(guī)、技術規(guī)范還未出臺，各省還是在執(zhí)行各自的測繪監(jiān)理管理辦法，工作的重心通常還是聚焦在測繪成果質(zhì)量檢查環(huán)節(jié)，尚不能對質(zhì)量管理、進度控制、工程組織協(xié)調(diào)等進行科學統(tǒng)籌協(xié)調(diào)，由于沒有相應機制上的制約與保護，監(jiān)理發(fā)揮的作用受到了很大限制，工作形式各不相同，業(yè)主和監(jiān)理方的權利難以保障，甚至存在業(yè)主引進監(jiān)理裝門面走形式的現(xiàn)象，重大測繪項目的成果質(zhì)量仍然難以保證。只有將監(jiān)理納入測繪行業(yè)統(tǒng)一管理的范疇，制定并實行國家測繪工程監(jiān)理有關法規(guī)和技術規(guī)范，實行統(tǒng)一監(jiān)管，才能保證測繪工程監(jiān)理健康發(fā)展。

螺旋更新位置:鯨魚靠近獵物的過程滿足螺旋方程

由于泡泡網(wǎng)攻擊的過程中收縮包圍機制與螺旋更新位置同時發(fā)生,假設鯨魚執(zhí)行其中任意一個行為的概率均為50%,即鯨魚的位置更新公式為:

其中p是[0,1]中的隨機數(shù).

(2) 搜索獵物

由于在實際情況中座頭鯨的隨機搜索過程依賴于彼此的位置,故鯨魚算法使用||＞1強迫搜索代理遠離參考鯨魚.與攻擊過程相反,在搜索過程中并不根據(jù)最佳搜索代理更新位置,而是根據(jù)隨機選擇的搜索代理的位置進行更新.該機制與|→|＞1都強調(diào)探索的過程并允許鯨魚算法進行全局搜索,其位置更新公式為

其中是當前種群選擇的一個隨機位置向量(隨機鯨魚).

1.3 適應度函數(shù)

為了衡量優(yōu)化搜索過程中與最優(yōu)解的距離,針對移動自組網(wǎng)絡在視頻傳輸過程中存在的鏈路擁塞及能量損耗問題,本文采用路徑擁塞度及路徑總能量作為適應度函數(shù).

(1) 路徑擁塞度

為預測并衡量生成路徑的工作負載,引入路徑擁塞度的概念,表示生成路徑工作負載的程度.路徑擁塞度由節(jié)點負荷率計算所得:

其中fcj為生成路徑pj的擁塞度,ai表示節(jié)點vi的負荷率.節(jié)點負荷率由通過經(jīng)過該節(jié)點的鏈路數(shù)l決定:

其中L為網(wǎng)絡中有效鏈路總和.

(2) 路徑魯棒性

由于移動自組網(wǎng)絡節(jié)點通常使用電池供電,故有限的能量也成為了影響移動自組網(wǎng)絡可靠性的一個因素.為盡可能保障移動自組網(wǎng)絡在有限能量下的生存時間,引入路徑魯棒性作為約束.路徑的生存周期與當前路徑中剩余能量最少的節(jié)點有關,當該節(jié)點能量耗盡時,路徑將不再有效.假設路徑pj中剩余能量最少的節(jié)點為vi,則可定義路徑魯棒性為:

其中Einit表示該節(jié)點的初始能量.該公式表明路徑魯棒性與路徑中剩余能量最少的節(jié)點的剩余能量比例以及節(jié)點負荷率有關,該節(jié)點剩余能量占初始能量比例越多,負荷率越小,則魯棒性越強.

(3) 適應度函數(shù)

綜上可知,路徑擁塞度越小,路徑魯棒性越強時,該路徑越有可能被選為候選路徑.除此之外,候選路徑應盡可能短,所以還引入跳數(shù)作為約束條件,于是適應度函數(shù)為

其中ω1,ω2和ω3是非負加權常量,ε為路徑跳數(shù).

2 仿真實驗與分析

2.1 仿真環(huán)境參數(shù)

使用Matlab對本文路由發(fā)現(xiàn)算法進行仿真與比較.測試所用的網(wǎng)絡拓撲由Atarraya工具[2]生成.網(wǎng)絡拓撲節(jié)點數(shù)為25,通訊距離為100 m,節(jié)點類型為Mica2,節(jié)點能量為不大于2000 mAh的隨機數(shù).生成的網(wǎng)絡拓撲如圖1所示.

圖1 測試用網(wǎng)絡拓撲

圖1中節(jié)點旁標注的數(shù)字表示該節(jié)點剩余能量.當兩個節(jié)點間的距離小于通訊距離(100 m)時,兩個節(jié)點間存在鏈路.

2.2 仿真結(jié)果與性能分析

為評估路由發(fā)現(xiàn)算法的性能,引入路由算法AODV[3]與AOMDV[4]進行比較.三個算法的測試參數(shù)均保持一致,其中種群數(shù)量為50,維度為25,迭代次數(shù)為50,1ω,2ω和3ω分別取值為0.4,0.4和0.2.假設源節(jié)點為1,目的節(jié)點為25,測試結(jié)果見表1.

表1 各算法查找結(jié)果

從表1數(shù)據(jù)可知,AODV算法的尋找速度明顯快于AOMDV和本文算法(WOA-MPD).可能的原因是AODV算法僅考慮跳數(shù)最短的路徑,且不考慮多路徑的情況,故尋找時間最少.雖然AODV算法成功找出了網(wǎng)絡拓撲中跳數(shù)最短的路徑,但是它在尋找路徑的過程中沒有考慮網(wǎng)絡服務質(zhì)量的問題,所得路徑的Fitness值較高,并不滿足實際應用情況.

AOMDV和WOA-MPD均考慮了多路徑情況,實際魯棒性更強.但是AOMDV算法同樣只考慮了網(wǎng)絡的拓撲結(jié)構(gòu),而沒有考慮網(wǎng)絡運行中的服務質(zhì)量,得出的部分路徑Fitness值較大,在網(wǎng)絡的實際運行過程中容易出現(xiàn)節(jié)點電量過早耗盡的情況,影響網(wǎng)絡的正常服務.同時AOMDV算法的尋找時間最長,在大規(guī)模網(wǎng)絡的情況下耗時過大.

由于在適應度函數(shù)中考慮了節(jié)點擁塞度與剩余電量等因素,本文提出的WOA-MPD算法找出的三條路徑的Fitness值均較小,保障了網(wǎng)絡的魯棒性.并且三條路徑的跳數(shù)均與最低跳數(shù)(5跳)僅相差一跳,在保障了魯棒性的同時也保障了路徑的長度盡可能短,提高了路由效率.

3 結(jié)論

本文針對移動自組網(wǎng)絡在視頻傳輸過程中存在的鏈路擁塞及能量損耗問題,將路徑擁塞度及路徑魯棒性定義為適應度函數(shù),并通過鯨魚優(yōu)化算法有效求解滿足多約束條件的多路由路徑,提高了移動自組網(wǎng)絡的性能與魯棒性,并保證其服務質(zhì)量.