云邊環(huán)境下基于博弈論的兩階段任務(wù)遷移策略

王藝潔，凡佳飛，王陳宇

（1.山東科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，山東青島 266000；2.空裝駐上海地區(qū)軍事代表局空裝駐南京地區(qū)第三軍事代表室，南京 211100）

（*通信作者電子郵箱wyj_jsj@163.com）

0 引言

隨著物聯(lián)網(wǎng)（Internet of Things，IoT）的發(fā)展，移動設(shè)備的數(shù)量激增，具有沉浸式體驗的移動應(yīng)用程序正在逐漸流行，并成為5G［1］網(wǎng)絡(luò)中的主流應(yīng)用程序，豐富的應(yīng)用程序規(guī)模也變得越來越大，比如自然語言處理［2］、虛擬現(xiàn)實［3］、智能交通［4］、車輛互聯(lián)網(wǎng)［5］等，但這些新型應(yīng)用程序需要大計算量和高能耗，而受輕量級移動設(shè)備的限制，計算密集型應(yīng)用和計算資源有限的移動設(shè)備之間的沖突為未來物聯(lián)網(wǎng)的發(fā)展帶來了巨大挑戰(zhàn)［6］。

為了解決移動設(shè)備資源有限以及延遲的問題，移動邊緣計算（Mobile Edge Computing，MEC）［7-8］被提出。移動邊緣計算可以在緊鄰移動設(shè)備的無線接入網(wǎng)絡(luò)內(nèi)提供云計算能力，同時能夠滿足物聯(lián)網(wǎng)應(yīng)用的延遲要求［9］并提高物聯(lián)網(wǎng)移動設(shè)備的可靠性和能效，因此在過去的幾年時間出現(xiàn)了許多有關(guān)MEC 任務(wù)遷移的研究工作。Liu 等［10］提出Stackelberg 動態(tài)博弈模型，通過研究具有一個接入點（Access Point，AP）和許多其他無線設(shè)備的物聯(lián)網(wǎng)應(yīng)用的無線MEC 系統(tǒng)中的資源分配問題來獲得節(jié)點的最佳分配資源；Chen 等［11］研究在多信道無線干擾環(huán)境下的移動邊緣云計算的多用戶遷移問題，將移動設(shè)備之間的分布式計算遷移決策問題轉(zhuǎn)化為任務(wù)遷移博弈，但它未考慮到MEC 存在計算資源不足的可能性；文獻(xiàn)［12］中建立博弈模型并使用變分不等式理論計算靜態(tài)混合策略的任務(wù)均衡分配，通過分散算法用于在附近設(shè)備和邊緣云之間分配計算任務(wù)，但它并未考慮到任務(wù)之間的信號干擾；Zheng等［13］研究動態(tài)環(huán)境下移動計算的多用戶計算遷移問題，并提出多智能體隨機(jī)學(xué)習(xí)算法保證收斂速度達(dá)到納什均衡。Liu等［14］研究了在車輛邊緣網(wǎng)絡(luò)中多車輛計算遷移問題，通過計算遷移博弈來減少車輛計算開銷，但仍需進(jìn)一步研究車輛數(shù)與整體開銷的關(guān)系。

由于大多數(shù)有關(guān)MEC 計算遷移的研究工作僅僅考慮移動設(shè)備和MEC 服務(wù)器之間的資源分配［15］，而沒有考慮到集中式云計算（Centralized Cloud Computing，CCC）服務(wù)器［16］強(qiáng)大的計算能力和豐富的計算資源。而MEC 雖然可以減少處理延遲，改善用戶體驗，但是對于大量的物聯(lián)網(wǎng)移動設(shè)備和移動應(yīng)用程序的增加，MEC 服務(wù)器的資源瓶頸變得逐漸明顯，尤其要考慮網(wǎng)絡(luò)運營商的資本支出與運營支出；另一方面，物聯(lián)網(wǎng)移動設(shè)備在與云進(jìn)行數(shù)據(jù)交換時有可能經(jīng)歷較長的等待時間，但集中云可以為用戶提供精確的云處理能力?？梢哉fMEC 與云是互補的，因此充分利用移動設(shè)備、MEC 和CCC 的計算資源進(jìn)行計算遷移是值得考慮的一個重要舉措。近兩年以來，邊緣計算和云計算的關(guān)系變得清晰，二者并非互斥關(guān)系，而是相互融合。邊緣計算解決了云原生應(yīng)用的供應(yīng)問題，成為云計算在未來發(fā)展的一個重要落地支撐，從而來到“云邊協(xié)同”的新階段。

基于上述的問題，本文研究了多通道無線干擾環(huán)境下MEC 資源受限的多用戶任務(wù)遷移問題，并提出了一種用于物聯(lián)網(wǎng)系統(tǒng)中移動邊緣和云中心協(xié)同的計算資源分配機(jī)制［17］，為物聯(lián)網(wǎng)移動設(shè)備提供強(qiáng)大的混合云平臺，使得MEC 與集中式云共存。本文的目標(biāo)是確定物聯(lián)網(wǎng)移動設(shè)備的任務(wù)遷移決策。通過考慮移動設(shè)備的各異性，建立任務(wù)遷移模型滿足多用戶的任務(wù)遷移需求，提出了一種基于博弈論的兩階段任務(wù)遷移策略，以分布式的方式實現(xiàn)高效任務(wù)遷移。

1 系統(tǒng)模型

任務(wù)遷移考慮MEC 服務(wù)器和云中心服務(wù)器協(xié)同工作的范例。范例中包含一組移動設(shè)備、MEC 和CCC。在云邊協(xié)同環(huán)境下提供一種優(yōu)化解決方案，使得移動設(shè)備的成本開銷能達(dá)到一個近似最優(yōu)的結(jié)果。

1.1 通信模型

假設(shè)在云邊協(xié)同系統(tǒng)下有N個移動設(shè)備，表示為N={1，2，…，N}。通過無線基站部署MEC 服務(wù)器，移動設(shè)備可以通過無線接入點（Wireless Access Point，WAP）與MEC 連接通信，將移動設(shè)備的計算任務(wù)遷移到MEC 服務(wù)器上執(zhí)行。而無線基站有K條信道，這里的K個信道可以表示為K={1，2，…，K}。MEC 服務(wù)器擁有有限的計算資源，將MEC 的計算資源記為S。如果任務(wù)過多，可以通過有線連接的主干網(wǎng)遷移到集中式的云中心服務(wù)器執(zhí)行，本文假設(shè)云中心擁有無限的計算資源。而移動設(shè)備的每一個計算任務(wù)需要兩階段的任務(wù)遷移決策：第一階段是在移動設(shè)備端，設(shè)備首先決定是本地執(zhí)行還是MEC 服務(wù)器執(zhí)行；第二階段即在選擇MEC 執(zhí)行后，當(dāng)任務(wù)到達(dá)MEC 服務(wù)器發(fā)現(xiàn)資源不夠需要排隊，則決定是加入等待隊列還是繼續(xù)遷移到云中心服務(wù)器執(zhí)行。

用符號an表示第n個移動設(shè)備的決策結(jié)果，其中an={0}∪K：an=0代表計算任務(wù)由移動設(shè)備本地執(zhí)行；an=k表示移動設(shè)備n的計算任務(wù)通過信道an遷移到MEC 服務(wù)器上執(zhí)行。在第二階段的決策結(jié)果可以用符號yn表示，yn∈{0，1}：當(dāng)yn=0時，表示計算任務(wù)繼續(xù)遷移到集中式云服務(wù)器執(zhí)行；當(dāng)yn=1 時，表示計算任務(wù)在MEC 上執(zhí)行，MEC 資源不夠，任務(wù)也會排隊繼續(xù)等待執(zhí)行。此時，根據(jù)兩個階段能夠得到兩個決策向量α=(a1，a2，…，an)和ψ=(y1，y2，…，yn)。假設(shè)移動設(shè)備n通過信道k訪問MEC 服務(wù)器，則數(shù)據(jù)傳輸速率如式（1）［18］所示：

其中：W是信道帶寬，pn是n的傳輸功率，gn是n和基站之間的信道增益，σ0

2是背景噪聲功率。

在進(jìn)行第二階段的任務(wù)遷移時，MEC 與CCC 通過主干網(wǎng)進(jìn)行有線連接。本文使用rec表示二者之間的數(shù)據(jù)傳輸速率，同時假設(shè)這一速率是恒定不變的。

1.2 任務(wù)遷移博弈計算模型

移動設(shè)備n的計算任務(wù)，可以將其定義為Tn?(bn，qn)，其中bn是計算任務(wù)Tn所需的輸入數(shù)據(jù)量，qn是完成計算任務(wù)所需的總計算能力（即CPU 周期數(shù)量），本文將計算能耗和計算時間兩部分加權(quán)之和當(dāng)作執(zhí)行任務(wù)的總成本開銷。

1.2.1 本地計算模型

當(dāng)n選擇本地計算時，總成本開銷包括兩部分：任務(wù)本地執(zhí)行的時間和計算能耗。這里計算任務(wù)的執(zhí)行時間為，執(zhí)行任務(wù)的能耗為其中代表移動設(shè)備n的計算能力（即每秒的CPU 周期數(shù)）是每個CPU 周期的能耗系數(shù)。為了保證移動設(shè)備的能耗和執(zhí)行延遲最小，在本模型中制定一個能耗和延遲的加權(quán)和，并將其命名為開銷成本。因此本地執(zhí)行的總開銷成本為：

其中：λt和λe分別是移動設(shè)備n執(zhí)行延遲和能耗的權(quán)重系數(shù)，并且這兩個系數(shù)滿足λt+λe=1 且0 ≤λt，λe≤1。不同的場景具有不同的特征，也應(yīng)該對應(yīng)不同的加權(quán)參數(shù)，以此來反映不同研究場景的一般需求。

1.2.2 MEC計算模型

對于遷移到MEC的任務(wù)，延遲包括將任務(wù)傳送給MEC服務(wù)器的時間和在服務(wù)器上完成任務(wù)所需的計算時間。前者包括無線接口的傳輸時間以及移動設(shè)備與服務(wù)器之間的往返延遲。與文獻(xiàn)［19］相同，本文忽略了將計算結(jié)果發(fā)送回設(shè)備的延遲開銷，因為與傳入的數(shù)據(jù)相比，密集的計算任務(wù)產(chǎn)生的結(jié)果數(shù)據(jù)大小被認(rèn)為非常小。在任務(wù)遷移階段，傳輸任務(wù)需要時間以及會消耗能量，因此傳輸任務(wù)的延遲是任務(wù)的處理延遲是其中表示為MEC 服務(wù)器分配給移動設(shè)備n的計算能力（即每秒的CPU 周期數(shù)）。因此總延遲是處理延遲和傳輸延遲之和，即為

1.2.3 CCC計算模型

經(jīng)過第一階段的決策，移動設(shè)備將任務(wù)遷移到MEC 服務(wù)器，若此時MEC 服務(wù)器的計算資源不足夠，則移動設(shè)備需要決定繼續(xù)排隊等待任務(wù)執(zhí)行還是遷移到CCC 服務(wù)器上執(zhí)行。如果第二階段移動設(shè)備選擇將任務(wù)遷移到云服務(wù)器執(zhí)行，那么整體的延遲包括任務(wù)從MEC 傳輸?shù)紺CC 的延遲以及在云中心執(zhí)行的延遲。傳輸延遲為執(zhí)行延遲為因此總延遲是其中f c是中心云服務(wù)器的計算能力，這里認(rèn)為其為定值。綜上所述，將第一階段和第二階段的決策相結(jié)合可以得到總成本開銷為：

當(dāng)在MEC 服務(wù)器上執(zhí)行時yn=1，即成本開銷由遷移到MEC服務(wù)器的延遲與能耗組成；當(dāng)yn=0時，總成本開銷由遷移到云服務(wù)器的延遲與能耗組成。

根據(jù)通信和計算模型可以發(fā)現(xiàn)，當(dāng)選擇將計算任務(wù)遷移至MEC 服務(wù)器時，每個移動設(shè)備的成本開銷不僅取決于自己的遷移策略，還取決于其他移動設(shè)備的策略。如果太多移動設(shè)備選擇相同的策略（即相同的無線信道）來遷移任務(wù)，那么遷移率會很低，并導(dǎo)致更多計算成本（包括更長的傳輸時間以及更高的能耗），這種情況下可能移動設(shè)備進(jìn)行本地計算對自己會更有益。由于不同移動設(shè)備之間的相互影響關(guān)系，可以通過博弈論來進(jìn)行建模和分析用戶的遷移決策從而進(jìn)行計算遷移。但是由于移動設(shè)備的狀態(tài)是動態(tài)變化的，移動設(shè)備之間無法互相了解對方的狀態(tài)，而且移動設(shè)備更喜歡通過速度快的信道來降低其成本開銷，但是無線信道是隨著時間變化的，這使得問題更具有挑戰(zhàn)性。

2 任務(wù)遷移博弈

博弈論（Game Theory，GT）可以用來分析需要相互協(xié)作才能實現(xiàn)自己目標(biāo)的多個非合作實體之間的交互。由于每個實體的需求不同，并不會追求相同的利益，因此在每個參與者選擇最佳策略來達(dá)到自己的利益最大化時，都需要一個分散的策略。本文考慮利用每個移動設(shè)備的智能，以低復(fù)雜度來制定分散方案。文獻(xiàn)［20］中證明了資源分配問題類似于最大裝箱問題，被認(rèn)為是NP（Non-deterministic Polynomial）難的。在博弈論中，所有的參與者進(jìn)行自我調(diào)節(jié)從而達(dá)到一種互相滿意的狀態(tài)，使得任何參與者都沒有動機(jī)單方面偏離，這能夠減輕實施更為復(fù)雜的集中式系統(tǒng)的負(fù)擔(dān)。假設(shè)在執(zhí)行任務(wù)期間移動設(shè)備數(shù)量不會變，并且考慮一個準(zhǔn)靜態(tài)場景，在一個時隙內(nèi)狀態(tài)不變，但在不同的時隙內(nèi)狀態(tài)是有所改變的。

2.1 博弈公式化

定義集合a-n=(a1，a2，…，an-1，an+1，…，aN)作為除移動設(shè)備n以外其他移動設(shè)備的任務(wù)遷移決策。當(dāng)給定其他設(shè)備的決策a-n，移動設(shè)備n選擇合適的策略an使得自身總成本開銷最小，即Cn(an，a-n)，?n∈N。Cn(an，a-n)是n的成本開銷函數(shù)，那么移動設(shè)備n總開銷定義為：

將問題轉(zhuǎn)化為博弈模型G=(N，{An}n∈N，{Cn}n∈N)，其中N 是移動設(shè)備集合，An是移動設(shè)備n的博弈策略集。接下來引入最佳響應(yīng)策略的概念，以更好地獲得所有設(shè)備的決策。

定義1給定了除移動設(shè)備n以外的其他設(shè)備的策略a-n，則移動設(shè)備n的最佳響應(yīng)策略為：

表明所選擇的an是可以最小化移動設(shè)備n成本開銷的決策。

將任務(wù)遷移到MEC 服務(wù)器上是否成本開銷會低于本地執(zhí)行的成本，很大程度取決于其受到的來自其他移動設(shè)備的干擾，從引理1 可以找到通過干擾閾值來判斷任務(wù)遷移到MEC服務(wù)器是否對移動設(shè)備是有益的。

引理1給定計算遷移博弈中除了移動設(shè)備n以外其他設(shè)備的策略a-n，如果n在所選的無線信道上（an≥1）所受到來自其他設(shè)備的干擾滿足Fn(a) ≤THn，那么n的遷移是可以降低成本開銷的，即稱移動設(shè)備n的遷移是有益的任務(wù)遷移，其中閾值THn滿足：

證明 在計算閾值時只需要考慮遷移到MEC 服務(wù)器的情況，而不需要考慮遷移到云服務(wù)器的情況，即yn=1。若要移動設(shè)備n的遷移是有益的遷移，必須滿足遷移到MEC 服務(wù)器的開銷成本小于本地執(zhí)行成本。根據(jù)式（3）和（4），以及可以得到：

根據(jù)數(shù)據(jù)速率公式可以得到：

即Fn(a)≤THn。

根據(jù)引理1 可知，當(dāng)n在無線信道上受到的干擾足夠小時，將任務(wù)遷移到MEC 服務(wù)器上的成本開銷會小于本地執(zhí)行開銷成本，即將任務(wù)遷移到MEC 服務(wù)器對移動設(shè)備來說是有益的，否則移動設(shè)備應(yīng)該在本地執(zhí)行任務(wù)。

當(dāng)移動設(shè)備的任務(wù)完成第一階段的決策遷移到MEC 后，需要決定其仍在MEC 執(zhí)行或是遷移到CCC 執(zhí)行，yn可以通過以下計算得到：

在博弈論中，納什均衡（Nash Equilibrium，NE）是分析多個非合作實體決策互動結(jié)果的重要解決方案。接下來首先引入納什均衡的概念。

定義2對于所有的移動設(shè)備，遷移策略集合a*=是非合作博弈G的一個納什均衡，當(dāng)且僅當(dāng)它是最佳響應(yīng)的固定點，即對于?an∈An，n∈N，有：

納什均衡具有自我穩(wěn)定的特性，這意味著沒有任何一個移動設(shè)備有動機(jī)單方面背離NE，因為移動設(shè)備無法通過采取不同于NE的策略來進(jìn)一步降低成本開銷。

2.2 博弈性質(zhì)

為了證明博弈G存在NE 并最終證明博弈的收斂性，接下來要引入勢博弈的概念。

定義3如果博弈G=(N，{An}n∈N，{Cn}n∈N)存在一個勢函數(shù)P，滿足：α=(a1，a2，…，an) →R，對?n∈N，an，有≤Cn(an，a-n)，那 么≤P(an，a-n)，則稱這個博弈為勢博弈。

已知勢博弈存在納什均衡并且具有有限的改進(jìn)特性，任何改進(jìn)過程都可以在有限次的改進(jìn)步驟后終止。因此只需要證明博弈G=(N，{An}n∈N，{Cn}n∈N)是勢博弈。

定義勢函數(shù)為：

其中：I{condition}是指示函數(shù)，條件為真則I{condition}=1，否則I{condition}=0。

定理1如果通過構(gòu)造勢函數(shù)將成本開銷最小化問題轉(zhuǎn)化為勢博弈，那么它在有限的改進(jìn)內(nèi)擁有至少一個納什均衡。

證明 首先將成本開銷最小化問題轉(zhuǎn)化為策略博弈。假設(shè)移動設(shè)備n要更新當(dāng)前策略an，并且存在決策使得Cn(，a-n)＜Cn(an，a-n)成立。根據(jù)勢博弈的定義，需要表明成本開銷減少的同時，勢函數(shù)也會變小，即P(a-n)＜P(an，a-n)。考慮下列3種情況：1）an＞0，＞0；2）an＞0，=0；3）an=0，＞0。

1）假設(shè)當(dāng)前移動設(shè)備n的策略是an＞0，更新其為＞0，即Cn(，a-n) ＜Cn(an，a-n)。那么有：

此時可得P(an，a-n) -P(，a-n) ＞0。

2）假設(shè)當(dāng)前移動設(shè)備n的策略是an＞0，更新其為=0，那么有：

由于an＞0 且=0，說明THn，所以有P(an，a-n) -P(，a-n) ＞0。

3）假設(shè)當(dāng)前移動設(shè)備n的策略是an=0，更新其為此時有因此可以得到

綜合以上三種情況可得，策略的改變所造成的成本開銷的減少會導(dǎo)致勢函數(shù)的減少。通過構(gòu)造勢函數(shù)P(a)可知博弈G是一個勢博弈，證明的關(guān)鍵在于移動設(shè)備n改變其當(dāng)前的策略an為更好的策略，使開銷成本減小的同時導(dǎo)致任務(wù)遷移博弈的勢函數(shù)變小。根據(jù)定理1 可得，對每個具有有限策略空間的勢博弈，都存在納什均衡。這意味著任何更新參與者策略并改善其成本開銷的算法都可以保證在有限時間內(nèi)達(dá)到納什均衡。

3 基于博弈論的兩階段任務(wù)遷移算法

本章設(shè)計基于博弈論的兩階段任務(wù)遷移算法（Game Theory-Two Stages Task Offloading，GT-TSTO）。在第一階段移動設(shè)備決定任務(wù)本地執(zhí)行還是遷移到MEC 服務(wù)器執(zhí)行，第二階段是遷移至MEC 之后要決定是MEC 繼續(xù)執(zhí)行還是遷移到CCC執(zhí)行。

3.1 算法設(shè)計與描述

通過迭代更新移動設(shè)備n的最佳響應(yīng)策略，在每一次迭代的過程中，移動設(shè)備n通過計算求得使成本開銷最小的策略作為最佳響應(yīng)策略，從而來響應(yīng)其他移動設(shè)備的策略。MEC 服務(wù)器可以計算出傳輸速率，并傳送給移動設(shè)備。由定義2 可知，如果最佳響應(yīng)算法是收斂的，那么所有移動設(shè)備最佳響應(yīng)策略的固定點集是博弈G的納什均衡；但是收斂時間是隨著移動設(shè)備的數(shù)量呈指數(shù)增長的。為了能夠獲得結(jié)果令人滿意的遷移決策，GT-TSTO算法被設(shè)計實現(xiàn)納什均衡。

GT-TSTO 算法是一個分布式的任務(wù)遷移算法，系統(tǒng)的基站是可以時間同步的，可以通過基站時間來同步所有移動設(shè)備的操作。當(dāng)移動設(shè)備想要更新決策時，它們向基站廣播其參數(shù)。算法進(jìn)行比較后允許其中一個開銷成本最小的設(shè)備獲得更新決策的機(jī)會。經(jīng)過多次迭代后，所有移動設(shè)備的遷移決策達(dá)到穩(wěn)定狀態(tài)，此時達(dá)到開銷最小化的納什均衡。

在每一個準(zhǔn)靜態(tài)場景下的決策時隙內(nèi)，每一個移動設(shè)備都會依據(jù)自己的策略是否更新來決定是否發(fā)送更新請求消息（Request Update，RU）。RU 表明每個移動設(shè)備都想競爭更新決策（Update，UP）的機(jī)會來改善當(dāng)前決策。假設(shè)移動設(shè)備n贏得了決策機(jī)會，則n選擇一個最佳響應(yīng)決策作為更新決策，最小化自身的成本開銷。在有限次的迭代后，所有的移動設(shè)備達(dá)到了相互平衡的狀態(tài)，即納什均衡。

具體地，GT-TSTO算法的運行過程有以下幾個步驟。

1）無線干擾測量。移動設(shè)備可以從基站獲得相關(guān)信道的信息，在每個給定的決策時隙t內(nèi)計算當(dāng)前的無線信道干擾和傳輸速率。對每一個的移動設(shè)備n，它們在自己選擇的信道向無線基站發(fā)送信道信號，無線基站測量每個信道的總接收功率Pk(a(t))，這樣移動設(shè)備n可以得到自身所收到的無線信道干擾。無線信道干擾可以通過公式計算：

2）遷移決策更新。根據(jù)不同信道上測量出的信道干擾Θn(k，a-n(t))計算移動設(shè)備的最佳響應(yīng)集其中

之后，GT-TSTO算法進(jìn)入下一個循環(huán)，直到?jīng)]有移動設(shè)備在下一個決策時隙中找到當(dāng)前的最佳遷移決策，并且經(jīng)過有限次的迭代后，所有移動設(shè)備都將達(dá)到納什均衡的狀態(tài)，循環(huán)才會結(jié)束。最后可以根據(jù)所有移動設(shè)備的最終遷移決策列表計算出最小的總能耗。

具體算法描述如下：

算法1 基于博弈論的兩階段任務(wù)遷移算法（GT-TSTO）。

輸入 移動設(shè)備n的計算任務(wù)an，傳輸功率pn以及其他初始數(shù)據(jù)。

輸出 移動設(shè)備最優(yōu)決策集Sa、Sy和系統(tǒng)總成本開銷Ctotal。

初始化 設(shè)置初始決策槽t=0；移動設(shè)備n的決策結(jié)果an(0)=0。

根據(jù)勢博弈的有限改進(jìn)屬性，本算法可以在有限次的迭代決策后收斂到納什均衡。在仿真實驗中，在MEC 服務(wù)器未接收到RU 消息時可以終止任務(wù)遷移決策更新過程。這時MEC 服務(wù)器向所有移動設(shè)備廣播終止信息，并且每一個移動設(shè)備根據(jù)最后的決策時隙內(nèi)所獲得的決策來執(zhí)行任務(wù)。

在每個決策時隙內(nèi)，移動設(shè)備會并行執(zhí)行算法1中的2）～14）行的操作。盡管GT-TSTO 算法只能為云邊協(xié)作下的任務(wù)遷移提供近乎最優(yōu)的解決方案，但由于是隨機(jī)選取移動設(shè)備更新決策，這會使得算法擁有更高的計算效率。本算法主要涉及K個無線信道測量數(shù)據(jù)的排序操作，所以每一個決策時隙內(nèi)的計算復(fù)雜度為O(KlgK)，假設(shè)算法達(dá)到納什均衡需要I次迭代，那么本文的分布式任務(wù)遷移算法的總計算復(fù)雜度為O(IKlgK)。

3.2 性能分析

GT-TSTO算法性能通過研究策略博弈的重要性能指標(biāo)來分析——納什均衡的整體性能和最優(yōu)配置相差多少？通過PoA（Price of Anarchy）來量化這種差異，它反映了自私個體基于自身利益自由選擇策略對整體利益的影響程度，PoA 值的大小可以用來衡量納什均衡的性能。PoA 定義為在納什均衡中獲得的最差社會成本和全局最優(yōu)策略方案所獲得的最小社會成本之間的比率。

社會成本被定義為所有移動設(shè)備的總成本開銷，即：

PoA可以被定義為：

無線通道數(shù)量增加，可以減少來自干擾用戶的干擾，PoA減小，這表明減少干擾時可以提高NE的性能。而當(dāng)移動設(shè)備本地成本較低時，最差的納什均衡接近于集中式最優(yōu)解決方案，此時的PoA也較低。

4 實驗仿真

為了評估所提的云邊協(xié)同任務(wù)遷移方案的性能，本章將展示通過仿真實驗所產(chǎn)生的數(shù)值結(jié)果。在不失一般性的情況下，本文采用光纖無線混合網(wǎng)絡(luò)下集中式云服務(wù)器和MEC 協(xié)同方案。

假設(shè)每個MEC具有30個正交信道頻率資源，這意味著它最多可以同時服務(wù)30 個移動設(shè)備，并且其信道帶寬設(shè)置為5 MHz，每個基站信道數(shù)為5，同時在MEC 的覆蓋范圍內(nèi)隨機(jī)分配15～50 個移動設(shè)備。此外，移動設(shè)備的傳輸功率設(shè)置為2 W，背景噪聲設(shè)置為-80 dBm，信道增益取值為0.7～0.9，計算的數(shù)據(jù)大小為｛500，1 000，1 500，2 000｝KB，第二階段所需等待時間設(shè)置為0.1～2 s，任務(wù)所需的CPU 周期數(shù)隨機(jī)分布為｛1 000，2 000，3 000，4 000｝Mega cycles，MEC 和CCC 的計算能力分別為10 GHz和20 GHz，移動設(shè)備的計算能力隨機(jī)分布為｛0.5，0.8，1.0｝GHz。MEC 與CCC 的數(shù)據(jù)傳輸率為15 Mb/s，能量負(fù)載因子隨機(jī)分布于｛0，0.2，0.5，0.8，1.0｝，相應(yīng)的時間負(fù)載因子為1-

圖1 展示了有益任務(wù)遷移狀態(tài)的移動設(shè)備數(shù)動態(tài)變化的過程。從圖1 可見，隨著迭代次數(shù)增加，移動設(shè)備根據(jù)信道信息不斷調(diào)整任務(wù)遷移策略，使得處于有益遷移狀態(tài)的移動設(shè)備數(shù)也在增加，并最終達(dá)到穩(wěn)定狀態(tài)，說明GT-TSTO 算法可以在有限次數(shù)的迭代內(nèi)達(dá)到納什均衡。

圖1 有益任務(wù)遷移狀態(tài)的移動設(shè)備數(shù)變化Fig.1 Change of the number of mobile devices with beneficial task offloading status

圖2 展示了多個移動設(shè)備在本文所提的云邊環(huán)境下基于非合作博弈的任務(wù)遷移成本開銷變化情況，每一條折線代表一個移動設(shè)備從初始到達(dá)到納什均衡的成本開銷實時變化曲線。由于本仿真中MEC可以最多同時服務(wù)30個移動設(shè)備，所以初始設(shè)置了30個移動設(shè)備同時進(jìn)行任務(wù)遷移。

圖2 不同移動設(shè)備的成本開銷Fig.2 Overhead of different mobile devices

從圖2 可以看出每個移動設(shè)備的開銷隨著迭代次數(shù)的增加而變化，最終趨于穩(wěn)定，這說明此時已達(dá)到納什均衡，而且對于單個移動設(shè)備來說，迭代過程中遷移決策是不斷變化的，這是移動設(shè)備作為博弈方所進(jìn)行的遷移決策調(diào)整。因此在達(dá)到納什均衡之前，移動設(shè)備的成本開銷是不規(guī)則變化的，達(dá)到納什均衡后開銷保持恒定，但不同移動設(shè)備間的成本開銷是不同的。此時可以證明博弈G是收斂的，納什均衡存在且唯一。從圖2 可得出結(jié)論，與初始值相比，納什均衡下的移動設(shè)備總開銷減少了，這表明云邊環(huán)境下基于博弈論的任務(wù)遷移方法是可以有效減少開銷的。

圖3 是不同數(shù)量的移動設(shè)備達(dá)到納什均衡所需的迭代次數(shù)。隨著移動設(shè)備數(shù)的增加，達(dá)到納什均衡需要的迭代次數(shù)也線性增加，這說明本文所提出的云邊環(huán)境下的GT-TSTO 算法有較好的性能。

圖3 不同數(shù)量移動設(shè)備達(dá)到納什均衡的迭代次數(shù)Fig.3 Number of iterations for different numbers of mobile devices to reach Nash equilibrium

圖4 將GT-TSTO 算法在不同移動設(shè)備數(shù)的情況下獲得的最小總成本開銷，與本地計算、無排隊等待的MEC 計算和中心云計算進(jìn)行對比。所有移動設(shè)備的總成本開銷都會隨著移動設(shè)備數(shù)的增加而增加，但與本地計算與云計算相比，MEC計算和云邊協(xié)作計算都可以實現(xiàn)更少的成本開銷，而云邊協(xié)作計算性能更好，這驗證了GT-TSTO 算法能夠有效減少總成本開銷。當(dāng)移動設(shè)備數(shù)為30 時，所提算法所產(chǎn)生的總開銷為147，而本地執(zhí)行、云中心服務(wù)器執(zhí)行和MEC 執(zhí)行的移動設(shè)備總成本開銷分別為540、281和151，因此可以得到云邊環(huán)境下進(jìn)行任務(wù)遷移分別比本地執(zhí)行、云中心服務(wù)器執(zhí)行和MEC 服務(wù)器執(zhí)行降低了72.8%、47.9%和2.65%。由于MEC 的可用計算資源不足以滿足那些需要較多計算資源的任務(wù)，以上這些結(jié)果驗證了在MEC 環(huán)境中引入集中式云計算進(jìn)行任務(wù)遷移的必要性。

圖4 采用不同的任務(wù)遷移方案的總開銷的比較Fig.4 Comparison of total overhead using different task offloading schemes

5 結(jié)語

本文研究了云邊協(xié)作任務(wù)遷移問題，以最大限度降低遷移開銷為優(yōu)化目標(biāo)，提出了在云邊協(xié)作環(huán)境下基于博弈論的兩階段任務(wù)遷移方案，以獲得最佳遷移策略。通過本算法可以有效降低成本開銷，產(chǎn)生成本效益，而且能夠?qū)崿F(xiàn)更低的能耗。但本文研究仍存在不足，目前僅考慮單MEC 服務(wù)器與云服務(wù)器協(xié)同，而未考慮到多MEC 服務(wù)器與云服務(wù)器協(xié)同的復(fù)雜任務(wù)遷移情況。今后會深入研究多MEC 服務(wù)器與云服務(wù)器協(xié)作任務(wù)遷移，進(jìn)一步降低能耗，減少任務(wù)遷移的成本開銷。