無(wú)人機(jī)輔助的移動(dòng)邊緣計(jì)算中的任務(wù)分配策略

王岱巍，徐高潮，李 龍

（吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012）

0 引言

隨著物聯(lián)網(wǎng)（Internet of Things，IoT）的普及以及移動(dòng)應(yīng)用程序功能的日漸強(qiáng)大，用戶設(shè)備（User Equipment，UE）的計(jì)算需求已達(dá)到前所未有的水平。移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）技術(shù)由于可以在較小的延遲下為資源受限的UE提供處理計(jì)算密集型任務(wù)的能力，受到學(xué)術(shù)界和業(yè)界的日益關(guān)注。標(biāo)準(zhǔn)化組織和行業(yè)協(xié)會(huì)如歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)（European Telecommunications Standards Institute，ETSI）和5G汽車聯(lián)盟（5G Automotive Association，5GAA）已經(jīng)確定了MEC 的幾個(gè)應(yīng)用場(chǎng)景，主要有智能視頻加速、可感知應(yīng)用程序的性能優(yōu)化、萬(wàn)物互聯(lián)、大規(guī)模機(jī)械化通信等［1-2］。MEC 的基本原理是通過(guò)在接入點(diǎn)（Access Point，AP）部署云服務(wù)器，使UE 的計(jì)算任務(wù)可以在無(wú)線網(wǎng)絡(luò)的邊緣完成，從而將UE 從繁重的計(jì)算工作任務(wù)中解放出來(lái)并延長(zhǎng)其電池壽命［3-4］。

當(dāng)前對(duì)于MEC 的應(yīng)用中，提高系統(tǒng)能效或減少各種基于蜂窩網(wǎng)絡(luò)的MEC 系統(tǒng)的等待時(shí)間的相關(guān)研究主要有文獻(xiàn)［5-10］。文獻(xiàn)［5］中研究了多輸入多輸出（Multiple Input Multiple Output，MIMO）的MEC 系統(tǒng)，通過(guò)聯(lián)合優(yōu)化通信功耗和計(jì)算資源將總能耗降至最低；文獻(xiàn)［6］中研究了具有邊緣云和中心云并存的兩層異構(gòu)網(wǎng)絡(luò)，并且對(duì)計(jì)算卸載的目標(biāo)選擇進(jìn)行了優(yōu)化以最大限度地減少網(wǎng)絡(luò)通信的能耗；文獻(xiàn)［7-10］中考慮將無(wú)線電力傳輸（Wireless Powered Transmission，WPT）技術(shù)應(yīng)用到MEC 系統(tǒng)中，這使UE 能夠?yàn)槠錈o(wú)線通信和本地計(jì)算提供可持續(xù)的能量供應(yīng)，但增加了系統(tǒng)的復(fù)雜度。

此外，由于無(wú)人機(jī)（Unmanned Aerial Vehicle，UAV）在通信方面的諸多優(yōu)勢(shì)如按需部署、快速部署、視距通信等［11］，使用UAV協(xié)助的MEC服務(wù)有著巨大的前景。對(duì)此，有諸多側(cè)重點(diǎn)不同的相關(guān)研究。在文獻(xiàn)［12］中，對(duì)于UAV輔助的MEC系統(tǒng)，使用一種兩階段交替優(yōu)化的方法，獲得了使能量效率最大化的飛行軌跡與通信和計(jì)算資源的分配；在文獻(xiàn)［13］中，研究了啟用WPT 技術(shù)的支持UAV 的MEC 系統(tǒng)，其中UAV 可以提供能量發(fā)送和MEC 服務(wù)，以便為UE 供能以及計(jì)算卸載。通過(guò)交替算法，解決了在局部和二進(jìn)制泛洪模式下的計(jì)算速率最大化問(wèn)題。在另一項(xiàng)研究［14］中，UAV 作為UE 而不是MEC服務(wù)器，由多個(gè)蜂窩地面基站提供服務(wù)以計(jì)算UAV 產(chǎn)生的任務(wù)。通過(guò)連續(xù)凸逼近（Successive Convex Approximation，SCA）算法，優(yōu)化了資源分配策略和UAV 軌跡，使UAV 的任務(wù)完成時(shí)間最小化。此外，在文獻(xiàn)［15］中，考慮將多架UAV 以固定的飛行軌跡作為邊緣服務(wù)器為一定范圍內(nèi)的UE提供服務(wù)，通過(guò)使用強(qiáng)化學(xué)習(xí)解決混合整數(shù)非線性規(guī)劃的方法，使UE的能耗最小化。

盡管應(yīng)用廣泛，但限制UAV 在移動(dòng)邊緣計(jì)算中廣泛應(yīng)用的最主要原因在于，UAV 使用電池供能，其保持飛行狀態(tài)的時(shí)間和機(jī)載計(jì)算設(shè)備的計(jì)算能力都是有限的。為此，文獻(xiàn)［16-18］中的研究主要針對(duì)UAV 的能耗進(jìn)行優(yōu)化：文獻(xiàn)［16］中研究了基于UAV 的MEC 系統(tǒng)，在此模型中UAV 可以提供計(jì)算能力，幫助UE 計(jì)算其任務(wù)，通過(guò)使用SCA 方法共同優(yōu)化任務(wù)分配和UAV 的軌跡，將UAV 的總能量消耗降至最低；文獻(xiàn)［17］中分別考慮了UAV 和UE 兩者各自的能耗，并基于不同的帕累托最優(yōu)權(quán)衡得出了不同的軌跡與通信功率；文獻(xiàn)［18］中通過(guò)推導(dǎo)出旋翼UAV 的能耗計(jì)算公式，使用SCA 聯(lián)合優(yōu)化了飛行軌跡與通信策略，解決了旋翼無(wú)人機(jī)的能量最小化問(wèn)題。

此外，如果UE分布比較分散，單次飛行很難對(duì)于全部UE實(shí)現(xiàn)訪問(wèn)覆蓋，因此可能需要多次派遣UAV 來(lái)完成全部覆蓋或者派遣多架UAV 共同工作，因此，減少派遣次數(shù)或派遣數(shù)量，將有效地降低收集全部數(shù)據(jù)所需的時(shí)間或成本。為此，考慮在派遣UAV完成任務(wù)之前，對(duì)終端和UAV進(jìn)行預(yù)分配。通過(guò)多次飛行遍歷多個(gè)聚類中的終端，UAV 可以完成大規(guī)模的訪問(wèn)與通信任務(wù)。為此，可以考慮使用聚類算法對(duì)地面UE進(jìn)行劃分，從而將大規(guī)模的任務(wù)分成多個(gè)子任務(wù)來(lái)執(zhí)行。在文獻(xiàn)［19］中，使用了自組織特征映射（Self-Organizing feature Map，SOM）網(wǎng)絡(luò)對(duì)用戶進(jìn)行實(shí)時(shí)聚類，該聚類以信道增益作為判斷類別的指標(biāo)，得到了UAV 的最佳部署位置；在文獻(xiàn)［20］中，提出了一種基于最小包圍圓和改進(jìn)K均值聚類算法（K-means clustering algorithm）的無(wú)人機(jī)基站優(yōu)化部署方法，解決了無(wú)人機(jī)基站在無(wú)線通信中的位置部署和軌跡優(yōu)化問(wèn)題。當(dāng)前基于歐氏距離的聚類方法主要有K-Means 算法及其衍生的改進(jìn)算法、迭代自組織數(shù)據(jù)分析（Iterative Self-Organizing DATA analysis，ISODATA）方法等，對(duì)于K-Means 算法和類似的改進(jìn)算法，聚類數(shù)目需要預(yù)先確定，而在本文場(chǎng)景下，不同的地面節(jié)點(diǎn)分布、不同的數(shù)據(jù)傳輸量，都會(huì)導(dǎo)致最佳的聚類數(shù)目不同，因此難以預(yù)先確定；對(duì)于自適應(yīng)的ISODATA 算法，其諸多的初始參數(shù)在本文場(chǎng)景下也難以確定。

在此背景下，本文設(shè)計(jì)了一種適用于UE大范圍分布的場(chǎng)景下使用UAV 對(duì)計(jì)算卸載數(shù)據(jù)進(jìn)行收集的解決方案。首先，運(yùn)用現(xiàn)有的對(duì)于旋翼UAV 的功率計(jì)算函數(shù)及無(wú)線通信的能耗函數(shù)推導(dǎo)出本文描述場(chǎng)景中的能量消耗函數(shù)，并將問(wèn)題設(shè)定為在多個(gè)約束條件下該函數(shù)的最小化，該問(wèn)題需要優(yōu)化UAV 的飛行軌跡、飛行速率以及UAV 的通信策略，是一個(gè)非凸的問(wèn)題；之后，通過(guò)使用連續(xù)凸逼近方法，可以將原非凸問(wèn)題轉(zhuǎn)化為迭代求解凸優(yōu)化的問(wèn)題，在每次迭代時(shí)同時(shí)更新UAV 軌跡和通信時(shí)間分配；最后，可以收斂到一個(gè)滿足原問(wèn)題KKT（Karush-Kuhn-Tucker）條件的解。

在獲取了能耗最小化的策略后，進(jìn)一步設(shè)計(jì)了一個(gè)自適應(yīng)的聚類方法，通過(guò)多次迭代進(jìn)行分裂與合并，獲得合適的聚類策略，以保證每個(gè)聚類簇中所有的UE都可以在一次飛行中訪問(wèn)，且聚類的數(shù)量盡可能地少，從而減少UAV 的起飛次數(shù)以提高覆蓋效率，或減少UAV 的派遣數(shù)量（對(duì)于多UAV 訪問(wèn)多個(gè)聚類的場(chǎng)景）以降低覆蓋成本。

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

1.1 系統(tǒng)模型

如圖1 所示，考慮一種UAV 輔助的移動(dòng)邊緣計(jì)算下的數(shù)據(jù)收集場(chǎng)景。

圖1 無(wú)人機(jī)協(xié)助的移動(dòng)邊緣計(jì)算系統(tǒng)Fig.1 UAV-assisted MEC system

在此場(chǎng)景下，在地面上有N個(gè)UE，表示為集合N={1，2，…，N}，對(duì)于序號(hào)為n的UE（n∈N），其位置在三維坐標(biāo)系中表示為wn={xn，yn，0}，并有Offn大小的計(jì)算卸載數(shù)據(jù)需要上傳到邊緣服務(wù)器上。UAV 在此場(chǎng)景下作為移動(dòng)邊緣服務(wù)器的數(shù)據(jù)收集器，對(duì)全部UE的計(jì)算卸載數(shù)據(jù)進(jìn)行接收。將UAV 接收全部UE 數(shù)據(jù)的總時(shí)間表示為Tt，設(shè)UAV 的飛行高度恒定為H，其在t時(shí)刻的位置表示為loc(t)=(xt，yt，H)，0

其中β0表示距離為1 m 時(shí)的信道功率增益。根據(jù)香農(nóng)公式，UAV與第n個(gè)UE之間的傳輸速率Rn(t)可以表示為：

其中：B為信道帶寬；P為UE 的通信功率；σ2表示噪聲功率，表示單位距離為1 m 時(shí)的信噪比；將第n個(gè)UE在t時(shí)刻的通信狀態(tài)表示為Sn(t)，當(dāng)?shù)扔? 時(shí)表示第n個(gè)UE在t時(shí)刻與UAV 通信，0表示不通信。由于在TDMA 接入方式下UAV 在某個(gè)時(shí)刻t只能與1 個(gè)UE 通信，因此可以得到以下約束：

因此，在總的飛行時(shí)間里，UAV 與第n個(gè)UE 之間的傳輸數(shù)據(jù)量DATAn可以表示為：

由于UAV 需要收集所有UE 的數(shù)據(jù)，對(duì)于DATAn有以下約束：

1.2 UAV能耗模型

由文獻(xiàn)［18］中的研究可以得到，旋翼UAV 的飛行功率與速度之間的關(guān)系為：

其中各個(gè)參數(shù)的具體含義如表1所示。

表1 UAV相關(guān)參數(shù)Tab.1 UAV related parameters

當(dāng)速度為0 時(shí)，懸停功率可以表示為P0+Pi，由式（6），UAV在其飛行總時(shí)間內(nèi)的能耗可以表示為：

其中v(t)=。對(duì)于UAV 的通信能耗，設(shè)其在t時(shí)刻的通信功率為Pcomm(t)，因此，UAV 在飛行期間的通信能耗可以表示為：

考慮到UAV的最大通信功率為Pc，則有以下約束：

因此，UAV的總飛行能耗可以表示為：

1.3 聚類模型

由于UAV 板載電池的儲(chǔ)存電能有限，在大傳輸量或大分布范圍的場(chǎng)景下，單機(jī)單次飛行無(wú)法收集全部的計(jì)算卸載數(shù)據(jù)，需要派遣多架UAV同時(shí)執(zhí)行任務(wù)或單架UAV多次起降執(zhí)行任務(wù)。為此，將UAV 執(zhí)行的任務(wù)分成c個(gè)獨(dú)立的子任務(wù)，對(duì)于每個(gè)子任務(wù)taski(i∈[1，2，…，c])，將會(huì)在一次飛行中完成對(duì)于若干個(gè)UE進(jìn)行計(jì)算卸載數(shù)據(jù)的收集。將地面上的UE作為樣本，將UAV 需要執(zhí)行的子任務(wù)數(shù)量c作為聚類數(shù)目，就可將問(wèn)題轉(zhuǎn)化為將地面的N個(gè)樣本劃分成c個(gè)聚類的問(wèn)題。

首先，用Γi(i∈[1，2，…，c])表示第i個(gè)聚類，其中的樣本數(shù)表示為ki，則需要滿足約束：

此外，用Ei(i∈[1，2，…，c])表示UAV 收集聚類Γi中全部樣本所消耗的最小能量，將UAV 板載電池儲(chǔ)存的能量表示為Ecell，則需滿足以下約束：

1.4 問(wèn)題描述

基于以上討論，減少聚類的數(shù)量，將會(huì)減少派遣UAV 的成本，為此就需要UAV 以盡可能節(jié)能的策略飛行，從而可以在一次飛行中盡可能遍歷更多的UE，因此，問(wèn)題被分為能耗最小化和聚類數(shù)量最小化兩個(gè)問(wèn)題。

對(duì)于能耗最小化問(wèn)題，可以公式化表示為P1：

對(duì)于約束（18），由于UAV 使用場(chǎng)景的局限性，通常難以在任意位置起降，因此在本文模型中，考慮將起飛和降落點(diǎn)都設(shè)為同一個(gè)點(diǎn)loccenter。

對(duì)于聚類數(shù)量最小化問(wèn)題，可以公式化表述為P2：

由于在P2 的約束（12）中，Ei的計(jì)算依賴于對(duì)P1 的求解，因此，接下來(lái)的工作首先解決P1，得到一個(gè)計(jì)算Ei通用的方法，再根據(jù)此方法解決P2。

2 能量最小化方法

由于問(wèn)題P1是建立在連續(xù)時(shí)間變量上的，需要優(yōu)化的變量也是無(wú)限多的，無(wú)法有效求解，因此需要將其轉(zhuǎn)化為有限個(gè)變量的優(yōu)化問(wèn)題。首先將其飛行軌跡loc(t)轉(zhuǎn)化成有限個(gè)，將其細(xì)分成M個(gè)線段。在此，M的取值要足夠大，使每一個(gè)線段m的長(zhǎng)度足夠小，以使在每一個(gè)線段m∈[0，1，…，M-1]中，UAV 與各個(gè)UE 間的距離以及通信功率均可視為不變，從而可以將UAV 的軌跡近似視為M個(gè)固定的坐標(biāo)點(diǎn)組成的集合。為此，需要M+1個(gè)點(diǎn)來(lái)將路徑離散化，將這些點(diǎn)表示為集合{locm}，m∈[0，1，…，M]，其中，loc0=locM=loccenter，UAV 執(zhí)行任務(wù)的時(shí)間Tt也可以離散化為M個(gè)時(shí)間片段{Tm}，m∈[0，1，…，M-1]，Tm表示在線段m上的飛行時(shí)間。由于UAV 有飛行速度上限Vmax，在任意一個(gè)線段m上的飛行速度都不可能大于Vmax，因此可以將P1的約束（14）改寫(xiě)為：

將路徑離散化后，UAV 與第n個(gè)UE的距離不再是一個(gè)連續(xù)函數(shù)，而是M個(gè)表達(dá)式的集合。

將UAV 在線段m上飛行時(shí)與第n個(gè)UE 的通信時(shí)間表示為τmn，則需新增約束：

通信功率Pcomm(t)也可以離散化表示為Pm，m∈[0，1，…，M-1]，從而可以將約束（17）改寫(xiě)為：

對(duì)于P1中起飛和降落點(diǎn)的約束（18），同樣可以改寫(xiě)為：

用Δm=‖locm+1-locm‖，m∈[0，1，…，M-1]來(lái)表示線段m的長(zhǎng)度，則UAV 在線段m上的平均飛行速度vm可以轉(zhuǎn)化成Δm/Tm。將上述生成的離散化變量集合帶入P1 的目標(biāo)函數(shù)中，可以將原目標(biāo)函數(shù)改寫(xiě)為：

最終，可以將P1轉(zhuǎn)化為有限變量的優(yōu)化問(wèn)題P3，表示為：

P3 仍然是一個(gè)非凸問(wèn)題，因?yàn)槟繕?biāo)函數(shù)E({locm}，{Tm}，{τmn}，{Pm})以及約束（22）都是非凸的，難以直接求解，因此需要對(duì)其進(jìn)行轉(zhuǎn)化。首先，對(duì)于目標(biāo)函數(shù)的第一個(gè)非凸項(xiàng)，考慮到UAV 的主要能耗是保持飛行狀態(tài)所需的機(jī)械能耗，其通信能耗相對(duì)而言很小。因此，雖然減小通信功率可以降低一部分通信能耗，但是也會(huì)導(dǎo)致接收速率變低，從而使UAV 收集同樣大小數(shù)據(jù)的時(shí)間變長(zhǎng)，為此UAV 需要額外的懸?；蝻w行時(shí)間來(lái)完成任務(wù)，由此導(dǎo)致的額外機(jī)械能耗遠(yuǎn)大于節(jié)省的通信能耗。因此，想要最小化UAV 的飛行能耗，就必須將網(wǎng)卡的通信功率保持為UAV 所能提供的最大通信功率Pc以保持最大的數(shù)據(jù)接收速度。因此，可將其轉(zhuǎn)化為凸表達(dá)式，并將約束（23）省略。

此外，對(duì)于非凸約束（22），引入第二個(gè)松弛變量集合{ψmn}，將其表示為：

從而可以將式（22）改寫(xiě)為：

通過(guò)代換，可將松弛變量ψmn與原變量的關(guān)系表示為：

由定理1，問(wèn)題P3可以轉(zhuǎn)化為等價(jià)問(wèn)題P4：

定理1P3和P4等價(jià)。

證明 P3 與P4 的差別在于P4 中將松弛變量與原變量的關(guān)系表達(dá)式（27）、（30）變成了不等式約束（32）、（31），若P4 有一個(gè)解使約束（32）滿足嚴(yán)格不等條件，那么若不斷減小松弛變量φm，直到使約束（32）滿足嚴(yán)格相等條件，目標(biāo)函數(shù)E也會(huì)隨之逐漸減小，因此，此解一定不是P4 的最優(yōu)解，對(duì)于約束（31）同理。因此P4 的最優(yōu)解一定可以使約束（31）和（32）滿足嚴(yán)格相等條件，此時(shí)的目標(biāo)函數(shù)與約束都與P3 相同，因此P3與P4等價(jià)。證畢。

由于非凸約束（29），（31）和（32）的限制，P4 仍然非凸，然而，這3 個(gè)約束中的非凸表達(dá)式都可以通過(guò)替換獲取其在某個(gè)局部解的全局下界，從而將非凸表達(dá)式轉(zhuǎn)化為凸。對(duì)于約束（29），由于凸函數(shù)的一階泰勒展開(kāi)式可以視為凸函數(shù)的全局下界，可以將凸表達(dá)式在局部點(diǎn)處展開(kāi)，獲取其在的全局下界，表示為不等式：

對(duì)于約束（31）中不等式右側(cè)的表達(dá)式，雖然因?yàn)榉峭共荒苁褂靡浑A泰勒公式的性質(zhì)，但可以由定理2 獲取其全局下界，定理2表示如下：

證明 見(jiàn)文獻(xiàn)［21］中的定理2。

最終，將P4 中約束（29）、（31）和（32）中相關(guān)表達(dá)式替換為在局部點(diǎn)的全局下界表達(dá)式（33）、（35）和（34），可以將P4轉(zhuǎn)化為P5：

P5 在轉(zhuǎn)化后變成了一個(gè)凸問(wèn)題，可以使用相關(guān)的工具包進(jìn)行求解。在算法1 中，通過(guò)將P5 中的局部點(diǎn)逐步逼近到使目標(biāo)函數(shù)值更小的點(diǎn)，可以使每一輪迭代產(chǎn)生的局部最優(yōu)值逐漸趨近全局最優(yōu)值。當(dāng)兩輪迭代求得最優(yōu)值的比值大于給定閾值ε時(shí)，算法收斂，獲得的解可以視為原問(wèn)題P3的近似最優(yōu)解。算法1如下。

算法1 基于SCA的迭代算法。

算法的收斂性由定理3可知。

定理3算法1 每輪迭代的最優(yōu)值單調(diào)遞減且計(jì)算出的最優(yōu)解滿足原問(wèn)題P4的KKT條件。

證明 為方便起見(jiàn)，將P4 和P5 中的變量簡(jiǎn)單表示為x，將P4 中的約束表示為fi(x) ≥0，?i∈[1，2，…，I]，將算法1 中第j輪迭代計(jì)算P5時(shí)的全部約束表示為gi，j(x) ≥0，?j、?i∈[1，2，…，I]。

首先，由于在算法1中，第j輪迭代求解P5時(shí)的全部約束，一部分是將P4中的約束改寫(xiě)成了在某個(gè)局部點(diǎn)的全局下界，另一部分為原約束，因此可以滿足gi(x) ≤fi(x)。

由于滿足以上3 個(gè)條件，根據(jù)文獻(xiàn)［22］中的命題3 可知，算法1 最終迭代產(chǎn)生的解可以視為原問(wèn)題P4 的近似最優(yōu)解，且在此最優(yōu)解下的各項(xiàng)最優(yōu)值均滿足原問(wèn)題P4的KKT條件。證畢。

3 自適應(yīng)聚類方法

通過(guò)第2 章提出的能量最小化算法，可以在給定地面UE分布和數(shù)據(jù)傳輸量要求時(shí)，獲取使UAV 能耗最小的飛行軌跡、飛行速度以及與各個(gè)UE之間的通信時(shí)間。接下來(lái)?yè)?jù)此對(duì)地面上的終端進(jìn)行聚類，以減少飛行的次數(shù)或派遣UAV 的數(shù)量。為此，設(shè)計(jì)了一個(gè)以飛行能耗為聚類標(biāo)準(zhǔn)的自適應(yīng)聚類算法來(lái)解決P2，其具體步驟如算法2所示。

算法2 基于分裂與合并的自適應(yīng)聚類算法。

步驟1 將地面的N個(gè)UE表示為樣本集{w1，w2，…，wN}，c為聚類的數(shù)量，Ui(i=1，2，…，c)為初始的聚類中心。在算法開(kāi)始時(shí)，令c=1，隨機(jī)選取一個(gè)點(diǎn)Um作為聚類中心。

步驟2 按照以下關(guān)系

若‖w-Ui‖≤‖w-Uj‖；i，j=1，2，…，c且i≠j，則w∈Γi

將樣本分到各個(gè)聚類中去；

步驟3 按照以下關(guān)系

更新聚類中心Ui的位置，其中Ni是第i個(gè)聚類的樣本數(shù)目，wk為聚類Γi中的第k個(gè)樣本點(diǎn)。

步驟4 將Ui作為UAV 起飛和降落的地點(diǎn)loccenter，將聚類中的樣本作為此次飛行需要完成數(shù)據(jù)收集的UE集合，通過(guò)算法1計(jì)算其總能耗Ei。

步驟5 對(duì)于每一個(gè)聚類Γi(i=1，2，…，c)，判斷其總能耗Ei是否小于UAV機(jī)載能量Ecell，對(duì)于滿足能耗限制的聚類，將此聚類的樣本點(diǎn)及其總能耗Ei保存；對(duì)于超出機(jī)載能耗的聚類Γj，進(jìn)入步驟6；當(dāng)本步驟保存的全部聚類均滿足能量約束時(shí)，進(jìn)入步驟9。

步驟6 計(jì)算當(dāng)前不滿足能量約束的聚類Γj的標(biāo)準(zhǔn)差向量σj=[σjx，σjy]T，其中：

步驟12 計(jì)算以Unew為loccenter，以Γnew中的全部樣本作為需要完成計(jì)算卸載任務(wù)的UE 集合產(chǎn)生的能耗Enew，若Enew≤Ecell，則刪除生成Γnew的兩個(gè)原聚類，并使Γnew生效，令c=c-1，回到步驟9；如果Enew>Ecell，說(shuō)明不可合并，回到步驟10，從之前保存的位置向后繼續(xù)搜索。

算法2的整體流程如圖2所示。

圖2 算法2的流程Fig.2 Flowchart of algorithm 2

進(jìn)入步驟9 之前，算法通過(guò)不斷的分裂，將樣本分成多個(gè)滿足能量約束的聚類。由于某些特殊情況如樣本存在離群點(diǎn)，在步驟7 中通過(guò)標(biāo)準(zhǔn)差選擇的新聚類中心不合適等，分裂出的某些聚類內(nèi)樣本非常少，因此在步驟9～12將會(huì)嘗試對(duì)分裂完成后的聚類進(jìn)行合并。在步驟10 中，以聚類之間的距離Dij作為合并的優(yōu)先級(jí)，Dij越小，優(yōu)先級(jí)越高。由于當(dāng)兩個(gè)聚類各自的能量消耗之和大于Ecell時(shí)，合并出的新聚類將需要更多的能耗來(lái)完成數(shù)據(jù)收集任務(wù)，因此只有當(dāng)兩個(gè)聚類能量消耗之和小于機(jī)載能量Ecell時(shí)，才會(huì)嘗試進(jìn)行合并。在步驟12 中，一旦完成了合并，之前使用的遞增距離序列{Dij}將會(huì)失效，因此將返回步驟9 重新生成新的序列。若不能合并，則返回步驟10 繼續(xù)向后搜索下一個(gè)有合并可能的兩個(gè)聚類。當(dāng)步驟10 遍歷完{Dij}時(shí)，所有可能的合并操作已全部完成，算法結(jié)束。

4 仿真實(shí)驗(yàn)與分析

為驗(yàn)證所提出的能耗最小化算法和聚類算法的效果，設(shè)計(jì)了4個(gè)仿真實(shí)驗(yàn)，首先，在一個(gè)給定的UE 分布條件下，通過(guò)計(jì)算本文提出的能量最小化算法在不同卸載數(shù)據(jù)量下對(duì)應(yīng)的飛行軌跡來(lái)獲取結(jié)果，并分析其合理性。接著，設(shè)計(jì)了幾種不同的飛行軌跡方案來(lái)驗(yàn)證本文設(shè)計(jì)的算法在能耗方面的優(yōu)化。之后，為了呈現(xiàn)聚類算法的效果，在給定UE 的分布條件和各自的計(jì)算卸載數(shù)據(jù)量大小的情況下，將UAV 機(jī)載電池的能量作為變量，在固定的數(shù)據(jù)卸載量下獲取相應(yīng)的聚類結(jié)果。最后，在本文描述的應(yīng)用場(chǎng)景下，使用一種遞增聚類中心數(shù)目的K-Means 聚類算法與本文提出的聚類算法進(jìn)行對(duì)比，來(lái)驗(yàn)證本文提出的聚類算法的高效性和普適性。

4.1 實(shí)驗(yàn)環(huán)境與初始參數(shù)

仿真實(shí)驗(yàn)運(yùn)行在使用Intel Core i7 8750H 處理器，主頻為3.9 GHz，內(nèi)存為16 GB，操作系統(tǒng)為Ubuntu16.04 的計(jì)算機(jī)上，仿真程序代碼使用Python2.7 編寫(xiě)。對(duì)于優(yōu)化模塊，使用解決非線性優(yōu)化問(wèn)題的方法包PyOpt［23］來(lái)求解，使用的優(yōu)化器有SLSQP、ALGENCAN、NSGA2。

首先，對(duì)于UAV 相關(guān)參數(shù)，設(shè)UAV 重量W=20 N，空氣密度ρ=1.225 kg/m3，螺旋槳半徑R=0.4 m，螺旋槳梢速Utip=120 m/s，螺旋槳轉(zhuǎn)盤面積A=0.503 m2，懸停時(shí)轉(zhuǎn)子的感應(yīng)速率v0==4.03，螺旋槳葉片功率P0=79.856 W，感應(yīng)功率Pi=88.628 W，網(wǎng)卡最大通信功率Pc=5.0 W，螺旋槳在轉(zhuǎn)盤中的面積占比s=5%，UAV 的最大飛行速度Vmax=30.0 m/s。

此外，對(duì)于能耗最小化模塊，設(shè)置信道帶寬B=1MHz，UAV 的飛行高度H固定為100 m，噪聲功率σ2=-110 dBm，UE 的通信功率P為10 dBm，信道功率β0=-50 dB，由此可以計(jì)算出γ0=70 dB。

在算法1中，需要生成初始的軌跡集合、UAV 在每條線段m上的飛行時(shí)間集合以及在線段m上與第n個(gè)UE 的通信時(shí)間集合。在此，為了生成一個(gè)合理的初始值集合，使用動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）求解旅行商問(wèn)題（Traveling Salesman Problem，TSP）的方式，計(jì)算出以聚類中心為起點(diǎn)和終點(diǎn)，連接所有樣本點(diǎn)的最短路徑。然后將這條最短路徑離散化為M+1個(gè)點(diǎn)作為。之后計(jì)算出在此下可以滿足P3 約束的最小時(shí)間Tˉ作為集合中的每一項(xiàng)，并令τmn=作為的每一項(xiàng)，生成的結(jié)果作為算法1的初始值。實(shí)驗(yàn)設(shè)置了10個(gè)UE的位置，并將M設(shè)為30，以平衡精確度和算法的運(yùn)行時(shí)間。將全部N個(gè)UE 的計(jì)算卸載任務(wù)量Offn統(tǒng)一為同一個(gè)值，表示為Off，以方便算法的實(shí)現(xiàn)。

對(duì)于聚類模塊，由于在特定場(chǎng)景下，某個(gè)聚類中可能只含有一個(gè)樣本，而通過(guò)聚類算法計(jì)算的聚類中心位置，即起飛和降落點(diǎn)，也為此UE 的位置，因此，在實(shí)驗(yàn)中，設(shè)UAV 訪問(wèn)只有一個(gè)UE 的聚類時(shí)，飛行速度為0，在UE 的上方懸停，因此其產(chǎn)生的能耗僅與UE 的計(jì)算卸載任務(wù)量Offn有關(guān)。此外，設(shè)置聚類分裂時(shí)的分裂系數(shù)q=0.8。

4.2 結(jié)果與分析

首先，10 個(gè)UE 的位置如圖3 中所示，分別將數(shù)據(jù)傳輸量Off設(shè)置為0.1 Mb、1 Mb、10 Mb、100 Mb，使用所提出的能量最小化方案，獲得的軌跡如圖3所示。

圖3 四種數(shù)據(jù)傳輸量下的飛行軌跡對(duì)比Fig.3 Flight trajectories comparison under four data transmission amounts

由圖3（a）可知，當(dāng)吞吐量較小時(shí)，UAV 趨近于以一個(gè)半徑較小的接近環(huán)形的軌跡飛行，而不會(huì)向UE 的方向顯著偏移，這可以理解為當(dāng)傳輸量小時(shí)，雖然UAV 以此軌跡飛行會(huì)導(dǎo)致自身與UE 的距離較遠(yuǎn)，傳輸速率較低，但是由于數(shù)據(jù)量很小，傳輸速率降低導(dǎo)致的通信時(shí)間增加所產(chǎn)生的額外能耗并不如飛行時(shí)向UE偏向而產(chǎn)生的機(jī)械能耗大；當(dāng)數(shù)據(jù)量足夠大時(shí)，從圖3（d）中可以看出，UAV 趨近于在每一個(gè)UE 上方盤旋和懸停來(lái)與UE 通信，這也可以理解為由于數(shù)據(jù)量大，需要傳輸速率更快，這樣減少了總通信時(shí)間也就減少了飛行和懸停的時(shí)間，而由此節(jié)省的能量要大于向UE偏向所產(chǎn)生的額外機(jī)械能耗。當(dāng)吞吐量在一個(gè)適中的大小時(shí)，如圖3（b）、（c）所示，UAV 的軌跡會(huì)向UE 的位置偏移但不會(huì)飛至UE 的上方，這是優(yōu)化算法在飛行能耗和通信時(shí)間之間做出的權(quán)衡。

接下來(lái)，為了體現(xiàn)本文方案在能量上的優(yōu)化效果，本文額外設(shè)計(jì)了兩種使用固定軌跡的方案作為對(duì)比：第一種將UAV設(shè)置為在全體UE 的中心（質(zhì)心）上方懸停，表示為CENTER；第二種使UAV 沿著TSP 算法生成的固定軌跡飛行，表示為TSP，這兩種方案相對(duì)簡(jiǎn)單且易于實(shí)現(xiàn)；將本文所提出的能量最小化方案表示為ENERGY。在不同數(shù)據(jù)傳輸量Off下的能量消耗如表2所示。

從表2 可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，能量最小化方案對(duì)比TSP 方案具有顯著的優(yōu)勢(shì)，這是因?yàn)槠滹w行距離較短，節(jié)省了許多飛行能耗，而由于其飛行軌跡接近于在起飛點(diǎn)附近盤旋，其結(jié)果也接近于懸停方案；當(dāng)數(shù)據(jù)量逐漸變大，能量最小化方案的能耗逐漸接近于TSP方案，這是由于數(shù)據(jù)量變大，飛行軌跡逐漸接近于TSP 的軌跡造成的，而在此時(shí)使用懸停方案產(chǎn)生的能耗將會(huì)顯著變大，這是由于較大的數(shù)據(jù)量和較低的信道速率導(dǎo)致的較長(zhǎng)的懸停時(shí)間所導(dǎo)致。而本文所提出的能量最小化方案通過(guò)連續(xù)凸逼近的方法，平衡了通信速率和飛行距離，在不同的數(shù)據(jù)傳輸量下都有著更低的能耗。

表2 無(wú)人機(jī)在不同飛行方案下的能量消耗 單位：JTab.2 UAV energy consumption under different flight strategies unit：J

對(duì)于聚類方案的評(píng)估，仍然使用圖3 中的UE 分布，在全部UE 的計(jì)算卸載的數(shù)據(jù)量Off固定為10 Mb 的條件下，在不同的機(jī)載能量Ecell下聚類的結(jié)果和UAV在各個(gè)聚類中的飛行軌跡如圖4所示。

圖4 兩種機(jī)載能量條件下的聚類結(jié)果和飛行軌跡對(duì)比Fig.4 Comparison of clustering results and flight trajectories under two airborne energy conditions

在圖4 中，在Ecell為10 kJ 時(shí)，分成了3 個(gè)聚類；在Ecell為15 kJ 時(shí)分成了2 個(gè)聚類。由此可以看出，UAV 的機(jī)載電池儲(chǔ)存的能量越大，其在一次飛行中可以訪問(wèn)的UE 數(shù)量越多，每個(gè)聚類中的樣本數(shù)量也就越大。若以每個(gè)UE 的數(shù)據(jù)卸載量Off為變量，在同樣的機(jī)載能量Ecell下，得到的聚類結(jié)果也遵循此規(guī)律，在此不再贅述。

最后，在多種聚類策略中，基于歐氏距離進(jìn)行劃分的聚類算法適合本文中對(duì)UE進(jìn)行分類的場(chǎng)景，而由于現(xiàn)有的基于劃分的聚類算法需要在算法開(kāi)始時(shí)預(yù)先確定k個(gè)初始中心點(diǎn)，而在不同的UE 分布場(chǎng)景下，合適的k值也是不同的，因此，為了使算法可以在不同的UE 分布場(chǎng)景中獲得合適的初始中心點(diǎn)數(shù)目，設(shè)計(jì)了一種遞增k的K-Means 聚類算法：從1 開(kāi)始逐步遞增k，在每次迭代中隨機(jī)確定k個(gè)聚類中心的位置并使用K-Means算法獲取聚類結(jié)果，對(duì)所得的k個(gè)聚類分別計(jì)算UAV訪問(wèn)此聚類的能量消耗，若有某個(gè)聚類的能量超出了Ecell，則k=k+1。直到當(dāng)k到達(dá)某個(gè)值時(shí)，對(duì)于每個(gè)聚類，其全部UE的計(jì)算卸載數(shù)據(jù)都可以在一次飛行中收集，算法結(jié)束，記當(dāng)前值k=k*。在此，分別使用K-Means 和K-Means++算法作為上述遞增k的聚類算法獲取聚類結(jié)果的方案，將這兩組方案計(jì)算出的最終聚類數(shù)量與本文所提出的聚類算法計(jì)算出的聚類數(shù)量進(jìn)行對(duì)比。實(shí)驗(yàn)樣本使用網(wǎng)址http：//elib.zib.de/pub/mptestdata/tsp/tsplib/tsp/index.html 中的數(shù)據(jù)集att48.tsp，為了提高計(jì)算效率，取其中的前40條數(shù)據(jù)并分成4組，并將其中的每條數(shù)據(jù)的橫縱坐標(biāo)大小都除以10。在前兩組的對(duì)比中，將數(shù)據(jù)卸載量Off設(shè)為25 Mb，機(jī)載能量Ecell設(shè)為20 kJ；在后兩組的對(duì)比中，將數(shù)據(jù)卸載量Off設(shè)為50 Mb，機(jī)載能量Ecell設(shè)為25 kJ，最終得出的聚類數(shù)量如表3所示。

從表3 可以看出，本文提出的算法產(chǎn)生的聚類數(shù)量在幾個(gè)不同的樣例下都小于或等于K-Means 和K-Means++聚類的聚類數(shù)量。這是因?yàn)镵-Means 算法的結(jié)果受初始聚類中心的影響較大，而由于在本文場(chǎng)景下，UE 的分布情況在不同的時(shí)間、地點(diǎn)時(shí)沒(méi)有可循的規(guī)律，只能通過(guò)隨機(jī)生成初始聚類中心的方法來(lái)初始化K-Means 算法，當(dāng)初始聚類中心的位置不夠理想時(shí)，最終計(jì)算出的聚類數(shù)量就會(huì)偏大，即使使用K-Means++優(yōu)化了初始聚類中心點(diǎn)的離散程度，由于某些離群點(diǎn)的存在，其結(jié)果仍然不夠理想。而本文提出的方法通過(guò)動(dòng)態(tài)分裂與合并來(lái)調(diào)整聚類的數(shù)量，不依賴初始聚類中心的位置，可以廣泛適應(yīng)不同的UE 分布場(chǎng)景；也不需要逐步遞增聚類數(shù)目，可以快速收斂。

表3 在不同數(shù)據(jù)集上三種聚類算法的最終聚類數(shù)量Tab.3 Final number of clusters of three algorithms on different datasets

5 結(jié)語(yǔ)

針對(duì)當(dāng)前UAV 的應(yīng)用場(chǎng)景及其局限性，本研究以能量約束作為聚類是否可行的標(biāo)準(zhǔn)、以最小化聚類的數(shù)量為目的設(shè)計(jì)了一個(gè)自適應(yīng)的聚類算法。通過(guò)解決給定地面終端分布下的能量最小化問(wèn)題，獲得了一個(gè)可以有效判斷聚類方案是否可行的依據(jù)，并通過(guò)多次分裂和合并，在可以快速收斂的前提下將聚類的數(shù)量有效地縮減。該方法可以應(yīng)用在如智能工業(yè)、智慧城市等前沿領(lǐng)域，使用UAV 輔助進(jìn)行大范圍的信息采集，數(shù)據(jù)同步。本文將UAV 的起飛和降落點(diǎn)簡(jiǎn)單考慮為聚類中心，有一定的局限性。首先，聚類中心所在的位置在現(xiàn)實(shí)場(chǎng)景中并不一定支持UAV 起降；其次，UAV 并不一定需要在同一點(diǎn)起降，若考慮起飛和降落點(diǎn)的優(yōu)化，對(duì)于某一聚類內(nèi)UE 的數(shù)據(jù)收集所需的能量可能會(huì)更?。淮送?，多次飛行之間并無(wú)相互之間的聯(lián)系，若在地面設(shè)置某些固定的可以為無(wú)人機(jī)充電的起降點(diǎn)，并將UAV 的起降位置設(shè)置為這些起降點(diǎn)，就可將完成各個(gè)聚類收集任務(wù)的軌跡連接到一起，這意味著全部任務(wù)的完成將全程自動(dòng)，具有更強(qiáng)的實(shí)用性。而對(duì)于能量最小化模塊，其目標(biāo)函數(shù)將飛行高度設(shè)為定值，并未考慮用戶設(shè)備的水平高度帶來(lái)的影響。因此，下一步的研究將會(huì)在能量最小化中加入飛行高度變量，以及優(yōu)化起降點(diǎn)的選擇，使模型更加符合各種應(yīng)用場(chǎng)景的需求。