劉建強(qiáng)，張森林，霍 帥，王 毅，陳 宇

(1.鄭州航空工業(yè)管理學(xué)院 電子信息學(xué)院, 河南 鄭州 450046;2.鄭州航空工業(yè)管理學(xué)院 航空航天電子信息技術(shù)河南省協(xié)同創(chuàng)新中心，河南 鄭州 450046；3.鄭州航空工業(yè)管理學(xué)院 河南省通用航空技術(shù)重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450046；4.鄭州航空工業(yè)管理學(xué)院 科技處, 河南 鄭州 450046)

0 引 言

無(wú)人機(jī)自織網(wǎng)可用于應(yīng)急通信場(chǎng)合［1］。無(wú)人機(jī)承擔(dān)通信節(jié)點(diǎn)的作用，而無(wú)人機(jī)間的空空鏈路及無(wú)人機(jī)對(duì)地面的空地鏈路則是網(wǎng)絡(luò)的通信鏈路［2］。典型的無(wú)人機(jī)自組網(wǎng)如圖1 所示。無(wú)人機(jī)自組網(wǎng)的吞吐量是一個(gè)重要的性能指標(biāo)［3］。

在通信網(wǎng)絡(luò)初始部署時(shí)，由于缺乏足夠的需求信息，分配給無(wú)人機(jī)的位置可能不是最佳的，從而導(dǎo)致吞吐量不是最優(yōu)。

為達(dá)成吞吐量最優(yōu)，在網(wǎng)絡(luò)運(yùn)行過(guò)程中，無(wú)人機(jī)節(jié)點(diǎn)可以收集有關(guān)用戶(hù)位置及其數(shù)據(jù)速率需求的信息，利用這些信息構(gòu)建網(wǎng)絡(luò)的全局視圖，進(jìn)而優(yōu)化各種網(wǎng)絡(luò)性能指標(biāo)。本文提出了一種基于遺傳算法的近似算法，用于優(yōu)化無(wú)人機(jī)節(jié)點(diǎn)的位置和無(wú)人機(jī)節(jié)點(diǎn)與用戶(hù)的連接關(guān)系，進(jìn)而使吞吐量最大化。

1 研究進(jìn)展和問(wèn)題分析

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

然而，上述算法大多考慮單個(gè)無(wú)人機(jī)的位置優(yōu)化，或者在考慮多個(gè)無(wú)人機(jī)節(jié)點(diǎn)位置優(yōu)化時(shí)，沒(méi)有考慮用戶(hù)流量需求帶來(lái)的影響。實(shí)際上，一方面，無(wú)人機(jī)節(jié)點(diǎn)間的距離影響對(duì)應(yīng)的鏈路容量，進(jìn)而影響吞吐量；另一方面，當(dāng)用戶(hù)節(jié)點(diǎn)處于多個(gè)無(wú)人機(jī)節(jié)點(diǎn)的覆蓋范圍時(shí)，選擇不同的無(wú)人機(jī)節(jié)點(diǎn)服務(wù)，也會(huì)影響網(wǎng)絡(luò)整體的吞吐量。

如圖2 所示的網(wǎng)絡(luò)和用戶(hù)、用戶(hù)之間通信流量需求如表1 前兩例所示，由于C2連接的無(wú)人機(jī)節(jié)點(diǎn)不同，導(dǎo)致使用圖2（a）方案獲得的吞吐量為10，使用圖2（b）方案獲得的吞吐量為19。統(tǒng)計(jì)數(shù)據(jù)如表1 后兩列所示。

表1 節(jié)點(diǎn)選擇影響吞吐量

圖2 用戶(hù)節(jié)點(diǎn)和無(wú)人機(jī)節(jié)點(diǎn)的連接對(duì)吞吐量的影響

從上述分析可以看出，通過(guò)優(yōu)化無(wú)人機(jī)節(jié)點(diǎn)的位置以及無(wú)人機(jī)節(jié)點(diǎn)與服務(wù)用戶(hù)之間的連接關(guān)系，無(wú)人機(jī)網(wǎng)絡(luò)系統(tǒng)的吞吐量得到優(yōu)化。

2 系統(tǒng)建模

2.1 問(wèn)題描述

假設(shè)在既定地域內(nèi)，有m個(gè)用戶(hù)需要進(jìn)行通信，現(xiàn)擬使用n架具有組網(wǎng)功能的無(wú)人機(jī)提供通信服務(wù)。如圖3(a)所示，空心圓點(diǎn)表示一定區(qū)域內(nèi)的用戶(hù)節(jié)點(diǎn)，實(shí)心圓點(diǎn)表示自組織網(wǎng)絡(luò)中的無(wú)人機(jī)節(jié)點(diǎn)。每個(gè)無(wú)人機(jī)節(jié)點(diǎn)可為多個(gè)用戶(hù)節(jié)點(diǎn)提供通信服務(wù)，但每個(gè)用戶(hù)節(jié)點(diǎn)在同一時(shí)間只可選擇一個(gè)無(wú)人機(jī)節(jié)點(diǎn)享受服務(wù)，無(wú)人機(jī)節(jié)點(diǎn)間按自組織的方式連接成網(wǎng)絡(luò)。圖3(b)是圖3(a)的二維示意描述。

圖3 無(wú)人機(jī)自組織網(wǎng)絡(luò)服務(wù)區(qū)域用戶(hù)示意

2.2 模型建立

2.2.1 系統(tǒng)表示

記該系統(tǒng)為S（V，C，T）。其中V為該區(qū)域內(nèi)的無(wú)人機(jī)節(jié)點(diǎn)，共有n個(gè)；C代表該區(qū)域內(nèi)的通信用戶(hù)，共有m個(gè)；T為系統(tǒng)中的流量需求。每個(gè)無(wú)人機(jī)節(jié)點(diǎn)或用戶(hù)節(jié)點(diǎn)的位置Pi=(pi(x),pi(y),pi(z))。顯然，節(jié)點(diǎn)均處于一個(gè)三維空間。由于所討論的吞吐量和節(jié)點(diǎn)間距離相關(guān)，二維平面和三維空間在距離上沒(méi)有本質(zhì)差別，為了表述方便，本文擬在二維空間來(lái)描述。

2.2.2 數(shù)據(jù)鏈路

用E來(lái)表示無(wú)人機(jī)節(jié)點(diǎn)間的鏈路集合，則圖G（V，E）可表示該區(qū)域內(nèi)的無(wú)人機(jī)自組織網(wǎng)絡(luò)。記該圖的鄰接矩陣為A，即

一條通信鏈路au,v存在兩個(gè)無(wú)人機(jī)節(jié)點(diǎn)u和v之間當(dāng)且僅當(dāng)它們之間的距離在彼此的傳輸范圍內(nèi)。也就是

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

若有兩個(gè)以上的節(jié)點(diǎn)存在一個(gè)無(wú)人機(jī)節(jié)點(diǎn)中，則選擇一個(gè)距離較近的節(jié)點(diǎn)建立連接。本文假設(shè)所有鏈接都是對(duì)稱(chēng)的。任何兩個(gè)無(wú)人機(jī)之間都存在一條路徑，即圖G是連通的。

每個(gè)無(wú)人機(jī)可以同時(shí)與所有相鄰無(wú)人機(jī)通信而不會(huì)干擾其他無(wú)人機(jī)的通信。無(wú)人機(jī)到無(wú)人機(jī)的通信最大傳輸范圍是RV2V。無(wú)人機(jī)到用戶(hù)的通信最大傳輸范圍是RV2C。無(wú)人機(jī)到無(wú)人機(jī)的最大通信傳輸范圍大于無(wú)人機(jī)到用戶(hù)的最大通信傳輸范圍，即RV2V≥RV2C。

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

網(wǎng)絡(luò)G服務(wù)的所有終端記為C(G)，無(wú)人機(jī)u∈V提供通信服務(wù)的用戶(hù)集合記為C(u)。假設(shè)每個(gè)用戶(hù)只從一個(gè)無(wú)人機(jī)節(jié)點(diǎn)處得到通信服務(wù)，所有的無(wú)人機(jī)節(jié)點(diǎn)覆蓋全部用戶(hù)，即

無(wú)人機(jī)和用戶(hù)之間的關(guān)聯(lián)關(guān)系用矩陣B表示，即

一條通信鏈路bu,v存在無(wú)人機(jī)節(jié)點(diǎn)v和用戶(hù)節(jié)點(diǎn)u之間當(dāng)且僅當(dāng)它們之間的距離在彼此的傳輸范圍內(nèi)。也就是：

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

2.2.3 流量需求

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

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

瓶頸鏈路可以是兩個(gè)無(wú)人機(jī)之間，也可以是一個(gè)無(wú)人機(jī)與其關(guān)聯(lián)用戶(hù)之間。

則該流量所達(dá)到的吞吐量是

當(dāng)fij≤Bij時(shí)，流（i,j）可實(shí)現(xiàn)的最大吞吐量為fij。如果fij≥Bij，則可通過(guò)增加Bij來(lái)增加流（i,j）的吞吐量τij?？刂破款i鏈路上的節(jié)點(diǎn)彼此靠近可以實(shí)現(xiàn)這一目標(biāo)。

2.2.4 吞吐量最大化描述

系統(tǒng)總吞吐量τ由給出。

在上述給定條件下，本文所有優(yōu)化的目標(biāo)為

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

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

如前所述，用戶(hù)節(jié)點(diǎn)對(duì)無(wú)人機(jī)的選擇以及無(wú)人機(jī)節(jié)點(diǎn)的位置都將影響網(wǎng)絡(luò)的吞吐量，而吞吐量的優(yōu)化又是一個(gè)復(fù)雜的過(guò)程。因此，本文引入遺傳算法，利用遺傳算法良好的全局優(yōu)化能力來(lái)獲得吞吐量的最大值。遺傳算法［12］（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。算法要點(diǎn)包括以下幾個(gè)方面。

3.1 地域編號(hào)

為了方便使用遺傳算法，將無(wú)人機(jī)自組織網(wǎng)絡(luò)地域用多個(gè)正六邊形覆蓋，并為每個(gè)網(wǎng)格進(jìn)行編號(hào)，每個(gè)無(wú)人機(jī)節(jié)點(diǎn)或用戶(hù)節(jié)點(diǎn)所處的位置用其所在的網(wǎng)格編號(hào)表示。如圖4 所示，無(wú)人機(jī)V1、V2、V3、V4分別處于15、60、43和46號(hào)網(wǎng)格處。

圖4 無(wú)人機(jī)自組織網(wǎng)絡(luò)地域網(wǎng)格化示意

顯然，正六邊形的邊長(zhǎng)越小，其所需網(wǎng)格數(shù)越多，與此同時(shí)，所描述的位置越精確。為了表征地域被正六邊形劃分的細(xì)膩程度，本文稱(chēng)正六邊形的邊長(zhǎng)為粒度半徑。

3.2 確定無(wú)人機(jī)節(jié)點(diǎn)之間的鄰接矩陣

無(wú)人機(jī)自組織網(wǎng)絡(luò)的自組織特性表現(xiàn)在在有效通信范圍內(nèi)，可以自主地和其他節(jié)點(diǎn)連接，即根據(jù)無(wú)人機(jī)節(jié)點(diǎn)集{Vi}，確定對(duì)應(yīng)的鄰接矩陣A。

根據(jù)文獻(xiàn)［10］，在相關(guān)因素如發(fā)射功率、噪聲功率、信道相同的情況下，兩個(gè)節(jié)點(diǎn)之間距離越近，則其對(duì)應(yīng)的鏈路容量越大。

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

由于上述方法是選擇距離最近的節(jié)點(diǎn)作為鄰接節(jié)點(diǎn)，因此總能保證點(diǎn)對(duì)點(diǎn)之間鏈路容量最大。在此基礎(chǔ)上進(jìn)行優(yōu)化，可以縮短優(yōu)化過(guò)程。

根據(jù)鄰接矩陣A，可以使用Dijkstra 算法得到兩個(gè)節(jié)點(diǎn)之間的最短路徑P。

3.3 確定用戶(hù)和無(wú)人機(jī)之間的關(guān)聯(lián)矩陣

如前所述，用戶(hù)選擇不同的無(wú)人機(jī)節(jié)點(diǎn)可能導(dǎo)致系統(tǒng)的吞吐量不同，因此需要優(yōu)化用戶(hù)和無(wú)人機(jī)之間的連接關(guān)系。

若用戶(hù)i和對(duì)端j的流量需求為fij，該用戶(hù)總的流量需求為無(wú)人機(jī)節(jié)點(diǎn)g的所有鏈路容量之和記為T(mén)g。用戶(hù)i僅處于一個(gè)無(wú)人機(jī)節(jié)點(diǎn)g的有效通信范圍RV2C內(nèi)，則直接連接到該無(wú)人機(jī)上；但是如果處于多個(gè)無(wú)人機(jī)節(jié)點(diǎn)的有效通信范圍內(nèi)，則需要選擇連接在哪個(gè)無(wú)人機(jī)上。記連接在無(wú)人機(jī)節(jié)點(diǎn)g上的用戶(hù)為Cg，則Cg按下式確定。

根據(jù)的結(jié)果，即可確定關(guān)聯(lián)矩陣B中的bg,*。根據(jù)這種方法，同樣可以得到其他無(wú)人機(jī)節(jié)點(diǎn)的關(guān)聯(lián)矩陣元素，進(jìn)而得到關(guān)聯(lián)矩陣B。

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

接下來(lái)的過(guò)程主要是通過(guò)控制無(wú)人機(jī)節(jié)點(diǎn)的位置來(lái)增加Bij對(duì)應(yīng)的鏈路容量。

3.4 確定無(wú)人機(jī)節(jié)點(diǎn)位置移動(dòng)的范圍

無(wú)人機(jī)可部署位置由兩方面的因素決定：服務(wù)對(duì)象即用戶(hù)的位置和鄰居無(wú)人機(jī)節(jié)點(diǎn)的位置。要求其部署位置離其用戶(hù)的距離不大于RV2C，離其鄰居無(wú)人機(jī)節(jié)點(diǎn)的位置不大于RV2V。其部署范圍如圖5 所示。以相鄰節(jié)點(diǎn)為圓心，以RV（不大于RV2V）為半徑畫(huà)圓；以用戶(hù)位置為圓心，以RC（不大于RV2C）為半徑畫(huà)圓，則所有圓的交集即為該無(wú)人機(jī)部署的可選位置。顯然，在這個(gè)范圍內(nèi)，該無(wú)人機(jī)節(jié)點(diǎn)和其他無(wú)人機(jī)節(jié)點(diǎn)以及用戶(hù)都能保證正常的連接。本文稱(chēng)RC和RV為位置約束半徑。顯然，約束半徑越大，則無(wú)人機(jī)可移動(dòng)優(yōu)化范圍越大，反之亦然。

圖5 位置約束半徑示意圖

如圖5 所示，以V3的可移動(dòng)優(yōu)化范圍為例，分別以其鄰居無(wú)人機(jī)節(jié)點(diǎn)V1、V2、V4為圓心，以小于RV2V的RV為半徑做圓；以其用戶(hù)節(jié)點(diǎn)C6為圓心，以小于RV2C的RC為半徑做圓，四個(gè)圓的重疊部分H 即為V3可移動(dòng)優(yōu)化的范圍。同理，可以確定其他無(wú)人機(jī)節(jié)點(diǎn)的可移動(dòng)范圍。

3.5 編碼并使用遺傳算法進(jìn)行優(yōu)化

遺傳算法求解優(yōu)化問(wèn)題首先要對(duì)問(wèn)題進(jìn)行編碼形成種群，然后對(duì)種群進(jìn)行遺傳操作。

3.5.1 編碼和種群初始化

優(yōu)化對(duì)象是無(wú)人機(jī)節(jié)點(diǎn)的位置，為了方便使用經(jīng)典遺傳算法，這里進(jìn)行二進(jìn)制編碼。由圖4 和圖5可以得到無(wú)人機(jī)可移動(dòng)優(yōu)化位置編號(hào)結(jié)果，如圖6所示。例如無(wú)人機(jī)節(jié)點(diǎn)V3的可選擇優(yōu)化位置為{17，30，36，37，50}，該集合共5 個(gè)位置，可以使用3 位二進(jìn)制數(shù)進(jìn)行編碼，如表2所示。

表2 節(jié)點(diǎn)位置遺傳編碼

圖6 遺傳編碼示意圖

將每一個(gè)無(wú)人機(jī)節(jié)點(diǎn)都按上述方法進(jìn)行編碼，按無(wú)人機(jī)序號(hào)將二進(jìn)制字符串連接在一起，就是對(duì)地域內(nèi)的無(wú)人機(jī)位置的一種表示。

假設(shè)第i個(gè)無(wú)人機(jī)節(jié)點(diǎn)位置的編碼為Code(i),則一個(gè)可能的位置方案對(duì)應(yīng)的染色體編碼為：

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

3.5.2 依據(jù)適應(yīng)值進(jìn)行遺傳操作

1）適應(yīng)值計(jì)算

染色體n對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量用τ(n)表示，則

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

每個(gè)染色體編碼都有一個(gè)適應(yīng)值，該值是評(píng)價(jià)該染色體的依據(jù)。對(duì)于本優(yōu)化問(wèn)題，適應(yīng)度函數(shù)設(shè)計(jì)為：

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

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

2）染色體復(fù)制操作

當(dāng)執(zhí)行復(fù)制操作時(shí)，染色體n以概率進(jìn)入下一代種群。

3）染色體雜交操作

經(jīng)典的遺傳算法雜交算子是選擇兩個(gè)染色體，隨機(jī)選擇一個(gè)雜交位i，然后兩個(gè)染色體相互對(duì)應(yīng)的交換從i+ 1 到末位的位段。對(duì)于本問(wèn)題來(lái)說(shuō)，由于染色體分段表征多個(gè)無(wú)人機(jī)節(jié)點(diǎn)的位置，若隨機(jī)選擇雜交位，可能會(huì)使雜交位對(duì)應(yīng)的無(wú)人機(jī)節(jié)點(diǎn)位置表征錯(cuò)誤。例如，若染色體中表征V3 的基因段為001 和100，若雜交點(diǎn)為2，則雜交后為基因段為000和101，而101為無(wú)效基因。

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

4）染色體變異操作

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

3.5.3制定終止準(zhǔn)則

停止準(zhǔn)則可以表示為算法執(zhí)行的最大代數(shù)。對(duì)于本問(wèn)題來(lái)說(shuō)，吞吐量最大就是各用戶(hù)的流量需求總和若位置優(yōu)化的吞吐量達(dá)到該值，優(yōu)化可以結(jié)束；另一個(gè)條件是系統(tǒng)達(dá)不到用戶(hù)的流量需求量，這時(shí)若優(yōu)化的吞吐量最大值一直沒(méi)有明顯的提高，則可以終止迭代并輸出當(dāng)前吞吐量值作為問(wèn)題的優(yōu)化結(jié)果。

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

算法1 基于遺傳算法的無(wú)人機(jī)位置優(yōu)化輸入:無(wú)人機(jī)自組網(wǎng)拓?fù)浼坝脩?hù)流量需求輸出:優(yōu)化后的位置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 仿真結(jié)果

利用MATLAB 及其中的GA 工具箱進(jìn)行了仿真。首先，生成地域內(nèi)的通信用戶(hù)位置以及用戶(hù)對(duì)流量的需求，然后依照上述算法生成無(wú)人機(jī)節(jié)點(diǎn)位置，使得生成的圖是連通的。

無(wú)人機(jī)高度保持在200 米。無(wú)人機(jī)對(duì)無(wú)人機(jī)通信的傳輸功率為2瓦，而無(wú)人機(jī)對(duì)無(wú)人機(jī)通信的傳輸距離RV2V保持在500 米。這意味著，如果任何兩個(gè)無(wú)人機(jī)之間的距離在500米以?xún)?nèi)，則它們之間可以存在連接。無(wú)人機(jī)對(duì)用戶(hù)通信的傳輸功率為1w，而無(wú)人機(jī)對(duì)用戶(hù)通信的傳輸距離RV2C保持在250m。為了估計(jì)鏈路的吞吐量，基于發(fā)送—接收距離和信道（傳播）模型估計(jì)SINR。然后，使用文獻(xiàn)［10］計(jì)算適當(dāng)?shù)耐掏铝恐怠?duì)于遺傳算法中的參數(shù)，種群規(guī)模取100，復(fù)制概率取0.4，交叉概率取0.4，變異概率取0.2。

4.1 無(wú)人機(jī)位置對(duì)鏈路流量和網(wǎng)絡(luò)吞吐量的影響

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

表3 吞吐量?jī)?yōu)化統(tǒng)計(jì)

圖7 位置優(yōu)化對(duì)鏈路容量及網(wǎng)絡(luò)吞吐量影響

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

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

表4 顯示了四個(gè)流的詳細(xì)信息。表中顯示，隨著位置約束半徑的增大，吞吐量可能進(jìn)一步提高。這是因?yàn)殡S著位置約束半徑的增大，可以測(cè)試更多的無(wú)人機(jī)位置以提高吞吐量。

表4 吞吐量約束半徑影響統(tǒng)計(jì)

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

圖8 位置約束半徑影響

在初始進(jìn)化過(guò)程中，該算法對(duì)所有位置約束半徑產(chǎn)生相似的吞吐量。然而，在第11次進(jìn)化中，位置約束半徑100m 對(duì)應(yīng)的吞吐量落在位置約束半徑150m 和200m 對(duì)應(yīng)的吞吐量之后。同樣，在第15 次進(jìn)化中，位置約束半徑150m 對(duì)應(yīng)的吞吐量落在位置約束半徑200m 對(duì)應(yīng)的吞吐量之后。這是因?yàn)?，位置約束半徑越小，無(wú)人機(jī)的可優(yōu)化機(jī)動(dòng)范圍就越受限。當(dāng)位置約束半徑100m 時(shí)的可優(yōu)化機(jī)動(dòng)范圍是位置約束半徑為150m 和200m 時(shí)可優(yōu)化機(jī)動(dòng)范圍的子集。因此，在第11 代進(jìn)化過(guò)程中，該算法嘗試在位置約束半徑為150m 和200m 情況下的位置優(yōu)化，可能導(dǎo)致性能改進(jìn)。但是，這些導(dǎo)致性能改進(jìn)的位置可能落在位置約束半徑為100m 的可優(yōu)化機(jī)動(dòng)范圍之外。類(lèi)似地，在迭代15 中，該算法嘗試在位置約束半徑200m 且不在位置約束半徑150m 的范圍內(nèi)進(jìn)行位置優(yōu)化，從而導(dǎo)致吞吐量的提升。因此，當(dāng)位置約束半徑較大時(shí)，與較小的半徑相比，可以獲得更大的吞吐量改進(jìn)。

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

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

圖9 粒度半徑影響

5 總 結(jié)

本文提出了一種基于遺傳算法的近似算法，用于控制無(wú)人機(jī)的位置，優(yōu)化無(wú)人機(jī)自組網(wǎng)的拓?fù)?，進(jìn)而使吞吐量最大化。仿真分析表明，該方法可以?xún)?yōu)化自組網(wǎng)的吞吐量，且優(yōu)化速度和位置約束半徑和粒度半徑有關(guān)。本方法可以用于中繼通信的無(wú)人機(jī)自組網(wǎng)提升吞吐量使用。