天地融合網(wǎng)絡(luò)中基于博弈論的分布式卸載算法研究

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

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

0 引言

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

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

在具體的MEC網(wǎng)絡(luò)中，ECN對部署資源的分配非常重要。尤其是當(dāng)多設(shè)備同時卸載競爭資源時，通信信道被大量占用導(dǎo)致設(shè)備相互干擾加大，進(jìn)而影響整體網(wǎng)絡(luò)性能。

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

1 系統(tǒng)模型

1.1 通信卸載場景

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

1.2 計算模型

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

1.2.1 本地處理

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

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

(3)

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

En=θn(Fbs)2an，

(4)

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

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

(5)

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

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

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

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

(6)

Eup(n)=PnTup(n)，

(7)

(8)

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

(9)

1.3 卸載問題描述

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

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

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

(10)

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

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

2.1 博弈論基本思想

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

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

2.2 算法實現(xiàn)

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

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

① 初始化終端設(shè)備決策全為本地決策。

② 每個時隙下每個終端設(shè)備的工作有：

a. 計算已有決策對應(yīng)開銷值；

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

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

③ 下一個時隙，邊緣服務(wù)器隨機(jī)選擇一個終端設(shè)備進(jìn)行決策更新。重復(fù)迭代過程，直至當(dāng)前時隙無可更新決策的終端設(shè)備，此時算法結(jié)束。

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

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

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

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

但從開銷角度來看，該選擇策略并非最優(yōu)。可引入貪心算法的思想，MEC服務(wù)器對可更新決策開銷集UC進(jìn)行排序，優(yōu)先選擇卸載后開銷值大的用戶進(jìn)行任務(wù)卸載。將該算法中“在可更新終端設(shè)備集UD中隨機(jī)選擇一個終端設(shè)備進(jìn)行更新”的隨機(jī)選擇策略替換為貪心選擇策略。

3 仿真結(jié)果分析

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

表1 仿真參數(shù)指標(biāo)

3.1 博弈論算法仿真結(jié)果

將程序結(jié)束后卸載方所有設(shè)備的總體開銷值作為評判標(biāo)準(zhǔn)，把該算法與另外3種常見的計算卸載方案加以對比：

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

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

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

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

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

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

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

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

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

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

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

根據(jù)2.3節(jié)中引入的貪心策略，優(yōu)化MEC服務(wù)器選擇更新策略后重新進(jìn)行仿真，可得結(jié)果如圖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)化后算術(shù)開銷隨參數(shù)N與K的變化趨勢與原算法保持一致，但此時算法的損耗值在原算法基礎(chǔ)上進(jìn)一步減小。分析原因是優(yōu)先選擇了卸載后損耗大的終端設(shè)備進(jìn)行任務(wù)卸載。根據(jù)ECN和移動終端處理能力之比，在終端設(shè)備之間相互干擾尚不嚴(yán)重的情況下，那些卸載到邊緣節(jié)點上處理開銷依舊大的任務(wù)，被放置在本地處理只會帶來更大的時延與能耗。優(yōu)先卸載處理它們，能有效解決這一問題。

4 結(jié)束語

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

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