基于模式融合的網絡動態資源柔性調度仿真

姜 濤

(長春工業大學人文信息學院，吉林 長春 130122)

1 引言

移動網絡教學是一種新型的學習模式，有助于實現開放式教學目標，為教學的全面展開奠定了基礎[1]。由于網絡資源的有限性，導致不能滿足眾多教育網絡的需要，目前，移動網絡中動態教育資源的有效調度，是移動網絡面臨的主要難題之一。

文獻[2]提出基于蟻群算法的網絡動態資源柔性調度方法，通過建立調度模型，構建基于Qo S的多目標優化調度函數，利用蟻群算法進行求解，但該方法的網絡動態資源共享效果較差；文獻[3]提出基于max-min算法的網絡動態資源柔性調度方法，利用整數線性規劃建立虛擬鏈路的動態帶寬分配策略，在傳統調度模型的基礎上引入了數據流量在虛擬鏈路中的傳輸時延，并建立相應的5G網絡資源調度模型。采用max-min算法，獲得更好的調度方案，但該方法存在網絡動態資源分配不均的問題。文獻[4]提出基于遺傳算法的網絡動態資源柔性調度方法，將每個染色體視作獨立的智能體，采用工序編碼方式隨機初始化每個智能體，結合多智能體協作與競爭理論設計了實現智能體之間交互作用的鄰居交互算子，利用ASA對每個智能體開展局部尋優，引入遺傳算法，選擇動態調度與靜態分配的使用方式，實現網絡動態資源柔性調度，但該方法網絡動態資源利用率較小，應用效果不理想。

為此，提出基于模式融合的網絡動態資源柔性調度方法。明確移動中心網絡結構，獲取網絡結構中節點負載和資源占有率，并以此得出適配因子，利用max-min蟻群算法自動調度資源，實現移動網絡動態教育資源的均衡分配，提高資源利用率。

2 基于模式融合的網絡動態資源柔性調度方法

2.1 資源調度原理

1)假設a為移動中心網絡中節點數量，R為節點當前資源規模，則節點當前資源規模占據自身所能容納總資源的比重為

(1)

式中，p代表節點當前資源規模占據自身所能容納總資源的比重；n代表資源維度；b代表任務集合中互不相交的子集；x(k)代表節點的第k維資源量；d代表每個任務需要的資源。

2)假定e(i，j)為第i節點已經調度好的資源，則該資源與其它節點全部已經調度的資源量之間的比值f[e(i，j)]為

(2)

式中，g(i，j)代表節點待調度的資源；h代表資源均衡度；l代表資源負載度；mi代表第i個節點已經調度到資源量。

3)假定mi為第i節點已經調度到的資源，則各個節點的動態權值w為

(3)

式中，o代表剩余資源動態權值；Q代表資源的剩余值；S代表常數；t代表同資源對節點剩余負載能力的影響；u代表節點在加入任務后的資源均衡度。

4)假定z為總的請任務數，則節點的剩余負載能力Y為

(4)

式中，α代表請求任務集合數量；β代表每個任務所需要資源規模；δ代表節點對資源的容量；ε代表任務集合中每個集合任務數；φ代表總的資源數量。

5)假設σ為任意隨機非負正整數；則可完成對動態資源均衡分配μ為

(5)

式中，v代表節點的負載權重。根據上述描述，可以明確移動中心網絡動態資源調度原理。利用該原理，資源調度具體流程如圖1所示。

圖1 基于模式融合的網絡動態資源調度流程

2.2 移動中心網絡結構節點的分布

目前教育網絡應用的拓撲結構多是以網絡服務器作為轉發設備來設計，此這類結構具有極高的可擴展性和二分帶寬大等優勢，但隨著挖網絡節點服務器的增多，均衡調度越加困難。為實現資源調度目標，本章節度對當前常用的幾種移動中心網絡結構，如HCN，DCent等，進行分析[5]。

一般情況下，為明確節點在移動網絡結構中的分布，需要將拓撲結構轉換為無向圖模式。定義如下：假定移動中心網絡拓撲結構G(V，E，φ)是由眾多節點和鏈路構成的圖，其中V、E代表節點的集合、鏈路的集合；φ是從E到無序偶集合上的函數。節點x，y之間存在邊鏈路(x，y)，則x和y可以實現通信。

定義：網絡拓撲結構G(V，E，φ)中有n個節點V=(v1，v2，…，vn)，則n階方陣A(G)=aij稱為G的鄰接矩陣，其中

(6)

當i=j時設定aij=1。

以圖2(a)HCN網絡拓撲結構為例，矩陣表達形式如下

圖2 節點分布示意圖

(7)

根據矩陣表形式得到節點分布示意圖，如圖3所示。

圖3 混合max-min和蟻群算法資源調度流程

2.3 確定適配因子

在整個移動網絡結構中，各節點組成一個相當大的集群系統。該集群系統由一個中心節點和若干個計算節點組成，中心節點負責按照某種負載均衡策略進行任務請求的分配，計算節點任務請求的處理執行[6]。對于一個規模較大的集群系統而言，避免節點集群中僅有少量節點提供服務以至超載而其它節點處于空閑狀態，平衡各節點之間的任務請求分配，成為該子議案共享中面臨的關鍵問題。

1)節點負載狀態確定

節點狀態有三種：空閑狀態、繁忙狀態以及節點過載狀態。其中，空閑狀態是指節點都處在一種空置狀態，相當于節點中沒有任何負載數據；繁忙狀態是指節點一直處在資源將近飽和的狀態；過載狀態是指節點已經處在滿載狀態，不能再接收調度的資源[7]。

對于網絡節點負載狀態的確定，目前有小波包、最小二乘支持向量機兩種方法，但前者計算精度不夠，后者計算過程較為復雜，因此將二者結合，提出一種混合預測模型。混合預測模型具體運行過程如下：

步驟1：網絡服務節點初始化，清空節點中負載信息和樣本空間。

步驟2：想節點中輸入資源，并采集節點的負載值。

步驟3：將采集到的負載值生成負載序列值存放在樣本空間中。

步驟4：建立節點負載估算模型。將上述結果輸入到模型當中，進行模型訓練。

步驟5：利用訓練好的模型預測連接節點的負載值。

步驟6：將計算出來的節點負載值并發給負載均衡節點，用新的負載值來更新節點負載狀態。

步驟7：誤差判斷。計算節點預測負載值與實際值之間的誤差，若誤差大于設定的閾值，則回到步驟4，重新訓練樣本；若設定的誤差小于設定的閾值，則需要重復步驟5操作，直至得到較為準確的負載預測值[8]。

2)資源占有率確定

除了要明確節點資源占有率外，還需要明確各節點的資源占有率，才能得到適配因子，為后續資源調度奠定基礎。

節點資源占有率是指節點現有資源在該節點總體資源使用能力中的比重，公式表示如下

(8)

式中，c為節點資源占有率；z為節點現有資源規模；v為節點總體資源使用能力。

3)適配因子確定

根據上述結果，計算二者之間的適配因子a，計算公式如下

(9)

式中，bi為資源處理權；e為增加匹配的可行性系數；d為節點負載指數。

2.4 混合模式實現資源調度

對于資源調度，常用的處理模式有蟻群算法、max-min算法、遺傳算法、貪婪算法等，但均存在一些缺點，因此本文將其中兩種單一模式結合在一起，實現優勢互補，即提出基于模式融合的網絡動態資源柔性調度方法，主要選用max-min算法和蟻群算法來完成[9]。

1)max-min算法

max-min算法是一種較為經典的調度方法，優點是簡單，易操作，因此執行效率較高。基本原理過程如下：

步驟1：判斷網絡節點是否處在空閑狀態。若處在空閑狀態，則直接跳轉到步驟7；若不是空閑狀態則繼續執行步驟2；

步驟2：將節點中現有資源映射到所有可用節點上，并求出最快完成該任務的時間。

步驟3：根據步驟2得到的結果，找出最早完成時間所對應的那個資源規模和所對應的節點。

步驟4：將資源映射到節點上，并將該資源從節點資源集合刪除。

步驟5：更新節點的期望就緒時間。

步驟6：更新其它資源在節點上完成映射的時間，并回到步驟1。

步驟7：結束。

2)蟻群算法

蟻群算法是模擬螞蟻覓食原理而構建的一種尋優方法，其基本原理如下：

步驟1：假定蟻群規模為M，其中每只螞蟻都代表一種調度方案。

步驟2：初始化移動網絡節點集群系統，并提供集群中所有節點自身的CPU個數以及處理性能等，這些記為集群節點的信息素[10]。

步驟3：利用初始化公式對集群節點的信息素初始化，得到初始信息素。

步驟4：收集各節點的資源信息。

步驟5：隨機選取一個節點組作為資源調度的第一個節點，并根據其信息素計算出轉移概率的大小。按照從大到小的順序決定下一資源分配的節點[11]。重復本步驟，直至所有節點都調度完成。

步驟6：根據適配因子，篩選調度方案，并根據執行時間和負載均衡性，修改信息素，重復上述步驟，直至尋找到最優資源調度方案。

步驟7：結束。

3)混合算法

將上述max-min算法和蟻群算法混合在一起，實現網絡動態教育資源柔性調度，基本流程如圖4所示[12]。

圖4 實驗環境

通過以上步驟，將max-min算法與蟻群算法相結合，實現網絡動態資源的柔性調度。

3 實驗結果與分析

3.1 實驗環境

表1 實驗環境

3.2 實驗平臺

由C1oudSim搭建資源均衡調度仿真平臺。平臺操作步驟如下：

步驟1：初始化GridSim 庫

步驟2：創建數據中心，在CloudSim仿真平臺中，一個數據中心由一個或多個Machine組成，一個Machine是由一個或多個PEs或CPUs組成。

步驟3：創建代理Broker。

步驟4：創建虛擬機。

步驟5：創建云任務。

步驟6：啟動仿真。

步驟7：在仿真結束后統計結果[12]。

3.3 移動網絡節點分布

圖5 移動網絡節點分布波形圖

3.4 結果分析

1)調度精度

為驗證研究方法的網絡動態資源柔性調度精度，在本次實驗中，將文獻[2]、文獻[3]、文獻[4]三種傳統方法作為實驗的對照組，與研究方法作對比，得到網絡資源調度精度結果。

根據圖6的實驗結果可得知，對于移動網絡整體區域來講，研究方法的資源柔性調度效果是更好的，具有更高的調度精度。三種傳統方法的調度精度最高為40%，這樣的精度是無法滿足實際應用要求的，說明傳統方法具有較差的應用性。相比之下，研究方法的資源調度精度可以穩定在50～60%，研究方法不僅在精度上有所提升，且具有很好的穩定性。

圖6 不同方法調度精度對比

2)資源利用率

由表2可知，本文調度方法運行下，資源利用率最后達到為95.77%。這一結果與基于三種單一模式的網絡動態教育資源調度方法相比，資源利用率有了極大提高，由此證明了本文基于模式融合的網絡動態資源柔性調度的有效性和可行性。

表2 資源利用率

3)負載均衡度

由表3可知，本文調度方法運行下，資負載均衡度最終達到為93.12%。而基于三種單一模式的網絡動態教育資源調度方法運行下，負載均衡度達到88.14%、85.10%、90.12%。四種結果對比可知，本文基于模式融合的網絡動態資源柔性調度方法調度效果更好。

表3 節點負載均衡度

通過上述資源利用率和負載均衡度兩個指標結果，證明了本文方法能更改善資源不均衡現象，更有利于實現資源共享。