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

梁富偉， 裘華東

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

0 引言

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

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

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

1 系統模型

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

如表1所示為對相關符號的說明。

表1 符號說明

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

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

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

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

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

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

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

1.1 局部處理

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

1.2 遠程處理

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

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

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

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

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

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

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

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

2 優化目標

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

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

3 算法設計

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

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

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

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

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

為了尋找Nash均衡，提出一種高斯賽德爾算法［10］，第一步隨機選擇 a=(a1，a2，…，an)，ai={0，1}作為初始點。多種情況下，初始點是不可行解(不滿足時間約束)。那么，在每次迭代中，隨機選擇用戶Um，并求解在給定a時mOPT問題的最優解。如果mOPT的最優解不同當前決策值am，則設置am為新的最優解;否則，隨機選擇另一用戶繼續執行該過程。該迭代過程執行至沒有任一用戶決策變量發生改變為止，即表明算法到達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均衡存在性

本節證明在同質和半同質環境下Nash均衡的存在性［13-14］。定義

則可以重寫mOPT為:

定義1 MCC系統為半同質的，當且僅當:

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

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

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

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

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

由于用戶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系統為同質的，當且僅當:

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

由于同質系統也是半同質系統，那么，Nash均衡可同上的方法找到。

5 仿真實驗

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

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

圖2 Nash均衡數量

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

圖3 迭代次數

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

圖4 計算卸載率

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

圖5 標準能耗代價情況

6 結語

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