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

楊裴裴,黃 燕,葉海智

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

1 引言

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

(4)

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

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

(5)

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

空間域拓撲結(jié)構如下圖1所示。

圖1 空間域拓撲結(jié)構

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

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

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

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

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

1)CPU

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

(6)

CPU需求量讀取公式如下:

(7)

2)節(jié)點選擇概率

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

(8)

信息素辨識公式如下:

(9)

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

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

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

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

V=tnj+tik*EUT

(10)

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

4 仿真與分析

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

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

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

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

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

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

(11)

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

表1 不同方法的負載平衡度

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

5 結(jié)束語

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