啟發(fā)式規(guī)劃算法下云邊緣節(jié)點(diǎn)均衡調(diào)度仿真

楊裴裴,黃 燕,葉海智

(1. 鄭州工商學(xué)院信息工程學(xué)院,河南 鄭州 451400;2. 河南師范大學(xué),河南 新鄉(xiāng) 453007)

1 引言

隨著科學(xué)技術(shù)的快速發(fā)展,互聯(lián)網(wǎng)成為人類生活不可或缺的重要組成部分。作為由計(jì)算機(jī)技術(shù)和數(shù)字技術(shù)共同組建的高質(zhì)量網(wǎng)絡(luò)服務(wù)平臺(tái),互聯(lián)網(wǎng)在對(duì)現(xiàn)代社會(huì)造成重大影響的同時(shí),還被廣泛應(yīng)用于醫(yī)療衛(wèi)生、機(jī)械制造、航空航天等多個(gè)領(lǐng)域。物聯(lián)網(wǎng)計(jì)算又稱云計(jì)算[1],即通過處理和生成超大數(shù)據(jù)集,實(shí)現(xiàn)整體用戶資源共享。然而當(dāng)下社會(huì)信息化強(qiáng)度的不斷提升不僅加重了物聯(lián)網(wǎng)計(jì)算的負(fù)擔(dān),還降低了用戶資源利用率。為了將信息化時(shí)代下爆炸式增長(zhǎng)的數(shù)據(jù)按目標(biāo)需求彈性分配至各云邊緣節(jié)點(diǎn)并順利完成調(diào)度作業(yè),相關(guān)人員開展對(duì)云邊緣節(jié)點(diǎn)調(diào)度方法的研究。

林霄[2]等人通過將云計(jì)算平臺(tái)的海量數(shù)據(jù)納入SnF調(diào)度決策,促使布局散亂的離散化數(shù)據(jù)按決策需求排列成與所有網(wǎng)絡(luò)節(jié)點(diǎn)相對(duì)應(yīng)的跨數(shù)據(jù)中心網(wǎng)絡(luò)場(chǎng)景。通過量化分析場(chǎng)景內(nèi)計(jì)算復(fù)雜度較高的部分?jǐn)?shù)據(jù),并針對(duì)性提供實(shí)時(shí)調(diào)度服務(wù),實(shí)現(xiàn)云邊緣節(jié)點(diǎn)調(diào)度,該方法存在調(diào)度性能差的問題。沈?qū)W利[3]等人通過在異構(gòu)資源環(huán)境下按數(shù)據(jù)量和任務(wù)數(shù)量減少節(jié)點(diǎn)備份任務(wù),使集群節(jié)點(diǎn)在啟動(dòng)數(shù)量和作業(yè)完成時(shí)間兩方面得到全面優(yōu)化。通過將優(yōu)化集群節(jié)點(diǎn)與自適應(yīng)調(diào)度算法結(jié)合,獲取基于任務(wù)特征的調(diào)度因子,實(shí)現(xiàn)云邊緣節(jié)點(diǎn)調(diào)度。何貞貞[4]等人通過計(jì)算各任務(wù)間的數(shù)據(jù)流大小,確定節(jié)點(diǎn)可用資源與任務(wù)通信開銷間的關(guān)聯(lián)度,并參考關(guān)聯(lián)度拓?fù)溥厵?quán)重,繪制針對(duì)節(jié)點(diǎn)調(diào)度任務(wù)的有向無環(huán)圖,實(shí)現(xiàn)云邊緣節(jié)點(diǎn)調(diào)度,上述兩種方法存在負(fù)載平衡度低的問題。

為了解決上述方法中存在的問題,提出基于啟發(fā)式規(guī)劃算法的云邊緣節(jié)點(diǎn)調(diào)度方法。

2 云邊緣節(jié)點(diǎn)空間域建模

空間域建模是擴(kuò)大網(wǎng)絡(luò)生命周期、固定任意時(shí)間點(diǎn)網(wǎng)絡(luò)瞬時(shí)狀態(tài)的有力手段。因具備較為優(yōu)越的節(jié)點(diǎn)匯聚能力和路由規(guī)劃能力,空間域建模常作為設(shè)計(jì)方案被廣泛應(yīng)用于動(dòng)態(tài)網(wǎng)絡(luò)的靜態(tài)片段分析中。就云邊緣節(jié)點(diǎn)調(diào)度問題而言,如果單純以網(wǎng)絡(luò)結(jié)構(gòu)為調(diào)度背景,則極易由于通訊干擾、鏈路傳輸模式不當(dāng)和數(shù)據(jù)包丟失[5]等問題導(dǎo)致網(wǎng)絡(luò)中參與調(diào)度的節(jié)點(diǎn)個(gè)數(shù)與節(jié)點(diǎn)集群總數(shù)不一致。想要彌補(bǔ)以上缺陷,獲取觀測(cè)結(jié)果更為精確的多匯聚節(jié)點(diǎn)調(diào)度背景,需要在考慮容量原則、工作負(fù)載合并原則和流量平衡原則的基礎(chǔ)上,建立基于云邊緣節(jié)點(diǎn)的空間域。參與調(diào)度的節(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式如下:

(1)

式中,g表示數(shù)據(jù)鏈路的傳輸速率;n表示目標(biāo)狀態(tài)的后驗(yàn)分布;r表示節(jié)點(diǎn)遷移率;α表示期望最小累積損失;v2表示節(jié)點(diǎn)密度;β表示傳感器能量信號(hào)強(qiáng)度。

節(jié)點(diǎn)集群總數(shù)的計(jì)算公式如下:

(2)

式中,?i表示節(jié)點(diǎn)i的有效覆蓋面積;dk表示節(jié)點(diǎn)k的無效覆蓋面積;h表示傳感器能量信號(hào)衰減度;j表示網(wǎng)絡(luò)最大發(fā)射功率;δm表示網(wǎng)絡(luò)載波頻率;λ表示節(jié)點(diǎn)剩余能量。

由于時(shí)間具有連續(xù)性和不可逆性,因此單位時(shí)刻點(diǎn)在網(wǎng)絡(luò)中有且僅有一種表現(xiàn)形式,即源節(jié)點(diǎn)線性延伸形式。相較于云中心節(jié)點(diǎn),云邊緣節(jié)點(diǎn)的低編解碼復(fù)雜度[6]、通信半徑[7]和能耗標(biāo)準(zhǔn)更低,這表示任意位置上的云邊緣節(jié)點(diǎn)均不會(huì)每時(shí)每刻移動(dòng),且即便發(fā)生移動(dòng),其任意時(shí)間窗[8]的移動(dòng)幅度也會(huì)因觀測(cè)價(jià)值過低而忽略不計(jì)。這種類比靜態(tài)片段的動(dòng)態(tài)移動(dòng)過程促使云邊緣節(jié)點(diǎn)在度量動(dòng)作好壞和確定置信狀態(tài)兩方面存在不容忽視的誤差。節(jié)點(diǎn)動(dòng)作好壞的度量公式如下:

(3)

節(jié)點(diǎn)置信狀態(tài)的確定公式如下:

(4)

式中,b表示節(jié)點(diǎn)適應(yīng)度值;ε表示全局交叉變異率;In表示歷史觀測(cè)動(dòng)作;lnm表示目標(biāo)狀態(tài);c′表示鄰域節(jié)點(diǎn)之間的轉(zhuǎn)移概率;B表示節(jié)點(diǎn)集群的總體能量利用閾值。

空間域[9]顧名思義,指的是由自變量像元組成的三維空間。將散落在不同陣列的云邊緣節(jié)點(diǎn)視為自變量像元,根據(jù)調(diào)度需求和節(jié)點(diǎn)位置,按容量原則、工作負(fù)載合并原則和流量平衡原則將自變量像元映射至三維空間。容量原則、工作負(fù)載合并原則和流量平衡原則的表達(dá)式如下:

(5)

式中,u表示節(jié)點(diǎn)運(yùn)行效率評(píng)價(jià)因子;ai表示鄰域節(jié)點(diǎn)通信半徑;ai+1表示休眠節(jié)點(diǎn)占總節(jié)點(diǎn)的比例;ω表示負(fù)載合并處理耗時(shí);jm表示調(diào)度工作響應(yīng)需求;φ表示節(jié)點(diǎn)內(nèi)存的可用量;表示相互獨(dú)立的流量平衡空間。

空間域拓?fù)浣Y(jié)構(gòu)如下圖1所示。

圖1 空間域拓?fù)浣Y(jié)構(gòu)

經(jīng)過空間域建模的云邊緣節(jié)點(diǎn)成功彌補(bǔ)通訊干擾、鏈路不當(dāng)傳輸模式和數(shù)據(jù)包丟失所導(dǎo)致的傳感器穩(wěn)定性下降問題,并依靠自變量像元映射空間消除云邊緣節(jié)點(diǎn)在度量動(dòng)作好壞和確定置信狀態(tài)兩方面存在的誤差,為后續(xù)云邊緣節(jié)點(diǎn)調(diào)度奠定堅(jiān)實(shí)的基礎(chǔ)。

3 云邊緣節(jié)點(diǎn)調(diào)度

邊緣計(jì)算[10]作為熱門研究話題,始終活躍在不同應(yīng)用領(lǐng)域,尤其是計(jì)算機(jī)領(lǐng)域中?？紤]到云端協(xié)作給網(wǎng)絡(luò)用戶[11]帶來的低時(shí)延、高效率服務(wù),計(jì)算機(jī)領(lǐng)域相關(guān)學(xué)者將云端協(xié)作視為在有限資源中創(chuàng)造無限價(jià)值的技術(shù)。云邊緣節(jié)點(diǎn)調(diào)度隸屬于云端協(xié)作技術(shù)的一項(xiàng)分支,是實(shí)現(xiàn)數(shù)據(jù)傳輸最小化、應(yīng)用程序執(zhí)行性能最大化的重要環(huán)節(jié)。傳統(tǒng)的云邊緣節(jié)點(diǎn)調(diào)度方法由于存在默認(rèn)任務(wù)缺乏依賴性、任務(wù)執(zhí)行過程中間斷概率高等問題,無法發(fā)揮邊緣資源的最大化功效,因此提出基于啟發(fā)式規(guī)劃算法的云邊緣節(jié)點(diǎn)調(diào)度方法。

3.1 啟發(fā)式規(guī)劃算法

啟發(fā)式規(guī)劃算法是直觀展現(xiàn)待解決問題可行解[12]與最優(yōu)解偏離度,并根據(jù)經(jīng)驗(yàn)構(gòu)造給予待解決問題預(yù)計(jì)規(guī)劃的一種自然體算法。在節(jié)點(diǎn)調(diào)度等網(wǎng)絡(luò)規(guī)劃中,啟發(fā)式規(guī)劃算法主要用于評(píng)估目標(biāo)調(diào)度節(jié)點(diǎn)與目標(biāo)調(diào)度終點(diǎn)的最優(yōu)路徑,其評(píng)估過程較為復(fù)雜,需同時(shí)考慮不同調(diào)度任務(wù)對(duì)CPU[13]、節(jié)點(diǎn)選擇概率等因素的約束條件,因此在采用啟發(fā)式規(guī)劃算法調(diào)度云邊緣節(jié)點(diǎn)前,應(yīng)優(yōu)先以云邊緣節(jié)點(diǎn)空間域?yàn)榛A(chǔ),深入探討不同調(diào)度任務(wù)對(duì)CPU、節(jié)點(diǎn)選擇概率等因素的約束條件。

1)CPU

不同調(diào)度任務(wù)對(duì)CPU的約束條件可以理解為不同調(diào)度任務(wù)對(duì)于CPU的需求。以空間域中某一時(shí)刻一個(gè)云邊緣節(jié)點(diǎn)接收到的來自上層網(wǎng)絡(luò)的調(diào)度任務(wù)為例,想要在合理分配可用資源的前提下保留云邊緣節(jié)點(diǎn)CPU可用量,需要讀取這一次調(diào)度任務(wù)從起始時(shí)刻到終止時(shí)刻的全部CPU需求量。云邊緣節(jié)點(diǎn)CPU可用量的計(jì)算公式如下:

(6)

CPU需求量讀取公式如下:

(7)

2)節(jié)點(diǎn)選擇概率

云邊緣節(jié)點(diǎn)規(guī)模決定了調(diào)度任務(wù)搜尋目標(biāo)節(jié)點(diǎn)的難度,隨機(jī)數(shù)學(xué)[14]普遍認(rèn)為,傳統(tǒng)方法在執(zhí)行云邊緣節(jié)點(diǎn)調(diào)度任務(wù)時(shí),其目標(biāo)調(diào)度節(jié)點(diǎn)與目標(biāo)調(diào)度終點(diǎn)的核心選擇思路圍繞隨機(jī)分布理論[15]展開,這種不公平的選擇方法降低了目標(biāo)節(jié)點(diǎn)選擇概率。啟發(fā)式規(guī)劃算法選擇目標(biāo)節(jié)點(diǎn)依賴節(jié)點(diǎn)上分泌的信息素,即通過搜索符合目標(biāo)調(diào)度節(jié)點(diǎn)和目標(biāo)調(diào)度終點(diǎn)的信息素,實(shí)現(xiàn)節(jié)點(diǎn)選擇概率的大幅提升。隨機(jī)分布理論的表達(dá)式如下:

(8)

信息素辨識(shí)公式如下:

(9)

3.2 節(jié)點(diǎn)調(diào)度

在確定不同調(diào)度任務(wù)對(duì)CPU、節(jié)點(diǎn)選擇概率的約束條件的基礎(chǔ)上,正式采用啟發(fā)式規(guī)劃算法調(diào)度云邊緣節(jié)點(diǎn)。啟發(fā)式規(guī)劃算法框架如下圖2所示。

圖2 啟發(fā)式規(guī)劃算法框架

如上圖2可見,啟發(fā)式規(guī)劃算法根據(jù)不同調(diào)度任務(wù)對(duì)CPU、節(jié)點(diǎn)選擇概率等因素的約束條件選擇合適的底層算法,并部署符合該任務(wù)需求的路徑,通過反復(fù)優(yōu)化調(diào)度可行解,降低調(diào)度可行解與調(diào)度最優(yōu)解偏離度,實(shí)現(xiàn)云邊緣節(jié)點(diǎn)調(diào)度。啟發(fā)式規(guī)劃算法的表達(dá)式如下:

V=tnj+tik*EUT

(10)

式中,tnj表示可分配節(jié)點(diǎn)陣列;tik表示最優(yōu)路徑解;EUT表示最小復(fù)雜不均衡度。

4 仿真與分析

為了驗(yàn)證基于啟發(fā)式規(guī)劃算法的云邊緣節(jié)點(diǎn)調(diào)度仿真的整體有效性,采用MATLAB仿真軟件進(jìn)行測(cè)試。選擇數(shù)量不一的三組節(jié)點(diǎn)(10×107、10×108、10×109)作為驗(yàn)證算法調(diào)度性能的試驗(yàn)對(duì)象。

分別采用所提方法、文獻(xiàn)[2]方法和文獻(xiàn)[3]方法調(diào)度三組節(jié)點(diǎn),并對(duì)比不同方法選中節(jié)點(diǎn)、調(diào)度終點(diǎn)和調(diào)度軌跡與目標(biāo)節(jié)點(diǎn)、目標(biāo)終點(diǎn)和理想軌跡的重合度。不同方法的調(diào)度結(jié)果如下圖3所示。

圖3 不同方法的調(diào)度結(jié)果

如上圖3可見,所提方法在調(diào)度三組數(shù)量不一的云邊緣節(jié)點(diǎn)時(shí),選中節(jié)點(diǎn)、調(diào)度終點(diǎn)和調(diào)度軌跡均與目標(biāo)節(jié)點(diǎn)、目標(biāo)終點(diǎn)和理想軌跡高度重合,說明所提方法面對(duì)任何數(shù)量的云邊緣節(jié)點(diǎn),均能遵循調(diào)度策略完成目標(biāo)任務(wù),即所提方法的調(diào)度性能較強(qiáng)。因?yàn)樗岱椒ㄔ谡{(diào)度云邊緣節(jié)點(diǎn)前,優(yōu)先獲取不同調(diào)度任務(wù)對(duì)CPU、節(jié)點(diǎn)選擇概率等因素的約束條件。文獻(xiàn)[2]方法和文獻(xiàn)[3]方法在調(diào)度三組數(shù)量不一的云邊緣節(jié)點(diǎn)時(shí),雖存在選中節(jié)點(diǎn)或調(diào)度終點(diǎn)與目標(biāo)節(jié)點(diǎn)和目標(biāo)終點(diǎn)重合的現(xiàn)象,但總體來看,兩種方法幾乎與目標(biāo)任務(wù)完全背離,說明文獻(xiàn)[2]方法和文獻(xiàn)[3]方法面對(duì)任何數(shù)量的云邊緣節(jié)點(diǎn),均無法遵循調(diào)度策略完成目標(biāo)任務(wù),即文獻(xiàn)[2]方法和文獻(xiàn)[3]方法的調(diào)度性能較差。經(jīng)上述對(duì)比,可知所提方法的調(diào)度性能明顯優(yōu)于傳統(tǒng)方法。

負(fù)載平衡度是指算法將工作任務(wù)分配到多個(gè)操作單元(服務(wù)器)的能力。舉例來說,計(jì)算機(jī)云平臺(tái)僅有一個(gè)服務(wù)器,那么所有的節(jié)點(diǎn)調(diào)度任務(wù)均需要通過這一個(gè)服務(wù)器辦理。在節(jié)點(diǎn)數(shù)量較少的情況下,一個(gè)服務(wù)器尚能支撐云邊緣調(diào)度任務(wù),但當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí),為了將堆積在一個(gè)服務(wù)器的節(jié)點(diǎn)調(diào)度工作合理分配到其它服務(wù)器,需要降低單位服務(wù)器吞吐量,以達(dá)到加快任務(wù)執(zhí)行效率的目的。

因能從側(cè)面反映計(jì)算機(jī)集群、網(wǎng)絡(luò)連接和磁盤驅(qū)動(dòng)器對(duì)當(dāng)前資源的分配能力,負(fù)載平衡度常作為度量指標(biāo)判斷算法執(zhí)行性能。為了進(jìn)一步驗(yàn)證所提方法的實(shí)用性,分別采用所提方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法調(diào)度三組節(jié)點(diǎn),并計(jì)算不同方法的執(zhí)行時(shí)間和單位服務(wù)器吞吐量。執(zhí)行時(shí)間和單位服務(wù)器吞吐量計(jì)算公式如下:

(11)

不同方法的負(fù)載平衡度如下表1所示。

表1 不同方法的負(fù)載平衡度

如上表1可見,隨著節(jié)點(diǎn)數(shù)量的增加,所提方法執(zhí)行節(jié)點(diǎn)調(diào)度任務(wù)所消耗時(shí)間始終維持在較低水平,且單位服務(wù)器吞吐量較高,說明所提方法的負(fù)載平衡度較高,能夠?qū)⒐?jié)點(diǎn)調(diào)度任務(wù)合理分配到各服務(wù)器,在保證單位服務(wù)器高吞吐量、高執(zhí)行度的同時(shí),提升云邊緣節(jié)點(diǎn)調(diào)度效率。文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的執(zhí)行時(shí)間與所提方法存在較大差距,說明文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的負(fù)載平衡度較低,無法將節(jié)點(diǎn)調(diào)度任務(wù)合理分配到各服務(wù)器,從而促使云邊緣節(jié)點(diǎn)調(diào)度效率降低。經(jīng)上述對(duì)比,進(jìn)一步驗(yàn)證了所提方法的實(shí)用性。

5 結(jié)束語

近年來,人們對(duì)網(wǎng)絡(luò)計(jì)算需求越來越高,現(xiàn)有的計(jì)算架構(gòu)已無法滿足網(wǎng)絡(luò)用戶需求。為了降低網(wǎng)絡(luò)傳輸壓力,相關(guān)人員投入到云邊緣節(jié)點(diǎn)調(diào)度方法的研究之中。本文提出一種基于啟發(fā)式規(guī)劃算法的云邊緣節(jié)點(diǎn)調(diào)度方法,經(jīng)過仿真驗(yàn)證了該方法的調(diào)度效果。如何在保證云邊緣節(jié)點(diǎn)調(diào)度性能的同時(shí),對(duì)云邊緣節(jié)點(diǎn)調(diào)度過程實(shí)時(shí)監(jiān)控,是下一步工作的重點(diǎn)。