鮮永菊，宋青蕓，郭陳榕，劉 闖

(重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065)

E-mail：xianyj@cqupt.edu.cn

1 引 言

移動邊緣計算(Mobile Edge Computing，MEC)技術(shù)通過將云數(shù)據(jù)中心下沉至靠近數(shù)據(jù)源端的接入網(wǎng)一側(cè)，能夠近距離為用戶提供計算、通信、存儲等能力，同時使得移動網(wǎng)絡(luò)傳輸成本更低、效率更高、應(yīng)用復(fù)雜度不受終端的限制[1-3]，在AR/VR、物聯(lián)網(wǎng)(Internet of Things，IoT)、車聯(lián)網(wǎng)等場景中有著廣闊的應(yīng)用前景.計算卸載技術(shù)作為MEC中十分重要的一環(huán)[4]，為移動用戶帶來了海量計算能力，拓展了用戶處理任務(wù)的能力.

鑒于此，眾多學(xué)者針對計算卸載展開了研究，其中卸載策略和資源分配是研究重點.Chouhan與Nguyen等人采用部分卸載劃分計算任務(wù)，使任務(wù)同時在多端進(jìn)行計算，相較于二元卸載，多端并行計算帶來了效率的提升[5，6]；Qin等人通過博弈理論對單用戶多MEC問題建模[7]，為單個用戶提供了多種卸載選擇；在Qin等人方案的基礎(chǔ)上，Yi等人提出的卸載方案，更加適合時延敏感場景[8]；另外，Zhang等人通過結(jié)合機(jī)器學(xué)習(xí)完成了信道和計算資源的分配，并分析了多種分類器學(xué)習(xí)效果上的差異[9].還有學(xué)者聯(lián)合卸載策略與資源分配提出方案，其中Ren等人考慮了隨機(jī)任務(wù)到達(dá)模型，提出JCRM方案，以提高長期網(wǎng)絡(luò)的穩(wěn)定性[10]；Hu等人為任務(wù)執(zhí)行過程中的能耗問題提出了解決方案，并設(shè)計基于方向交叉的遺傳算法，完成聯(lián)合優(yōu)化問題[11].由于資源分配與任務(wù)卸載往往是緊密聯(lián)系的，因此與單獨的卸載策略或資源分配的方案相比，聯(lián)合方案往往能獲得更佳的效果.

現(xiàn)有的工作大多都假設(shè)MEC計算資源是足夠的，請求卸載的任務(wù)都可以在滿足約束條件下完成計算卸載，MEC服務(wù)器不擔(dān)心出現(xiàn)性能瓶頸.但隨時間發(fā)展，由基站硬件成本限制所導(dǎo)致MEC服務(wù)器計算資源有限的問題將日漸明顯，尤其在商圈，機(jī)場等任務(wù)請求密集的網(wǎng)絡(luò)中，MEC服務(wù)器提供的計算資源往往不足以應(yīng)對大量請求任務(wù)[4].現(xiàn)有的一些卸載方案，在計算資源不足時會導(dǎo)致用戶需求無法滿足，引發(fā)多用戶競爭有限的MEC計算資源產(chǎn)生“死鎖”問題[12]，導(dǎo)致卸載用戶數(shù)量下降；同時，在資源不足時，已有方案獲得的系統(tǒng)效益往往較差.為改善這些的問題，Ning等人與Wu等人的方案均通過多MEC協(xié)作的方式擴(kuò)展計算資源[13，14]，將MEC無法完成的任務(wù)通過二次卸載的方式，交給其他仍有計算資源的MEC執(zhí)行，但多MEC協(xié)作實際需滿足的條件十分苛刻，實際的應(yīng)用價值不大；Liu等人提出一種卸載方案，在MEC沒有額外計算資源可用時，通過價格制約卸載的方式保證最大化自身收益，并提出了兩種定價策略，比較了方案之間的差異[15]；Zhao等人考慮任務(wù)主動緩存的方案[16]，這種方案可以緩存熱點計算任務(wù)，當(dāng)同類任務(wù)請求時，可以快速響應(yīng)且不占用MEC計算資源，這樣可有效改善熱點任務(wù)的計算，但隨著任務(wù)種類的增多，緩存策略帶來的收益將十分有限.

基于上述存在的問題，本文通過聯(lián)合價格約束卸載與計算資源分配的方式，在計算資源受限MEC中實現(xiàn)總收益最大化.主要的工作有以下幾個方面：

1) 在計算資源受限MEC中通過調(diào)整價格制約任務(wù)卸載，并通過Stackelberg博弈建模于MEC與用戶之間的交互.在博弈模型分析中，將最大化MEC系統(tǒng)收益的聯(lián)合優(yōu)化問題分解為多個子問題.

2) 針對上述問題，為計算資源有限MEC提出了一種差異化定價方法，并在此基礎(chǔ)上通過多任務(wù)卸載算法完成了任務(wù)卸載.

3) 提出了一種改進(jìn)模擬退火算法用于計算資源分配，算法通過控溫策略保證廣度搜索能力，通過資源重分配保證深度搜索能力.

2 系統(tǒng)模型

考慮在任務(wù)密集區(qū)域(如商圈，機(jī)場，學(xué)校等)的多用戶單MEC網(wǎng)絡(luò)，在一個卸載周期內(nèi)，有大量用戶通過無線鏈路請求計算卸載，區(qū)域內(nèi)的MEC服務(wù)器負(fù)責(zé)接收請求的計算任務(wù)，完成計算后，將計算結(jié)果返回用戶端.為簡化問題，假設(shè)每個用戶只請求一個計算任務(wù)，任務(wù)可以按位任意劃分，使得任務(wù)可以在本地與MEC端并行運算.另外，假設(shè)卸載過程中每個用戶擁有相同的信道帶寬，且每個用戶的信道占用不重疊的頻率以同時將數(shù)據(jù)卸載到MEC服務(wù)器上，任務(wù)卸載時考慮準(zhǔn)靜態(tài)信道模型，信道在卸載周期內(nèi)保持恒定不變，但可以在不同任務(wù)的卸載周期間發(fā)生變化，并假設(shè)卸載任務(wù)將在一定時間內(nèi)完成計算.

以N={1，2，…，N}表示N個用戶的集合，用戶i的任務(wù)通過二元組Ti(bi，di)表示，其中bi表示任務(wù)的總數(shù)據(jù)量，di表示計算1bit該任務(wù)數(shù)據(jù)所需要的CPU周期數(shù)；用戶i卸載任務(wù)數(shù)據(jù)量的比例為λi，λi∈[0，1]，即λibi數(shù)據(jù)量的任務(wù)會被卸載到MEC服務(wù)器進(jìn)行計算，使用集合V={λ1，λ2，…，λN}表示N個用戶卸載比例集合.用戶本地計算能力為floc，i，MEC服務(wù)器為多任務(wù)提供有限的計算資源fmec，使用集合W={fmec，1，fmec，2，…，fmec，N}表示MEC為N個用戶分配的計算資源集合.

為了確保卸載至MEC的任務(wù)可以在卸載周期內(nèi)完成計算，現(xiàn)考慮一個實際的限制條件：設(shè)定MEC服務(wù)器在每個卸載周期內(nèi)用于計算接收數(shù)據(jù)的總CPU周期上限為F[15]，設(shè)定F可以確保在計算資源不足的情況下有序地處理到來的任務(wù)，F(xiàn)值越大，對應(yīng)的卸載周期越長.該約束條件為：

∑Ni=1λidibi≤F

(1)

需要注意這里的F和fmec分別是MEC服務(wù)器對于卸載CPU周期的總量與計算頻率上限.

首先考慮用戶與MEC之間的通信，任務(wù)的上傳速率為：ri=Blog2(1+Ptra，igi/BNo)，其中Ptra，i表示用戶i的發(fā)送功率，gi表示用戶i與MEC服務(wù)器之間的信道增益，No表示信道單位噪聲與干擾的功率譜密度.

其次，當(dāng)任務(wù)卸載時，用戶i本地執(zhí)行部分任務(wù)花費的時間為：tloc，i=(1-λi)bidi/floc，i；任務(wù)在MEC服務(wù)器端計算部分任務(wù)花費的時間為：tmec，i=ttra，i+texe，i，其中ttra，i=λibi/ri，表示用戶向MEC上傳任務(wù)產(chǎn)生的時延，texe，i=λibidi/fmec，i代表任務(wù)在MEC端的執(zhí)行產(chǎn)生的時延；由于MEC向用戶回傳的計算結(jié)果數(shù)據(jù)量很小，因此回傳時間忽略不計.最終用戶i完成任務(wù)總時延為：

ti=max(tloc，i，tmec，i)

(2)

最后，用戶i在本地執(zhí)行部分任務(wù)消耗的能量為：eloc，i=κibidi(1-λi)(floc，i)2，其中κi是與移動用戶的硬件架構(gòu)相關(guān)的常數(shù)；用戶i向MEC服務(wù)器發(fā)送任務(wù)需要的能耗為：etra，i=Ptra，i·ttra，i=λiPtrabi/ri.最終用戶i完成該任務(wù)的總能耗為：

ei=etra，i+eloc，i

(3)

3 優(yōu)化問題分析及求解

3.1 Stackelberg博弈分析

在MEC任務(wù)執(zhí)行過程中，用戶占用了MEC服務(wù)器的計算資源來處理任務(wù)，而MEC服務(wù)器必須確保其用于計算總卸載數(shù)據(jù)的可用CPU周期低于F.為了調(diào)整計算資源的需求和供給，MEC服務(wù)器可對每個用戶i的卸載數(shù)據(jù)的CPU周期bidi收費，以出售自身有限的資源.

對此，Stackelberg博弈可用于建模MEC與用戶之間的交互，Stackelberg博弈模型是一種產(chǎn)量領(lǐng)導(dǎo)模型，可以反應(yīng)非對稱競爭關(guān)系，并將競爭者角色定為領(lǐng)導(dǎo)者與跟隨者.本文將MEC服務(wù)器視為領(lǐng)導(dǎo)者，而用戶視為跟隨者.領(lǐng)導(dǎo)者先對跟隨者的CPU周期制定價格；然后，跟隨者將依據(jù)領(lǐng)導(dǎo)者制定的價格，獨立計算其用于卸載的CPU周期，以分別進(jìn)行本地計算和卸載.

將MEC給用戶i單位CPU周期的價格定義為μi，U={μ1，μ2，…，μN(yùn)}表示所有用戶的單價集合，MEC最大化收益問題表示為(主問題)：

P1：maxQ(U，V，W)=∑Ni=1μiλidibi

s.t. C1：μi>0

C2：∑Ni=1fmec，i≤fmec

C3：∑Ni=1λidibi≤F

(4)

式(4)中約束條件C1確保MEC服務(wù)器提供的價格為正數(shù)，C2確保MEC在并行運算時為每個用戶分配的頻率不大于總頻率，C3確保MEC接收CPU總周期小于上限值.對于用戶而言，其主要目的是降低完成任務(wù)所需要付出的成本.成本由完成任務(wù)付出的時延、能耗以及費用的加權(quán)和表示[15].這個問題表示為(從問題)：

P2：minUi(λi)=αiti+βiei+γiμiλidibi

s.t. C1：0≤λi≤1

C2：αi+βi+γi=1

(5)

其中αi、βi和γi分別表示用戶i對于執(zhí)行任務(wù)產(chǎn)生的時延、能耗以及費用成本的權(quán)重，不同用戶權(quán)重不同.Stackelberg博弈中的問題P1和P2以一種復(fù)雜的方式耦合在一起，即MEC的定價策略與資源分配會影響用戶的卸載，而用戶卸載又會反過來影響邊緣云的收益.

考慮問題中MEC與用戶之間的博弈，每個用戶都可通過給定價格μi以及fmec，i求解問題P2，獨立決定其卸載比例.知道了每個用戶的卸載比例，MEC通過求解問題P1來設(shè)置其最佳單價集合U、卸載比例集合V以及資源分配集合W，以上過程稱為逆向歸納.由于問題是多目標(biāo)優(yōu)化，為降低求解難度，將原問題分為3個子問題，分別求解定價策略、卸載策略以及資源分配問題.

3.2 差異化定價策略

本節(jié)分析MEC的定價策略，假設(shè)分配給用戶i的fmec，i已知.先分析跟隨者的行為，根據(jù)式(5)，用戶i的總成本可寫為λi的分段函數(shù)：

Ui=(γiμidi+βiPtra，iri-βiκidif2loc，i-
αidifloc，i)λibi+αidibifloc，i+βiκibidif2loc，i0≤λi≤φi
(γiμidi+αiri+αidifmec，i+βiPtra，iri-
βiκidif2loc，i)λibi+βiκibidif2loc，iφi<λi≤1

(6)

其中φi=1/(1+floc，i/diri+floc，i/fmec，i)，是在區(qū)間[0，1]內(nèi)的一個卸載比例.公式(6)的前半段表示用戶在本地計算的時延較長，后半段表示卸載至MEC服務(wù)器的計算時延較長.當(dāng)λi=φi時表示本地與卸載計算時延相等.為了求解P2，對Ui一階求導(dǎo)，可得卸載比例與單價的關(guān)系，由(7)式給出：

λi=10≤μi≤G1，i
φiG1，i<μi≤G2，i
0G2，i<μi

(7)

此時得到的λi為用戶i的最佳卸載比例，用戶將根據(jù)該比例卸載任務(wù)，其中：

G1，i=-βiPtra，iγiridi+βiκif2loc，iγi-αiγiridi-αiγifmec，i

(8)

G2，i=-βiPtra，iγiridi+βiκif2loc，iγi+αiγifloc，i

(9)

此外，式(7)將作為博弈中的反應(yīng)函數(shù)，被領(lǐng)導(dǎo)者觀察到.

接著分析MEC服務(wù)器行為，領(lǐng)導(dǎo)者根據(jù)觀察到的反應(yīng)函數(shù)調(diào)整μi，MEC的定價策略由定理1給出：

定理1.為使收益最大化，計算資源受限MEC需將μi定為G2，i或正無窮.

證明：為了最大化MEC系統(tǒng)的利潤，MEC服務(wù)器應(yīng)在保證用戶卸載量不變的情況下，盡可能提高售價，因此MEC服務(wù)器應(yīng)將單價定在反應(yīng)函數(shù)每個分段右界.當(dāng)滿足式(7)第1段時，μi應(yīng)為G1，i，此時單價較小，用戶全部卸載；同理，當(dāng)滿足第2段時，μi應(yīng)為G2，i，此時單價較大，用戶的卸載比例為φi；當(dāng)定價位于第3段時，μi應(yīng)為正無窮，此時用戶不卸載.顯然，定價為G1，i不適合計算資源有限系統(tǒng)；同時，在信道資源充足時，用于傳輸任務(wù)的能耗將小于本地計算該任務(wù)帶來的能耗[11]，因此G2，i為正數(shù)，保證了定價的合理性.故計算資源受限MEC應(yīng)將價格定在G2，i或無窮高.

證畢

3.3 多用戶卸載策略

定價策略決定后，MEC需限制多用戶卸載的總CPU周期小于F，通過引入二進(jìn)制決策變量集合x用來表示用戶的卸載決策：

λi=φixi

(10)

其中二進(jìn)制數(shù)xi定義為：

xi=0G2，i<μi
10≤μi≤G2，i

(11)

此時問題P1被重寫為：

P3：maxQ(x，U)=∑Ni=1μiφixibidi

s.t. C1：∑Ni=1φixidibi≤F

(12)

根據(jù)定理1，當(dāng)xi=1時，最優(yōu)價格由G2，i給出.最優(yōu)價格與用戶任務(wù)的信息相關(guān)，這些信息可以在當(dāng)用戶向MEC服務(wù)器發(fā)起卸載請求時獲取.問題P3可轉(zhuǎn)化為：

P3′：maxQ(x)=∑Ni=1G2，iφixibidi

s.t. C1：∑Ni=1φixidibi≤F

(13)

問題P3′可等效為重量為φibidi，價值為G2，iφibidi，重量限制為F的非整數(shù)二元背包問題，該問題是NP-complete的.對問題的求解分為兩步，首先設(shè)置一個較大的步長Fd，將重量與F進(jìn)行近似處理，將非整數(shù)0-1背包問題轉(zhuǎn)化為整數(shù)0-1背包問題，同時減小了問題的規(guī)模；接著，通過動態(tài)規(guī)劃思想對問題求解，多用戶卸載決策算法實現(xiàn)步驟如下所示.

算法1.多用戶卸載決策算法

輸入：用戶集N，定價策略集G2，CPU周期上限為F，步長Fd

初始化：L=F/Fd；

fori=1：N

forj=1：L

if(j<φibidi/Fd)

V(i，j)=V(i-1，j)；

else

if(V(i-1，j)>V(i-1，j-φibidi/Fd)+G2，iφibidi)

V(i，j)=V(i-1，j)；

else

V(i，j)=V(i-1，j-φibidi)+G2，iφibidi；

end if

end if

end for

end for

最大收益Q*=V(N，L)

輸出：最大收益Q*，卸載決策變量x

3.4 基于模擬退火思想的計算資源分配

3.2節(jié)與3.3節(jié)中的定價策略以及卸載策略均是在計算資源分配已告知用戶的條件下得出的，接下來分析計算資源分配問題.

計算資源分配的難點在于多任務(wù)決策變量與資源分配變量是耦合在一起的.一方面決策變量需要計算資源分配的結(jié)果；另一方面，MEC實際只需為決策變量x中值為1的用戶分配計算資源，資源分配同樣依賴決策變量的結(jié)果.由于以上原因，本文通過模擬退火算法隨機(jī)尋優(yōu)的方式完成計算資源分配.模擬退火算法是依靠隨機(jī)數(shù)方法迭代求解的尋優(yōu)算法，伴隨著算法中溫度不斷下降，解狀態(tài)會逐漸穩(wěn)定，這個過程中有概率發(fā)生突跳，使得解狀態(tài)重新進(jìn)入不穩(wěn)定狀態(tài).

在最大化收益問題中，由于部分用戶不卸載，MEC服務(wù)器不需要為這些用戶分配計算資源，其計算資源分配應(yīng)為0.含0計算資源分配解極易導(dǎo)致模擬退火算法陷入局部最優(yōu)解[17]，并很難在有限的迭代中跳出局部最優(yōu)解.為解決該問題，對模擬退火算法做出兩點改進(jìn)：

1) 計算資源集合W作為算法的解狀態(tài)，算法中決策變量確定后，需對決策變量中值為1的用戶進(jìn)行計算資源重分配，通過求解凸優(yōu)化問題解決.

2) 算法加入控溫策略，并且算法只考慮基于溫度的單層循環(huán)，當(dāng)溫度下降至小于1，算法停止.

改進(jìn)1)可確保解的精度，假設(shè)根據(jù)卸載策略確定卸載的用戶集合M={1，2，…，M}，j∈M代表其中第j個用戶，W′={fmec，1，fmec，2，…，fmec，M}表示M個用戶的計算資源的集合.此時用戶j將以卸載比例φj卸載任務(wù)，問題P1可重寫為：

P4：maxQ(W′)=∑Mj=1μj11+floc，jdjrj+floc，jfmec，jbjdj

s.t. C1：μj>0

C2：∑Mj=1fmec，j=fmec

C3：∑Mj=111+floc，jdjrj+floc，jfmec，jbjdj≤F

(14)

優(yōu)化問題P4是分?jǐn)?shù)規(guī)劃問題，對其進(jìn)行變量替換，令Yj=fmec，j/[(1+floc，j/rjbj)fmec，j+floc，j]，同時令Zj=1/[(1+floc，j/rjbj)fmec，j+floc，j]，得到集合Y={Y1，Y2，…，YM}.將原問題P4轉(zhuǎn)化為：

P4′：maxQ(Y)=∑Mj=1μjbjdjYj

s.t. C1：μj>0

C2：∑Mj=1Yj=Zjfmec

C3：∑Mj=1Yjbjdj≤F

(15)

C4：Zj≥0

C5：(1+floc，jrjdj)Yj+floc，jZj=1

問題P4′的函數(shù)式與約束條件均為凸函數(shù)，所以問題P4′是一個凸優(yōu)化問題，考慮到約束條件里有不等式約束，可通過內(nèi)點法對其求解[18].

改進(jìn)2)可降低算法搜索次數(shù)，同時增加算法解空間的廣度搜索能力.只考慮基于溫度的單層循環(huán)，將大幅減少迭代次數(shù)，但這并沒有丟失模擬退火算法的核心思想.

此外，根據(jù)Metropolis準(zhǔn)則，當(dāng)前解向一次較差解的移動的概率隨著溫度的變化而變化，根據(jù)這一特征，算法從較大的溫度開始，采用相對平緩的溫度下降公式Tk=Tk-1×η，(η為降溫系數(shù))保證了算法開始有較大的概率接受差解.控溫策略是當(dāng)解沒有更新時，以Tk/2T0>random[0，1)的概率保持溫度不變，保持算法接受較差解的概率，提高算法的廣度搜索能力.改進(jìn)模擬退火算法的具體步驟如下所示.

算法2.改進(jìn)模擬退火算法

輸入：用戶信息，初始資源分配集合W0，初始溫度T0

初始化：k←0，σ0←0；

repeat

k←k+1；

While (true)

隨機(jī)產(chǎn)生置亂集合σk；

Wk←Wk-1+σk；

if (Wk內(nèi)元素滿足約束C2)

break；

end if

end while

根據(jù)定理一得到單價集合Uk，多用戶卸載決策算法得到xk；

對xk中值為1的用戶通過求解凸優(yōu)化得到計算資源集W′k；

計算目標(biāo)函數(shù)q′；

根據(jù)Metropolis準(zhǔn)則與控溫策略調(diào)整解狀態(tài)Wk，溫度Tk.

if (q′>q)

Wbest←W′k，q←q′；

end if

untilT≤1

輸出：資源分配Wbest，總收益q

伴隨著溫度下降，算法在每次迭代中，首先通過隨機(jī)置亂產(chǎn)生一組資源分配變量；接著根據(jù)公式(9)以及算法1多用戶卸載決策算法得到卸載決策變量；最后通過求解(15)式的凸優(yōu)化問題完成計算資源再分配.直至溫度下降小于1，迭代結(jié)束，否則更新資源分配變量進(jìn)入下一次迭代.

根據(jù)控溫策略與溫度下降公式，溫度可在常數(shù)時間內(nèi)下降至1，即迭代次數(shù)k為常數(shù)；多用戶卸載決策算法需要遍歷整個二維數(shù)組，時間復(fù)雜度為O(NL)；解向量更新的時間復(fù)雜度為O(N).故改進(jìn)模擬退火算法總的時間復(fù)雜度為O(kNL+kN).

4 仿真分析

本文仿真分析基于MATLAB平臺，參考文獻(xiàn)[15]的仿真參數(shù)設(shè)置：信道總帶寬B=1MHz，信道噪聲與干擾的功率譜密度為-174dBm/HZ，信道增益在 [-50，-30]dBm內(nèi)均勻分布.用戶i本地的CPU頻率floc，i在[0.1，1]GHz中隨機(jī)取值；任務(wù)的數(shù)據(jù)大小bi在 [100，500]KB中隨機(jī)取值；單位任務(wù)計算量di在[500，1500]cycles/bit中隨機(jī)取值.默認(rèn)狀態(tài)下，算法的初始溫度為40，用戶數(shù)量N=40，用戶i的發(fā)射功率Ptra，i=0.1W，系數(shù)κ=10-27， MEC服務(wù)器提供的CPU頻率fmec=100GHz，CPU周期上限為F=6×109cycles/slot，降溫系數(shù)η=0.97.

首先驗證本文對模擬退火算法的改進(jìn)對問題解的影響，圖1、圖2分別是受初始溫度的影響，算法迭代次數(shù)與問題解的變化情況.仿真對比了與傳統(tǒng)模擬退火算法以及文獻(xiàn)[19]中遺傳模擬退火算法.由于本文算法增加了控溫策略，整體迭代次數(shù)多于傳統(tǒng)模擬退火算法，但在可接受的范圍內(nèi).關(guān)于算法解質(zhì)量的對比，本文算法可在較低的初始溫度達(dá)到解的穩(wěn)定，并且解的質(zhì)量較優(yōu)；傳統(tǒng)算法容易陷入局部最優(yōu)解，解的質(zhì)量較差；遺傳退火算法在模擬退火算法中加入適應(yīng)性替換方法，可以改善算法過早收斂的問題，但對本文問題的求解效果并不是很理想.因此，改進(jìn)算法在處理本文聯(lián)合優(yōu)化問題有較好的效果.

圖1 初始溫度對迭代次數(shù)的影響Fig.1 Relationship between initial temperature and number of iterations

圖2 初始溫度對總收益的影響Fig.2 User requests and the actual number of users to uninstall relations

圖3 請求用戶數(shù)對實際卸載用戶數(shù)的影響Fig.3 User requests and the actual number of users to uninstall relations

圖4 CPU周期上限對實際卸載用戶數(shù)的影響Fig.4 Effect of the upper limit of CPU cycleson the actual number of users uninstalled

圖5 用戶數(shù)量對總收益的影響Fig.5 Number of users relationship with total revenue

圖6 CPU周期上限對總收益的影響Fig.6 Relationship between the upper limit of CPU cycles and total revenue

資源有限MEC中所面臨的問題主要是由于“死鎖”導(dǎo)致卸載用戶數(shù)量降低，以及解的質(zhì)量不佳兩個問題，接下來分別驗證兩點，并與基于貪心的卸載算法以及文獻(xiàn)[15]中提出的統(tǒng)一卸載算法、非統(tǒng)一卸載算法進(jìn)行對比.

圖3表示總卸載用戶數(shù)與請求卸載用戶數(shù)量的關(guān)系.當(dāng)請求卸載用戶數(shù)量較少時，多數(shù)算法都能保證所有用戶完成卸載.隨著請求卸載的用戶數(shù)量上升，總卸載用戶數(shù)也呈上升趨勢.由于受到F的限制，實際卸載用戶數(shù)量到達(dá)30左右時，將無法容納更多用戶完成卸載.本文算法聯(lián)合卸載與資源分配，有利于調(diào)整多用戶的卸載行為，避免多用戶競爭資源引發(fā)問題，提高了實際卸載的用戶數(shù)量，而貪心算法與非統(tǒng)一算法不同程度受到“死鎖”問題的影響，用戶卸載數(shù)量較低，統(tǒng)一算法通過價格限制了很多用戶的卸載，因此卸載用戶數(shù)量最低.

圖4表示F值變化對MEC實際卸載用戶數(shù)量的影響，隨著F的增加，實際卸載的用戶數(shù)量也隨之增加.當(dāng)F值較低時，本文算法相比其他算法卸載用戶數(shù)提升較明顯，這是因為本文算法結(jié)合了計算資源分配，計算資源影響用戶的卸載量，使得更多用戶卸載執(zhí)行.隨著F值增加，4種算法基本都可以滿足所有用戶卸載.

圖5表示請求用戶數(shù)量與MEC系統(tǒng)收益的關(guān)系.仿真結(jié)果表示隨著請求卸載的用戶數(shù)增加，4種算法得到的總收益呈上升趨勢.當(dāng)用戶數(shù)量小于30，收益上升的趨勢近似線性增長，這是因為用戶數(shù)量較小時，MEC服務(wù)器所提供的計算資源可以滿足所有的用戶都進(jìn)行卸載.當(dāng)用戶數(shù)量增多時，4種策略的總收益上升趨勢趨于平緩，這是由于用戶任務(wù)的計算量達(dá)到了F上限，限制了一些用戶任務(wù)的卸載，本文算法中聯(lián)合了定價、卸載與計算資源分配，優(yōu)化了用戶卸載比例，可以得到最佳用戶卸載組合，獲得最大的收益.

圖6表示F值變化對MEC系統(tǒng)總收益的影響.隨著F的增加，可以卸載到邊緣云的任務(wù)數(shù)量也隨之增加，4種算法得到的總收益都呈現(xiàn)整體上升的趨勢.當(dāng)F值較低時，本文算法相較其他3種算法的提升比較明顯，隨著F值的增加，本文算法、貪心算法與非統(tǒng)一算法都獲得較好的收益，但本文算法為多用戶提供了更合理的計算資源，有最高的總收益.另外統(tǒng)一算法只考慮單一定價方案，導(dǎo)致任務(wù)卸載門限變高，因此總收益最低.

5 結(jié) 論

本文分析了計算資源有限MEC中任務(wù)卸載和資源分配問題.通過價格約束的方法限制部分用戶的卸載，同時為MEC設(shè)定CPU周期接收上限以保證任務(wù)可持續(xù)執(zhí)行，在這基礎(chǔ)上解決了最大化MEC系統(tǒng)總收益的聯(lián)合優(yōu)化問題：首先通過Stackelberg博弈來模擬MEC與用戶之間的交互，通過改進(jìn)模擬退火算法完成計算資源分配，并在每次迭代中對用戶制定差異化定價、卸載決策以及計算資源重分配.最終，算法通過迭代，高效地得到了最佳卸載與資源分配方案，最大程度提高了卸載用戶數(shù)量，同時有效提高了MEC系統(tǒng)的總收益.