基于遺傳算法的無人機自組網吞吐量優化方法

劉建強，張森林，霍 帥，王 毅，陳 宇

(1.鄭州航空工業管理學院 電子信息學院, 河南 鄭州 450046;2.鄭州航空工業管理學院 航空航天電子信息技術河南省協同創新中心，河南 鄭州 450046；3.鄭州航空工業管理學院 河南省通用航空技術重點實驗室，河南 鄭州 450046；4.鄭州航空工業管理學院 科技處, 河南 鄭州 450046)

0 引 言

無人機自織網可用于應急通信場合［1］。無人機承擔通信節點的作用，而無人機間的空空鏈路及無人機對地面的空地鏈路則是網絡的通信鏈路［2］。典型的無人機自組網如圖1 所示。無人機自組網的吞吐量是一個重要的性能指標［3］。

在通信網絡初始部署時，由于缺乏足夠的需求信息，分配給無人機的位置可能不是最佳的，從而導致吞吐量不是最優。

為達成吞吐量最優，在網絡運行過程中，無人機節點可以收集有關用戶位置及其數據速率需求的信息，利用這些信息構建網絡的全局視圖，進而優化各種網絡性能指標。本文提出了一種基于遺傳算法的近似算法，用于優化無人機節點的位置和無人機節點與用戶的連接關系，進而使吞吐量最大化。

1 研究進展和問題分析

無人機的位置影響各種網絡性能指標，如吞吐量、覆蓋范圍、連接和收益。為解決通信容量與流量需求之間的不匹配問題，文獻［4］開發了一種通過控制無人機航向角來優化中繼鏈路性能的算法。文獻［5］提出了一種用于最優端到端通信鏈的分散移動控制算法，該算法使用一組無人機充當通信中繼節點?？刂破魇褂秒S機近似計算優化通信目標函數，將無人機虛擬控制點的位置驅動到優化后的中繼位置。文獻［6］對干擾容量的影響因素進行了理論分析，并導出了容量的閉合表達式，該表達式可用于確定無人機的最佳位置。文獻［7］認為，路由協議應考慮中繼放置服務，為充當中繼節點的無人機找到理想位置，從而避免無人機運動對視頻傳播的影響，并提出了一種無人機中繼放置機制，以支持具有令人滿意的體驗質量（QoE）的實時視頻的傳輸。文獻［8］提出了多種分布式網關選擇算法和基于云的穩定性控制機制。文獻［9］提出了一種在無人機自組網中基于集群的控制平面消息管理，基于無人機上下文信息，控制器可以在不傳輸控制消息的情況下預測無人機信息，進而優化位置信息。

然而，上述算法大多考慮單個無人機的位置優化，或者在考慮多個無人機節點位置優化時，沒有考慮用戶流量需求帶來的影響。實際上，一方面，無人機節點間的距離影響對應的鏈路容量，進而影響吞吐量；另一方面，當用戶節點處于多個無人機節點的覆蓋范圍時，選擇不同的無人機節點服務，也會影響網絡整體的吞吐量。

如圖2 所示的網絡和用戶、用戶之間通信流量需求如表1 前兩例所示，由于C2連接的無人機節點不同，導致使用圖2（a）方案獲得的吞吐量為10，使用圖2（b）方案獲得的吞吐量為19。統計數據如表1 后兩列所示。

表1 節點選擇影響吞吐量

圖2 用戶節點和無人機節點的連接對吞吐量的影響

從上述分析可以看出，通過優化無人機節點的位置以及無人機節點與服務用戶之間的連接關系，無人機網絡系統的吞吐量得到優化。

2 系統建模

2.1 問題描述

假設在既定地域內，有m個用戶需要進行通信，現擬使用n架具有組網功能的無人機提供通信服務。如圖3(a)所示，空心圓點表示一定區域內的用戶節點，實心圓點表示自組織網絡中的無人機節點。每個無人機節點可為多個用戶節點提供通信服務，但每個用戶節點在同一時間只可選擇一個無人機節點享受服務，無人機節點間按自組織的方式連接成網絡。圖3(b)是圖3(a)的二維示意描述。

圖3 無人機自組織網絡服務區域用戶示意

2.2 模型建立

2.2.1 系統表示

記該系統為S（V，C，T）。其中V為該區域內的無人機節點，共有n個；C代表該區域內的通信用戶，共有m個；T為系統中的流量需求。每個無人機節點或用戶節點的位置Pi=(pi(x),pi(y),pi(z))。顯然，節點均處于一個三維空間。由于所討論的吞吐量和節點間距離相關，二維平面和三維空間在距離上沒有本質差別，為了表述方便，本文擬在二維空間來描述。

2.2.2 數據鏈路

用E來表示無人機節點間的鏈路集合，則圖G（V，E）可表示該區域內的無人機自組織網絡。記該圖的鄰接矩陣為A，即

一條通信鏈路au,v存在兩個無人機節點u和v之間當且僅當它們之間的距離在彼此的傳輸范圍內。也就是

這里RV2V是無人機之間通信的最大傳輸范圍，而pu和pv分別表示無人機u和v的位置。

若有兩個以上的節點存在一個無人機節點中，則選擇一個距離較近的節點建立連接。本文假設所有鏈接都是對稱的。任何兩個無人機之間都存在一條路徑，即圖G是連通的。

每個無人機可以同時與所有相鄰無人機通信而不會干擾其他無人機的通信。無人機到無人機的通信最大傳輸范圍是RV2V。無人機到用戶的通信最大傳輸范圍是RV2C。無人機到無人機的最大通信傳輸范圍大于無人機到用戶的最大通信傳輸范圍，即RV2V≥RV2C。

無人機及其相關用戶通信信道與相鄰無人機之間使用的信道不同。也就是說，如果cu表示無人機u與相關用戶通信所使用的信道，則?u∈V，k∈N(u),使cu≠ck，其中N(u)表示u的鄰居的集合。這可有效地消除相鄰無人機關聯用戶之間的干擾。

網絡G服務的所有終端記為C(G)，無人機u∈V提供通信服務的用戶集合記為C(u)。假設每個用戶只從一個無人機節點處得到通信服務，所有的無人機節點覆蓋全部用戶，即

無人機和用戶之間的關聯關系用矩陣B表示，即

一條通信鏈路bu,v存在無人機節點v和用戶節點u之間當且僅當它們之間的距離在彼此的傳輸范圍內。也就是：

這里RV2C是無人機之間通信的傳輸范圍，而pu和pv分別表示無人機u和用戶v的位置。

2.2.3 流量需求

用無序偶（i,j）表示用戶i和用戶j之間的通信流，其流量需求大小用fij表示，則m個用戶之間的流量需求用矩陣T表示。

流（i,j）在自組網中經過的路徑記為Pij，鏈路l∈Pij的容量可以通過文獻［10］中的方法獲得。記cl,（i,j）為鏈路l∈Pij上流（i,j）的允許容量,當有多條流通過一段鏈路時，按照最大最小公平性原則分配各流的允許容量［11］。記Bij為流（i,j）的瓶頸鏈路上的允許容量，即

瓶頸鏈路可以是兩個無人機之間，也可以是一個無人機與其關聯用戶之間。

則該流量所達到的吞吐量是

當fij≤Bij時，流（i,j）可實現的最大吞吐量為fij。如果fij≥Bij，則可通過增加Bij來增加流（i,j）的吞吐量τij?？刂破款i鏈路上的節點彼此靠近可以實現這一目標。

2.2.4 吞吐量最大化描述

系統總吞吐量τ由給出。

在上述給定條件下，本文所有優化的目標為

(8.a)表示求取所有用戶流的總和最大化。(8.b)第一式表示由無人機節點V和用戶節點C組成，用戶節點間的流量矩陣為T，這是系統的初始輸入；第二式表示任何一個無人機節點最少有一個距離小于RV2V的無人機節點，第三式表示任何一個用戶節點最少有一個距離小于RV2C的無人機節點，它們一起表示所有無人機節點都連接在網絡上，所有用戶都由無人機節點提供通信服務，這是系統的假設條件。

3 算法設計

如前所述，用戶節點對無人機的選擇以及無人機節點的位置都將影響網絡的吞吐量，而吞吐量的優化又是一個復雜的過程。因此，本文引入遺傳算法，利用遺傳算法良好的全局優化能力來獲得吞吐量的最大值。遺傳算法［12］（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。算法要點包括以下幾個方面。

3.1 地域編號

為了方便使用遺傳算法，將無人機自組織網絡地域用多個正六邊形覆蓋，并為每個網格進行編號，每個無人機節點或用戶節點所處的位置用其所在的網格編號表示。如圖4 所示，無人機V1、V2、V3、V4分別處于15、60、43和46號網格處。

圖4 無人機自組織網絡地域網格化示意

顯然，正六邊形的邊長越小，其所需網格數越多，與此同時，所描述的位置越精確。為了表征地域被正六邊形劃分的細膩程度，本文稱正六邊形的邊長為粒度半徑。

3.2 確定無人機節點之間的鄰接矩陣

無人機自組織網絡的自組織特性表現在在有效通信范圍內，可以自主地和其他節點連接，即根據無人機節點集{Vi}，確定對應的鄰接矩陣A。

根據文獻［10］，在相關因素如發射功率、噪聲功率、信道相同的情況下，兩個節點之間距離越近，則其對應的鏈路容量越大。

因此，無人機節點之間鏈路生成可以采用如下方法：對于{Vi}中的任何一個節點u，計算和其他節點的空間距離，選擇最近節點v*＝arg min|pu pv|并與之建立鏈路，即au,v= 1。

由于上述方法是選擇距離最近的節點作為鄰接節點，因此總能保證點對點之間鏈路容量最大。在此基礎上進行優化，可以縮短優化過程。

根據鄰接矩陣A，可以使用Dijkstra 算法得到兩個節點之間的最短路徑P。

3.3 確定用戶和無人機之間的關聯矩陣

如前所述，用戶選擇不同的無人機節點可能導致系統的吞吐量不同，因此需要優化用戶和無人機之間的連接關系。

若用戶i和對端j的流量需求為fij，該用戶總的流量需求為無人機節點g的所有鏈路容量之和記為Tg。用戶i僅處于一個無人機節點g的有效通信范圍RV2C內，則直接連接到該無人機上；但是如果處于多個無人機節點的有效通信范圍內，則需要選擇連接在哪個無人機上。記連接在無人機節點g上的用戶為Cg，則Cg按下式確定。

根據的結果，即可確定關聯矩陣B中的bg,*。根據這種方法，同樣可以得到其他無人機節點的關聯矩陣元素，進而得到關聯矩陣B。

利用關聯矩陣B和流量矩陣T和3.2 節中獲得的P，即可求得各流（i,j）在鏈路l上的允許容量cl,（i,j），進而求得（i,j）的瓶頸容量Bij。

接下來的過程主要是通過控制無人機節點的位置來增加Bij對應的鏈路容量。

3.4 確定無人機節點位置移動的范圍

無人機可部署位置由兩方面的因素決定：服務對象即用戶的位置和鄰居無人機節點的位置。要求其部署位置離其用戶的距離不大于RV2C，離其鄰居無人機節點的位置不大于RV2V。其部署范圍如圖5 所示。以相鄰節點為圓心，以RV（不大于RV2V）為半徑畫圓；以用戶位置為圓心，以RC（不大于RV2C）為半徑畫圓，則所有圓的交集即為該無人機部署的可選位置。顯然，在這個范圍內，該無人機節點和其他無人機節點以及用戶都能保證正常的連接。本文稱RC和RV為位置約束半徑。顯然，約束半徑越大，則無人機可移動優化范圍越大，反之亦然。

圖5 位置約束半徑示意圖

如圖5 所示，以V3的可移動優化范圍為例，分別以其鄰居無人機節點V1、V2、V4為圓心，以小于RV2V的RV為半徑做圓；以其用戶節點C6為圓心，以小于RV2C的RC為半徑做圓，四個圓的重疊部分H 即為V3可移動優化的范圍。同理，可以確定其他無人機節點的可移動范圍。

3.5 編碼并使用遺傳算法進行優化

遺傳算法求解優化問題首先要對問題進行編碼形成種群，然后對種群進行遺傳操作。

3.5.1 編碼和種群初始化

優化對象是無人機節點的位置，為了方便使用經典遺傳算法，這里進行二進制編碼。由圖4 和圖5可以得到無人機可移動優化位置編號結果，如圖6所示。例如無人機節點V3的可選擇優化位置為{17，30，36，37，50}，該集合共5 個位置，可以使用3 位二進制數進行編碼，如表2所示。

表2 節點位置遺傳編碼

圖6 遺傳編碼示意圖

將每一個無人機節點都按上述方法進行編碼，按無人機序號將二進制字符串連接在一起，就是對地域內的無人機位置的一種表示。

假設第i個無人機節點位置的編碼為Code(i),則一個可能的位置方案對應的染色體編碼為：

求和表示的是字符串的連接。按照上述方法生成多個染色體，組成種群。

3.5.2 依據適應值進行遺傳操作

1）適應值計算

染色體n對應的網絡吞吐量用τ(n)表示，則

其中τi,j(n)表示染色體n中由用戶i到j的流量值。

每個染色體編碼都有一個適應值，該值是評價該染色體的依據。對于本優化問題，適應度函數設計為：

其中τm,τavg分別為當前代染色體的最大和平均吞吐量。

這個適應度函數有以下特點：適應值范圍為（0，1）；最大吞吐量對應的適應值為1，吞吐量為均值的染色體適應度為0.5；越靠近最優值，其適應值變化越靈敏，而在平均值以下，則下降更快。其好處在于：在算法初期盡快淘汰適應值較低的個體；在算法后期有效地拉開最優解附近點的適應值距離，避免陷入次優解。

2）染色體復制操作

當執行復制操作時，染色體n以概率進入下一代種群。

3）染色體雜交操作

經典的遺傳算法雜交算子是選擇兩個染色體，隨機選擇一個雜交位i，然后兩個染色體相互對應的交換從i+ 1 到末位的位段。對于本問題來說，由于染色體分段表征多個無人機節點的位置，若隨機選擇雜交位，可能會使雜交位對應的無人機節點位置表征錯誤。例如，若染色體中表征V3 的基因段為001 和100，若雜交點為2，則雜交后為基因段為000和101，而101為無效基因。

為避免這種情況，此處對經典遺傳算法進行改進，限定雜交位置為各基因段的連接點，即可能的雜交位置為從而保證各位基因段的完整性。

4）染色體變異操作

經典的變異算子在染色體上隨機產生變異位，即相應位取反，直接使用，同樣會產生無效基因。如對于表7 中的基因段100，變異位選擇了2 或3 位，都會產生無效基因。為避免這種情況，此處變異算子在經典變異算子的基礎上增加基因健康檢驗，若出現無效基因，則重復經典基因算子，直到產生的基因是合法的為止。

3.5.3制定終止準則

停止準則可以表示為算法執行的最大代數。對于本問題來說，吞吐量最大就是各用戶的流量需求總和若位置優化的吞吐量達到該值，優化可以結束；另一個條件是系統達不到用戶的流量需求量，這時若優化的吞吐量最大值一直沒有明顯的提高，則可以終止迭代并輸出當前吞吐量值作為問題的優化結果。

上述算法可以用如算法1 的偽代碼來表示。首先將考察的地域進行網格化；第2行生成無人機節點i的可選擇位置Po(i)，供優化選擇使用；第6行使用隨機的方法在Po(i)中選擇一個位置，作為對應無人機位置優化的實現；第8行使用字符串連接的方式獲取一個染色體Code(i)，并通過循環的方式獲得多個染色體，形成初始種群；第10 行是遺傳算法的終止條件，其中表示最近多代最大吞吐量的平均值，表示當前吞吐量和平均最大吞吐量的差值大于一定量；第11 行是計算當前種群中每個染色體的適應值；第12 至14 行根據前文所述的遺傳算子進行染色體操作；第15 行求得當前進化的群體中最大的吞吐量值；第18行則是在結束進化后，根據最大吞吐量的值進行解碼，從而得到對應無人機的位置。該優化的位置可以通過數據鏈路發送給各無人機，由飛控系統執行對應操作，控制無人機到目標位置，從而達到最大的網絡吞吐量。

算法1 基于遺傳算法的無人機位置優化輸入:無人機自組網拓撲及用戶流量需求輸出:優化后的位置1 GriddingRegion()2 Po(i) ←OptionalPositionForUAV()3 generation=0 4 for i=0;i＜=Npop;i++5 for j=0;j＜=Nuav;j++6 P(j) ←InitalizePositions(Po(j))7 end for 8 Nuav Code（P(j)）)Code(i) ←∑j = 0 end for 10while(τ ≠∑i ∑jfij or||9 τ --τm ≥δ)do 11Fitness=Evaluate(Pop(generation))12Reproduction(Pop(generation))13Crossover(Pop(generation))14Mutation(Pop(generation))15 τm = MaxThought(Pop(generation))16generation++17end while 18Pmax ←DeCode(τm)

4 仿真結果

利用MATLAB 及其中的GA 工具箱進行了仿真。首先，生成地域內的通信用戶位置以及用戶對流量的需求，然后依照上述算法生成無人機節點位置，使得生成的圖是連通的。

無人機高度保持在200 米。無人機對無人機通信的傳輸功率為2瓦，而無人機對無人機通信的傳輸距離RV2V保持在500 米。這意味著，如果任何兩個無人機之間的距離在500米以內，則它們之間可以存在連接。無人機對用戶通信的傳輸功率為1w，而無人機對用戶通信的傳輸距離RV2C保持在250m。為了估計鏈路的吞吐量，基于發送—接收距離和信道（傳播）模型估計SINR。然后，使用文獻［10］計算適當的吞吐量值。對于遺傳算法中的參數，種群規模取100，復制概率取0.4，交叉概率取0.4，變異概率取0.2。

4.1 無人機位置對鏈路流量和網絡吞吐量的影響

表3 顯示了四個流的細節（約束半徑200 米和粒度半徑30 米）。圖7（a）顯示了無人機的初始和最終（由算法確定）位置。在無人機的初始位置，沒有一個流量的需求得到滿足。然而，隨著無人機最終位置的確定，流量2 和流量3 的需求得到充分滿足，流量1和流量4的吞吐量有所增加。

表3 吞吐量優化統計

圖7 位置優化對鏈路容量及網絡吞吐量影響

圖7（b）顯示出算法如何通過迭代進行。最大總吞吐量在代30時實現。在代5中，流3的需求得到滿足。此外，由于流1 和流4 共享一個瓶頸鏈路（即鏈路V2V3），因此在大多數情況下，它們的吞吐量是相同的。然而，在進化后期，流4的吞吐量略高于流1。當V3靠近V2時就會發生這種情況。在進化的三四代中，流4 的需求得到滿足（7Mbps），流1 的吞吐量略有增加，而流2 的吞吐量急劇下降。流量2 的吞吐量急劇下降是由鏈路V2V3的容量下降引起的。因此，此時，流1和流4正在與流2爭奪V3的位置。流1和4希望V3更接近V2，而流2希望V3更接近V4。最后由于流2對全網吞吐量提升效果更明顯而獲勝。

4.2 位置約束半徑（Position Constraint Radius，PCR）的影響

表4 顯示了四個流的詳細信息。表中顯示，隨著位置約束半徑的增大，吞吐量可能進一步提高。這是因為隨著位置約束半徑的增大，可以測試更多的無人機位置以提高吞吐量。

表4 吞吐量約束半徑影響統計

圖8 顯示出位置約束半徑如何影響吞吐量的改進。

圖8 位置約束半徑影響

在初始進化過程中，該算法對所有位置約束半徑產生相似的吞吐量。然而，在第11次進化中，位置約束半徑100m 對應的吞吐量落在位置約束半徑150m 和200m 對應的吞吐量之后。同樣，在第15 次進化中，位置約束半徑150m 對應的吞吐量落在位置約束半徑200m 對應的吞吐量之后。這是因為，位置約束半徑越小，無人機的可優化機動范圍就越受限。當位置約束半徑100m 時的可優化機動范圍是位置約束半徑為150m 和200m 時可優化機動范圍的子集。因此，在第11 代進化過程中，該算法嘗試在位置約束半徑為150m 和200m 情況下的位置優化，可能導致性能改進。但是，這些導致性能改進的位置可能落在位置約束半徑為100m 的可優化機動范圍之外。類似地，在迭代15 中，該算法嘗試在位置約束半徑200m 且不在位置約束半徑150m 的范圍內進行位置優化，從而導致吞吐量的提升。因此，當位置約束半徑較大時，與較小的半徑相比，可以獲得更大的吞吐量改進。

4.3 粒度半徑(Particle Size Radius,PSR)的影響

圖9 顯示了當算法搜索（近似）最優無人機位置時粒度半徑的影響。在初始代中，較大的粒度半徑會導致吞吐量的急劇增加；稍后，較小的粒度半徑將逐漸增加。當粒度半徑較大時，算法收斂速度較快，但通常情況下，確定的解不如粒度半徑較小時接近最優解。粒度半徑越小，算法收斂速度越慢，但確定的解越接近最優解。

圖9 粒度半徑影響

5 總 結

本文提出了一種基于遺傳算法的近似算法，用于控制無人機的位置，優化無人機自組網的拓撲，進而使吞吐量最大化。仿真分析表明，該方法可以優化自組網的吞吐量，且優化速度和位置約束半徑和粒度半徑有關。本方法可以用于中繼通信的無人機自組網提升吞吐量使用。