李 斌 劉文帥 費(fèi)澤松

①(南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院 南京 210044)

②(北京理工大學(xué)信息與電子學(xué)院 北京 100081)

1 引言

隨著5G網(wǎng)絡(luò)的不斷成熟，物聯(lián)網(wǎng)的高速發(fā)展，物聯(lián)網(wǎng)設(shè)備將部署在地球上的任何地方，用于執(zhí)行某些具有特定計(jì)算需求的任務(wù)[1,2]。然而由于一些部署在山脈和海洋等復(fù)雜地形的設(shè)備，僅僅依靠傳統(tǒng)地面無線網(wǎng)絡(luò)可能無法滿足物聯(lián)網(wǎng)設(shè)備的計(jì)算要求。此外，地面網(wǎng)絡(luò)的基礎(chǔ)設(shè)施易受地震和颶風(fēng)等自然災(zāi)害的破壞，這可能會(huì)中斷設(shè)備通信。為了解決上述問題，空天地異構(gòu)網(wǎng)絡(luò)(Space-Air-Ground Integrated Network, SAGIN)的研究成為未來6G網(wǎng)絡(luò)架構(gòu)的核心方向之一[3-7]，將人類的網(wǎng)絡(luò)空間提升到一個(gè)新的維度。具體而言，SAGIN可分為3個(gè)部分，即天基網(wǎng)絡(luò)、空基網(wǎng)絡(luò)和地基網(wǎng)絡(luò)。在空基網(wǎng)絡(luò)中，無人機(jī)(Unmanned Aerial Vehicle, UAV)作為空中飛行基站為地面終端用戶提供低時(shí)延的移動(dòng)邊緣計(jì)算(Mobile Edge Computing, MEC)服務(wù)。在天基網(wǎng)絡(luò)中的低軌(Low Earth Orbit, LEO)衛(wèi)星可通過無縫網(wǎng)絡(luò)覆蓋提供無處不在的云計(jì)算服務(wù)[8]。通過多種網(wǎng)絡(luò)深度融合，SAGIN可以綜合利用各自資源，從而滿足差異化應(yīng)用與用戶需求。

目前關(guān)于空地協(xié)同或天地協(xié)同的研究已經(jīng)取得了很多有價(jià)值的研究成果[9-13]。譬如，為了權(quán)衡無人機(jī)和地面設(shè)備的能耗，文獻(xiàn)[9]通過引入權(quán)重因子，聯(lián)合優(yōu)化無人機(jī)軌跡、系統(tǒng)資源使得系統(tǒng)能耗最小化。為了解決用戶在卸載數(shù)據(jù)時(shí)存在竊聽問題，文獻(xiàn)[10]通過聯(lián)合優(yōu)化用戶關(guān)聯(lián)匹配混合資源分配，提出了一種最小化系統(tǒng)能耗的安全卸載策略。為了研究空地協(xié)同網(wǎng)絡(luò)性能，文獻(xiàn)[11]提出了一種新的MEC框架，其框架包括多個(gè)地面服務(wù)器以及1個(gè)由無人機(jī)攜帶的空中服務(wù)器，通過聯(lián)合優(yōu)化通信和計(jì)算資源及無人機(jī)軌跡使得系統(tǒng)的加權(quán)計(jì)算效率最大化。隨著LEO衛(wèi)星的最新發(fā)展，為探究衛(wèi)星的任務(wù)處理能力，文獻(xiàn)[12]提出了利用衛(wèi)星為遠(yuǎn)程設(shè)備提供計(jì)算服務(wù)，通過聯(lián)合優(yōu)化通信和計(jì)算資源使得系統(tǒng)能耗最小化。為了探索天地協(xié)同網(wǎng)絡(luò)性能，文獻(xiàn)[13]提出了一個(gè)具有3層計(jì)算結(jié)構(gòu)的混合云和攜帶MEC服務(wù)器的LEO衛(wèi)星網(wǎng)絡(luò)，研究了地面用戶、LEO衛(wèi)星邊緣節(jié)點(diǎn)和云服務(wù)器之間的協(xié)作關(guān)系，在LEO衛(wèi)星的覆蓋時(shí)間和計(jì)算能力的約束下最小化地面用戶的總能耗。近期，由北京郵電大學(xué)深圳研究院與天儀研究院共同發(fā)起的“天算星座”實(shí)驗(yàn)，通過對(duì)衛(wèi)星智能化，構(gòu)建空天協(xié)同計(jì)算網(wǎng)絡(luò)，為推動(dòng)我國衛(wèi)星互聯(lián)網(wǎng)發(fā)展提供技術(shù)支撐。

隨著各類應(yīng)用需求的不斷提升，為充分利用SAGIN的互補(bǔ)特性，實(shí)現(xiàn)無線網(wǎng)絡(luò)與MEC技術(shù)的有機(jī)融合，涌現(xiàn)出了一些工作[14-17]。譬如，文獻(xiàn)[14]將衛(wèi)星當(dāng)作空中中繼節(jié)點(diǎn)，將用戶的任務(wù)通過衛(wèi)星中繼傳輸?shù)降孛娣?wù)器進(jìn)行處理。文獻(xiàn)[15]將無人機(jī)當(dāng)作移動(dòng)中繼節(jié)點(diǎn)，將用戶的任務(wù)通過無人機(jī)中繼傳輸給LEO衛(wèi)星處理。而上述文獻(xiàn)忽視了直接在衛(wèi)星或無人機(jī)上進(jìn)行任務(wù)處理的可行性。為了探索空天地協(xié)同計(jì)算的可行性，文獻(xiàn)[16]提出SAGIN邊緣/云計(jì)算框架，其中無人機(jī)為地面用戶提供邊緣計(jì)算服務(wù)，衛(wèi)星提供云計(jì)算服務(wù)，在能量和計(jì)算的限制下加載計(jì)算密集型任務(wù)，通過聯(lián)合優(yōu)化資源分配和任務(wù)調(diào)度，尋求最優(yōu)卸載策略。文獻(xiàn)[17]將LEO衛(wèi)星和高空平臺(tái)結(jié)合起來為地面用戶提供邊緣計(jì)算服務(wù)，通過聯(lián)合優(yōu)化關(guān)聯(lián)匹配、傳輸預(yù)編碼矩陣、計(jì)算任務(wù)分配和資源分配實(shí)現(xiàn)系統(tǒng)總能耗最小化。上述研究工作展現(xiàn)出空天地異構(gòu)網(wǎng)絡(luò)的巨大優(yōu)勢，然而它們僅考慮了時(shí)延或能耗的單一約束。

不同于上述研究，文獻(xiàn)[18]考慮了時(shí)延和能耗共同約束，通過聯(lián)合優(yōu)化通信和計(jì)算資源來提高SAGIN性能。但是該工作將無人機(jī)當(dāng)作空中靜止服務(wù)器，未考慮無人機(jī)固有的移動(dòng)本質(zhì)。為了充分利用UAV靈活部署、高機(jī)動(dòng)性以及LEO衛(wèi)星廣域覆蓋的特點(diǎn)，進(jìn)一步挖掘空天地異構(gòu)網(wǎng)絡(luò)的互惠潛力，本文提出一種面向SAGIN的移動(dòng)邊緣計(jì)算系統(tǒng)，如何合理地進(jìn)行多邊緣節(jié)點(diǎn)的協(xié)同計(jì)算和資源有效分配是亟待解決的關(guān)鍵問題，其主要貢獻(xiàn)如下：

(1)本文將多無人機(jī)引入空天地異構(gòu)網(wǎng)絡(luò)中，并在部分卸載的基礎(chǔ)上，聯(lián)合優(yōu)化用戶匹配關(guān)聯(lián)因子、用戶任務(wù)分配量、帶寬分配、無人機(jī)計(jì)算資源分配以及多無人機(jī)的軌跡，構(gòu)建一個(gè)整數(shù)、非線性、多變量耦合的能耗最小化問題。

(2)為了求解該非凸優(yōu)化問題，本文采用交替迭代優(yōu)化算法，將原非凸問題分解為3個(gè)子問題，并利用變量替換和連續(xù)凸逼近算法進(jìn)行求解，并提出一種基于迭代的能耗最小化資源分配算法。最后給出了算法的收斂性和計(jì)算復(fù)雜度。

(3)仿真結(jié)果表明，本文算法具有良好的收斂特性以及在降低系統(tǒng)能耗方面的有效性。

2 系統(tǒng)模型

如圖1所示，空天地網(wǎng)絡(luò)中有1顆攜帶服務(wù)器的LEO衛(wèi)星和M架攜帶微服務(wù)器的UAV為K個(gè)地面終端用戶服務(wù)。其中，信關(guān)站作為控制中心，負(fù)責(zé)收集衛(wèi)星、無人機(jī)和用戶間的鏈路信道信息以及地面用戶的服務(wù)需求等參數(shù)，用于進(jìn)行邊緣網(wǎng)絡(luò)中計(jì)算和通信資源分配和無人機(jī)軌跡規(guī)劃。為了便于表達(dá)和分析，定義用戶、UAV的集合分別為?k ∈K?{1,2,...,K}，?m ∈M?{1,2,...,M}。由于LEO衛(wèi)星具有高速運(yùn)動(dòng)的特性，因此用戶與LEO衛(wèi)星之間通信時(shí)長會(huì)受LEO覆蓋時(shí)間的限制。假設(shè)UAV的飛行周期和LEO衛(wèi)星覆蓋時(shí)間相同，記為T。UAV飛行在固定高度H，為了使得UAV的位置相對(duì)用戶近乎保持不變，將T 分割為長度為δt=T/N的足夠小的時(shí)隙，且僅在不同時(shí)隙下UAV的位置發(fā)生變化，記時(shí)隙集合?n ∈N={1,2,...,N}。采用笛卡爾坐標(biāo)系，UAV m在第n個(gè)時(shí)隙內(nèi)的位置為qm[n]=[xm[n],ym[n],H]，用戶k的位置固定為wk=[xk,yk,0]。UAV m在每個(gè)時(shí)隙內(nèi)距離變化與飛行速度有關(guān)，假設(shè)UAV m在飛行周期結(jié)束后返回起點(diǎn)，為了避免UAV之間發(fā)生碰撞，其位移約束須滿足以下約束

圖1 系統(tǒng)模型圖

2.1 LEO衛(wèi)星覆蓋時(shí)間模型

因此，地面終端用戶與低軌衛(wèi)星之間的最長通信時(shí)間可表示為

圖2 低軌衛(wèi)星與地面終端用戶的幾何關(guān)系圖

2.2 通信模型

2.3 計(jì)算模型

3 優(yōu)化問題描述

在本文中，通過聯(lián)合優(yōu)化用戶匹配關(guān)聯(lián)因子、用戶任務(wù)分配、帶寬分配、無人機(jī)計(jì)算資源分配以及無人機(jī)的軌跡，實(shí)現(xiàn)無人機(jī)的總能耗最小化。具體優(yōu)化問題建模為

其中，約束C1和約束C2表示無人機(jī)的飛行軌跡，約束C3表示無人機(jī)之間的安全距離來防止碰撞，約束C4表示用戶計(jì)算任務(wù)分配的約束，約束C5表示本地計(jì)算的任務(wù)需要在時(shí)長T內(nèi)完成，約束C6和C7表示劃分給UAV的任務(wù)量需要在時(shí)長T內(nèi)完成，約束C8表示劃分給LEO的任務(wù)量需要在時(shí)長T內(nèi)完成，約束C9表示用戶的總能耗不能超過其可用能量，約束C10和C11表示用戶只能關(guān)聯(lián)1個(gè)UAV，約束C12表示帶寬分配比率，約束C13表示限制UAV自身最大CPU計(jì)算頻率。由于目標(biāo)函數(shù)的非線性以及約束條件C10是整數(shù)變量，使得上述問題是非線性整數(shù)規(guī)劃問題，很難求得其最優(yōu)解。

4 優(yōu)化問題求解

由于問題式(8)是變量高度耦合的非線性整數(shù)規(guī)劃問題，難以直接進(jìn)行求解。為了有效求解該問題，本文采取交替優(yōu)化的策略，將其分解為3個(gè)子問題進(jìn)行求解，分別為用戶無人機(jī)的關(guān)聯(lián)匹配、計(jì)算任務(wù)和帶寬分配、無人機(jī)計(jì)算資源分配和無人機(jī)軌跡優(yōu)化。

4.1 關(guān)聯(lián)匹配

4.2 計(jì)算任務(wù)和帶寬分配

上述問題是線性規(guī)劃問題，它可以借助優(yōu)化工具進(jìn)行求解(例如CVX)。

4.3 無人機(jī)計(jì)算資源分配和軌跡優(yōu)化

上述問題是標(biāo)準(zhǔn)凸優(yōu)化問題，可以借助凸優(yōu)化求解軟件(例如CVX)進(jìn)行求解。

5 復(fù)雜度與收斂性分析

在前一小節(jié)中，將原始問題分解為3個(gè)子問題，并通過松弛和連續(xù)凸逼近等方法將非凸問題轉(zhuǎn)換成凸問題，進(jìn)而提出一種基于交替迭代的優(yōu)化算法求解原問題式(8)。交替優(yōu)化算法的實(shí)現(xiàn)過程如表1所示。

表1 交替優(yōu)化算法(算法1)

5.1 復(fù)雜度分析

5.2 收斂性分析

6 仿真結(jié)果與分析

圖3 K=12時(shí)多個(gè)UAV的飛行軌跡

平均值為5.394 m/s，從圖中可以觀察到時(shí)隙內(nèi)的飛行速度變化較為平滑?？紤]到飛行能耗隨速度的增大而快速升高，優(yōu)化后的飛行速度波動(dòng)較小這一現(xiàn)象進(jìn)一步驗(yàn)證了軌跡優(yōu)化與能耗最小化的關(guān)聯(lián)性。

圖4驗(yàn)證了不同方案下算法的收斂性，其中系統(tǒng)包含12個(gè)用戶，可以看出，采用交替優(yōu)化算法求解在7次迭代左右達(dá)到收斂。所對(duì)比的固定圓形軌跡策略中，各UAV的軌跡均為半徑為500 m的圓，對(duì)于UAV 1, UAV 2和UAV 3，出發(fā)點(diǎn)與圓心連線分別平行和垂直于y軸。與固定圓形軌跡方案相比，所提算法收斂速度略慢，但目標(biāo)值更優(yōu)，能耗減小了43.3%，這一點(diǎn)驗(yàn)證了所提算法具有較好的性能。

圖4 交替優(yōu)化算法的收斂曲線

為進(jìn)一步驗(yàn)證系統(tǒng)的服務(wù)效果，圖5繪制了各個(gè)時(shí)隙內(nèi)5個(gè)用戶的卸載速率。由圖可知，用戶卸載速率有較大的波動(dòng)，并且每個(gè)用戶都至少獲得了一個(gè)速率較大的時(shí)間段用作任務(wù)卸載傳輸，對(duì)應(yīng)于UAV先靠近用戶提供卸載服務(wù)，后遠(yuǎn)離并服務(wù)其他用戶的過程。該現(xiàn)象驗(yàn)證了優(yōu)化算法利用UAV自身移動(dòng)性，使用戶得到滿足需求的傳輸速率與傳輸時(shí)間，兼顧到所有用戶的服務(wù)質(zhì)量。

圖5 K=5時(shí)用戶在不同時(shí)隙內(nèi)的卸載速率

圖6表示不同方案下，用戶數(shù)量變化對(duì)UAV能耗的影響。對(duì)于固定帶寬方案，每個(gè)用戶均分帶寬；對(duì)于隨機(jī)關(guān)聯(lián)方案，用戶隨機(jī)選擇關(guān)聯(lián)的UAV。從圖中可見，隨用戶數(shù)增加，UAV能耗增長速度逐漸變大。用戶數(shù)量較小時(shí)，能耗增加幅度較小，這是由于UAV資源充足，能以較小的飛行代價(jià)與計(jì)算開銷服務(wù)用戶。而當(dāng)用戶數(shù)量增大時(shí)，由于用戶分布具有隨機(jī)性，UAV飛行中任務(wù)卸載時(shí)，所關(guān)聯(lián)的用戶無法全部以較短的時(shí)間完成卸載傳輸，導(dǎo)致留給UAV計(jì)算任務(wù)的時(shí)間減少，計(jì)算頻率增大，計(jì)算能耗快速升高。

圖6 UAV能耗隨用戶數(shù)量變化

7 結(jié)束語

本文研究了空天地異構(gòu)網(wǎng)絡(luò)賦能的移動(dòng)邊緣計(jì)算部分任務(wù)卸載及資源分配算法。首先，分析了低軌衛(wèi)星的覆蓋時(shí)間，建立了通信模型和計(jì)算模型。通過聯(lián)合優(yōu)化用戶與無人機(jī)之間的關(guān)聯(lián)匹配、用戶任務(wù)分配、帶寬分配、無人機(jī)計(jì)算資源分配和無人機(jī)軌跡，實(shí)現(xiàn)無人機(jī)能耗最小化。其次，為了有效求解這個(gè)具有離散二進(jìn)制變量和耦合約束的非凸問題，將原問題分解為3個(gè)子問題，并采用變量替換和連續(xù)凸近似方法將原問題轉(zhuǎn)為凸優(yōu)化問題進(jìn)行求解。最后，通過仿真驗(yàn)證了所提算法的收斂性與在降低無人機(jī)能耗方面的有效性。下一步將在本文的基礎(chǔ)上考慮由于低軌衛(wèi)星高速運(yùn)動(dòng)而導(dǎo)致用戶離開服務(wù)衛(wèi)星的覆蓋范圍而中斷服務(wù)，由此考慮為保障用戶通信的連續(xù)性，將用戶的任務(wù)切換至其它衛(wèi)星，考慮多顆低軌衛(wèi)星協(xié)同下的卸載方案。