李曉青 賀占權 周衛彤
1(航天恒星科技有限公司 北京 100095) 2(北京航空航天大學電子信息工程學院 北京 100191)
移動通信技術已經發展到第五代(5G)，5G網絡的主要工作頻段為3 000～5 000 MHz，遠遠高于4G網絡，這導致5G信號在信道中傳播的衰減要更高。5G基站的覆蓋半徑僅為100～300 m左右，這為實現偏遠地區用戶以及海空中用戶的組網覆蓋提出了嚴重挑戰[1]。近年來以小型化、低成本、低延遲和高吞吐量為特點的LEO衛星極大地促進了天地一體化網絡(ISTN)的發展[2]，ISTN已成為5G時代移動通信系統中一個必不可少的替代方案[3]。
考慮到5G時代偏遠地區及海、空用戶節點的組網需求，無法直接通過布置地面基站來完成全域覆蓋，這使得ISTN朝著衛星可直連用戶的方向發展；
此外，用戶設備(User Equipment, UE)側流量急劇增長，而由于自身資源有限，UE在處理計算密集型和時間敏感型業務時能力不足的情況。為此，移動邊緣計算(MEC)技術應運而生，相比于傳統移動云計算(Mobile Cloud Computing，MCC)技術，MEC技術可以在更靠近UE側配置，顯著減少云端處理任務的時延。相比于傳統蜂窩網絡架構，ISTN架構的傳播時延顯著增加，天地鏈路變化頻繁。隨著服務的增多導致大量數據通過鏈路進行傳輸，大大增加了鏈路負載，給ISTN的網絡架構設計帶來嚴重挑戰。使用MEC技術[4]，將計算資源從云端分配至邊緣服務器，能夠極大地改善對用戶的QoS，并且可以有效減少整個ISTN的流量。
在基于MEC的網絡架構中，資源優化分配策略是研究熱點。文獻[5]考慮將多個獨立用戶的任務卸載到一個基站的蜂窩網絡場景下，抽象為以時延和能量消耗最小化為目標的混合整數非線性優化(Mixed-Integer Nonlinear Programming, MINLP)問題，并設計了次優的算法來獲得最優資源分配方案。文獻[6]將擁有多個基站蜂窩網絡劃分為不同子區域，通過將多個獨立計算任務卸載到MEC服務器或云端，對基站服務緩存和任務卸載進行聯合決策以優化時延和能量消耗，基于Lyapunov優化和Gibbs采樣對優化問題進行求解，提出一種次優的服務存儲策略和任務卸載方案。文獻[7]探討ISTN場景下應用MEC技術來改善用戶QoS的可行性，提出在近UE側地面站和遠端核心網地面網關布置MEC服務器，并提出一種協作計算卸載(Cooperative Computation Offloading, CCO)模型來實現天地一體化網絡中多MEC服務器并行計算。文獻[8]提出了一種在LEO衛星與近UE側地面站布置MEC服務器的雙邊緣天地一體化網絡，并提出基于雙邊緣ISTN中的協作分流方案，通過分析得出分流效率和能耗的性能。
上述文獻普遍基于在擁有存儲和計算能力的固定基站中配置MEC服務器，為UE緩存熱點服務，并將用戶的計算任務卸載至MEC服務器，將場景抽象成以服務緩存和任務卸載為決策，以最小化時延和能量消耗為目標的優化問題，并提出最優或次優的服務存儲策略和任務分流方案。
本文考慮一種在LEO衛星上配置MEC服務器，直接與地面用戶建立天地鏈路的ISTN架構，為地面基站無法覆蓋到的區域提供MEC服務，大幅度提高偏遠地區用戶的QoS。基于串聯排隊理論得出ISTN場景的總時延成本，通過拉格朗日對偶理論和梯度下降法給出了ISTN網絡的總傳輸時延成本的極小值，并基于模擬退火算法，提出任務卸載和資源分配聯合調度方案，在多項式時間內給出近似全局最優的ISTN的時延成本。仿真結果表明本文算法相比于低復雜度啟發式算法減少了20%的總時延成本，驗證了ISTN下通過MEC技術保障地面用戶QoS的可行性和有效性。
典型的ISTN包含地面網絡與空間網絡，具有規模龐大、支持的業務種類多、拓撲結構呈現立體多層次化和高動態變化的特點。
1.1 網絡模型
本文考慮如圖1所示的LEO衛星-UE雙層天地一體化網絡模型，將MEC服務器部署在LEO衛星上，為UE提供任務卸載服務。每個時隙內由MEC服務器決策是否為UE提供MEC服務以及LEO衛星為UE分配的帶寬資源。
圖1 ISTN架構
定義LEO衛星提供的通信能力為衛星提供的鏈路總帶寬W(單位為Hz)；
提供的計算能力為MEC服務器中CPU的主頻F(單位為Hz)，MEC服務器的CPU可以處理用戶卸載至LEO衛星的任務。
對于UE側，定義UE集合為U={u1,u2,…,ui}，UEui配置主頻為fi的CPU以本地處理計算任務；
ui產生的計算任務請求的CPU指令周期個數服從均值為ci(單位為CPU cycles)的負指數分布；
計算任務的平均大小為di(單位為bits)。在時隙內ui上計算任務的產生是一個速率為λi的泊淞過程，在實際應用中，可以通過基于自回歸模型等成熟的需求預測模型來估計時隙開始時的瞬時需求[10]，使MEC服務器可以根據UE端設備的需求，為UE動態提供MEC服務。
傳統的ISTN網絡架構下進行任務卸載時，衛星通過用戶鏈路、饋電鏈路為UE提供與遠端核心網的鏈接，時延較長。本文設計的ISTN網絡架構下，星上MEC服務器直接通過用戶鏈路為用戶提供MEC服務，無須通過饋電鏈路。在此架構上初步探究ISTN網絡針對偏遠地區用戶及海空中用戶的計算密集型任務的服務能力。
1.2 任務卸載和資源分配模型
假設每個UE的等效全向輻射功率(Equivalent Isotropically Radiated Power，EIRP)相同，LEO衛星采用正交頻分復用(Frequency Division Multiple Access，FDMA)的接入方式，當不同用戶共享頻譜資源時不存在相互干擾。
MEC服務器進行任務卸載的決策有本地執行、完全卸載和部分卸載三種方案。本地執行即整個計算任務在UE本地完成；
完全卸載即整個計算任務由MEC卸載和處理；
為了簡化分析，我們不考慮部分卸載的情況。則可定義一個二元決策變量ai={0,1}表示LEO衛星上的MEC服務器是否為UEui提供MEC服務。其中ai=1表示MEC服務器為ui提供MEC服務；
ai=0表示ui在本地處理計算任務，則時隙內任務卸載決策是A={a1,a2,…,ai}。
整個LEO衛星可提供的總帶寬為W，單位為bit/s,定義時隙內LEO衛星帶寬資源分配決策B={b1,b2,…,bi}，其中bi=[0,1]，表示MEC服務器為ui分配的帶寬占總帶寬比例。因為本地計算的UE不占用頻帶資源，若ai=0，則bi=0，則用戶鏈路通信速率Ri有:
Ri=biW
(1)
由于采用FDMA多址接入技術，所有UE分配的頻譜資源不超過衛星的總通量，則ISTN的頻帶資源約束表示為:
(2)
1.3 時延模型
計算卸載的性能通常以時間延遲和能量消耗作為衡量指標。在ISTN場景下，我們主要關注MEC服務器在減小業務時延上的能力。ISTN下UE 產生的計算任務可以在本地執行或完全卸載，在本地執行時，時延成本是指在UE處執行本地計算所花費的時間，在完全卸載時，時延包括傳輸時延、傳播時延、排隊時延和計算時延。
(3)
為了分析ISTN網絡下計算任務完全卸載的時延成本，根據分組交換網絡思想，可將整個網絡建模成如圖2所示的串聯排隊系統。
圖2 串聯排隊系統
圖2中隊列集Q={Qi|?ai≠0}是獨立的M/D/1/FCFS隊列，Qi表示卸載UE產生計算任務并上傳LEO衛星的過程，Q是一個M/G/1/FCFS隊列，表示MEC服務器處理計算任務的過程。隊列Qi的服務時間ti為用戶ui產生的計算任務的傳輸時延：
(4)
根據排隊論的Pollaczek-Khinchin公式和Little定理任務有隊列Qi的平均停留時間期望Ti為:
(5)
此時隊列遵循穩態約束條件:
(6)
(7)
(8)
根據Pollaczek-Khinchin公式和Little定理有隊列Q*的平均停留時間期望Ts為:
(9)
其中隊列遵循穩態約束條件:
(10)
實際上，Pollaczek-Khinchin公式的穩態約束條件可理解為計算資源約束。由此，我們定義計算任務卸載至MEC服務器處理的時延成本為:
(11)
式中：Tsi(bi)是ui與LEO衛星的鏈路傳輸時延;Ts(A)是計算在LEO衛星上的平均停留時間;tc表示UE與LEO衛星之間的鏈路傳播時延，由于我們忽略不同UE與LEO的距離變化，因此對于每個UE，tc是常數。
為了分析ISTN下用戶QoS保障的問題，定義ISTN的總時延成本為:
(12)
其表示ISTN網絡場景下MEC服務器減小UE時延成本的能力。
1.4 優化問題模型
優化問題的目標是制定任務卸載決策A和帶寬資源分配決策B，以最大限度地減少總時延成本T(A,B)。優化問題P1的模型為:
(13)
(14)
(15)
(16)
式(14)是計算任務上傳隊列穩定約束條件，代表LEO衛星在每個時隙內為UE分配的帶寬應使計算任務上傳隊列穩定；
式(15)是ISTN的帶寬資源約束條件；
式(16)是MEC服務器的M/G/1隊列穩態約束，也可將其理解為MEC服務器的計算資源上限。
可以很容易地注意到，P1是一個MINLP問題，且優化函數非凸，這使得P1非常難以求解；
另一方面，對于整數規劃問題，通過窮舉法得出最優的任務卸載決策A的時間復雜度為O(2N)，這是一個指數級復雜度，并且對于每個卸載決策，都需要確定最佳的帶寬分配。
由于算法的復雜性較高，在實際應用中是不可行的。
本文基于模擬退火算法和梯度下降法提出一種天地一體化網絡任務卸載和資源分配(Satellite-Terrestrial Task Offloading and Resource Allocation，ST-TORA)方案。對于如何求解P1，首先考慮將A和B解耦，選定部分UE進行任務卸載，確定卸載決策向量A，將原問題松弛并根據拉格朗日法求解，得到帶寬配置方案B和天地一體化網絡總時延開銷T(A,B)。然后基于模擬退火算法迭代更新決策變量A直到找到P1的局部最優解，將算法的時間復雜度降為多項式時間。
2.1 資源分配(RA)方案
當MEC服務器為多個UE提供MEC服務時，如何有效地將LEO衛星有限的帶寬資源分配給卸載UE是本節要解決的問題。取ki=λidi/Φ，Ki=di/2Φ，隊列Qi的平均服務時間為：
(17)
式中：ki代表了傳輸隊列Qi穩定所需要分配最小帶寬資源比例，當bi (18) s.t.bi>ki,?bi≠0 (19) (20) 定理問題P2在滿足約束條件下是一個凸優化問題。 證明式(19)的Hessian矩陣為： (21) 其中： (22) (23) 根據次梯度法得到拉格朗日乘子的迭代公式為: [εi(n)-m(bi-ki)]+ (24) (25) 式中：[x]+=max{0,x}； (26) 通過梯度下降法求解帶寬分配的迭代公式為: (27) 當迭代步長小于最小迭代步長δ時迭代停止。因此當確定任務卸載決策A時，資源分配(Resource Allocation，RA)算法描述如算法1所示。 算法1RA 算法 輸入：A,ki,Ki,I,W,F,tc。 輸出：B,T。 初始化m,n,δ,,εi(0),μ(0),bi(0)； n=n+1; endwhile 計算T(A,B)； returnB,T 在任務卸載場景下，不同的UE業務有著不同的計算任務大小，RA算法可以為計算任務更大的UE分配更多的帶寬資源，最小化網絡場景下的傳輸時延成本。 任務卸載決策A的求解是一個整數規劃問題，由窮舉法尋找A的最優解的時間復雜度為O(2N)，為指數級復雜度。可以預見，MEC服務器應優先為業務數據量更大、請求計算資源更多、計算資源更少的UE提供MEC服務，這意味著最優解附近的解也相對較優，適用于整數規劃中的模擬退火算法。本文基于模擬退火算法，在多項式時間內尋找問題P1的近似全局最優值。 首先確定一個滿足約束條件的初始任務卸載決策A，并通過RA算法得到B和T。之后對任務卸載決策向量A進行N*次如算法2所示的隨機擾動得到Anew，通過RA算法得到Bnew和Tnew。其中N*為鄰域解空間大小。 算法2disturb 算法 輸入：A,I,W,F。 輸出：Anew。 隨機選取擾動UEi； chosen=rand； ifchosen≤0.6 ai=1； else ifchosen≤0.85 ||A中所有元素相等 隨機選取與UEi卸載決策不同的UEj； ai=1-ai,aj=1-aj； else ai=0； returnAnew 令Δ=Tnew-T。若Δ<0則接受該結果； 算法3ST-TORA 算法 輸入：ci,di,λi,fi,I,W,F,tc。 輸出：A,B,T。 [B,T]=RA(A,ki,Ki,I,W,F,tc)； Whileτ>τmin fori=1:N*； Anew=disturb(A,W,F)； [Bnew,Tnew]=RA(Anew,ki,Ki,I,W,F,tc)； Δ=Tnew-T,P=exp(Δ/τ)； ifΔ<0‖P>rand A=Anew； B=Bnew； T=Tnew； end if end for τ=ατ； end while returnA,B,T ST-TORA算法的時間復雜度取決于鄰域解空間個數大小以及溫度下降率，對于N位向量A，取N*=τ=N，ST-TORA算法的時間復雜度為O(NlogN)[12]。相比于窮舉法，ST-TORA算法可在多項式時間內趨于全局最優。 在本節中，通過仿真對本文提出的ST-TORA算法進行驗證，仿真結果表明了應用于天地一體化網絡場景，在LEO衛星上部署MEC服務器，為UE提供邊緣計算服務，以保障網絡QoS的可行性及有效性。 考慮由單個LEO衛星和UE構成的天地一體化網絡場景，通過在LEO衛星部署MEC服務器為UE提供邊緣計算服務。其中每個UE的計算任務數據平均大小di，所需CPU轉數ci，UE端CPU計算能力fi以及任務產生速率λi均隨機生成，其中任務平均大小di與所需CPU轉數ci呈線性相關。其中仿真平臺配置為：Intel(R) Core(TM)i5- 4210H CPU @2.90 GHz； 表1 ISTN場景仿真參數 3.2.1資源分配(RA)算法 圖3所示為相同任務卸載決策下，本文基于梯度下降法設計的RA方案與帶寬資源平均分配(Equal Bandwidth，EB)方案下，LEO衛星提供邊緣計算的時延成本T與卸載用戶數量的關系，其中LEO衛星總通量W為1 Gbit/s，MEC服務器的CPU主頻F為10 GHz。 圖3 卸載時延與卸載UE數量關系 可以看出，隨著卸載UE數量的增多，RA算法按業務需求量分配帶寬的優勢更加明顯。當任務卸載決策確定時，計算任務在MEC服務器的總停留時間的期望Ts(A)確定，RA算法可動態地為業務需求高的UE分配更高的帶寬資源，避免帶寬資源浪費并最小化總時延成本。 圖4給出了LEO衛星總通量W為1 Gbit/s，MEC服務器的CPU主頻F為10 GHz的場景下，RA算法的平均帶寬利用率與卸載UE數量的關系。平均帶寬利用率定義為五十次仿真下帶寬分配向量B中各元素之和的平均值。 圖4 平均帶寬利用率與卸載UE數量關系 RA算法的性能由每次迭代的步長m以及拉格朗日乘子εi和μ的初值決定，若步長m過大則可能越過極值點，m過小則算法收斂時間過慢； 3.2.2ST-TORA算法 圖5給出ST-TORA算法下3種總通量的LEO衛星進行任務卸載的時延成本與UE總數量的關系。MEC服務器的CPU主頻F設置為10 GHz。 圖5 不同總通量下時延成本與UE數量關系 可以看出天地一體化網絡場景下時延成本與衛星的總通量直接相關，這是因為衛星總通量的增長直接減少計算任務的傳輸時延，大大保障UE端的QoS。隨著UE數量的增長，每0.5 Gbit/s的通量增長可為UE側減少100 ms的傳輸時延。隨著衛星通信技術的不斷進步，超低軌道高通量衛星提供的總通量可高達100 Gbit/s級，傳輸時延可縮短至μs級； 圖6給出了ST-TORA算法下3種計算能力的MEC服務器進行任務卸載的UE卸載比例與UE總數量的關系。LEO衛星提供的總通量W設置為1 Gbit/s。 可以看出，卸載UE比例是MEC計算能力的一個遞增函數。由于計算資源約束條件的存在，MEC服務器的CPU主頻越高，計算任務在MEC服務器的總停留時間越短，MEC服務器可為更多的UE提供服務。當UE總數量較少時，天地一體化網絡中LEO衛星可以提供足夠的計算資源和帶寬資源時，所有UE可以將計算任務上傳至MEC服務器； 圖7 不同算法下時延成本與UE數量關系 表2 不同算法收斂時間對比 單位：s 由圖7可以看出，由于為過多的UE提供了MEC計算服務，LEO衛星為每個用戶分配的帶寬資源只能勉強維持傳輸隊列穩定，因此本地成本優先式算法的性能最差。隨著UE數量的增多，相比于低復雜度的Heuristic 算法的時延成本，本文所提ST-TORA 算法的時延成本可降低約20%。兩種算法同樣基于啟發式算法，但基于模擬退火思想的ST-TORA算法可以跳出局部最優解達到全局最優解。但由表2可以看出ST-TORA算法的收斂時間要高于Heuristic算法，這是因為模擬退火算法的時間復雜度受溫度下降率以及溫度下界的直接影響，在本文仿真場景參數下，為了保證算法在減小時延成本方面的優越性，ST-TORA算法的時間復雜度高于Heuristic算法。 本文研究支持MEC 的天地一體化網絡場景下任務卸載和資源分配聯合優化方案。首先建立了LEO衛星(邊緣網絡)-UE的雙層ISTN模型；
n表示迭代次數；
m表示迭代步長，應取足夠小的正數。令：2.2 任務卸載決策
否則將有概率接受這個結果，概率計算公式為P=exp(Δ/τ),其中τ為當前溫度，初始值設置為用戶總數量。更新τnew=ατ，其中α為溫度下降率。然后重新開始迭代，直到溫度τ到達溫度下界τmin，其中τmin設為一個足夠小的正數。基于此，本文提出ST-TORA算法如算法3所示。
3.1 仿真場景及參數設置
8 GB RAM；
硬盤1 TB；
Windows 10 Education 64位。在MATLAB 2020a環境下進行仿真，仿真參數如表1所示。
3.2 仿真結果及分析
而拉格朗日乘子會隨著迭代次數的增加而逐漸收斂。由圖4可以看出，在帶寬利用率保持在0.95以上的同時，RA算法可以很好地逼近目標函數的極小值。
而相同通量下，LEO衛星可提供的覆蓋性遠高于地面基站。
隨著UE數量的增多，由于MEC服務器的計算資源和LEO衛星提供的帶寬資源有限，相同UE總數量下卸載UE個數會趨于一個穩定值。
然后通過排隊論與分組交換網絡的思想對模型的時延成本進行考察，并最終將降低時延成本的過程抽象為一個MINLP問題，本文將其轉為2個子問題進行求解：(1) 為最小化計算任務卸載至部署了MEC服務器的LEO衛星的傳輸時延成本，基于拉格朗日乘數法和梯度下降法，為每個UE分配最優的帶寬資源。(2) 基于模擬退火算法，降低整數優化的時間復雜度，尋找到逼近最優的聯合任務卸載和資源分配方案。仿真結果表明本文算法能夠更好地滿足天地一體化網絡下的需求，有效降低其時延成本。下一步的工作考慮引入核心網-LEO-UE三層模型的緩存網絡場景[14]，進一步優化天地一體化網絡下UE的QoS。