考慮任務(wù)依賴的衛(wèi)星邊緣計算資源分配與卸載決策算法*

方 海,趙 揚(yáng),高 媛,楊 旭

(西安空間無線電技術(shù)研究所，陜西 西安 710100)

1 引言

衛(wèi)星是6G網(wǎng)絡(luò)的重要節(jié)點(diǎn)[1 - 4]，以星鏈為代表的衛(wèi)星星座正在快速地發(fā)展[5]。在傳統(tǒng)的衛(wèi)星任務(wù)處理模式中，數(shù)據(jù)傳輸?shù)降孛鏀?shù)據(jù)中心進(jìn)行處理，隨著6G網(wǎng)絡(luò)中衛(wèi)星業(yè)務(wù)的不斷擴(kuò)展和豐富，海量數(shù)據(jù)將導(dǎo)致更長的數(shù)據(jù)傳輸時間和更大的帶寬壓力。

邊緣計算的出現(xiàn)為用戶利用網(wǎng)絡(luò)邊緣節(jié)點(diǎn)的計算能力進(jìn)行數(shù)據(jù)處理提供了新的模式[6]。在邊緣計算模式下，將分散在每顆衛(wèi)星上的計算資源整合到同一架構(gòu)中，實(shí)現(xiàn)分散衛(wèi)星計算能力的融合，為衛(wèi)星處理海量數(shù)據(jù)任務(wù)和時敏任務(wù)提供了統(tǒng)一的在軌邊緣計算能力，能夠更充分利用在軌計算資源，節(jié)省海量數(shù)據(jù)傳輸帶寬，提高實(shí)時數(shù)據(jù)分析能力，實(shí)現(xiàn)衛(wèi)星資源的高效利用。任務(wù)卸載是邊緣計算中的關(guān)鍵技術(shù)之一，即何時將何任務(wù)卸載到哪個邊緣處理器，任務(wù)卸載決策算法是系統(tǒng)高效運(yùn)行的關(guān)鍵。

對于衛(wèi)星邊緣計算，文獻(xiàn)[7-9]研究了衛(wèi)星邊緣計算應(yīng)用場景，給出了衛(wèi)星網(wǎng)絡(luò)邊緣計算的體系架構(gòu)。在卸載決策算法上文獻(xiàn)[10,11]基于深度強(qiáng)化學(xué)習(xí),文獻(xiàn)[12]基于博弈論進(jìn)行了衛(wèi)星邊緣計算場景中多個移動設(shè)備競爭多顆衛(wèi)星星載資源的卸載決策，以降低系統(tǒng)時延和能耗。文獻(xiàn)[13,14]通過將原始非凸問題轉(zhuǎn)換為凸問題，解決了同時滿足低軌衛(wèi)星覆蓋時間和計算能力約束的用戶總能耗最小化問題。以上算法均將待卸載任務(wù)視為不可分割的實(shí)體，用戶任務(wù)必須作為一個整體在本地或邊緣處理器執(zhí)行。但是將用戶任務(wù)分解成子任務(wù)，可以提高卸載效率[15]。文獻(xiàn)[15]中子任務(wù)必須順序地執(zhí)行,但是在實(shí)際中有依賴關(guān)系的子任務(wù)必須順序執(zhí)行，相互獨(dú)立的子任務(wù)可以并行執(zhí)行。文獻(xiàn)[16-18]考慮了子任務(wù)之間的依賴關(guān)系，但是均沒有考慮子任務(wù)待處理數(shù)據(jù)發(fā)送時的無線資源分配。雖然子任務(wù)的卸載可以減少任務(wù)節(jié)點(diǎn)的能源消耗，但因為卸載的子任務(wù)會導(dǎo)致任務(wù)節(jié)點(diǎn)和邊緣處理器之間的通信延遲，總體任務(wù)延遲還與任務(wù)待處理數(shù)據(jù)通信的無線資源分配有關(guān)。

隨著衛(wèi)星技術(shù)的發(fā)展，多處理器系統(tǒng)已實(shí)現(xiàn)星載應(yīng)用。與現(xiàn)有工作不同，本文考慮星載多處理器系統(tǒng)環(huán)境，提出了一種聯(lián)合無線資源分配同時考慮子任務(wù)依賴關(guān)系的卸載決策調(diào)度算法，且基于啟發(fā)式搜索算法，在保證任務(wù)依賴性的同時能夠降低任務(wù)延遲和能量消耗。

2 系統(tǒng)模型

衛(wèi)星網(wǎng)絡(luò)包含高軌衛(wèi)星和低軌衛(wèi)星，高軌衛(wèi)星相對于低軌衛(wèi)星一般是大衛(wèi)星，相對有較高的整星功率和計算能力。為了充分利用衛(wèi)星網(wǎng)絡(luò)的計算能力，本文重點(diǎn)解決低軌衛(wèi)星計算任務(wù)卸載到高軌衛(wèi)星的計算卸載問題。

2.1 衛(wèi)星邊緣計算架構(gòu)

高低軌協(xié)同的衛(wèi)星邊緣計算網(wǎng)絡(luò)體系結(jié)構(gòu)如圖1所示。低軌道衛(wèi)星群位于衛(wèi)星網(wǎng)絡(luò)邊緣計算層的網(wǎng)絡(luò)邊緣。該層衛(wèi)星節(jié)點(diǎn)較多，搭載的嵌入式計算設(shè)備算力有限，但可以為空間或地面用戶提供高可靠性、低延遲的邊緣處理能力。高軌衛(wèi)星通信覆蓋范圍廣，可以實(shí)現(xiàn)對低軌衛(wèi)星群的全覆蓋，高軌衛(wèi)星計算和帶寬資源充足，適合處理計算量大的復(fù)雜任務(wù)，同時可以負(fù)責(zé)衛(wèi)星邊緣計算網(wǎng)絡(luò)資源的管理。低軌衛(wèi)星計算任務(wù)可以卸載到所接入的高軌衛(wèi)星，也可以在本地計算。低軌衛(wèi)星的計算任務(wù)可以是低軌衛(wèi)星本身產(chǎn)生的，也可以是接入該衛(wèi)星的陸?？仗斓冉K端產(chǎn)生的。

Figure 1 System structure of satellite edge computing圖1 衛(wèi)星邊緣計算系統(tǒng)結(jié)構(gòu)圖

2.2 任務(wù)模型

2.3 通信模型

在高低軌協(xié)同計算的衛(wèi)星網(wǎng)絡(luò)中，低軌衛(wèi)星子任務(wù)可以卸載到高軌衛(wèi)星中的任一處理器執(zhí)行或在本地執(zhí)行。將低軌衛(wèi)星u到高軌衛(wèi)星的可用帶寬W分成Q個子帶，低軌衛(wèi)星u的任務(wù)可以分配使用bu個子帶，0≤bu≤Q。僅考慮低軌衛(wèi)星到高軌衛(wèi)星鏈路的帶寬分配，高軌衛(wèi)星內(nèi)部處理器之間通過內(nèi)部高速交換網(wǎng)絡(luò)全互聯(lián)，設(shè)高軌衛(wèi)星內(nèi)部處理器之間的傳輸速率為R。

低軌衛(wèi)星u到高軌衛(wèi)星的鏈路信噪比如式(1)所示：

(1)

其中，U為低軌衛(wèi)星集合,N0為背景噪聲功率譜密度;hu為低軌衛(wèi)星u到高軌衛(wèi)星的上行信道增益，包括路損和天線增益;pu為低軌衛(wèi)星u卸載任務(wù)時數(shù)據(jù)發(fā)送的發(fā)射功率，0

低軌衛(wèi)星u到高軌衛(wèi)星的傳輸速率如式(2)所示：

Ru=(W/Q)bulb(1+γu)

(2)

對于所有存在子任務(wù)卸載到高軌衛(wèi)星的低軌衛(wèi)星u，帶寬資源分配策略B={bu}，bu∈{1,2,…,Q};所有子任務(wù)在低軌衛(wèi)星本地執(zhí)行時bu=0。

同樣，功率資源分配策略P={pu}，pu>0，所有子任務(wù)在低軌衛(wèi)星本地執(zhí)行時pu=0。

2.4 計算調(diào)度模型

高軌衛(wèi)星包含M個完全互聯(lián)的處理器，高軌衛(wèi)星處理器集合S={s1,s2,…,sM}，每個處理器sj的計算能力為fsj。低軌衛(wèi)星集合U={u1,u2,…,uN}，低軌衛(wèi)星處理器集合為S′={s′u|u∈U}，設(shè)fu為低軌衛(wèi)星u的本地計算能力，計算能力單位為cycles/s。

3 任務(wù)卸載與資源分配算法

衛(wèi)星邊緣計算卸載問題的目標(biāo)是為應(yīng)用中的子任務(wù)分配合適的處理器，以最小化系統(tǒng)開銷。系統(tǒng)開銷根據(jù)任務(wù)延遲和能耗來評估。本節(jié)首先對該問題進(jìn)行形式化，之后提出一種啟發(fā)式卸載算法來有效地進(jìn)行任務(wù)卸載決策和無線資源分配。

3.1 問題描述

為了在系統(tǒng)約束下降低任務(wù)平均執(zhí)行延遲和低軌衛(wèi)星總功耗，首先提出時延和能耗模型，將優(yōu)化問題形式化，設(shè)低軌衛(wèi)星u完成任務(wù)Vu的時延為tu，如式(3)所示:

tu=EFT(u,|Vu|),u∈U

(3)

EFT(u,k)的計算如式(4)所示：

(4)

EST(u,k,m)=max{ap(u,k,m),at(u,k,m)}

(5)

at(u,k,m)=

(6)

(7)

其中,Rm′,m表示2個處理器之間的通信速率，其計算如式(8)所示：

(8)

Tm′,m為路徑傳播時延，其計算如式(9)所示:

(9)

其中，Lm′,m為低軌衛(wèi)星和高軌衛(wèi)星的距離,c為光速。

式(3)是遞歸定義，遞歸退出條件如式(10)所示：

EST(u,1,m)=0，?m∈S∪S′,?u∈U

(10)

每一個任務(wù)的起始子任務(wù)最早開始時間都是0。

對于低軌衛(wèi)星u的能耗Eu，分別由本地計算功率Eu,c和傳輸發(fā)射功率Eu,t決定，如式(11)所示：

Eu=Eu,c+Eu,t

(11)

傳輸發(fā)射功率Eu,t的計算如式(12)所示：

Eu,t=pudu/Ru

(12)

其中,du為所有子任務(wù)前序在本地、后序在高軌衛(wèi)星的任務(wù)的數(shù)據(jù)的和，也即需要從低軌衛(wèi)星發(fā)送到高軌衛(wèi)星的數(shù)據(jù)量的總和，如式(13)所示：

(13)

Eu,c和低軌衛(wèi)星本地執(zhí)行任務(wù)有關(guān)，是本地執(zhí)行任務(wù)的總功耗，設(shè)低軌衛(wèi)星u本地執(zhí)行任務(wù)單位時間內(nèi)的能耗為εuJ/s,則Eu,c的計算如式(14)所示：

(14)

綜合時延和能耗，將低軌衛(wèi)星u的開銷定義如式(15)所示：

Cu=αutu+βuEu

(15)

其中，αu和βu分別為時延代價和能耗代價在系統(tǒng)開銷中的權(quán)重，αu,βu∈[0,1]，αu+βu=1，?u∈U。通過卸載決策實(shí)現(xiàn)無線資源和計算資源的聯(lián)合優(yōu)化分配，從而降低低軌衛(wèi)星系統(tǒng)整體的卸載開銷。

將系統(tǒng)開銷定義為所有低軌衛(wèi)星的卸載開銷的加權(quán)和，如式(16)所示：

(16)

其中，λu為每個低軌衛(wèi)星的權(quán)重。將聯(lián)合任務(wù)卸載和資源分配問題描述為系統(tǒng)開銷最小化問題，如式(17)～式(22)所示：

(17)

(18)

(19)

(20)

(21)

0

(22)

其中，Uoffload為存在子任務(wù)卸載到高軌衛(wèi)星的低軌衛(wèi)星集合，式(18)和式(19)是處理器分配約束，表示每個子任務(wù)可以本地執(zhí)行或者卸載到高軌衛(wèi)星某個處理器上執(zhí)行；式(20)是子任務(wù)依賴約束，表示子任務(wù)的調(diào)度必須滿足子任務(wù)依賴關(guān)系；式(21)是無線資源分配約束，即分配的總帶寬不能超過系統(tǒng)總帶寬；式(22)是功率約束，每個低軌衛(wèi)星的發(fā)射功率不能超過其功率限制。

3.2 任務(wù)卸載與資源分配聯(lián)合優(yōu)化算法

由于式(17)的聯(lián)合優(yōu)化問題是一個混合整數(shù)非線性規(guī)劃問題，求解最優(yōu)解需要指數(shù)級的時間復(fù)雜度。隨著低軌衛(wèi)星及其子任務(wù)數(shù)量的增加，難以在有限的時間內(nèi)給出最優(yōu)解。本文針對衛(wèi)星網(wǎng)絡(luò)環(huán)境，提出了一種基于動態(tài)優(yōu)先級的任務(wù)卸載與資源分配聯(lián)合優(yōu)化算法，該算法能夠適應(yīng)任務(wù)執(zhí)行環(huán)境中的動態(tài)資源分配。解決式(17)的問題分為以下幾步：

(1)按照子任務(wù)依賴關(guān)系對子任務(wù)進(jìn)行排序；

(2)根據(jù)系統(tǒng)參數(shù)給出初始的卸載策略；

(3)在初始卸載策略下進(jìn)行帶寬資源和功率資源分配；

(4)在資源分配策略下重新給出卸載策略；

(5)新的卸載策略不能帶來優(yōu)勢時算法退出。

(23)

本試驗采用隨機(jī)排列，不設(shè)重復(fù)。①九麥2號4.6畝；②中麥895 1.55畝；③小偃22（CK）1.55畝；④秦農(nóng)578 0.72畝；⑤西農(nóng)223 1.65畝；⑥陜農(nóng)33 1.8畝；⑦武農(nóng)6號1.44畝；⑧凳峰168 1.2畝；合計占地14.5畝。（田間排列設(shè)置見附表1）。

為了綜合考慮功耗和時延開銷，定義子任務(wù)的優(yōu)先級如式(24)所示：

(24)

首先低軌衛(wèi)星內(nèi)部根據(jù)子任務(wù)rank(u,k)的值進(jìn)行優(yōu)先級排序，得到當(dāng)前資源分配下優(yōu)先級最高的未調(diào)度的子任務(wù)。在各個低軌衛(wèi)星之間選擇priority(u,k)最大的低軌衛(wèi)星進(jìn)行卸載調(diào)度，選擇時延最小的處理器進(jìn)行卸載，得到任務(wù)卸載決策X和處理器調(diào)度策略Z。

在給定任務(wù)卸載決策X和處理器調(diào)度策略Z的情況下，為降低時延和功耗，設(shè)定目標(biāo)函數(shù)如式(25)所示:

(25)

其中,P和B為無線資源分配策略，t′u為低軌衛(wèi)星u中需要發(fā)送數(shù)據(jù)到高軌衛(wèi)星的數(shù)據(jù)傳輸時延。無線資源分配包括上行功率分配和子帶個數(shù)分配，以式(25)作為目標(biāo)函數(shù)，滿足約束的無線資源分配問題可以表述為式(26)：

s.t. 0

(26)

通過拉格朗日乘子法，可得出關(guān)于bu和pu的非線性方程組，每個低軌衛(wèi)星分配的子帶個數(shù)滿足式(26)約束，用式(27)確定bu的值：

(27)

由于每個低軌衛(wèi)星傳輸功率互相獨(dú)立，bu確定后利用二分法可求出pu的值。

至此，給出了算法運(yùn)行需要的全部定義和參數(shù)，并給出了進(jìn)行資源分配和調(diào)度決策的啟發(fā)式規(guī)則。算法1為任務(wù)卸載算法。首先,使用式(23)對所有子任務(wù)進(jìn)行排序;然后，對于每一個低軌衛(wèi)星上的任務(wù)，選擇排名最高的未調(diào)度子任務(wù)，形成候選調(diào)度集;接著，使用式(24)在候選調(diào)度集中搜索具有最高優(yōu)先級的子任務(wù)；再選擇處理該子任務(wù)時延最小的處理器作為該子任務(wù)的卸載目標(biāo)處理器。重復(fù)該過程，直到所有子任務(wù)都被調(diào)度。

算法1任務(wù)卸載與資源分配聯(lián)合優(yōu)化算法

輸入:Vu，Eu，S,S′，Pu，W,Q。

輸出:卸載決策X、調(diào)度策略Z、資源分配策略P、B。

iter=1，C=Inf;

whileTrue

ifiter=1

對?u∈U，?k∈Vu,B={bu}，bu=W/(Q×N)，P={pu},pu=Pu;

else

根據(jù)X通過解決式(26)重新分配資源得到B和P；

endif

根據(jù)式(23)計算rank(u,k)；

對?u∈U,?k∈Vu，選擇排名最高的未調(diào)度子任務(wù)，形成候選子任務(wù)集；

根據(jù)式(24)計算候選子任務(wù)的優(yōu)先級；

選擇優(yōu)先級最高的子任務(wù)，選擇處理該子任務(wù)時延最小的處理器作為該子任務(wù)的卸載目標(biāo)處理器，直至所有子任務(wù)均已調(diào)度，得到卸載決策Xnew和處理器調(diào)度策略Znew;

根據(jù)Xnew，Znew和式(16)計算系統(tǒng)開銷Cnew;

ifCnew

C=Cnew;X=Xnew;

P=Pnew;B=Bnew;

iter=iter+1;

else

break;

endif

endwhile

returnX、Z、P、B;

4 仿真結(jié)果分析

本文對算法的性能進(jìn)行仿真驗證。首先介紹仿真場景和仿真參數(shù)的設(shè)置,然后在此基礎(chǔ)上，將所提出的算法與當(dāng)前其它算法的性能進(jìn)行了比較。

4.1 參數(shù)設(shè)置

基于Walker星座進(jìn)行了仿真，該星座包括32個軌道面，每個軌道面內(nèi)有50顆衛(wèi)星，軌道高度為1 100 km，共有1 600顆低軌衛(wèi)星，高軌衛(wèi)星位于地球同步軌道，每顆低軌衛(wèi)星同時只能接入一顆高軌衛(wèi)星。每個低軌衛(wèi)星的任務(wù)被劃分為10個子任務(wù)，子任務(wù)依賴關(guān)系與文獻(xiàn)[16]的一致。具體仿真參數(shù)如表1所示。

Table 1 Simulation parameters

4.2 仿真分析

基于4.1節(jié)參數(shù)設(shè)置，通過500次蒙特卡洛仿真對提出的卸載決策算法性能進(jìn)行評估。仿真在處理器為AMD Ryzen 7 PRO 4750U，內(nèi)存為32.0 GB，操作系統(tǒng)為Windows 7的計算機(jī)上進(jìn)行，仿真中的任務(wù)數(shù)據(jù)量和任務(wù)計算量均是以上述數(shù)據(jù)為均值隨機(jī)產(chǎn)生的。

低軌衛(wèi)星和高軌衛(wèi)星之間的通信帶寬設(shè)置如表1所示，高軌衛(wèi)星處理器之間通過高速有線通道相互連接。任務(wù)數(shù)據(jù)量、任務(wù)計算量、高軌衛(wèi)星處理器的數(shù)量和低軌衛(wèi)星的數(shù)量都對任務(wù)卸載的性能有顯著影響。因此，本文主要評估這幾項因素的影響，評估指標(biāo)為系統(tǒng)時延和能耗。

首先分析高軌衛(wèi)星處理器數(shù)量的影響。將低軌衛(wèi)星的數(shù)量設(shè)置為30顆，圖2為不同子任務(wù)待處理數(shù)據(jù)量下任務(wù)平均完成時間和高軌衛(wèi)星處理器個數(shù)的關(guān)系，圖3分別為不同子任務(wù)待處理數(shù)據(jù)量下系統(tǒng)功耗和高軌衛(wèi)星處理器個數(shù)的關(guān)系。圖4為不同任務(wù)計算量下任務(wù)平均完成時間和高軌衛(wèi)星處理器個數(shù)的關(guān)系，圖5為不同任務(wù)計算量下系統(tǒng)功耗和高軌衛(wèi)星處理器個數(shù)的關(guān)系。從圖中可見，低軌衛(wèi)星任務(wù)完成的平均時間和總功耗都隨著高軌衛(wèi)星處理器個數(shù)的增加而降低；同時在高軌衛(wèi)星處理器個數(shù)不變的情況下，任務(wù)數(shù)據(jù)量和任務(wù)計算量的降低都會導(dǎo)致系統(tǒng)時延和能耗的降低。這表明，高軌衛(wèi)星處理器個數(shù)的增加為低軌衛(wèi)星提供了更多的處理器選擇，使子任務(wù)可以具有更高的并行度，因此可以降低系統(tǒng)總體開銷。

Figure 2 Average latency versus number of processors under different amount of task data圖2 不同任務(wù)數(shù)據(jù)量下處理器數(shù)量和平均延遲的關(guān)系

Figure 3 Energy consumption versus number of processors under different amount of task data圖3 不同任務(wù)數(shù)據(jù)量下處理器數(shù)量和總能耗的關(guān)系

Figure 4 Average latency versus number of processors under different amount of task workload圖4 不同任務(wù)計算量下處理器數(shù)量和平均延遲的關(guān)系

Figure 5 Energy consumption versus number of processors under different amount of task workload圖5 不同任務(wù)計算量下處理器下數(shù)量和總能耗的關(guān)系

在高軌衛(wèi)星處理器個數(shù)為16，待處理數(shù)據(jù)量為40 Mbits，子任務(wù)平均計算量為8 Gcycles的情況下，圖6給出了低軌衛(wèi)星數(shù)量和系統(tǒng)平均延遲的關(guān)系，圖7給出了低軌衛(wèi)星數(shù)和系統(tǒng)總功耗的關(guān)系。圖6和圖7同時還給出了與文獻(xiàn)[16]中提出的DEFO(Distributed Earliest Finish-time Offloading)算法以及和不卸載時系統(tǒng)性能的比較結(jié)果。可以發(fā)現(xiàn)，隨著低軌衛(wèi)星數(shù)目的增加，各個策略的時延和功耗都有增加；與不卸載相比，DEFO算法和本文算法都可以明顯降低系統(tǒng)的平均執(zhí)行時間。同時，在各個低軌衛(wèi)星數(shù)量條件下，與DEFO算法相比，本文算法無論是在降低時延還是系統(tǒng)能耗方面都更具優(yōu)勢，時延平均降低了14.6%，能耗降低了54.1%，說明本文聯(lián)合考慮無線資源分配的卸載算法可以更有效地提高系統(tǒng)整體效能。

Figure 6 Relationship between number of LEO satellites and average latency圖6 低軌衛(wèi)星數(shù)和系統(tǒng)平均延遲的關(guān)系

Figure 7 Relationship between number of LEO satellites and energy consumption圖7 低軌衛(wèi)星數(shù)和系統(tǒng)總功耗的關(guān)系

5 結(jié)束語

本文研究了高低軌協(xié)同計算的衛(wèi)星邊緣計算網(wǎng)絡(luò)中的卸載決策問題，對存在子任務(wù)依賴的任務(wù)延遲和能耗聯(lián)合優(yōu)化的卸載問題進(jìn)行了建模，提出了一種基于動態(tài)優(yōu)先級的子任務(wù)卸載算法。該算法在保證任務(wù)依賴關(guān)系的同時，將能源消耗和時延引入優(yōu)先級定義中，能根據(jù)具體的子任務(wù)分配無線和計算資源，使優(yōu)先級排序在任務(wù)卸載決策階段更加有效。仿真結(jié)果表明，與現(xiàn)有工作相比，本文算法可以減少衛(wèi)星邊緣網(wǎng)絡(luò)中的任務(wù)延遲和能耗，有利于實(shí)現(xiàn)衛(wèi)星計算和無線資源的高效利用。