移動云環(huán)境中數(shù)據(jù)流應(yīng)用的Cloudlet選擇策略研究

劉偉，熊曙，杜薇，王偉

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

1 引言

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

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

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

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

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

2） 設(shè)計了一個動態(tài)調(diào)整的適應(yīng)度函數(shù)，根據(jù)移動設(shè)備的剩余電量調(diào)整應(yī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)系的前提下，充分利用移動數(shù)據(jù)流應(yīng)用中可以并行執(zhí)行的組件，提高了應(yīng)用性能。

2 研究動機

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

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

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

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

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

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

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

3 相關(guān)工作

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

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

4 系統(tǒng)模型

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

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

1） 移動設(shè)備

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

2） Cloudlet

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

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

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

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

4） Cloudlet選擇策略

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

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

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

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

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

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

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

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

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

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

組件vi的完成時間可以由式（4）計算。

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

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

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

移動設(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è)備能量消耗。

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

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

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

4.4.2 CPU能耗

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

1） 計算能耗

2） 空閑能耗

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

由此可以計算出空閑能耗

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

4.5 問題定義

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

約束條件如下。

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

命題1式（12）是一個NP-hard問題。

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

約束條件如下。

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

5 算法設(shè)計

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

5.1 問題編碼

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

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

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

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

5.3 分子操作設(shè)計

1） 單分子碰撞

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

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

2） 單分子分解

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

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

3） 分子間碰撞

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

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

4） 分子合成

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

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

5.4 算法描述

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

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

2）i←1

3） whilei≤PopSize

4） 隨機生成一個Cloudlet選擇策略分子X

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

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

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

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

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） 隨機從分子群Molecules中選擇一個分子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） 隨機從分子群Molecules中選擇2個分子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） 解空間大小

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

2） 可選算法分析

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

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

假設(shè)初始分子群的規(guī)模為 PopSize，應(yīng)用的組件個數(shù)為n，迭代次數(shù)為MaxIter。在初始階段生成PopSize個分子的分子群，并初始化每一個分子的動能和勢能，計算勢能時需要計算一次適應(yīng)度，而計算適應(yīng)度函數(shù)的時間復(fù)雜度為O（n），故在初始階段的時間復(fù)雜度為O（PopSize×n）。在迭代階段，單分子分解反應(yīng)的時間復(fù)雜度為O（n），單分子碰撞反應(yīng)的時間復(fù)雜度為O（1），分子合成反應(yīng)的時間復(fù)雜度為O（n），分子間碰撞反應(yīng)的時間復(fù)雜度為O（1），所以在4種分子操作過程中的平均復(fù)雜度為O（n），同時還需要計算新分子的適應(yīng)度函數(shù)。迭代次數(shù)為 MaxIter，所以迭代過程中的時間復(fù)雜度為O（MaxIter×n×n）。綜上所述，整 個 算 法 的 時 間 復(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屬于選擇策略任意元素。由于每一次迭代的獨立性，經(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→∞時，可以得到最優(yōu)解的概率為所以當(dāng)?shù)螖?shù)足夠多時，算法總會收斂于全局最優(yōu)解。

6 仿真實驗與結(jié)果分析

6.1 仿真實驗環(huán)境配置

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

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

表2 Cloudlet配置

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

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

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

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

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

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

6.2 實驗結(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)行對比，其中 H-PSP策略聯(lián)合利用移動設(shè)備和單個Cloudlet的計算能力，并以最小化應(yīng)用的完成時間為目標(biāo)，其中單個Cloudlet選取計算能力最強的Cloudlet作為組件候選的執(zhí)行位置；POCSS策略是選擇一個應(yīng)用的完成時間最小或移動設(shè)備能耗最低的 Cloudlet，并將應(yīng)用的所有可卸載的組件全都卸載到一個Cloudlet上進(jìn)行執(zhí)行。

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

1） Cloudlet之間的帶寬的影響

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

表4 實驗1環(huán)境配置

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

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

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

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

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

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

表5 實驗2環(huán)境配置

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

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

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

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

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

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

表6 實驗3環(huán)境配置

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

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

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

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

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

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

表7 實驗4環(huán)境配置

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

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

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

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

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

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

表8 實驗5環(huán)境配置

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

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

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

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

6） 收斂特性

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

其中CROCS參數(shù)設(shè)置為：分子群規(guī)模PopSize為40，分子反應(yīng)決定因子MoleColl為0.2，初始動能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。分別獨立運行30次，CROCS與GA、DPSO算法運行的結(jié)果如表9所示，收斂曲線如圖9所示。

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

圖9 收斂曲線

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

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

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

7 結(jié)束語

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