一種無人機自組網DSR協議優化方法

劉慶華，黃聲培，葉金才，康一鳴

桂林電子科技大學信息與通信學院，廣西 桂林 541004

集群無人機協同通信的無線組網技術簡稱無人機自組網，網絡中每個無人機（unmanned aerial vehicle，UAV）節點均配置收發信機，具有拓撲不固定、通信自組織、無控制中心的特點。無人機自組網規模易于擴展，節點動態加入和退出并不影響網絡的通信。無人機自組網突破了依靠地面基站的限制，可以進行快速部署，在軍事行動、救災、邊防等方面具有廣泛應用。

相比于傳統的地面移動自組網，無人機自組網的網絡拓撲變化更快，網絡節點的能量和帶寬均有限，如何建立高效穩定的傳輸路徑，保證通信質量，同時控制好網絡的路由開銷，是無人機自組網研究的熱點問題。其中，路由協議是協調無人機節點組網通信、維護網絡的關鍵，是無人機自組網高效運行的保障。

動態源路由（dynamic source routing，DSR）協議和其他路由協議相比，具有更低的路由開銷。但該協議在路由請求洪泛的過程中，只保證了鏈路的連通性，忽略了鏈路的穩定性，通信質量并不高。文獻[1]加入了節點能量因素，對DSR 協議路由發現過程進行了相應的修改，提高路由發現的效率和網絡能量的利用率。文獻[2]用多播算法與DSR 協議相結合的方式，提高了自組網的分組傳遞率和網絡吞吐量。文獻[3]用MIKBIT（mobile internetwork broadcast infrastructure technique）的組播方式來減少請求分組開銷，提高了DSR 協議的性能。文獻[4]提出一種擁塞感知與多路徑相結合的方法，利用相關因子處理DSR 協議端到端時延的問題。文獻[5]利用相鄰節點之間的距離和移動性來評估路由發現、路由維持和路由切換過程，保證數據包的傳遞率。

除了上述優化方法，還可利用群智能優化算法解決DSR 協議的路由優化問題。群智能優化算法是近年來研究的熱點，其中具有代表性的有蟻群算法（ant colony optimization，ACO）[6-7]、粒子群算法（particle swarm optimization，PSO）[8]、螢火蟲算法（firefly algorithm，FA）[9-10]等，FA算法由Yang教授提出，該算法的魯棒性強，目前已應用于解決特征選擇優化[10]、多模態函數優化[11]等問題。本文針對無人機場景，提出了一種基于螢火蟲算法的DSR協議優化（firefly algorithm dynamic source routing，FA_DSR）方法，利用螢火蟲算法來優化傳統的DSR路由協議，均衡網絡節點的資源消耗，提升無人機自組網的性能。仿真實驗結果表明，相比傳統DSR 協議的路由方法，優化方法降低了路由開銷，提高了無人機自組網的性能。

1 相關算法和協議介紹

1.1 螢火蟲算法

螢火蟲算法的靈感來源于觀察自然界中螢火蟲的習性[12]。螢火蟲的熒光作為一種信號，主要作用是為了吸引異性和誘捕獵物，同時也是一種預警保護機制。螢火蟲算法最初用于處理連續優化問題，起始時刻，螢火蟲隨機分布于搜索空間中，其位置代表了待求問題的可行解，螢火蟲的熒光亮度表示該螢火蟲的適應度，亮度低的螢火蟲會被亮度高的螢火蟲吸引，亮度越高吸引力越強，由于距離的增加會導致亮度衰減，因此，吸引力與距離成反比。一般地，螢火蟲算法的步驟描述如下：

步驟1 初始化算法參數。

步驟2 初始化螢火蟲位置，計算適應度函數。

步驟3 計算螢火蟲的相對吸引力，其吸引力公式為：

其中，β0表示初始吸引力，即rij為0 時的吸引力；γ表示介質對光的吸收系數；，rij表示螢火蟲i和j之間的歐氏距離，公式為：

其中，d表示空間的維度，xi,v表示螢火蟲i的第v維數據。

步驟4 螢火蟲向熒光亮度更高的螢火蟲移動，其移動公式如下：

其中，xi(t)表示螢火蟲i在第t次迭代時的位置，xj(t)為螢火蟲i在第t次迭代移動的對象j的位置，α表示擾動因子，rand為0～1之間的隨機數。

步驟5 計算螢火蟲移動后所到新位置的適應度值，若該位置優于移動前的位置，則該螢火蟲移動到該位置；否則，螢火蟲停留在移動前的位置。

步驟6 達到搜索精度或迭代極限Gmax，搜索完成，輸出結果，否則轉到步驟3。

1.2 DSR協議

DSR協議算法流程主要包括兩部分：路由發現和路由維護[13]。該協議查找路由的方式如圖1 所示，源節點S有業務傳輸需求時，首先將路由請求廣播到一跳鄰居節點(A,B)，收到路由請求的節點判斷是否緩存有到達目的節點的路由。如果有，則向源節點S發送緩存路由回復；如果沒有，一跳中間節點(A,B)繼續廣播該路由請求，通過中間節點不斷重復，最終到達目的節點D，其路徑為(S→B→C→D)。D收到路由請求后，逆著請求得到的首條路徑往源節點S發送路由回復(D→C→B→S)，源節點S收到路由回復，路由尋路過程結束，從而建立源節點S到目的節點D的傳輸路徑。

圖1 DSR協議的路由發現過程Fig.1 Routing discovery process of DSR protocol

路由維護過程為：當某一節點檢測鏈路的下一跳不可達時，表明傳輸鏈路斷開，該節點首先檢查緩存區是否緩存有到達目的節點的路由，如果有，則繼續沿著緩存的路由向目的節點發送數據；如果沒有，該節點沿著傳輸路徑逆向往源節點發送路由錯誤，收到路由錯誤的節點刪除故障鏈路，更新路由緩存[14]。當源節點收到路由錯誤后，重新啟動路由發現過程。

本文為了提高DSR 協議的路由發現效率，保障無人機自組網傳輸鏈路的穩定性，將螢火蟲算法運用于DSR 協議的路徑優化問題中，綜合優化DSR 協議的路由發現過程，提出了一種基于螢火蟲算法的無人機自組網DSR協議優化（FA_DSR）方法。

2 DSR協議優化（FA_DSR）方法的原理和實現

為了評估螢火蟲的熒光亮度，算法需要構建適應度函數，螢火蟲算法利用適應度函數來衡量每個螢火蟲的亮度，選取熒光亮度更高的螢火蟲作為下一跳節點，從而提高DSR協議的路由請求效率，保證傳輸鏈路的穩定性。

2.1 適應度函數

為了均衡優化無人機自組網的網絡性能和路由開銷，根據無人機自組網的特點，優化方法考慮以下四點因素構建適應度函數：

（1）節點的能耗。節點的存活時間由節點的剩余能量決定，在路由選擇的過程中，應盡可能選擇能量消耗較小的節點，防止通信鏈路過早中斷，延長通信鏈路的生存時間。能量適應度值表示節點消耗的能量與初始能量的比值，體現了節點的能耗情況，表達式如下：

其中，Ej_con表示節點j消耗的能量值，Einitial表示節點初始能量值，nj表示節點j發送數據包的數量，ET(k)表示發送k比特數據包的能量消耗，mj表示節點j接收數據包的數量，ER(k)表示接收k比特數據包的能量消耗。

（2）節點的移動速率。由于無人機的運動狀態隨機變化，導致網絡拓撲時刻發生變化，移動速率越大拓撲變化越快，因此，選取移動速率相對較小的節點構建傳輸鏈路，要比移動速率大的節點更穩定。速率適應度值衡量了節點的移動速率大小，其表達式如下：

其中，Sj_current表示節點j的當前移動速率值，Smax表示節點移動速率的最大值，速率適應度值衡量了節點的移動速率大小。

（3）節點的緩沖擁塞率。緩沖擁塞率體現節點發送數據包的繁忙程度。緩沖區的容量有限，如果擁塞程度較高，說明此節點待發送的數據包較多，丟失數據包的概率大，因此，優先選擇繁忙程度低的節點作為轉發節點。擁塞適應度值表示節點緩沖區的擁塞率大小，其表達式如下：

其中，Cj_current表示節點j當前的緩沖區隊列大小，Cmax表示節點緩沖區總容量大小。

（4）節點的傳輸損耗。傳輸損耗主要由傳輸距離決定。由于節點之間的距離不同，導致節點的接收功率產生差異，接收功率大小反映了節點之間通信連接的穩定性，距離越近，傳輸損耗越小，接收功率越大，業務接收越穩定，距離越遠則相反。傳輸損耗適應度表達式如下：

其中，Dij_prop表示發送節點i和接收節點j傳播的歐氏距離，Dmax表示兩節點之間的最大傳播距離，Ptx_power表示節點發送的功率值，Pth表示接收功率門限值。

為了便于將各項適應度值映射轉化螢火蟲的熒光亮度，同時也為了更精確的衡量節點的適應度，需要將各項適應度函數整合為非線性的綜合適應度函數，由于線性度量在相近的數值區分不如非線性明顯，采用非線性適應度函數計算更精確，更貼合實際情況，定義FA_DSR的綜合適應度函數為：

本文將節點的能量消耗、移動速率、緩沖擁塞和傳輸損耗因素構建綜合適應度函數，利用綜合適應度函數衡量螢火蟲的熒光亮度，選取熒光亮度高的螢火蟲作為下一跳節點，綜合優化DSR協議的路由請求過程，降低網絡的路由開銷，提高無人機自組網的性能。

2.2 FA_DSR的實現

利用螢火蟲優化算法，對傳統DSR 協議的請求洪泛策略進行優化，保證通信鏈路的穩定性。FA_DSR的路由請求流程如圖2所示。

圖2 FA_DSR的路由請求流程Fig.2 Routing request flow of FA_DSR

（1）源節點初始化路由請求選項。為了傳遞位置信息和綜合適應度函數值，優化的DSR 協議對原DSR 協議請求選項進行了更改，FA_DSR的請求選項信息如表1所示。

表1 FA_DSR的請求選項信息Table 1 Request option information of FA_DSR

表中，x_position、y_position、z_position和fitness_fun_value為新增的選項信息。

（2）初始化螢火蟲。源節點的一跳鄰居收到路由請求后，將節點的位置作為初始螢火蟲的位置，即xi,v=Xj,v，初始化適應度取值范圍[Fmin,Fmax]和最大迭代數Gmax等基本參數，適應度取值范圍的選取需要均衡網絡中可用節點的數量和節點的穩定性，Fmin過小則節點穩定性不足，Fmin過大則網絡中可用節點數量不足，其具體數值見仿真實驗部分。根據公式（8）計算螢火蟲的綜合適應度值，根據適應度取值范圍舍棄低適應度的螢火蟲，剩余的螢火蟲將適應度值作為螢火蟲的熒光亮度，即Ii=Fj。

（3）螢火蟲向更高亮度的螢火蟲移動。由于路徑選擇屬于組合優化問題，而螢火蟲算法適用于處理連續優化問題，所以，為了能將螢火蟲算法應用于路徑選擇問題中，本文不再按照公式（3）移動，而是按照一定的概率選擇移動公式[16]，即螢火蟲個體的每一維坐標按照一定的概率做隨機離散移動，其離散移動公式如下：

其中，rand(v)表示第v維向量隨機產生的0～1 之間的隨機數，pset表示設定的概率閥值，Pset∈[0,1]，xj為螢火蟲個體xi在第t次迭代移動的對象，式（9）表明螢火蟲個體i在第t次迭代移動時以概率1-Pset轉移到個體j對應的第v維向量，以Pset的概率維持原來的第v維向量。

（4）調整螢火蟲位置，更新熒光值。由于移動后的螢火蟲與具體的無人機節點位置可能存在偏差，因此，需要將移動后的螢火蟲映射調整到具體的無人機節點上，并更新調整后螢火蟲的熒光值。螢火蟲與無人機節點的位置映射函數[17]為：

其中，xi為螢火蟲i的位置，Xn為表示無人機節點n的位置，l(xi,Xn)表示螢火蟲xi與無人機節點Xn之間的歐氏距離。

（5）判斷是否滿足終止條件。如果搜索到達目的節點或達到最大迭代數，則算法搜索結束，否則轉到步驟（3）。

3 仿真實驗

使用OPNET Modeler 網絡仿真軟件[18]來模擬具體的無人機自組網通信，其主要仿真參數如下：

網絡部署面積為5 km×5 km，節點總個數為30 個，各節點隨機分布在部署區域內，節點海拔高度為0.1 km，節點的移動模型為default random waypoint[19]。節點傳輸速率為5.5 Mb/s，通信連接數量為4 條單向CBR 數據流，發包間隔為0.2 s，數據包大小k為1 024 bit，節點初始能量Einitial設為40 J，ET(k)設為8.5 mJ，ER(k)設為6.3 mJ，概率閥值pset設為0.05，發送功率Ptx_power設為5 mW。最大迭代數Gmax設為32，適應度取值范圍[Fmin,Fmax]設為[0.2，1.0]，仿真時長為10 min。

DSR 為原始協議，DT_DSR（decition tree dynamic source routing）為基于決策樹算法的優化協議，FA_DSR為提出的基于螢火蟲算法的優化協議。為了比較DSR協議優化前后性能，仿真對比分析了網絡的平均端到端時延、業務接收速率、路由開銷和丟包率指標。

端到端時延統計了數據包從源節點產生到目的節點接收經歷的時間。如圖3對比了仿真時間內3種不同協議的平均端到端時延。從圖中可以看出，隨著仿真時間的進行，3 種協議產生了不同程度的時延，由于采用了螢火蟲算法對節點的能耗、移動速率、緩沖擁塞和傳輸損耗來構建綜合適應度函數，利用綜合適應度函數衡量螢火蟲的熒光亮度，選取熒光亮度更高的螢火蟲作為下一跳節點，提高了傳輸鏈路的穩定性，減少了鏈路斷裂導致的路由重啟現象，FA_DSR的端到端時延要比DT_DSR 和DSR 協議要低，雖然DT_DSR 相比原始DSR協議的端到端時延也有所下降，但遠不及FA_DSR的表現，DT_DSR 的端到端時延相比DSR 協議降低了26.99%，而FA_DSR 的端到端時延相比DSR 協議則降低了73.91%。

圖3 平均端到端時延Fig.3 Average of end-to-end delay

業務接收速率反映了目的節點接收源節點發送業務數據的快慢程度。從圖4可以看出，仿真開始后，3種協議的業務接收速率逐漸增加，逐漸接近業務發送速率。隨著仿真時間的推進，3種協議的業務接收速率開始受到網絡拓撲變化的影響，業務接收速率出現波動下降的情況，DSR 協議的業務接收速率下降最明顯，DT_DSR的業務接收速率也開始緩慢下降，但下降幅度總體小于DSR 協議。由于FA_DSR 利用適應度函數衡量螢火蟲的熒光強度，綜合選取傳輸路徑的下一跳節點，通信鏈路比DSR和DT_DSR的更穩定，受到網絡拓撲變化的影響最小，FA_DSR的業務接收速率總體高于DT_DSR和DSR協議。統計數據顯示，DT_DSR的業務接收速率比DSR 協議提高了17.42%，而FA_DSR 的業務接收速率相比DSR協議提高了33.80%。

圖4 業務接收速率Fig.4 Receiving rate of traffic

如圖5 的路由負荷發送速率和圖6 的路由負荷接收速率共同反映了網絡的路由開銷。路由負荷發送速率記錄了整個網絡中發送的路由負荷流量，路由負荷接收速率記錄了整個網絡中接收的路由負荷流量。由于FA_DSR融入了適應度函數，減少了一部分低效的路由洪泛，提高路由發現的效率，減少了路由負荷流量，降低了網絡的路由開銷。仿真結果顯示，DT_DSR的路由負荷發送速率比DSR協議減少了13.62%，而FA_DSR的路由負荷發送速率比DSR協議減少了44.99%；DT_DSR的路由負荷接收速率比DSR協議減少了15.25%，而FA_DSR的路由負荷接收速率比DSR協議減少了37.55%。

圖5 路由負荷發送速率Fig.5 Sending rate of routing load

圖6 路由負荷接收速率Fig.6 Receiving rate of routing load

如圖7 為3 種協議的丟包率對比結果，丟包率為丟失的數據包與源節點發送數據包之比，其大小反映了傳輸鏈路的可靠性。從圖中可以看出，仿真一開始，傳輸路徑還沒有建立，3種協議均丟失大量數據包，隨著路徑建立完成，丟包率開始下降，隨著仿真時間的進行，傳輸路徑受到網絡拓撲變化的影響，DSR協議不能很好的適應網絡的拓撲變化，其丟包率迅速提高。DT_DSR的丟包率相比DSR 協議有了一定的程度的降低，說明其優化策略起了一定的作用，而FA_DSR根據網絡資源實施更加科學的算法機制來選取路徑，FA_DSR的傳輸路徑相比DSR 和DT_DSR 更穩定，從而大大降低了丟包率。仿真結果顯示，DT_DSR的平均丟包率比DSR協議減少了36.33%，而FA_DSR 的平均丟包率比DSR 協議減少了68.01%。

圖7 丟包率Fig.7 Packet loss rate

仿真實驗結果充分表明，與傳統DSR 協議和現有的DT_DSR優化方法相比，本文所提的FA_DSR優化方法能有效降低網絡的路由開銷，減少端到端時延，提高業務的接收速率，降低丟包率。該優化方法可以為無人機自組網提供穩定高效的路由服務，保障無人機自組網的通信質量。

4 結論與展望

本文在傳統DSR 協議的基礎上，提出了一種基于螢火蟲算法的無人機自組網DSR 協議優化方法，利用螢火蟲算法來優化DSR協議的路由發現過程。本文方法雖然增加了路由算法的復雜度和請求報文的長度，但仿真實驗表明，提出的協議優化方法與傳統的DSR 協議相比，提高了網絡的性能，降低了網絡的路由開銷。

本文的優化方法有效解決了無人機自組網通信質量不佳，路由開銷較大的問題。然而，本文僅考慮了節點能量、移動速率和傳輸損耗等少數幾個因素，無人機自組網是一個龐大而復雜的通信系統，需要考慮的因素還有很多。因此，如果能更細致地研究無人機自組網的網絡特性，將路由協議與不同的優化算法相結合，一定能提出更好的路由方案，甚至是高性能的、全新的路由協議。