疏官勝，劉煒清，李 京

(中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026)

1 引 言

近年來，隨著智能移動設(shè)備的廣泛普及，一大批移動應(yīng)用也涌現(xiàn)出來，深入到人們生活的方方面面.這些移動應(yīng)用強(qiáng)大的功能和豐富的體驗(yàn)對設(shè)備的處理能力提出了越來越高的要求，進(jìn)而刺激著智能移動設(shè)備的快速升級換代.然而， 移動設(shè)備上有限的資源仍越來越明顯地成為了限制移動應(yīng)用體驗(yàn)及其適用場景的瓶頸.隨著移動網(wǎng)絡(luò)的持續(xù)升級和云計(jì)算技術(shù)的逐漸成熟，研究者們嘗試將移動應(yīng)用中計(jì)算復(fù)雜的部分通過無線網(wǎng)絡(luò)遷移到云端運(yùn)行，從而突破智能移動設(shè)備的資源瓶頸、提升應(yīng)用的服務(wù)體驗(yàn).隨著相關(guān)的研究成果逐漸積累，人們將這一新興領(lǐng)域稱為移動云計(jì)算.其中，針對移動云環(huán)境中應(yīng)用種類繁多、網(wǎng)絡(luò)狀況復(fù)雜多變等特點(diǎn)，如何實(shí)時地為各類應(yīng)用決策出適宜當(dāng)前環(huán)境狀況的計(jì)算遷移方案成為了研究者們關(guān)注的熱點(diǎn).

移動云計(jì)算中的計(jì)算遷移技術(shù)能極大地縮減應(yīng)用的響應(yīng)時間，這主要得益于以下兩點(diǎn)優(yōu)勢：

1)相較于資源匱乏的移動終端，云數(shù)據(jù)中心強(qiáng)大的計(jì)算資源能夠極大地加速被遷移模塊的執(zhí)行；

2)一個應(yīng)用中的多模塊間的并行執(zhí)行能進(jìn)一步縮短響應(yīng)時間.

現(xiàn)有的研究工作都在不同程度上利用了這兩點(diǎn)優(yōu)勢.例如， Odessa[1]將每一幀圖像切分成很多小的圖片(tiles)，而后對這些切分后的小圖片并行地進(jìn)行人臉識別，從而縮短處理每一幀圖像所需的時間，這里所采用的就是數(shù)據(jù)并行的方式.除數(shù)據(jù)并行外，流水線并行(pipeline)以及任務(wù)并行則是另外兩種常見的并行加速方式.流水線并行在針對基于數(shù)據(jù)流的移動云計(jì)算工作中得到了廣泛的運(yùn)用.而任務(wù)并行加速在多線程/進(jìn)程的移動應(yīng)用中就已經(jīng)得到了運(yùn)用，但在移動云環(huán)境中部分應(yīng)用模塊已經(jīng)遷移到云端的場景下進(jìn)行任務(wù)并行的特殊之處并沒有得到研究者們的充分重視.

在移動云環(huán)境下的應(yīng)用，與單純在移動設(shè)備上執(zhí)行時的最大不同在于分布于移動端和云端的應(yīng)用模塊需要通過無線網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)交互，而移動環(huán)境中動態(tài)變化且受限的無線網(wǎng)絡(luò)條件使得這一特性對縮短應(yīng)用的響應(yīng)時間有著不可忽視的作用.由于在移動云計(jì)算中計(jì)算遷移常以應(yīng)用的模塊為最小粒度，故在本文接下來的描述中用"模塊并行"特指在移動云環(huán)境中的任務(wù)并行.對于可模塊并行的應(yīng)用而言，常常會出現(xiàn)多對模塊同時進(jìn)行跨網(wǎng)絡(luò)的數(shù)據(jù)傳輸，而現(xiàn)有的移動云計(jì)算研究往往都采取簡單的"即時發(fā)送、網(wǎng)絡(luò)公平競爭"或"先來先服務(wù)、網(wǎng)絡(luò)獨(dú)占"兩種方式，并未考慮不同網(wǎng)絡(luò)傳輸策略對應(yīng)用響應(yīng)時間的影響.

本文針對移動云環(huán)境的特性，將模塊間跨網(wǎng)絡(luò)的數(shù)據(jù)傳輸策略集成到傳統(tǒng)只包含各模塊執(zhí)行地點(diǎn)的計(jì)算遷移方案中，并為可模塊并行的移動應(yīng)用設(shè)計(jì)了高效的貪心算法從而在不同環(huán)境下實(shí)時地決策出其擴(kuò)展的計(jì)算遷移方案.在擴(kuò)展的計(jì)算遷移方案中，移動應(yīng)用中不涉及移動設(shè)備上傳感器及輸入輸出組件的模塊(即可遷移模塊)可在移動設(shè)備或云中任意一端執(zhí)行.對所有需要在移動端和云端間通過網(wǎng)絡(luò)傳輸數(shù)據(jù)的模塊對而言，其數(shù)據(jù)傳輸?shù)臅r機(jī)都由底層的移動云計(jì)算支撐平臺依據(jù)本文所設(shè)計(jì)的算法進(jìn)行全局控制.而多對模塊同時傳輸時也不再拘泥于上述的兩種傳統(tǒng)策略，而采用更為靈活的混合策略.

為可模塊并行的應(yīng)用決策上述擴(kuò)展的計(jì)算遷移方案的算法是本文的主要工作.算法設(shè)計(jì)過程中的主要挑戰(zhàn)來源于兩個方面：

1)擴(kuò)展的計(jì)算遷移方案的可行域是隨著模塊數(shù)目及模塊間數(shù)據(jù)傳輸邊的數(shù)目指數(shù)爆炸的；

2)由于移動環(huán)境的動態(tài)變化，算法需要快速決策出適合于當(dāng)前環(huán)境的遷移方案，即對算法有較高的實(shí)時性要求.

為了解決這兩方面帶來的矛盾，對移動云中應(yīng)用的特性進(jìn)行了分析，并針對性地設(shè)計(jì)了啟發(fā)式的算法.具體而言，基于前人對于線性拓?fù)漕悜?yīng)用的研究結(jié)論[11]上的推廣，本文在搜索遍歷應(yīng)用各模塊執(zhí)行地點(diǎn)時進(jìn)行大量的剪枝，從而降低算法的執(zhí)行時間.其次，本文設(shè)計(jì)了多種貪心算法決策固定模塊執(zhí)行地點(diǎn)時各數(shù)據(jù)依賴的模塊對間的數(shù)據(jù)傳輸策略.

在實(shí)驗(yàn)中，仿真驗(yàn)證了多種網(wǎng)絡(luò)條件、多種應(yīng)用拓?fù)浣Y(jié)構(gòu)下算法的性能.其結(jié)果顯示，當(dāng)移動應(yīng)用各模塊間的數(shù)據(jù)依賴越復(fù)雜，模塊間數(shù)據(jù)傳輸量較大時，本文所設(shè)計(jì)的算法能得到顯著的性能提升.

2 相關(guān)工作

首先對現(xiàn)有的相關(guān)工作進(jìn)行簡要介紹.其中主要包括移動云系統(tǒng)的通用框架以及幾類現(xiàn)有的典型計(jì)算遷移方案決策算法.

2.1 移動云計(jì)算架構(gòu)

在移動云計(jì)算的眾多研究工作中，一個基本的共識便是這些應(yīng)用需要為終端用戶提供與未使用計(jì)算遷移技術(shù)時并無二致的功能，但在遷移后能提供更好的用戶體驗(yàn)，即計(jì)算遷移對用戶透明.為了實(shí)現(xiàn)這一目標(biāo)，研究者們提出了綜合移動設(shè)備、網(wǎng)絡(luò)傳輸以及云中心的分布式移動云計(jì)算架構(gòu).傳統(tǒng)的移動云計(jì)算架構(gòu)中的"云"值得是遠(yuǎn)端的云中心[2-4]，而針對時延敏感型的移動應(yīng)用，有研究者提出利用移動設(shè)備周圍的空閑服務(wù)器(微云[5]，cloudlet)就近為承接從移動終端上遷移出來的計(jì)算.圖1展示了一個結(jié)合了微云和云中心的典型移動云計(jì)算架構(gòu).本文所考慮的場景及所設(shè)計(jì)的算法也適用于這一典型架構(gòu).

圖1 用戶設(shè)備-微云-云數(shù)據(jù)中心架構(gòu)Fig.1 Devices-cloudlet-cloud datacenter hierarchy

然而在移動云計(jì)算的典型架構(gòu)下，不同的研究工作對于分布在移動端和云端的模塊間的通信有著不同的處理模式.早期的研究者們通過采用遠(yuǎn)程過程調(diào)用(RPC)的方式實(shí)現(xiàn)模塊間的遠(yuǎn)程通信[6]，后來基于跨平臺執(zhí)行框架的移動云計(jì)算平臺逐漸成為主流(如基于OSGi Service Platform[7]的Cuckoo[8]、基于Microsoft .NET CLR[6]的MAUI[9]、基于Sprout[10]的Odessa[1]).運(yùn)行于這些平臺上的移動應(yīng)用中的跨網(wǎng)絡(luò)傳輸都交由底層的平臺處理.本文所提出的擴(kuò)展的計(jì)算遷移方案正是為了這種能全局控制網(wǎng)絡(luò)傳輸?shù)囊苿釉朴?jì)算平臺而設(shè)計(jì).

2.2 典型計(jì)算遷移方案決策算法

現(xiàn)有的研究工作針對不同類型移動應(yīng)用的特性，分別設(shè)計(jì)了相應(yīng)的計(jì)算遷移決策算法.如Moo-Ryong Ra[1]等人針對基于數(shù)據(jù)流的應(yīng)用設(shè)計(jì)了以同時提升應(yīng)用吞吐率和響應(yīng)時間為目標(biāo)的決策算法；Zhang Weiwen[11]等人則根據(jù)線性拓?fù)鋺?yīng)用的特性分析設(shè)計(jì)了同時優(yōu)化移動設(shè)備能耗以及完成時間的計(jì)算遷移決策算法；J Flinn[12]等人為延遲敏感的交互式應(yīng)用提出了基于微云(cloudlet)的擴(kuò)展移動云計(jì)算架構(gòu)并在此基礎(chǔ)上設(shè)計(jì)了一系列的算法在保障響應(yīng)時間的前提下提高應(yīng)用的質(zhì)量(即保真度，fidelity).在這些工作中，研究者們都將應(yīng)用的響應(yīng)時間做為應(yīng)用性能的重要衡量指標(biāo)，本文也采用響應(yīng)時間作為衡量指標(biāo).

而在算法的選擇上，有的著重保證算法實(shí)時性而設(shè)計(jì)相應(yīng)的貪心算法(如Odessa[1])、有的著眼于縮小可行解搜索范圍的剪枝或啟發(fā)式方法[13,14]、還有的通過求解最優(yōu)化問題為特殊場景下的應(yīng)用求解最優(yōu)計(jì)算遷移方案[11].本文結(jié)合了搜索剪枝及貪心兩類算法，以期在算法實(shí)時性及得出的遷移方案效率之間獲取平衡.

3 問題建模

接下來分別從設(shè)備及網(wǎng)絡(luò)建模、應(yīng)用的建模及問題描述三方面來闡述本文的研究目標(biāo).

3.1 設(shè)備及網(wǎng)絡(luò)

由于本文著眼于算法的設(shè)計(jì)，故將不同設(shè)備間的差異及特性進(jìn)行簡化.在本文中，統(tǒng)一用每秒處理的百萬指令條數(shù)(MIPS)作為移動終端及云中服務(wù)器的計(jì)算能力的衡量指標(biāo).設(shè)移動設(shè)備的處理能力為Pmobi，云服務(wù)器的處理能力為Pserv.考慮到移動應(yīng)用的模塊間往往有著較為可觀的數(shù)據(jù)傳輸量(如傳感器數(shù)據(jù)或中間結(jié)果)，用帶寬B來衡量移動端與云端之間的網(wǎng)絡(luò)狀況.

此外，不論是計(jì)算資源或是網(wǎng)絡(luò)帶寬資源，本文都不考慮多用戶多應(yīng)用之間的競爭.這一假設(shè)主要基于以下兩點(diǎn)考量：

1)由于云服務(wù)器的計(jì)算能力遠(yuǎn)遠(yuǎn)強(qiáng)于移動終端，故而假設(shè)單個移動設(shè)備只將計(jì)算遷移到一臺其專屬的云中虛擬機(jī)上；

2)在移動端與云端的網(wǎng)絡(luò)通路可簡單分為靠近云數(shù)據(jù)中心的固定網(wǎng)絡(luò)以及接入移動設(shè)備的無線網(wǎng)絡(luò).

相較穩(wěn)定高速的固定網(wǎng)絡(luò)而言，移動設(shè)備接入的無線網(wǎng)絡(luò)往往會成為移動端與云端之間網(wǎng)絡(luò)帶寬的瓶頸.

3.2 可模塊并行的移動應(yīng)用

在大部分的移動云計(jì)算模型中，應(yīng)用的模塊拓?fù)湫畔⒛軌蛲ㄟ^源碼掃描或者開發(fā)者描述而獲得[10,15,16].在移動云計(jì)算中，應(yīng)用常常可以被刻畫為一個有向無環(huán)圖G(V,E)(Directed Acyclic Graph，縮寫為 DAG)，其中每個頂點(diǎn)代表應(yīng)用的一個功能模塊，每條邊(f,g)表示模塊g依賴于模塊f.考慮到絕大部分移動應(yīng)用都會和終端用戶進(jìn)行交互(比如接受用戶輸入和展示結(jié)果)或者依賴移動設(shè)備上的傳感器數(shù)據(jù)，假定有向無環(huán)圖中的源節(jié)點(diǎn)(source nodes)和匯節(jié)點(diǎn)(sink nodes)都是只能在移動設(shè)備上執(zhí)行的不可遷移模塊，而其他的模塊都設(shè)為可遷移模塊.

圖2 假想中最簡單的可模塊并行的應(yīng)用Fig.2 Simplest imaginary module-concurrent MCC application

本文所關(guān)注的可模塊并行的移動應(yīng)用的直觀體現(xiàn)為，有兩個或以上的模塊依賴于同一模塊的數(shù)據(jù)，即在圖中至少有一個節(jié)點(diǎn)f有兩條或以上的出邊(f,g1)、(f,g2).圖中每個節(jié)點(diǎn)都有u∈V都有一個權(quán)重Wnode(u)表征完成這一模塊所需執(zhí)行的百萬指令條數(shù).圖中每條邊(u,v)∈E都有一個權(quán)重Wedge(u,v)用以表示模塊間所需傳輸?shù)臄?shù)據(jù)量.圖2展示了一個假想中最簡單的可模塊并行的移動云應(yīng)用.

3.3 應(yīng)用的局部時間消耗

應(yīng)用的響應(yīng)時間是由應(yīng)用的各模塊執(zhí)行時間及模塊間的數(shù)據(jù)傳輸時間所決定的.而在不同的網(wǎng)絡(luò)條件、移動終端和遷移方案下，同一個應(yīng)用的模塊執(zhí)行時間及數(shù)據(jù)傳輸時間都不盡相同.

簡述其構(gòu)造過程如下：

1) 將圖G中的任意節(jié)點(diǎn)u∈V分割為兩個節(jié)點(diǎn)u和u′放入圖G′，并增加一條邊 (u,u′)， 其邊權(quán)等于此模塊獨(dú)占所處設(shè)備的一個CPU核時所需的執(zhí)行時間，即W(u,u′)=Wnode(u)/(|αu-1|*Pmobi+αu*Pserv)；

2) 對圖G中的任意邊(u,v)∈E，在圖G′中添加邊(u′,v),其邊權(quán)等于此連接獨(dú)占所有網(wǎng)絡(luò)帶寬時所需的數(shù)據(jù)傳輸時間.由于同一設(shè)備上的不同模塊可共享存儲，所以假定其間的通信時間為0.因而有，

3) 增加一個虛擬的源節(jié)點(diǎn)s并以權(quán)重為0的邊指向所有入度為0的節(jié)點(diǎn)，從所有出度為0的節(jié)點(diǎn)連出一條權(quán)重為0的邊指向一個新增加的虛擬匯節(jié)點(diǎn)t.

圖3展示了在特定遷移方案圖2中假想應(yīng)用的AOE圖.

圖3 生成應(yīng)用AOE圖的過程
Fig.3 Process of generating the AOE graph for an application

考慮到現(xiàn)有的移動設(shè)備往往都配備了4至8核的處理器，而一個移動應(yīng)用往往僅有為數(shù)不多的若干個功能模塊，故而假定所有的模塊都可互不沖突地執(zhí)行，即邊權(quán)W(u,u′)就代表了實(shí)際的模塊執(zhí)行時間.

而由于多對跨網(wǎng)絡(luò)的模塊間數(shù)據(jù)傳輸需要競爭有限的網(wǎng)絡(luò)帶寬，邊權(quán)W(u′,v)并不一定反映真實(shí)的網(wǎng)絡(luò)傳輸時間.若在某時間段有k條連接同時傳輸數(shù)據(jù)，則這k條邊都需加大其邊權(quán)以抵消網(wǎng)絡(luò)競爭帶來的影響.具體而言，對圖G′中任意一條傳輸邊(u′,v)∈E′，假定其數(shù)據(jù)傳輸過程由m個連續(xù)的時間片(t1,t2),(t2,t3),…,(tm-1,tm)組成，第i個時間片中固定有ki條連接同時傳輸數(shù)據(jù)，需要從i=1開始對其邊權(quán)進(jìn)行如下更新W(u′,v)=W(u′,v)+(ti+1-ti)*(k-1)/k.由于這些傳輸邊的先后順序除被應(yīng)用的模塊拓?fù)渌s束外，還可被算法人為地設(shè)定.所以需要綜合結(jié)合下一小節(jié)所介紹的數(shù)據(jù)傳輸策略及應(yīng)用的模塊拓?fù)鋬煞矫娴男畔?，在確定每條數(shù)據(jù)傳輸邊的開始時機(jī)之后對這些邊權(quán)進(jìn)行統(tǒng)一調(diào)整，進(jìn)而代表真實(shí)的數(shù)據(jù)傳輸時間.

3.4 數(shù)據(jù)傳輸策略

對于可模塊并行的移動應(yīng)用而言，其部分模塊遷移到云端之后，常常會出現(xiàn)多對模塊間同時進(jìn)行數(shù)據(jù)傳輸?shù)那闆r，且開始時刻、持續(xù)的時間都不同.這也使得對于真實(shí)傳輸時間的估計(jì)和優(yōu)化變得復(fù)雜.由于底層的移動云計(jì)算平臺都能對模塊間的數(shù)據(jù)傳輸進(jìn)行集中控制和規(guī)劃，本文假定模塊間的數(shù)據(jù)傳輸?shù)拈_始順序可由底層平臺控制，而一旦傳輸開始則不能中斷或暫停，同時在傳輸?shù)亩鄺l連接平均地共享網(wǎng)絡(luò)帶寬.

3.5 問題描述

4 算法設(shè)計(jì)

4.1 模塊執(zhí)行地點(diǎn)：限制搜索范圍

在第3.2節(jié)對移動應(yīng)用的建模中一個重要的特性便是，應(yīng)用模塊拓?fù)鋱D中的源節(jié)點(diǎn)和匯節(jié)點(diǎn)都是不可遷移的模塊，以此代表移動應(yīng)用與用戶及所處環(huán)境進(jìn)行交互的特性.在前人在針對線性拓?fù)涞挠?jì)算遷移方案研究[11]中，發(fā)現(xiàn)在起、止模塊都在移動設(shè)備上執(zhí)行時，若遷移部分模塊至云端能提升應(yīng)用性能，則最優(yōu)的遷移方案一定是線性拓?fù)渲杏星覂H有一段連續(xù)的若干模塊同時遷移到云端.也就是說，移動端和云端之間只會依次有一次上行和下行的數(shù)據(jù)傳輸.這一結(jié)論稍作轉(zhuǎn)換則可得到：若模塊u和模塊v都被決策為在云上執(zhí)行，則這兩模塊之間的其他模塊都應(yīng)在云上執(zhí)行.在直觀上也很好理解，由于云服務(wù)器的計(jì)算能力遠(yuǎn)強(qiáng)于移動終端，若模塊u和模塊v之間的某模塊被決策于移動端執(zhí)行，通過網(wǎng)絡(luò)來回傳輸數(shù)據(jù)的耗時以及移動設(shè)備上有限的計(jì)算能力都將延長應(yīng)用總體的響應(yīng)時間.

算法1. DFS遍歷不同模塊部署方案

//最初調(diào)用時可遷移模塊都在云端

//最終的擴(kuò)展計(jì)算遷移方案

function:DFSExecLoc

//記錄探索到的最優(yōu)遷移方案

then

endif

αi←0

endif

endforeach

endfunction

4.2 數(shù)據(jù)傳輸策略：貪心算法

然而，如圖2所示，可模塊并行的應(yīng)用的一個典型特征就是：一個模塊執(zhí)行完畢后需要將相應(yīng)的中間數(shù)據(jù)發(fā)送個多個后續(xù)模塊.上述兩種傳統(tǒng)的貪心策略在這種常出現(xiàn)多條傳輸連接的數(shù)據(jù)同時準(zhǔn)備完畢的場景下，要么多條鏈接同時發(fā)送互相競爭，要么隨機(jī)選擇一條連接進(jìn)行發(fā)送.本文在這兩種傳統(tǒng)的貪心策略之外，嘗試為可模塊并行的應(yīng)用設(shè)計(jì)更為合理高效的貪心策略.

通過借鑒AOE圖中關(guān)鍵路徑算法的思想，將同一個模塊發(fā)出的多條跨網(wǎng)絡(luò)的數(shù)據(jù)傳輸連接的最晚開始時間lst都計(jì)算出來并進(jìn)行比較，每次選擇最晚開始時間lst最早的一條連接進(jìn)行數(shù)據(jù)傳輸.每次按照最晚開始時間lst最早選出來的傳輸邊是最為緊要的一條邊，有理由期待優(yōu)先傳送這一條邊上的數(shù)據(jù)會比隨機(jī)選擇一條邊傳輸或?qū)捑鶆蚍峙涞玫礁痰膽?yīng)用響應(yīng)時間.

進(jìn)一步思考會發(fā)現(xiàn)，上述簡單直接的貪心策略還有進(jìn)一步提升的空間.如圖4所示的特殊情況，雖然兩條邊的最遲開始時間相同，但顯然優(yōu)先啟動邊(u′,v1)是更為明智的選擇.這里的貪心思路在于優(yōu)先傳送有著更少數(shù)據(jù)量的邊，從而使得后續(xù)能夠充分并行的模塊執(zhí)行盡早執(zhí)行.因此，將貪心算法改進(jìn)為以下形式：對從同一個模塊發(fā)出的多條傳輸邊，分別計(jì)算其作為下一條傳輸邊時(其他傳輸邊都等待其傳輸結(jié)束后才開始)，應(yīng)用響應(yīng)時間的縮短量，并選用能最大縮短應(yīng)用響應(yīng)時間的一條邊作為下一條傳輸邊.

然而在具體實(shí)現(xiàn)時，由于AOE圖中各傳輸邊的權(quán)值需要與這些邊的先后次序進(jìn)行同步的更新，這將使得上述算法中每枚舉一條傳輸就需要有額外O(m)的邊權(quán)更新復(fù)雜度，這顯然是不可接受的.因此，在實(shí)際實(shí)現(xiàn)中，選用固定當(dāng)前AOE邊權(quán)，將帶來最少響應(yīng)時間增加的邊作為下一條發(fā)起傳輸?shù)倪?假設(shè)這一模塊的所有出邊序列為R，(ui′,vi)和(uj′,vj)分別代表R中的第i和第j條數(shù)據(jù)傳輸邊，可以根據(jù)下式來計(jì)算出應(yīng)該首先傳輸?shù)倪叄?/p>

圖4 并行數(shù)據(jù)傳輸?shù)臉O端情況Fig.4 Extreme case of concurrent data transmission

按照此式則可輕松得出圖4所示的例子中，邊(u′,v1)相較邊(u′,v2)有著更高的優(yōu)先級.算法2展示了這一貪心算法的主要邏輯.

算法2.貪心算法求得數(shù)據(jù)傳輸時機(jī)

//當(dāng)前探索的應(yīng)用模塊部署方案

function:GreedyFindBeta

//將所有跨網(wǎng)絡(luò)數(shù)據(jù)傳輸邊按est排序

L←GetSortedTransEdges(G′)

whileL!= NULLdo

//獲得一個模塊的多條出邊序列R

whileL[i].est=L[0].estdo

ifL[i].src=L[0].srcthen

R.insert(L[i])

endif

i←i+1

endwhile

ifR=NULLthen

L.deleteFirst()

else

L.deleteList(R)

endif

endwhile

endfunction

5 實(shí)驗(yàn)評估

為了驗(yàn)證所設(shè)計(jì)的算法的有效性，設(shè)計(jì)了一系列的仿真實(shí)驗(yàn)對其進(jìn)行測試.

5.1 實(shí)驗(yàn)設(shè)置

在仿真試驗(yàn)中，固定應(yīng)用的可遷移模塊數(shù)為10，足以覆蓋大部分的移動應(yīng)用.而其他的各種參數(shù)，如應(yīng)用的模塊拓?fù)洹⒏髂K的計(jì)算量、模塊間的數(shù)據(jù)傳輸量、移動設(shè)備及云服務(wù)器的處理能力和移動端于云端之間的可用帶寬等，都是由腳本自動隨機(jī)產(chǎn)生的.而在生成這些隨機(jī)參數(shù)的過程中，選取了兩個有代表性的變量進(jìn)行控制，以此測試算法在不同場景下的性能表現(xiàn)，其分別是：應(yīng)用各模塊間數(shù)據(jù)傳輸?shù)氖杳艹潭?、模塊計(jì)算時間與模塊間數(shù)據(jù)傳輸時間的比值.其具體的定義將在隨后各小節(jié)詳細(xì)介紹.在所有的試驗(yàn)中，每組實(shí)驗(yàn)都會對的同樣配置下隨機(jī)生成的100個應(yīng)用進(jìn)行測試，并取其平均值作為其結(jié)果.

在各組實(shí)驗(yàn)中，主要比較本文所涉及的貪心算法和傳統(tǒng)的兩種貪心算法，即"即時發(fā)送、網(wǎng)絡(luò)公平競爭"和"先來先服務(wù)、網(wǎng)絡(luò)獨(dú)占".算法的結(jié)果都以比值的形式呈現(xiàn)，具體而言是當(dāng)前算法得出的應(yīng)用響應(yīng)時間除以"即時發(fā)送、網(wǎng)絡(luò)公平競爭"算法得出的響應(yīng)時間.這一比值越小則表明算法的結(jié)果越好.由于上述三種貪心方式都可能不同情況下獲得更短的響應(yīng)時間，所以在實(shí)際應(yīng)用中可將這三種貪心算法所得的遷移方案進(jìn)行比較后，選取有著最短響應(yīng)時間的遷移方案進(jìn)行部署.將這一算法的結(jié)果也列入實(shí)驗(yàn)對比之中.

此外，還根據(jù)應(yīng)用的模塊拓?fù)浼熬W(wǎng)絡(luò)帶寬、設(shè)備處理能力等，為每組實(shí)驗(yàn)計(jì)算其響應(yīng)時間比值的松弛下界.這一松弛下界的取值等于放松兩種不同的約束得到的兩個松弛下界中較大的一個.具體而言，這兩個簡單的松弛下界是通過:

1)假設(shè)移動端到云端之間有無窮多條帶寬為B的網(wǎng)絡(luò)通路，模塊間的任一數(shù)據(jù)傳輸都可獨(dú)占一條通路進(jìn)行數(shù)據(jù)傳輸，從而得到一個簡單的松弛下界.

2)假設(shè)遷移到云端的模塊執(zhí)行時間都為零，故這一響應(yīng)時間的松弛下界等于網(wǎng)絡(luò)傳輸?shù)目倳r間(總數(shù)據(jù)量/帶寬B)與不可遷移模塊中計(jì)算量最小的兩個模塊的執(zhí)行時間總和.

通過取這兩個松弛下界中較大的一個作為響應(yīng)時間的松弛下界，可以大致估計(jì)各貪心算法的結(jié)果距最優(yōu)解的差距.

5.2 模塊間依賴程度對性能的影響

采用模塊間數(shù)據(jù)傳輸邊的數(shù)量除以全連通圖中邊的總數(shù)量的比值LinkRate來衡量應(yīng)用各模塊間的依賴程度.圖5顯示了在不同LinkRate下，各貪心算法的所得響應(yīng)時間與"即時發(fā)送、網(wǎng)絡(luò)公平競爭"算法所得響應(yīng)時間的比值RespTimeRate.由于"即時發(fā)送、網(wǎng)絡(luò)公平競爭"算法是目前移動云計(jì)算的研究工作中最為廣泛運(yùn)用的數(shù)據(jù)傳輸策略，故而可認(rèn)為(1-RespTimeRate)就代表了比現(xiàn)行通用方法性能提升的比例.

圖5 不同的LinkRate下算法的性能Fig.5 Performance of greedy algorithms under various LinkRate

由圖5可知，本文設(shè)計(jì)的算法要優(yōu)于傳統(tǒng)通用的貪心算法，當(dāng)綜合比較多種貪心算法的結(jié)果后選擇最優(yōu)的遷移方案，則在一定條件下能縮短5%左右的響應(yīng)時間.當(dāng)LinkRate很小，即模塊間的數(shù)據(jù)傳輸邊非常少時，各貪心算法的性能與平均分配帶寬的方案相差不大，這是因?yàn)樵跀?shù)據(jù)傳輸很稀疏的情況下，同時有多條連接同時傳輸?shù)母怕室泊蟠蠼档停蚨y以體現(xiàn)出不同算法之間的的差異.隨著模塊間數(shù)據(jù)傳輸?shù)谋壤龃?，可模塊并行的程度也相應(yīng)增加，本文所設(shè)計(jì)算法的優(yōu)勢開始逐漸體現(xiàn).直到近乎任意兩模塊之間都有數(shù)據(jù)依賴關(guān)系時(LinkRate=1)，為數(shù)據(jù)傳輸?shù)拈_始時機(jī)進(jìn)行優(yōu)化的積極影響才開始削弱.

值得注意的是，綜合了三種貪心策略的算法在LinkRate較小和較大時都與算法所能達(dá)到的松弛下界逼近，說明在這些情況下，這一算法幾乎能夠獲得最優(yōu)的性能.而在LinkRate處于適中的位置時，由于松弛下界的RespTimeRate顯著降低，這是因?yàn)樗捎玫乃沙谙陆缡怯蓛山M簡單的松弛下界中取較大得來的，LinkRate較小時，"無窮多條網(wǎng)絡(luò)通路"這一松弛下界距下確界較近，而LinkRate較大時，則是"忽略云端模塊執(zhí)行開銷"的松弛下界距下確界較近.而當(dāng)LinkRate大小適中時，這兩種簡單松弛下界距下確界都較遠(yuǎn)，故而使得圖中的松弛下界快速下降，并不意味著本文所設(shè)計(jì)的算法在這一場景下距最優(yōu)解有更大的差距.

圖6 不同的LinkRate下所有算法的執(zhí)行時間和Fig.6 Total execution time of all three greedy algorithms under various LinkRate

另一方面，比值LinkRate的增大等價于應(yīng)用AOE圖中的邊數(shù)m的增多，這顯然會帶來算法執(zhí)行時間的增長.圖6展示了在不同LinkRate下，綜合的貪心算法在個人PC機(jī)(Intel Core i7-3770)上所消耗的時間.由于擴(kuò)展的遷移方案常常是在云端進(jìn)行決策的，且實(shí)際的應(yīng)用中模塊間的依賴都較低(互相緊密依賴的功能/函數(shù)往往都被打包進(jìn)一個模塊中)，故而可以相信這一算法能夠滿足移動云環(huán)境下的實(shí)時性需求(幾秒內(nèi)返回結(jié)果).

5.3 計(jì)算或通信密集對性能的影響

采用一對模塊間的數(shù)據(jù)傳輸在獨(dú)占網(wǎng)絡(luò)帶寬場景下的期望時間除以在移動設(shè)備上獨(dú)占一個CPU核計(jì)算一個模塊所花的期望時間的比值TransCompRate來衡量應(yīng)用對通信資源和計(jì)算資源的側(cè)重.圖7顯示了在不同TransCompRate下，各貪心算法的RespTimeRate.由圖7可知，當(dāng)應(yīng)用是典型的通信密集型應(yīng)用時(與網(wǎng)絡(luò)狀況不佳的情況等價)，各決策算法都傾向于不遷移任何應(yīng)用模塊以避免高昂的通信開銷，這時各算法之間的差距很小(TransCompRate很小時).而隨著應(yīng)用中計(jì)算所占比重的增加(或網(wǎng)絡(luò)狀況的好轉(zhuǎn))，本文所設(shè)計(jì)算法的優(yōu)勢開始逐漸體現(xiàn)出來(TransCompRate適中).直到應(yīng)用逐漸體現(xiàn)出計(jì)算密集型應(yīng)用的特征(或網(wǎng)絡(luò)狀況極好)，數(shù)據(jù)傳輸在應(yīng)用整體的響應(yīng)時間中所占的比重越來越低，這時各個貪心算法之間的差距開始緩慢的縮小(TransCompRate較大).但不論在何種情況，本文所設(shè)計(jì)的算法以及綜合多種貪心算法后的綜合算法都能顯著地降低應(yīng)用的響應(yīng)時間.

圖7 不同TransComRate下各算法的性能Fig.7 Performance of greedy algorithms under varous TransCompRate

6 結(jié) 論

本文針對移動云計(jì)算中可模塊并行的移動應(yīng)用，探討了其特性并提出在對應(yīng)用進(jìn)行計(jì)算遷移時，不光決策應(yīng)用各模塊的執(zhí)行地點(diǎn)，還同時優(yōu)化各跨網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)捻樞?，從而進(jìn)一步降低可模塊并行應(yīng)用的響應(yīng)時間.為了應(yīng)對移動環(huán)境快速多變的特性，本文設(shè)計(jì)了高效的貪心決策算法，在滿足實(shí)時性需求的前提下顯著降低應(yīng)用的響應(yīng)時間.通過一系列的仿真實(shí)驗(yàn)驗(yàn)證，本文設(shè)計(jì)的貪心算法相較傳統(tǒng)的公平競爭及先來先服務(wù)的數(shù)據(jù)傳輸方案，能縮短約5%的響應(yīng)時間.