徐意祥，李莉

（北京航空航天大學(xué)自動化科學(xué)與電氣工程學(xué)院，北京100191）

無人機編隊飛行與協(xié)同通信，是當前無人機編隊的熱門研究課題[1-3]。無人機可以用于軍事作戰(zhàn)，電子偵查，通信中繼，還可以用于民用。無人機群的突出作用，在于利用無人機的數(shù)量優(yōu)勢，在各種工作場景中發(fā)揮協(xié)同的作用。因此協(xié)同控制好無人機編隊，提高無人機編隊的使用效率，就顯得十分重要。無人機編隊自主重構(gòu)是為了按照需要，快速組成給定編隊隊形[4-6]；無人機分簇算法，是為了在無人機編隊的基礎(chǔ)上，為了提高無人機群的相互通信效率。

無人機外出執(zhí)勤遠離路基基站人員控制，因此需要無人機群具有一定的智能性。目前傳統(tǒng)編隊算法在無人機的隊形重構(gòu)上還不夠智能化，也不夠快速，同時無人機編隊的協(xié)同通信的效率還不夠高。因此需要設(shè)計算法，完成無人機自主重構(gòu)[7-10]，并且提高無人機之間的協(xié)同通信效率。

通過在Linux系統(tǒng)上使用NS3仿真軟件[11-13]，首先設(shè)計無人機類，配置無人機間的通信協(xié)議，設(shè)置無人機節(jié)點數(shù)量，配置仿真環(huán)境。然后設(shè)計魚群算法實現(xiàn)無人機編隊的快速自主重構(gòu)，同時采用HEED分簇算法實現(xiàn)無人機群分簇[14-17]。

該仿真暫設(shè)定無人機數(shù)量9架。只需要給定隊形，無人機就可以自動實現(xiàn)隊形的快速自主重構(gòu)。同時按照設(shè)計的HEED算法實現(xiàn)分簇，提高無人機的協(xié)同通信效率。該系統(tǒng)仿真證明，算法智能性好，編隊自主重構(gòu)快速，通信效率提高，容易調(diào)整維護，適應(yīng)性強，魯棒性強，能很好地解決無人機編隊重構(gòu)和協(xié)同通信的問題[18-21]。因此，筆者采用的魚群算法和HEED分簇算法進行無人機系統(tǒng)仿真設(shè)計。

1 系統(tǒng)設(shè)計

1.1 仿真環(huán)境設(shè)計

無人機群由多個無人機組成。魚群算法的關(guān)鍵在于：一是搜索目標位置，這需要通信協(xié)議的支持，保持無人機間的通信順暢。而通信是三維空間的，不是平面上的。因此只要能夠?qū)崿F(xiàn)無人機間的通信，在搜索目標位置的問題上，只需要確定初選簇頭節(jié)點，經(jīng)過正方形編隊隊形的位置計算，就可以完成目標位置的搜索；二是簇頭節(jié)點的競爭與選取，選取標準是無人機節(jié)點的自由度和無人機的能量參數(shù)，而無人機的自由度這一參數(shù)的確定是在通信范圍內(nèi)確定的一個半徑r內(nèi)的節(jié)點數(shù)量，同樣是取決于通信，上述已經(jīng)說明通信本身就是在三維空間實現(xiàn)；三是無人機的運動與重構(gòu)，然而本課題不涉及飛控算法的研究，因此只需要確定無人機的重構(gòu)算法是按照魚群算法重構(gòu)，但是至于在三維空間如何運動屬于飛控研究課題，不在本文研究范圍內(nèi)，因此在搜索到目標位置以后，就是按照魚群算法朝目標位置移動的過程，而且是在運動過程中繼續(xù)搜索更好目標位置。

因為本課題不涉及無人機的飛控算法，在滿足無人機群的編隊任務(wù)需求下，對上述魚群算法，HEED分簇算法以及混合路由協(xié)議進行仿真驗證。在復(fù)雜作戰(zhàn)任務(wù)情況下，加入飛控算法可以滿足實際三維空間飛機飛行需求，同時無人機間的通信也是三維的立體的，而魚群算法和HEED分簇算法是對編隊自主重構(gòu)算法和提高通信效率的設(shè)計，實際過程的重構(gòu)是魚群算法配合飛控算法完成自主重構(gòu)，對三位空間和二維空間都適用，魚群算法和HEED分簇算法的相關(guān)參數(shù)不涉及三維坐標，只和無人機節(jié)點自由度以及無人機能量有關(guān)。因此魚群算法和HEED分簇算法在二維空間仿真也是滿足研究課題需求的。故本文采用了二維空間的仿真。

1.2 無人機模型

建立單個無人機模型，根據(jù)仿真需求，完成無人機編隊自主重構(gòu)，分簇，實現(xiàn)無人機間的通信。無人機模型的主要參數(shù)有：無人機在仿真環(huán)境中的位置，無人機移動速度，無人機移動方向，無人機是否是簇頭節(jié)點，以及無人機的簇群成員，無人機視野，擁擠因子，無人機最大步長，無人機行為模式，鄰居通信節(jié)點的MAC地址，以及通信路由表等參數(shù)。

2 算法設(shè)計

2.1 魚群算法自主重構(gòu)

無人機群在執(zhí)勤作業(yè)過程中，面對不同的任務(wù)需求和障礙，適當改變編隊隊形，對提高無人機編隊的生存率和工作效率，是十分必要的。

仿真過程開始，無人機群隨機設(shè)定初始化為三角形初始隊形如圖1所示是在matlab中顯示的隨機初始化的無人機隊形，為三角形。

圖1 初始無人機隊形

目標隊形正方形在NS3的可視化界面下仿真如圖2所示。首先按照分簇算法選定簇頭節(jié)點無人機，并規(guī)定該無人機按照圓形軌跡運動，其他無人機按照魚群算法自主重構(gòu)逐漸形成編隊，并且最終按照圓形軌跡巡航。

圖2 正方形目標隊形

首先無人機群確定幾何中心附近無人機節(jié)點(x0,y0)，以該無人機為正方形中心，在空間中模擬一個正方形網(wǎng)格，網(wǎng)格交叉點就是各個無人機節(jié)點最終的目標位置，并給目標位置編號(l0,l1,......,l8)，對應(yīng)位置(x0,y0)，(x1,y1)……(x8,y8)。

以無人機的視野為半徑r的各個目標(l0,l1,......,l8)位置周圍，統(tǒng)計無人機節(jié)點數(shù)量nx。數(shù)量nx的大小作為目標位置周圍的無人機節(jié)點的密度。魚群算法自主重構(gòu)流程圖如圖3所示。

圖3 魚群算法自主重構(gòu)流程圖

無人機節(jié)點尋找視野范圍內(nèi)的目標位置lx，并得到目標位置lx的無人機濃度nx。無人機節(jié)點按照步長p移動，方向是濃度最低的目標位置lx。

無人機節(jié)點準確來到目標位置lx，完成該位置的自主重構(gòu)。其他剩余位置以此類推。

整個算法中，首先以其中一個無人機為參照點，該無人機作圓形軌跡的巡航運動。以該無人機為中心，計算出正方形的隊形的所有空位置，作為目標位置。其他無人機在搜索過程中，計算目標位置無人機濃度，并選擇目標位置，按照步長移動，直至到達目標位置為止。尋找目標位置是魚群的覓食過程，而計算目標位置濃度是為了避免魚群的追尾行為。

2.2 無人機編隊HEED分簇算法

HEED是無線傳感網(wǎng)的一種多跳分簇算法，簇頭選取考慮兩項重要參數(shù)：剩余能量和簇間通信開銷。HEED在選取簇頭時都考慮節(jié)點剩余能量，但是簇間通信開銷反應(yīng)了節(jié)點和鄰居節(jié)點的距離和節(jié)點自由度，同時還被用作決定節(jié)點是否加入分簇的參考指標。低能量的簇群會從新限定通信范圍，而高能量的簇群則擴大通信范圍，覆蓋更多的簇群。HEED算法為網(wǎng)絡(luò)提供統(tǒng)一的簇頭分布和更好的負載平衡。HEED算法是一個分布式分簇算法，簇頭節(jié)點從分散的傳感網(wǎng)絡(luò)中選取。HEED綜合考慮了節(jié)點剩余能量和簇間通信開銷，不像LEACH隨機選出簇頭節(jié)點。在HEED算法中，節(jié)點被唯一映射到一個簇群中，并且可以直接和簇頭通信。但是該算法在選取簇頭時，節(jié)點多次重復(fù)發(fā)送數(shù)據(jù)直到找到最小通信能耗的節(jié)點作為自己的簇頭，否則選自己為簇頭。這樣勢必帶來一定的通信開銷和能量損耗。

仿真采用改進的HEED算法，在選擇簇頭時，依據(jù)能量、節(jié)點自由度，采取競爭機制選取簇頭。其余節(jié)點依照改進的分簇算法選擇合適的簇頭節(jié)點請求加入。完成分簇。具體設(shè)計過程如下：

首先依照節(jié)點剩余能量Ei'和節(jié)點自由度mi，統(tǒng)計候選簇頭節(jié)點；

剩余能量計算公式：Ei'=Ei-Et-qi·X-qi'·t，其中Ei為無人機i的初始能量，Et是利用NS3軟件的能量模塊統(tǒng)計處的通信能耗，qi是無人機的單位距離飛行能耗，X為飛行路程，qi'是無人機i的單位時間巡航能耗，t為巡航時間。

以平均無人機編隊的能量分布和負載均衡為考量，在無人機編隊中選出剩余能量最多Ei和自由度最高mi的無人機節(jié)點作為簇頭節(jié)點Ci；

選擇簇頭的標準：gi=λ1·mi+λ2·Ei

簇頭的參數(shù)指標gimax當選簇頭，其中λ1和λ2為常系數(shù)。

沒有當選簇頭節(jié)點的節(jié)點以到簇頭節(jié)點的距離di、簇群節(jié)點數(shù)量nc為參考，選擇最優(yōu)的簇頭，并申請加入該簇群；

所有的無人機節(jié)點作為簇頭或者普通成員節(jié)點，完成分簇；如果觸發(fā)了重新分簇的條件，比如簇頭節(jié)點能量過低或者通信阻塞，則在簇內(nèi)重新選擇簇頭，替代原有簇頭；如果編隊重組，則觸發(fā)簇頭競爭機制，回到第一步重新分簇。無人機群的HEED分簇算法流程如圖4所示。

2.3 無人機編隊路由算法

整個仿真中路由協(xié)議的算法是貫穿整個無人機網(wǎng)絡(luò)協(xié)調(diào)通信與交互信息的關(guān)鍵。路由的算法主要分為路徑發(fā)現(xiàn)模塊，路徑維護模塊，路徑選擇模塊3部分，同時主要分為編隊之前和分簇之后的兩個階段。在編隊之前主要是路由形成過程，需要動態(tài)路由算法，在完成分簇之后，編隊自主重構(gòu)也完成了，這是就會進行路由維護，需要靜態(tài)路由算法。

圖4 HEED分簇算法流程圖

路徑發(fā)現(xiàn)模塊調(diào)整了無人機節(jié)點對PREQ和PREP幀的處理方法，從信號幀中提取無人機節(jié)點的位置信息，是否有簇頭標志，無人機的自由度，無人機的MAC地址等，并配合自主重構(gòu)算法和HEED分簇算法完成通信及分簇的必要通信，并產(chǎn)生無人機節(jié)點間通信的路由路徑，同時保存到路由表中，在路由表中按照編號產(chǎn)生路由表。路徑發(fā)現(xiàn)模塊是路由算法的核心模塊。

路徑維護模塊負責維護已經(jīng)生成的并且編隊穩(wěn)定的路由表。路由表的每條路徑都有一定的生存時間，當編隊自主重構(gòu)觸發(fā)或者分簇算法觸發(fā)之后，會重新回到路由發(fā)現(xiàn)模塊，并且重新產(chǎn)生新的路由表，刪除舊的路由表。在維護路由表過程中，每一個節(jié)點都會保存一條到達簇頭的路由表，而簇頭節(jié)點則會保存到達每一個普通節(jié)點的路由表。當某個節(jié)點失效時，路徑上的節(jié)點收到通知后刪除該包含節(jié)點的路由。

路徑選擇模塊則是在同時可用多條路徑時，為無人機節(jié)點選擇路徑最短通信最不擁堵的路徑，并將該路徑設(shè)為主路徑，其他路徑按照同樣的標準按照序號備份。主路徑失效后或者不是最優(yōu)，按照序號選擇備份路徑，并取代主路徑。如果節(jié)點之間跳數(shù)過多超過2跳時，則會選擇跳數(shù)最少的路徑，通常是找簇頭節(jié)點，由簇頭節(jié)點充當中間節(jié)點。否則跳數(shù)小于等于兩跳時，會選擇路徑最短的路徑。

AODV和OLSR混合路由建立過程是為了建立無人機節(jié)點間的多條通信路由，具體步驟如下：

源節(jié)點啟動路由發(fā)現(xiàn)機制，查找AODV路由表，看看是否存在目標節(jié)點的路由信息。在形成編隊自主重構(gòu)和完成分簇后，通常直接選擇選擇路徑Metric值最小的主路徑進行通信。在編隊過程中，沒有目標節(jié)點的穩(wěn)定路徑，需要啟動路由發(fā)現(xiàn)過程。源節(jié)點構(gòu)造Improved PREQ幀，并在網(wǎng)絡(luò)中廣播Improved PREQ幀。AODV協(xié)議原來的路由信息表包括下一個目的節(jié)點的MAC地址、目的節(jié)點的MAC地址、發(fā)現(xiàn)重試次數(shù)以及路徑狀態(tài)標志FLAGS、路徑空時鏈路METRIC值、目的節(jié)點序列號SN、路由發(fā)現(xiàn)過程超時的時間、路由信息表過期時間；改進的路由協(xié)議新增了第一跳鄰居節(jié)點的MAC地址，用于記錄距離目標節(jié)點只有一跳的鄰居節(jié)點MAC地址。

中間節(jié)點處理Improved PREQ幀，接收一個新的PREQ幀，按照OLSR協(xié)議的算法，決定是否更新到源節(jié)點的路由，并判斷是否繼續(xù)轉(zhuǎn)發(fā)該幀。如果路由表沒有這條路徑，就新建一條路徑，否則查看所收到的PREQ幀中源節(jié)點的序列號及Metric值，再判斷要不要更新路由表和繼續(xù)轉(zhuǎn)發(fā)該幀信號；如果本節(jié)點是目的節(jié)點，則不用轉(zhuǎn)發(fā)，否則繼續(xù)轉(zhuǎn)發(fā)。目的節(jié)點可能收到多個來自同相同源節(jié)點的PREQ幀，根據(jù)路由表的相關(guān)更新算法，判斷最優(yōu)路徑，丟掉非最優(yōu)路徑。

目的節(jié)點收到轉(zhuǎn)發(fā)過來的PREQ幀時，根據(jù)路由算法，判斷是否更新路由，并向源節(jié)點發(fā)送PREP幀回復(fù)。

中間節(jié)點收到來自目的節(jié)點的PREP幀，按照之前保存的最優(yōu)路徑轉(zhuǎn)發(fā)PREP給源節(jié)點。

源節(jié)點收到目的節(jié)點的PREP幀后，在路由表中保存路徑，便完成了路由發(fā)現(xiàn)和保存過程。該混合路由算法流程如圖5所示。

3 仿真驗證

圖6是無人機群以簇頭無人機為中心，按照圓形軌跡運動，其余無人機節(jié)點按照魚群算法完成編隊自主重構(gòu)，形成的運動軌跡，該軌跡是在MATLAB下仿真得出的運動軌跡效果圖。最終無人機群基本完成圓形運動，軌跡圖顯示編隊的自主重構(gòu)效果良好。在自主重構(gòu)運動過程中，預(yù)定位置是以簇頭為中心的正方形網(wǎng)格的幾個點。

圖7描述的是無人機節(jié)點與各自目標位置的距離誤差。雖然距離誤差有些波動，但是最終程收斂狀態(tài)。說明魚群算法在自主重構(gòu)中的效果良好，并且收斂速度快。

圖5 路由算法流程圖

圖6 無人機群自主重構(gòu)過程運動軌跡

圖7 無人機隊形預(yù)定位置誤差

圖8顯示的是無人機群在完成自主重構(gòu)以后，形成的編隊狀態(tài)。黑色邊緣線節(jié)點是簇頭節(jié)點，是初始狀態(tài)下按照HEED分簇算法選取的無人機簇頭節(jié)點。

圖8 簇頭初始選擇

當自主重構(gòu)完成以后，分簇效果如圖8顯示選出的簇頭并不是最佳，而分簇算法在完成編隊以后會重新觸發(fā)競爭簇頭節(jié)點，中間節(jié)點是競爭之后選取的新節(jié)點。圖9中顯示該簇頭的自由度最高，通信效率有所提升。說明HEED分簇算法良好。

圖10顯示無人機群完成編隊的自主重構(gòu)，并且完成簇頭重新競爭之后的整個仿真效果圖，圖中顯示無人機群間的通信正常，并且以中間的簇頭節(jié)點無人機為中心，無人機間的通信效率有所提高，沒有發(fā)生通信阻塞情況。

4 結(jié) 論

無人機群采用魚群算法完成自主重構(gòu)正常，無人機群在給定編隊隊形情況下能夠快速自主重構(gòu)，完成編隊工作，收斂正常，無人機仿真飛行運動正常；分簇功能正常，分簇可以通過圖形界面形象展示簇群分布，可以通過圖形如圓形劃分標示簇群，更直觀反應(yīng)簇的分布和簇內(nèi)節(jié)點成員；分簇算法運行正常，簇頭選取正常，無人機節(jié)點可以正常請求離開和加入簇群；簇頭競爭機制正常，簇間通信良好；從生成仿真環(huán)境，開始運行仿真，采用反應(yīng)路由和按需路由混合的路由協(xié)議實現(xiàn)無人機群通信正常，通信穩(wěn)定；完成編隊自主重構(gòu)和分簇過程中，通信協(xié)議能夠有效為無人機群的協(xié)同提供良好的通信服務(wù)；完成分簇后和之前，通信協(xié)議的工作模式可以正常切換，通信效率提升，無人機節(jié)點通信負載減輕。

圖9 簇頭競爭選擇

圖10 無人機編隊的通信仿真