(浙江工業(yè)大學 信息工程學院，杭州 310023)

0 引言

霧計算是一個高度虛擬化的計算平臺，在傳統(tǒng)的云計算數(shù)據(jù)中心與終端設備間，提供計算、存儲和網(wǎng)絡服務，以提高物聯(lián)網(wǎng)計算性能。霧計算利用附件設備完成數(shù)據(jù)處理，而將數(shù)據(jù)上傳至“遙遠”的云端進行處理，可節(jié)約遠程傳輸帶寬，降低計算延時，緩解云端計算壓力。同時，霧計算技術的位置感知能力更強，延遲更低，適用于多節(jié)點部署，因此在車聯(lián)網(wǎng)等物聯(lián)網(wǎng)和交通指揮系統(tǒng)等互聯(lián)網(wǎng)系統(tǒng)中廣泛應用[1]。

云計算模式中的資源高度集中，導致數(shù)據(jù)中心遠離用戶端，容易造成傳輸擁塞與傳輸延遲。而霧計算通過將云計算的部分功能轉移到網(wǎng)絡邊緣，在更靠近終端的地方，為用戶提供實時交互、移動性支持和外置感知等服務，減少了系統(tǒng)內部數(shù)據(jù)流量，提高終端的響應能力。但是，由于不同終端、不同任務的資源需求不同，需要霧計算有適當?shù)娜蝿照{度策略對海量的霧計算節(jié)點資源進行分配與調度。因此，構建合理的資源管理、任務調度體系，可進一步提高霧計算服務質量，在信息技術領域具有重要的理論意義以及現(xiàn)實應用價值。

當前，這對霧計算特點的任務調度算法研究較少。汪成亮利用Rete算法構造推理網(wǎng)絡，將推理節(jié)點優(yōu)化分配至各計算節(jié)點，提高了節(jié)點的資源利用率[2]。湯琳煜基于穩(wěn)定匹配的思想，解決任務與服務設備的分配問題[3]。韓奎奎提出一種改進的遺傳算法，進行任務調度與分配[4]。熊凱采用強化學習算法有效提高異構車聯(lián)霧架構下的資源優(yōu)化[1]。從霧計算任務調度的研究現(xiàn)狀來看，其研究較少，缺少一種較廣泛應用的霧計算任務調度算法。為此，本文提出一種基于改進蜂群算法，為霧計算的任務調度提供一種新的思路[5]。

1 霧計算概述

霧計算是由Cisco公司所提出的一種分布式計算結構，自2011年被提出以來，這種技術被廣泛地應用于智能服務機器人、智能家居、智能電網(wǎng)、智能交通等領域。霧計算的整體架構如圖1所示。

圖1 霧計算平臺整體結構

如圖1所示，霧計算利用霧集群中的邊緣閑散計算資源，為終端用戶提供計算服務。無集群的整體結構設計如圖2所示。

其中，霧中心節(jié)點負責整個霧集群節(jié)點的任務內編排與控制，霧服務節(jié)點負責提供Docker容器和霧計算能力，霧網(wǎng)絡節(jié)點負責網(wǎng)絡拓撲發(fā)現(xiàn)與數(shù)據(jù)轉發(fā)。霧服務節(jié)點均基于Docker引擎，運行不同數(shù)量的容器，而這些容器構成了容器集群，提供霧計算服務。

霧計算體系內的調度問題，其實質為任務請求過程中的重疊問題。在霧計算為用戶請求任務分配計算資源時，每個任務的處理必然會持續(xù)一段時間，而任務請求時間及其后的持續(xù)時間段，會導致任務處理時間重疊。而霧計算任務的角度的目的為：對于處理時間上有重疊的任務集合，制定合理的資源、任務調度方案，以保證所有任務處理的總體時間最短。

2 霧計算任務調度模型

2.1 任務調度流程

霧計算任務調度過程如圖3所示，由霧中心節(jié)點在調度任務與計算資源的約束下，通過調度算法，選擇合適的霧服務節(jié)點，在霧服務節(jié)點的Pod容器內進行任務計算。

圖3 任務調度過程

調度服務不斷向霧中心節(jié)點查詢待調度的Pod列表，以及當前霧節(jié)點集群中的可用霧服務節(jié)點Node列表，根據(jù)調度策略，優(yōu)選霧服務節(jié)點資源進行任務處理[6]。

默認的調度流程為以下兩個步驟：

1)根據(jù)霧中心節(jié)點與霧服務節(jié)點的通信，了解霧服務節(jié)點的可用狀態(tài)，構建可用服務節(jié)點Node列表；

2)按照改進人工蜂群算法對可用的霧服務節(jié)點進行評價，選擇最合適的霧服務節(jié)點，完成霧服務節(jié)點的調度。

2.2 任務調度數(shù)學模型

霧計算任務調度模型的描述可使用五元組G=(V,P,E,W,C)來描述。

其中，V= {vi| 1≤i≤n}表示待處理的任務集合；P= {pi| 1≤i≤m}為可用的霧服務節(jié)點；E={eii| 1≤i≤n, 1≤j≤m}為DAG圖中的有向邊集合，表示任務vj是否需要任務vi的處理結果；W為式(1)所示的一個n×m的矩陣。

(1)

wij表示采用節(jié)點pj處理任務vi時的系統(tǒng)開銷。C為如式(2)所示的一個m×m的矩陣。

(2)

cij表示，若eij≠0時，vi完成后，到vj開始處理前的通信開銷。若vi和vj在同一個節(jié)點上完成，或eij=0時，cij=0。

綜上，霧計算的任務調度過程看作是如圖4所示的一個有向無環(huán)圖。

圖4 任務調度過程

在霧服務節(jié)點集合P={p1,p2,…,pi,…,pm}上，執(zhí)行任務集合V= {vi| 1≤i≤n}的過程，是一個在任務模型DAG圖上，具有時間有限約束的調度函數(shù)f，函數(shù)f以特定的開始時間，將任務映射到處理單元上，一個任務的調度可描述如式(3)所示：

f:T→{1,2,…,m}×[0, ∞)

(3)

若，有v∈T，且f(v)=(i,t)，表示任務v在時間t，被分配到霧服務節(jié)點pi上執(zhí)行。

任務調度函數(shù)f，可通過Gantt圖(甘特圖)來表示。在Gantt 中，存儲了一個處理單元表，對于每一個處理單元，每個任務都有處理單元與之相對，可直觀地表示任務的開始時間與結束時間，按照分配到該霧服務節(jié)點上的所有任務，按照先后執(zhí)行的順序進行排列。

Gantt圖可使用如式(4)所示的四元表來表示：

Gant(pi,vj,ST(vi,pi),FT(vj,pi))

(4)

其中:ST(vj,pi)表示在任務vj，在霧服務節(jié)點pi上的開始執(zhí)行時間，F(xiàn)T(vj,pi)表示在任務vj，在霧服務節(jié)點pi上的結束執(zhí)行時間。

在任務調度系統(tǒng)中，所有霧節(jié)點上的最大調度長度SL定義為：

(5)

而霧計算任務調度策略的目標即為：最大調度長度SL的最小化。

3 霧計算任務調度算法設計與優(yōu)化

3.1 算法思路

在以性能優(yōu)先的霧計算平臺中，其調度的目標就是在霧計算平臺的資源和待處理任務的約束下，使得如圖4所示的有向無環(huán)圖的遍歷時間最短。已有的研究成果表明，DAG圖的遍歷問題是一個NP-完全問題，在多項式時間復雜度內，無法找到問題精確解。對此本文將采用人工蜂群(artifical bee colony，ABC )算法，將任務分配給霧服務節(jié)點的過程，模擬為派遣蜜蜂前往蜜源采蜜的過程，以求解霧計算任務調度數(shù)學問題，在較短時間內，找到較優(yōu)的霧計算任務調度策略，以提高任務的調度和處理效率[7]。

ABC模擬蜂蜜的覓食采蜜機制，將覓食的蜂群劃分為偵查蜂、觀察蜂、雇傭蜂3個類型。雇傭蜂的數(shù)量與環(huán)境中食物點(蜜源)數(shù)量相同，雇傭蜂在環(huán)境區(qū)域內隨機搜索蜜源，存儲所找到的蜜源信息；雇傭蜂在完成區(qū)域搜索后，與觀察蜂分享區(qū)域內的蜜源地址信息；觀察蜂在蜂巢內，接收偵查蜂傳遞的信息，確定環(huán)境內蜜源。若蜜源長時間內沒有進化，則暫時放棄該蜜源，隨機搜索新的、更具價值的蜜源，以取代沒有進化的蜜源[8]。

ABC通過模擬蜂蜜的覓食采蜜機制，將覓食的蜂群劃分為偵查蜂、觀察蜂、雇傭蜂3個類型，其具體步驟如下所示。

1)初始化階段：初始化蜜源數(shù)量N，觀察蜂數(shù)量和雇傭蜂數(shù)量N，蜜源最大開采次數(shù)Limit，最大迭代次數(shù)Maxcycle。在初始階段，偵查蜂隨機搜索N個蜜源，采用N個D維向量表示搜索所得的N個蜜源，蜜源的產(chǎn)生公式如式(5)所示：

xij=xminj+α(xmaxj-xminj)

(5)

其中:xij表示蜜源i∈{1,2,…,N}的第j∈{1,2,…,D}個維度，α為(0,1)間的隨機數(shù)，xminj和xmaxj分別表示第j個維度空間內的最小值和最大值。

2)雇傭蜂階段：當雇傭蜂在區(qū)域內搜集到新的蜜源后，根據(jù)貪婪規(guī)則更新區(qū)域內的蜜源，若新蜜源的適應度，較原蜜源的適應度更高，則將新蜜源替代原有蜜源，其更新的公式如式(6)所示：

vij=xij+φij(xik-xkj)

(6)

其中:xij為原有的蜜源位置，vij為雇傭蜂所搜索到的新的蜜源位置，φij為一個[0,1]間的隨機數(shù)，xkj為不同于當前蜜源的另一蜜源，k≠i，且k∈[1,N]。

3)觀察蜂階段：偵查蜂發(fā)現(xiàn)新蜜源后，通過適應度函數(shù)計算蜜源的適應度值，以衡量蜜源的質量，蜜源適應度的計算公式如式(7)所示：

(7)

其中:fi為蜜源xi的適應度值觀察蜂通過雇傭蜂的所傳遞的信息，用于判斷新蜜源位置，與新蜜源質量。新蜜源質量越高，前往采蜜的觀察蜂越多，并采用輪盤賭概率，派遣前驅采蜜的觀察蜂，觀察蜂選擇新蜜源的概率公式如式(8)所示：

(8)

4)偵查蜂階段：在Limit次循環(huán)后，若蜜源仍未被更新，則選擇放棄該蜜源。 此時，雇傭蜂就會變?yōu)閭刹榉洌鼗貍刹榉潆A段，尋找新的蜜源。

最終，在尋找到適應度值滿足預設要求，或者當?shù)螖?shù)超出了預設的最大迭代次數(shù)后，將適應度值最高的蜜源作為算法結果，并退出人工蜂群算法的迭代。

3.2 人工蜂群算法改進與優(yōu)化

雖然ABC算法有較好的收斂性。但對初始值質量的要求較高，若初始方案的質量較低，將影響ABC算法的收斂精度與收斂速度等問題。但在霧計算的任務調度過程中，初始的任務分配方案是隨機的，可能影響ABC算法效果。

針對該問題，本文主要通過在初始階段引入正弦映射，以提高初始值質量，和在迭代過程中，引入混沌思想，以提高搜索范圍的方式，進行ABC算法的優(yōu)化[9]。

混沌具有非線性動力系統(tǒng)的固有特性，混沌空間中的變化過程看似是雜亂無章，但在這個看似雜亂無章的混亂過程中，又體現(xiàn)了精致的內在規(guī)律性，其數(shù)學描述如下所示：

xk+1=τ(xk)

(9)

其中:k=0,1,2,…，τ為一個非線性的映射，0

如式(10)所示的正弦非線性映射，通過正弦變化，可得到所需的混沌序列。

xn+1=asin(bxn)

(10)

其中:a和b為正弦非線性映射模型的相關參數(shù)。

在人工蜂群算法的初始化階段，采用正弦非線性映射，引入到人工蜂群的初始化過程?；谡易兓娜斯し淙旱姆N群變量初始化如式(11)所示：

Chk+1=sin(πChk)

(11)

其中:k為迭代計數(shù)器，k=0,1,2,…,m，m為最大混沌迭代次數(shù)，Chk∈(0,1)。將式(11)引入到人工蜂群的初始化過程，采用混沌變量后的種群變量轉換公式如式(12)所示：

xij=xminj+Chkj(xmaxj-xminj)

(12)

其中:xminj和xmaxj分別表示第j個維度空間內的最小值和最大值。

3.3 資源調度算法流程

基于改進人工蜂群算法，快速實現(xiàn)任務與霧計算資源間的匹配，實現(xiàn)霧計算任務的快速調度。為了讓改進人工蜂群算法適用于霧計算資源的調度分配，還需要算法中的解和適應度函數(shù)進行重構[10]。

1)解的重新構造：假設霧計算層的可用霧服務節(jié)點數(shù)為m，待任務數(shù)為n。任務調度的目的就是將n個計算任務分配到m個霧服務節(jié)點上進行處理。因此，蜂群解描述如式(13)所示：

Xi=(xi1,xi2,…,xin),i=1,2,…,m

(13)

例如，將任務(t0,t1,t2,t3)分配到霧計算虛擬資源(p0,p1)上，最終的解表述為X0=(1,0,0,1)，X1=(0,1,1,0)，即將任務t0和t3分配到霧服務節(jié)點p0上進行處理，在霧服務節(jié)點p1上計算資源v1上計算任務t1和t2。

2)適應度函數(shù)的計算：對蜜源質量進行評價的適應度函數(shù)設計如式(13)所示：

(13)

即完成所有任務的時間越短，該調度策略的適應度函數(shù)值越大，以確保找到最優(yōu)的任務調度策略[11]。

基于改進蜂群算法的霧計算資源優(yōu)化調度策略流程如圖5所示。

圖5 基于改進人工蜂群的任務調度

1)蜂群規(guī)模初始化，采用混沌映射初始化人工蜂群的種群，產(chǎn)生初始解，根據(jù)將n個計算任務分配到m個虛擬霧服務中心上，構成人工蜂群算法的初始解，并設置人工蜂群算法的最大迭代次數(shù)Maxcycle等初始化參數(shù)。

2)雇傭蜂按照貪婪規(guī)則，搜尋區(qū)域內的新蜜源位置，基于適應度函數(shù)計算新蜜源適應度，通過新蜜源適應度值與當前解適應度值的對比，選擇適應度更優(yōu)的蜜源位置，獲得更優(yōu)的霧計算資源分配方案。

3)在迭代過程中引入混沌思想，讓適應度函數(shù)越高的蜜源，能招募到更多的觀察蜂，通過新蜜源的不斷更新，保留條件最優(yōu)蜜源。

4)若某蜜源超過了預設臨界值Limit，則將觀察蜂轉換為偵查蜂，產(chǎn)生新的蜜源，替代被放棄的蜜源。

5)當人工蜂群的迭代次數(shù)超過了最大迭代次數(shù)Maxcycle時，算法結束，將適應度最高的蜜源，作為霧計算任務調度策略；否則繼續(xù)執(zhí)行第2)步。

4 基于改進人工蜂群的資源調度策略

在基于改進人工蜂群算法的霧計算平臺任務調度過程如圖6所示。

圖6 基于改進算法的資源調度過程

霧計算平臺終端通過霧計算將服務提交到FMDC霧中心節(jié)點，設置資源監(jiān)控器，監(jiān)測當霧層的資源使用狀況，并將資源信息存儲到霧中心節(jié)點，將待處理任務進行集中管理，通改進人工蜂群的資源調度算法，制定任務調度策略，最終完成待處理任務的計算。

基于改進人工蜂群的任務調度過程具體實現(xiàn)如下所示：

算法： 改進人工蜂群的任務調度

輸入： 人工蜂群初始化參數(shù)(N, D, Maxcycle)

輸出： 資源調度方案

Step 1. 在初始化階段引入正弦映射

Step 2. fori=1:N

Step 3. forj=1:D

Step 4. ch(1,j) = rand

Step 5. fork= 1:cmax

Step 6. ch(k+1,j) = sin(pi×ch(k,j))

Step 7. end

Step 8.xij=xminj+chkj(xmaxj-xminj)

Step 9. 計算適應度值

Step 10. end

Step 11. end

5 仿真實驗分析

為證明本文所研究的改進人工蜂群算法在任務調度中的有效性，采用Matlab工具，對ABC人工蜂群算法和改進人工蜂群算法進行對比仿真實驗。

仿真實驗過程中相關參數(shù)設置如下：蜜源停留最大次數(shù)Limit=100，蜜源數(shù)目N=20，最大迭代次數(shù)Maxcycle=2 500，隨機生成100～700個不同的任務，對比分析不同任務數(shù)量下，兩種不同算法的任務完成時間。為確保算法實驗結果的精確性，對分別使用兩種算法分別獨立運行20次，取其平均值作為算法的執(zhí)行結果[12]。

在不同任務數(shù)量下，兩種不同算法的任務完成時間對比情況如圖7所示。

如圖7所示，當任務量較少時，兩種算法的優(yōu)化效果并未有明顯區(qū)別，根據(jù)不同調度算法完成所有任務的時間也相差不大，但是隨著任務數(shù)量的不斷增長，改進人工該算法完成所有任務的時間明顯更優(yōu)。究其原因，主要是因為隨著任務數(shù)量的增加，人工蜂群算法容易陷入局部最優(yōu)解，從而消耗較長時間也難以獲得全局最優(yōu)解，而在改進人工蜂群算法中，通過引入混沌策略，極大地提高了算法的全局尋優(yōu)能力，提高了任務調度效率，以優(yōu)化霧計算資源使用更優(yōu)，和提高霧計算平臺的任務處理效率與性能。

6 結束語

霧計算資源的任務調度策略是霧計算技術的研究重點之一，通過任務調度策略的優(yōu)化，有助于霧計算資源的應用優(yōu)化，進一步提升霧計算性能。本文所采用的改進人工蜂群算法，不僅能在多項式時間內找到較優(yōu)解，提高了任務調度性能，同時通過在初始階段引入混沌思想，提高了初始值質量，擴大了搜索范圍，提高了解的質量，優(yōu)化了任務調度策略，有利于霧計算性能的進一步提升。