張鋒輝，符茂勝，劉偉榮

(1.皖西學(xué)院 電子與信息工程學(xué)院，安徽 六安 237012；2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083)

0 引 言

隨著移動(dòng)互聯(lián)網(wǎng)的蓬勃發(fā)展，移動(dòng)終端設(shè)備由于其便攜性得到了越來越廣泛的應(yīng)用，一份2016年中國互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告顯示，中國大陸地區(qū)使用手機(jī)上網(wǎng)的網(wǎng)民比例為90.1%，且呈逐年增加趨勢[1]。但不斷復(fù)雜的移動(dòng)應(yīng)用程序如人臉識(shí)別、增強(qiáng)現(xiàn)實(shí)等給移動(dòng)設(shè)備帶來了巨大負(fù)擔(dān)。移動(dòng)云計(jì)算技術(shù)允許將設(shè)備的計(jì)算任務(wù)卸載到云計(jì)算服務(wù)器上執(zhí)行，極大縮短了移動(dòng)應(yīng)用程序執(zhí)行時(shí)間且降低設(shè)備電能損耗，因此移動(dòng)云計(jì)算這種巨大優(yōu)勢得到了業(yè)內(nèi)越來越廣泛的關(guān)注[2-4]。

在移動(dòng)云計(jì)算中設(shè)備可以將任務(wù)卸載至遠(yuǎn)程云、本地微云或由附近設(shè)備組成的移動(dòng)云，而卸載任務(wù)至移動(dòng)云能夠較大程度地降低任務(wù)傳輸時(shí)間、減少無線帶寬使用及降低云計(jì)算費(fèi)用,因此利用移動(dòng)云進(jìn)行計(jì)算的方式得到國內(nèi)外眾多學(xué)者的深入研究[5-6]。但不合理的任務(wù)卸載會(huì)導(dǎo)致任務(wù)執(zhí)行時(shí)間變長、費(fèi)用增高等問題，特別是當(dāng)移動(dòng)云中多個(gè)資源需求節(jié)點(diǎn)(resource demander,RD)同時(shí)向資源提供節(jié)點(diǎn)(resource provider,RP)卸載任務(wù)時(shí)，無序的任務(wù)卸載策略會(huì)極大地降低移動(dòng)云計(jì)算效率。因此，合理的任務(wù)卸載策略是提高移動(dòng)云服務(wù)效率的關(guān)鍵。

鑒于此，本文對移動(dòng)云中多個(gè)RDs同時(shí)向RPs卸載任務(wù)的情景進(jìn)行研究，針對降低各個(gè)RD卸載任務(wù)的執(zhí)行時(shí)間問題，提出了基于隨機(jī)博弈的任務(wù)卸載策略。文中以移動(dòng)云每個(gè)RD卸載任務(wù)至RPs所節(jié)省的時(shí)間為各自效用，建立基于RDs效用最大的優(yōu)化模型。按照任務(wù)完成的時(shí)間將云計(jì)算卸載分為多個(gè)時(shí)間片，并利用任務(wù)產(chǎn)生的特點(diǎn)將節(jié)點(diǎn)效用優(yōu)化問題轉(zhuǎn)化為各個(gè)RD為使自身的效用最大化而進(jìn)行任務(wù)卸載博弈問題。建立隨機(jī)博弈模型并針對該模型提出了反向迭代算法得到博弈的納什均衡策略，實(shí)驗(yàn)將該策略與靜態(tài)博弈獲得的策略進(jìn)行對比，結(jié)果表明,采用隨機(jī)博弈方法獲得的策略能夠明顯提高每個(gè)RD的效用，從而提高移動(dòng)云的計(jì)算效率。

1 相關(guān)工作

近年來,針對移動(dòng)云中通過任務(wù)卸載而提高RD的效用問題，國內(nèi)外學(xué)者分別從時(shí)間、能耗等方面進(jìn)行了大量研究。針對在異構(gòu)網(wǎng)絡(luò)下移動(dòng)云節(jié)點(diǎn)的任務(wù)分配問題，Lu等[7]提出離線集中式方法和在線分布式方法優(yōu)化了任務(wù)執(zhí)行時(shí)間。Zhang等[8]針對中斷容忍網(wǎng)絡(luò)下移動(dòng)云工作量分配問題提出分布式算法減少任務(wù)執(zhí)行時(shí)間。Yaqoob等[9]針對降低移動(dòng)云中任務(wù)執(zhí)行時(shí)間和能耗問題提出異質(zhì)性感知的任務(wù)分配算法。Shi等[10]在固定任務(wù)執(zhí)行時(shí)間和能量消耗限制條件下提出了基于高能量效率的移動(dòng)云任務(wù)調(diào)度算法。Zhang等[11]使用了分布式算法進(jìn)行任務(wù)卸載，提高移動(dòng)云各個(gè)節(jié)點(diǎn)的效用。這些研究從不同角度優(yōu)化了移動(dòng)云節(jié)點(diǎn)的任務(wù)分配，從而減少任務(wù)執(zhí)行時(shí)間或降低能耗，但這些研究僅針對處理單個(gè)節(jié)點(diǎn)任務(wù)卸載的優(yōu)化問題，沒有考慮到多個(gè)節(jié)點(diǎn)任務(wù)卸載時(shí)的競爭關(guān)系。

當(dāng)移動(dòng)云中有多個(gè)節(jié)點(diǎn)進(jìn)行任務(wù)卸載時(shí)，Tang等[12]提出了雙側(cè)競價(jià)機(jī)制提高了移動(dòng)云中RDs和RPs的效用。Kim等[13]針對合作環(huán)境和非合作環(huán)境下的移動(dòng)云，引入李雅普諾夫飄移懲罰因子進(jìn)行雙側(cè)控制，降低RDs和RPs的成本，提高移動(dòng)云計(jì)算效率。但這些研究主要考慮的是有代理進(jìn)行移動(dòng)端管理的場景，沒有考慮多個(gè)RDs根據(jù)自身的情況直接將任務(wù)卸載到RPs的情景，因此,本文針對此情況進(jìn)行研究，提出了基于隨機(jī)博弈的RD任務(wù)卸載策略，提高了移動(dòng)云任務(wù)執(zhí)行效率。

2 系統(tǒng)模型

移動(dòng)云中的節(jié)點(diǎn)主要由資源需求節(jié)點(diǎn)RD和資源提供節(jié)點(diǎn)RP組成，它們通過ad-hoc網(wǎng)絡(luò)進(jìn)行連接，任意設(shè)備之間的通信距離為1跳。該系統(tǒng)中RD的數(shù)量為N，RP的數(shù)量為M，且RD可同時(shí)卸載多個(gè)任務(wù)到不同的RP。由于計(jì)算任務(wù)會(huì)不斷產(chǎn)生，本文將任務(wù)卸載過程劃分為多個(gè)時(shí)間片進(jìn)行研究，并將每個(gè)時(shí)間片定義為任意RP節(jié)點(diǎn)完成任務(wù)所需的最長時(shí)間。當(dāng)計(jì)算任務(wù)產(chǎn)生后會(huì)自動(dòng)進(jìn)入隊(duì)列等待卸載[14]，設(shè)第i個(gè)RD隊(duì)列的長度為Li。該移動(dòng)云系統(tǒng)如圖1所示。

在每個(gè)時(shí)間片中會(huì)有數(shù)量不等的任務(wù)產(chǎn)生，設(shè)在時(shí)間片t內(nèi)有ai個(gè)任務(wù)產(chǎn)生并到達(dá)隊(duì)列，且到達(dá)隊(duì)列的任務(wù)數(shù)量呈泊松分布[15]。每個(gè)任務(wù)具有不同的數(shù)據(jù)量，其中，任務(wù)的數(shù)據(jù)量服從均值為zi的獨(dú)立同分布。每個(gè)任務(wù)的數(shù)據(jù)處理密度使用γ(cycle/bit)表示，數(shù)據(jù)處理密度指處理單位數(shù)據(jù)所需CPU周期，且每個(gè)RD的數(shù)據(jù)處理密度服從均值為γi的獨(dú)立同分布[16]。數(shù)據(jù)量的最大值為zmax，計(jì)算密度的最大值為γmax，可知0≤zi≤zmax,0≤γi≤γmax。在該移動(dòng)云中第i個(gè)RD的CPU處理速度為pi(cycle/s)，處理每個(gè)任務(wù)的平均時(shí)間為

(1)

圖1 移動(dòng)云中任務(wù)卸載示意圖Fig.1 Task offloading in mobile cloud

在時(shí)間片t內(nèi)RD取出di個(gè)任務(wù)進(jìn)行卸載，同時(shí)有ai個(gè)任務(wù)到達(dá)隊(duì)列，此時(shí)隊(duì)列中的任務(wù)數(shù)量為si，如果任務(wù)可全部進(jìn)入隊(duì)列，則在下一個(gè)時(shí)間片中隊(duì)列的任務(wù)數(shù)量為

(2)

該移動(dòng)云中網(wǎng)絡(luò)傳輸速率為v(bit/s)，在任務(wù)傳輸過程中由于RD卸載的數(shù)據(jù)量遠(yuǎn)小于接收結(jié)果的數(shù)據(jù)量，因此,在傳輸過程中所需時(shí)間可僅考慮任務(wù)卸載的時(shí)間[17]，故任務(wù)在傳輸過程中所需的平均時(shí)間hi=zi/v。 在移動(dòng)云資源提供方RP中，使用cj(cycle/s)表示第j個(gè)RP的CPU處理速度，當(dāng)任務(wù)量為G時(shí)，第j個(gè)RP處理該任務(wù)所需時(shí)間為G/cj[18]。在每個(gè)時(shí)間片中，第i個(gè)RD從隊(duì)列中取出一定數(shù)量的任務(wù)進(jìn)行卸載，任務(wù)數(shù)量使用di表示，且RD將這些任務(wù)分配到不同的RP上，設(shè)分配給第j個(gè)RP的工作量為bij，第j個(gè)RP完成所有工作所需的時(shí)間為

(3)

(4)

將每個(gè)RD進(jìn)行任務(wù)卸載所節(jié)省的總時(shí)間定義為其效用，因此,第i個(gè)RD卸載任務(wù)所獲效用ui=twi-dihi。在移動(dòng)云中，每個(gè)RD通過任務(wù)卸載獲取自身最大化效用，可得到的公式為

maxui

(5)

s.t. 0≤zi≤zmax

0≤γi≤γmax

0≤di≤Li

3 隨機(jī)博弈建模

由于每個(gè)時(shí)間片中RD任務(wù)產(chǎn)生具有隨機(jī)特性[13]，根據(jù)(5)式無法確定每個(gè)RD卸載任務(wù)的數(shù)量，不能確定其最優(yōu)的收益，而在多個(gè)時(shí)間片內(nèi)研究任務(wù)卸載，采用隨機(jī)博弈的方法可確定每個(gè)RD的最優(yōu)卸載策略。因此，本文將每個(gè)RD的效用優(yōu)化問題轉(zhuǎn)化為RD為獲得最大效用而進(jìn)行博弈的問題。在該系統(tǒng)中每個(gè)RD是一個(gè)玩家，則該博弈為N玩家隨機(jī)博弈。在每個(gè)時(shí)間片中，第i個(gè)RD首先取出di個(gè)任務(wù)，并將其卸載到不同的RP，同時(shí)新產(chǎn)生任務(wù)到達(dá)隊(duì)列，如果任務(wù)的數(shù)量超過第i個(gè)RD中隊(duì)列的容量，RD需自行處理多余的任務(wù)。因此，在動(dòng)作di條件下第i個(gè)RD的隊(duì)列中任務(wù)數(shù)量的轉(zhuǎn)移概率為

(6)

(7)

(8)

P(S′|Si,(bi1,…,diM),(b-i1,…,b-iM))=

(9)

(9)式中，(b-i1,…,b-iM)表示不包含第i個(gè)RD的其他所有RD的動(dòng)作。 當(dāng)其他RD的動(dòng)作固定時(shí)，第i個(gè)RD在每個(gè)狀態(tài)下的策略可通過(10)式獲得。

(10)

4 反向迭代算法

在隨機(jī)博弈中需要確定每個(gè)狀態(tài)下各個(gè)RD的最優(yōu)動(dòng)作，本文提出反向迭代算法進(jìn)行計(jì)算。首先假設(shè)除第i個(gè)RD外其他RD的最優(yōu)動(dòng)作為(b-i1,…,b-iM)*，然后使用(11)式計(jì)算出在該條件下第i個(gè)RD的最優(yōu)策略。

(11)

利用(11)式得到第i個(gè)RD的動(dòng)作，并根據(jù)(12)式計(jì)算其收益。

(12)

在每次迭代過程中根據(jù)(11)—(12)式進(jìn)行計(jì)算，直到前后2次長期收益的差值小于ε，此時(shí)該博弈已經(jīng)達(dá)到ε-納什均衡[6]。其迭代過程如圖2所示。

圖2中首先初始化每個(gè)RD的值及第1到第N-1個(gè)RD所有狀態(tài)下的策略，并根據(jù)其他RD的策略得到第N個(gè)RD的最優(yōu)策略，而后根據(jù)第N個(gè)RD和第1到第N-2個(gè)RD的策略得到第N-1個(gè)RD的最優(yōu)策略，最終得到所有人的最優(yōu)策略。根據(jù)所有RD的最優(yōu)策略和初始值得到RD所有狀態(tài)下的值，自此完成1次迭代。根據(jù)上次迭代得到每個(gè)RD的策略進(jìn)行第2次迭代，直到所得的值和上次迭代的值相減小于ε時(shí)停止迭代，此時(shí)該博弈達(dá)到ε-納什均衡，各個(gè)RD在每個(gè)狀態(tài)下得到的策略為最優(yōu)策略。

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

本節(jié)首先驗(yàn)證該博弈的收斂性，并比較不同參數(shù)時(shí)系統(tǒng)特性，其次將隨機(jī)博弈的方法和靜態(tài)博弈的方法進(jìn)行對比。該系統(tǒng)中所有節(jié)點(diǎn)隨機(jī)散布于一個(gè)圓形空間，該空間中有3個(gè)RD和5個(gè)RP[13]。所有RD和RP均是現(xiàn)有常見的移動(dòng)端，其CPU處理頻率為[1,2]GHz，數(shù)據(jù)量大小zi為[0.15,0.25]Mbit，計(jì)算密度γi為[2,5](Kcycle/bit)，每個(gè)RD的隊(duì)列可以存儲(chǔ)5個(gè)任務(wù)即Li=5，網(wǎng)絡(luò)傳輸速率為5 MHz[19]。實(shí)驗(yàn)中RD和RP的所有參數(shù)分別如表1和表2所示。

表1 RD的參數(shù)設(shè)置Tab.1 Parameter setting of RDs

表2 RP的參數(shù)設(shè)置Tab.2 Parameter setting of RPs

設(shè)置迭代停止條件ε=0.001，比較折扣系數(shù)對收斂性的影響，當(dāng)β=0.9，β=0.8，β=0.7時(shí)，從圖3中可以看出該隨機(jī)博弈是收斂的，當(dāng)折扣系數(shù)越小算法的收斂速度越快，當(dāng)β=0.7時(shí)該系統(tǒng)經(jīng)迭代14次便可收斂。

同樣，當(dāng)每個(gè)RD中隊(duì)列容量不同時(shí)其獲得效用也不同，圖4顯示了不同隊(duì)列容量的RD效用，可以看出當(dāng)隊(duì)列容量較大時(shí)RD效用也較高，這是由于隊(duì)列容量大時(shí)，每個(gè)RD可以卸載的任務(wù)量具有更多的選擇性。

圖3 隨機(jī)博弈的收斂性Fig.3 Convergence of stochastic game

圖4 不同隊(duì)列容量時(shí)RD效用比較Fig.4 Comparison of RDs’ revenue with different queue capacity

為了與隨機(jī)博弈獲得的策略進(jìn)行對比，本文設(shè)計(jì)靜態(tài)博弈的方法，即在每個(gè)時(shí)間片內(nèi)RD執(zhí)行相同的策略，如把隊(duì)列中所有的任務(wù)全部卸載，而后進(jìn)行分配博弈。實(shí)驗(yàn)在10個(gè)時(shí)間片中對比了這2種方法，圖5顯示不同RD在每個(gè)時(shí)間片上的收益。從圖5中可以看出，采用隨機(jī)博弈的方法，每個(gè)時(shí)間片上RD的收益波動(dòng)不大，這是因?yàn)楫?dāng)任務(wù)隨機(jī)到達(dá)時(shí)，采用隨機(jī)博弈的方法RD會(huì)考慮到當(dāng)前和以后時(shí)間片任務(wù)到達(dá)概率對長期收益的影響而做出決策，因此收益波動(dòng)不大，且在大多數(shù)時(shí)間片中采用隨機(jī)博弈方法獲取的效用明顯高于采用靜態(tài)博弈的效用。

圖6顯示了采用隨機(jī)博弈和靜態(tài)博弈方法下每個(gè)時(shí)間片中所有RD總效用的對比。從圖6中可以看出，采用隨機(jī)博弈下所有RD的總效用明顯高于采用靜態(tài)博弈的總效用，這是因?yàn)椴捎秒S機(jī)博弈時(shí)每個(gè)RD會(huì)根據(jù)自身和其他RD的狀態(tài)采取卸載動(dòng)作，避免了當(dāng)所有RD都進(jìn)行卸載而造成效用下降問題。圖7顯示了10個(gè)時(shí)間片中每個(gè)RD的總效用，可以看出采用隨機(jī)博弈的方法每個(gè)RD可獲得更高的效用。

圖5 不同時(shí)間片采用隨機(jī)博弈和靜態(tài)博弈RD效用的對比Fig.5 Comparison of RDs’ revenue with stochastic game and static game in different time slots

圖6 采用隨機(jī)博弈和靜態(tài)博弈RD效用和的對比Fig.6 Comparison of total revenue for all the RDs between stochastic game and static game

由于每個(gè)RD的效用是任務(wù)卸載所節(jié)省的時(shí)間，因此，采用隨機(jī)博弈獲得的策略縮短了任務(wù)執(zhí)行時(shí)間，提高了移動(dòng)云的服務(wù)效率。當(dāng)移動(dòng)云的節(jié)點(diǎn)固定時(shí)，每個(gè)RD只需要運(yùn)行一次反向迭代算法便可獲得節(jié)點(diǎn)的最優(yōu)卸載策略，且當(dāng)折扣系數(shù)小于0.7時(shí)，算法所需的迭代次數(shù)會(huì)低于10次，其運(yùn)行時(shí)間也會(huì)更少。

圖7 采用隨機(jī)博弈和靜態(tài)博弈每個(gè)RD總收益的對比Fig.7 Comparison of total income per RD using stochastic game and static game

6 結(jié) 論

文中針對任務(wù)隨機(jī)到達(dá)情況下，移動(dòng)云中多用戶任務(wù)卸載的情景進(jìn)行了研究。以各個(gè)RD進(jìn)行任務(wù)卸載所節(jié)省的時(shí)間為其效用，建立優(yōu)化模型，并根據(jù)任務(wù)隨機(jī)到達(dá)特性將其轉(zhuǎn)化為多用戶隨機(jī)博弈模型，提出反向迭代算法得到ε-納什均衡。最后和靜態(tài)博弈策略進(jìn)行了仿真對比，結(jié)果表明，使用隨機(jī)博弈獲得的策略使每個(gè)時(shí)間片內(nèi)RD效用更加穩(wěn)定，同時(shí)降低任務(wù)運(yùn)行時(shí)間、提高移動(dòng)云服務(wù)效率。