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

方 海,趙 揚,高 媛,楊 旭

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

1 引言

衛星是6G網絡的重要節點[1 - 4]，以星鏈為代表的衛星星座正在快速地發展[5]。在傳統的衛星任務處理模式中，數據傳輸到地面數據中心進行處理，隨著6G網絡中衛星業務的不斷擴展和豐富，海量數據將導致更長的數據傳輸時間和更大的帶寬壓力。

邊緣計算的出現為用戶利用網絡邊緣節點的計算能力進行數據處理提供了新的模式[6]。在邊緣計算模式下，將分散在每顆衛星上的計算資源整合到同一架構中，實現分散衛星計算能力的融合，為衛星處理海量數據任務和時敏任務提供了統一的在軌邊緣計算能力，能夠更充分利用在軌計算資源，節省海量數據傳輸帶寬，提高實時數據分析能力，實現衛星資源的高效利用。任務卸載是邊緣計算中的關鍵技術之一，即何時將何任務卸載到哪個邊緣處理器，任務卸載決策算法是系統高效運行的關鍵。

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

隨著衛星技術的發展，多處理器系統已實現星載應用。與現有工作不同，本文考慮星載多處理器系統環境，提出了一種聯合無線資源分配同時考慮子任務依賴關系的卸載決策調度算法，且基于啟發式搜索算法，在保證任務依賴性的同時能夠降低任務延遲和能量消耗。

2 系統模型

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

2.1 衛星邊緣計算架構

高低軌協同的衛星邊緣計算網絡體系結構如圖1所示。低軌道衛星群位于衛星網絡邊緣計算層的網絡邊緣。該層衛星節點較多，搭載的嵌入式計算設備算力有限，但可以為空間或地面用戶提供高可靠性、低延遲的邊緣處理能力。高軌衛星通信覆蓋范圍廣，可以實現對低軌衛星群的全覆蓋，高軌衛星計算和帶寬資源充足，適合處理計算量大的復雜任務，同時可以負責衛星邊緣計算網絡資源的管理。低軌衛星計算任務可以卸載到所接入的高軌衛星，也可以在本地計算。低軌衛星的計算任務可以是低軌衛星本身產生的，也可以是接入該衛星的陸海空天等終端產生的。

Figure 1 System structure of satellite edge computing圖1 衛星邊緣計算系統結構圖

2.2 任務模型

2.3 通信模型

在高低軌協同計算的衛星網絡中，低軌衛星子任務可以卸載到高軌衛星中的任一處理器執行或在本地執行。將低軌衛星u到高軌衛星的可用帶寬W分成Q個子帶，低軌衛星u的任務可以分配使用bu個子帶，0≤bu≤Q。僅考慮低軌衛星到高軌衛星鏈路的帶寬分配，高軌衛星內部處理器之間通過內部高速交換網絡全互聯，設高軌衛星內部處理器之間的傳輸速率為R。

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

(1)

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

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

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

(2)

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

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

2.4 計算調度模型

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

3 任務卸載與資源分配算法

衛星邊緣計算卸載問題的目標是為應用中的子任務分配合適的處理器，以最小化系統開銷。系統開銷根據任務延遲和能耗來評估。本節首先對該問題進行形式化，之后提出一種啟發式卸載算法來有效地進行任務卸載決策和無線資源分配。

3.1 問題描述

為了在系統約束下降低任務平均執行延遲和低軌衛星總功耗，首先提出時延和能耗模型，將優化問題形式化，設低軌衛星u完成任務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為低軌衛星和高軌衛星的距離,c為光速。

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

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

(10)

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

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

Eu=Eu,c+Eu,t

(11)

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

Eu,t=pudu/Ru

(12)

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

(13)

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

(14)

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

Cu=αutu+βuEu

(15)

其中，αu和βu分別為時延代價和能耗代價在系統開銷中的權重，αu,βu∈[0,1]，αu+βu=1，?u∈U。通過卸載決策實現無線資源和計算資源的聯合優化分配，從而降低低軌衛星系統整體的卸載開銷。

將系統開銷定義為所有低軌衛星的卸載開銷的加權和，如式(16)所示：

(16)

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

(17)

(18)

(19)

(20)

(21)

0

(22)

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

3.2 任務卸載與資源分配聯合優化算法

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

(1)按照子任務依賴關系對子任務進行排序；

(2)根據系統參數給出初始的卸載策略；

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

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

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

(23)

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

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

(24)

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

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

(25)

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

s.t. 0

(26)

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

(27)

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

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

算法1任務卸載與資源分配聯合優化算法

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

輸出:卸載決策X、調度策略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

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

endif

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

對?u∈U,?k∈Vu，選擇排名最高的未調度子任務，形成候選子任務集；

根據式(24)計算候選子任務的優先級；

選擇優先級最高的子任務，選擇處理該子任務時延最小的處理器作為該子任務的卸載目標處理器，直至所有子任務均已調度，得到卸載決策Xnew和處理器調度策略Znew;

根據Xnew，Znew和式(16)計算系統開銷Cnew;

ifCnew

C=Cnew;X=Xnew;

P=Pnew;B=Bnew;

iter=iter+1;

else

break;

endif

endwhile

returnX、Z、P、B;

4 仿真結果分析

本文對算法的性能進行仿真驗證。首先介紹仿真場景和仿真參數的設置,然后在此基礎上，將所提出的算法與當前其它算法的性能進行了比較。

4.1 參數設置

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

Table 1 Simulation parameters

4.2 仿真分析

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

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

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

Figure 2 Average latency versus number of processors under different amount of task data圖2 不同任務數據量下處理器數量和平均延遲的關系

Figure 3 Energy consumption versus number of processors under different amount of task data圖3 不同任務數據量下處理器數量和總能耗的關系

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

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

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

Figure 6 Relationship between number of LEO satellites and average latency圖6 低軌衛星數和系統平均延遲的關系

Figure 7 Relationship between number of LEO satellites and energy consumption圖7 低軌衛星數和系統總功耗的關系

5 結束語

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