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

張艮山 劉旭寧

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

0 引 言

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

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

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

1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

1.1 卸載決策

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

(1)

1.2 本地執(zhí)行代價(jià)

1.3 CAP執(zhí)行代價(jià)

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

(2)

(3)

(4)

(5)

(6)

1.4 云端執(zhí)行代價(jià)

(7)

(8)

1.5 優(yōu)化問題

(9)

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

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

2.1 博弈模型

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

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

(10)

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

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

(11)

(12)

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

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

(13)

s.t. C2，C3，C4，C5

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

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

(14)

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

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

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

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

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

(15)

ui(a)-ui(a′)

(16)

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

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

2.3 博弈算法

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

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

算法1卸載博弈算法

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

2. setNE=False andk=0

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

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

4.whileflag==0 andi≤Ndo

//計(jì)算資源分配

//比較代價(jià)函數(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 實(shí)驗(yàn)評(píng)估與分析

本節(jié)利用MATLAB計(jì)算仿真的結(jié)果研究不同參數(shù)配置下的算法性能。設(shè)置用戶數(shù)是N=8，移動(dòng)設(shè)備的CPU速率為500×106cycles/s，單位處理能耗為1/730×106J/cycle。考慮執(zhí)行一個(gè)x264CBR編碼任務(wù)，任務(wù)對(duì)于CPU的執(zhí)行請(qǐng)求為1 900 cycles/byte，任務(wù)的本地計(jì)算時(shí)間為4.75×10-7J/bit，本地計(jì)算能耗為3.25×10-7J/bit。每個(gè)任務(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。每個(gè)移動(dòng)設(shè)備上每bit的傳輸和接收能耗均設(shè)置為1.42×10-7J/bit，CAP的CPU速率為2.5×109cycle/s，遠(yuǎn)程云端的每臺(tái)服務(wù)器的CPU速率為5×109cycle/s。若卸載任務(wù)至云端，傳輸速率為Rac=15 Mbits，β=3×10-7J/bit，αi=α=0.5 s/J，假設(shè)每個(gè)用戶擁有M=100個(gè)任務(wù)。

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

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

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

圖2 能耗相對(duì)比延時(shí)的權(quán)值αi對(duì)代價(jià)的影響

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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