王藝潔，凡佳飛，王陳宇

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

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

0 引言

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

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

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

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

1 系統(tǒng)模型

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

1.1 通信模型

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

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

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

2是背景噪聲功率。

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

1.2 任務遷移博弈計算模型

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

1.2.1 本地計算模型

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

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

1.2.2 MEC計算模型

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

1.2.3 CCC計算模型

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

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

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

2 任務遷移博弈

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

2.1 博弈公式化

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

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

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

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

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

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

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

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

即Fn(a)≤THn。

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

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

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

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

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

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)，則稱這個博弈為勢博弈。

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

定義勢函數(shù)為：

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

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

證明 首先將成本開銷最小化問題轉(zhuǎn)化為策略博弈。假設移動設備n要更新當前策略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）假設當前移動設備n的策略是an＞0，更新其為＞0，即Cn(，a-n) ＜Cn(an，a-n)。那么有：

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

2）假設當前移動設備n的策略是an＞0，更新其為=0，那么有：

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

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

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

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

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

3.1 算法設計與描述

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

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

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

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

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

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

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

具體算法描述如下：

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

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

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

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

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

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

3.2 性能分析

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

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

PoA可以被定義為：

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

4 實驗仿真

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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