面向云邊協(xié)同的資源調(diào)度優(yōu)化策略

趙宏偉, 荊學(xué)慧, 張 帥, 阮 瑩, 張子祺

(沈陽大學(xué) 信息工程學(xué)院, 遼寧 沈陽 110044)

隨著工業(yè)互聯(lián)網(wǎng)和5G的大規(guī)模商用,整個(gè)產(chǎn)業(yè)對(duì)云邊協(xié)同的深度融合充滿期待.伴隨5G技術(shù)的推廣應(yīng)用,已有的CDN架構(gòu)已不能滿足5G技術(shù)的發(fā)展需求[1].目前CDN已結(jié)合邊緣計(jì)算,主要應(yīng)用于本地化且熱點(diǎn)內(nèi)容頻繁請(qǐng)求的應(yīng)用場(chǎng)景.并將虛擬內(nèi)容分發(fā)網(wǎng)絡(luò)(vCDN)部署于運(yùn)營(yíng)商區(qū)域的邊緣數(shù)據(jù)中心,解決傳統(tǒng)架構(gòu)所具有的網(wǎng)絡(luò)壓力大等問題.在日常生活中我們也離不開云邊協(xié)同架構(gòu),如與我們生活息息相關(guān)的智慧交通和智慧家居.

傳統(tǒng)云計(jì)算模式的數(shù)據(jù)傳輸過程,需要將用戶待處理的大量數(shù)據(jù)匯聚于云數(shù)據(jù)中心,這種方式不但時(shí)延較長(zhǎng),浪費(fèi)現(xiàn)有資源,而且對(duì)跨域鏈路帶寬造成極大的負(fù)擔(dān).國(guó)內(nèi)外學(xué)者對(duì)此也提出不同的改進(jìn)辦法,主要從解決負(fù)載均衡問題、任務(wù)卸載和排隊(duì)處理等幾方面著手研究.文獻(xiàn)[2]提出以跨域作業(yè)平均完成時(shí)間最小化為優(yōu)化目標(biāo)的在線調(diào)度算法,該算法解決數(shù)據(jù)熱點(diǎn)積壓,邊緣節(jié)點(diǎn)數(shù)據(jù)負(fù)載不均的問題,在降低整體任務(wù)平均完成時(shí)間的同時(shí),也能有效降低當(dāng)前任務(wù)完成時(shí)間.文獻(xiàn)[3]提出一種集中控制的資源調(diào)度方法,選擇合適少量的邊緣計(jì)算節(jié)點(diǎn),在已選擇的節(jié)點(diǎn)間,采取降低端到端的時(shí)間延遲.文獻(xiàn)[4]提出一種基于蜜蜂角色轉(zhuǎn)換、蜜源的選擇和改變隨機(jī)數(shù)3方面優(yōu)化人工蜂群算法,以滿足多維QoS任務(wù)資源調(diào)度任務(wù),從多方面考慮蜂群算法中解的適應(yīng)度.減緩求解的搜索速度,擴(kuò)大解的搜索范圍,避免陷入局部最優(yōu)解,能有效地提升用戶滿意度.文獻(xiàn)[5]針對(duì)單目標(biāo)的虛擬資源調(diào)度問題,提出多目標(biāo)離散問題,在原有的智能算法基礎(chǔ)上加以改進(jìn),提出離散型人工蜂群算法.滿足單目標(biāo)的同時(shí),從用戶和服務(wù)商2方面考慮保證多性能的最優(yōu)化.目前智能算法在處理邊緣和云協(xié)同的資源調(diào)度問題上已經(jīng)取得一定的成果.但數(shù)據(jù)發(fā)展多樣化對(duì)云和邊緣上資源調(diào)度問題提出更高的要求,在提高效率的同時(shí),需要盡可能滿足多目標(biāo)任務(wù).

圖1 云邊協(xié)同的網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Cloud and edge collaboration network structure

本文針對(duì)上述大環(huán)境的要求,結(jié)合文獻(xiàn)[6]中提出的條件,從經(jīng)濟(jì)花費(fèi)、完成時(shí)間和負(fù)載均衡3方面建立云和邊緣上的適應(yīng)度計(jì)算函數(shù).提出一種改進(jìn)搜索策略的人工蜂群算法,并結(jié)合差分思想,使算法搜索方向和搜索步長(zhǎng)隨著迭代次數(shù)的增加進(jìn)行相應(yīng)的調(diào)整,加快搜索速率,跳出局部最優(yōu)解的同時(shí)確保解的準(zhǔn)確性和穩(wěn)定性.

云邊協(xié)同的結(jié)構(gòu)如圖1所示,主要分為云計(jì)算中心層、終端層和邊緣服務(wù)器層[7].各層次間相互聯(lián)系,相互協(xié)同通信.

1 改進(jìn)的人工蜂群算法

智能群體算法在云計(jì)算技術(shù)中起著至關(guān)重要的作用,在資源調(diào)度上也取得較好的成果,確保云邊結(jié)合能夠帶給用戶高效快捷的服務(wù).對(duì)此本文提出一種優(yōu)化的人工蜂群算法,主要是針對(duì)搜索策略等加以改進(jìn).

1.1 人工蜂群算法

人工蜂群算法(ABC)是模仿蜜蜂行為提出的一種優(yōu)化算法[8],由蜜源和人工蜜蜂2種要素構(gòu)成,人工蜜蜂又分為偵查蜂、跟隨蜂和引領(lǐng)蜂3種.蜜源相當(dāng)于優(yōu)化問題的可行解.引領(lǐng)蜂負(fù)責(zé)在隨機(jī)蜜源周圍進(jìn)行搜索找到合適的蜜源,并把搜索到的蜜源信息以一定概率分享給其他蜜蜂.跟隨蜂根據(jù)引領(lǐng)蜂發(fā)送回的信息,按一定概率進(jìn)行跟隨,進(jìn)一步挖掘.如果蜜源經(jīng)過若干周期仍沒有改進(jìn),偵查蜂則隨機(jī)搜索新的蜜源.具體步驟如下[9].

解的初始化.搜索空間內(nèi)隨機(jī)分布產(chǎn)生NP個(gè)初始蜜源(x1,x2,…,xNP),對(duì)應(yīng)空間解.每個(gè)蜜源xi都是一個(gè)D維的向量,其中D是解的維度.由式(1)隨機(jī)產(chǎn)生可行解xij,其中i∈{1,2,…,NP},j∈{1,2,…,D}.

xij=xmin j+rand[0,1](xmax j-xmin j).

(1)

式中:xmin j表示解在j維度下的下邊界;xmax j表示解在j維度下的上邊界.

引領(lǐng)蜂階段.根據(jù)式(2)在現(xiàn)有蜜源的基礎(chǔ)上搜索新蜜源,即新解vij.

vij=xij+φ(xij-xkj).

(2)

式中,φ∈[-1,1]的隨機(jī)數(shù),k是{1,2,…,NP}中隨機(jī)選取的參數(shù),且k≠i.分別計(jì)算適應(yīng)度值,根據(jù)貪婪算法,選擇較大進(jìn)行保留.

跟隨蜂階段.跟隨蜂采用輪盤賭的方法選擇引領(lǐng)蜂,見式(3),選擇概率pi大的跟隨.其中fiti的計(jì)算見式(4).

式中,fiti為xi的適應(yīng)度,fi表示解的函數(shù)值.再根據(jù)式(2)在所選擇解的周圍搜索并計(jì)算適應(yīng)度值,采用貪婪算法選擇較好解.

偵察蜂階段.經(jīng)過tr次迭代后解仍沒有變化,且已超過開采次數(shù)L,則放棄該蜜源,選取新解.

1.2 差分人工蜂群算法

當(dāng)偵查蜂和跟隨蜂采取局部搜索時(shí),基于人工蜂群算法的局部搜索策略,隨機(jī)選取2個(gè)蜜源在j維上做差值,作為更新部分.這導(dǎo)致步長(zhǎng)是隨機(jī)選取,沒有方向性,浪費(fèi)不必要的時(shí)間.針對(duì)這一問題引入最優(yōu)解xbest的概念,利用已知的最優(yōu)解提供參考,加快搜索效率.φ表示對(duì)步長(zhǎng)的擾動(dòng)程度,決定搜索區(qū)域的范圍,對(duì)此提出結(jié)合差分思想的改進(jìn)人工蜂群算法[10].改進(jìn)后的方法可以在避免陷入局部最優(yōu)解的同時(shí),提高搜索效率,從而提高算法的開發(fā)能力.這種變異策略以一定的概率變換搜索方程.

vij=xij+2(φ-0.5)(xij-xkj)+φ(xbest,j-xij),φ∈[0,1].

(5)

式(5)中,式(2)更新的蜜源變?yōu)樾碌膙ij,2個(gè)蜜源的步長(zhǎng)系數(shù)由原來的φ變?yōu)?(φ-0.5),在原有基礎(chǔ)上增加搜索密度,對(duì)解的范圍加以精分,大大增加解的可能性,克服原人工蜂群算法的局限性.同時(shí)利用精英因子的學(xué)習(xí)功能,兼顧搜索速率.式(5)的第3項(xiàng)易使當(dāng)前解偏向原有最優(yōu)解,所以給予較小傾斜,當(dāng)系數(shù)取0時(shí),式(5)更接近式(2).

在式(5)的基礎(chǔ)上提出改變?chǔ)盏南禂?shù)得到式(6),這樣即使在解的密度較大情況下,也能及時(shí)跳出局部最優(yōu)的限制,增加步長(zhǎng),避免陷入局部最優(yōu)解.對(duì)于后期的搜索也可以避免已知最優(yōu)解的影響,增加隨機(jī)性,從方向和步長(zhǎng)2方面尋求新解,加快搜索效率.a、b分別為第2項(xiàng)和第3項(xiàng)的系數(shù)因子[11].K表示人工蜂群算法迭代次數(shù).

vij=xij+2a(φ-0.5)(xij-xkj)+bφ(xbest.j-xij),φ∈[0,1].

(6)

DABC算法描述給出了改進(jìn)后的人工蜂群算法具體執(zhí)行過程.變系數(shù)人工蜂群算法,是通過結(jié)合差分的思想以及添加變系數(shù)因子在原始人工蜂群算法上加以改進(jìn).算法中種植條件由3個(gè)評(píng)價(jià)指標(biāo)負(fù)載均衡度、經(jīng)濟(jì)花費(fèi)和消耗時(shí)間的閾值所決定,當(dāng)?shù)芷跀?shù)達(dá)到最大迭代周期數(shù)時(shí),記入當(dāng)前的最優(yōu)解.改進(jìn)算法中根據(jù)式(6)更新蜜源,其中a、b主要決定搜索效率,加快搜索最優(yōu)解的時(shí)間.

算法偽代碼如下.

1) 輸入:最大迭代周期數(shù)L,初始蜂群規(guī)模Cn,蜜源NP,函數(shù)維數(shù)D;2) 初始化食物源位置xij,其中i∈{1,2,…,NP},j∈{1,2,…,D},評(píng)估蜜源質(zhì)量(即解的適應(yīng)度值fiti).3) While(l≤L) do4) 引領(lǐng)蜂階段 每個(gè)引領(lǐng)蜂選取相應(yīng)蜜源; 根據(jù)式(6)產(chǎn)生一個(gè)新的蜜源vij; 計(jì)算該位置適應(yīng)度值fiti,應(yīng)用貪婪選擇機(jī)制進(jìn)行選擇;5) 根據(jù)式(3)計(jì)算每個(gè)蜜源被選擇的概率pi;6) 跟隨蜂階段 每個(gè)跟隨蜂采用輪盤賭選取引領(lǐng)蜂進(jìn)行跟隨; 根據(jù)概率pi選擇一個(gè)蜜源; 根據(jù)式(6)在該蜜源周圍搜索產(chǎn)生新蜜源vij; 計(jì)算新蜜源適應(yīng)度值fiti,應(yīng)用貪婪選擇機(jī)制進(jìn)行選擇;7) 偵察蜂階段 判斷是否有放棄的解; 如果有,引領(lǐng)蜂變成偵察蜂; 根據(jù)式(1)在解空間隨機(jī)產(chǎn)生新蜜源; 如果沒有,結(jié)束搜索;8) 記住迄今為止發(fā)現(xiàn)的最優(yōu)解9) l=l+1.10)End while11)輸出:最優(yōu)解.

2 云邊協(xié)同資源調(diào)度

2.1 云邊協(xié)同系統(tǒng)調(diào)度框架

云邊協(xié)同調(diào)度框架如圖2所示,用戶設(shè)備發(fā)送任務(wù)到達(dá)服務(wù)器,由服務(wù)器將任務(wù)抽象成n個(gè)子任務(wù),分別送于不同的邊緣集群進(jìn)行計(jì)算.由于邊緣集群計(jì)算能力有限,對(duì)于較大任務(wù)調(diào)度到云計(jì)算中心處理,再由云計(jì)算中心將數(shù)據(jù)層層反饋至用戶設(shè)備端.

圖2 云邊協(xié)同調(diào)度框架Fig.2 Cloud edge collaborative scheduling framework

2.2 云邊協(xié)同調(diào)度模型

邊緣和云協(xié)同系統(tǒng)中包含一個(gè)計(jì)算能力強(qiáng)大的云計(jì)算中心,和跨域部署于各地區(qū)的邊緣集群構(gòu)成.各集群的計(jì)算能力用計(jì)算單元s的數(shù)量來描述,各計(jì)算單元的處理能力均相同.邊緣集群以Si表示,云計(jì)算中心以Sv表示.各集群包含不同的計(jì)算熱點(diǎn),熱點(diǎn)所含有的計(jì)算單元數(shù)目不同則計(jì)算能力不同,云計(jì)算中心視為計(jì)算單元充足.將任務(wù)T采用一定算法分配到各集群上,同時(shí)滿足各項(xiàng)評(píng)價(jià)指標(biāo),這里給出負(fù)載ws、經(jīng)濟(jì)花費(fèi)c和消耗時(shí)間t三個(gè)指標(biāo).

任務(wù)T分解為n維的抽象子任務(wù)T={T1,T2,…Tn},每一個(gè)子任務(wù)Ti分配到一個(gè)計(jì)算集群(Si)處理.每個(gè)計(jì)算集群中包含m個(gè)計(jì)算能力不同的計(jì)算熱點(diǎn)Si={Si1,Si2,…,Sim}.本文引入3個(gè)消極的評(píng)價(jià)指標(biāo),即表現(xiàn)為數(shù)值越小越好的評(píng)價(jià)指標(biāo),以P表示集群屬性.則每一個(gè)計(jì)算集群熱點(diǎn)屬性可以表示為P(Sim)={pw s,pc,pt},由此每一個(gè)計(jì)算集群屬性記為P(Si)={Pw s,Pc,Pt}.m表示每個(gè)計(jì)算集群的熱點(diǎn)總數(shù),n表示需要計(jì)算的抽象任務(wù)數(shù)[12].綜上計(jì)算集群則需要滿足以下條件:

(7)

在數(shù)據(jù)處理上優(yōu)先考慮將數(shù)據(jù)上傳至邊緣端,各抽象任務(wù)部署于邊緣集群的屬性集合式(7)上,則應(yīng)滿足少于調(diào)度至云端的負(fù)載均衡度、經(jīng)濟(jì)花費(fèi)和消耗時(shí)間.即滿足條件如下:

(8)

云計(jì)算中心計(jì)算功能強(qiáng)大,計(jì)算單元數(shù)充足. 當(dāng)把抽象任務(wù)集中于云端時(shí), 任務(wù)可以全部計(jì)算, 但計(jì)算單元應(yīng)用達(dá)到最多, 消耗資源最多, 負(fù)載、經(jīng)濟(jì)花費(fèi)和時(shí)間消耗都較大, 不適宜選取. 當(dāng)把待處理任務(wù)集中于某一邊緣計(jì)算集群時(shí), 集群可能因計(jì)算單元不足而無法完成計(jì)算任務(wù). 對(duì)此提出用解本身最小值來彌補(bǔ), 用當(dāng)前解值和最小解做差值, 消除最理想狀態(tài). 所以選取式(9)計(jì)算解的適應(yīng)度函數(shù),消除影響.

(9)

式中:Pi表示計(jì)算集群?jiǎn)蝹€(gè)屬性;Pimin表示單個(gè)屬性的最小值.

2.3 基于DABC的云邊協(xié)同資源調(diào)度

基于改進(jìn)人工蜂群算法DABC的云邊協(xié)同資源調(diào)度策略,將云邊協(xié)同資源調(diào)度的3個(gè)評(píng)價(jià)屬性負(fù)載均衡度、經(jīng)濟(jì)花費(fèi)和完成時(shí)間的最優(yōu)值選取問題轉(zhuǎn)化為人工蜂群算法對(duì)Pw s、Pc和Pt的尋優(yōu)問題.并選取云邊協(xié)同調(diào)度模型作為適應(yīng)度函數(shù),最大迭代周期數(shù)L的選取依賴于云邊協(xié)同仿真模擬器的處理能力和實(shí)際任務(wù)數(shù).蜂群整體規(guī)模的選取依據(jù)為云邊協(xié)同資源調(diào)度系統(tǒng)所需要處理的任務(wù)T.以下是云邊協(xié)同資源調(diào)度的具體流程:

步驟1 設(shè)置3個(gè)評(píng)價(jià)指標(biāo)負(fù)載Pw s、經(jīng)濟(jì)花費(fèi)Pc、消耗時(shí)間Pt,最大迭代周期數(shù)L;

步驟2 根據(jù)需要處理的任務(wù)數(shù)T,隨機(jī)產(chǎn)生初始種群,蜂群規(guī)模為Cn;

步驟3 引領(lǐng)蜂初始化蜜源位置,根據(jù)式(9)評(píng)估屬性適應(yīng)度fiti;

步驟4 根據(jù)式(6)的計(jì)算方法(這里xij和vij均為資源調(diào)度策略中的任務(wù)屬性解,以Pi表示)產(chǎn)生任務(wù)屬性Pi的解,并計(jì)算該位置適應(yīng)度值;

步驟5 根據(jù)式(3)計(jì)算解的選擇概率pi,跟隨蜂采用貪心算法進(jìn)行跟隨;

步驟6 跟隨蜂根據(jù)式(6)的計(jì)算方法在已求得單個(gè)屬性Pi的解周圍產(chǎn)生任務(wù)屬性的新解Pi;

步驟7 計(jì)算新求得任務(wù)屬性解的適應(yīng)度,采用貪婪機(jī)制選擇;

步驟8 判斷是否有被拋棄任務(wù)屬性Pi的解,如果有,引領(lǐng)蜂轉(zhuǎn)化為偵察蜂,偵察蜂根據(jù)式(1)進(jìn)行計(jì)算,隨機(jī)搜索新屬性的較好解;

步驟9 記入當(dāng)前任務(wù)屬性得到最優(yōu)值;

步驟10 判斷是否滿足終止條件,預(yù)設(shè)的仿真模擬器最大迭代周期數(shù);

步驟11 滿足則輸出最優(yōu)的資源調(diào)度方案,若不滿足則轉(zhuǎn)為步驟4.

3 云邊協(xié)同資源調(diào)度模擬仿真

本文實(shí)驗(yàn)在CloudSim仿真器上結(jié)合多臺(tái)虛擬機(jī)進(jìn)行模擬. 選取一個(gè)云數(shù)據(jù)中心,600個(gè)邊緣集群, 各邊緣集群所含熱點(diǎn)數(shù)隨機(jī). 任務(wù)數(shù)由100～500遞增. 為評(píng)價(jià)多目標(biāo)情況下云邊協(xié)同調(diào)度模型及改進(jìn)算法, 本文通過多次改變經(jīng)濟(jì)花費(fèi)、負(fù)載均衡度和完成時(shí)間3個(gè)函數(shù)的權(quán)值的大小, 得出算法改進(jìn)有效的結(jié)論, 同時(shí)也驗(yàn)證了算法的普適性和穩(wěn)定性. 本文選取人工蜂群算法(ABC)、改進(jìn)的人工蜂群算法DABC和PSO算法進(jìn)行比較, 通過改變?nèi)蝿?wù)數(shù)來衡量對(duì)經(jīng)濟(jì)花費(fèi), 完成時(shí)間和負(fù)載均衡度造成的影響.

通過圖3可以得出改進(jìn)算法有效降低成本,改進(jìn)算法中隨著任務(wù)數(shù)的增加,經(jīng)濟(jì)花費(fèi)增長(zhǎng)逐漸變緩,說明更多的任務(wù)選擇部署在邊緣端,就近選擇本地服務(wù)器來調(diào)度數(shù)據(jù),減少不必要的資源浪費(fèi),降低調(diào)度成本.整體可以看出改進(jìn)算法有效降低成本,任務(wù)數(shù)越高,效果越明顯.

圖4看出人工蜂群算法對(duì)完成時(shí)間的影響較大,能有效的減少完成時(shí)間,提升算法效率.由于是多目標(biāo)問題,需要犧牲其他函數(shù),對(duì)經(jīng)濟(jì)花費(fèi)和負(fù)載均衡度的提升有一定影響.當(dāng)任務(wù)數(shù)增多時(shí),完成時(shí)間降低效果較好,隨著任務(wù)數(shù)的增長(zhǎng),后期完成時(shí)間增長(zhǎng)相對(duì)穩(wěn)定.

圖5顯示了負(fù)載均衡度隨任務(wù)數(shù)增長(zhǎng)的變化,利用空閑資源與帶寬進(jìn)行任務(wù)調(diào)度,分散整體任務(wù),將整體任務(wù)部署于多個(gè)邊緣集群和云計(jì)算中心,以達(dá)到負(fù)載均衡的目標(biāo).當(dāng)任務(wù)數(shù)較少時(shí),對(duì)PSO算法的負(fù)載均衡度影響較大.從整體圖像可以看出,相較于其他2種算法改進(jìn)的人工蜂群算法對(duì)負(fù)載均衡度有一定影響.ABC算法和DABC算法較為平穩(wěn),說明系數(shù)因子對(duì)負(fù)載均衡度影響較小.

圖4 完成時(shí)間隨任務(wù)數(shù)的變化

圖5 負(fù)載均衡度隨任務(wù)數(shù)的變化

4 結(jié) 論

本文針對(duì)跨域環(huán)境下的資源調(diào)度問題,提出了云邊協(xié)同的多目標(biāo)資源調(diào)度優(yōu)化策略.基于云和邊緣計(jì)算的各自特點(diǎn),搭建了云邊協(xié)同資源調(diào)度模型,其綜合考慮經(jīng)濟(jì)花費(fèi)、完成時(shí)間和負(fù)載均衡3個(gè)指標(biāo),同時(shí)提出一種基于差分思想的人工蜂群算法,用于優(yōu)化和求解所構(gòu)建的協(xié)同模型.最后,通過仿真實(shí)驗(yàn)驗(yàn)證,DABC蜂群算法性能較好,云邊協(xié)同模型能滿足云邊資源調(diào)度系統(tǒng)的多目標(biāo)要求,在降低成本和減少時(shí)間的同時(shí),提高了資源調(diào)度效率.DABC算法和模型對(duì)解決云邊協(xié)同的多目標(biāo)資源調(diào)度問題具有重要的意義.