啟發式規劃算法下云邊緣節點均衡調度仿真

楊裴裴,黃 燕,葉海智

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

1 引言

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

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

為了解決上述方法中存在的問題,提出基于啟發式規劃算法的云邊緣節點調度方法。

2 云邊緣節點空間域建模

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

(1)

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

節點集群總數的計算公式如下:

(2)

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

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

(3)

節點置信狀態的確定公式如下:

(4)

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

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

(5)

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

空間域拓撲結構如下圖1所示。

圖1 空間域拓撲結構

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

3 云邊緣節點調度

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

3.1 啟發式規劃算法

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

1)CPU

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

(6)

CPU需求量讀取公式如下:

(7)

2)節點選擇概率

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

(8)

信息素辨識公式如下:

(9)

3.2 節點調度

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

圖2 啟發式規劃算法框架

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

V=tnj+tik*EUT

(10)

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

4 仿真與分析

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

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

圖3 不同方法的調度結果

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

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

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

(11)

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

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

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

5 結束語

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