曾曉婉,王海軍,馬東堂,周 力

(國(guó)防科技大學(xué) 電子科學(xué)學(xué)院,長(zhǎng)沙 410073)

0 引 言

無(wú)人機(jī)具有體積較小、隱蔽性強(qiáng)、靈活機(jī)動(dòng)、可提供視距鏈路等優(yōu)點(diǎn),對(duì)極端環(huán)境和復(fù)雜地理?xiàng)l件具有較強(qiáng)的適應(yīng)能力和生存能力,特別是在地面基礎(chǔ)設(shè)施損毀、衛(wèi)星信號(hào)拒止、災(zāi)情瞬息萬(wàn)變等惡劣環(huán)境中,無(wú)人機(jī)輔助通信的作用尤為突出[1]。應(yīng)急環(huán)境下,無(wú)人機(jī)可作為空中基站為地面用戶提供信號(hào)覆蓋。然而,搭建無(wú)人機(jī)網(wǎng)絡(luò)不僅要考慮地面用戶的不均勻分布,使能量有限的無(wú)人機(jī)為盡可能多的地面用戶提供信號(hào)覆蓋,還要使無(wú)人機(jī)之間形成穩(wěn)健的骨干網(wǎng),以實(shí)現(xiàn)無(wú)人機(jī)內(nèi)部的信息交互。因此,研究一種適應(yīng)用戶分布特點(diǎn)、滿足用戶服務(wù)質(zhì)量(Quality of Service,QoS)要求、保持無(wú)人機(jī)之間的連通并減少能耗的無(wú)人機(jī)基站部署方法,具有重要現(xiàn)實(shí)意義。

信道建模是無(wú)人機(jī)優(yōu)化部署的基礎(chǔ)。文獻(xiàn)[2]提出了一種空對(duì)地(Air to Ground,A2G)信道的概率路徑損耗模型,其中通信鏈路可以是視距(Line-of-Sight,LoS)鏈路或非視距(Non-Line-of-Sight,NLoS)鏈路,其發(fā)生概率是環(huán)境參數(shù)、建筑物高度以及地面設(shè)備和無(wú)人機(jī)之間仰角的函數(shù)。大多數(shù)關(guān)于無(wú)人機(jī)通信網(wǎng)絡(luò)部署的研究均采用此概率路徑損耗模型[3-6]?，F(xiàn)有的無(wú)人機(jī)基站部署工作,按優(yōu)化目標(biāo)的不同,大致可分為最大化服務(wù)用戶數(shù)或用戶覆蓋率[7-9]、最小化無(wú)人機(jī)數(shù)量[10]、最大化傳輸速率[11]、最小化無(wú)人機(jī)和用戶的發(fā)射功率[12]、最大化用戶能量效率[13]等。其中,文獻(xiàn)[7]通過(guò)優(yōu)化無(wú)人機(jī)位置和路徑損耗補(bǔ)償因子以最大化無(wú)人機(jī)的上行鏈路服務(wù)用戶數(shù);文獻(xiàn)[8]推導(dǎo)出無(wú)人機(jī)覆蓋用戶的中斷概率閉合表達(dá)式,并求得最大覆蓋半徑和最佳高度;文獻(xiàn)[9]使用Q-learning算法來(lái)最大化無(wú)人機(jī)的用戶覆蓋率;文獻(xiàn)[10]研究了無(wú)人機(jī)的數(shù)量和位置優(yōu)化問(wèn)題,以確保用戶QoS;文獻(xiàn)[11]以最大化網(wǎng)絡(luò)總傳輸速率為目標(biāo),使用深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)算法求出無(wú)人機(jī)最優(yōu)懸停位置和功率分配;文獻(xiàn)[12]以最小化無(wú)人機(jī)網(wǎng)絡(luò)上行鏈路總發(fā)射功率為目標(biāo),設(shè)計(jì)了一種基于用戶位置統(tǒng)計(jì)信息的無(wú)人機(jī)水平部署和用戶關(guān)聯(lián)方案;文獻(xiàn)[13]聯(lián)合優(yōu)化無(wú)人機(jī)水平位置、用戶關(guān)聯(lián)和地面用戶的發(fā)射功率以最大化地面用戶的能量效率。然而,上述研究大部分是在二維平面對(duì)無(wú)人機(jī)進(jìn)行部署,且未考慮無(wú)人機(jī)之間的連通。

本文綜合考慮無(wú)人機(jī)之間的連通、用戶QoS和無(wú)人機(jī)的服務(wù)公平性,以最大化服務(wù)用戶數(shù)為目標(biāo),對(duì)無(wú)人機(jī)的三維坐標(biāo)和覆蓋半徑進(jìn)行優(yōu)化。本文主要貢獻(xiàn)如下:

一是將無(wú)人機(jī)部署問(wèn)題建模為最大化服務(wù)用戶數(shù)的同時(shí)保證無(wú)人機(jī)之間的連通、用戶QoS和服務(wù)公平性的問(wèn)題。經(jīng)分析,該問(wèn)題是非確定性多項(xiàng)式難題(Non-deterministic Polynomial Hard,NP-hard)。

二是將部署問(wèn)題分解為水平部署和高度優(yōu)化兩個(gè)子問(wèn)題。提出了一種融合了遺傳算法和粒子群算法的啟發(fā)式方法(A Heuristic Algorithm Combining Genetic Algorithm and Particle Swarm Optimization Algorithm,GAPSO),以較低的時(shí)間復(fù)雜度獲得最優(yōu)部署結(jié)果。另外,通過(guò)高度微調(diào)算法進(jìn)一步降低無(wú)人機(jī)與服務(wù)用戶之間的路徑損耗。

三是分別在用戶隨機(jī)分布和分簇分布模式下進(jìn)行仿真,結(jié)果驗(yàn)證了所提算法能以較低的時(shí)間復(fù)雜度和無(wú)人機(jī)平均發(fā)射功率獲得最優(yōu)部署結(jié)果。

需要特別說(shuō)明的是,本文中無(wú)人機(jī)服務(wù)用戶數(shù)指地面用戶中無(wú)人機(jī)能為其提供有效通信的用戶數(shù)量,用戶覆蓋率指無(wú)人機(jī)服務(wù)用戶數(shù)占地面用戶數(shù)的比例,服務(wù)公平性指不同無(wú)人機(jī)之間服務(wù)用戶數(shù)的公平性。

1 系統(tǒng)模型和問(wèn)題描述

1.1 場(chǎng)景介紹

圖1描述了無(wú)人機(jī)通信網(wǎng)絡(luò)模型。網(wǎng)絡(luò)共有3類實(shí)體:無(wú)人機(jī)、地面用戶和控制中心。數(shù)量有限的無(wú)人機(jī)基站懸停在一定高度,形成空中骨干網(wǎng)的同時(shí),為盡可能多的地面用戶提供有效通信。場(chǎng)景中共有無(wú)人機(jī)與核心控制器(UAV-BS to Core Controller,U2C)通信、無(wú)人機(jī)與無(wú)人機(jī)(UAV to UAV,U2U)通信以及無(wú)人機(jī)與所服務(wù)的用戶(UAV-BS to Device,U2D)通信。在U2C通信中,控制中心用來(lái)與無(wú)人機(jī)網(wǎng)絡(luò)交互控制指令,或?qū)崿F(xiàn)無(wú)人機(jī)網(wǎng)絡(luò)與其他網(wǎng)絡(luò)的互通。在U2U通信中,無(wú)人機(jī)使用獨(dú)立的通信鏈路,與其他通信類型之間不存在干擾。在U2D通信中,無(wú)人機(jī)可周期地獲取地面節(jié)點(diǎn)的位置信息并更新位置?；緝?nèi)用戶采用頻分多址(Frequency Division Multiple Access,FDMA)的方式,不同無(wú)人機(jī)基站采用正交頻段,它們之間不存在干擾。

圖1 無(wú)人機(jī)通信網(wǎng)絡(luò)模型

本文主要考慮U2U通信和U2D通信。

1.2 信道模型

對(duì)于空對(duì)空信道,無(wú)人機(jī)i和無(wú)人機(jī)k之間的信道路徑損耗可采用自由空間傳播損耗(Free Space Propagation Loss,FSPL)模型計(jì)算,表示為

(1)

式中:di,k表示無(wú)人機(jī)i和無(wú)人機(jī)k之間的距離;f0表示無(wú)人機(jī)之間通信的載波頻率;c是光速。因此,給定無(wú)人機(jī)之間的發(fā)送功率和通信帶寬,由香農(nóng)公式,在保證最低傳輸速率的前提下,無(wú)人機(jī)之間的最大通信距離是確定的,用dmax表示。

對(duì)于空對(duì)地信道,采用文獻(xiàn)[2]推導(dǎo)的空對(duì)地信道概率模型,將信道損耗建模為L(zhǎng)oS和NLoS分量的概率加權(quán)和。無(wú)人機(jī)i和用戶j的平均路徑損耗表示為

(2)

A=ηLoS-ηNLoS

,

(3)

(4)

(5)

(6)

式中:α和β是由環(huán)境(例如農(nóng)村、城市、密集城市等)決定的常量因子;θi,j是無(wú)人機(jī)i和用戶j的俯仰角;di,j表示無(wú)人機(jī)i和用戶j之間的距離;hi是無(wú)人機(jī)的高度;ri,j是無(wú)人機(jī)i和用戶j之間的水平歐氏距離;ηLoS和ηNLoS分別是LoS和NLoS下的平均附加路徑損耗(與環(huán)境有關(guān));fc是載波頻率。

圖2直觀展示了城市環(huán)境中不同路徑損耗下無(wú)人機(jī)的高度和覆蓋半徑之間的關(guān)系,圖中θopt表示無(wú)人機(jī)取最大覆蓋半徑時(shí)的仰角。

圖2 城市環(huán)境中不同下覆蓋半徑和高度的關(guān)系

由公式(2)～(6)和圖2可得出以下結(jié)論:

結(jié)論1:在給定環(huán)境中,θopt是常量,由下列方程計(jì)算得出[2]:

(7)

結(jié)論2:在給定環(huán)境中,路徑損耗越大,無(wú)人機(jī)的最大覆蓋半徑越大。

結(jié)論3:對(duì)于給定的路徑損耗,無(wú)人機(jī)在仰角為θopt時(shí),覆蓋半徑最大。

結(jié)論4:當(dāng)無(wú)人機(jī)與地面用戶的水平距離固定時(shí),只有當(dāng)無(wú)人機(jī)仰角為θopt時(shí),路徑損耗最小。

1.3 信號(hào)覆蓋質(zhì)量情況衡量

由于不同無(wú)人機(jī)基站采用正交頻段,小區(qū)間不存在互干擾,因此可用信噪比(Signal-to-Noise Ratio,SNR)來(lái)衡量信號(hào)覆蓋質(zhì)量情況。鑒于此,當(dāng)用戶j收到來(lái)自無(wú)人機(jī)i的信噪比γi,j大于閾值Λth時(shí),可認(rèn)為無(wú)人機(jī)i可為用戶j提供有效通信。SNR計(jì)算如下:

(8)

(9)

式中:pi,j表示無(wú)人機(jī)i對(duì)用戶j的發(fā)射功率;Ngw是高斯白噪聲功率。

1.4 問(wèn)題描述和建模

已知地面用戶的數(shù)量和位置,無(wú)人機(jī)數(shù)量固定,綜合考慮無(wú)人機(jī)之間的連通、用戶QoS和服務(wù)公平性,以最大化無(wú)人機(jī)服務(wù)用戶數(shù)為目標(biāo)優(yōu)化無(wú)人機(jī)的3D坐標(biāo)和覆蓋半徑。具體來(lái)說(shuō),部署的無(wú)人機(jī)在最大化服務(wù)用戶數(shù)的同時(shí),應(yīng)滿足如下要求:

①在U2U通信中,每個(gè)無(wú)人機(jī)應(yīng)至少存在兩個(gè)鄰居節(jié)點(diǎn);

②為避免碰撞,任意兩架無(wú)人機(jī)之間的距離應(yīng)不小于dmin;

⑤每個(gè)用戶最多與1架無(wú)人機(jī)建立通信,位于多架無(wú)人機(jī)覆蓋半徑重疊區(qū)域的用戶優(yōu)先與服務(wù)用戶數(shù)最少的無(wú)人機(jī)建立通信;

⑥考慮到地形和功耗,無(wú)人機(jī)的飛行高度應(yīng)在合理區(qū)間[hmin,hmax]內(nèi)。

基于上述分析,將無(wú)人機(jī)部署問(wèn)題建模如下:

地溫傳感器的使用過(guò)程當(dāng)中常常會(huì)受到天氣狀況的影響，在陰雨天氣當(dāng)中，低溫傳感器會(huì)由于地表的雨水較多，導(dǎo)致出現(xiàn)傳感器的對(duì)接線發(fā)生故障。陰雨天氣時(shí)，地表的積水隨著傳感器的外管壁進(jìn)行滲透，這種故障產(chǎn)生時(shí)，表現(xiàn)為傳感器的傳送數(shù)值不準(zhǔn)確或者是短路，因此一旦發(fā)現(xiàn)故障，就需要馬上開(kāi)展檢查，并且針對(duì)外管壁進(jìn)行加固，防止雨水的滲透，做好密封防水工作。

(10a)

(10b)

(10c)

(10d)

C4:hmin≤hi≤hmax。

(10e)

式中:約束條件C1保證了U2U通信時(shí)無(wú)人機(jī)至少有2個(gè)鄰居節(jié)點(diǎn);C2定義了無(wú)人機(jī)服務(wù)用戶的上限;C3表示每個(gè)用戶最多由一個(gè)無(wú)人機(jī)提供服務(wù);C4表示無(wú)人機(jī)的高度在一定范圍內(nèi)。

經(jīng)分析,該問(wèn)題屬于NP-hard問(wèn)題,針對(duì)大規(guī)模無(wú)人機(jī)的部署,很難在可接受的時(shí)間內(nèi)求出最優(yōu)解[14]。遺傳算法是解決多變量復(fù)雜優(yōu)化問(wèn)題的有效方案,廣泛應(yīng)用于各領(lǐng)域優(yōu)化問(wèn)題。本文將部署問(wèn)題分解為水平部署和高度優(yōu)化兩個(gè)子問(wèn)題,采用一種將遺傳算法和粒子群算法相結(jié)合的GAPSO算法和高度微調(diào)法實(shí)現(xiàn)無(wú)人機(jī)的部署優(yōu)化。

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

2.1 GAPSO算法

粒子群優(yōu)化算法(Particle Swarm Optimization Algorithm,PSO)受二維空間中的鳥(niǎo)群運(yùn)動(dòng)的啟發(fā)而產(chǎn)生,后被推廣到解決N維空間優(yōu)化問(wèn)題。在粒子群優(yōu)化算法中,問(wèn)題可能的解等價(jià)于搜索空間中的一個(gè)位置(稱為“粒子”),算法初始化形成一群隨機(jī)粒子,即隨機(jī)的初始解。所有粒子皆有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)度,除了當(dāng)前位置外,還記錄了迄今為止該粒子達(dá)到過(guò)的適應(yīng)度最好的位置(歷史最優(yōu)粒子)和種群中所有粒子達(dá)到過(guò)的適應(yīng)度最好的位置(全局最優(yōu)粒子)。粒子們參照最優(yōu)粒子的位置在解空間中搜索,并多次迭代找到最優(yōu)解。

設(shè)D維搜索空間中有m個(gè)粒子,第i個(gè)粒子的歷史最優(yōu)粒子和全局最優(yōu)粒子分別表示為Pi=[pi1,…,piD]T和Pg=[pg1,…,pgD]T,其飛行速度和位置向量分別表示為Vi=[vi1,…,viD]T和Xi=[xi1,…,xiD]T,則粒子i第t+1次的飛行速度和位置可按如下公式計(jì)算:

vid(t+1)=c1·r1·[pid(t)-xid(t)]+

c2·r2·[pgd(t)-xid(t)]+ω·vid(t),

(11)

xid(t+1)=xid(t)+vid(t+1) 。

(12)

式中:1≤i≤m;1≤d≤D;ω為慣性因子;c1,c2為加速因子;r1,r2為[0,1]之間的隨機(jī)數(shù)。在迭代過(guò)程中,為降低粒子飛出搜索空間的概率,粒子的速度向量被限制在[-Vmax,Vmax],位置向量被限制在[-Xmax,Xmax]。

遺傳粒子群算法融合了遺傳算法強(qiáng)大的全局搜索性能和粒子群的位置轉(zhuǎn)移思想,其基本思想是:首先,進(jìn)行種群初始化,計(jì)算個(gè)體適應(yīng)度,并按適應(yīng)度降序的順序排序;然后,對(duì)前50%的優(yōu)秀個(gè)體采用PSO算法進(jìn)行提高并遺傳到下一代,淘汰剩余個(gè)體;接著,對(duì)已提高的優(yōu)秀個(gè)體通過(guò)交叉和變異得到完整的下一代;最后,多次迭代直至達(dá)到迭代次數(shù)或當(dāng)前種群滿足預(yù)設(shè)條件。具體流程如圖3所示。

圖3 GAPSO算法流程

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

2.2.1 設(shè)計(jì)思路

圖4 算法設(shè)計(jì)思路

2.2.2 算法具體步驟

表1列出了算法中使用的符號(hào)和定義。

表1 算法符號(hào)定義

無(wú)人機(jī)基站部署方法具體步驟如下:

輸入:地面用戶數(shù)據(jù)庫(kù)

輸出:全局最優(yōu)個(gè)體及其適應(yīng)度λ

1 仰角優(yōu)化:由公式(7)計(jì)算無(wú)人機(jī)的最優(yōu)仰角θopt;

3 種群初始化

5 選擇:個(gè)體按適應(yīng)度降序的順序排序,保留前50%的個(gè)體;

7 提高:設(shè)置c1,c2和ω,用PSO算法更新個(gè)體水平坐標(biāo);

8 建立U2U連接圖

9 判斷坐標(biāo)合理性

10 建立U2D連接圖

11 計(jì)算適應(yīng)度

12 比較新舊個(gè)體的適應(yīng)度,更新每個(gè)個(gè)體的歷史最優(yōu)個(gè)體;

13 比較全部個(gè)體的適應(yīng)度,更新全局最優(yōu)個(gè)體;

14 end for

16 從已提高個(gè)體中隨機(jī)選擇2個(gè)個(gè)體,從中選擇適應(yīng)度大的個(gè)體作為父體,再以相同的方法選出母體;

17 生成2個(gè)位于區(qū)間(0,1)的隨機(jī)數(shù);

18 交叉:當(dāng)?shù)谝粋€(gè)隨機(jī)數(shù)小于等于pc時(shí),將父母染色體的水平坐標(biāo)對(duì)半交叉;

19 變異:當(dāng)?shù)诙€(gè)隨機(jī)數(shù)小于等于pm時(shí),將父母染色體的水平坐標(biāo)隨機(jī)變異,若變異后坐標(biāo)超出無(wú)人機(jī)部署區(qū)域的邊界,則將坐標(biāo)約束在邊界上;

20 建立U2U連接圖

21 判斷坐標(biāo)合理性

22 建立U2D連接圖

23 計(jì)算適應(yīng)度

24 比較新舊個(gè)體的適應(yīng)度,更新每個(gè)個(gè)體的歷史最優(yōu)粒子;

25 比較全部個(gè)體的適應(yīng)度,更新全局最優(yōu)粒子;

26 end for

27 end for

28 高度微調(diào)

因篇幅所限,種群初始化、建立U2U連接圖、判斷坐標(biāo)合理性、建立U2D連接圖、計(jì)算適應(yīng)度、高度微調(diào)的具體步驟和算法,請(qǐng)用微信掃描本文OSID碼,在“開(kāi)放科學(xué)數(shù)據(jù)與內(nèi)容”中查看。

3 仿真驗(yàn)證和結(jié)果分析

3.1 仿真設(shè)置

本節(jié)通過(guò)Matlab仿真所提算法,動(dòng)態(tài)展示部署過(guò)程,并評(píng)估算法性能。詳細(xì)的部署演示視頻可通過(guò)微信掃描本文OSID碼,在“開(kāi)放科學(xué)數(shù)據(jù)與內(nèi)容”中查看。在本文的仿真中,300個(gè)用戶分別以用戶分簇分布和隨機(jī)分布兩種模式分布在4 000 m×4 000 m的區(qū)域內(nèi)。仿真的主要參數(shù)如表2所列。

表2 主要仿真參數(shù)

3.2 部署示例

3.2.1 用戶隨機(jī)分布

圖5(a)展示了用戶在區(qū)域內(nèi)隨機(jī)分布,圖5(b)顯示了100次迭代后得到的無(wú)人機(jī)3D位置、無(wú)人機(jī)之間的鏈路及其與服務(wù)用戶的連接情況,圖5(c)和圖5(d)分別是其水平部署結(jié)果和高度部署結(jié)果的展示。由圖可見(jiàn),無(wú)人機(jī)之間形成了穩(wěn)定的連通,每個(gè)無(wú)人機(jī)至少有兩個(gè)鄰居節(jié)點(diǎn),無(wú)人機(jī)服務(wù)用戶數(shù)達(dá)到理論最大值,每個(gè)無(wú)人機(jī)服務(wù)的用戶數(shù)不超過(guò)25。

(a)用戶隨機(jī)分布

3.2.2 用戶分簇分布

圖6(a)展示了用戶分簇分布的一種典型場(chǎng)景,其中,有的簇與其他簇分界明顯,有的簇與其他簇界線不明顯;屬于不同簇的用戶分布方式不一,有的零散程度大,有的較為密集,有的呈“一”字型分布。圖6(b)顯示了100次迭代后的無(wú)人機(jī)3D位置、無(wú)人機(jī)之間的鏈路及其與服務(wù)用戶之間的連接情況,圖6(c)和圖6(d)分別是其水平部署結(jié)果和高度部署結(jié)果的展示。由圖可見(jiàn),分簇場(chǎng)景下,無(wú)人機(jī)在尋求服務(wù)用戶數(shù)最大化的同時(shí)盡量聚攏以確保無(wú)人機(jī)之間的連通。

3.3 算法性能評(píng)估

3.3.1 迭代收斂性

進(jìn)化算法的收斂性分析主要研究在迭代時(shí)間趨于無(wú)窮的假設(shè)下,算法能否最終找到并保留問(wèn)題的全局最優(yōu)解[15-16],或者全局最優(yōu)解能否占據(jù)整個(gè)種群[17]。仿真結(jié)果表明,K-means初始化、Voronoi Diagram初始化和隨機(jī)初始化三種方式均能收斂到用戶覆蓋率的理論最大值(即全局最優(yōu)解)。GAPSO算法的首要步驟是對(duì)初始種群中的100個(gè)個(gè)體進(jìn)行水平位置初始化,那么,種群初始化如何影響算法的收斂性呢?圖7展示了K-means初始化、Voronoi Diagram初始化和隨機(jī)初始化三種方式下用戶覆蓋率隨迭代次數(shù)的變化情況,所示結(jié)果為算法收斂到全局最優(yōu)解的5 000次仿真結(jié)果的平均值。

圖7 三種初始化方式下的收斂性

由圖7可知,在用戶分簇分布下,三種初始化方式迭代10次以內(nèi)均可收斂到全局最優(yōu)解。這是因?yàn)榉执胤植紩r(shí)用戶較為緊密,所有的簇基本能被無(wú)人機(jī)的最大覆蓋半徑覆蓋。值得注意的是,K-means初始化方式雖然能以較快速度收斂,但卻極易早熟性收斂。具體來(lái)說(shuō),在用戶隨機(jī)分布模式下,種群在初始化過(guò)程中雖然每產(chǎn)生一個(gè)個(gè)體就要重新分簇且每次分簇的簇心都不盡相同,但由于隨機(jī)分布下用戶比較疏散,因此對(duì)覆蓋用戶數(shù)的影響不大,這會(huì)造成種群的多樣性降低,從而使整個(gè)群體基本喪失進(jìn)化能力,出現(xiàn)算法較早收斂于局部最優(yōu)解的現(xiàn)象。即使通過(guò)增加分簇的個(gè)數(shù)減輕“早熟”現(xiàn)象,但隨著分簇個(gè)數(shù)的增加,K-means初始化的算法收斂情況將與隨機(jī)初始化的算法收斂情況類似。在用戶分簇模式下,K-means初始化也存在“早熟”現(xiàn)象,但由于用戶緊密,生成的初始種群的適應(yīng)度值接近全局最優(yōu)解,因此相比隨機(jī)分布模式,“早熟”現(xiàn)象對(duì)其影響較小。在用戶隨機(jī)分布模式下,Voronoi Diagram初始化和隨機(jī)初始化的算法在運(yùn)行過(guò)程中的收斂情況相似,平均在迭代75次左右時(shí)收斂。但Voronoi Diagram初始化方式下的算法收斂到全局最優(yōu)解的概率比隨機(jī)初始化要高,這是因?yàn)閂oronoi Diagram初始化以Voronoi Diagram頂點(diǎn)坐標(biāo)作為無(wú)人機(jī)水平位置,可使無(wú)人機(jī)不偏離用戶。

3.3.2 時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是輸入規(guī)模的函數(shù),表述了算法在一定輸入規(guī)模下完成相應(yīng)計(jì)算任務(wù)所花費(fèi)的基本操作數(shù)[18]。一般來(lái)說(shuō),進(jìn)化算法的時(shí)間復(fù)雜度是用算法找到問(wèn)題的最優(yōu)解或近似解所需的適應(yīng)度值評(píng)估次數(shù)或者迭代的次數(shù)來(lái)衡量[19-21]。因此,可認(rèn)為GAPSO算法的時(shí)間復(fù)雜度與種群大小K和最小迭代次數(shù)τmin有關(guān),兩個(gè)參數(shù)的乘積越小,算法的效率越高。本文將最小迭代次數(shù)定義為當(dāng)適應(yīng)度收斂到某個(gè)最優(yōu)解的次數(shù)占全部迭代次數(shù)的20%時(shí)所需的全部迭代次數(shù)。

表3給出了種群大小K與所需的最小迭代次數(shù)τmin之間的關(guān)系,所示數(shù)據(jù)從5 000次仿真結(jié)果的平均值中分析得出(迭代次數(shù)向上取整,統(tǒng)一取10的整數(shù)倍),其中初始化方式選擇Voronoi Diagram初始化。由于種群的多樣性越高,算法收斂到全局最優(yōu)解的概率越大。由表3,為提高算法的效率并增大種群找到全局最優(yōu)解的概率,在用戶隨機(jī)分布模式下可將種群大小和迭代次數(shù)分別設(shè)置為100和100,在用戶分簇分布模式下可將種群大小和迭代次數(shù)分別設(shè)置為20和20。

表3 種群大小與最小迭代次數(shù)的關(guān)系

3.3.3 用戶覆蓋率和服務(wù)公平性

本文用簡(jiǎn)氏公平指數(shù)(Jain’s fairness)來(lái)衡量服務(wù)公平性,定義為

(13)

式中:Si表示無(wú)人機(jī)i的服務(wù)用戶數(shù)。可見(jiàn),Ψc取值在1/N～1之間變化,當(dāng)所有無(wú)人機(jī)的服務(wù)用戶數(shù)相等時(shí)達(dá)到最大值1。

考慮到無(wú)人機(jī)的最大通信距離dmax對(duì)整個(gè)網(wǎng)絡(luò)的連通有一定影響,因此探索它如何影響用戶覆蓋率和服務(wù)公平性。圖8顯示了用戶覆蓋率和服務(wù)公平性隨無(wú)人機(jī)最大通信距離的變化趨勢(shì),所示結(jié)果為5 000次仿真結(jié)果的平均值?？梢钥闯?用戶覆蓋率隨著無(wú)人機(jī)最大通信距離的增大而增大,且均能收斂到理論最大值(250÷300≈83.33%)附近;服務(wù)公平性隨著無(wú)人機(jī)最大通信距離的增大而增大,且均能收斂到理論最大值1的附近。這是因?yàn)楫?dāng)無(wú)人機(jī)最大通信距離較小時(shí),為滿足U2U通信中無(wú)人機(jī)至少有兩個(gè)鄰居節(jié)點(diǎn)的約束條件,無(wú)人機(jī)之間的重疊覆蓋區(qū)域較多。當(dāng)無(wú)人機(jī)最大通信距離足夠大時(shí),無(wú)人機(jī)可在保持相互通信的同時(shí),分散到不同區(qū)域以最大化服務(wù)用戶數(shù)和服務(wù)公平性。

圖8 用戶覆蓋率和服務(wù)公平性隨dmax的變化情況

3.3.4 無(wú)人機(jī)的平均發(fā)射功率

假設(shè)地面用戶所需的接收功率pr為-74 dBm,則無(wú)人機(jī)i對(duì)用戶j的發(fā)射功率可計(jì)算為

(14)

圖9將GAPSO算法在高度固定和高度同時(shí)優(yōu)化(GAPSO算法在高度同時(shí)優(yōu)化時(shí)的高度初始化采用隨機(jī)初始化)兩種方式下所需的無(wú)人機(jī)平均發(fā)射功率與本算法使用的高度微調(diào)法進(jìn)行對(duì)比,所示結(jié)果為5 000次仿真結(jié)果的平均值。圖9(a)基于用戶分簇分布場(chǎng)景,圖9(b)基于用戶隨機(jī)分布場(chǎng)景。

如圖9(a)所示,在分簇模式下,本文所提算法不能以最低的無(wú)人機(jī)平均發(fā)射功率獲得最大的用戶覆蓋率。原因在于,無(wú)人機(jī)的初始高度為可獲得理論最大覆蓋半徑的對(duì)應(yīng)高度,這使得算法在運(yùn)行過(guò)程中,為使每個(gè)無(wú)人機(jī)至少有2個(gè)鄰居節(jié)點(diǎn),個(gè)別無(wú)人機(jī)可能被部署在簇間空白區(qū)域,若此時(shí)仍有個(gè)別地面用戶位于覆蓋半徑內(nèi),無(wú)人機(jī)則需要更多的發(fā)射功率以保證用戶的通信質(zhì)量。對(duì)于高度固定法部署的無(wú)人機(jī),由于其覆蓋半徑有限,為覆蓋更多用戶,在算法運(yùn)行過(guò)程中,無(wú)人機(jī)極有可能在每個(gè)簇內(nèi)形成閉環(huán)的U2U通信(此時(shí)每個(gè)無(wú)人機(jī)有2個(gè)鄰居節(jié)點(diǎn))。此外,由于本文分簇場(chǎng)景中用戶較為集中,因此,當(dāng)高度固定法設(shè)置的高度較低時(shí),部署的無(wú)人機(jī)能以較小的覆蓋半徑、較低的平均發(fā)射功率獲得較大的覆蓋率。

在隨機(jī)分布模式下,用戶間距沒(méi)有分簇分布時(shí)密集,因此也更具普遍性。如圖9(b)所示,比起高度固定和高度同時(shí)優(yōu)化的情況,高度微調(diào)法部署的無(wú)人機(jī)用戶覆蓋率最高,平均發(fā)射功率最低。這是因?yàn)?高度微調(diào)法的原理是結(jié)論5,即當(dāng)無(wú)人機(jī)與地面用戶的水平距離固定時(shí),只有當(dāng)無(wú)人機(jī)懸停于hopt(本文仿真場(chǎng)景下為334.37 m)時(shí),其路徑損耗最小,若無(wú)人機(jī)高度增高或者降低,路徑損耗將隨之增大,為滿足用戶QoS要求,無(wú)人機(jī)的發(fā)射功率也將增大。

4 結(jié)束語(yǔ)

本文提出了一種無(wú)人機(jī)基站3D部署算法,在最大化服務(wù)用戶數(shù)的同時(shí)滿足用戶QoS要求、無(wú)人機(jī)之間的連通和服務(wù)公平性。仿真結(jié)果表明,所提方法能以較低的時(shí)間復(fù)雜度獲得最優(yōu)部署結(jié)果,并能以較低的無(wú)人機(jī)平均發(fā)射功率最大化無(wú)人機(jī)的服務(wù)用戶數(shù)。

未來(lái)的工作將研究A2G干擾模型和無(wú)人機(jī)資源分配策略,并實(shí)地采集無(wú)人機(jī)和地面用戶通信的真實(shí)數(shù)據(jù),以進(jìn)一步驗(yàn)證所提算法的有效性。