羅志勇，黃 澳，孫韶輝，辛 寧

(1.中山大學 電子與通信工程學院，廣東 廣州 518107;2.大唐移動通信設備有限公司，北京 100083;3.中國空間技術研究院通信與導航衛(wèi)星總體部，北京 100094；4.國家航天局衛(wèi)星通信系統(tǒng)創(chuàng)新中心，北京 100094)

0 引言

計算卸載策略一直是邊緣計算技術(Mobile Edge Computing，MEC)推廣應用過程中重要的研究內容[1-3]。一方面，通信技術的不斷發(fā)展使得數據流量不斷增加、業(yè)務需求不斷提高[4]，而終端設備計算能力與能量儲備卻是有限的，難以滿足業(yè)務在時延和能耗方面的需求。因此，在傳統(tǒng)通信網絡中終端設備通常將任務傳輸給遠處的云計算中心進行處理[5]，在邊緣網絡中則是需要將任務卸載到邊緣節(jié)點(Edge Computing Node,ECN)上[6]。另一方面，因為ECN具有輕量化特點，部署資源有限，同時移動設備進行卸載時自身也有能量資源消耗，所以也需要有合適的計算卸載策略來優(yōu)化卸載過程。

Wu H等人[7]將響應時延作為主要研究對象，提出GAMEC策略進行卸載節(jié)點的選擇決策。余翔等人[8]提出基于博弈論的功率分配算法，對功率和計算卸載進行聯(lián)合優(yōu)化，提高卸載性能。文獻[9-10]基于聯(lián)合思想，將計算卸載同計算資源分配聯(lián)合為一個NP-hard優(yōu)化問題，各自采用不同方法分兩步進行了求解。

在具體的MEC網絡中，ECN對部署資源的分配非常重要。尤其是當多設備同時卸載競爭資源時，通信信道被大量占用導致設備相互干擾加大，進而影響整體網絡性能。

在天地融合網絡這一應用場景下，由于星上資源的寶貴，這樣的問題更加突出[11-12]。針對該問題，本文從文獻[13]提出的地面基站內多終端設備博弈卸載模型中受到了啟發(fā)，提出該場景下的博弈論卸載算法。經過有限次迭代達到非合作博弈下的“納什均衡”，最終實現了該算法在天地融合網絡中的運用和改進。

1 系統(tǒng)模型

1.1 通信卸載場景

在海洋、荒漠或戰(zhàn)爭、災害等復雜地理環(huán)境中，地面蜂窩網絡難以滿足船只、UAV等終端的服務需求，移動終端可選卸載方式只有將任務卸載到部署了MEC服務的LEO衛(wèi)星上進行處理，其卸載模型如圖1所示。

圖1 星-地卸載場景Fig.1 Satellite-Ground computing unload scene

該場景在復雜地理環(huán)境中有明確需求存在。但就現有技術水平而言，從地面將計算任務卸載到星上處理并不經濟，難以在上述固定需求外開展大規(guī)模應用。

另一種考慮為由于衛(wèi)星之間處理能力的不均等，使得處理能力弱的衛(wèi)星有可能將任務卸載到能力強的衛(wèi)星上，來減小開銷的星間卸載場景。其卸載場景基本單元如圖2所示。

圖2 星間卸載模型基本單元Fig.2 Satellite-Satellite computing unload scene

該卸載場景需要衛(wèi)星之間存在星間鏈并且具備交換通信能力。例如銥星星座中每顆衛(wèi)星與同、異軌道面共4顆衛(wèi)星構成星間鏈路[14]。在這個基本結構上延伸擴展形成一個龐大的衛(wèi)星星座。設想星座中存在CPU頻率高的高處理能力衛(wèi)星，而周圍衛(wèi)星處理能力較弱。倘若衛(wèi)星可通過一定的卸載策略進行決策判斷，將任務卸載到能力強的衛(wèi)星上進行處理，則此時利用卸載策略最小化卸載方開銷，比星地卸載場景中節(jié)約地面終端資源的意義更大。

上述場景中，通信模型都為一個衛(wèi)星邊緣計算節(jié)點對應服務范圍內多個終端設備。可建立數學模型并設定參數如下：

終端設備集P={1,2,3,…,N},每個設備都有不可分解的計算任務;

無線信道集C= {1,2,3,…,K},代表衛(wèi)星提供K個可進行任務卸載的正交子信道;

決策集S={s1,s2,…,sn}，其中，有si代表終端設備i的決策情況。當si= 0時，代表任務本地計算；當si∈C時，代表任務將卸載到第si個信道上進行處理。

考慮到不同終端設備進行任務卸載時可能利用相同子信道導致相互干擾，根據Shann-Hartley定理可得到從終端n卸載任務到SEC服務器第k個信道的數據傳輸速率為：

(1)

式中，w為子信道帶寬，w0代表傳輸過程中的噪聲功率，qi代表終端i傳輸功率；gi,k為終端設備i在衛(wèi)星信道k上的信道增益。

(2)

1.2 計算模型

根據決策的不同，任務處理類型可分為本地處理和衛(wèi)星邊緣節(jié)點處理兩大類。

1.2.1 本地處理

本地處理對應終端設備決策si= 0的情況，即計算任務由終端本身處理而不卸載至MEC網絡中。此時需知參數主要是終端CPU處理能力Fbs和能耗因數θn。

定義本地處理時延為任務所需CPU操作數和本地處理能力之比：

(3)

本地處理過程中的能耗即為任務所需CPU操作數、本地處理能力平方與能耗因數之積：

En=θn(Fbs)2an，

(4)

式中，能耗因數θn通常與芯片中開關電容元件數量等參數有關[17]。

綜上所述，本地處理模型的計算開銷函數即可表示為:

(5)

1.2.2 衛(wèi)星邊緣節(jié)點處理

衛(wèi)星邊緣節(jié)點處理對應終端設備決策si∈C的情況，即終端設備本地處理能力不足或者本地處理開銷較大時，決定把計算任務卸載到衛(wèi)星所提供的第si條子信道上進行處理。

整個計算卸載過程分為三部分：終端任務上傳、邊緣節(jié)點處理以及處理結果回傳。倘若節(jié)點上部署的資源正在被其他終端設備調用，則還需等待資源釋放的等待時延。

結合式(1)可定義上傳時延、上傳能耗、節(jié)點處理時延為：

(6)

Eup(n)=PnTup(n)，

(7)

(8)

綜合式(6)～式(8)，考慮到已卸載終端數num和可能存在的排隊時延Twait后，可得衛(wèi)星邊緣節(jié)點處理模型的開銷函數表達式為：

(9)

1.3 卸載問題描述

考慮多用戶對衛(wèi)星邊緣節(jié)點上部署資源的競爭，優(yōu)化參數目標為綜合考慮時延與能耗的總開銷值。

用S-i={s1,…,si-1,si+1,…,sn}代表終端設備i以外所有終端設備的決策向量集。則對終端設備i來說，需要做出決策si以獲取期望最小開銷：

minCosti(si,S-i),?i∈P,si∈{0∪C}，

(10)

從而獲得能夠使整個天地融合網絡MEC系統(tǒng)卸載過程總體開銷最小的解決策集S。

2 基于博弈論的計算卸載算法

2.1 博弈論基本思想

在有多個參與者的博弈過程中，各參與者都需要結合其他參與者的決策情況，在迭代中不斷調整自身決策使自己盡可能獲取更大增益/更小開銷，經過有限次的迭代達到“納什均衡”情況。在該情況下任何一個理智的決策者都不會再做出更新決策的選擇，因為他已經獲得了當前情況下的最大收益或最小開銷。

因此，該思想適用于計算卸載中多終端非合作博弈場景[18]，分布式的卸載策略讓每個節(jié)點可自行評估決策好壞并做出當前情況最優(yōu)決策，完成卸載節(jié)點選擇和任務卸載，從而使得MEC系統(tǒng)整體卸載開銷最小。

2.2 算法實現

在MEC系統(tǒng)中，不同終端之間的非合作博弈是勢博弈的一種，其特點是存在一個單調勢函數。每次迭代中用戶改變策略導致開銷變化都能映射到勢函數中，可證明經過有限次迭代，必能得到“納什均衡”解[19]。

由此可設計博弈論卸載算法，具體要點如下：

① 初始化終端設備決策全為本地決策。

② 每個時隙下每個終端設備的工作有：

a. 計算已有決策對應開銷值；

b. 評估所有可能的決策值，取當前情況下開銷值最小決策為最優(yōu)決策；

c. 比較已有決策與最優(yōu)決策，若最優(yōu)決策開銷小于當前決策開銷，代表終端設備決策可更新。

③ 下一個時隙，邊緣服務器隨機選擇一個終端設備進行決策更新。重復迭代過程，直至當前時隙無可更新決策的終端設備，此時算法結束。

據此，可給出多用戶博弈卸載策略如下:

算法 1:天地融合網絡中博弈論卸載算法輸入:N 個計算任務元組、噪聲功率w0、各終端傳輸功率P與對應各信道上的增益g1初始化:可更新決策集不為空2對于每個用戶從i = 1轉到 N進行3初始化用戶決策 si= 0, 計算本地處理開銷 cost(i)=λtiTi+λeiEi4while當前可更新用戶集不為空5 將更新決策用戶集置空;6 對于每個用戶從i = 1轉到 N進行7 對于每個衛(wèi)星子信道從l= 1 轉到 K 進行8 獲取該信道信干噪比,計算上傳速率 Rup(n);9 計算該用戶在該信道總體開銷值 C(si,S-i);10 該用戶最優(yōu)決策開銷值newsi(t) = min(C(si,S-i))11 if最優(yōu)決策開銷現有決策開銷,then12 將更新請求與內容一并發(fā)送至 SEC 節(jié)點13 可更新決策用戶集用戶數 +1;14 邊緣衛(wèi)星MEC服務器在可更新決策用戶集中隨機選擇一個,按內容更新決策與對應開銷值15 對于每個用戶從i = 1轉到N進行16 if收到到更新指令,then17 下一時隙更新 si(t + 1) = newsi(t);18 else19 下一時隙不更新 si(t + 1) = si(t)。

2.3 貪心算法優(yōu)化

根據現有算法1，在每一次迭代中MEC服務器在可更新的終端設備列表中隨機選擇一個終端設備進行決策更新，這樣的隨機選擇策略充分體現了終端設備之間接入卸載的公平性。

但從開銷角度來看，該選擇策略并非最優(yōu)?？梢胴澬乃惴ǖ乃枷?，MEC服務器對可更新決策開銷集UC進行排序，優(yōu)先選擇卸載后開銷值大的用戶進行任務卸載。將該算法中“在可更新終端設備集UD中隨機選擇一個終端設備進行更新”的隨機選擇策略替換為貪心選擇策略。

3 仿真結果分析

以1.1節(jié)中星地卸載模型為例，一些基本參數設置如表1所示，在Matlab2020a平臺上進行編程仿真測試。

表1 仿真參數指標

3.1 博弈論算法仿真結果

將程序結束后卸載方所有設備的總體開銷值作為評判標準，把該算法與另外3種常見的計算卸載方案加以對比：

① 本地處理方案，只有本地處理決策。

② 忽略排隊時延方案，只做出將任務卸載到邊緣計算節(jié)點上的決策。

③ 不考慮排隊時延方案，即該方案不能接受存在的排隊時延。一旦邊緣計算節(jié)點資源已被其他終端設備利用，終端設備就只會做出將任務放置在本地進行處理的決策。

圖3展示了4種算法的卸載性能:本地處理算法和忽略排隊時延算法因為決策的單一性，設備間相互干擾會很大，兩者開銷明顯大于博弈論算法。而在博弈論卸載算法和不考慮排隊時延算法二者中，后者因為算法本身選取策略稍弱，加之忽略了排隊時延存在時可能有的增益，總體開銷稍大。

圖3 不同算法下的卸載開銷Fig.3 Unloading loss of different algorithms

圖4衛(wèi)星支持的子信道數量增加實際增加了ECN上的通信資源，不同終端設備決策到相同信道上相互干擾的情況更少、競爭減小。因此博弈論、不考慮排隊時延、忽略排隊時延3種方案總開銷都呈下降趨勢。本地處理方案與其無關，總開銷保持不變。

圖4 子信道個數K對總體開銷的影響Fig.4 Impact of subchannel number on overhead

圖5表明終端設備數/待卸載任務數N的變化，一方面本身增加了網絡中總的待處理任務量；另一方面在信道資源不變的情況下，有更多終端設備受到了其他設備的干擾。各方案總體開銷值都在增加，尤其是忽略排隊處理方案受到影響很大。

圖5 待卸載任務數N對總體開銷的影響Fig.5 Impact of device number on overhead

在這過程中博弈論算法總體開銷最低，始終保持著較好表現。

3.2 貪心優(yōu)化結果

根據2.3節(jié)中引入的貪心策略，優(yōu)化MEC服務器選擇更新策略后重新進行仿真，可得結果如圖6和圖7所示。

圖6 貪心優(yōu)化算法效果(K變化)Fig.6 Greedy strategy optimization effect(K changes)

圖7 貪心優(yōu)化算法效果(N變化)Fig.7 Greedy strategy optimization effect(N changes)

由圖6與圖7可得，優(yōu)化后算術開銷隨參數N與K的變化趨勢與原算法保持一致，但此時算法的損耗值在原算法基礎上進一步減小。分析原因是優(yōu)先選擇了卸載后損耗大的終端設備進行任務卸載。根據ECN和移動終端處理能力之比，在終端設備之間相互干擾尚不嚴重的情況下，那些卸載到邊緣節(jié)點上處理開銷依舊大的任務，被放置在本地處理只會帶來更大的時延與能耗。優(yōu)先卸載處理它們，能有效解決這一問題。

4 結束語

本文針對天地融合移動邊緣計算網絡，研究其中各終端對邊緣節(jié)點通信資源的競爭問題。針對終端計算任務不可分割的二進制卸載類型，提出該場景下基于博弈論的分布式卸載算法。在討論適用場景、進行公式推導與計算模型的構建后，Matlab程序仿真結果表明該方法能有效減小卸載方的時延與能耗。貪心思想的引入改進了MEC服務器的選擇更新策略，使得總體開銷值進一步縮小。在實際意義上對天地融合網絡時延方面的不足具有一定的彌補。

在后續(xù)工作中，將在此基礎上嘗試與排隊論、強化學習等多種理論和方法結合，從模型與算法等角度進行進一步優(yōu)化完善，適應規(guī)模更大、鏈路更復雜的天地融合網絡，進一步提高卸載效率。