無人機(jī)系統(tǒng)編隊(duì)分簇網(wǎng)絡(luò)仿真研究

徐意祥，李莉

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

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

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

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

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

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

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

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

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

1.2 無人機(jī)模型

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

2 算法設(shè)計(jì)

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

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

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

圖1 初始無人機(jī)隊(duì)形

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

圖2 正方形目標(biāo)隊(duì)形

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

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

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

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

無人機(jī)節(jié)點(diǎn)準(zhǔn)確來到目標(biāo)位置lx，完成該位置的自主重構(gòu)。其他剩余位置以此類推。

整個(gè)算法中，首先以其中一個(gè)無人機(jī)為參照點(diǎn)，該無人機(jī)作圓形軌跡的巡航運(yùn)動(dòng)。以該無人機(jī)為中心，計(jì)算出正方形的隊(duì)形的所有空位置，作為目標(biāo)位置。其他無人機(jī)在搜索過程中，計(jì)算目標(biāo)位置無人機(jī)濃度，并選擇目標(biāo)位置，按照步長移動(dòng)，直至到達(dá)目標(biāo)位置為止。尋找目標(biāo)位置是魚群的覓食過程，而計(jì)算目標(biāo)位置濃度是為了避免魚群的追尾行為。

2.2 無人機(jī)編隊(duì)HEED分簇算法

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

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

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

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

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

選擇簇頭的標(biāo)準(zhǔn)：gi=λ1·mi+λ2·Ei

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

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

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

2.3 無人機(jī)編隊(duì)路由算法

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

圖4 HEED分簇算法流程圖

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

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

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

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

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

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

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

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

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

3 仿真驗(yàn)證

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

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

圖5 路由算法流程圖

圖6 無人機(jī)群自主重構(gòu)過程運(yùn)動(dòng)軌跡

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

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

圖8 簇頭初始選擇

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

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

4 結(jié) 論

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

圖9 簇頭競(jìng)爭選擇

圖10 無人機(jī)編隊(duì)的通信仿真