移動云環境中數據流應用的Cloudlet選擇策略研究

劉偉，熊曙，杜薇，王偉

（1. 武漢理工大學計算機科學與技術學院，湖北 武漢 430070；2. 交通物聯網技術湖北省重點實驗室，湖北 武漢 430070；3. 同濟大學計算機科學與技術系，上海 200092）

1 引言

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

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

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

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

1） 建立了移動數據流應用的 Cloudlet選擇問題的系統模型，旨在最小化應用完成時間和移動設備能耗，同時將問題定義為雙目標的組合優化問題，并證明該問題是NP-hard問題。

2） 設計了一個動態調整的適應度函數，根據移動設備的剩余電量調整應用完成時間與移動設備能耗的權值，進而采用線性加權法將該雙目標問題歸一成單目標問題。

3） 提出了一種基于化學反應優化算法的Cloudlet選擇策略CROCS（chemical reaction optimization Cloudlet selection strategy）。該策略能夠在滿足組件間依賴關系的前提下，充分利用移動數據流應用中可以并行執行的組件，提高了應用性能。

2 研究動機

本文所提出的移動數據流應用的Cloudlet選擇策略的主要思想是將移動數據流應用的并行組件分散到多個Cloudlet上執行，以提高應用的執行效率，減少完成時間。然后，將通過一個具有一般拓撲結構的移動數據流應用程序——光學字符識別（OCR，optical character recognition）在多Cloudlet環境中運行的例子驗證本文思想的正確性。

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

圖1 光學字符識別應用程序結構

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

圖2 移動數據流應用Cloudlet選擇場景

表1 不同選擇方案對應的應用完成時間

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

3 相關工作

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

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

4 系統模型

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

4.1 相關概念模型

1） 移動設備

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

2） Cloudlet

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

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

3） 網絡連接

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

4） Cloudlet選擇策略

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

4.2 移動數據流應用模型

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

4.3 應用完成時間模型

完成時間[8]是移動數據流應用一個重要的性能指標，表示應用程序從數據輸入到結果輸出的時間。完成時間越低表示應用的響應速度越快，用戶體驗越好。

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

其中，當xk=0且xi≠0,J時，表示組件vk在移動端執行，vi在除代理 CloudletJ之外的其他CloudLetxi上執行，其數據傳輸時間由 2個部分組成：1） 數據從移動設備傳輸到代理 CloudletJ的時間，2） 數據由代理CloudletJ傳輸到Cloudletxi上的時間。當xk=0且xi=J時，即組件vk在移動設備上執行，組件vi在代理CloudletJ上執行，其數據傳輸時間為組件間的數據量 datak,i與移動設備上傳數據帶寬Bu的比值。當xk,xi∈[1,m]且xi≠xk時，即組件vk和組件vi在不同的Cloudlet上執行，其數據傳輸時間為組件間的數據量 datak,i與Cloudlet之間的帶寬 B的比值。當xk≠0,J且xi=0時，即組件 vk在除了代理 CloudletJ之外的CloudLetxk上執行，組件 vi在移動設備上執行，其數據傳輸時間包括數據從Cloudletxk傳輸到代理CloudletJ的時間和數據從代理CloudletJ傳輸到移動設備的時間。當xk=J且xi=0時，表示組件vk在代理CloudletJ上執行，組件vi在移動設備上執行，其數據傳輸時間為組件間的數據傳輸量datak,i與移動設備下載數據的帶寬的比值。當xi=xk時，表示組件vk和組件vi在同一位置執行，其數據傳輸時間為0。

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

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

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

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

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

由此，可以得到應用的完成時間為

4.4 移動設備能耗模型

移動設備能耗主要由無線網絡接口、屏幕、CPU、GPS等部件產生的能耗[24]組成，本文主要考慮無線網絡接口數據傳輸和CPU能耗。

4.4.1 數據傳輸能耗

本文中數據傳輸能耗包括數據發送和接收時移動設備能量消耗。

1） 數據發送能耗

其 中 ，succ（i）表示組 件 vi后繼組 件 的集 合,表示移動設備無線網絡發送數據所用時間的總和。

2） 數據接收能耗

4.4.2 CPU能耗

CPU能耗包括計算能耗和空閑能耗。計算能耗表示有組件在移動設備上執行時CPU的能量消耗，空閑能耗為沒有組件在移動設備上執行時 CPU處于空閑狀態的能量消耗。

1） 計算能耗

2） 空閑能耗

空閑時間可以通過完成時間減去數據發送時間、數據接收時間和計算時間計算。

由此可以計算出空閑能耗

則移動設備能耗可以表示為

4.5 問題定義

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

約束條件如下。

限制條件（a）表示入口組件 v0和出口組件 vn必須在移動設備上執行，限制條件（b）表示中間組件的執行位置為移動設備或者 Cloudlet；限制條件（c）表示組件之間的依賴關系，即組件vi開始執行之前必須等待其前驅組件執行完成并將所需數據傳輸到該組件vi所在執行位置。

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

證明假設不考慮移動設備能耗，該問題就變成了最小化應用完成時間的單目標組合優化問題，并且認為開始組件和結束組件可以在任何計算節點上執行，則該問題可規約成式（13）形式。

約束條件如下。

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

5 算法設計

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

5.1 問題編碼

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

5.2 適應度函數

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

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

5.3 分子操作設計

1） 單分子碰撞

單分子碰撞ineff_coll（X,x1）：是指單個分子碰撞容器壁改變其勢能和動能的過程。分子的結構X發生輕微變化，產生新的分子結構x1，利用這一特點進行問題求解空間的領域搜索。

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

2） 單分子分解

單分子分解 decompose（X,x1,x2）：是指動能較大的分子與容器壁發生碰撞后，分解成2個分子的過程。分子X發生單分子分解后，將產生2個新的分子x1和x2，單分子分解反應過程中對分子結構的改變較大，用于提高算法的全局搜索能力。

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

3） 分子間碰撞

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

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

4） 分子合成

分子合成反應synthesis（X1,X2,x）：是指2個分子碰撞后合成一個新分子的過程，即原分子X1和X2發生分子合成碰撞后產生x。由于分子合成反應對分子結構的改變很大，提高分子搜索新區域能力，用于增強算法全局搜索能力。

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

5.4 算法描述

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

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

圖3 CROCS算法流程

算法1基于化學反應優化算法的Cloudlet選擇策略（CROCS）

輸入Mobile，Cloudlet，G（V,E），迭代次數MaxIter，權重參數α和β

輸出選擇策略X

1） 初 始 化 PopSize,Molecules,MoleColl,InitialKE/*PopSize為分子群初始規模，Molecules為分子群,MoleColl為分子反應決定類型因子，InitialKE為初始動能*/

2）i←1

3） whilei≤PopSize

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

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

6）f1（X）←computtotalenergy（X）/*依 據式（11）計算選擇策略分子X對應的移動設備能耗*/

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

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）/*發生單分子分解反應*/

19） else

20） ineff_coll（X,x1） /*發生單分子碰撞反應*/

21） else

22） 隨機從分子群Molecules中選擇2個分子X1和X2

23） if （synthesis criterion met） then synthesis（X1,X2,x）/*發生分子合成反應*/

25） else

26） iter_ineff_cole（X1,X2,x1,x2）/*發生分子間碰撞反應*/

27） end while

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

returnX

5.5 解空間分析

本節將分析問題的解空間，并給出選擇化學反應算法求解該問題的原因。

1） 解空間大小

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

2） 可選算法分析

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

5.6 時間復雜度分析

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

5.7 算法收斂性分析

化學反應算法收斂性主要取決于化學反應操作算子[32],經過基本的化學反應之后，令選擇策略X1到選擇策略X2的轉換概率 P（X1→X2）＞0, 選擇策略X1和X2屬于選擇策略任意元素。由于每一次迭代的獨立性，經過MaxIter次迭代過程后，算法不能從次優解達到全局最優解的概率是1- （1-p）MaxIter。因此算法經過 MaxIter次迭代后能夠達到最優解的概率是1-（1-p）MaxIter，當MaxIter→∞時，可以得到最優解的概率為所以當迭代次數足夠多時，算法總會收斂于全局最優解。

6 仿真實驗與結果分析

6.1 仿真實驗環境配置

1） Cloudlet和移動設備配置

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

表2 Cloudlet配置

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

表3 移動設備配置

2） 網絡配置

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

3） 移動數據流應用配置

為了不失一般性，實驗采用應用模型如圖1所示的光學字符識別移動數據流應用程序進行實驗。

6.2 實驗結果分析

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

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

1） Cloudlet之間的帶寬的影響

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

表4 實驗1環境配置

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

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

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

圖4 Cloudlet之間的帶寬對應用完成時間和移動設備能耗的影響

2） Cloudlet個數的影響

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

表5 實驗2環境配置

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

圖5 Cloudlet個數對應用完成時間和移動設備能耗的影響

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

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

3） 應用程序并行組件指令數在總指令數中占比的影響

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

表6 實驗3環境配置

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

圖6 并行組件指令數占比對應用完成時間和移動設備能耗的影響

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

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

4） 移動設備與Cloudlet之間帶寬的影響

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

表7 實驗4環境配置

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

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

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

圖7 移動設備與Cloudlet之間的距離對應用完成時間和移動設備能耗的影響

5） 參數α的影響

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

表8 實驗5環境配置

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

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

圖8 參數α對應用完成時間和移動設備能耗的影響

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

6） 收斂特性

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

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

表9 CROCS與GA、DPSO運行結果

圖9 收斂曲線

如表9所示，CROCS相較于GA和DPSO策略得到全局最優解的概率更高。其次，對應的平均適應度和最大適應度值也相對于GA和DPSO策略更優，并且從標準差看CROCS策略有更高的求解穩定性。因此，CROCS相較于GA和DPSO策略有更好的全局收斂性。

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

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

7 結束語

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