(浙江工業(yè)大學(xué) 信息工程學(xué)院,杭州 310023)
霧計算是一個高度虛擬化的計算平臺,在傳統(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]。
霧計算是由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ù)處理的總體時間最短。
霧計算任務(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)度。
霧計算任務(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的最小化。
在以性能優(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é)果,并退出人工蜂群算法的迭代。
雖然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)的最小值和最大值。 基于改進人工蜂群算法,快速實現(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)步。 在基于改進人工蜂群算法的霧計算平臺任務(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 為證明本文所研究的改進人工蜂群算法在任務(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ù)處理效率與性能。 霧計算資源的任務(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)度策略,有利于霧計算性能的進一步提升。3.3 資源調(diào)度算法流程
4 基于改進人工蜂群的資源調(diào)度策略
5 仿真實驗分析
6 結(jié)束語