宋政育，郝媛媛，孫昕

1 引言

近年來，為了滿足移動通信和物聯(lián)網的大計算量、低時延應用的需求，并降低移動終端的能耗，歐洲通信標準化委員會提出了多接入邊緣計算（Multi-Access Edge Computing，MEC）技術［1］. 在缺乏地面通信基礎設施的偏遠地區(qū)，可在低軌（Low Earth Orbit，LEO）衛(wèi)星中部署MEC 服務器，為偏遠地區(qū)的用戶提供高質量的邊緣計算服務［2］. 為了充分發(fā)揮MEC 技術在降低移動終端能耗和計算時延等方面的優(yōu)勢，必須采用高效的任務遷移以及通信和計算資源分配算法［3，4］. 現有的任務遷移及資源分配算法一般基于凸優(yōu)化理論設計，還有部分文獻采用啟發(fā)式算法. 文獻［5］設計了基于時分多址接入和正交頻分多址接入的兩種多用戶MEC 模型，在計算任務時延的約束下，基于凸優(yōu)化理論提出了使用戶能耗加權和最小的任務遷移和資源分配算法.文獻［6］則采用凸優(yōu)化方法設計了一種統(tǒng)計性的通信和計算資源分配算法，使移動設備和MEC 服務器的長期平均功率最小化. 文獻［7］研究了異構MEC網絡的能耗和時延的折中優(yōu)化問題. 當用戶數量或計算任務較多時，MEC 服務器容易發(fā)生過載現象. 為了解決該問題，可在系統(tǒng)中部署多個MEC 服務器，各MEC 服務器可進行邊緣計算協(xié)作. 文獻［8］基于遺傳算法和粒子群優(yōu)化方法，研究了密集部署的小蜂窩網絡MEC 服務器的選擇和通信資源分配問題，其中每個小蜂窩基站均可部署MEC 服務器并進行協(xié)作邊緣計算. 文獻［9］將小蜂窩基站的部分任務數據遷移至部署于宏蜂窩基站且計算能力更強的MEC 服務器，實現MEC 服務器間的協(xié)作邊緣計算. 上述文獻僅研究了地面通信網絡的邊緣計算問題，所提出的任務遷移和資源分配算法不適用于衛(wèi)星通信網絡.

目前，針對衛(wèi)星通信網絡邊緣計算的研究比較有限. 文獻［10］首次提出了星地一體化網絡的MEC 技術，由于LEO 衛(wèi)星與地面之間的信號傳播時延最低可達到1~4 ms，MEC 技術可用于星地一體化網絡. 文獻［11］提出了一種星地一體化的邊緣計算網絡架構，并分析了該網絡架構面臨的技術挑戰(zhàn). 文獻［12］研究了一種空天地一體化的邊緣計算系統(tǒng)，并提出了基于機器學習的最優(yōu)任務遷移策略. 上述衛(wèi)星邊緣計算的算法均未考慮衛(wèi)星間的協(xié)作問題.

本文通過LEO 衛(wèi)星通信網絡的星間鏈路［13］（Inter-Satellite Link，ISL）進行任務數據的二次遷移，實現相鄰衛(wèi)星間的邊緣計算協(xié)作. 以地面移動用戶的加權總能耗最小化為目標，在保證任務時延需求的條件下，提出一種基于ISL 的LEO 衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法. 仿真結果表明，該算法的收斂速度快；與本地計算和任務數據全部上傳算法相比，本文所提出的算法的用戶總能耗更低；與非協(xié)作邊緣計算相比，基于ISL 的LEO 衛(wèi)星協(xié)作邊緣計算可有效降低用戶能耗，且隨著ISL 的信道容量和MEC 服務器計算能力的增加，用戶的總能耗不斷降低.

2 系統(tǒng)模型與優(yōu)化問題

2.1 系統(tǒng)模型

設某LEO 衛(wèi)星協(xié)作邊緣計算系統(tǒng)有M個地面移動用戶、N個LEO 衛(wèi)星以及K個正交子載波. 在某LEO 衛(wèi)星的覆蓋范圍內，采用部分任務遷移機制，通過正交頻分多址接入同時將M個用戶的部分或全部任務數據遷移至衛(wèi)星MEC 服務器進行邊緣計算，移動用戶在本地對未被遷移至衛(wèi)星的任務數據進行計算.假定移動用戶的CPU 采用動態(tài)電壓和頻率調整技術［8］，則任意用戶m進行任務數據的本地計算所需的功率為：

其中：κ為一個與CPU 架構有關的常數；fm為用戶m的進行本地計算時的CPU時鐘頻率.

設用戶m計算任務的總數據量為ηm，用戶m向LEO 衛(wèi)星遷移的數據量為Sm，二者的單位均為比特，則用戶m進行本地計算所需的時間為：其中，β為計算每比特任務數據所需的CPU周期數.

用戶m進行本地計算所需的能量可表示為：

設ρmk為子載波分配指示變量，當子載波k分配給用戶m時，ρmk=1，否則ρmk=0，則：

當任務數據遷移時，用戶m在子載波k上的數據速率可表示為：

其中，pmk與hmk分別為用戶m在子載波k上的發(fā)射功率和信道增益；B0為子載波帶寬；σ2為加性高斯白噪聲的功率.

用戶m進行任務遷移的總數據速率為：

用戶m進行任務遷移所需的總功率為：

用戶m進行任務遷移所需的能量為：

其中：Ttx為各用戶任務數據遷移時的傳輸時間.

假定N個LEO 衛(wèi)星中任意兩個相鄰的衛(wèi)星間可通過ISL 進行邊緣計算協(xié)作. 設地面移動用戶接入衛(wèi)星n，當衛(wèi)星n的計算能力不足時，可將部分任務數據遷移至相鄰衛(wèi)星j的MEC 服務器進行協(xié)作計算. 設衛(wèi)星n通過ISL遷移至相鄰衛(wèi)星j的數據量為D，衛(wèi)星n和衛(wèi)星j的MEC 服務器計算時的CPU 時鐘頻率分別為fnEC和fjEC，則二者進行邊緣計算的時間分別為：

設ISL 的信道容量為C，則衛(wèi)星通過ISL 遷移任務數據所產生的時延為：

任務數據計算結果的數據量很小，用戶下載結果的時間可忽略. 由于星地之間距離較遠，不可忽略信號自由空間傳播時延. 假定LEO 衛(wèi)星n的高度為Hn，光速為c，則地面用戶與衛(wèi)星n之間的信號自由空間傳播時延可近似表示為：

LEO衛(wèi)星進行協(xié)作邊緣計算的總時延為：

2.2 優(yōu)化問題

本文對LEO 衛(wèi)星協(xié)作邊緣計算系統(tǒng)的任務遷移策略以及通信和計算資源分配進行優(yōu)化，其中通信資源包括各用戶的發(fā)射功率、用戶與衛(wèi)星間的子載波以及任務遷移的時間；計算資源指用戶進行本地計算時的CPU 時鐘頻率. 以所有用戶的加權總能耗最小化為目標，以任務的可容忍時延等為約束條件建立優(yōu)化問題，則該優(yōu)化問題可表示為：

其中，f=(fm），ρ=(ρmk)，p=(pmk)，s=(smk).fmmax和Pmmax分別為用戶m的CPU最大時鐘頻率和最大發(fā)射功率.T為計算任務可容忍的最大時延.wm為權重參數，用于表示用戶的優(yōu)先級. 約束條件C3和C4表示用戶進行本地計算和邊緣計算的時延均不能超過任務可容忍的最大時延.C7和C8表示系統(tǒng)中每個子載波最多可分配給一個用戶.

3 任務遷移和資源分配算法

3.1 ISL遷移的最優(yōu)數據量

為了設計LEO 衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法，需要確定相鄰衛(wèi)星間通過ISL 遷移的最優(yōu)數據量，可得優(yōu)化問題的相關定理.

定理1 優(yōu)化問題式(14)的目標函數為關于Ttx的單調遞減函數.

證明由式（5）可得：

將優(yōu)化問題式（14）的目標函數轉換為：

對目標函數E求關于Ttx的導數，可得：

為證明E為關于Ttx的單調遞減函數，需證明定義f(rmk) =則可 得. 對函數f(rmk)求關于rmk的導數，有因為rmk≥0，所以當rmk=0時，函數f(rmk)可達最大值，即f(0) =0；當rmk>0時，則f(rmk) ＜0. 若系統(tǒng)中至少一個子載波的數據速率rmk>0，則有因此，優(yōu)化問題式（14）的目標函數為關于Ttx的單調遞減函數. 對于rmk=0,?m,k的特殊情況，所有的任務數據均由用戶在本地進行計算，此時不需要進行任務遷移和資源分配算法的設計. 證畢.

由定理1可知，為了降低能耗，用戶將以可允許的最大時長遷移任務數據. 因為Ttx+Tsat≤T，所以當Tsat取得最小值時，用戶傳輸時長Ttx可達到最大，此時用戶的能耗最低.根據式（13），對于衛(wèi)星n時，max為常數，當取得最小值，即Tsat取得最小值.

由式（18）可得，衛(wèi)星間通過ISL遷移的最優(yōu)數據量為：

將D*代入式（13），可得Tsat的最小值，即：

3.2 任務遷移和資源分配算法設計

由優(yōu)化問題式（14）的約束條件C1和C3，可得：

優(yōu)化問題的目標函數為關于fm的單調遞增函數，由式（21）可得fm的最優(yōu)解，即：

為了保證優(yōu)化問題的可行性，由式（21）可得：

則由式（23）可得：

將式（20）和式（22）代入式（14）中，優(yōu)化問題式（14）轉換為：

優(yōu)化問題式（25）的目標函數為非凸的，不易對其直接求解，故將其分解為任務遷移子問題和無線資源分配子問題，通過迭代求解子問題，得到優(yōu)化問題式（25）的解.

若假定子載波分配變量ρ已知，將式（15）代入優(yōu)化問題式（25），則可得到任務遷移子問題為：

定理2任務遷移子問題式（26）為凸優(yōu)化問題.

證明任務遷移子問題式（26）的目標函數的第一項為關于矢量s的凸函數，第二項符合函數的結構. 由于函數為關于x和t的聯(lián)合凸函數，故優(yōu)化問題式（26）的目標函數為關于s和Ttx的聯(lián)合凸函數.定義函數，則約束條件C10 可等價于因為g(s,Ttx)與函數的結構一致，所以g(s,Ttx)為關于s和Ttx的聯(lián)合凸函數，即約束條件C10 為凸的. 優(yōu)化問題式（26）的其它約束條件均為線性的. 因此，任務遷移子問題式（26）的目標函數和可行集均為凸的，為凸優(yōu)化問題. 證畢.

任務遷移子問題式（26）為凸優(yōu)化問題，則可通過標準凸優(yōu)化算法（例如內點法等），得到其最優(yōu)解. 對于無線資源分配子問題式（27），由于存在整數優(yōu)化變量，難以直接獲得其最優(yōu)解，因此采用拉格朗日對偶分解方法求解.

松弛無線資源分配子問題式（27）的約束條件C2和C11，則其拉格朗日函數為：

其中，θ=(θm)和λ=(λm)分別為約束條件C2 和C11 的拉格朗日因子. 對偶函數為Q(θ,λ) =

由式（28）可知，對于確定的拉格朗日因子θ和λ，可將對偶函數Q(θ,λ)進一步分解為K個獨立的子問題，且每個子問題對應一個子載波. 對應于子載波k的子問題可表示為：

定義函數Gmk和Hmk，即：

則子載波分配的最優(yōu)解為：

由式（33）可得，用戶m在子載波k上的最優(yōu)功率分配為：

基于任務遷移子問題式（26）和無線資源分配子問題式（27）的求解過程，LEO 衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法歸納為算法1.

定理3描述了算法1的收斂性.

定理3 算法1 每次迭代均可降低目標函數E(ρ,p,s,Ttx)的值，并在有限次迭代內收斂.

當固定子載波分配變量ρ(l)時，算法1求子問題（26）的最優(yōu)解()，并更新功率分配為p(2l+1)，所以式（35）中的不等式(a)成立. 同樣地，當固定各用戶遷移的數據量時，算法1 可得到子問題式（27）的解(?m和傳輸時間)，所以式（35）中的不等式(b)成立. 不等式（35）表明，算法1的每次迭代均可降低目標函數E(ρ,p,s,Ttx)的值. 由于目標函數值是有下界的，故算法1將在有限次迭代內收斂. 證畢.

算法1迭代求解子問題式（26）和（27）直至收斂. 由于子問題式（26）為凸優(yōu)化問題，得到其最優(yōu)解的復雜度為多項式復雜度. 子問題式（27）采用拉格朗日對偶方法求解，其復雜度也為多項式復雜度. 根據定理3，算法1將在有限次迭代內收斂，因此算法1具有多項式復雜度.

4 仿真結果與分析

本節(jié)對LEO 衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法（算法1）的性能進行仿真與分析. 設置LEO 衛(wèi)星的飛行高度為1500 km，無線信道衰落包括自由空間路徑損耗和萊斯衰落，衛(wèi)星天線增益為43.3 dBi. 系統(tǒng)總帶寬為20 MHz，子載波數量K=128，用戶數量M=16，衛(wèi)星MEC 服務器的CPU 時鐘頻率為8 GHz，且κ=10-26，β=120 cycle/bit.

圖1 示出了本文提出的LEO 衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法的收斂性. 在每次迭代之后，用戶總能耗均降低，并在數次迭代后收斂. 對于不同的任務可容忍時延T，算法的收斂速度略有差別，但均可在約8次迭代內收斂. 因此，本文所提出的任務遷移和資源分配算法的收斂速度較快.

圖1 LEO衛(wèi)星協(xié)作邊緣計算任務遷移和資源分配算法的收斂性

圖2 示出了地面用戶總能耗與計算任務數據量ηm之間的關系，隨著計算任務數據量的增加，本文所提出的任務遷移和資源分配算法（算法1）、本地計算以及任務數據全部上傳算法的用戶總能耗都在增加. 由于算法1采用了部分任務遷移機制，可根據無線信道質量和計算任務數據量等因素優(yōu)化遷移至衛(wèi)星的數據量，所以其能耗始終低于其它兩種算法. 當計算任務的數據量為3 Mbit 時，算法1 的能耗比本地計算的能耗降低約81%. 對于任務數據全部上傳算法，當計算任務的數據量較少時，其能耗低于本地計算的能耗. 當計算任務的數據量較大時，因為全部數據均必須在有限的帶寬和時間內上傳至LEO 衛(wèi)星MEC 服務器，所以任務數據全部上傳算法的能耗將隨著任務數據量的增加而快速增長.當計算任務的數據量超過1.5 Mbit 時，任務數據全部上傳算法的能耗將遠大于本地計算和算法1的能耗.

圖2 用戶總能耗與計算任務數據量之間的關系

圖3示出了地面用戶總能耗與計算任務可容忍時延T之間的關系. 當計算任務的可容忍時延較小時，用戶需要在較短時間內完成任務數據的遷移和計算，因此三種算法的總能耗均較高. 隨著任務可容忍時延的增加，用戶可在較長的時間內以較低的發(fā)射功率進行任務數據的遷移，且本地計算的時間也較長，因此總能耗逐漸降低. 此外，算法1的能耗始終低于本地計算和任務數據全部上傳算法的能耗. 當計算任務可容忍時延為0.2 s時，算法1的能耗比本地計算的能耗降低約74%.

圖4 示出了用戶總能耗與ISL 信道容量之間的關系. 可以看出，ISL 的信道容量越大，用戶總能耗越低.對于相同的ISL信道容量，衛(wèi)星MEC服務器的CPU時鐘頻率fECn越高，用戶總能耗越低. 這是由于當ISL的信道容量較大時，衛(wèi)星間任務數據遷移產生的傳輸時延較小，并且衛(wèi)星MEC服務器的CPU時鐘頻率越高，衛(wèi)星執(zhí)行邊緣計算所需的時間越短，因此用戶向衛(wèi)星遷移任務數據的時間Ttx較長. 由定理1可知，用戶總能耗是關于Ttx的單調遞減函數，故用戶總能耗將隨著ISL信道容量和衛(wèi)星MEC 服務器的CPU 時鐘頻率的增加而降低. 當ISL的信道容量為0時，表示LEO衛(wèi)星間無法進行邊緣計算協(xié)作，此時用戶的總能耗最高. 與非協(xié)作衛(wèi)星邊緣計算相比，當ISL 的信道容量為100 Mbit/s 時，基于ISL 的LEO衛(wèi)星協(xié)作邊緣計算的能耗可至少降低約22%.

圖3 用戶總能耗與計算任務可容忍的時延之間的關系

圖4 用戶總能耗與ISL信道容量之間的關系

5 結論

研究了LEO 衛(wèi)星協(xié)作邊緣計算的任務遷移和資源分配算法，以地面用戶加權總能耗最小化為目標，以計算任務可容忍時延等為約束條件，通過LEO 衛(wèi)星ISL進行任務數據的二次遷移，實現衛(wèi)星間邊緣計算的協(xié)作.由于所建立的優(yōu)化問題的非凸性，將其分解為兩個子問題分別求解，并提出了LEO 衛(wèi)星協(xié)作邊緣計算的任務遷移和資源分配算法. 仿真結果表明，該算法可在8次迭代內收斂. 與本地計算和任務數據全部上傳算法相比，本文所提出的算法可至少降低約74%的用戶總能耗；與非協(xié)作衛(wèi)星邊緣計算相比，基于ISL 的LEO 衛(wèi)星協(xié)作邊緣計算可至少降低約22%的用戶總能耗，且ISL的信道容量越大，用戶總能耗越低.