劉鵬飛 毛鶯池 王龍寶

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

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

中圖分類號(hào)： TP393.027

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

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

1 相關(guān)工作

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

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

2 問題陳述

2.1 問題陳述

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

2.2 遺傳算法

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

SGA具有如下特點(diǎn)。

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

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

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

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

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

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

3.1 算法思路

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

3.2 云霧協(xié)作模型

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

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

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

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

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

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

1）移動(dòng)用戶提交任務(wù)請(qǐng)求到近端霧計(jì)算資源節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

3.4 任務(wù)分配算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交叉操作偽代碼如下。

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

變異操作偽代碼如下：

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

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

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

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

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

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

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

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

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

3.6 判斷策略

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

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

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

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

例如，對(duì)于變異后的染色體

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

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

4 實(shí)驗(yàn)及其結(jié)果分析

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

實(shí)驗(yàn)2 SLO違規(guī)率及服務(wù)提供商花費(fèi)對(duì)比實(shí)驗(yàn)。

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

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

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

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

2）霧端資源節(jié)點(diǎn)單位時(shí)間的費(fèi)用較低，該分配策略將本地化的任務(wù)請(qǐng)求分配到了近端霧資源節(jié)點(diǎn)。

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

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

5 結(jié)語

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

參考文獻(xiàn) （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)的霧計(jì)算架構(gòu)：中國(guó)，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] 韓奎奎，謝在鵬，呂鑫.一種基于改進(jìn)遺傳算法的霧計(jì)算任務(wù)調(diào)度策略[J].計(jì)算機(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.）