基于云霧協作模型的任務分配方法

劉鵬飛 毛鶯池 王龍寶

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

關鍵詞：云計算;霧計算;任務分配;任務調度;遺傳算法

中圖分類號： TP393.027

文獻標志碼：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 引言

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

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

1 相關工作

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

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

2 問題陳述

2.1 問題陳述

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

2.2 遺傳算法

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

SGA具有如下特點。

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

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

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

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

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

3 基于云霧協作模型的任務分配方法

3.1 算法思路

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

3.2 云霧協作模型

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

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

1）通過霧系統處理用戶本地請求可以降低服務延遲;

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

3.3 云霧協作模型下任務分配

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

1）移動用戶提交任務請求到近端霧計算資源節點。

2）霧計算資源節點提交任務請求相關參數到遠端云數據中心資源管理節點。

3）云數據中心資源管理節點根據任務請求相關參數以及分配策略判斷移動用戶的請求類型，若請求類型是本地化的查詢請求，則將任務請求分配到近端霧計算資源節點;否則分配到遠端云計算資源節點，最后找到最優任務請求分配結果。

4）云數據中心資源管理節點將最優任務請求分配結果反饋到霧端。

5）霧端根據最優分配結果將非本地的任務請求發送到云數據中心。

6）霧計算資源節點根據最優分配結果執行本地化的任務請求。

7）云計算資源節點根據最優分配結果執行非本地化的任務請求。

8）云數據中心將任務請求執行結果反饋到霧端。

9）霧系統匯總處理結果，響應移動用戶。

任務請求分配模型如圖4所示。

3.4 任務分配算法

基于云霧協作模型的任務分配算法包括以下9個部分，各部分的規則設計如下。

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

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

①不能將所有任務請求分配到同一個霧計算資源節點上，造成嚴重負載不均。

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

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

3）計算個體適應度值。在霧計算架構下移動用戶任務請求分配過程中，適應度函數是評價群體進化方向的關鍵，也是執行遺傳算法“優勝劣汰”的主要依據。這里以服務提供商的花費作為目標函數。

4）終止條件判斷。當進化代數達到規定迭代次數I時，輸出結果;否則轉到步驟5）。

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

①根據適應度函數公式計算出所有個體適應度值，累計求出適應度值總和。

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

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

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

④隨機產生一個（0，1）區間上的隨機數，根據該隨機數出現在上述哪個概率區來確定哪個個體被選中。

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

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

交叉操作偽代碼如下。

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

變異操作偽代碼如下：

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

9）更新迭代計數器。迭代計數器i=i+1，轉到步驟3）。

3.5 目標函數

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

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

其中：k表示因為服務超時而發生SLO違規的請求序號，tstopk表示第k個請求的實際響應時間，tdeadlinek表示第k個請求在SLO規定中的請求截止響應時間，q表示發生SLO違規的請求總個數，γk表示第k個發生SLO違規的請求基本懲罰，η表示因發生超時而導致的單位時間懲罰。

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

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

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

3.6 判斷策略

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

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

1）若請求類型是本地的霧端請求，則進一步判斷其對應的資源節點，如果對應的資源節點是霧端資源則不作處理，如果不是霧端資源，則將該資源節點突變為能夠使得當前霧端完成時間最短的霧資源節點。

2）若請求類型是非本地的云端請求，則進一步判斷其對應的資源節點：如果對應的資源節點是云端資源則不作處理;如果不是云端資源，則將該資源節點突變為能夠使得當前云端完成時間最短的云資源節點。

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

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

對于上面的染色體X，任務請求和資源節點的對應關系如表2所示，任務請求1分配到了云資源節點1上，任務請求2分配到了霧資源節點5上，任務請求3和6分配到了霧資源節點4上，任務請求4分配到了云資源節點3上，任務請求5分配到了云資源節點2上。顯然有些霧端的任務請求并沒有被分配到霧端資源節點上，所以對于沒有被分配到霧端的任務請求讓其對應的云端資源節點突變為能夠使得當前霧端完成時間最小的資源節點。對于沒有分配到云端的任務請求以同樣的方式處理。

4 實驗及其結果分析

4.1 實驗設置

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

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

4.2 實驗結果

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

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

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

實驗2 SLO違規率及服務提供商花費對比實驗。

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

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

從圖8可以看出，FOG-IGA在服務提供商花費方面整體上也低于CLOUD-IGA，主要原因有兩個：

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

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

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

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

5 結語

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

參考文獻 （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] 北京物聯遠信息技術有限公司.一種面向物聯網的霧計算架構：中國，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].計算機科學，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.）