一種基于螢火蟲算法的飛行自組織網絡路由協議

王紅茹，趙紅碩

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

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

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

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

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

1 系統理論

1.1 OLSR 協議

OLSR 協議是一種表驅動的路由協議，OLSR 的處理流程下：

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

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

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

4) 節點根據TC 分組建立網絡拓撲表，根據一跳鄰居表、二跳鄰居表和網絡拓撲表建立并維護網絡路由表；

5) 節點根據自身維護的路由表發送數據包。

1.2 螢火蟲算法

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

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

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

3) 定義相對吸引度；

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

5) 根據終止條件決定是否從步驟4)繼續執行。

2 FA-OLSR 協議

FANETs 中，節點之間的相對運動狀態決定了節點之間的鏈路持續時間，FA-OLSR 協議使用節點間的相對速度信息計算鏈路持續時間指標。此外，節點之間的相對距離反映了節點之間的鏈路通信質量，為了更好地衡量通信鏈路的可靠性和中繼性，FA-OLSR 協議引入Beta 分布函數計算鏈路質量指標。

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

2.1 鏈路穩定性計算

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

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

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

圖1 中繼點位置示意

Beta 分布函數為

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

Beta 分布函數的概率密度函數為

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

式中R為無人機節點的通信距離。

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

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

2.2 螢火蟲編碼

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

2.3 初始化螢火蟲種群

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

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

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

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

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

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

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

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

2.4 計算螢火蟲亮度

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

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

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

2.5 螢火蟲位置移動

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

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

輸入：螢火蟲種群。

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

參數設置：螢火蟲xi的亮度為I[i]、0～1 范圍內的隨機數為r、不同的吸引度參數 β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 性質，使得螢火蟲個體代表的CMPR不能夠覆蓋所有的嚴格二跳鄰居。因此需要對螢火蟲個體進行篩選，將不能完全覆蓋二跳鄰居節點的螢火蟲個體剔除。為了保證移動操作的有效性，在迭代開始前，篩選出不具備MPR 性質的螢火蟲個體，并使用周圍亮度較亮的螢火蟲覆蓋，保證螢火蟲處在有效位置。如果螢火蟲出現位置重合，對其中一個螢火蟲進行隨機移動。

2.7 MPR 選擇機制

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

輸入：螢火蟲種群。

輸出：最優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

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

3 仿真結果與分析

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

表1 仿真環境參數表

端到端時延、數據包傳遞成功率和網絡吞吐量的定義如下：

1) 端到端時延：數據包傳輸時延通常包括緩存區時延、路由查找時延以及數據包傳送時延等，表現為節點產生消息到消息被接收之間的時間段。

2) 數據包傳遞成功率：數據包傳遞成功率定義為目的節點成功接收的數據包數目與源節點發送的數據包數目的比值，反映了網絡通信的可靠性。

3) 網絡吞吐量：吞吐量定義為單位時間內成功發送的數據量，表示網絡傳輸數據包的能力。

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

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

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

圖3 節點傳輸數據平均端到端時延性能

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

圖4 網絡吞吐量性能

4 結論

1）FA-OLSR 協議提出了鏈路持續時間和鏈路質量指標衡量鏈路性能，組合鏈路持續時間和鏈路質量指標計算鏈路穩定性并將其作為選擇CMPR的準則。

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

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