霧計算平臺的任務(wù)調(diào)度算法研究

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

0 引言

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

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

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

1 霧計算概述

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

圖1 霧計算平臺整體結(jié)構(gòu)

如圖1所示，霧計算利用霧集群中的邊緣閑散計算資源，為終端用戶提供計算服務(wù)。無集群的整體結(jié)構(gòu)設(shè)計如圖2所示。

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

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

2 霧計算任務(wù)調(diào)度模型

2.1 任務(wù)調(diào)度流程

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

圖3 任務(wù)調(diào)度過程

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

默認的調(diào)度流程為以下兩個步驟：

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

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

2.2 任務(wù)調(diào)度數(shù)學(xué)模型

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

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

(1)

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

(2)

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

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

圖4 任務(wù)調(diào)度過程

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

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

(3)

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

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

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

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

(4)

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

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

(5)

而霧計算任務(wù)調(diào)度策略的目標(biāo)即為：最大調(diào)度長度SL的最小化。

3 霧計算任務(wù)調(diào)度算法設(shè)計與優(yōu)化

3.1 算法思路

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

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

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

vij=xij+φij(xik-xkj)

(6)

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

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

(7)

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

(8)

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

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

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

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

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

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

xk+1=τ(xk)

(9)

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

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

xn+1=asin(bxn)

(10)

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

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

Chk+1=sin(πChk)

(11)

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

xij=xminj+Chkj(xmaxj-xminj)

(12)

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

3.3 資源調(diào)度算法流程

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

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

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

(13)

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

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

(13)

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

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

圖5 基于改進人工蜂群的任務(wù)調(diào)度

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

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

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

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

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

4 基于改進人工蜂群的資源調(diào)度策略

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

圖6 基于改進算法的資源調(diào)度過程

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

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

算法： 改進人工蜂群的任務(wù)調(diào)度

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

輸出： 資源調(diào)度方案

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. 計算適應(yīng)度值

Step 10. end

Step 11. end

5 仿真實驗分析

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

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

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

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

6 結(jié)束語

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