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

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

0 引言

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

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

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

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

1 系統(tǒng)模型

1.1 通信卸載場(chǎng)景

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

圖1 星-地卸載場(chǎng)景Fig.1 Satellite-Ground computing unload scene

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

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

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

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

上述場(chǎng)景中，通信模型都為一個(gè)衛(wèi)星邊緣計(jì)算節(jié)點(diǎn)對(duì)應(yīng)服務(wù)范圍內(nèi)多個(gè)終端設(shè)備?？山?shù)學(xué)模型并設(shè)定參數(shù)如下：

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

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

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

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

(1)

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

(2)

1.2 計(jì)算模型

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

1.2.1 本地處理

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

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

(3)

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

En=θn(Fbs)2an，

(4)

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

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

(5)

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

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

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

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

(6)

Eup(n)=PnTup(n)，

(7)

(8)

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

(9)

1.3 卸載問題描述

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

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

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

(10)

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

2 基于博弈論的計(jì)算卸載算法

2.1 博弈論基本思想

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

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

2.2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

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

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

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

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

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

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

圖3展示了4種算法的卸載性能:本地處理算法和忽略排隊(duì)時(shí)延算法因?yàn)闆Q策的單一性，設(shè)備間相互干擾會(huì)很大，兩者開銷明顯大于博弈論算法。而在博弈論卸載算法和不考慮排隊(duì)時(shí)延算法二者中，后者因?yàn)樗惴ū旧磉x取策略稍弱，加之忽略了排隊(duì)時(shí)延存在時(shí)可能有的增益，總體開銷稍大。

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

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

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

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

圖5 待卸載任務(wù)數(shù)N對(duì)總體開銷的影響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的變化趨勢(shì)與原算法保持一致，但此時(shí)算法的損耗值在原算法基礎(chǔ)上進(jìn)一步減小。分析原因是優(yōu)先選擇了卸載后損耗大的終端設(shè)備進(jìn)行任務(wù)卸載。根據(jù)ECN和移動(dòng)終端處理能力之比，在終端設(shè)備之間相互干擾尚不嚴(yán)重的情況下，那些卸載到邊緣節(jié)點(diǎn)上處理開銷依舊大的任務(wù)，被放置在本地處理只會(huì)帶來更大的時(shí)延與能耗。優(yōu)先卸載處理它們，能有效解決這一問題。

4 結(jié)束語

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

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