劉偉，熊曙，杜薇，王偉

（1. 武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070；2. 交通物聯(lián)網(wǎng)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070；3. 同濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，上海 200092）

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，以智能手機(jī)為代表的移動(dòng)設(shè)備越來越普及，據(jù)國際電信聯(lián)盟數(shù)據(jù)顯示，在 2017年全球智能手機(jī)擁有量預(yù)計(jì)達(dá)到43億[1]。利用種類繁多的傳感器，移動(dòng)設(shè)備上產(chǎn)生了諸多如手勢(shì)識(shí)別[2]、人臉識(shí)別[3]等移動(dòng)數(shù)據(jù)流應(yīng)用程序，這類應(yīng)用對(duì)延遲比較敏感，運(yùn)行時(shí)需要大量的計(jì)算資源，且會(huì)導(dǎo)致移動(dòng)設(shè)備大量消耗電量。然而移動(dòng)設(shè)備的電池容量、計(jì)算能力、存儲(chǔ)空間等資源比較有限，在運(yùn)行此類應(yīng)用時(shí)，移動(dòng)設(shè)備的電量面臨著嚴(yán)峻的考驗(yàn)。移動(dòng)云計(jì)算（MCC，mobile cloud computing）的出現(xiàn)為突破移動(dòng)設(shè)備資源限制提供了可能[4]，將應(yīng)用的部分計(jì)算密集型任務(wù)通過計(jì)算卸載技術(shù)[5]卸載到遠(yuǎn)程的云計(jì)算中心上執(zhí)行，有效地降低了移動(dòng)設(shè)備的電量消耗，如 MAUI（mobile assistance using infrastructure）[6]、CloneCloud[7]、Odessa[8]等。

然而，遠(yuǎn)程云計(jì)算中心距離移動(dòng)用戶較遠(yuǎn)，通過廣域網(wǎng)連接將會(huì)帶來較高的網(wǎng)絡(luò)延遲[9]，很難保證移動(dòng)數(shù)據(jù)流應(yīng)用的服務(wù)質(zhì)量要求。為此，美國卡內(nèi)基梅隆大學(xué) Satayanarayanan教授[10]首次提出Cloudlet（微云）這一概念，它是距離移動(dòng)設(shè)備較近且資源豐富的一臺(tái)或多臺(tái)機(jī)器組成的計(jì)算機(jī)集群。移動(dòng)設(shè)備可以通過局域網(wǎng)與Cloudlet直接相連，擁有帶寬大和延遲低的優(yōu)勢(shì)[11]。因此，這種計(jì)算模式將移動(dòng)數(shù)據(jù)流應(yīng)用卸載到Cloudlet上執(zhí)行，能夠獲得良好的用戶體驗(yàn)。

隨著移動(dòng)云計(jì)算的發(fā)展和普及，各商家或單位部署有不同計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)等資源的 Cloudlet，可以同時(shí)為區(qū)域內(nèi)的用戶提供服務(wù)。用戶在運(yùn)行諸如人臉識(shí)別等移動(dòng)數(shù)據(jù)流應(yīng)用時(shí)，如何依據(jù)周圍Cloudlet收集的移動(dòng)設(shè)備、應(yīng)用特征和網(wǎng)絡(luò)狀況等信息，為應(yīng)用選擇合適的Cloudlet進(jìn)行網(wǎng)絡(luò)連接和計(jì)算卸載，以延長(zhǎng)移動(dòng)設(shè)備的續(xù)航時(shí)間和提高應(yīng)用程序的性能成為亟待解決的問題。

針對(duì)這一問題，研究者們從不同的角度展開了工作。然而，這些工作大多只為移動(dòng)設(shè)備上的應(yīng)用選擇單個(gè)Cloudlet進(jìn)行計(jì)算卸載，對(duì)于擁有較多并行組件的移動(dòng)數(shù)據(jù)流應(yīng)用，如光學(xué)字符識(shí)別、QR二維碼應(yīng)用[12]、對(duì)象識(shí)別[13]等，性能提升有限。為此，本文提出了一種可以充分利用多個(gè)Cloudlet資源來最大化移動(dòng)數(shù)據(jù)流應(yīng)用并行執(zhí)行效率的Cloudlet選擇策略，為用戶帶來更短的應(yīng)用完成時(shí)間和更低的移動(dòng)設(shè)備能量消耗。本文主要貢獻(xiàn)如下。

1） 建立了移動(dòng)數(shù)據(jù)流應(yīng)用的 Cloudlet選擇問題的系統(tǒng)模型，旨在最小化應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗，同時(shí)將問題定義為雙目標(biāo)的組合優(yōu)化問題，并證明該問題是NP-hard問題。

2） 設(shè)計(jì)了一個(gè)動(dòng)態(tài)調(diào)整的適應(yīng)度函數(shù)，根據(jù)移動(dòng)設(shè)備的剩余電量調(diào)整應(yīng)用完成時(shí)間與移動(dòng)設(shè)備能耗的權(quán)值，進(jìn)而采用線性加權(quán)法將該雙目標(biāo)問題歸一成單目標(biāo)問題。

3） 提出了一種基于化學(xué)反應(yīng)優(yōu)化算法的Cloudlet選擇策略CROCS（chemical reaction optimization Cloudlet selection strategy）。該策略能夠在滿足組件間依賴關(guān)系的前提下，充分利用移動(dòng)數(shù)據(jù)流應(yīng)用中可以并行執(zhí)行的組件，提高了應(yīng)用性能。

2 研究動(dòng)機(jī)

本文所提出的移動(dòng)數(shù)據(jù)流應(yīng)用的Cloudlet選擇策略的主要思想是將移動(dòng)數(shù)據(jù)流應(yīng)用的并行組件分散到多個(gè)Cloudlet上執(zhí)行，以提高應(yīng)用的執(zhí)行效率，減少完成時(shí)間。然后，將通過一個(gè)具有一般拓?fù)浣Y(jié)構(gòu)的移動(dòng)數(shù)據(jù)流應(yīng)用程序——光學(xué)字符識(shí)別（OCR，optical character recognition）在多Cloudlet環(huán)境中運(yùn)行的例子驗(yàn)證本文思想的正確性。

光學(xué)字符識(shí)別應(yīng)用程序通過檢查輸入圖片中的手寫體或者印刷體字符，經(jīng)過明暗處理后確定文字的形狀，然后采用字符識(shí)別方法將其翻譯成計(jì)算機(jī)文字。其應(yīng)用程序結(jié)構(gòu)如圖1所示，其中組件v0為開始組件，表示獲取輸入圖片；組件v1表示一維最大熵法計(jì)算閾值；組件v2表示最大類間方差法計(jì)算閾值；組件v3表示迭代法計(jì)算閾值；組件v4表示選擇二值化；組件v5表示識(shí)別過程組件v6為結(jié)束組件，表示輸出結(jié)果。組件v1、v2和v3為可以同時(shí)在不同 Cloudlet或者移動(dòng)設(shè)備上執(zhí)行的并行組件。其中各個(gè)組件的計(jì)算量分別為0、3 600、3 800、3 400、1 800、14 200和0（單位為百萬條指令），邊的權(quán)值表示組件之間的數(shù)據(jù)傳輸量大小，單位是KB。

圖1 光學(xué)字符識(shí)別應(yīng)用程序結(jié)構(gòu)

如圖2所示，當(dāng)用戶運(yùn)行該應(yīng)用程序時(shí)，周圍有3個(gè)具有相同計(jì)算能力的Cloudlet（用C1、C2和C3表示）可作為計(jì)算節(jié)點(diǎn)，其中C1作為距離用戶最近的代理 Cloudlet，用戶會(huì)向其發(fā)送計(jì)算卸載請(qǐng)求，同時(shí)將移動(dòng)設(shè)備的硬件信息發(fā)送給C1以備其做出選擇策略。然后代理Cloudlet依據(jù)周圍Cloudlet之間的帶寬與距離、移動(dòng)設(shè)備與各Cloudlet的計(jì)算能力與最早開始時(shí)間、代理Cloudlet與移動(dòng)設(shè)備之間的距離和帶寬等信息做出合適的選擇策略[14]，Cloudlet端和移動(dòng)設(shè)備依據(jù)選擇策略協(xié)同執(zhí)行計(jì)算任務(wù)，最后將應(yīng)用程序的結(jié)果返回到移動(dòng)設(shè)備。設(shè)置移動(dòng)設(shè)備與Cloudlet的計(jì)算能力分別為40 000和80 000，單位是每秒鐘執(zhí)行百萬指令數(shù)，與不同Cloudlet之間的帶寬為8 Mbit/s，Cloudlet之間的帶寬為240 Mbit/s。采用不同選擇方案對(duì)應(yīng)的應(yīng)用完成時(shí)間如表1所示。

圖2 移動(dòng)數(shù)據(jù)流應(yīng)用Cloudlet選擇場(chǎng)景

表1 不同選擇方案對(duì)應(yīng)的應(yīng)用完成時(shí)間

通過以上例子表明，應(yīng)用的完成時(shí)間隨著不同的選擇方案而不同，并且其中并行組件較為分散的方案（如方案1、2和4）相較于其他并行組件集中的方案（如方案3、5和6）對(duì)應(yīng)的完成時(shí)間較低。因此可以通過選取合適的選擇方案加快應(yīng)用執(zhí)行速度。下面基于這一思想建立相應(yīng)模型、設(shè)計(jì)相應(yīng)算法，找出合適的選擇策略，并通過實(shí)驗(yàn)驗(yàn)證本文思想的正確性。

3 相關(guān)工作

隨著人臉識(shí)別等移動(dòng)數(shù)據(jù)流應(yīng)用越來越流行和移動(dòng)云計(jì)算的普及，用戶在運(yùn)行移動(dòng)數(shù)據(jù)流應(yīng)用時(shí)將常處于多Cloudlet環(huán)境中，如何選擇Cloudlet為用戶提供良好的服務(wù)是一個(gè)亟需解決的問題。在已有的工作中，文獻(xiàn)[15]針對(duì)非集中式部署的多Cloudlet環(huán)境，提出了一種應(yīng)用資源限制的選擇策略，選擇滿足應(yīng)用對(duì)資源需求的Cloudlet進(jìn)行計(jì)算卸載。文獻(xiàn)[16]依據(jù)距離進(jìn)行選擇，為應(yīng)用優(yōu)先選擇距離用戶最近的Cloudlet卸載應(yīng)用。文獻(xiàn)[17]考慮到離用戶最近的Cloudlet未必能提供最好的計(jì)算能力和良好的網(wǎng)絡(luò)質(zhì)量，提出選擇2個(gè)Cloudlet，其中一個(gè)擁有較好的網(wǎng)絡(luò)連接，另一個(gè)擁有較好的計(jì)算能力來保證執(zhí)行應(yīng)用的性能。文獻(xiàn)[18]則基于不同應(yīng)用對(duì)資源需求具有差異化的特點(diǎn)，對(duì)已發(fā)現(xiàn)的Cloudlet按照滿足應(yīng)用特點(diǎn)的服務(wù)質(zhì)量屬性進(jìn)行排名，依據(jù)該排名選擇合適的Cloudlet進(jìn)行卸載應(yīng)用。文獻(xiàn)[19]則考慮應(yīng)用卸載過程中移動(dòng)設(shè)備的能量消耗，選擇移動(dòng)設(shè)備能量消耗最低的Cloudlet。Mukherjee等[14]為了避免文獻(xiàn)[16]中某些任務(wù)可能需要卸載到遠(yuǎn)程云帶來較高延遲的情況，提出將最近的Cloudlet作為代理服務(wù)器，代理服務(wù)器通過廣播請(qǐng)求獲得周圍Cloudlet的信息，依據(jù)獲得的信息選擇最低移動(dòng)設(shè)備能耗或最低完成時(shí)間的Cloudlet 。文獻(xiàn)[20]則將不同的應(yīng)用部署到不同的Cloudlet上，而后依據(jù)應(yīng)用種類選擇 Cloudlet，系統(tǒng)中的應(yīng)用性能得到了進(jìn)一步的提升。

以上這些工作都沒有考慮具有一般拓?fù)浣Y(jié)構(gòu)的移動(dòng)數(shù)據(jù)流應(yīng)用有許多并行部分，可以在多個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行。文獻(xiàn)[21]利用這些并行部分，使應(yīng)用的部分組件在移動(dòng)設(shè)備上執(zhí)行，部分組件在 Cloudlet上執(zhí)行，提升了應(yīng)用執(zhí)行效率，進(jìn)而減小了應(yīng)用的完成時(shí)間。中國科學(xué)技術(shù)大學(xué)的劉煒清等[22]針對(duì)單個(gè) Cloudlet與移動(dòng)設(shè)備的帶寬有限從而限制了移動(dòng)數(shù)據(jù)流應(yīng)用吞吐量的問題，提出利用將部分組件的實(shí)例放置到其他 Cloudlet上執(zhí)行，提高了應(yīng)用的吞吐量。與之對(duì)比，本文工作主要是充分利用多個(gè)Cloudlet的資源使移動(dòng)數(shù)據(jù)流應(yīng)用的并行組件同時(shí)執(zhí)行，提升了應(yīng)用執(zhí)行效率，使移動(dòng)數(shù)據(jù)流應(yīng)用的完成時(shí)間最小化，降低移動(dòng)設(shè)備能耗。

4 系統(tǒng)模型

本文的目標(biāo)是尋找一種適合移動(dòng)數(shù)據(jù)流應(yīng)用的Cloudlet選擇策略以最小化應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能量消耗。為解決這一問題，首先需要對(duì)相關(guān)概念和移動(dòng)數(shù)據(jù)流應(yīng)用進(jìn)行建模，進(jìn)而建立相應(yīng)的完成時(shí)間和移動(dòng)設(shè)備能耗建立模型。

4.1 相關(guān)概念模型

1） 移動(dòng)設(shè)備

移動(dòng)設(shè)備可以用一個(gè)八元組表示,mobile={power, capacity,Pidle,Pcomp,Pts,Ptr,J,DJ}，其中，power表示移動(dòng)設(shè)備的剩余電量，capacity表示移動(dòng)設(shè)備的計(jì)算能力（單位是MIPS），Pidle表示移動(dòng)設(shè)備CPU處于空閑狀態(tài)時(shí)的功率，Pcomp表示移動(dòng)設(shè)備CPU處于計(jì)算狀態(tài)時(shí)的功率，Pts表示移動(dòng)設(shè)備發(fā)送數(shù)據(jù)的功率，Ptr表示移動(dòng)設(shè)備接收數(shù)據(jù)的功率，J表示代理Cloudlet編號(hào)，DJ表示移動(dòng)設(shè)備與代理Cloudlet的距離。

2） Cloudlet

系統(tǒng)中的Cloudlet可以通過Cloudlets=（C,D）表示，C表示Cloudlet的集合，D表示Cloudlet之間的關(guān)系。C={Cloudlet1, Cloudlet2,…, Cloudletm}，|C|=m。對(duì)于C中每一個(gè) Cloudlet可以使用一個(gè)三元組表示，Cloudletj={j, capacityj,Qj}，其中j表示編號(hào)，capacityj表示計(jì)算能力大?。▎挝皇荕IPS），Qj表示最早開始執(zhí)行時(shí)間。

由于系統(tǒng)中存在多個(gè) Cloudlet，它們之間的關(guān)系主要通過距離體現(xiàn)，所以采用一個(gè)矩陣D表示其距離關(guān)系，其中，di,j表示Cloudleti與 Cloudletj之間的距離（單位是 m），有di,j=dj,i，且當(dāng)i=j時(shí)，di,j=0。

3） 網(wǎng)絡(luò)連接

網(wǎng)絡(luò)連接主要由2個(gè)部分組成，分別是移動(dòng)設(shè)備與代理Cloudlet之間的網(wǎng)絡(luò)，以及Cloudlet之間的網(wǎng)絡(luò)。移動(dòng)設(shè)備與代理Cloudlet之間的上傳和下載帶寬分別為Bu和Bd；Cloudlet之間通過帶寬相同的有線網(wǎng)絡(luò)連接，帶寬單位是B。

4） Cloudlet選擇策略

移動(dòng)數(shù)據(jù)流應(yīng)用中的每一個(gè)組件可以在Cloudlet或移動(dòng)設(shè)備上執(zhí)行，對(duì)于一個(gè)由n個(gè)組件組成的移動(dòng)數(shù)據(jù)流應(yīng)用，其Cloudlet選擇策略可以使用一個(gè)n維向量表示，X={x1,x2, … ,xn}，xi∈[0,m]，其中xi表示第i個(gè)組件的執(zhí)行位置。當(dāng)xi=0時(shí)，表示該組件在移動(dòng)設(shè)備上執(zhí)行，當(dāng)xi∈[1,m]時(shí)，表示該組件在Cloudletxi上執(zhí)行。

4.2 移動(dòng)數(shù)據(jù)流應(yīng)用模型

移動(dòng)數(shù)據(jù)流應(yīng)用可以建模成有向無環(huán)圖G（V,E），其中V={v1,v2, … ,vn}表示組件的集合，E表示組件之間的依賴關(guān)系。對(duì)于V中每一個(gè)組件vi可以用一個(gè)三元組表示，vi={i,xi, Ii}，其中i為組件編號(hào)，xi為組件vi選擇的 Cloudlet位置，Ii為組件vi的指令數(shù)。E中每條邊的權(quán)重dataj,k表示組件vj和vk之間傳輸?shù)臄?shù)據(jù)量大小。如圖1所示，入口組件v0和出口組件v6表示虛擬組件，且這2個(gè)組件必須在移動(dòng)設(shè)備上執(zhí)行。

4.3 應(yīng)用完成時(shí)間模型

完成時(shí)間[8]是移動(dòng)數(shù)據(jù)流應(yīng)用一個(gè)重要的性能指標(biāo)，表示應(yīng)用程序從數(shù)據(jù)輸入到結(jié)果輸出的時(shí)間。完成時(shí)間越低表示應(yīng)用的響應(yīng)速度越快，用戶體驗(yàn)越好。

對(duì)于Cloudlet選擇策略X，因?yàn)閼?yīng)用的組件可以在不同的位置執(zhí)行，執(zhí)行時(shí)組件之間會(huì)產(chǎn)生數(shù)據(jù)傳輸時(shí)間和傳播時(shí)間，其中包含并行組件在多個(gè)Cloudlet或移動(dòng)設(shè)備上并行執(zhí)行產(chǎn)生的額外通信時(shí)間開銷。對(duì)于組件vk和vi之間的數(shù)據(jù)傳輸時(shí)間transk,i可以由式（1）計(jì)算。

其中，當(dāng)xk=0且xi≠0,J時(shí)，表示組件vk在移動(dòng)端執(zhí)行，vi在除代理 CloudletJ之外的其他CloudLetxi上執(zhí)行，其數(shù)據(jù)傳輸時(shí)間由 2個(gè)部分組成：1） 數(shù)據(jù)從移動(dòng)設(shè)備傳輸?shù)酱?CloudletJ的時(shí)間，2） 數(shù)據(jù)由代理CloudletJ傳輸?shù)紺loudletxi上的時(shí)間。當(dāng)xk=0且xi=J時(shí)，即組件vk在移動(dòng)設(shè)備上執(zhí)行，組件vi在代理CloudletJ上執(zhí)行，其數(shù)據(jù)傳輸時(shí)間為組件間的數(shù)據(jù)量 datak,i與移動(dòng)設(shè)備上傳數(shù)據(jù)帶寬Bu的比值。當(dāng)xk,xi∈[1,m]且xi≠xk時(shí)，即組件vk和組件vi在不同的Cloudlet上執(zhí)行，其數(shù)據(jù)傳輸時(shí)間為組件間的數(shù)據(jù)量 datak,i與Cloudlet之間的帶寬 B的比值。當(dāng)xk≠0,J且xi=0時(shí)，即組件 vk在除了代理 CloudletJ之外的CloudLetxk上執(zhí)行，組件 vi在移動(dòng)設(shè)備上執(zhí)行，其數(shù)據(jù)傳輸時(shí)間包括數(shù)據(jù)從Cloudletxk傳輸?shù)酱鞢loudletJ的時(shí)間和數(shù)據(jù)從代理CloudletJ傳輸?shù)揭苿?dòng)設(shè)備的時(shí)間。當(dāng)xk=J且xi=0時(shí)，表示組件vk在代理CloudletJ上執(zhí)行，組件vi在移動(dòng)設(shè)備上執(zhí)行，其數(shù)據(jù)傳輸時(shí)間為組件間的數(shù)據(jù)傳輸量datak,i與移動(dòng)設(shè)備下載數(shù)據(jù)的帶寬的比值。當(dāng)xi=xk時(shí)，表示組件vk和組件vi在同一位置執(zhí)行，其數(shù)據(jù)傳輸時(shí)間為0。

組件vk和vi之間的傳播時(shí)間tpropk,i可以由式（2）得出。

其中，S為傳播速度，大小為2×108m/s[23]。當(dāng)xk=0，xi∈[1,m]時(shí)，其數(shù)據(jù)傳播時(shí)間包括2個(gè)部分：1） 組件vk所在的移動(dòng)設(shè)備與代理CloudletJ之間的傳播時(shí)間;2） 代理CloudletJ與組件 vi所在Cloudletxi之間的傳播時(shí)間。當(dāng) xk, xi∈[1,m]且 xi≠ xk，即組件 vk和vi在不同Cloudlet上執(zhí)行，其傳播時(shí)間為兩組件所選擇執(zhí)行位置的距離與傳播速度比值。當(dāng)xk∈[1,m],xi=0時(shí)，其數(shù)據(jù)傳播時(shí)間包括組件 vk所選擇的Cloudletxk與代理 CloudletJ之間的傳播時(shí)間和代理CloudletJ與組件vi所在移動(dòng)設(shè)備的傳播時(shí)間。當(dāng)xk=xi時(shí)，即組件vk和vi在同一個(gè)位置執(zhí)行，其傳播時(shí)間為0。

由此可以得到組件vi的開始執(zhí)行時(shí)間STi和完成時(shí)間 FTi的計(jì)算式，如式（3）和式（4）所示。其中，使用pred（i）表示vi的前驅(qū)組件的集合。transk,i和tpropk,i分別表示組件vk和vi之間的數(shù)據(jù)傳輸時(shí)間和數(shù)據(jù)傳播時(shí)間。RTxi表示Cloudletxi的最早開始執(zhí)行時(shí)間，初始為Qxi，在組件選擇執(zhí)行位置后對(duì)RTxi進(jìn)行更新。RTm表示移動(dòng)設(shè)備的最早開始執(zhí)行時(shí)間，初值為 0，在組件選擇執(zhí)行位置后對(duì) RTm進(jìn)行更新。當(dāng)組件vi的前驅(qū)組件集合為空時(shí)，即vi為開始組件，其開始執(zhí)行時(shí)間為0；當(dāng)xi∈[1,m]，即組件vi的執(zhí)行位置在Cloudletxi，其開始執(zhí)行時(shí)間為前驅(qū)組件中最晚將數(shù)據(jù)傳輸?shù)紺loudletxi的時(shí)間與其最早開始執(zhí)行時(shí)間RTxi的最大值；當(dāng)xi=0時(shí)，即組件vi的執(zhí)行位置為移動(dòng)設(shè)備，其開始執(zhí)行時(shí)間為前驅(qū)組件中最晚將數(shù)據(jù)傳輸?shù)揭苿?dòng)設(shè)備的時(shí)間與移動(dòng)設(shè)備最早能開始執(zhí)行時(shí)間 RTm的最大值。

組件vi的完成時(shí)間可以由式（4）計(jì)算。

當(dāng)i=1或i=n時(shí)，即組件vi為開始組件和結(jié)束組件時(shí)，其完成時(shí)間為其開始執(zhí)行時(shí)間；當(dāng)組件vi不是開始組件或者結(jié)束組件時(shí)，完成時(shí)間為其開始執(zhí)行時(shí)間加上其所在執(zhí)行位置上的執(zhí)行時(shí)間。

由此，可以得到應(yīng)用的完成時(shí)間為

4.4 移動(dòng)設(shè)備能耗模型

移動(dòng)設(shè)備能耗主要由無線網(wǎng)絡(luò)接口、屏幕、CPU、GPS等部件產(chǎn)生的能耗[24]組成，本文主要考慮無線網(wǎng)絡(luò)接口數(shù)據(jù)傳輸和CPU能耗。

4.4.1 數(shù)據(jù)傳輸能耗

本文中數(shù)據(jù)傳輸能耗包括數(shù)據(jù)發(fā)送和接收時(shí)移動(dòng)設(shè)備能量消耗。

1） 數(shù)據(jù)發(fā)送能耗

其 中 ，succ（i）表示組 件 vi后繼組 件 的集 合,表示移動(dòng)設(shè)備無線網(wǎng)絡(luò)發(fā)送數(shù)據(jù)所用時(shí)間的總和。

2） 數(shù)據(jù)接收能耗

4.4.2 CPU能耗

CPU能耗包括計(jì)算能耗和空閑能耗。計(jì)算能耗表示有組件在移動(dòng)設(shè)備上執(zhí)行時(shí)CPU的能量消耗，空閑能耗為沒有組件在移動(dòng)設(shè)備上執(zhí)行時(shí) CPU處于空閑狀態(tài)的能量消耗。

1） 計(jì)算能耗

2） 空閑能耗

空閑時(shí)間可以通過完成時(shí)間減去數(shù)據(jù)發(fā)送時(shí)間、數(shù)據(jù)接收時(shí)間和計(jì)算時(shí)間計(jì)算。

由此可以計(jì)算出空閑能耗

則移動(dòng)設(shè)備能耗可以表示為

4.5 問題定義

在4.3節(jié)和4.4節(jié)分別介紹了移動(dòng)數(shù)據(jù)流應(yīng)用的完成時(shí)間模型和移動(dòng)設(shè)備能耗模型。對(duì)于給定的應(yīng)用、移動(dòng)設(shè)備和Cloudlets等信息，可以得到任意Cloudlet選擇策略X對(duì)應(yīng)的應(yīng)用完成時(shí)間FT和移動(dòng)設(shè)備能耗Etotal。本文的Cloudlet選擇問題是尋找合適的Cloudlet選擇策略X，最小化應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能耗，可以由式（12）定義。

約束條件如下。

限制條件（a）表示入口組件 v0和出口組件 vn必須在移動(dòng)設(shè)備上執(zhí)行，限制條件（b）表示中間組件的執(zhí)行位置為移動(dòng)設(shè)備或者 Cloudlet；限制條件（c）表示組件之間的依賴關(guān)系，即組件vi開始執(zhí)行之前必須等待其前驅(qū)組件執(zhí)行完成并將所需數(shù)據(jù)傳輸?shù)皆摻M件vi所在執(zhí)行位置。

命題1式（12）是一個(gè)NP-hard問題。

證明假設(shè)不考慮移動(dòng)設(shè)備能耗，該問題就變成了最小化應(yīng)用完成時(shí)間的單目標(biāo)組合優(yōu)化問題，并且認(rèn)為開始組件和結(jié)束組件可以在任何計(jì)算節(jié)點(diǎn)上執(zhí)行，則該問題可規(guī)約成式（13）形式。

約束條件如下。

而式（13）與并行程序在并行計(jì)算機(jī)系統(tǒng)最小化完成時(shí)間的調(diào)度問題[25]等價(jià)。依據(jù)文獻(xiàn)[26]，該問題的特殊情況是 NP-hard問題，所以式（12）的問題也是NP-hard問題。證畢。

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

由4.5節(jié)可知該Cloudlet選擇問題是一個(gè)雙目標(biāo)的組合優(yōu)化問題[27]，且屬于NP-hard問題。而化學(xué)反應(yīng)優(yōu)化算法是通過模擬分子運(yùn)動(dòng)這一自然現(xiàn)象得到的一種通用元啟發(fā)式算法[28]，可以用于求解此類組合優(yōu)化問題，并且該Cloudlet選擇問題與網(wǎng)格計(jì)算中多目標(biāo)任務(wù)調(diào)度和人工神經(jīng)網(wǎng)絡(luò)中參數(shù)優(yōu)化問題相似，在文獻(xiàn)[29-30]中已經(jīng)用實(shí)驗(yàn)表明了化學(xué)反應(yīng)優(yōu)化算法相較于其他啟發(fā)式搜索算法在求解該類問題上的性能優(yōu)勢(shì)。因此,本文采用基于化學(xué)反應(yīng)優(yōu)化的啟發(fā)式算法求解。在化學(xué)反應(yīng)優(yōu)化算法中包括分子和基本化學(xué)反應(yīng)兩大因素，其中每個(gè)分子包含3個(gè)重要組成部分：分子結(jié)構(gòu)、勢(shì)能和動(dòng)能。本文中分子結(jié)構(gòu)對(duì)應(yīng)著Cloudlet選擇問題的解，勢(shì)能決定分子結(jié)構(gòu)的穩(wěn)定程度，其在本文為Cloudlet選擇策略的目標(biāo)函數(shù)值，動(dòng)能是系統(tǒng)中判斷是否發(fā)生反應(yīng)的量化值。基本化學(xué)反應(yīng)包括單分子碰撞、單分子分解、分子間碰撞和分子合成4種，通過這4種化學(xué)反應(yīng)操作使分子結(jié)構(gòu)不斷變得穩(wěn)定的過程，同樣對(duì)應(yīng)著在問題求解空間內(nèi)不斷尋求更優(yōu)Cloudlet選擇策略的過程。

5.1 問題編碼

針對(duì)本文移動(dòng)數(shù)據(jù)流應(yīng)用的Cloudlet選擇問題，采用十進(jìn)制編碼方式對(duì)分子結(jié)構(gòu)進(jìn)行編碼，分子中的原子對(duì)應(yīng)于組件的選擇位置，則其整個(gè)的分子結(jié)構(gòu)對(duì)應(yīng)于一個(gè)Cloudlet選擇策略。例如對(duì)于圖1中光學(xué)字符識(shí)別應(yīng)用對(duì)應(yīng)的一種分子結(jié)構(gòu)X={0,1,2,3,1,1,0}，表示組件v0和v6在移動(dòng)設(shè)備上執(zhí)行，組件v1、v4和v5在Cloudlet1上執(zhí)行，組件v2在Cloudlet2上執(zhí)行，組件v3在Cloudlet3上執(zhí)行。

5.2 適應(yīng)度函數(shù)

本文Cloudlet選擇策略的目標(biāo)是最小化移動(dòng)數(shù)據(jù)流應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能耗。這里通過簡(jiǎn)單的線性加權(quán)將2個(gè)目標(biāo)歸一為單目標(biāo)，所以對(duì)于該問題的適應(yīng)度函數(shù)f（X）可以使用式（14）表示。

其中，函數(shù)f1（X）和f2（X）分別表示 Cloudlet選擇策略X對(duì)應(yīng)的應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗。f1（allinmobile）表示應(yīng)用程序的所有組件都在移動(dòng)設(shè)備上執(zhí)行的能耗，f2（allinmobile）表示應(yīng)用程序的所有組件都在移動(dòng)設(shè)備上執(zhí)行的完成時(shí)間。α和β分別表示用戶依據(jù)移動(dòng)設(shè)備剩余電量對(duì)完成時(shí)間和移動(dòng)設(shè)備能耗的權(quán)重要求，其中α,β∈（0,1）且滿足α+β=1。當(dāng)移動(dòng)設(shè)備剩余電量較為充足時(shí)，應(yīng)用的完成時(shí)間作為主要優(yōu)化目標(biāo)，可以設(shè)置α＞β；當(dāng)剩余電量不足時(shí)，移動(dòng)設(shè)備能耗作為主要優(yōu)化目標(biāo)，可以設(shè)置α＜β。

5.3 分子操作設(shè)計(jì)

1） 單分子碰撞

單分子碰撞ineff_coll（X,x1）：是指單個(gè)分子碰撞容器壁改變其勢(shì)能和動(dòng)能的過程。分子的結(jié)構(gòu)X發(fā)生輕微變化，產(chǎn)生新的分子結(jié)構(gòu)x1，利用這一特點(diǎn)進(jìn)行問題求解空間的領(lǐng)域搜索。

本文具體設(shè)計(jì)采用在原分子（原Cloudlet選擇策略）X中，隨機(jī)選擇一個(gè)原子，隨機(jī)變換其值（組件的選擇位置），產(chǎn)生新的分子（新 Cloudlet選擇策略）x1。

2） 單分子分解

單分子分解 decompose（X,x1,x2）：是指動(dòng)能較大的分子與容器壁發(fā)生碰撞后，分解成2個(gè)分子的過程。分子X發(fā)生單分子分解后，將產(chǎn)生2個(gè)新的分子x1和x2，單分子分解反應(yīng)過程中對(duì)分子結(jié)構(gòu)的改變較大，用于提高算法的全局搜索能力。

本文具體設(shè)計(jì)采用原分子（原Cloudlet選擇策略）X隨機(jī)產(chǎn)生一個(gè)分解點(diǎn)，新分子（新 Cloudlet選擇策略）x1獲得原分子X分解點(diǎn)之前的所有原子（組件的選擇位置），新分子（新Cloudlet選擇策略）x2獲得原分子X分解點(diǎn)之后的所有原子，其余部分隨機(jī)產(chǎn)生。

3） 分子間碰撞

分子間碰撞 iter_ineff_cole（X1,X2,x1,x2）：是指2個(gè)分子發(fā)生碰撞后產(chǎn)生2個(gè)新分子的過程，即原分子X1和X2發(fā)生分子間碰撞之后產(chǎn)生新分子x1和x2。分子間碰撞與單分子碰撞類似，反應(yīng)劇烈程度都不大，對(duì)分子結(jié)構(gòu)的改變較小，用于在鄰域空間搜索問題的解。

本文具體設(shè)計(jì)采用類似遺傳算法中單點(diǎn)交叉的方式，隨機(jī)選擇一個(gè)位置作為碰撞點(diǎn)，新分子（新Cloudlet選擇策略）x1獲得原分子（原 Cloudlet選擇策略）X1碰撞點(diǎn)之前的原子（組件的選擇位置）和（原 Cloudlet選擇策略）X2碰撞點(diǎn)之后的原子，新分子（新 Cloudlet選擇策略）x2獲得原分子X1碰撞點(diǎn)之后的原子和原分子X2碰撞點(diǎn)之前的原子。

4） 分子合成

分子合成反應(yīng)synthesis（X1,X2,x）：是指2個(gè)分子碰撞后合成一個(gè)新分子的過程，即原分子X1和X2發(fā)生分子合成碰撞后產(chǎn)生x。由于分子合成反應(yīng)對(duì)分子結(jié)構(gòu)的改變很大，提高分子搜索新區(qū)域能力，用于增強(qiáng)算法全局搜索能力。

本文具體設(shè)計(jì)采用隨機(jī)生成一個(gè)劃分點(diǎn)，碰撞后的新分子（新Cloudlet選擇策略）x獲得原分子（原 Cloudlet選擇策略）X1的劃分點(diǎn)之前原子（組件的選擇位置）和獲得原分子（原Cloudlet選擇策略）X2的劃分點(diǎn)之后原子。

5.4 算法描述

算法 1給出了基于化學(xué)反應(yīng)優(yōu)化算法的Cloudlet選擇策略（CROCS），其對(duì)應(yīng)的流程圖如圖3所示。對(duì)于給定的移動(dòng)設(shè)備mobile、Cloudlets、應(yīng)用程序G（V,E）等信息，CROCS算法會(huì)得到一個(gè)近似最優(yōu)的選擇策略X。

該算法分為3個(gè)階段：初始階段、迭代過程和最后階段。在初始階段（算法1中1）～11）），初始化系統(tǒng)參數(shù)并隨機(jī)產(chǎn)生PopSize個(gè)選擇策略分子組成的分子群，計(jì)算每一個(gè)分子的適應(yīng)度值，初始化其勢(shì)能和動(dòng)能。隨后進(jìn)入迭代階段（算法 1中12） ～27）），迭代階段結(jié)束條件由初始設(shè)置的迭代次數(shù)MaxIter決定。在每一次迭代過程中，首先由在[0,1]之間的隨機(jī)數(shù)t與系統(tǒng)參數(shù)MoleColl值的大小關(guān)系決定發(fā)生單分子反應(yīng)還是發(fā)生分子間的反應(yīng)。當(dāng)隨機(jī)數(shù)t大于系統(tǒng)參數(shù)MoleColl，隨機(jī)從分子群中選擇一個(gè)分子，如果分解反應(yīng)條件滿足，則發(fā)生單分子分解反應(yīng)，否則發(fā)生單分子碰撞反應(yīng)。當(dāng)隨機(jī)數(shù)t小于系統(tǒng)參數(shù)MoleColl，隨機(jī)從分子群中選擇2個(gè)分子，如果合成反應(yīng)條件滿足，則發(fā)生分子合成反應(yīng)，否則發(fā)生分子間碰撞反應(yīng)。在最后階段（算法1中 28）～29）），從分子群中得到所含勢(shì)能最小的分子作為最終的Cloudlet選擇策略。

圖3 CROCS算法流程

算法1基于化學(xué)反應(yīng)優(yōu)化算法的Cloudlet選擇策略（CROCS）

輸入Mobile，Cloudlet，G（V,E），迭代次數(shù)MaxIter，權(quán)重參數(shù)α和β

輸出選擇策略X

1） 初 始 化 PopSize,Molecules,MoleColl,InitialKE/*PopSize為分子群初始規(guī)模，Molecules為分子群,MoleColl為分子反應(yīng)決定類型因子，InitialKE為初始動(dòng)能*/

2）i←1

3） whilei≤PopSize

4） 隨機(jī)生成一個(gè)Cloudlet選擇策略分子X

5）f2（X）←computfinishtime（X）/*依據(jù)式（5）計(jì)算選擇策略分子X對(duì)應(yīng)的應(yīng)用完成時(shí)間*/

6）f1（X）←computtotalenergy（X）/*依 據(jù)式（11）計(jì)算選擇策略分子X對(duì)應(yīng)的移動(dòng)設(shè)備能耗*/

7） PE[X]←computeFitness（X）/*依據(jù)式（14）計(jì)算選擇策略分子X的適應(yīng)度并初始化勢(shì)能*/

8） KE[X]←InitialKE /*初始化策略分子X的動(dòng)能*/

9） 將分子X加入到分子群Molecules中

10）i←i+1

11） end while

12）j←1

13） whilej≤MaxIter /*迭代 MaxIter次*/

14）t=random（0,1）

15） if （t＞ MoleColl）

16） 隨機(jī)從分子群Molecules中選擇一個(gè)分子X

17） if （decomposition criterion met）then

18） decompose（X,x1,x2）/*發(fā)生單分子分解反應(yīng)*/

19） else

20） ineff_coll（X,x1） /*發(fā)生單分子碰撞反應(yīng)*/

21） else

22） 隨機(jī)從分子群Molecules中選擇2個(gè)分子X1和X2

23） if （synthesis criterion met） then synthesis（X1,X2,x）/*發(fā)生分子合成反應(yīng)*/

25） else

26） iter_ineff_cole（X1,X2,x1,x2）/*發(fā)生分子間碰撞反應(yīng)*/

27） end while

28）X←findthebest（Molecules）/*從分子群中找到最優(yōu)的策略*/

returnX

5.5 解空間分析

本節(jié)將分析問題的解空間，并給出選擇化學(xué)反應(yīng)算法求解該問題的原因。

1） 解空間大小

如上文模型所述，對(duì)于一個(gè)擁有n個(gè)組件的應(yīng)用。除開始和結(jié)束組件外，其每一個(gè)組件的選擇位置為m個(gè)Cloudlet或移動(dòng)設(shè)備，即可選擇位置個(gè)數(shù)為m+1，故解空間的大小為（m+1）n-2。

2） 可選算法分析

求解這類組合優(yōu)化問題的算法可以分為確定性算法（如線性規(guī)劃等）和啟發(fā)式算法（如化學(xué)反應(yīng)優(yōu)化算法、模擬退火算法和遺傳算法[31]等）。然而確定性算法在這種指數(shù)級(jí)的解空間大小下，將面臨組合爆炸問題。在啟發(fā)式算法中，化學(xué)反應(yīng)優(yōu)化算法能夠通過 4種基本化學(xué)反應(yīng)實(shí)現(xiàn)啟發(fā)式搜索。其中單分子碰撞和分子間碰撞反應(yīng)作用于鄰域搜索；分子合成和單分子分解反應(yīng)作用于全局搜索。因而化學(xué)反應(yīng)算法相較于其他啟發(fā)式算法，能夠避免過早地陷入局部最優(yōu)。因此，在本文中采用化學(xué)反應(yīng)優(yōu)化算法求解該問題。

5.6 時(shí)間復(fù)雜度分析

假設(shè)初始分子群的規(guī)模為 PopSize，應(yīng)用的組件個(gè)數(shù)為n，迭代次數(shù)為MaxIter。在初始階段生成PopSize個(gè)分子的分子群，并初始化每一個(gè)分子的動(dòng)能和勢(shì)能，計(jì)算勢(shì)能時(shí)需要計(jì)算一次適應(yīng)度，而計(jì)算適應(yīng)度函數(shù)的時(shí)間復(fù)雜度為O（n），故在初始階段的時(shí)間復(fù)雜度為O（PopSize×n）。在迭代階段，單分子分解反應(yīng)的時(shí)間復(fù)雜度為O（n），單分子碰撞反應(yīng)的時(shí)間復(fù)雜度為O（1），分子合成反應(yīng)的時(shí)間復(fù)雜度為O（n），分子間碰撞反應(yīng)的時(shí)間復(fù)雜度為O（1），所以在4種分子操作過程中的平均復(fù)雜度為O（n），同時(shí)還需要計(jì)算新分子的適應(yīng)度函數(shù)。迭代次數(shù)為 MaxIter，所以迭代過程中的時(shí)間復(fù)雜度為O（MaxIter×n×n）。綜上所述，整 個(gè) 算 法 的 時(shí) 間 復(fù) 雜 度 為O（（MaxIter×n+PopSize）×n）。

5.7 算法收斂性分析

化學(xué)反應(yīng)算法收斂性主要取決于化學(xué)反應(yīng)操作算子[32],經(jīng)過基本的化學(xué)反應(yīng)之后，令選擇策略X1到選擇策略X2的轉(zhuǎn)換概率 P（X1→X2）＞0, 選擇策略X1和X2屬于選擇策略任意元素。由于每一次迭代的獨(dú)立性，經(jīng)過MaxIter次迭代過程后，算法不能從次優(yōu)解達(dá)到全局最優(yōu)解的概率是1- （1-p）MaxIter。因此算法經(jīng)過 MaxIter次迭代后能夠達(dá)到最優(yōu)解的概率是1-（1-p）MaxIter，當(dāng)MaxIter→∞時(shí)，可以得到最優(yōu)解的概率為所以當(dāng)?shù)螖?shù)足夠多時(shí)，算法總會(huì)收斂于全局最優(yōu)解。

6 仿真實(shí)驗(yàn)與結(jié)果分析

6.1 仿真實(shí)驗(yàn)環(huán)境配置

1） Cloudlet和移動(dòng)設(shè)備配置

實(shí)驗(yàn)中的Cloudlet由以下3臺(tái)服務(wù)器模擬，配置信息如表2所示。使用Cloudlet1作為代理Cloudlet，Cloudlet2、Cloudlet3作為其他計(jì)算服務(wù)器。其中Cloudlet2計(jì)算能力最強(qiáng)，Cloudlet3其次，作為代理的Cloudlet1計(jì)算能力最弱。

表2 Cloudlet配置

實(shí)驗(yàn)采用的移動(dòng)設(shè)備為智能手機(jī)，其配置、CPU和無線接口在不同狀態(tài)下功率（單位是 mw）信息如表3所示，其中CPU功率和無線網(wǎng)絡(luò)接口功率等信息是依據(jù)Android操作系統(tǒng)應(yīng)用程序框架提供的能耗分析配置文件（PowerProfile.xml）獲得。

表3 移動(dòng)設(shè)備配置

2） 網(wǎng)絡(luò)配置

實(shí)驗(yàn)中的網(wǎng)絡(luò)配置分為2個(gè)方面：Cloudlet與移動(dòng)設(shè)備之間的網(wǎng)絡(luò)，移動(dòng)設(shè)備的默認(rèn)上傳帶寬Bu和下載帶寬Bd設(shè)置為8 Mbit/s；Cloudlet之間的網(wǎng)絡(luò)，本文Cloudlet之間的帶寬B大小相同，同時(shí)Cloudlet選擇策略的結(jié)果與Cloudlet之間的帶寬大小有關(guān)，所以采用4種不同的Cloudlet之間的帶寬，分別是10 Mbit/s、30 Mbit/s、50 Mbit/s和210 Mbit/s。

3） 移動(dòng)數(shù)據(jù)流應(yīng)用配置

為了不失一般性，實(shí)驗(yàn)采用應(yīng)用模型如圖1所示的光學(xué)字符識(shí)別移動(dòng)數(shù)據(jù)流應(yīng)用程序進(jìn)行實(shí)驗(yàn)。

6.2 實(shí)驗(yàn)結(jié)果分析

在本節(jié)中，將CROCS策略與已有的2種策略：H-PSP（heuristic based on partial stochastic path）[21]和 POCSS（power and latency aware optimum Cloudlet selection strategy）[14]進(jìn)行對(duì)比，其中 H-PSP策略聯(lián)合利用移動(dòng)設(shè)備和單個(gè)Cloudlet的計(jì)算能力，并以最小化應(yīng)用的完成時(shí)間為目標(biāo)，其中單個(gè)Cloudlet選取計(jì)算能力最強(qiáng)的Cloudlet作為組件候選的執(zhí)行位置；POCSS策略是選擇一個(gè)應(yīng)用的完成時(shí)間最小或移動(dòng)設(shè)備能耗最低的 Cloudlet，并將應(yīng)用的所有可卸載的組件全都卸載到一個(gè)Cloudlet上進(jìn)行執(zhí)行。

為了驗(yàn)證本文算法有效性，首先，以應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能量消耗作為性能指標(biāo)，采用控制變量法，分別改變Cloudlet之間的帶寬、Cloudlet個(gè)數(shù)、應(yīng)用程序并行組件指令數(shù)在總指令數(shù)中的占比和參數(shù)α等影響因素，然后統(tǒng)計(jì)分析應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能耗隨這些因素的變化規(guī)律。其次，通過引入已經(jīng)廣泛應(yīng)用的遺傳算法進(jìn)行對(duì)比，考察其收斂特性。

1） Cloudlet之間的帶寬的影響

本組實(shí)驗(yàn)研究Cloudlet之間的帶寬對(duì)應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能耗的影響，實(shí)驗(yàn)參數(shù)的配置如表4所示。

表4 實(shí)驗(yàn)1環(huán)境配置

本實(shí)驗(yàn)中設(shè)置 Cloudlet個(gè)數(shù)為 3個(gè)，分別為Cloudlet1、Cloudlet2和 Cloudlet3，移動(dòng)設(shè)備與Cloudlet之間的帶寬為8 Mbit/s，并行組件指令數(shù)在總指令數(shù)中占比為初始的40%，Cloudlet之間的帶寬分別取10 Mbit/s、30 Mbit/s、50 Mbit/s。具體實(shí)驗(yàn)結(jié)果如圖4所示。

如圖4（a）所示，隨著Cloudlet之間帶寬的增大，CROCS策略和POCSS策略的應(yīng)用完成時(shí)間隨之減小，而H-PSP策略沒有變化。CROCS策略和POCSS策略都需要通過代理Cloudlet與其他Cloudlet進(jìn)行交互，所以Cloudlet之間的帶寬增加降低了組件間數(shù)據(jù)傳輸成本，減小了應(yīng)用的完成時(shí)間。在Cloudlet之間的帶寬較低的情況下，較高的數(shù)據(jù)傳輸時(shí)間成本使得CROCS策略沒有發(fā)揮其充分利用應(yīng)用的組件間并行性優(yōu)勢(shì)，使得CROCS策略在Cloudlet之間的帶寬較小的條件下并沒有優(yōu)勢(shì)。隨著 Cloudlet之間的帶寬的增加，組件之間的傳輸時(shí)間成本降低，CROCS策略可以充分利用應(yīng)用的并行性，進(jìn)而與其他 2種策略相比在完成時(shí)間上有明顯的優(yōu)勢(shì),相較于H-PSP策略和POCSS策略在完成時(shí)間上平均有3%和14.8%的性能提升。

如圖 4（b）所示，隨著 Cloudlet之間帶寬的增大，CROCS策略和POCSS策略的移動(dòng)設(shè)備能耗都越來越小，且都處于較低的水平。由于兩者都沒有任何組件在移動(dòng)設(shè)備上執(zhí)行，移動(dòng)設(shè)備能耗主要由數(shù)據(jù)傳輸能耗和空閑能耗組成，Cloudlet之間的帶寬增加使這兩者策略的應(yīng)用完成時(shí)間都有所降低（如圖 4（a）所示），由此降低了一定的空閑能耗，但空閑能耗在總能耗中占比太低，對(duì)于移動(dòng)設(shè)備能耗的降低并不明顯。而H-PSP策略的移動(dòng)設(shè)備能耗相較于其他2種策略較高，其原因是H-PSP策略會(huì)使用移動(dòng)設(shè)備資源執(zhí)行一定的并行組件以減小應(yīng)用的完成時(shí)間，從而帶來了較高的計(jì)算能耗。綜合來看，相較于H-PSP策略和POCSS策略在移動(dòng)設(shè)備的能耗上平均有70.5%和6%的能耗降低。

圖4 Cloudlet之間的帶寬對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響

2） Cloudlet個(gè)數(shù)的影響

本組實(shí)驗(yàn)研究Cloudlet個(gè)數(shù)對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響，實(shí)驗(yàn)參數(shù)的配置如表5所示。

表5 實(shí)驗(yàn)2環(huán)境配置

本實(shí)驗(yàn)中，為了減小Cloudlet之間的帶寬對(duì)本實(shí)驗(yàn)的影響，將其設(shè)置為210 Mbit/s，移動(dòng)設(shè)備與Cloudlet之間的帶寬為8 Mbit/s，并行組件指令數(shù)在總指令數(shù)中占比為40%，Cloudlet個(gè)數(shù)依次為1個(gè)、2個(gè)、3個(gè)和4個(gè)，當(dāng)Cloudlet個(gè)數(shù)為超過3個(gè)時(shí)，超過部分采用Cloudlet3模擬。具體實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 Cloudlet個(gè)數(shù)對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響

如圖 5（a）所示，隨著 Cloudlet個(gè)數(shù)的增加，CROCS策略的應(yīng)用完成時(shí)間逐漸減小。當(dāng)Cloudlet個(gè)數(shù)從一個(gè)增長(zhǎng)到3個(gè)時(shí)，主要是由于CROCS策略會(huì)使應(yīng)用中更多的并行組件能夠分散到多個(gè)Cloudlet上并行執(zhí)行，從而降低了應(yīng)用的完成時(shí)間，而當(dāng)Cloudlet個(gè)數(shù)與光學(xué)字符識(shí)別并行組件達(dá)到相同的3個(gè)時(shí)，應(yīng)用的并行程度達(dá)到最大，此時(shí)進(jìn)一步增加Cloudlet規(guī)模，應(yīng)用完成時(shí)間的降低是通過引入了計(jì)算能力較強(qiáng)的Cloudlet加快應(yīng)用效率實(shí)現(xiàn)的。對(duì)于H-PSP策略和POCSS策略，Cloudlet個(gè)數(shù)從一個(gè)增加到 2個(gè)的時(shí)候，完成時(shí)間有所降低，其后則保持不變。原因是引入了計(jì)算能力更強(qiáng)的Cloudlet2，H-PSP策略和POCSS策略會(huì)主要使用計(jì)算能力更強(qiáng)的Cloudlet2進(jìn)行計(jì)算卸載，從而降低了應(yīng)用的完成時(shí)間，當(dāng)Cloudlet個(gè)數(shù)進(jìn)一步增加，這2種策略仍然只使用該計(jì)算能力較強(qiáng)的Cloudlet2，所以并不會(huì)影響應(yīng)用的完成時(shí)間。綜合來看，相較于H-PSP策略和POCSS策略，CROCS策略在完成時(shí)間上平均有4.5%和12%的性能提升，最好情況下分別能達(dá)到12.1%和22.3%。

如圖 5（b）所示，隨著 Cloudlet個(gè)數(shù)的增加，CROCS策略的移動(dòng)設(shè)備能耗也隨著降低。當(dāng)Cloudlet個(gè)數(shù)從一個(gè)增加到2個(gè)的時(shí)候，CROCS策略的移動(dòng)設(shè)備能耗顯著降低，這是由于當(dāng) Cloudlet個(gè)數(shù)只有一個(gè) Cloudlet時(shí)，CROCS策略會(huì)利用移動(dòng)設(shè)備的計(jì)算能力，將部分組件留在移動(dòng)設(shè)備上執(zhí)行，會(huì)產(chǎn)生較高的移動(dòng)設(shè)備計(jì)算能耗。隨著Cloudlet個(gè)數(shù)進(jìn)一步增加，應(yīng)用的并行組件能夠分散到其他Cloudlet上執(zhí)行，從而顯著降低了移動(dòng)設(shè)備的能耗。H-PSP策略在Cloudlet個(gè)數(shù)較多的時(shí)候依然需要利用移動(dòng)設(shè)備的計(jì)算能力，從而會(huì)一直產(chǎn)生較高的移動(dòng)設(shè)備能耗。相比之下，CROCS策略的移動(dòng)設(shè)備能耗在 Cloudlet個(gè)數(shù)足夠多時(shí)相較于 H-PSP和POCSS策略分別減小了77.1%和5.9%。

3） 應(yīng)用程序并行組件指令數(shù)在總指令數(shù)中占比的影響

本組實(shí)驗(yàn)為了進(jìn)一步驗(yàn)證CROCS策略對(duì)于組件之間可并行部分充分利用的特性，在保持應(yīng)用的總指令數(shù)不變前提下，將光學(xué)字符識(shí)別中的3個(gè)并行組件指令數(shù)與全部組件的指令數(shù)的比例逐步提高，探究應(yīng)用的并行性對(duì)選擇策略的影響。具體實(shí)驗(yàn)配置如表6所示。

表6 實(shí)驗(yàn)3環(huán)境配置

本組實(shí)驗(yàn)中，Cloudlet之間帶寬設(shè)置為210 Mbit/s，移動(dòng)設(shè)備與Cloudlet之間的帶寬為8 Mbit/s，Cloudlet個(gè)數(shù)為3個(gè)，應(yīng)用中并行組件指令數(shù)占比為40%、60%、80%。具體實(shí)驗(yàn)結(jié)果如圖 6（a）和圖 6（b）所示。

圖6 并行組件指令數(shù)占比對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響

如圖6（a）所示，隨著并行組件指令數(shù)占比越來越高，CROCS策略和H-PSP策略的應(yīng)用完成時(shí)間會(huì)相應(yīng)減小，而 POCSS策略沒有變化。主要是因?yàn)樵贑ROCS策略和H-PSP策略中，可以并行執(zhí)行組件的指令數(shù)增多，同時(shí)執(zhí)行的效率更高，加快了應(yīng)用的執(zhí)行速度，從而降低了應(yīng)用的完成時(shí)間。但CROCS策略相較于H-PSP策略，其應(yīng)用完成時(shí)間減小的幅度更為明顯，這是由于CROCS策略對(duì)于并行組件的并行程度利用得更加充分。而 POCSS策略中應(yīng)用程序的所有組件都只在同一個(gè) Cloudlet上執(zhí)行，并沒有考慮到組件間的并行性，所以并行組件指令數(shù)占比對(duì)其沒有影響。綜合來看，隨著并行組件的指令數(shù)占比的增加，CROCS策略的應(yīng)用完成時(shí)間相較于其他2種策略優(yōu)勢(shì)更加明顯。具體來說，相較于H-PSP策略和POCSS策略在完成時(shí)間上有19.3%和28.2%的性能提升。

如圖6（b）所示，隨著并行組件指令數(shù)占比越來越高，CROCS策略的移動(dòng)設(shè)備能耗相較于 H-PSP策略優(yōu)勢(shì)越來越明顯。由于H-PSP策略中需要在移動(dòng)設(shè)備上執(zhí)行的指令數(shù)的增加，導(dǎo)致移動(dòng)設(shè)備CPU處于計(jì)算狀態(tài)的時(shí)間相應(yīng)增長(zhǎng)，且 CPU計(jì)算功率相較于網(wǎng)絡(luò)接口的數(shù)據(jù)傳輸功率和 CPU空閑功率較高，從而顯著增加了移動(dòng)設(shè)備能耗，所以相較于H-PSP策略，CROCS策略在移動(dòng)設(shè)備能耗上有較大優(yōu)勢(shì)。其次，CROCS策略和POCSS策略的所有組件都是在Cloudlet上執(zhí)行，其移動(dòng)設(shè)備能耗主要只由兩部分組成，網(wǎng)絡(luò)接口的數(shù)據(jù)傳輸能耗和CPU空閑能耗。雖然CROCS策略的應(yīng)用完成時(shí)間降低了不少（如圖6（a）所示），但是CPU空閑功率太小，并沒有大幅降低移動(dòng)設(shè)備能耗。所以CROCS策略和 POCSS策略相比，移動(dòng)設(shè)備能耗相差不大。綜合來看，相較于H-PSP策略和POCSS策略在移動(dòng)設(shè)備的能耗上平均有83.7%和4%的能耗減小。

4） 移動(dòng)設(shè)備與Cloudlet之間帶寬的影響

本組實(shí)驗(yàn)為了驗(yàn)證移動(dòng)設(shè)備與Cloudlet之間的帶寬對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響，實(shí)驗(yàn)參數(shù)配置如表7所示。

表7 實(shí)驗(yàn)4環(huán)境配置

本實(shí)驗(yàn)中設(shè)置Cloudlet之間的帶寬為210 Mbit/s，Cloudlet個(gè)數(shù)為3，參數(shù)α為0.5，并行組件指令數(shù)占比為40%，移動(dòng)設(shè)備與Cloudlet之間的帶寬分別設(shè)置為4 Mbit/s、8 Mbit/ss和12 Mbit/s。具體實(shí)驗(yàn)結(jié)果如圖7所示。

如圖7（a）所示，隨著移動(dòng)設(shè)備與Cloudlet之間的帶寬增大，CROCS、H-PSP和POCSS策略的應(yīng)用完成時(shí)間都隨之降低，這是由于隨著移動(dòng)設(shè)備與Cloudlet之間帶寬的增大提高了移動(dòng)設(shè)備與Cloudlet端的數(shù)據(jù)傳輸效率，從而減小了應(yīng)用完成時(shí)間。與此同時(shí)，CROCS策略的應(yīng)用完成時(shí)間相較于H-PSP和CROCS策略在完成時(shí)間相對(duì)較小，這是因?yàn)?CROCS策略能夠更加充分的利用多個(gè)Cloudlet計(jì)算能力加快應(yīng)用執(zhí)行效率，進(jìn)而CROCS策略相較于其他2種策略在完成時(shí)間較優(yōu)。

圖7（b）展示了不同移動(dòng)設(shè)備與Cloudlet之間的帶寬對(duì)移動(dòng)能耗的影響。從中可以看出隨著移動(dòng)設(shè)備與Cloudlet之間帶寬的增大，3種選擇策略的移動(dòng)設(shè)備能耗都相應(yīng)降低。這是由于移動(dòng)設(shè)備與Cloudlet之間的帶寬的增加導(dǎo)致移動(dòng)設(shè)備的網(wǎng)絡(luò)接口處于數(shù)據(jù)傳輸時(shí)間降低，從而移動(dòng)設(shè)備的數(shù)據(jù)傳輸能耗隨之降低，并最終降低了移動(dòng)設(shè)備能量消耗。同時(shí)還可以看出 CROCS和 POCSS策略相較于H-PSP策略，移動(dòng)設(shè)備能耗處于較低水平，這是由于H-PSP策略優(yōu)化目標(biāo)主要是應(yīng)用的完成時(shí)間，其對(duì)移動(dòng)設(shè)備計(jì)算能力的使用產(chǎn)生了較多能耗。

圖7 移動(dòng)設(shè)備與Cloudlet之間的距離對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響

5） 參數(shù)α的影響

本組實(shí)驗(yàn)為了探究參數(shù)α對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響，實(shí)驗(yàn)參數(shù)的配置如表8所示。

表8 實(shí)驗(yàn)5環(huán)境配置

本組實(shí)驗(yàn)中，Cloudlet之間帶寬設(shè)置為210 Mbit/s，移動(dòng)設(shè)備與Cloudlet之間的帶寬為8 Mbit/s，Cloudlet個(gè)數(shù)設(shè)置為2個(gè)，應(yīng)用中并行組件指令數(shù)占比為40%，參數(shù)α分別設(shè)置為0.1、0.5和0.9。具體實(shí)驗(yàn)結(jié)果如圖8所示。

圖8（a）表示參數(shù)α對(duì)應(yīng)用的完成時(shí)間的影響。隨著參數(shù)α的增大，本文提出的CROCS策略的應(yīng)用完成時(shí)間相應(yīng)變小。這是由于參數(shù)α的增大表示主要優(yōu)化目標(biāo)越來越偏向于應(yīng)用的完成時(shí)間，從而導(dǎo)致CROCS策略會(huì)選擇使用移動(dòng)設(shè)備的計(jì)算資源執(zhí)行部分并行組件，減小了應(yīng)用的完成時(shí)間。而H-PSP和POCSS策略不受參數(shù)α的影響，所以其應(yīng)用的完成時(shí)間沒有變化。

圖8 參數(shù)α對(duì)應(yīng)用完成時(shí)間和移動(dòng)設(shè)備能耗的影響

圖8（b）表示參數(shù)α對(duì)移動(dòng)設(shè)備能耗的影響。隨著參數(shù)α的增大， CROCS策略的移動(dòng)設(shè)備能耗隨之增大。這是由于參數(shù)α的增大導(dǎo)致CROCS策略會(huì)選擇使用移動(dòng)設(shè)備的計(jì)算資源執(zhí)行部分并行組件減小應(yīng)用完成時(shí)間，從而移動(dòng)設(shè)備將產(chǎn)生較大的計(jì)算能耗，因此移動(dòng)設(shè)備的能耗相應(yīng)增加。同樣地，參數(shù)α對(duì)POCSS和H-PSP策略沒有影響，所以其移動(dòng)設(shè)備能耗沒有變化。綜上所述，實(shí)驗(yàn)結(jié)果表明CROCS策略可以通過調(diào)整應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備能耗的權(quán)重參數(shù)α動(dòng)態(tài)地給出選擇策略，達(dá)到了預(yù)期的效果。

6） 收斂特性

為了考察化學(xué)反應(yīng)優(yōu)化算法在求解此類組合優(yōu)化問題時(shí)的收斂特性，選取已經(jīng)被廣泛應(yīng)用的遺傳算法（GA，genetic algorithm）和離散粒子群優(yōu)化算法（DPSO，discrete particle swarm optimization）[33]與之進(jìn)行對(duì)比。

其中CROCS參數(shù)設(shè)置為：分子群規(guī)模PopSize為40，分子反應(yīng)決定因子MoleColl為0.2，初始動(dòng)能InitialKE為500，迭代次數(shù)MaxIter為500。GA參數(shù)設(shè)置為：種群規(guī)模為40，變異概率為0.02，交叉概率為0.8，迭代次數(shù)為500。DPSO的參數(shù)設(shè)置為：粒子群規(guī)模為40，慣性常數(shù)為0.8，加速度系數(shù)為0.5，迭代次數(shù)為500。分別獨(dú)立運(yùn)行30次，CROCS與GA、DPSO算法運(yùn)行的結(jié)果如表9所示，收斂曲線如圖9所示。

表9 CROCS與GA、DPSO運(yùn)行結(jié)果

圖9 收斂曲線

如表9所示，CROCS相較于GA和DPSO策略得到全局最優(yōu)解的概率更高。其次，對(duì)應(yīng)的平均適應(yīng)度和最大適應(yīng)度值也相對(duì)于GA和DPSO策略更優(yōu)，并且從標(biāo)準(zhǔn)差看CROCS策略有更高的求解穩(wěn)定性。因此，CROCS相較于GA和DPSO策略有更好的全局收斂性。

圖9為CROCS與GA、DPSO策略的收斂曲線。CROCS的收斂曲線相較于GA策略更接近與底線，并且收斂的速度相對(duì)較快；而DPSO雖然在計(jì)算初期收斂速度較快，但很快陷入局部最優(yōu)解，無法跳出。因此，CORCS策略可以更快地跳出局部最優(yōu)解，而GA和DPSO更易于陷入局部最優(yōu)，無法找到全局最優(yōu)解。主要因?yàn)榛瘜W(xué)反應(yīng)優(yōu)化算法中單分子分解和分子合成的分子操作對(duì)分子結(jié)構(gòu)改變較大，具有很強(qiáng)的全局搜索能力。綜上所述，CROCS相較于 GA策略的收斂速度更快且全局收斂性更好，相較于DPSO策略的全局收斂性更好。

綜合以上6組實(shí)驗(yàn)，本文提出的CROCS策略與H-PSP策略和POCSS策略在應(yīng)用性能上平均分別提升了8.9%和18.2%，在移動(dòng)設(shè)備能耗方面則平均分別減少了77.1%和5.3%，并且在收斂特性上也有較優(yōu)的效果。

7 結(jié)束語

本文針對(duì)在多Cloudlet環(huán)境中移動(dòng)數(shù)據(jù)流應(yīng)用的Cloudlet選擇問題，提出了一種基于化學(xué)反應(yīng)優(yōu)化算法的 Cloudlet選擇策略 CROCS，該策略通過充分利用多個(gè)Cloudlet資源最大化移動(dòng)數(shù)據(jù)流應(yīng)用的并行執(zhí)行效率，在提升移動(dòng)數(shù)據(jù)流應(yīng)用性能的同時(shí)兼顧移動(dòng)設(shè)備的能量消耗。仿真實(shí)驗(yàn)表明，本文提出的選擇策略相較于其他沒有充分考慮移動(dòng)數(shù)據(jù)流應(yīng)用中擁有大量可以并行執(zhí)行的組件的策略，在應(yīng)用的完成時(shí)間和移動(dòng)設(shè)備的能量消耗上有較為明顯的優(yōu)勢(shì)。在未來工作方面，考慮從用戶的移動(dòng)性方面展開研究。用戶的移動(dòng)會(huì)導(dǎo)致用戶周圍的網(wǎng)絡(luò)和可用的Cloudlet資源發(fā)生變化，需要實(shí)時(shí)基于周圍環(huán)境選擇合適的Cloudlet才能滿足應(yīng)用的服務(wù)質(zhì)量需求。另外，本文仿真實(shí)驗(yàn)環(huán)境設(shè)置與實(shí)際環(huán)境還有一定的差距，未來考慮更加貼近實(shí)際運(yùn)行環(huán)境的因素，探究其對(duì)算法性能的影響。