共享通信信道下多用戶競爭的能效計算卸載機制

梁富偉， 裘華東

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

0 引言

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

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

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

1 系統(tǒng)模型

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

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

表1 符號說明

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

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

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

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

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

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

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

1.1 局部處理

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

1.2 遠程處理

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

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

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

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

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

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

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

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

2 優(yōu)化目標

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

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

3 算法設計

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

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

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

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

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

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

高斯賽德爾算法-尋找Nash均衡點算法如下:

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ì)的，當且僅當:

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

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

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

證明 在該定理條件下，有:

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

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

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

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

因此，式(11)表明:

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

定理1和定理2表明算法中任一用戶決策的改變均不會同步導致其他用戶決策的改變。因此，當算法終止時，沒有任一用戶將改變當前決策，即達到Nash均衡解。

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

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

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

5 仿真實驗

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

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

圖2 Nash均衡數(shù)量

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

圖3 迭代次數(shù)

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

圖4 計算卸載率

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

圖5 標準能耗代價情況

6 結(jié)語

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