資源受限移動邊緣計算任務(wù)拆分卸載調(diào)度決策

張艮山 劉旭寧

(石家莊學(xué)院 河北 石家莊 050035)

0 引 言

通過將任務(wù)拆分并卸載至云端進行數(shù)據(jù)融合、存儲和處理，移動用戶可以潛在地降低自身設(shè)備的能耗和每個任務(wù)的處理延時[1-2]。然而，移動設(shè)備與云端之間的數(shù)據(jù)傳輸會帶來額外的通信延時和傳輸能耗，這樣會影響卸載任務(wù)的服務(wù)質(zhì)量以及全局移動設(shè)備的能量利用[3]。

在這種移動計算環(huán)境下，先前的研究工作主要圍繞以下幾個方向展開，包括單用戶單應(yīng)用卸載[4]、多用戶單應(yīng)用卸載[5-8]、單用戶多任務(wù)卸載[9-10]以及多用戶多任務(wù)卸載[11]。利用傳統(tǒng)的移動云計算技術(shù)，僅有移動設(shè)備和云端服務(wù)器可以進行任務(wù)處理與調(diào)度，加入計算訪問點(Computing Access Point,CAP)后[12]，即引入新的具有計算能力的無線訪問點或基站后形成的新的計算環(huán)境，類似于通過多CAP連接的移動邊緣計算環(huán)境[13]和朵云環(huán)境[14]。此時，移動設(shè)備上的任務(wù)除了可以在本地設(shè)備調(diào)度執(zhí)行，還可以進一步通過CAP卸載至云端執(zhí)行。在考慮融合CAP之后，系統(tǒng)性能的改善可通過求解集中式卸載優(yōu)化問題來完成，如文獻[12]和文獻[15]分別在單用戶和多用戶環(huán)境下求解得到了最優(yōu)卸載與調(diào)度解。然而，已有研究即使考慮了多用戶的任務(wù)卸載情形，也僅是將用戶考慮為同質(zhì)且目標(biāo)一致的實體，未考慮在實際環(huán)境中各個用戶的自私性，以及用戶與計算訪問點間在制定任務(wù)卸載與資源分配調(diào)度策略時的相互影響，這樣得到的任務(wù)卸載結(jié)果僅是理想結(jié)果，且存在不穩(wěn)定性，對于移動計算環(huán)境是極為不利的。

本文將研究自私型移動用戶與計算訪問點間的相互影響。該環(huán)境中，每個移動用戶均擁有輪詢式調(diào)度策略下的多個順序排列任務(wù)需要調(diào)度。本文將在多用戶環(huán)境下考慮任務(wù)的卸載決策和通信與計算資源聯(lián)合分配問題，并以節(jié)省移動設(shè)備能耗與維持多用戶的服務(wù)質(zhì)量為目標(biāo)。不同于文獻[15]中利用一種啟發(fā)式方法求解集中式非凸混合線性規(guī)則問題，本文將利用博弈的思維使移動用戶獨立分布式地基于各自的代價函數(shù)計算自身的卸載決策，而CAP則同步?jīng)Q策通信與計算資源的分配。筆者證實了所提的博弈模型中存在納什均衡(Nash Equilibrium,NE)解，并設(shè)計了一種分布式算法可在收斂情況下達到該NE解。進一步，證實了移動用戶可信任地將其任務(wù)信息傳輸至CAP，使得CAP可以計算NE，沒有任一用戶會脫離該NE。實驗結(jié)果也證實了該博弈方法可在動態(tài)的參數(shù)配置下完成全局代價更低的調(diào)度與卸載解。

1 系統(tǒng)模型

考慮一個資源受限的云訪問網(wǎng)絡(luò)環(huán)境，由一個運程云端服務(wù)器、一個計算訪問點CAP和N個移動用戶組成，如圖1所示。每個移動用戶擁有M個順序的任務(wù)，以輪詢調(diào)度的方式用戶的每個任務(wù)得到處理。輪詢調(diào)度過程中，當(dāng)前一輪任務(wù)調(diào)度后，新的一輪將啟動，直到所有任務(wù)完成。該系統(tǒng)模型也可簡單擴展為每個用戶擁有不同的任務(wù)數(shù)量的場景。且在輪詢調(diào)度系統(tǒng)中，移動用戶的卸載決策與資源分配均需要考慮最優(yōu)化目標(biāo)。相關(guān)符號說明見表1。

圖1 系統(tǒng)模型

1.1 卸載決策

在任務(wù)輪詢調(diào)度的每一輪中，每個移動用戶擁有一個任務(wù)可在本地設(shè)備執(zhí)行或卸載執(zhí)行。卸載任務(wù)可在CAP端執(zhí)行也可在遠程云端執(zhí)行。定義卸載決策滿足：

(1)

1.2 本地執(zhí)行代價

1.3 CAP執(zhí)行代價

由于在多個卸載至CAP的任務(wù)中，僅有某些任務(wù)在CAP端執(zhí)行，需要進一步分配CAP可用的通信與計算資源。對于用戶i卸載至CAP的任務(wù)，數(shù)據(jù)的上傳與下載時間分別為：

(2)

(3)

(4)

(5)

(6)

1.4 云端執(zhí)行代價

(7)

(8)

1.5 優(yōu)化問題

(9)

最優(yōu)化問題是一個非凸混合線性規(guī)化問題，即使可得到最優(yōu)解，理性的移動用戶也不一定會執(zhí)行該最優(yōu)解提供的卸載方案。以下將通過博弈的方法，使得用戶可以以分布式的方式在CAP決定通信與計算資源分配的前提下計算各自的卸載決策，并在實驗中驗證博弈方法也能獲得近似最優(yōu)的性能。

2 多用戶任務(wù)卸載博弈

2.1 博弈模型

首先將移動用戶與CAP間的相互影響建立為一個移動環(huán)境下的卸載決策博弈模型，并尋找式(9)的最優(yōu)解。將博弈定義為：

GMCO=(I,(Ai)i∈I,(ui)i∈I)

(10)

式中：I={1,2,…,N}表示由所有移動用戶組成的博弈者集合；Ai表示用戶i的所有可能策略組成的策略集合；ui表示用戶i需要最小化的代價函數(shù)。

此時，ui為策略組合a=(ai,a-i)的函數(shù)，其中，ai∈Ai，a-i=(a1,a2,…,ai-1,…,ai+1,…,aN)∈∏j≠iAj。定義用戶i的策略集合和代價函數(shù)分別為：

(11)

(12)

通過選擇ai，用戶i可以決定在何處處理任務(wù)可最小化其代價函數(shù)ui，即能耗與延時的權(quán)重之和。假設(shè)所有移動用戶均有意愿參與到博弈中，那么對于每個用戶而言，參與博弈的期望代價應(yīng)小于不參與博弈下的本地處理任務(wù)得到的代價。由于每個移動用戶擁有多個任務(wù)，用戶目標(biāo)是降低每一輪的延時使得下一輪任務(wù)調(diào)度可以盡早開始。因此，式(12)中的代價函數(shù)表明用戶目標(biāo)是均衡其能耗與執(zhí)行延時。

接收所有用戶的卸載決策a后，CAP將分配通信與計算資源至每個用戶以最小化總體系統(tǒng)代價，即求解以下的資源分配問題：

(13)

s.t. C2，C3，C4，C5

2.2 博弈結(jié)構(gòu)及性質(zhì)

定義1表明，博弈者若利用處于納什均衡NE處的策略組合，將沒有任一博弈者可以通過改變自身策略降低其自身代價。由于并不是所有博弈形式均存在納什均衡，以下將證明所提出的博弈模型GMCO至少存在一個納什均衡。

(14)

定義3有限改進性質(zhì)(Finiteimprovement Property，F(xiàn)IP)。博弈G中的一條路徑表示一個序列(a[0],a[1],…)，對于每個k≥1，存在一個唯一的博弈者i，使得ai[k]≠ai[k-1]∈Ai，且a-i[k]≠a-i[k-1]。(a[0],a[1],…)為一條改進路徑，若對于所有k≥1，ui(ai[k])

推論1每個擁有有限策略集合的OPG均擁有至少一個純策略納什均衡和FIP。

推論1的證明參見勢博弈相關(guān)文獻。為了證明本文的博弈模型GMCO總存在一個NE，只需證明GMCO為勢博弈即可。

定理1所提博弈模型GMCO為帶有勢函數(shù)的OPG，總存在一個NE和FIP。

證明：構(gòu)建函數(shù)：

(15)

ui(a)-ui(a′)

(16)

由于式(15)中的φ(a)滿足式(14)定義的OPG的勢函數(shù)的條件，故上式為GMCO的一個勢函數(shù)。因此，GMCO是一個勢博弈OPG，故該博弈GMCO總存在一個NE和FIP。證畢。

綜合以上分析，卸載博弈模型轉(zhuǎn)化為勢博弈的原因在于：本文設(shè)計的卸載博弈模型并無直接方法可證明其存在卸載決策的納什均衡解，因為并非所有博弈都存在納什均衡解，若卸載博弈算法不存在納什均衡，則算法將無法收斂，無法收斂即不可行。而擁有有限策略集合的勢博弈OPG是必須存在納什均衡解的，因此將設(shè)計的卸載博弈模型轉(zhuǎn)化為勢博弈，進而證明其存在納什均衡解。而在性能提升方面即是勢博弈可以通過有限改進性質(zhì)使得博弈者可以不脫離納什均衡而走向代價相互最優(yōu)的策略組合實現(xiàn)的。

2.3 博弈算法

已證明博弈必定存在納什均衡，本節(jié)提出一種基于FIP的卸載博弈算法尋找博弈GMCO的NE。由于CAP擁有來自所有用戶的信息，并需要根據(jù)策略組合分配通信與計算資源到所有卸載任務(wù)上，可以計算GMCO的NEa*并發(fā)送a*到所有用戶。由于NE具有的性質(zhì)，用戶將執(zhí)行策略a*且不會有主動脫離它的意愿。

算法流程如算法1所示。由于GMCO是一個勢博弈OPG，且FIP的性質(zhì)使得每個可改進路徑都是有限的，故算法最終可以達到NEa*，此時沒有任一用戶可以通過改變其策略進一步降低自身的代價。

算法1卸載博弈算法

//求解(13)設(shè)置初始化策略組合及相應(yīng)資源分配方案

2. setNE=False andk=0

//設(shè)置初始NE及k值

3.whileNE==Falsedoflag==0 andi=1

4.whileflag==0 andi≤Ndo

//計算資源分配

//比較代價函數(shù)

8. seta[k+1]=(ai[k+1],a-i[k+1]),flag=1

9.k=k+1

10.elseifi==Nthen

11. setflag=1,NE=True

12.else

13.i=i+1

14.endif

15.endwhile

16.endwhile

3 實驗評估與分析

本節(jié)利用MATLAB計算仿真的結(jié)果研究不同參數(shù)配置下的算法性能。設(shè)置用戶數(shù)是N=8，移動設(shè)備的CPU速率為500×106cycles/s，單位處理能耗為1/730×106J/cycle。考慮執(zhí)行一個x264CBR編碼任務(wù)，任務(wù)對于CPU的執(zhí)行請求為1 900 cycles/byte，任務(wù)的本地計算時間為4.75×10-7J/bit，本地計算能耗為3.25×10-7J/bit。每個任務(wù)的輸入和輸出數(shù)據(jù)量假設(shè)服從[10 MB,30 MB]和[1 MB,3 MB]的均勻分布。根據(jù)IEEE802.11n標(biāo)準(zhǔn)，設(shè)CUL=CDL=72.2 bits。每個移動設(shè)備上每bit的傳輸和接收能耗均設(shè)置為1.42×10-7J/bit，CAP的CPU速率為2.5×109cycle/s，遠程云端的每臺服務(wù)器的CPU速率為5×109cycle/s。若卸載任務(wù)至云端，傳輸速率為Rac=15 Mbits，β=3×10-7J/bit，αi=α=0.5 s/J，假設(shè)每個用戶擁有M=100個任務(wù)。

為了性能的比較，選擇以下的基準(zhǔn)方法作為對比策略：1) 隨機映射方法。該方法中的卸載決策與隨機映射NE方法得到的a[0]完全相同。2) 共享CAP方法。該方法中的卸載決策與共享CAP的NE方法得到的a[0]完全相同。3) 最優(yōu)策略。該方法利用窮舉法得到最優(yōu)決策，是理論上的最優(yōu)解。

隨機映射方法云端資源非限制條件下使用的常規(guī)資源分配方法，選擇該方法進行比較可以證明分布式自主卸載決策的可行性。共享CAP方法由于與共享CAP的NE方法擁有相同的初始策略組合，引入該方法對比可以度量共享CAP的NE方法所使用的通過策略改進和進化得到的納什均衡解能否降低自身代價，即證明卸載博弈算法的有效性。最優(yōu)策略是一種理論最優(yōu)解，在實驗規(guī)模較小時可以通過窮舉法得到卸載的最優(yōu)決策，但實驗規(guī)模增大時求解復(fù)雜度過高，因此該方法可作為其他可行算法的性能度量參照。

圖2研究了系統(tǒng)能耗代價與權(quán)重值α間的影響。可以看到，共享CAP方法優(yōu)于隨機映射方法，而本文算法得到的隨機映射NE和共享CAP NE均得到了近似最優(yōu)的性能，這表明即使本文算法采用隨機起始策略組合，最終得到的NE同樣會在系統(tǒng)總體代價上接近于最優(yōu)解。

圖2 能耗相對比延時的權(quán)值αi對代價的影響

圖3 相對權(quán)重β對總代價的影響

圖4 本地設(shè)備速率對總代價的影響

圖5 用戶數(shù)量對總代價的影響

圖6所示為算法在不同用戶數(shù)量N值下尋找NE時算法需要的迭代次數(shù)。可以看到，隨著N值的增加，兩類算法僅需要較小的迭代次數(shù)即可找到NE，換言之，博弈GMCO中的可改進路徑長度也是較小的。盡管隨機映射NE需要比共享CAP NE更多的迭代次數(shù)，但前者可避免利用半定松馳法求解起始策略組合時的過高計算復(fù)雜度。

圖6 用戶數(shù)量對算法迭代的影響

綜合以上分析可知，多用戶任務(wù)卸載決策博弈算法具備較好的有效性和可行性。需要強調(diào)的是，本文在考慮多用戶對于計算節(jié)點的共享時，并未考慮實際環(huán)境中可能出現(xiàn)的信道共享情形下數(shù)據(jù)傳輸間的干擾問題。這種干擾可能影響多個移動用戶與計算訪問點間數(shù)據(jù)上行和數(shù)據(jù)下行的傳輸速率，進而影響任務(wù)的執(zhí)行時間和執(zhí)行能耗，這可作為影響卸載決策的又一重要因素進行研究與考量。

4 結(jié) 語

本文提出了一種擁有計算訪問點環(huán)境下的多用戶任務(wù)卸載決策博弈算法。在該環(huán)境中，每個移動用戶擁有多個獨立任務(wù)以輪詢方式調(diào)度。為了優(yōu)化移動設(shè)備的能耗與用戶任務(wù)處理的延時，將該集中式的非凸優(yōu)化問題建立為分布式的卸載博弈決策問題，證明了算法提供的博弈模型是一種勢博弈模型，由此證明了博弈中存在納什均衡，各個用戶可在處于納什均衡處的解而不脫離出來。仿真實驗驗證了該博弈算法可以得到與理論最優(yōu)策略近似的最優(yōu)解。