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

王藝潔，凡佳飛，王陳宇

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

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

0 引言

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

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

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

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

1 系統(tǒng)模型

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

1.1 通信模型

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

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

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

2是背景噪聲功率。

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

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

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

1.2.1 本地計(jì)算模型

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

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

1.2.2 MEC計(jì)算模型

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

1.2.3 CCC計(jì)算模型

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

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

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

2 任務(wù)遷移博弈

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

2.1 博弈公式化

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

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

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

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

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

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

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

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

即Fn(a)≤THn。

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

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

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

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

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

2.2 博弈性質(zhì)

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

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

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

定義勢(shì)函數(shù)為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體地，GT-TSTO算法的運(yùn)行過程有以下幾個(gè)步驟。

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

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

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

具體算法描述如下：

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

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

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

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

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

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

3.2 性能分析

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

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

PoA可以被定義為：

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

4 實(shí)驗(yàn)仿真

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

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

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

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

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

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

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

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

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

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