劉鵬飛 毛鶯池 王龍寶

摘 要：針對在云霧協(xié)作下實現(xiàn)移動用戶任務(wù)請求的合理分配與調(diào)度的問題，提出了一種基于云霧協(xié)作模型的任務(wù)分配算法——IGA。首先，采用混合編碼的方式對個體進行編碼，并采用隨機的方式產(chǎn)生初始種群;其次設(shè)定服務(wù)商的花費作為目標(biāo)函數(shù);然后進行選擇、交叉、變異操作產(chǎn)生出符合條件的新個體;最后，根據(jù)染色體中的任務(wù)請求類型分配到相應(yīng)的資源節(jié)點上，并更新迭代計數(shù)器，直到迭代完成。仿真結(jié)果表明，在處理移動用戶請求時，與傳統(tǒng)的云模型相比，云霧協(xié)作模型在時延上降低了近30s，服務(wù)水平目標(biāo)（SLO）違規(guī)率上降低了約10個百分比，在服務(wù)提供商花費上亦有所減少。

關(guān)鍵詞：云計算;霧計算;任務(wù)分配;任務(wù)調(diào)度;遺傳算法

中圖分類號： TP393.027

文獻標(biāo)志碼：A

Abstract： To realize reasonable allocation and scheduling of mobile user task requests under cloud and fog collaboration， a task assignment algorithm based on cloud-fog collaboration model， named IGA （Improved Genetic Algorithm）， was proposed. Firstly， individuals were coded in the way of mixed coding， and initial population was generated randomly. Secondly， the objective function was set as the cost of service providers. Then select， cross， and mutate were used to produce new qualified individuals. Finally， the request type in a chromosome was assigned to the corresponding resource node and iteration counter was updated until the iteration was completed. The simulation results show that compared with traditional cloud model， cloud-frog collaboration model reduces the time delay by nearly 30 seconds， reduces Service Level Objective （SLO） violation rate by nearly 10%， and reduces the cost of service providers.

Key words： cloud computing; fog calculating; task allocation; task scheduling; Genetic Algorithm （GA）

0 引言

隨著網(wǎng)絡(luò)邊緣設(shè)備數(shù)量的迅速增加，邊緣設(shè)備產(chǎn)生的數(shù)據(jù)量越來越大，已經(jīng)達(dá)到了澤字的級別。根據(jù)國際電信聯(lián)盟（International Telecommunication Union-Telecommunication Sector， ITU-T）的報告顯示，到2020年，每人每秒將會產(chǎn)生1.7MB的數(shù)據(jù)[1]，顯然人類已經(jīng)進入了大數(shù)據(jù)時代。集中式的云已經(jīng)不能高效處理邊緣設(shè)備產(chǎn)生的海量數(shù)據(jù)[2]。霧計算是對云計算的延伸，它是在終端節(jié)點和遠(yuǎn)端云之間再擴展的一層，也可以叫邊緣網(wǎng)絡(luò)層。在物聯(lián)網(wǎng)應(yīng)用中有些請求的處理并不需要放到遠(yuǎn)端的云，而是可以直接在距離用戶較近的霧端進行處理。圖1是一個簡單的霧計算架構(gòu)圖[3]，底層是物聯(lián)網(wǎng)設(shè)備層，該層由移動終端（如智能手機、平板電腦等）組成，主要用于信息收集;中間層是霧計算層，該層主要是由霧設(shè)備（如路由器、網(wǎng)關(guān)、小型服務(wù)器等）組成，這些霧設(shè)備通常具有一定的處理能力來完成部分任務(wù)處理;上層是云數(shù)據(jù)中心層，該層主要是由云服務(wù)器組成，云服務(wù)器用來分析和處理大量數(shù)據(jù)?；谶@種架構(gòu)模式，霧計算具有低延遲、移動性支持、位置感知等[2]特征。

霧計算將云提供的服務(wù)擴展到網(wǎng)絡(luò)邊緣來提供本地化的服務(wù)，這有效滿足了移動用戶對低時延、移動性支持、位置感知的服務(wù)需求（架構(gòu)如圖1）;然而移動用戶的任務(wù)請求并非完全是基于本地化的，也可能需要發(fā)送到云端進行處理，為此云霧協(xié)作的服務(wù)模式應(yīng)運而生?，F(xiàn)有的針對云霧協(xié)作服務(wù)模式的研究已經(jīng)取得了一些成果，但是仍然存在不足。首先，當(dāng)前研究在云霧協(xié)作模式下分配任務(wù)請求時未能有效判斷任務(wù)請求的類型;其次，當(dāng)前研究在分配任務(wù)請求時通常采用靜態(tài)分配資源的方式，未能動態(tài)給任務(wù)分配資源，而這些不足可能會給用戶造成高時延的不良體驗。針對此問題，本文提出了基于云霧協(xié)作模型的任務(wù)分配算法。該算法能夠判斷任務(wù)請求的類型，動態(tài)在云霧資源節(jié)點上進行分配。在云霧協(xié)作模型下分配任務(wù)請求時以該算法作為分配策略并以服務(wù)提供商花費作為目標(biāo)函數(shù)展開研究。實驗結(jié)果表明，與傳統(tǒng)云模型相比，云霧協(xié)作模型在處理移動用戶請求時在時延上降低了近30s，服務(wù)水平目標(biāo)（Service Level Objective， SLO）違規(guī)率上降低了10%左右，在服務(wù)提供商花費上亦有所減少。

1 相關(guān)工作

目前基于霧計算的研究還處于發(fā)展階段，關(guān)于霧端的任務(wù)分配與調(diào)度還是一個較新的研究熱點。吳翠云等文獻[4]中文獻4的作者姓名不是這個名字，請調(diào)整語句引用，注意在正文中要按照文獻的先后順序進行引用針對物聯(lián)網(wǎng)檢測節(jié)點的原始數(shù)據(jù)如何高效地處理問題，提出“云+霧”的分級運算模式。霧端資源節(jié)點接收到原始數(shù)據(jù)時會判斷這些數(shù)據(jù)是否能夠在本地處理完成，若能夠在本地處理完成，則采用分布式計算的方式處理數(shù)據(jù)，最后反饋給被控終端;若不能夠在本地處理完成，則將分析處理后的數(shù)據(jù)交給遠(yuǎn)端的云服務(wù)器，由云服務(wù)器再次進行處理，之后將處理結(jié)果反饋到霧端，由霧端調(diào)整被控終端。Deng等[5]針對云霧計算環(huán)境中的能耗和時延問題，提出將能耗和時延問題分為三個子問題并通過現(xiàn)有的優(yōu)化技術(shù)進行解決。第一個子問題是在霧計算子系統(tǒng)中優(yōu)化功耗和時延，為了解決這個問題，文獻[6]中采用了凸優(yōu)化技術(shù)。第二個子問題是一個整數(shù)非線性規(guī)劃問題，致力于在云環(huán)境中優(yōu)化功耗和時延。為了解決這個問題，文獻[7]中采用了非線性的整數(shù)規(guī)劃方法。第三個子問題是最小化數(shù)據(jù)從霧節(jié)點到云服務(wù)器的傳輸延遲，針對這個問題，文獻[8]中采用了匈牙利方法。Song等[9]提出一個基于圖分區(qū)的霧計算任務(wù)負(fù)載平衡機制。根據(jù)終端任務(wù)請求所需的資源級別將任務(wù)分配給單個或多個虛擬資源節(jié)點。虛擬資源節(jié)點通過圖分區(qū)向終端用戶提供服務(wù)。Cardellini等[10]評估了霧計算環(huán)境中的分布式服務(wù)質(zhì)量調(diào)度器，該調(diào)度器主要包括工作監(jiān)視器、服務(wù)質(zhì)量（Quality of Service， QoS）監(jiān)視器、自適應(yīng)調(diào)度器。其中：工作監(jiān)視器負(fù)責(zé)獲取霧節(jié)點上計算組件傳入和傳出的數(shù)據(jù);QoS監(jiān)視器負(fù)責(zé)估計QoS參數(shù)（例如網(wǎng)絡(luò)等待時間）;自適應(yīng)調(diào)度器周期性地運行，負(fù)責(zé)檢查每個計算組件要執(zhí)行的任務(wù)。Oueis等[11]為了提高用戶的體驗質(zhì)量，對霧計算環(huán)境中的負(fù)載均衡問題進行了研究。文獻[12]中提出了一種改進的遺傳算法（Genetic Algorithm， GA），用于處理霧端的任務(wù)調(diào)度和減少CPU執(zhí)行時間，實驗結(jié)果表明該算法在霧端調(diào)度時間緊迫型任務(wù)時要優(yōu)于傳統(tǒng)的基本遺傳算法（Simple Genetic Algorithm， SGA）。本文與其不同的是初始種群隨機生成，采用了不同的交叉變異概率參數(shù)以及可以動態(tài)地進行任務(wù)分配，并提出了一種可應(yīng)用的實際場景。在霧計算架構(gòu)中任務(wù)調(diào)度、管理和操作的目的是為移動用戶提供一個高效、低成本的服務(wù)。文獻[13]中提出一個新的生物啟發(fā)式優(yōu)化算法，該算法在問題空間搜索最優(yōu)解的過程中引入了遺傳算法中的選擇、交叉操作，這有效擴大了基因的多樣性，使得算法具有了更強的全局搜索能力。實驗結(jié)果表明，在霧端資源節(jié)點分配任務(wù)請求時該算法能夠獲得更短的執(zhí)行時間以及更少的內(nèi)存消耗。

以上研究工作更多考慮的是任務(wù)在調(diào)度過程中的時延、能耗、網(wǎng)絡(luò)延遲等問題，并沒有考慮更多服務(wù)質(zhì)量的問題。文獻[14]中針對用戶任務(wù)請求在虛擬機上的分配問題，提出一種資源分配算法，該算法的思想是當(dāng)用戶請求到達(dá)時優(yōu)先將請求分配到能夠滿足用戶需求的最小空間上處理，目的是減少空間浪費以及服務(wù)等級協(xié)議（Service-Level Agreement， SLA）違規(guī)。文獻[15]中針對用戶在多維QoS方面的需求，提出QBD-Sufferage（請補充QB-Sufferage的英文全稱Quality of service Deadline-Sufferage）算法，該算法在傳統(tǒng)Sufferage算法基礎(chǔ)上引入了效益函數(shù)和QoS約束。實驗結(jié)果表明QBD-Sufferage算法要比傳統(tǒng)Sufferage算法獲得更高的效益值。文獻[16]中指出QoS約束對于霧計算來說非常重要，其約束指標(biāo)主要包括時間、可靠性、連接性、網(wǎng)絡(luò)帶寬、存儲容量。

2 問題陳述

2.1 問題陳述

在霧計算架構(gòu)下移動用戶的成本開銷與CPU的執(zhí)行時間成正比，所以為了減少移動用戶的成本開銷，則需要通過優(yōu)化霧資源節(jié)點上的任務(wù)分配來減少CPU的執(zhí)行時間。在霧計算環(huán)境中任務(wù)請求分配與調(diào)度本質(zhì)上是一種優(yōu)化類問題，很難在問題空間中搜索到全局最優(yōu)解。隨著資源節(jié)點和終端任務(wù)請求數(shù)的急劇增加，傳統(tǒng)的任務(wù)分配與調(diào)度算法已經(jīng)不能夠很好地滿足實際應(yīng)用的需求，一些群智能分配算法逐漸被引入，常見的群智能算法有遺傳算法、模擬退火算法、蟻群算法等。本文中使用了遺傳算法的相關(guān)知識。傳統(tǒng)遺傳算法作為一個經(jīng)典的任務(wù)分配算法能夠有效地在霧端資源節(jié)點上分配任務(wù)請求，但是容易出現(xiàn)早熟現(xiàn)象，陷入局部最優(yōu)[17]，無法在問題空間搜索到較好的分配結(jié)果。

2.2 遺傳算法

SGA主要特點是直接對結(jié)構(gòu)對象進行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則[18]，即通過對生物繁殖和進化過程中染色體的選擇、交叉、變異等操作的模仿來完成對問題空間最優(yōu)解的尋找[19]。SGA的整體流程如圖2所示。

SGA具有如下特點。

1）并行性。SGA與其他優(yōu)化算法最大的不同在于求解過程。SGA在求解過程中是從問題空間中的一個解集開始而并非一個單一的解，因此SGA具有一定的并行性以及搜索的隨機性。

2）自適應(yīng)性。SGA在求解的過程中根據(jù)適應(yīng)度函數(shù)值的大小來決定個體進化的概率，適應(yīng)度值越大個體被保留下來的概率越大，適應(yīng)度值越小個體被保留下來的概率越小，因此SGA具有一定的自適應(yīng)性。

3）易擴展性。SGA是其他改進遺傳算法的原型和基礎(chǔ)，經(jīng)過簡單改進便可以和其他算法結(jié)合使用，因此SGA具有很強的易擴展性。

4）簡單性。SGA模仿生物遺傳進化的思想，易于理解，因此便于應(yīng)用在大量實際問題求解的過程中。

SGA雖然具有很多優(yōu)點，但是也存在一些待改進的地方。一方面，算法在尋找簡單函數(shù)最優(yōu)解的過程中易出現(xiàn)“早熟現(xiàn)象”即局部收斂現(xiàn)象;另一方面，算法在迭代過程中易出現(xiàn)大量冗余迭代。

3 基于云霧協(xié)作模型的任務(wù)分配方法

3.1 算法思路

針對上述問題，本文在傳統(tǒng)遺傳算法的基礎(chǔ)上作了進一步研究，提出了基于云霧協(xié)作模型的任務(wù)分配算法——IGA（Improved Genetic Algorithm）。IGA在基本遺傳算法SGA基礎(chǔ)上作了進一步優(yōu)化。該任務(wù)分配算法在SGA中引入了請求類型判斷策略，在變異操作之后對任務(wù)請求類型進行判斷。該算法會根據(jù)任務(wù)請求的類型，動態(tài)地將任務(wù)請求分配到云霧資源節(jié)點上。

3.2 云霧協(xié)作模型

本文以大型賽事活動為例來講述傳統(tǒng)云模型和云霧協(xié)作模型的區(qū)別。在大型賽事活動中，移動用戶的查詢請求更多傾向于賽事活動相關(guān)內(nèi)容或者賽事活動周邊的超市、餐館等信息。假設(shè)賽事活動現(xiàn)場的移動用戶發(fā)出查詢請求，若使用傳統(tǒng)云計算服務(wù)模型[20]來處理移動用戶請求，那么活動主辦方首先需要將賽事活動相關(guān)信息上傳到遠(yuǎn)端的云服務(wù)器，然后移動用戶和云數(shù)據(jù)中心建立一個長距離的通信連接，最后檢索內(nèi)容、處理請求。若使用圖3云霧協(xié)作服務(wù)模型[20]來處理移動用戶請求，則可以有效縮短通信距離?；顒又鬓k方可以在大型賽事活動內(nèi)部署本地站點，預(yù)先緩存本地的內(nèi)容，通過這種方式移動用戶可以享受高速率的本地連接而無需和遠(yuǎn)端的云進行通信，除非移動用戶的查詢請求不能基于本地化的霧實現(xiàn)時，才需要和遠(yuǎn)端的云進行通信。本地站點即本地霧計算信息系統(tǒng)，它可以通過部署在賽事活動現(xiàn)場不同地方的霧服務(wù)器共同形成。不同地方的霧服務(wù)器可以預(yù)先緩存特定內(nèi)容，然后通過WiFi為移動用戶提供精確的基于位置的服務(wù)。

在使用圖3所示的云霧協(xié)作服務(wù)模型處理移動用戶請求時，可以給移動用戶帶來兩個直接的優(yōu)勢：

1）通過霧系統(tǒng)處理用戶本地請求可以降低服務(wù)延遲;

2）通過本地連接查詢內(nèi)容的方式可以降低使用帶寬的成本。

3.3 云霧協(xié)作模型下任務(wù)分配

以上面提到的大型賽事活動為例，移動用戶的任務(wù)請求傾向于是賽事活動的相關(guān)信息或者活動現(xiàn)場周邊的商店、餐館等信息，但也可能是非本地化的查詢請求，需要和遠(yuǎn)端的云進行通信，那么采用圖3所示的云霧協(xié)作服務(wù)模型處理移動用戶請求的步驟如下：

1）移動用戶提交任務(wù)請求到近端霧計算資源節(jié)點。

2）霧計算資源節(jié)點提交任務(wù)請求相關(guān)參數(shù)到遠(yuǎn)端云數(shù)據(jù)中心資源管理節(jié)點。

3）云數(shù)據(jù)中心資源管理節(jié)點根據(jù)任務(wù)請求相關(guān)參數(shù)以及分配策略判斷移動用戶的請求類型，若請求類型是本地化的查詢請求，則將任務(wù)請求分配到近端霧計算資源節(jié)點;否則分配到遠(yuǎn)端云計算資源節(jié)點，最后找到最優(yōu)任務(wù)請求分配結(jié)果。

4）云數(shù)據(jù)中心資源管理節(jié)點將最優(yōu)任務(wù)請求分配結(jié)果反饋到霧端。

5）霧端根據(jù)最優(yōu)分配結(jié)果將非本地的任務(wù)請求發(fā)送到云數(shù)據(jù)中心。

6）霧計算資源節(jié)點根據(jù)最優(yōu)分配結(jié)果執(zhí)行本地化的任務(wù)請求。

7）云計算資源節(jié)點根據(jù)最優(yōu)分配結(jié)果執(zhí)行非本地化的任務(wù)請求。

8）云數(shù)據(jù)中心將任務(wù)請求執(zhí)行結(jié)果反饋到霧端。

9）霧系統(tǒng)匯總處理結(jié)果，響應(yīng)移動用戶。

任務(wù)請求分配模型如圖4所示。

3.4 任務(wù)分配算法

基于云霧協(xié)作模型的任務(wù)分配算法包括以下9個部分，各部分的規(guī)則設(shè)計如下。

1）對個體進行編碼。本文采用文獻[21]中的編碼方式，染色體的長度等于任務(wù)請求數(shù)量的兩倍。如果任務(wù)的請求數(shù)目為m，則每一條染色體的有2×m個基因。其中前m個基因表示霧計算資源節(jié)點情況，后m個基因表示任務(wù)請求的分配順序。假設(shè)一條染色體為51234521234567，則任務(wù)請求和霧計算資源節(jié)點之間的對應(yīng)關(guān)系如表1所示，從表1中可以看出終端任務(wù)請求1和6分配到了霧計算資源節(jié)點5上，任務(wù)請求2分配到了霧計算資源節(jié)點1上，任務(wù)請求3和7分配到了霧計算資源節(jié)點2上，任務(wù)請求4分配到了霧計算資源節(jié)點3上，任務(wù)請求5分配到了霧計算資源節(jié)點4上。

2）初始種群生成。該算法中的初始種群采用隨機的方式生成，并且根據(jù)約束條件選擇有效方案。假設(shè)初始種群g（0），設(shè)定迭代計數(shù)器i=0，g（i）表示第i代種群。具體約束條件參考以下兩個方面：

①不能將所有任務(wù)請求分配到同一個霧計算資源節(jié)點上，造成嚴(yán)重負(fù)載不均。

②同一個任務(wù)請求不能被分配到不同的資源節(jié)點上處理，但是一個資源節(jié)點上可以處理多個任務(wù)請求。

生成初始種群的偽代碼如下。

3）計算個體適應(yīng)度值。在霧計算架構(gòu)下移動用戶任務(wù)請求分配過程中，適應(yīng)度函數(shù)是評價群體進化方向的關(guān)鍵，也是執(zhí)行遺傳算法“優(yōu)勝劣汰”的主要依據(jù)。這里以服務(wù)提供商的花費作為目標(biāo)函數(shù)。

4）終止條件判斷。當(dāng)進化代數(shù)達(dá)到規(guī)定迭代次數(shù)I時，輸出結(jié)果;否則轉(zhuǎn)到步驟5）。

5）選擇操作。在本算法中通過一種選擇操作，將優(yōu)良個體的特性遺傳到下一代個體中，以體現(xiàn)“優(yōu)勝劣汰”的原則，該算法中的選擇操作采用了一種基于輪盤賭算法的方式來進行。具體步驟如下。

①根據(jù)適應(yīng)度函數(shù)公式計算出所有個體適應(yīng)度值，累計求出適應(yīng)度值總和。

②計算出每個個體即每個染色體被選擇的概率，概率公式如式（1）所示：

其中：pi代表每個染色體的被選擇概率， f代表適應(yīng)度計算公式，M代表染色體個數(shù)。

③將每個概率值組成一個區(qū)域，所有概率值之和為1。

④隨機產(chǎn)生一個（0，1）區(qū)間上的隨機數(shù)，根據(jù)該隨機數(shù)出現(xiàn)在上述哪個概率區(qū)來確定哪個個體被選中。

例如，假設(shè)輪盤被分成了四份，第一個個體所占的比例為24%，第二個個體所占的比例為23%，第三個個體所占的比例為18%，第四個個體所占的比例為35%，則第一個個體構(gòu)成的區(qū)間是（0，0.24]，第二個個體構(gòu)成的區(qū)間是（0.24，0.47]，第三個個體構(gòu)成的區(qū)間是（0.47，0.65]，第四個個體構(gòu)成的區(qū)間是（0.65，1）區(qū)間表達(dá)仍不規(guī)范，如在等于0.24時，屬于哪個區(qū)別，請用閉區(qū)間來表示，類似于“（0，0.24]”、“（0.24，0.47]”的表達(dá)。四處均要修改這四處遺漏了區(qū)間表達(dá)，請用開閉區(qū)間來彼此區(qū)分。對于四個區(qū)間的修改，依次分別為：（0，0.24]，（0.24，0.47]，（0.47，0.65]，（0.65，1）。。如果隨機產(chǎn)生的隨機數(shù)為0.23，那么該次選擇的個體是第一個;如果隨機產(chǎn)生的隨機數(shù)為0.28，那么該次選擇的個體是第二個，以此來確定個體被選中的次數(shù)，更加直觀的描述如圖5輪盤所示。

6）交叉操作。交叉操作是實現(xiàn)基因重組的主要手段，類似于生物學(xué)有性繁殖的過程，使不同的個體基因片段相互交換，產(chǎn)生新的個體。本文針對不同的隊列采用不同的交叉方式，每個隊列會產(chǎn)生對應(yīng)的一個新的個體，最后把兩個隊列對應(yīng)的新個體合并，形成一個完整的新個體。其中資源隊列采用單點交叉，交叉點位置隨機產(chǎn)生;任務(wù)隊列采用部分匹配交叉，隨機產(chǎn)生交叉點。對于新產(chǎn)生的個體檢查是否符合約束條件，如果不符合則摒棄，重新進行交叉，直至新個體滿足約束條件。

交叉操作偽代碼如下。

7）變異操作?；蛲蛔兪菍崿F(xiàn)染色體內(nèi)部基因改變的有效手段。與交叉操作類似，針對不同的隊列采用不同的變異方式，最后把兩個隊列產(chǎn)生的新個體合成一個完整的新個體，并對新個體進行約束條件的檢查。如果不符合約束條件則摒棄，重新進行變異操作，直至新個體符合約束條件。其中資源隊列采用的變異方法為隨機操作，即隨機選取變異的基因位置，讓其等位基因來替換;任務(wù)請求隊列采用的變異方法為設(shè)定發(fā)生變異基因的位數(shù)Z（Z為整數(shù)），隨機選取變異點，以變異點為起點，對其隨后的Z個基因采用完全排列組合方式產(chǎn)生出新個體。

變異操作偽代碼如下：

8）請求類型判斷。判斷變異后染色體后半部分任務(wù)請求的類型，若請求類型是近端相關(guān)內(nèi)容，則將相關(guān)請求分配到近端霧計算資源節(jié)點;否則分配到云計算資源節(jié)點。

9）更新迭代計數(shù)器。迭代計數(shù)器i=i+1，轉(zhuǎn)到步驟3）。

3.5 目標(biāo)函數(shù)

云霧協(xié)作模型下的任務(wù)分配是指在一個特定的云霧環(huán)境中，根據(jù)一定的分配策略，盡可能地滿足移動用戶的需求，同時最小化服務(wù)提供商的花費。本文算法中的目標(biāo)函數(shù)主要考慮的是服務(wù)提供商的花費，該花費主要包括云霧計算資源節(jié)點處理終端任務(wù)請求的花費和SLO違規(guī)時的懲罰兩個方面。SLO作為SLA具體可測量的特征，包括可用性、響應(yīng)時間、質(zhì)量等，它可以量化服務(wù)提供商的服務(wù)水平。SLO違規(guī)率越低，則用戶滿意度越高。

1）SLO違規(guī)懲罰函數(shù)。設(shè)Penalty此處遺漏了一個字符，請補充表示發(fā)生SLO違規(guī)的總懲罰花費，則違規(guī)懲罰函數(shù)定義如式（2）所示：

其中：k表示因為服務(wù)超時而發(fā)生SLO違規(guī)的請求序號，tstopk表示第k個請求的實際響應(yīng)時間，tdeadlinek表示第k個請求在SLO規(guī)定中的請求截止響應(yīng)時間，q表示發(fā)生SLO違規(guī)的請求總個數(shù)，γk表示第k個發(fā)生SLO違規(guī)的請求基本懲罰，η表示因發(fā)生超時而導(dǎo)致的單位時間懲罰。

2）云霧計算資源節(jié)點花費函數(shù)。設(shè)vm表示云霧計算資源節(jié)點處理請求的總花費，則云霧計算資源節(jié)點花費函數(shù)定義如式（3）所示：

其中：n表示云端和霧端虛擬資源的類型總個數(shù)，Pvmi， j表示類型為i的虛擬資源節(jié)點中序號為j的虛擬資源節(jié)點運行的單價成本，vmci表示第i個類型的計算資源處理請求的總花費，ti， j表示類型為i的虛擬資源節(jié)點中序號為j的虛擬資源節(jié)點處理請求所花費的時間，Mi表示類型為i的虛擬資源節(jié)點的個數(shù)。

綜上有服務(wù)提供商總花費函數(shù)。設(shè)cost表示服務(wù)提供商總花費，則總花費函數(shù)定義如式（5）所示：

3.6 判斷策略

基于云霧協(xié)作的任務(wù)分配算法在變異操作之后判斷終端任務(wù)請求類型，若請求類型是基于位置感知的近端相關(guān)內(nèi)容，則將相關(guān)請求分配到近端霧計算資源節(jié)點進行處理;否則分配到云計算資源節(jié)點進行處理。具體任務(wù)請求判斷策略如下。

判斷變異后染色體的后半部分任務(wù)請求類型，請求類型分為兩種。

1）若請求類型是本地的霧端請求，則進一步判斷其對應(yīng)的資源節(jié)點，如果對應(yīng)的資源節(jié)點是霧端資源則不作處理，如果不是霧端資源，則將該資源節(jié)點突變?yōu)槟軌蚴沟卯?dāng)前霧端完成時間最短的霧資源節(jié)點。

2）若請求類型是非本地的云端請求，則進一步判斷其對應(yīng)的資源節(jié)點：如果對應(yīng)的資源節(jié)點是云端資源則不作處理;如果不是云端資源，則將該資源節(jié)點突變?yōu)槟軌蚴沟卯?dāng)前云端完成時間最短的云資源節(jié)點。

例如，對于變異后的染色體

其中前六位數(shù)中的1、2、3、4、5表示五個資源，設(shè)4、5表示霧端資源，1、2、3表示云端資源，后面六位數(shù)1、2、3、4、5、6表示六個任務(wù)請求，設(shè)1、2、3、4表示霧端任務(wù)請求，5、6表示云端任務(wù)請求。

對于上面的染色體X，任務(wù)請求和資源節(jié)點的對應(yīng)關(guān)系如表2所示，任務(wù)請求1分配到了云資源節(jié)點1上，任務(wù)請求2分配到了霧資源節(jié)點5上，任務(wù)請求3和6分配到了霧資源節(jié)點4上，任務(wù)請求4分配到了云資源節(jié)點3上，任務(wù)請求5分配到了云資源節(jié)點2上。顯然有些霧端的任務(wù)請求并沒有被分配到霧端資源節(jié)點上，所以對于沒有被分配到霧端的任務(wù)請求讓其對應(yīng)的云端資源節(jié)點突變?yōu)槟軌蚴沟卯?dāng)前霧端完成時間最小的資源節(jié)點。對于沒有分配到云端的任務(wù)請求以同樣的方式處理。

4 實驗及其結(jié)果分析

4.1 實驗設(shè)置

仿真實驗環(huán)境設(shè)置：仿真軟件CloudSim3.0.2;處理器Intel core i5-4210M CPU @2.60GHz;內(nèi)存12GB;操作系統(tǒng)Windows 10旗艦版;開發(fā)工具MyEclipse8.5、JDK1.7.0_15;開發(fā)語言Java。

終端任務(wù)請求由系統(tǒng)模擬產(chǎn)生，其個數(shù)設(shè)置為100～1000，長度設(shè)置為500～15000MI。資源節(jié)點數(shù)設(shè)置為6，其中4個為云計算資源節(jié)點，2個為霧計算資源節(jié)點，云計算和霧計算資源節(jié)點參數(shù)如表3，表3中單價參考文獻[22]來設(shè)置。違規(guī)基本懲罰設(shè)置為2，單位時間懲罰設(shè)置為5。IGA各參數(shù)設(shè)置如表4所示。

4.2 實驗結(jié)果

本文對傳統(tǒng)云模型下采用的IGA任務(wù)分配算法CLOUD-IGA、輪詢調(diào)度算法（Round-Robin Scheduling Algorithm，RRSA）CLOUD-RRSA以及云霧協(xié)作模型下采用的該任務(wù)分配算法FOG-IGA進行仿真實驗。首先作了FOG-IGA、CLOUD-IGA以及CLOUD-RRSA的時延對比實驗;其次作了FOG-IGA和CLOUD-IGA的SLO違規(guī)率、服務(wù)提供商花費對比實驗。其中IGA在傳統(tǒng)云模型下分配任務(wù)請求時不考慮任務(wù)請求類型判斷。為了實驗結(jié)果的有效性，CLOUD-IGA分配策略和FOG-IGA分配策略均以10次運行結(jié)果的平均值作為最終實驗結(jié)果。

通過設(shè)置不同的終端請求數(shù)來比較FOG-IGA、CLOUD-IGA以及CLOUD-RRSA的時延。實驗結(jié)果如圖6所示。

觀察圖6可以發(fā)現(xiàn)隨著終端請求數(shù)的變化，與CLOUD-IGA和CLOUD-RRSA方法相比，F(xiàn)OG-IGA在時延上具有優(yōu)勢。主要是因為FOG-IGA將本地化的請求分配到了近端霧計算資源節(jié)點上進行處理，而CLOUD-IGA和CLOUD-RRSA完全將用戶請求分配到遠(yuǎn)端的云進行處理，沒有判斷用戶請求的類型，所以在時延上較高。在云端分配任務(wù)請求時CLOUD-IGA整體優(yōu)于CLOUD-RRSA，主要是因為該算法模擬了生物遺傳和進化機制，在問題空間中通過多次迭代搜索到了較好的分配結(jié)果。FOG-IGA和CLOUD-IGA在時延上并沒有很大的差距，主要是因為霧端資源節(jié)點的處理能力相對較弱，但其接近終端用戶的特點對于處理本地化的請求還是具有一定優(yōu)勢。

實驗2 SLO違規(guī)率及服務(wù)提供商花費對比實驗。

通過設(shè)置不同的終端請求數(shù)來比較FOG-IGA和CLOUD-IGA的SLO違規(guī)率以及服務(wù)提供商花費。實驗結(jié)果如圖7～8所示。

從圖7可以看出，F(xiàn)OG-IGA在違規(guī)率方面整體上低于CLOUD-IGA，主要是因為FOG-IGA在分配任務(wù)請求時考慮了用戶請求的類型，將本地化的請求分配到了近端霧資源節(jié)點，非本地化的請求分配到了遠(yuǎn)端云資源節(jié)點，這有效縮短了響應(yīng)時間，所以降低減少了SLO違規(guī);但是在任務(wù)請求數(shù)達(dá)到1000時SLO違規(guī)率突然變高，可能原因是本地化的請求較多，而霧資源節(jié)點處理能力不足，導(dǎo)致部分任務(wù)請求不能在規(guī)定時間內(nèi)完成。CLOUD-IGA在SLO違規(guī)率上較高，主要是因為該分配策略沒有判斷任務(wù)請求的類型，完全將用戶請求在距離用戶較遠(yuǎn)的云端進行分配，增加了響應(yīng)時間。

從圖8可以看出，F(xiàn)OG-IGA在服務(wù)提供商花費方面整體上也低于CLOUD-IGA，主要原因有兩個：

1）該分配策略整體違規(guī)率較低，在服務(wù)提供商花費函數(shù)中違規(guī)率越低，SLO違規(guī)時的懲罰就越少;

2）霧端資源節(jié)點單位時間的費用較低，該分配策略將本地化的任務(wù)請求分配到了近端霧資源節(jié)點。

文中服務(wù)提供商的花費主要包括云霧資源節(jié)點處理終端任務(wù)請求的花費和SLO違規(guī)時的懲罰兩個方面，而FOG-IGA有效降低了這兩個方面的花費，所以在總花費上有所降低。

綜合上述實驗結(jié)果可見，霧端資源節(jié)點對于處理一定量的本地化請求具有明顯優(yōu)勢，但是隨著本地化任務(wù)請求數(shù)的增多其優(yōu)勢可能會不那么明顯，甚至不如遠(yuǎn)端的云。

5 結(jié)語

本文針對移動用戶的不同請求在云霧資源節(jié)點上的分配問題，提出了基于云霧協(xié)作的任務(wù)分配算法。在云霧協(xié)作模型下分配任務(wù)請求時以該算法作為分配策略展開研究。仿真實驗結(jié)果表明在處理移動用戶請求時，與傳統(tǒng)云模型相比，云霧協(xié)作模型在時延上降低了近30s，SLO違規(guī)率上降低了約10個百分比，在服務(wù)提供商花費上亦有所減少。

參考文獻 （References）

[1] The World Telecommunication Standardization Assembly. ITU.WTSA-16： setting the standard[R]. Yasmine Hammamet： WTSA-16， 2016： 1-9.

[2] CHIANG M， ZHANG T. Fog and IoT： an overview of research opportunities[J]. IEEE Internet of Things Journal， 2017， 3（6）： 854-864.

[3] SARKAR S， MISRA S. Theoretical modelling of fog computing： a green computing paradigm to support IoT applications[J]. IET Networks， 2016， 5（2）： 23-29.

[4] 北京物聯(lián)遠(yuǎn)信息技術(shù)有限公司.一種面向物聯(lián)網(wǎng)的霧計算架構(gòu)：中國，201511019375.3[P].2016-05-25. （Beijing Wulianyuan Information Technology Co.， Ltd. A fog computing architecture for the Internet of Things： China， 201511019375.3 [P].2016-05-25.）

[5] DENG R， LU R， LAI C， et al. Optimal workload allocation in fog-cloud computing towards balanced delay and power consumption[J]. IEEE Internet of Things Journal， 2016， 3（6）： 1171-1181.

[6] HE J， CHENG P， SHI L， et al. Time synchronization in WSNs： a maximum-value-based consensus approach[J]. IEEE Transactions on Automatic Control， 2014， 59（3）： 660-675.

[7] LI D， SUN X L. Nonlinear Integer Programming[M]. Berlin： Springer， 2006： 70-82.

[8] KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics， 2010， 52（1）： 7-21.

[9] SONG N N， GONG C， AN X S， et al. Fog computing dynamic load balancing mechanism based on graph repartitioning[J]. China Communications， 2016， 13（3）： 156-164.

[10] CARDELLINI V， GRASSI V， PRESTI F L， et al. On QoS-aware scheduling of data stream applications over fog computing infrastructures[C]// Proceedings of the 2015 IEEE Symposium on Computers and Communication. Piscataway， NJ： IEEE， 2016： 271-276.

[11] OUEIS J， STRINATI E C， BARBAROSSA S. The fog balancing： load distribution for small cell cloud computing [C]// Proceedings of the 2015 IEEE 81st Vehicular Technology Conference. Piscataway， NJ： IEEE， 2015：1-6.

[12] 韓奎奎，謝在鵬，呂鑫.一種基于改進遺傳算法的霧計算任務(wù)調(diào)度策略[J].計算機科學(xué)，2018，45（4）：137-142.（HAN K K， XIE Z P， LYU X. A fog computing task scheduling strategy based on improved genetic algorithm[J]. Computer Science， 2018，45（4）： 137-142.）