胡 楊，韓嘉偉，張志紅，李 軍，劉 暢，曾祥豹，李小飛，王音心

(1.中電科技集團(tuán)重慶聲光電有限公司，重慶 401332；2.中國(guó)電子科技集團(tuán)公司第二十六研究所，重慶 400060；3.重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引言

隨著智能手機(jī)、平板電腦等移動(dòng)終端在生活中的廣泛普及，人們從互聯(lián)網(wǎng)獲取信息的方式已從傳統(tǒng)的臺(tái)式電腦終端逐漸轉(zhuǎn)移至移動(dòng)終端。由中國(guó)互聯(lián)網(wǎng)信息中心發(fā)布的《第41次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示，截至2017年12月，我國(guó)手機(jī)網(wǎng)民規(guī)模達(dá)7.72億，且使用移動(dòng)手機(jī)上網(wǎng)的比例高達(dá)97.5%，超過(guò)了60.1%的臺(tái)式電腦上網(wǎng)比例[l]。在互聯(lián)網(wǎng)用戶服務(wù)需求日益多樣化的趨勢(shì)下，移動(dòng)終端還需依賴更強(qiáng)大的網(wǎng)絡(luò)資源和技術(shù)平臺(tái)才可提供更多、更強(qiáng)健的服務(wù)，因此，科研人員提出了移動(dòng)云計(jì)算(MCC)[2-3]的概念，將傳統(tǒng)云計(jì)算(CC)技術(shù)和理念融合到移動(dòng)互聯(lián)網(wǎng)的服務(wù)領(lǐng)域中，利用云端強(qiáng)大的處理和存儲(chǔ)能力來(lái)減輕移動(dòng)設(shè)備端的負(fù)載，以提升整個(gè)服務(wù)體系的處理能力與服務(wù)能力。但在實(shí)際生活中，移動(dòng)終端用戶往往找不到可用的云基礎(chǔ)設(shè)施，不能保證隨時(shí)隨地的接入情況，而且由于服務(wù)器距離太遠(yuǎn)，任務(wù)遷移也會(huì)面臨著高網(wǎng)絡(luò)延遲和通信成本的問(wèn)題。因此，科研人員基于移動(dòng)云計(jì)算的思想，提出了移動(dòng)Ad Hoc云計(jì)算[4-5]的概念并受到了廣泛關(guān)注。

在移動(dòng)Ad Hoc云中人們關(guān)注的兩個(gè)重要指標(biāo)是：任務(wù)卸載過(guò)程中產(chǎn)生的系統(tǒng)能量消耗[6]和任務(wù)卸載時(shí)延[7]。任務(wù)卸載過(guò)程中產(chǎn)生的系統(tǒng)能量消耗，包括在任務(wù)提交和計(jì)算結(jié)果返回階段產(chǎn)生的通信能耗，以及在代理終端執(zhí)行處理過(guò)程中產(chǎn)生的計(jì)算能耗。所述能耗大小直接影響到移動(dòng)設(shè)備的電池續(xù)航能力，該問(wèn)題對(duì)由資源(如內(nèi)存、CPU)受限且電池容量小的移動(dòng)設(shè)備所組成的移動(dòng)Ad Hoc云的影響尤為明顯，如果不能處理好任務(wù)卸載過(guò)程中的能耗問(wèn)題，將會(huì)影響到云系統(tǒng)的續(xù)航能力，降低系統(tǒng)的服務(wù)性能。在任務(wù)卸載中存在數(shù)據(jù)傳輸及任務(wù)處理時(shí)延，雖然相對(duì)傳統(tǒng)移動(dòng)云計(jì)算，移動(dòng)Ad Hoc云在任務(wù)時(shí)延上具有很大的優(yōu)勢(shì)，但由于網(wǎng)絡(luò)中存在多個(gè)性能差異的移動(dòng)設(shè)備，而且每個(gè)設(shè)備間的無(wú)線網(wǎng)絡(luò)環(huán)境也各不相同，因此，在客戶端卸載任務(wù)時(shí)，每個(gè)代理終端產(chǎn)生的時(shí)延也不盡相同。對(duì)于云游戲、云感知等時(shí)延敏感性的實(shí)時(shí)性任務(wù)[8]，如果時(shí)延過(guò)大，將會(huì)嚴(yán)重影響到移動(dòng)Ad Hoc云的服務(wù)質(zhì)量(QOS)，從而降低客戶服務(wù)體驗(yàn)。對(duì)于文件壓縮、圖像處理等非時(shí)延敏感性任務(wù)，則可以適當(dāng)放寬對(duì)時(shí)延的要求?？傊?，對(duì)于任何計(jì)算任務(wù)，時(shí)延總是越小越好。

本文在移動(dòng)Ad Hoc云任務(wù)卸載的過(guò)程中，提出了一種降低系統(tǒng)能耗與任務(wù)時(shí)延的聯(lián)合優(yōu)化算法(JOECD)，解決了客戶端計(jì)算任務(wù)恰當(dāng)選擇代理終端問(wèn)題。

1 系統(tǒng)模型

圖1 任務(wù)卸載系統(tǒng)模型

移動(dòng)Ad Hoc云計(jì)算系統(tǒng)任務(wù)卸載模型如圖1所示，客戶端在網(wǎng)絡(luò)中發(fā)現(xiàn)一系列合適的代理終端并向其卸載自身計(jì)算任務(wù)，代理終端利用自身的可用資源為客戶端進(jìn)行服務(wù)，并把執(zhí)行完成后的任務(wù)返回給客戶端[9]。不失一般性，假設(shè)網(wǎng)絡(luò)中存在兩種無(wú)線通信方式，即WiFi與蜂窩網(wǎng)絡(luò)。眾所周知，WiFi的通信成本普遍低于蜂窩網(wǎng)絡(luò)，而通信速率普遍高于蜂窩網(wǎng)絡(luò)，因此，在任務(wù)卸載的過(guò)程中優(yōu)先選擇使用WiFi進(jìn)行通信。如果代理終端移出了WiFi的通信范圍，則客戶端自動(dòng)切換為蜂窩網(wǎng)絡(luò)繼續(xù)通信。

假設(shè)系統(tǒng)中存在M個(gè)客戶端(C)需要卸載任務(wù)，且每個(gè)客戶端的任務(wù)量不同，第i個(gè)客戶端Ci的任務(wù)量為Wi，在任務(wù)來(lái)臨時(shí)卸載至代理終端，默認(rèn)每個(gè)客戶端僅存在一個(gè)計(jì)算任務(wù)。同時(shí)，假設(shè)系統(tǒng)中存在N個(gè)代理終端(A)可共享資源，第j個(gè)代理終端Aj的最大可用資源量為Qj，當(dāng)用戶卸載的任務(wù)處理完成后返回結(jié)果給客戶端。假設(shè)系統(tǒng)中的所有移動(dòng)設(shè)備上可用的整體資源及剩余電池能量都足以運(yùn)行每個(gè)獨(dú)立的計(jì)算任務(wù)，即任何計(jì)算任務(wù)都可以選擇卸載至網(wǎng)絡(luò)中任意其他代理終端進(jìn)行處理。因此，當(dāng)客戶端在進(jìn)行任務(wù)卸載時(shí)，需根據(jù)代理終端的屬性決策出如何選擇代理終端進(jìn)行任務(wù)卸載，以達(dá)到優(yōu)化系統(tǒng)能耗和時(shí)延的目的。當(dāng)客戶端Ci中的計(jì)算任務(wù)到達(dá)時(shí)，Ci會(huì)在系統(tǒng)中尋求足夠的資源來(lái)處理自身的計(jì)算任務(wù)，在任務(wù)卸載的過(guò)程中會(huì)產(chǎn)生相應(yīng)的能量消耗及時(shí)延。

基于上述假設(shè)，對(duì)移動(dòng)Ad Hoc云在任務(wù)卸載過(guò)程中涉及到系統(tǒng)能耗及任務(wù)時(shí)延進(jìn)行建模，并由此推導(dǎo)出目標(biāo)函數(shù)。

1.1 計(jì)算能耗

在任務(wù)卸載過(guò)程中，系統(tǒng)能耗包括在移動(dòng)設(shè)備上處理計(jì)算任務(wù)所產(chǎn)生的計(jì)算能耗，以及在數(shù)據(jù)傳輸過(guò)程中產(chǎn)生的通信能耗。其中，計(jì)算能耗與計(jì)算任務(wù)量及當(dāng)前終端的處理能力有關(guān)，因此，客戶端Ci在任務(wù)卸載中產(chǎn)生的總計(jì)算能耗ei為

(1)

1.2 通信能耗

(2)

(3)

為了便于分析，假設(shè)在Aj將任務(wù)處理后得到的結(jié)果數(shù)據(jù)大小為客戶端Ci提交數(shù)據(jù)的ρ倍(0<ρ≤1)，因此，結(jié)果回傳階段在WiFi和蜂窩中傳輸?shù)臄?shù)據(jù)量如下：

(4)

(5)

因此，在卸載任務(wù)至代理終端的過(guò)程中產(chǎn)生的通信能耗為

(6)

式中：bcell為蜂窩的網(wǎng)絡(luò)帶寬；2為單位時(shí)間的通信能耗。

因此，Ci在任務(wù)卸載過(guò)程中所產(chǎn)生的總通信能耗為

(7)

式中上角com表示通信。

為了便于討論，本文假設(shè)所有移動(dòng)設(shè)備在能耗方面都是同性質(zhì)的。對(duì)于所有設(shè)備都使用同樣的單位時(shí)間能耗λ1與λ2，用于通信的能量總量一般高于用于計(jì)算處理的能量[9]，即λ1<λ2。

1.3 任務(wù)時(shí)延模型

類似于通信能耗，如果將客戶端Ci的計(jì)算任務(wù)卸載至代理終端Aj，則卸載計(jì)算任務(wù)所產(chǎn)生的任務(wù)時(shí)延可表示為數(shù)據(jù)傳輸產(chǎn)生的傳輸時(shí)間及任務(wù)處理所產(chǎn)生的計(jì)算時(shí)間之和，即

(8)

因此，客戶端Ci在任務(wù)卸載過(guò)程中所產(chǎn)生的任務(wù)時(shí)延為

(9)

1.4 優(yōu)化問(wèn)題

使下式最小

(10)

目標(biāo)函數(shù)需要滿足:

(11)

(12)

xij≥0j=1,…,N

(13)

值得注意的是，通常需要根據(jù)具體情況的不同對(duì)任務(wù)延遲和系統(tǒng)能耗進(jìn)行綜合權(quán)衡[11]。在上述目標(biāo)函數(shù)中，我們使用權(quán)重參數(shù)γ進(jìn)行靈活配置。例如，如果移動(dòng)設(shè)備電池性能問(wèn)題并不用嚴(yán)重，或者當(dāng)前客戶端的計(jì)算任務(wù)對(duì)延遲非常敏感，則可以將γ設(shè)置得盡可能小。在這種情況下，優(yōu)化問(wèn)題變?yōu)楸M量使任務(wù)時(shí)延最小化以降低對(duì)能耗的關(guān)注度。然而，如果能耗是移動(dòng)設(shè)備的主要關(guān)注點(diǎn)，而任務(wù)延遲是可以容忍的，則γ可以設(shè)置得足夠大。

2 系統(tǒng)能耗與任務(wù)時(shí)延的聯(lián)合優(yōu)化算法

在移動(dòng)Ad Hoc云中，客戶端在卸載一些計(jì)算密集型任務(wù)過(guò)程中不僅會(huì)產(chǎn)生相應(yīng)的傳輸能耗與計(jì)算能耗，而且還會(huì)產(chǎn)生一定的任務(wù)時(shí)延。為了降低系統(tǒng)能耗與減小任務(wù)時(shí)延，本節(jié)提出了一種運(yùn)用在移動(dòng)Ad Hoc云中，基于系統(tǒng)能耗與任務(wù)時(shí)延的聯(lián)合優(yōu)化 (JOECD)算法。

2.1 算法具體流程

當(dāng)每一個(gè)客戶端的計(jì)算任務(wù)來(lái)臨時(shí)，都會(huì)執(zhí)行JOECD算法，主要流程如圖2所示。

(14)

圖2 JOECD算法流程圖

為更清晰地展現(xiàn)客戶端進(jìn)行任務(wù)決策并卸載的過(guò)程，在算法1)中對(duì)JOECD算法進(jìn)行了詳細(xì)的設(shè)計(jì)：

輸入?yún)?shù)：客戶端卸載任務(wù)量W,代理終端最大可用資源量Q,單位時(shí)間的計(jì)算能耗λ1，單位時(shí)間的通信能耗λ2,WiFi的網(wǎng)絡(luò)帶寬bwf,蜂窩的網(wǎng)絡(luò)帶寬bcell,客戶端個(gè)數(shù)M，代理終端個(gè)數(shù)N。

輸出參數(shù):系統(tǒng)能耗E，任務(wù)時(shí)延D。

2)l=l+1；

3)for 每一個(gè)代理終端j=1∶N；

4)根據(jù)式(10)計(jì)算Sij；

5)end for；

9)根據(jù)式(1)，(7)，(9)計(jì)算Ei與Di；

10)更新可用資源量Q(l)；

11)將Ci從集合C中移除；

12)else；

13)任務(wù)卸載失敗，Ei=0，Di=0；

14)end if；

16)返回步驟2)；

17)end if；

18)返回E，D。

2.2 復(fù)雜度分析

算法復(fù)雜度是衡量算法優(yōu)劣的一個(gè)指標(biāo)[12]，本文提出的任務(wù)卸載決策算法的復(fù)雜度為O(MN2)。

如上所述，該算法是根據(jù)客戶端的數(shù)量一輪一輪進(jìn)行的，首先分析算法中第l輪決策中的復(fù)雜度，如算法1)所示，它主要包括以下步驟：

a.計(jì)算Si。對(duì)于客戶端Ci，需對(duì)網(wǎng)絡(luò)中所有的代理終端，即A中所有元素通過(guò)式(14)都計(jì)算一次Sij以得到Si，這個(gè)步驟的復(fù)雜度為O(N)。

根據(jù)上述分析，第l輪決策中的復(fù)雜度為平方階，即O(N2)。由于系統(tǒng)中存在M個(gè)客戶端，因此，在算法中這個(gè)決策步驟會(huì)執(zhí)行M次，因此，本文提出的任務(wù)卸載決策算法的復(fù)雜度可表示為O(MN2)。

3 仿真與性能分析

為了對(duì)本文提出的系統(tǒng)能耗與任務(wù)時(shí)延的聯(lián)合優(yōu)化算法進(jìn)行性能評(píng)估，將JOECD與文獻(xiàn)[2]中提出的移動(dòng)云計(jì)算(MCC)方案在系統(tǒng)能耗與任務(wù)時(shí)延上進(jìn)行對(duì)比。在MCC方案中，客戶端通過(guò)宣布一個(gè)總的回報(bào)以激勵(lì)代理卸載資源，并將回報(bào)與資源卸載量進(jìn)行迭代至雙方收益最大化。由此可知，MCC方案中并沒(méi)有對(duì)系統(tǒng)能耗與任務(wù)時(shí)延進(jìn)行控制。

3.1 參數(shù)設(shè)置

3.2 性能分析

圖3 系統(tǒng)能耗與客戶端數(shù)量之間關(guān)系

由圖3可知，當(dāng)客戶端數(shù)量從1增加到10時(shí)，兩種方案的系統(tǒng)能耗都隨著客戶端數(shù)量的增加而增加，這是因?yàn)楫?dāng)云系統(tǒng)中計(jì)算資源充足時(shí)，卸載更多的任務(wù)會(huì)導(dǎo)致更多的計(jì)算能耗和通信能耗。在到達(dá)的任務(wù)量較少時(shí)，由于系統(tǒng)內(nèi)資源充足，JOECD算法通過(guò)任務(wù)卸載決策算法可選擇當(dāng)前系統(tǒng)中能耗與任務(wù)時(shí)延最低的代理終端進(jìn)行任務(wù)卸載，而移動(dòng)云計(jì)算(MCC)方案則更關(guān)注系統(tǒng)收益以及資源利用方面，從而盡可能選擇任務(wù)卸載過(guò)程中系統(tǒng)收益最高及通信成本最低的代理終端。因此，JOECD算法在能耗方面的表現(xiàn)優(yōu)于MCC方案。但當(dāng)客戶端增多時(shí)，由于系統(tǒng)中的總計(jì)算資源有限，導(dǎo)致了在JOECD算法中無(wú)更多的代理終端進(jìn)行選擇，從而不得不選擇能耗與時(shí)延較高的代理進(jìn)行任務(wù)卸載。因此，在客戶端數(shù)量較多時(shí)，JOECD算法在系統(tǒng)能耗上的表現(xiàn)會(huì)與MCC方案趨于接近。

圖4給出JOECD算法與MCC方案在任務(wù)時(shí)延上的差異。由圖可看出，任務(wù)時(shí)延隨著云系統(tǒng)內(nèi)客戶端的數(shù)量增加而增加，這是由于任務(wù)數(shù)量越多且每個(gè)任務(wù)的分配過(guò)程都會(huì)產(chǎn)生時(shí)延，故而造成的總時(shí)延升高。當(dāng)云系統(tǒng)內(nèi)的任務(wù)數(shù)量增加時(shí)，云系統(tǒng)內(nèi)的可用計(jì)算資源逐漸變得不再充足，此時(shí)JOECD算法中新的客戶端已無(wú)機(jī)會(huì)選擇時(shí)延表現(xiàn)更優(yōu)的代理終端，只能選擇時(shí)延較高的代理滿足任務(wù)需求；而在MCC方案中，即使存在代理間的資源動(dòng)態(tài)調(diào)整，但因?yàn)樵葡到y(tǒng)內(nèi)總的資源量受限，剩余資源不能滿足到達(dá)的任務(wù)總量要求。因此，在客戶端數(shù)量較高時(shí)，兩種方案在任務(wù)時(shí)延趨于接近。

圖4 任務(wù)時(shí)延與客戶端數(shù)量之間關(guān)系

4 結(jié)束語(yǔ)

本文綜合考慮了移動(dòng)Ad Hoc云任務(wù)分配過(guò)程中系統(tǒng)能耗與任務(wù)時(shí)延問(wèn)題，提出了任務(wù)卸載過(guò)程中基于系統(tǒng)能耗與任務(wù)時(shí)延的聯(lián)合優(yōu)化算法。該算法對(duì)任務(wù)卸載過(guò)程中會(huì)產(chǎn)生的計(jì)算能耗、通信能耗及卸載時(shí)延進(jìn)行建模并提出了優(yōu)化目標(biāo)問(wèn)題。通過(guò)預(yù)估處理對(duì)每個(gè)客戶端的需要卸載任務(wù)進(jìn)行卸載決策，以達(dá)到減小系統(tǒng)能耗和任務(wù)時(shí)延的目的。