一種基于螢火蟲算法的飛行自組織網(wǎng)絡路由協(xié)議

王紅茹，趙紅碩

哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

飛行自組織網(wǎng)絡(flying Ad-Hoc networks，F(xiàn)ANETs)是移動自組織網(wǎng)絡 (mobile ad-hoc network, MANET)在空天領域的擴展應用。無人機等飛行器的稀疏分布和高動態(tài)特性導致網(wǎng)絡拓撲結(jié)構(gòu)頻繁變化[1]，應用在MANET 的路由協(xié)議無法在FANETs 中取得良好的通信效果。如何設計一個適用于FANETs 的路由協(xié)議，對于實現(xiàn)無人機之間可靠通信具有重要的現(xiàn)實意義。

按照建立路由的方式，基于拓撲的路由協(xié)議分為先驗式路由協(xié)議和反應式路由協(xié)議。反應式路由協(xié)議如動態(tài)源路由(dynamic source routing protocol，DSR)協(xié)議，在出現(xiàn)數(shù)據(jù)傳輸需求時才開啟路由發(fā)現(xiàn)進程。相關的研究集中在如何評估鏈路路由質(zhì)量并獲取最佳路由[2-4]。先驗式路由協(xié)議如最優(yōu)化鏈路狀態(tài)(optimized link state routing，OLSR)協(xié)議，每個節(jié)點維護反映網(wǎng)絡最新路由信息的路由表，相關的研究集中在握手消息(Hello)發(fā)送間隔的調(diào)整[5-7]、路由選擇準則[8-10]以及多點中繼（multipoint relay，MPR）選擇機制的設計[11-19]。相比于DSR 協(xié)議，OLSR 協(xié)議更適合低時延、高可靠性要求的飛行自組織網(wǎng)絡。

OLSR 協(xié)議中，每個節(jié)點的部分一跳鄰居節(jié)點被選作MPR，只有MPR 可以洪泛拓撲控制(topology control，TC)信息，網(wǎng)絡拓撲結(jié)構(gòu)通過MPR 與其多點中繼選擇節(jié)點(MPR selector)間的鏈路拓撲信息建立。如何設計適用于FANETs 特點的MPR 選擇機制是實現(xiàn)無人機節(jié)點之間穩(wěn)定通信的關鍵所在。OLSR 協(xié)議使用一跳鄰居節(jié)點的連接度作為MPR 選擇準則，盡量減少數(shù)據(jù)包的重復轉(zhuǎn)發(fā)情況。然而該準則不能反映鏈路通信質(zhì)量，連接度高的節(jié)點不能確保具備穩(wěn)定有效的鏈路通信功能。文獻[11]通過統(tǒng)計物理層的信噪比信息評估鏈路質(zhì)量并作為MPR 選擇準則，文獻[12]通過節(jié)點間的距離和鄰居變化率選取MPR，文獻[13]優(yōu)先選擇具有較高剩余能量和較低速度的節(jié)點作為MPR。以上相關研究通過設計鏈路質(zhì)量評定準則獲取最優(yōu)的通信鏈路。然而以上相關研究只能對當下鏈路拓撲質(zhì)量做評估，缺少對網(wǎng)絡拓撲穩(wěn)定性的考慮，難以適應高動態(tài)的飛行自組織網(wǎng)絡。針對飛行自組織網(wǎng)絡的高動態(tài)特性，文獻[14-16]通過全球定位系統(tǒng)(global positioning system，GPS)獲取節(jié)點的速度和位置信息并計算節(jié)點之間的鏈路持續(xù)時間，將鏈路持續(xù)時間加入到衡量鏈路質(zhì)量的標準之中。文獻[17]使用計算一段時間周期內(nèi)2 個節(jié)點之間Hello 消息的收發(fā)成功比例以及移動相似度作為MPR 的評選指標。通過對節(jié)點移動狀態(tài)的評估和預測，MPR 選擇機制得到優(yōu)化，所建立的拓撲路由能夠保證一定的穩(wěn)定性，然而使用貪心策略的MPR 選擇機制會使得MPR 集合CMPR產(chǎn)生冗余。MPR 選擇問題被證明是一個多項式復雜程度的非確定性問題(non-deterministic polynomial, NP)[18]。對于該類問題，使用啟發(fā)式算法可獲取近似最優(yōu)解。文獻[19]將量子計算與遺傳算法相結(jié)合，提出了一種基于量子比特與量子疊加的MPR 選擇算法，該算法能有效地減少CMPR冗余情況，但會引入大量的計算量，對無人機的計算能力有較高要求。

針對上述研究問題，本文提出基于螢火蟲算法(firefly algorithm，F(xiàn)A)的FA-OLSR 協(xié)議，通過使用節(jié)點間鏈路持續(xù)時間和鏈路質(zhì)量評估鏈路性能，組合鏈路持續(xù)時間和鏈路質(zhì)量指標計算鏈路穩(wěn)定性并將其作為選擇MPR 集合的準則。螢火蟲算法具有參數(shù)少、收斂快、求解精度較高的優(yōu)點，因此FA-OLSR 協(xié)議的MPR 選擇機制利用螢火蟲算法來求取CMPR的最優(yōu)解。文中提出的FAOLSR 協(xié)議能夠較為準確地評估鏈路質(zhì)量、減少CMPR冗余度并建立穩(wěn)定的通信路由，使無人機之間的通信性能得到明顯提升。

1 系統(tǒng)理論

1.1 OLSR 協(xié)議

OLSR 協(xié)議是一種表驅(qū)動的路由協(xié)議，OLSR 的處理流程下：

1) 節(jié)點通過接收和發(fā)送Hello 消息填充并更新本地鏈路信息表、一跳鄰居表、二跳鄰居表；

2) 節(jié)點在一跳鄰居表中選取部分鄰居節(jié)點作為MPR，建立CMPR；

3) MPR 建立MPR Selector 表，將包含MPR與MPR Selector 之間的鏈路狀態(tài)信息的TC 分組洪泛到全網(wǎng)絡；

4) 節(jié)點根據(jù)TC 分組建立網(wǎng)絡拓撲表，根據(jù)一跳鄰居表、二跳鄰居表和網(wǎng)絡拓撲表建立并維護網(wǎng)絡路由表；

5) 節(jié)點根據(jù)自身維護的路由表發(fā)送數(shù)據(jù)包。

1.2 螢火蟲算法

FA 是一種求解優(yōu)化問題的啟發(fā)式算法。該算法的靈感來自于螢火蟲的閃爍行為，種群中每個螢火蟲代表一個候選解，螢火蟲亮度取決于在目標函數(shù)上的性能表現(xiàn)[20]。FA 算法有以下核心思想：首先，每個螢火蟲都有可能被其他螢火蟲吸引；其次，螢火蟲對其他螢火蟲的吸引力與自身的亮度成正比、與2 只螢火蟲之間的距離成反比。這種吸引機制使得整個螢火蟲種群都會向優(yōu)質(zhì)解的方向移動，而螢火蟲之間的移動卻是相對獨立的，因此可以獲得局部最優(yōu)解和全局最優(yōu)解。FA 的算法流程如下所述：

1) 設置算法的各項參數(shù)，初始化種群中螢火蟲位置；

2) 將目標函數(shù)映射為螢火蟲的絕對亮度；

3) 定義相對吸引度；

4) 螢火蟲位置移動和更新；

5) 根據(jù)終止條件決定是否從步驟4)繼續(xù)執(zhí)行。

2 FA-OLSR 協(xié)議

FANETs 中，節(jié)點之間的相對運動狀態(tài)決定了節(jié)點之間的鏈路持續(xù)時間，F(xiàn)A-OLSR 協(xié)議使用節(jié)點間的相對速度信息計算鏈路持續(xù)時間指標。此外，節(jié)點之間的相對距離反映了節(jié)點之間的鏈路通信質(zhì)量，為了更好地衡量通信鏈路的可靠性和中繼性，F(xiàn)A-OLSR 協(xié)議引入Beta 分布函數(shù)計算鏈路質(zhì)量指標。

FA-OLSR 協(xié)議利用螢火蟲算法求取CMPR的最優(yōu)解。在使用螢火蟲算法求取CMPR的過程中，采用0-1 編碼對螢火蟲進行編碼，使用節(jié)點的連接度初始化螢火蟲的位置，利用MPR Selector 和MPR 之間的鏈路穩(wěn)定性計算螢火蟲的亮度。通過移動更新螢火蟲的位置探索最優(yōu)的CMPR，經(jīng)過一定的迭代次數(shù)后得到最優(yōu)CMPR。

2.1 鏈路穩(wěn)定性計算

本文在仿真過程中，忽略無人機在垂直方向上的坐標信息和速度信息。設無人機節(jié)點a、k的速度分別為va、vk， 坐標信息分別為(xa,ya)、(xk,yk)。根據(jù)相對運動學，無人機節(jié)點a、k之間的相對速度、相對距離為

根據(jù)無人機節(jié)點a、k之間的相對速度，計算得到a、k之間的鏈路持續(xù)時間：

中繼節(jié)點在源節(jié)點通信范圍內(nèi)時，便可以承擔轉(zhuǎn)發(fā)中繼的功能。如果中繼節(jié)點靠近源節(jié)點通信范圍邊緣時，鏈路通信效果較差，反之中繼效果較差。如圖1 所示，節(jié)點O為源節(jié)點，節(jié)點a、b、c為中繼節(jié)點。節(jié)點O選擇其中一個作為自己的中繼節(jié)點。其中節(jié)點a靠近源節(jié)點，中繼效果很差；節(jié)點c處在源節(jié)點O通信范圍邊緣，通信鏈路容易中斷；節(jié)點b處在相較合適的位置，具有較好的鏈路通信效果和中繼效果。為了評估節(jié)點之間的鏈路質(zhì)量，F(xiàn)A-OLSR 協(xié)議引入了Beta 分布函數(shù)。

圖1 中繼點位置示意

Beta 分布函數(shù)為

式中：Beta 分布的定義域為[0,1]，α、β為不小于0 的參數(shù)。

Beta 分布函數(shù)的概率密度函數(shù)為

對無人機節(jié)點a、k之間的相對距離歸一化處理得到參數(shù)rak：

式中R為無人機節(jié)點的通信距離。

通過以上分析可知，源節(jié)點臨近區(qū)域與通信范圍邊緣區(qū)域具有相同的通信質(zhì)量，因此取Beta 分布中參數(shù)值α=β=2，代入rak到Beta 分布的概率密度函數(shù)并計算鏈路質(zhì)量指標為

鏈路質(zhì)量指標是對鏈路通信效果和中繼效果的綜合評價。鏈路質(zhì)量和鏈路持續(xù)時間指標組合形成鏈路穩(wěn)定性指標，并將其作為衡量鏈路性能的準則。

2.2 螢火蟲編碼

CMPR是節(jié)點一跳鄰居的子集，CMPR的選擇問題是一種離散型問題。因此，在利用螢火蟲算法求取MPR 集合時，需要對螢火蟲離散化。一跳鄰居節(jié)點只有非MPR 和MPR 這2 種類型，因此采用0-1 編碼策略對螢火蟲編碼。設定節(jié)點i的一跳鄰居集合為Ni={Ni1,Ni2,···,Nin}，n為一跳鄰居節(jié)點數(shù)目，則對于節(jié)點i的一跳鄰居Nik，螢火蟲i的對應維度xik編碼方式為

2.3 初始化螢火蟲種群

螢火蟲種群中的螢火蟲個體都需要滿足MPR 集合的性質(zhì)，即螢火蟲個體代表的CMPR能夠覆蓋所有的嚴格對稱二跳鄰居節(jié)點；其次，螢火蟲種群應該具有多樣性，避免陷入局部最優(yōu)的情況。因此FA-OLSR 采用輪盤賭策略初始化螢火蟲個體，單個螢火蟲個體的初始化流程如下所述：

1) 設置序號為i的一跳鄰居節(jié)點的連接度為D(i)，被選中為MPR 的概率定義為pi；

2) 在一跳鄰居集N1={N11,N12,···,N1n}中選擇對某一二跳鄰居唯一可達的節(jié)點為MPR；

3) 計算每個一跳鄰居節(jié)點被選擇為MPR 的概率pi：

4）計算每一個一跳鄰居節(jié)點代表的累加概率值qi：

5）在[0,1)內(nèi)取隨機數(shù)r，選擇滿足條件qi-1＜r≤qi的一跳鄰居為MPR；

6）重復步驟5），直到螢火蟲個體具備CMPR的性質(zhì)。

采用上述流程對螢火蟲種群中的螢火蟲個體進行初始化，得到初始螢火蟲種群。

2.4 計算螢火蟲亮度

CMPR承擔著洪泛TC 消息分組的任務，最小數(shù)量的CMPR能夠減少網(wǎng)絡中消息的洪范數(shù)量，降低路由開銷。考慮到FANETs 的高動態(tài)性，使用本文提出的鏈路持續(xù)時間和鏈路質(zhì)量組成的鏈路穩(wěn)定性指標作為MPR 選擇準則。文獻[17]中指出，MPR 是作為中繼節(jié)點覆蓋某個節(jié)點的2 跳鄰居，計算鏈路穩(wěn)定性指標的時候要考慮其傳遞性與中繼放大的特性。因此計算螢火蟲i的適應度函數(shù)為

式中：f(rak;2,2)為本地節(jié)點a與一跳鄰居節(jié)點k之間的鏈路質(zhì)量，tak為本地節(jié)點a與一跳鄰居節(jié)點k之間的鏈路持續(xù)時間，兩者之和組成鏈路穩(wěn)定性指標；tk j為一跳鄰居節(jié)點k和與其連接的二跳鄰居節(jié)點j之間的鏈路持續(xù)時間，f(rk j;2,2)為一跳鄰居節(jié)點k和與其連接的二跳鄰居節(jié)點j之間的鏈路質(zhì)量參數(shù)，average 表示節(jié)點k與通過該節(jié)點到達的所有嚴格對稱二跳鄰居節(jié)點的鏈路指標的算術平均值，兩者之和作為一跳鄰居節(jié)點k和與之相連的二跳鄰居之間的平均鏈路穩(wěn)定性指標。

螢火蟲的亮度直接由螢火蟲的適應度函數(shù)值設定：

2.5 螢火蟲位置移動

FA-OLSR 協(xié)議的MPR 選擇問題設置為最小化問題，螢火蟲的亮度與MPR 解集的質(zhì)量成反比，螢火蟲亮度較亮者會被螢火蟲亮度較暗者吸引。螢火蟲之間的吸引力和螢火蟲之間的距離成反比，由于螢火蟲編碼方式為0-1 編碼，因此設定螢火蟲的吸引力程度為使螢火蟲維度值發(fā)生變化的不同概率值 β1、β2(0 ＜β2＜β1＜1)。

螢火蟲與代表最優(yōu)解的螢火蟲在相同維度上的值相同時，表明螢火蟲在此維度的值接近最優(yōu)解的位置，以較大概率 β1保持原值不變；反之，以較小概率 β2保持原值不變。另外，為了避免陷入局部最優(yōu)，螢火蟲移動時引入隨機策略。當2 個螢火蟲處于同一位置時，即2 個螢火蟲各個維度相同時，隨機改變其中1 個螢火蟲的某一維度值。螢火蟲的移動算法（Algorithm 1）如下所示：

輸入：螢火蟲種群。

輸出：移動操作后的螢火蟲種群。

參數(shù)設置：螢火蟲xi的亮度為I[i]、0～1 范圍內(nèi)的隨機數(shù)為r、不同的吸引度參數(shù) β1、 β2。

計算過程：

forxi∈populations do

ifI[j]＞I[i] then

fork=0 toDdo

ifxik==xjkANDr＞β1then

xjk←NOTxjk

else ifxik≠xjkANDr＞β2then

xjk←NOTxjk

end if

end for

end if

end for

2.6 螢火蟲個體篩選

螢火蟲的移動操作也會破壞MPR 性質(zhì)，使得螢火蟲個體代表的CMPR不能夠覆蓋所有的嚴格二跳鄰居。因此需要對螢火蟲個體進行篩選，將不能完全覆蓋二跳鄰居節(jié)點的螢火蟲個體剔除。為了保證移動操作的有效性，在迭代開始前，篩選出不具備MPR 性質(zhì)的螢火蟲個體，并使用周圍亮度較亮的螢火蟲覆蓋，保證螢火蟲處在有效位置。如果螢火蟲出現(xiàn)位置重合，對其中一個螢火蟲進行隨機移動。

2.7 MPR 選擇機制

螢火蟲表示為xj,j∈[0,s)，s為種群規(guī)模，imax為最大迭代次數(shù)。FA-OLSR 的MPR 選擇機制如下：

輸入：螢火蟲種群。

輸出：最優(yōu)CMPR。

計算過程：

whileit＜imaxdo

forj=0 tosdo

if (xjis not a MPR)

xj←xj-1

end if

end for

forj=0 tosdo

ComputeI(j) according to Eq (1)

end for

sort(xj,I(j)),j∈[0,s)

Apply the move operation according to Algorithm 1

end while

return the best solution,CMPR

螢火蟲之間通過相互吸引、移動的方式，最終聚集到最優(yōu)螢火蟲的周圍，獲取最優(yōu)CMPR的過程與螢火蟲種群這種行為極為相似。MPR 選擇機制需要根據(jù)不同的網(wǎng)絡拓撲狀況尋找最合適的部分一跳鄰居節(jié)點轉(zhuǎn)發(fā)TC 分組消息，因此，在設計MPR 選擇機制的過程中，將螢火蟲個體作為CMPR的解，通過移動、迭代操作不斷接近最優(yōu)CMPR。

3 仿真結(jié)果與分析

FANETs 路由協(xié)議的仿真在OMNET++平臺上完成。 FA-OLSR、 LD_OLSR、 OLSR、 OLSRr2 協(xié)議的仿真參數(shù)設置如表1 所示。端到端時延、節(jié)點間數(shù)據(jù)包的傳遞成功率和網(wǎng)絡吞吐量作為衡量路由協(xié)議的性能指標。仿真記錄不同的節(jié)點速度下路由協(xié)議的性能變化。

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

端到端時延、數(shù)據(jù)包傳遞成功率和網(wǎng)絡吞吐量的定義如下：

1) 端到端時延：數(shù)據(jù)包傳輸時延通常包括緩存區(qū)時延、路由查找時延以及數(shù)據(jù)包傳送時延等，表現(xiàn)為節(jié)點產(chǎn)生消息到消息被接收之間的時間段。

2) 數(shù)據(jù)包傳遞成功率：數(shù)據(jù)包傳遞成功率定義為目的節(jié)點成功接收的數(shù)據(jù)包數(shù)目與源節(jié)點發(fā)送的數(shù)據(jù)包數(shù)目的比值，反映了網(wǎng)絡通信的可靠性。

3) 網(wǎng)絡吞吐量：吞吐量定義為單位時間內(nèi)成功發(fā)送的數(shù)據(jù)量，表示網(wǎng)絡傳輸數(shù)據(jù)包的能力。

圖2～圖4 分別給出了FA-OLSR、LD-OLSR、OLSR、OLSR-r2 在不同的節(jié)點速度下的各種性能。

如圖2 所示，在網(wǎng)絡拓撲相對穩(wěn)定的階段，F(xiàn)A-OLSR、LD-OLSR、OLSR、OLSR-r2 協(xié)議的數(shù)據(jù)包傳輸成功率相差不大，隨著節(jié)點移動速度的提高，幾種協(xié)議的數(shù)據(jù)包傳輸成功率均呈現(xiàn)下降的趨勢。以節(jié)點連接度為MPR 選擇準則的OLSR 協(xié)議和以鏈路帶寬為MPR 選擇準則的OLSR-r2 協(xié)議不太適應頻繁變化的網(wǎng)絡拓撲結(jié)構(gòu)，數(shù)據(jù)包傳輸成功率較差。在選擇MPR 時考慮節(jié)點間鏈路持續(xù)時間因素的LD-OLSR 和FAOLSR 協(xié)議能夠較好地適應快速變化的網(wǎng)絡拓撲結(jié)構(gòu)，數(shù)據(jù)包傳輸成功率較高。FA-OLSR 相對于LD-OLSR 協(xié)議，在節(jié)點較高移動速度場景下具有更好的數(shù)據(jù)傳輸成功率表現(xiàn)，這是因為FAOLSR 協(xié)議綜合考慮了鏈路持續(xù)時間和鏈路質(zhì)量的因素，而且在MPR 選擇機制中利用了啟發(fā)式算法，更容易獲取最優(yōu)解，使得獲取的路由鏈路更加穩(wěn)定。

對于表驅(qū)動路由協(xié)議，每個節(jié)點都維護一張具有到全網(wǎng)絡節(jié)點路徑的路由表。如圖3 所示，隨著節(jié)點移動速度的提高，節(jié)點之間的通信鏈路斷裂風險提高， FA-OLSR、 LD-OLSR、 OLSR、OLSR-r2 協(xié)議的平均端到端時延均呈現(xiàn)出上升的趨勢。以節(jié)點連接度為MPR 選擇準則的OLSR協(xié)議和以鏈路帶寬為MPR 選擇準則的OLSRr2 協(xié)議不太適應頻繁變化的網(wǎng)絡拓撲結(jié)構(gòu)，通信鏈路斷裂概率較大，因此具有較大的網(wǎng)絡端到端時延。相比于LD_OLSR，F(xiàn)A-OLSR 協(xié)議在選取MPR時參考了鏈路質(zhì)量因素，所選擇通信鏈路中的節(jié)點具有更好的中繼性，因此FA-OLSR 協(xié)議具有較小、更平穩(wěn)的平均端到端時延。

圖3 節(jié)點傳輸數(shù)據(jù)平均端到端時延性能

如圖4 所示，在網(wǎng)絡拓撲相對穩(wěn)定的階段，F(xiàn)A-OLSR 協(xié)議因為具有比其他路由協(xié)議更多的路由開銷，吞吐量相對較低。隨著節(jié)點移動速度的提高，F(xiàn)A-OLSR、LD-OLSR、OLSR、OLSR-r2 協(xié)議的吞吐量呈現(xiàn)出下降的趨勢。由于數(shù)據(jù)包傳輸成功率的差異，F(xiàn)A-OLSR、LD-OLSR 協(xié)議相比OLSR、 OLSR-r2 協(xié)議吞吐量較高。 相比于LD_OLSR 協(xié)議，F(xiàn)A-OLSR 協(xié)議的MPR 選擇機制使用了螢火蟲優(yōu)化算法，雖然帶來了一定的路由開銷，但優(yōu)化的CMPR成員更加穩(wěn)定，路由維護階段的路由開銷較少，因此具有較高的吞吐量。

圖4 網(wǎng)絡吞吐量性能

4 結(jié)論

1）FA-OLSR 協(xié)議提出了鏈路持續(xù)時間和鏈路質(zhì)量指標衡量鏈路性能，組合鏈路持續(xù)時間和鏈路質(zhì)量指標計算鏈路穩(wěn)定性并將其作為選擇CMPR的準則。

2）FA-OLSR 協(xié)議在螢火蟲算法的基礎上設計了MPR 選擇機制，采用0-1 編碼對螢火蟲進行編碼，使用節(jié)點的連接度初始化螢火蟲的位置，確保了螢火蟲個體代表合格的CMPR。MPR Selector和MPR 之間的鏈路穩(wěn)定性被用來計算螢火蟲的亮度。螢火蟲的移動操作被用來探索最優(yōu)CMPR。

實驗結(jié)果證明，相比于LD_OLSR、OLSR、OLSR-r2 協(xié)議，所提出的FA-OLSR 協(xié)議在端到端時延、吞吐量、數(shù)據(jù)包成功率指標均有所提升，在大多數(shù)場景下有著更加優(yōu)異的網(wǎng)絡性能，因而FA-OLSR 協(xié)議對高動態(tài)的FANETs 網(wǎng)絡具有良好的適用性。