余 翔，陳宇博，劉 晗，褚 軒

(重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065)

盡管5G網(wǎng)絡(luò)為全球大約20億用戶提供增強的移動寬帶服務(wù)，以及關(guān)鍵場景中高可靠和低延遲的服務(wù)。但當(dāng)前5G網(wǎng)絡(luò)受到經(jīng)濟成本與技術(shù)水平的限制，導(dǎo)致網(wǎng)絡(luò)覆蓋范圍有限。尤其在沙漠、極地、海洋地區(qū)以及其他難以建立地面基站的地區(qū)缺乏網(wǎng)絡(luò)覆蓋。為了提供無縫覆蓋和不間斷的網(wǎng)絡(luò)服務(wù)，衛(wèi)星通信已成為未來 5G/6G通信的有力補充［1］。

隨著新興業(yè)務(wù)如物聯(lián)網(wǎng)（IoT）、增強現(xiàn)實（AR）、虛擬現(xiàn)實（VR）和4K/8K視頻傳輸業(yè)務(wù)的發(fā)展，用戶終端的計算能力與續(xù)航能力導(dǎo)致了用戶體驗提升的瓶頸。在傳統(tǒng)非地面網(wǎng)絡(luò)（NTN）的透傳模式下衛(wèi)星充當(dāng)?shù)孛婢W(wǎng)關(guān)與用戶設(shè)備間的中繼節(jié)點，通過中繼請求地面云數(shù)據(jù)中心服務(wù)的模式，占用了大量帶寬并導(dǎo)致了用戶難以忍受的響應(yīng)時延與能耗。受到地面多接入邊緣計算（Multi?Access Edge Computing，MEC）技術(shù)的啟發(fā)［2］，為解決用戶對更高服務(wù)質(zhì)量（QoS）需求的挑戰(zhàn)，相較于傳統(tǒng)中心云模式，將計算能力下沉靠近用戶的低軌衛(wèi)星（Low Earth Orbit，LEO），形成全新的LEO衛(wèi)星邊緣計算場景。LEO衛(wèi)星節(jié)點上部署MEC的服務(wù)器可以減少頻繁的衛(wèi)星到地面鏈路傳輸，降低用戶的響應(yīng)時延與能耗，從而更好滿足用戶的任務(wù)需求，同時，LEO衛(wèi)星通信網(wǎng)絡(luò)的廣域覆蓋還能解決偏遠地區(qū)的網(wǎng)絡(luò)需求問題。

在傳統(tǒng)邊緣計算的研究中，文獻［3］表明了在多核服務(wù)器的MEC系統(tǒng)中，設(shè)計合理的任務(wù)卸載策略可以有效地降低系統(tǒng)時延，而文獻［4］則表明了多個邊緣節(jié)點間的協(xié)作，可以擴展網(wǎng)絡(luò)計算能力，獲得更優(yōu)的時間收益。但由于LEO節(jié)點自身載荷能耗敏感，在軌運行呈現(xiàn)高動態(tài)和周期性，與傳統(tǒng)場景下的研究有很大差異。因此，低軌衛(wèi)星邊緣計算已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的關(guān)注，被認為是未來網(wǎng)絡(luò)部署的重要研究方向之一。

考慮到能量和負載的影響，LEO衛(wèi)星上的MEC服務(wù)器可以采用輕量級的管理平臺，例如Docker［2］，這使衛(wèi)星具有計算和內(nèi)容分發(fā)的功能。文獻［5］討論了在STN網(wǎng)絡(luò)中通過MEC技術(shù)以提高QoS的可能，給出了所設(shè)計的衛(wèi)星邊緣場景模型，并設(shè)計了一種協(xié)作的計算卸載策略，通過仿真表明計算卸載策略可以顯著地降低用戶感知時延和系統(tǒng)能耗。文獻［6］提出了一種空地海集成的網(wǎng)絡(luò)架構(gòu)，并研究了一種基于深度強化學(xué)習(xí)的聯(lián)合通信和計算資源分配策略，目的是將用戶的總執(zhí)行延遲降到最低。文獻［7］則探討了一種新型具有雙邊緣計算功能的衛(wèi)星地面網(wǎng)絡(luò)，提出了一種雙邊緣計算卸載算法，通過 DECO?TCM 和 DECO?ECM 優(yōu)化了卸載延遲和系統(tǒng)能耗，并且還進行了數(shù)值仿真，證明了該算法使平均延遲和能量消耗分別降低約45%和49%。文獻［8］提出一個軟件定義的STN來管理和協(xié)調(diào)網(wǎng)絡(luò)，將資源分配描述為一個聯(lián)合優(yōu)化問題，并采取深度Q學(xué)習(xí)來解決。文獻［9］提出了一種基于排隊論和加權(quán)方法的服務(wù)器選擇策略。綜合各種因素評分來選擇最合適的計算卸載節(jié)點，仿真表明，對比固定選擇策略和隨機選擇策略，該策略可以將平均響應(yīng)延遲分別降低17%和34%。文獻［10］針對物聯(lián)網(wǎng)（IoT）設(shè)備的快速增長和計算需求，提出了一種基于博弈論的計算卸載策略以降低用戶計算成本，并通過仿真證明了該策略的有效性。

盡管在文獻［7］與［10］中，優(yōu)化了系統(tǒng)的時延與能耗，但忽略了LEO衛(wèi)星相對有限的計算能力和LEO衛(wèi)星地面覆蓋范圍的時變性。由于衛(wèi)星邊緣場景下，有限的計算能力和通信時間是反映衛(wèi)星邊緣節(jié)點特性的重要因素，也是優(yōu)化LEO衛(wèi)星邊緣場景的關(guān)鍵要素。因此，本文綜合考慮衛(wèi)星邊緣節(jié)點的計算能力和間歇性通信，同時計算卸載過程中的資源分配也是影響時延與能耗的關(guān)鍵因素，影響著用戶服務(wù)質(zhì)量，也需要對其進行合理分配優(yōu)化。

本文針對LEO衛(wèi)星邊緣計算卸載系統(tǒng)，在衛(wèi)星邊緣節(jié)點高動態(tài)性和計算能力有限的約束條件下，建立了系統(tǒng)模型，以時延和能耗作為系統(tǒng)成本。由于所提出的問題是一個混合整數(shù)非線性規(guī)劃（Mixed Integer Nonlinear Programming，MINP）問題，直接求解困難，為了減少計算復(fù)雜性，通過將問題拆分為資源分配和卸載決策兩個子問題。第一個子問題是具有預(yù)定卸載決策下的資源分配問題，第二個子問題是最優(yōu)資源分配下的卸載決策求解問題。在此基礎(chǔ)上，提出基于博弈論的計算卸載聯(lián)合資源優(yōu)化（Game Theory with Computing Offloading and Resource Allocation，GT?CORA）策略，進而降低系統(tǒng)總成本并提升用戶服務(wù)質(zhì)量。

1 系統(tǒng)模型

本文研究的是單LEO衛(wèi)星邊緣計算系統(tǒng)，如圖1所示，該系統(tǒng)是由一個配備了MEC服務(wù)器的在軌運行LEO衛(wèi)星和多個地面用戶組成，地面用戶任務(wù)獨立可卸載。部署MEC服務(wù)器的在軌LEO衛(wèi)星稱為衛(wèi)星邊緣節(jié)點，地面的用戶數(shù)量為K，用集合D＝｛i：i＝1，2，…，K｝ 表示。 單個設(shè)備表示為i。 同時考慮到衛(wèi)星運行的高動態(tài)性，只有在特定的通信窗口才能通過無線信道進行數(shù)據(jù)通信，實現(xiàn)計算卸載，執(zhí)行地面設(shè)備用戶任務(wù)，返回計算結(jié)果。

圖1 衛(wèi)星邊緣計算系統(tǒng)模型

1.1 低軌衛(wèi)星覆蓋模型

不同于地面MEC的網(wǎng)絡(luò)模型，LEO衛(wèi)星邊緣節(jié)點的特點之一就是高動態(tài)性，因此地面用戶與衛(wèi)星邊緣節(jié)點的連接并非全天候保持實時連接，需要衛(wèi)星邊緣節(jié)點和地面用戶設(shè)備保持特殊的幾何可視關(guān)系，當(dāng)衛(wèi)星邊緣節(jié)點進入通信窗口才能進行通信和數(shù)據(jù)的傳輸。根據(jù)文獻［11］，所需要滿足的幾何關(guān)系如圖2所示。其中，Re表示地球半徑，h表示衛(wèi)星軌道運行高度，s表示用戶與衛(wèi)星邊緣節(jié)點的幾何距離。

圖2 衛(wèi)星與地面用戶的空間幾何關(guān)系圖

忽略其他因素，只有當(dāng)α＞0時，衛(wèi)星進入通信窗口，數(shù)據(jù)傳輸可行，其中α為衛(wèi)星邊緣節(jié)點與地面的仰角，表達式為

式中，Δ?＝?t－ ?s，其中，?t和φt分別表示用戶設(shè)備的經(jīng)度與緯度，?s和φs分別表示衛(wèi)星邊緣節(jié)點的經(jīng)度和維度。同時如果移動設(shè)備之間相距很遠，這些設(shè)備間則不構(gòu)成競爭，因此地面設(shè)備位于一個相對于衛(wèi)星節(jié)點靜止不動的較小區(qū)域，可以假設(shè)這些設(shè)備與衛(wèi)星之間的幾何關(guān)系是相同的。

θ為LEO衛(wèi)星邊緣節(jié)點與地面設(shè)備間的地心夾角，可以表達為

當(dāng)α＝0可以求得通信窗口的最大臨界值θ0。

1.2 通信模型

對于無線通信模型，假設(shè)衛(wèi)星接入帶寬劃分為K個子信道，每個信道的帶寬為W，用戶通過計算卸載可以降低任務(wù)的處理時延與能耗，但在傳輸任務(wù)時也帶來額外的通信時延與能耗，根據(jù)香農(nóng)定理，將通信模型定義為

式中，Ri為用戶i的上行傳輸速率，Pi為用戶i的上行發(fā)射功率，hi為信道增益，N為高斯白噪聲功率。

1.3 計算模型

1.3.1 本地計算

在本地卸載的決策下，計算任務(wù)Wi由本地用戶設(shè)備執(zhí)行。是本地用戶設(shè)備的CPU時鐘周期，也代表著本地設(shè)備的計算能力，可以計算出本地卸載任務(wù)的執(zhí)行時延為

本地能耗的計算根據(jù)文獻［12］得

式中，κ表示能量因子，取決于芯片架構(gòu)［13］，結(jié)合時延與能耗可以得到本地卸載的成本函數(shù)為

式中，β和1－β分別表示能耗于時延在成本函數(shù)的權(quán)重值，且0≤β≤1。

1.3.2 衛(wèi)星邊緣計算

在衛(wèi)星邊緣計算的情況下，計算任務(wù)卸載到在軌運行的衛(wèi)星邊緣節(jié)點執(zhí)行處理。為衛(wèi)星邊緣節(jié)點分配給用戶設(shè)備i的計算能力（CPU cycles/s）?？紤]用戶設(shè)備與在軌衛(wèi)星之間的距離所導(dǎo)致的傳播時延，衛(wèi)星卸載策略的時延消耗可以表達為

s可以表達為

式中，θ為用戶設(shè)備與衛(wèi)星節(jié)點的地心夾角。

卸載到衛(wèi)星邊緣節(jié)點的能耗可以表達為

式中，F(xiàn)s為衛(wèi)星邊緣節(jié)點的CPU運行時鐘頻率。

結(jié)合式（7），式（10）和式（11）可以得到選擇衛(wèi)星邊緣節(jié)點卸載的成本函數(shù)為

2 基于博弈論的計算卸載聯(lián)合資源優(yōu)化

2.1 問題描述

根據(jù)第1節(jié)的系統(tǒng)模型，將計算卸載問題轉(zhuǎn)化為一個資源約束條件下的系統(tǒng)成本函數(shù)最優(yōu)化問題，定義為

式中，C1為上行通信資源的約束，保證分配給卸載用戶的上行傳輸功率不超過最大傳輸功率。C2為計算資源的約束，保證分配給卸載用戶的計算資源不超過服務(wù)器擁有的最大資源，C3代表二進制變量的卸載策略。

在式（13）中，由于通信資源和計算資源是連續(xù)變量，而卸載決策是整數(shù)向量，因此該問題是一個混合整數(shù)非線性規(guī)劃（MINLP）問題，是一個NP難的問題。為了簡化求解，可重寫MINLP問題為

2.2 資源分配

由式（14）拆出的資源分配問題為

給定卸載決策情況下，將式（12），式（7），式（10）和式（11）代入式（15），并拆開整理后可得

式中，V為不與優(yōu)化變量相關(guān)的常數(shù)項，且式（16）第一個加號左側(cè)項可表達為通信資源分配子問題，右側(cè)可表達為計算資源分配子問題。求解式（16）的最小值等價為求解兩個子問題的最小值。資源分配問題可以由式（17）和式（18）分別表示。

上行功率分配子問題為

計算資源分配子問題為

2.2.1 上行功率分配子問題

對于上行功率分配子問題（17），可以改寫為

引理1g（Pi）函數(shù)是單峰的。

證明首先g（Pi）在R是二次可微的，接下來檢查擬凸的二階條件，即存在一點x0使得0 也滿足

g（Pi） 的一階導(dǎo)數(shù)為

可以看出g′（Pi）的正負完全取決于等號右側(cè)的分子部分，令

算法1上行發(fā)射功率分配二分法

2.2.2 計算資源分配子問題

對于計算資源分配子問題可以改寫為

以及

式（22）的拉格朗日函數(shù)可以表示為

式中，λ表示拉格朗日乘子，拉格朗日函數(shù)的導(dǎo)數(shù)為

通過使得拉格朗日梯度等于零，解出最優(yōu)計算資源分配。最優(yōu)計算資源分配如下

式中，λ?＞0是連續(xù)滿足的。因此可以得到KKT條件

將式（27）代入式（28）可得

最終將式（29）代入式（27）得到問題（22）最優(yōu)解的封閉形式為

2.3 計算卸載

本文將最優(yōu)資源分配下的最優(yōu)計算卸載子問題表示為非合作策略博弈G，該博弈可以表示為G＝表示博弈參與者的集合，表示用戶參與者i的策略集合，表示系統(tǒng)成本函數(shù)，a－i表示除設(shè)備i以外的所有設(shè)備的卸載選擇。在一個競爭博弈環(huán)境下，每個用戶都在約束條件下獨立調(diào)整策略來最大化自己的利益，即最小化系統(tǒng)成本

定義1如果對于?i∈D存在卸載策略組合為非合作博弈G的納什均衡（Nash Equilibrium，NE），表示為除了用戶i外所有用戶設(shè)備的卸載策略組合，有

式（32）表示均衡狀態(tài)給定用戶的卸載決策a－i情況下，ai不能通過單方面改變它的卸載決策來進一步降低系統(tǒng)的計算開銷，但是NE可能存在，或不存在。接下來，本文將引入勢博弈的概念來解決這個問題。

定義2在一個有限博弈模型G中，存在一個函數(shù)對所有游戲參與者和策略向量滿足

則表明該博弈存在勢博弈。

定理1如果一個勢博弈具有有限的策略集合，那么它存在一個純策略的納什均衡。

接下來，證明本文提出的博弈G存在確切的勢博弈。

證明首先定義一個勢函數(shù)P：A→R為

基于式（29）可以得到

基于式（34）可以得到P（1，a－i） 和P（0，a－i） 分別為

由

可以得到

同理可以計算得到

通過式（39）和式（40）證明滿足定義2，即本文的博弈存在并可以通過一個確切的勢博弈函數(shù)表示，并且根據(jù)納什均衡存在定理［15］，其中至少存在一組純策略納什均衡。

基于上述分析，本文提出基于博弈論的計算卸載聯(lián)合資源優(yōu)化（Game Theory with Computing Offloading and Resource Allocation，GT?CORA）策略，詳細描述見算法2。

算法 2GT?CORA

3 仿真結(jié)果和分析

本節(jié)通過仿真結(jié)果來驗證GT?CORA的性能，模擬了一個單衛(wèi)星邊緣節(jié)點，多地面用戶設(shè)備的計算卸載系統(tǒng)，結(jié)合文獻［16－20］中的主要參數(shù)設(shè)置，表1為性能評估中的主要參數(shù)設(shè)置，并將GT?CORA與以下卸載策略進行對比。

表1 仿真參數(shù)

（1） 本地卸載（ALL Local Offloading，ALO）：所有的用戶選擇本地執(zhí)行任務(wù)。

（2） 全部卸載（All SMEC Offloading，ASO）：所有用戶都選擇將任務(wù)卸載至衛(wèi)星邊緣節(jié)點。

（3） 貪婪卸載（Greedy Offloading，GO）：用戶貪婪選擇開銷最小的節(jié)點進行卸載。

在仿真實驗中，假設(shè)有5～40個地面用戶設(shè)備分布在相較于LEO低軌衛(wèi)星覆蓋范圍靜止不動的較小區(qū)域，區(qū)域經(jīng)緯度分別設(shè)置為 106°34′和29°33′，假設(shè)地面終端產(chǎn)生任務(wù)的過程為泊松過程。衛(wèi)星節(jié)點選擇Celestrak公布的銥星星座的兩行軌道數(shù)據(jù)（Two?Line Orbital Element，TLE）中的一顆銥星的TLE作為模擬星座軌道，通過STK軟件選取2020年1月1日期間模擬LEO在軌運行衛(wèi)星的衛(wèi)星坐標(biāo)。

首先通過對比實驗研究不同卸載方案下的邊緣地區(qū)用戶設(shè)備數(shù)量與平均計算開銷的關(guān)系。從圖3可以看出，相較于ALO、ASO和GO策略，隨著用戶設(shè)備數(shù)量的增加，GT?CORA的平均計算開銷分別降低了47%、31%和20%。而且，隨著用戶設(shè)備的增加，由于設(shè)備之間競爭資源的愈加激烈，其他策略無法平衡設(shè)備間對資源的競爭，導(dǎo)致成本大幅增加。注意到本文所提出的GT?CORA策略和ASO策略之間的差距擴大了。這是因為隨著設(shè)備數(shù)量的增加，GT?CORA策略總是為設(shè)備提供更好的卸載策略和資源分配，而ASO總是選擇衛(wèi)星卸載，設(shè)備增多時，由于排隊等待衛(wèi)星節(jié)點處理，會帶來巨大的等待時延。因此，當(dāng)設(shè)備數(shù)量增加時，GT?CORA策略可以有效地降低系統(tǒng)的平均計算開銷。

圖3 用戶在不同卸載方案下的平均計算開銷

圖4顯示了平均計算開銷與完成任務(wù)所需CPU周期數(shù)量之間的關(guān)系，可以看到，GT?CORA、ASO、ALO、GO的平均計算開銷的趨勢都隨著任務(wù)計算所需CPU周期的增加而上升，這表明了計算需求更強的任務(wù)會帶來更多的平均計算開銷。相較于GO、ALO、ASO，GT?CORA策略的平均計算開銷有明顯降低，平均計算開銷分別降低了21%、36%和31%。此外還可以觀察到GO與ASO隨著任務(wù)計算所需CPU周期的增加曲線貼合，這是由于隨著任務(wù)計算能力的增加，本地的計算能力無法處理這些亟待解決的任務(wù)，GO策略選取最優(yōu)節(jié)點更加偏向于擁有強大計算能力的衛(wèi)星邊緣節(jié)點，策略選擇偏向ASO，但這也帶來了更多的等待時延和傳輸時延，增大了計算開銷。

圖4 任務(wù)計算所需CPU周期對應(yīng)的平均計算開銷

在圖5中，以不同的衛(wèi)星邊緣節(jié)點的計算能力來研究所提出策略的性能，相較于ALO、ASO、GO 3種策略，GT?CORA在不同的衛(wèi)星邊緣節(jié)點計算能力下都有不錯的效果，性能都優(yōu)于其他3種策略。圖5顯示了5 GHz前后的不同趨勢，下降趨勢的原因是隨著衛(wèi)星時鐘頻率的增加，器件的成本與之成反比，器件在這一時期占主導(dǎo)地位。相反，衛(wèi)星成本呈小幅上升趨勢的原因是與時鐘頻率成正比，在此期間衛(wèi)星成本占主導(dǎo)地位。此外，ASO策略選擇將任務(wù)全部卸載到衛(wèi)星邊緣節(jié)點之上，當(dāng)衛(wèi)星邊緣節(jié)點的時鐘頻率較低時會帶來更高的計算開銷。而ALO策略選擇將任務(wù)全部本地執(zhí)行，計算開銷與衛(wèi)星邊緣節(jié)點的計算能力無關(guān)，平均計算開銷保持不變。

圖5 衛(wèi)星邊緣節(jié)點時鐘頻率對應(yīng)的平均計算開銷

在任務(wù)成功率方面，通過圖6可以發(fā)現(xiàn)，本文所提出的GT?CORA策略任務(wù)成功率優(yōu)于其他策略，隨著用戶設(shè)備數(shù)量增多，任務(wù)成功率依舊保持在83%左右。而ASO和GO隨著用戶設(shè)備數(shù)量的增加，任務(wù)成功率下降趨勢明顯，這是由于用戶設(shè)備數(shù)量增多后選擇卸載到衛(wèi)星邊緣節(jié)點，但是衛(wèi)星邊緣節(jié)點位于通信窗口期內(nèi)的時間有限，導(dǎo)致了部分任務(wù)卸載失敗，或任務(wù)的時延等待超過了任務(wù)最大的容忍的時延閾值，從而任務(wù)成功率下降。

圖6 不同計算卸載策略的任務(wù)成功率

4 結(jié)束語

針對低軌衛(wèi)星邊緣計算場景，考慮LEO衛(wèi)星邊緣節(jié)點特性，采取博弈論解決地面多用戶設(shè)備間的計算卸載問題，設(shè)計了一種基于博弈論的計算卸載聯(lián)合資源分配優(yōu)化策略GT?CORA，仿真實驗表明，相較于其他算法，本文所提算法具有良好的計算卸載性能和任務(wù)成功率，尤其在地面設(shè)備增多時性能更優(yōu)。下一步將研究多LEO衛(wèi)星邊緣節(jié)點場景，和地面云節(jié)點融合場景下的計算卸載問題，從而實現(xiàn)多層次任務(wù)的高效卸載，提升用戶服務(wù)質(zhì)量。