無人機系統編隊分簇網絡仿真研究

徐意祥，李莉

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

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

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

通過在Linux系統上使用NS3仿真軟件[11-13]，首先設計無人機類，配置無人機間的通信協議，設置無人機節點數量，配置仿真環境。然后設計魚群算法實現無人機編隊的快速自主重構，同時采用HEED分簇算法實現無人機群分簇[14-17]。

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

1 系統設計

1.1 仿真環境設計

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

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

1.2 無人機模型

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

2 算法設計

2.1 魚群算法自主重構

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

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

圖1 初始無人機隊形

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

圖2 正方形目標隊形

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

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

圖3 魚群算法自主重構流程圖

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

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

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

2.2 無人機編隊HEED分簇算法

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

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

首先依照節點剩余能量Ei'和節點自由度mi，統計候選簇頭節點；

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

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

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

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

沒有當選簇頭節點的節點以到簇頭節點的距離di、簇群節點數量nc為參考，選擇最優的簇頭，并申請加入該簇群；

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

2.3 無人機編隊路由算法

整個仿真中路由協議的算法是貫穿整個無人機網絡協調通信與交互信息的關鍵。路由的算法主要分為路徑發現模塊，路徑維護模塊，路徑選擇模塊3部分，同時主要分為編隊之前和分簇之后的兩個階段。在編隊之前主要是路由形成過程，需要動態路由算法，在完成分簇之后，編隊自主重構也完成了，這是就會進行路由維護，需要靜態路由算法。

圖4 HEED分簇算法流程圖

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

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

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

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

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

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

目的節點收到轉發過來的PREQ幀時，根據路由算法，判斷是否更新路由，并向源節點發送PREP幀回復。

中間節點收到來自目的節點的PREP幀，按照之前保存的最優路徑轉發PREP給源節點。

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

3 仿真驗證

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

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

圖5 路由算法流程圖

圖6 無人機群自主重構過程運動軌跡

圖7 無人機隊形預定位置誤差

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

圖8 簇頭初始選擇

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

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

4 結 論

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

圖9 簇頭競爭選擇

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