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

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

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

相比于傳統(tǒng)的地面移動自組網(wǎng)，無人機自組網(wǎng)的網(wǎng)絡(luò)拓撲變化更快，網(wǎng)絡(luò)節(jié)點的能量和帶寬均有限，如何建立高效穩(wěn)定的傳輸路徑，保證通信質(zhì)量，同時控制好網(wǎng)絡(luò)的路由開銷，是無人機自組網(wǎng)研究的熱點問題。其中，路由協(xié)議是協(xié)調(diào)無人機節(jié)點組網(wǎng)通信、維護網(wǎng)絡(luò)的關(guān)鍵，是無人機自組網(wǎng)高效運行的保障。

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

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

1 相關(guān)算法和協(xié)議介紹

1.1 螢火蟲算法

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

步驟1 初始化算法參數(shù)。

步驟2 初始化螢火蟲位置，計算適應(yīng)度函數(shù)。

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

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

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

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

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

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

步驟6 達到搜索精度或迭代極限Gmax，搜索完成，輸出結(jié)果，否則轉(zhuǎn)到步驟3。

1.2 DSR協(xié)議

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

圖1 DSR協(xié)議的路由發(fā)現(xiàn)過程Fig.1 Routing discovery process of DSR protocol

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

本文為了提高DSR 協(xié)議的路由發(fā)現(xiàn)效率，保障無人機自組網(wǎng)傳輸鏈路的穩(wěn)定性，將螢火蟲算法運用于DSR 協(xié)議的路徑優(yōu)化問題中，綜合優(yōu)化DSR 協(xié)議的路由發(fā)現(xiàn)過程，提出了一種基于螢火蟲算法的無人機自組網(wǎng)DSR協(xié)議優(yōu)化（FA_DSR）方法。

2 DSR協(xié)議優(yōu)化（FA_DSR）方法的原理和實現(xiàn)

為了評估螢火蟲的熒光亮度，算法需要構(gòu)建適應(yīng)度函數(shù)，螢火蟲算法利用適應(yīng)度函數(shù)來衡量每個螢火蟲的亮度，選取熒光亮度更高的螢火蟲作為下一跳節(jié)點，從而提高DSR協(xié)議的路由請求效率，保證傳輸鏈路的穩(wěn)定性。

2.1 適應(yīng)度函數(shù)

為了均衡優(yōu)化無人機自組網(wǎng)的網(wǎng)絡(luò)性能和路由開銷，根據(jù)無人機自組網(wǎng)的特點，優(yōu)化方法考慮以下四點因素構(gòu)建適應(yīng)度函數(shù)：

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

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

（2）節(jié)點的移動速率。由于無人機的運動狀態(tài)隨機變化，導(dǎo)致網(wǎng)絡(luò)拓撲時刻發(fā)生變化，移動速率越大拓撲變化越快，因此，選取移動速率相對較小的節(jié)點構(gòu)建傳輸鏈路，要比移動速率大的節(jié)點更穩(wěn)定。速率適應(yīng)度值衡量了節(jié)點的移動速率大小，其表達式如下：

其中，Sj_current表示節(jié)點j的當(dāng)前移動速率值，Smax表示節(jié)點移動速率的最大值，速率適應(yīng)度值衡量了節(jié)點的移動速率大小。

（3）節(jié)點的緩沖擁塞率。緩沖擁塞率體現(xiàn)節(jié)點發(fā)送數(shù)據(jù)包的繁忙程度。緩沖區(qū)的容量有限，如果擁塞程度較高，說明此節(jié)點待發(fā)送的數(shù)據(jù)包較多，丟失數(shù)據(jù)包的概率大，因此，優(yōu)先選擇繁忙程度低的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。擁塞適應(yīng)度值表示節(jié)點緩沖區(qū)的擁塞率大小，其表達式如下：

其中，Cj_current表示節(jié)點j當(dāng)前的緩沖區(qū)隊列大小，Cmax表示節(jié)點緩沖區(qū)總?cè)萘看笮　?/p>

（4）節(jié)點的傳輸損耗。傳輸損耗主要由傳輸距離決定。由于節(jié)點之間的距離不同，導(dǎo)致節(jié)點的接收功率產(chǎn)生差異，接收功率大小反映了節(jié)點之間通信連接的穩(wěn)定性，距離越近，傳輸損耗越小，接收功率越大，業(yè)務(wù)接收越穩(wěn)定，距離越遠則相反。傳輸損耗適應(yīng)度表達式如下：

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

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

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

2.2 FA_DSR的實現(xiàn)

利用螢火蟲優(yōu)化算法，對傳統(tǒng)DSR 協(xié)議的請求洪泛策略進行優(yōu)化，保證通信鏈路的穩(wěn)定性。FA_DSR的路由請求流程如圖2所示。

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

（1）源節(jié)點初始化路由請求選項。為了傳遞位置信息和綜合適應(yīng)度函數(shù)值，優(yōu)化的DSR 協(xié)議對原DSR 協(xié)議請求選項進行了更改，F(xiàn)A_DSR的請求選項信息如表1所示。

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

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

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

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

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

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

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

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

3 仿真實驗

使用OPNET Modeler 網(wǎng)絡(luò)仿真軟件[18]來模擬具體的無人機自組網(wǎng)通信，其主要仿真參數(shù)如下：

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

DSR 為原始協(xié)議，DT_DSR（decition tree dynamic source routing）為基于決策樹算法的優(yōu)化協(xié)議，F(xiàn)A_DSR為提出的基于螢火蟲算法的優(yōu)化協(xié)議。為了比較DSR協(xié)議優(yōu)化前后性能，仿真對比分析了網(wǎng)絡(luò)的平均端到端時延、業(yè)務(wù)接收速率、路由開銷和丟包率指標。

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

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

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

圖4 業(yè)務(wù)接收速率Fig.4 Receiving rate of traffic

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

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

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

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

圖7 丟包率Fig.7 Packet loss rate

仿真實驗結(jié)果充分表明，與傳統(tǒng)DSR 協(xié)議和現(xiàn)有的DT_DSR優(yōu)化方法相比，本文所提的FA_DSR優(yōu)化方法能有效降低網(wǎng)絡(luò)的路由開銷，減少端到端時延，提高業(yè)務(wù)的接收速率，降低丟包率。該優(yōu)化方法可以為無人機自組網(wǎng)提供穩(wěn)定高效的路由服務(wù)，保障無人機自組網(wǎng)的通信質(zhì)量。

4 結(jié)論與展望

本文在傳統(tǒng)DSR 協(xié)議的基礎(chǔ)上，提出了一種基于螢火蟲算法的無人機自組網(wǎng)DSR 協(xié)議優(yōu)化方法，利用螢火蟲算法來優(yōu)化DSR協(xié)議的路由發(fā)現(xiàn)過程。本文方法雖然增加了路由算法的復(fù)雜度和請求報文的長度，但仿真實驗表明，提出的協(xié)議優(yōu)化方法與傳統(tǒng)的DSR 協(xié)議相比，提高了網(wǎng)絡(luò)的性能，降低了網(wǎng)絡(luò)的路由開銷。

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