梁富偉， 裘華東

(1.上海邦德職業(yè)技術(shù)學(xué)院信息中心，上海200444;2.國網(wǎng)浙江省電力有限公司，杭州310012)

0 引言

目前，移動(dòng)云計(jì)算(Mobile Cloud Computing，MCC)技術(shù)正在迅猛發(fā)展，且正在對(duì)移動(dòng)設(shè)置的運(yùn)行產(chǎn)生巨大影響。移動(dòng)云計(jì)算可以改善應(yīng)用執(zhí)行性能，通過將來自移動(dòng)用戶的計(jì)算任務(wù)遷移至云服務(wù)器執(zhí)行的方式來降低移動(dòng)用戶能耗［1］。這使移動(dòng)用戶可以從計(jì)算密集型應(yīng)用中獲得利益，避免應(yīng)用在局部設(shè)備上執(zhí)行的能源損耗。移動(dòng)用戶通過計(jì)算卸載將任務(wù)上傳至云端服務(wù)器執(zhí)行取代本地執(zhí)行的方式改善移動(dòng)電源能耗。計(jì)算卸載還可以使得云端資源得到更加充分的利用［2-3］。

一些文獻(xiàn)利用博弈理論研究移動(dòng)云計(jì)算。文獻(xiàn)［4］中考慮了一種多資源提供者環(huán)境，它們相互協(xié)作向移動(dòng)用戶提供服務(wù)，并通過博弈論的方式共享得到的收益。文獻(xiàn)［5］中為了降低移動(dòng)云計(jì)算中服務(wù)端和用戶端能耗，設(shè)計(jì)了一種基于擁塞博弈的優(yōu)化框架，使每個(gè)用戶作為一個(gè)博弈者進(jìn)行相互博弈，最終使得用戶選擇進(jìn)行計(jì)算卸載的服務(wù)器。文獻(xiàn)［6］中在移動(dòng)云計(jì)算中設(shè)計(jì)了一種嵌套式兩階段博弈算法，移動(dòng)用戶以最小化能耗和服務(wù)響應(yīng)時(shí)間為目標(biāo)，并得到了優(yōu)化解。文獻(xiàn)［7］中設(shè)計(jì)了一種非集中式博弈算法，通過用戶間的自組織得到了最優(yōu)的計(jì)算卸載決策。以上研究的不足在于，均忽略了用戶在計(jì)算卸載過程中對(duì)于有限無線信道資源的共享，也未考慮用戶間在計(jì)算卸載時(shí)的相互影響。

本文考慮的是多競爭用戶在共享信道下的計(jì)算卸載決策優(yōu)化問題，共享信道在多用戶上傳應(yīng)用時(shí)以動(dòng)態(tài)的時(shí)槽分配方式進(jìn)行，每個(gè)用戶的信道質(zhì)量各不相同，傳輸速率也不相同。由于用戶應(yīng)用具有截止時(shí)間約束，共享信道的競爭將對(duì)用戶計(jì)算卸載決策產(chǎn)生關(guān)鍵影響。該系統(tǒng)被建模為一個(gè)非合作博弈問題，用戶以最小化能耗為目標(biāo)，同時(shí)滿足應(yīng)用的截止時(shí)間。過多用戶選擇計(jì)算卸載時(shí)，單個(gè)用戶的傳輸速率將下降，導(dǎo)致無法滿足時(shí)間約束。設(shè)計(jì)了一種高斯賽德爾算法對(duì)非合作博弈進(jìn)行了求解，并總能求解得到博弈的Nash均衡解。

1 系統(tǒng)模型

移動(dòng)云計(jì)算環(huán)境的計(jì)算卸載模型如圖1所示，n個(gè)移動(dòng)用戶可以通過一個(gè)共享通信信道以計(jì)算卸載方式向云端提交應(yīng)用。

如表1所示為對(duì)相關(guān)符號(hào)的說明。

表1 符號(hào)說明

用戶Um，m∈{1，2，…，n}，以四無組(Jm，Lm，Rm，)進(jìn)行定義，具體含義是:

Jm=(Dm，Bm)，Dm表示為了執(zhí)行任務(wù)Jm需要的CPU周期數(shù)量，Bm表示為了遠(yuǎn)程執(zhí)行任務(wù)用戶Um需要上傳至云端的比特?cái)?shù);

Lm=(表示每個(gè)CPU周期的能耗表示若用戶Um決定局部執(zhí)行任務(wù)，即無需上傳至云端執(zhí)行，任務(wù)執(zhí)行每秒需要的CPU周期;

Rm=(表示無線傳輸功耗，rm表示用戶Um獨(dú)立使用信道時(shí)的無線數(shù)據(jù)上傳速率;

為了簡化描述，定義 βm=Bm/rm，Φm=

每個(gè)用戶Um擁有一個(gè)決策變量am，am=0表示用戶決定在局部設(shè)備上執(zhí)行任務(wù)，am=1表示用戶通過算卸載任務(wù)至云端執(zhí)行。對(duì)于云服器，令fs表示服務(wù)器計(jì)算功耗，且假設(shè)云端的服務(wù)器計(jì)算功耗不作為系統(tǒng)瓶頸，即云端擁有足夠資源執(zhí)行用戶上傳的任務(wù)。

用戶的計(jì)算卸載問題可理解為一個(gè)順序的迭代過程，在每次迭代中，每個(gè)用戶Um將當(dāng)前的決策am傳輸至云端控制器，然后控制器向用戶提供反饋，即按當(dāng)前決策可獲得的任務(wù)響應(yīng)時(shí)間。接下來，用戶更新決策，直到達(dá)到均衡狀態(tài)。最后執(zhí)行任務(wù)的計(jì)算卸載和任務(wù)處理。本質(zhì)上，云端控制器將收集用戶參數(shù)，然后這個(gè)多用戶的博弈過程，并在均衡狀態(tài)時(shí)終止，使得用戶能夠按照均衡點(diǎn)的策略進(jìn)行計(jì)算卸載。

1.1 局部處理

若用戶Um決定在局部設(shè)備上執(zhí)行任務(wù)，應(yīng)用文獻(xiàn)［8］中的能耗模型，局部任務(wù)執(zhí)行產(chǎn)生的能耗和時(shí)間分別為:

1.2 遠(yuǎn)程處理

若用戶Um決定將任務(wù)計(jì)算卸載至遠(yuǎn)程云端處理，則需同時(shí)考慮無線通信模型和云服務(wù)器執(zhí)行的能耗和時(shí)延。

考慮所有用戶共享同一無線通信信道上傳任務(wù)，假設(shè)現(xiàn)有m個(gè)用戶進(jìn)行任務(wù)上傳，共享時(shí)槽以輪詢方式進(jìn)行。不考慮損耗，假設(shè)用戶按β1≤β2≤…≤βm順序進(jìn)行排序，用戶Um的上傳時(shí)間為Toffm。用戶Um完成數(shù)據(jù)傳輸后，用戶Um+1繼續(xù)與剩余用戶共享通信信道。假設(shè)用戶任務(wù)上傳時(shí)間遠(yuǎn)大于通信時(shí)槽，則:

式中，ηm+1表示用戶Um完成數(shù)據(jù)傳輸后共享信道上傳任務(wù)的用戶數(shù)量，則1/ηm+1表示每個(gè)用戶的標(biāo)準(zhǔn)化數(shù)據(jù)傳輸速率。因此，

則式(1)表明對(duì)于一個(gè)上傳用戶Um(即am=1)，有:

表示通過無線信道上傳數(shù)據(jù)時(shí)的能耗，可計(jì)算功耗與上傳時(shí)間的乘積:

云服務(wù)器執(zhí)行:假設(shè)一旦任務(wù)上傳至一個(gè)云服務(wù)器，不存在時(shí)延即執(zhí)行任務(wù)，即擁塞發(fā)生在共享通信信道上而發(fā)生在云服務(wù)器上。用戶Um在服務(wù)器上的執(zhí)行時(shí)間為:

則總的遠(yuǎn)程執(zhí)行時(shí)間和總的遠(yuǎn)程執(zhí)行能耗分別為:

通過考慮用戶Um的決策變量am，可以找到總的響應(yīng)時(shí)間和能耗分別為:

2 優(yōu)化目標(biāo)

移動(dòng)云計(jì)算環(huán)境中，中心調(diào)度器需要為所有用戶決定決策變量am，使得總體能耗達(dá)到最小，同時(shí)確保所有用戶的響應(yīng)時(shí)間約束，即求解以下最優(yōu)化問題(Optimization Problem，OPT):

結(jié)合式(2)、(6)和(8)，目標(biāo)函數(shù)可重寫為:

3 算法設(shè)計(jì)

由于移動(dòng)云計(jì)算不存在中心調(diào)度器，因此，移動(dòng)用戶需要以自身為中心，根據(jù)其代價(jià)函數(shù)決定任務(wù)在局部執(zhí)行或計(jì)算卸載至云端執(zhí)行。換言之，各用戶Um自己設(shè)置策略am，用戶之間是非合作利益?zhèn)€體，以下利用博弈方法對(duì)該場景進(jìn)行研究。

模型中，每個(gè)用戶旨在最小化執(zhí)行功耗。用戶Um的目標(biāo)可建模為:令a－m=(a1，…，am－1，am+1，…，an)表示除用戶Um之外的所有用戶的計(jì)算卸載決策集，那么，給定a－m，用戶Um將根據(jù)以下優(yōu)化問題的解設(shè)置其決策變量am∈{0，1}:

式(8)表明目標(biāo)函數(shù)僅取決于am，且實(shí)際上，最優(yōu)決策解am=1，由于此時(shí)不存在用戶Um擁有局部執(zhí)行能耗。然而此時(shí)響應(yīng)時(shí)間約束無法得到滿足。因此，mOPT是一個(gè)帶有非無效解的優(yōu)化問題。

以下定義Nash均衡。假設(shè)存在一個(gè)矢量a*=，使得對(duì)于每個(gè)用戶Um，給定mOPT的解為則a*稱為Nash均衡。

為了度量Nash均衡的有效性，引入調(diào)和率PoA概率［9］，定義為一個(gè)Nash均衡的最差全局代價(jià)與集中式全局最優(yōu)代價(jià)之比。

為了尋找Nash均衡，提出一種高斯賽德爾算法［10］，第一步隨機(jī)選擇 a=(a1，a2，…，an)，ai={0，1}作為初始點(diǎn)。多種情況下，初始點(diǎn)是不可行解(不滿足時(shí)間約束)。那么，在每次迭代中，隨機(jī)選擇用戶Um，并求解在給定a時(shí)mOPT問題的最優(yōu)解。如果mOPT的最優(yōu)解不同當(dāng)前決策值am，則設(shè)置am為新的最優(yōu)解;否則，隨機(jī)選擇另一用戶繼續(xù)執(zhí)行該過程。該迭代過程執(zhí)行至沒有任一用戶決策變量發(fā)生改變?yōu)橹?，即表明算法到達(dá)Nash均衡點(diǎn)［11-12］。

高斯賽德爾算法-尋找Nash均衡點(diǎn)算法如下:

1.Procedure FindNashEquilibrium

2. sort users so that

3. randomly pick a binary vector a=(a1，a2，…，an)

4.NE=FALSE

5.S=

6. form=1→ndo

7. ifam=1 then

8. addmto the setS

9. end for

10. while NE=FALSE do

11.N={1，2，…，n}

12. fork=1→ndo

13.m←arandomly picked number from the setN

14.xopt←solution of(mOPT)for userUm

15. ifxopt≠amthen

16.am←xopt

17. ifxopt=0 then

18. removemfrom the setS

19. else

20. addmto the setS

21. goto line 27

22. else

23. removeifrom the setN

24. if|N|=0 then

25.NE=TRUE

26. return a

27. end for

28. endwhile

4 Nash均衡存在性

本節(jié)證明在同質(zhì)和半同質(zhì)環(huán)境下Nash均衡的存在性［13-14］。定義

則可以重寫mOPT為:

定義1 MCC系統(tǒng)為半同質(zhì)的，當(dāng)且僅當(dāng):

在初始決策am=0時(shí)執(zhí)行算法1，在每次迭代中，下一個(gè)擁有最小β值的用戶被選擇求解mOPT’問題，即:用戶按β值遞增的順序按序遍歷。當(dāng)算法執(zhí)行遇到一個(gè)用戶由于其時(shí)間約束而不選擇計(jì)算卸載或所有決定選擇計(jì)算卸載時(shí)，算法即終止，且已經(jīng)到達(dá)一個(gè)Nash均衡。

假設(shè)用戶Uk+1為算法在迭代k+1時(shí)所選擇的下一用戶，由于算法仍未終止，則有Sk={1，2，…，k}且

定理1 如果用戶Uk+1在迭代k+1時(shí)決定選擇計(jì)算卸載，且j∈Sk，則對(duì)于任一j＜k+1，j∈Sk+1。

證明 在該定理?xiàng)l件下，有:

利用式(11)和半同質(zhì)定義，可以得到:

由于用戶Uk+1選擇計(jì)算卸載，即Φk+1≤0，則有Φj≤Φk+1≤0。

定理2 如果用戶Uk+1在迭代k+1時(shí)不選擇計(jì)算卸載，則對(duì)于任一j＞k+1，用戶Uj也無法計(jì)算卸載。

證明 在迭代k+1時(shí)，對(duì)于任一用戶j＞k+1，有aj=0且:

因此，式(11)表明:

由于用戶Uk+1無法滿足時(shí)間約束，則Φk+1＞0，因此，Φj≥Φk+1＞0。

定理1和定理2表明算法中任一用戶決策的改變均不會(huì)同步導(dǎo)致其他用戶決策的改變。因此，當(dāng)算法終止時(shí)，沒有任一用戶將改變當(dāng)前決策，即達(dá)到Nash均衡解。

定義2 MCC系統(tǒng)為同質(zhì)的，當(dāng)且僅當(dāng):

βi=βjand τi=τj，i，j∈ {1，2，…，n}

由于同質(zhì)系統(tǒng)也是半同質(zhì)系統(tǒng)，那么，Nash均衡可同上的方法找到。

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

為了評(píng)估博弈模型的有效性［15］，通過仿真實(shí)驗(yàn)分析了算法的收斂時(shí)間、Nash均衡點(diǎn)處的能耗兩個(gè)方面的性能。仿真結(jié)果顯示算法在同質(zhì)和半同質(zhì)環(huán)境下總能收斂于Nash均衡點(diǎn)。為了進(jìn)行多場景實(shí)驗(yàn)，隨機(jī)生成了多個(gè)實(shí)驗(yàn)配置，每個(gè)實(shí)驗(yàn)配置以不同的初始決策量進(jìn)行多次實(shí)驗(yàn)，并取其均值。所有配置中，參數(shù)均以隨機(jī)均衡分布形式產(chǎn)生。請求的CPU周期D隨機(jī)分布于區(qū)間［1，10］Gcycles，輸入數(shù)據(jù)量B處于［0.42，42］Mb，信道數(shù)據(jù)傳輸速率r處于［6.4，64］Mb/s，局部計(jì)算功耗fl隨機(jī)分布在0.5、0.8和1(單位:giga CPU cycles/s)之間，云服務(wù)器計(jì)算功耗fs設(shè)置為100 giga CPU cycles/s，數(shù)據(jù)傳輸功耗Pt處于［0.75，1］W，局部能耗vl等于Pl/fl，局部執(zhí)行功耗Pl隨機(jī)分布在20、22.5和25 W間。

圖2顯示了算法得到的Nash均衡點(diǎn)的數(shù)量?？梢钥闯?，均衡點(diǎn)的數(shù)量隨著用戶數(shù)量的增加而增加，與預(yù)期一致。對(duì)于較少的用戶數(shù)量(12個(gè)用戶以下)，均衡點(diǎn)的數(shù)量基本隨用戶數(shù)量呈線性增加，而隨后均衡點(diǎn)的變化則更加劇烈。

圖2 Nash均衡數(shù)量

圖3顯示了平均和最大博弈收斂的迭代次數(shù)(時(shí)間)，基本與用戶數(shù)量呈線性增加，這表明基于博弈的計(jì)算卸載決策求解機(jī)制與問題的增加擴(kuò)展性較好。

圖3 迭代次數(shù)

圖4顯示了平均卸載率，定義為卸載至云端執(zhí)行的數(shù)量與總用戶數(shù)量之比，以及顯示了卸載率的最大值與最小值?？梢钥闯觯S著用戶數(shù)量的增加，均衡點(diǎn)處成比例的更少的用戶會(huì)選擇終止卸載，這是由于信道能力為常量，因此，遠(yuǎn)程執(zhí)行延時(shí)會(huì)隨著用戶比例的增加而增加的原因?qū)е碌摹?/p>

圖4 計(jì)算卸載率

圖5顯示了算法得到的能耗情況。可以看出，本文的計(jì)算卸載算法的能耗代價(jià)基本小于基準(zhǔn)算法的能耗，這是由于本文算法在確保滿足時(shí)間約束的同時(shí)，在優(yōu)化使用共享信道的同時(shí)，可以使用戶更加合理的自主決策計(jì)算卸載，降低在局部執(zhí)行應(yīng)用的自身能耗。而文獻(xiàn)［6］中重點(diǎn)對(duì)執(zhí)行延遲進(jìn)行了優(yōu)化，文獻(xiàn)［7］中則未考慮共享信道的多用戶爭用情況，這使得多用戶同步計(jì)算卸載對(duì)于優(yōu)化目標(biāo)是得不償失的。

圖5 標(biāo)準(zhǔn)能耗代價(jià)情況

6 結(jié)語

移動(dòng)云計(jì)算中，用戶可以通過計(jì)算卸載將應(yīng)用上傳至云端執(zhí)行，降低局部執(zhí)行能耗。然而，由于共享通信信道下，多競爭用戶上傳應(yīng)用時(shí)勢必會(huì)導(dǎo)致應(yīng)用執(zhí)行延時(shí)。為了解決時(shí)間約束下優(yōu)化執(zhí)行能耗的計(jì)算卸載決策問題，設(shè)計(jì)了一種基于非合作博弈算法，以用戶最小化自身能耗為目標(biāo)，通過一種高斯賽德爾方法對(duì)博弈的Nash均衡進(jìn)行了求解。仿真結(jié)果表明，算法總能收斂于Nash均衡點(diǎn)處，且能夠在滿足時(shí)間約束的情況下降低執(zhí)行能耗。