基于模式融合的網(wǎng)絡動態(tài)資源柔性調(diào)度仿真

姜 濤

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

1 引言

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

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

為此，提出基于模式融合的網(wǎng)絡動態(tài)資源柔性調(diào)度方法。明確移動中心網(wǎng)絡結(jié)構(gòu)，獲取網(wǎng)絡結(jié)構(gòu)中節(jié)點負載和資源占有率，并以此得出適配因子，利用max-min蟻群算法自動調(diào)度資源，實現(xiàn)移動網(wǎng)絡動態(tài)教育資源的均衡分配，提高資源利用率。

2 基于模式融合的網(wǎng)絡動態(tài)資源柔性調(diào)度方法

2.1 資源調(diào)度原理

1)假設a為移動中心網(wǎng)絡中節(jié)點數(shù)量，R為節(jié)點當前資源規(guī)模，則節(jié)點當前資源規(guī)模占據(jù)自身所能容納總資源的比重為

(1)

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

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

(2)

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

3)假定mi為第i節(jié)點已經(jīng)調(diào)度到的資源，則各個節(jié)點的動態(tài)權值w為

(3)

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

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

(4)

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

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

(5)

式中，v代表節(jié)點的負載權重。根據(jù)上述描述，可以明確移動中心網(wǎng)絡動態(tài)資源調(diào)度原理。利用該原理，資源調(diào)度具體流程如圖1所示。

圖1 基于模式融合的網(wǎng)絡動態(tài)資源調(diào)度流程

2.2 移動中心網(wǎng)絡結(jié)構(gòu)節(jié)點的分布

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

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

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

(6)

當i=j時設定aij=1。

以圖2(a)HCN網(wǎng)絡拓撲結(jié)構(gòu)為例，矩陣表達形式如下

圖2 節(jié)點分布示意圖

(7)

根據(jù)矩陣表形式得到節(jié)點分布示意圖，如圖3所示。

圖3 混合max-min和蟻群算法資源調(diào)度流程

2.3 確定適配因子

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

1)節(jié)點負載狀態(tài)確定

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

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

步驟1：網(wǎng)絡服務節(jié)點初始化，清空節(jié)點中負載信息和樣本空間。

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

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

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

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

步驟6：將計算出來的節(jié)點負載值并發(fā)給負載均衡節(jié)點，用新的負載值來更新節(jié)點負載狀態(tài)。

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

2)資源占有率確定

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

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

(8)

式中，c為節(jié)點資源占有率；z為節(jié)點現(xiàn)有資源規(guī)模；v為節(jié)點總體資源使用能力。

3)適配因子確定

根據(jù)上述結(jié)果，計算二者之間的適配因子a，計算公式如下

(9)

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

2.4 混合模式實現(xiàn)資源調(diào)度

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

1)max-min算法

max-min算法是一種較為經(jīng)典的調(diào)度方法，優(yōu)點是簡單，易操作，因此執(zhí)行效率較高。基本原理過程如下：

步驟1：判斷網(wǎng)絡節(jié)點是否處在空閑狀態(tài)。若處在空閑狀態(tài)，則直接跳轉(zhuǎn)到步驟7；若不是空閑狀態(tài)則繼續(xù)執(zhí)行步驟2；

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

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

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

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

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

步驟7：結(jié)束。

2)蟻群算法

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

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

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

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

步驟4：收集各節(jié)點的資源信息。

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

步驟6：根據(jù)適配因子，篩選調(diào)度方案，并根據(jù)執(zhí)行時間和負載均衡性，修改信息素，重復上述步驟，直至尋找到最優(yōu)資源調(diào)度方案。

步驟7：結(jié)束。

3)混合算法

將上述max-min算法和蟻群算法混合在一起，實現(xiàn)網(wǎng)絡動態(tài)教育資源柔性調(diào)度，基本流程如圖4所示[12]。

圖4 實驗環(huán)境

通過以上步驟，將max-min算法與蟻群算法相結(jié)合，實現(xiàn)網(wǎng)絡動態(tài)資源的柔性調(diào)度。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

表1 實驗環(huán)境

3.2 實驗平臺

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

步驟1：初始化GridSim 庫

步驟2：創(chuàng)建數(shù)據(jù)中心，在CloudSim仿真平臺中，一個數(shù)據(jù)中心由一個或多個Machine組成，一個Machine是由一個或多個PEs或CPUs組成。

步驟3：創(chuàng)建代理Broker。

步驟4：創(chuàng)建虛擬機。

步驟5：創(chuàng)建云任務。

步驟6：啟動仿真。

步驟7：在仿真結(jié)束后統(tǒng)計結(jié)果[12]。

3.3 移動網(wǎng)絡節(jié)點分布

圖5 移動網(wǎng)絡節(jié)點分布波形圖

3.4 結(jié)果分析

1)調(diào)度精度

為驗證研究方法的網(wǎng)絡動態(tài)資源柔性調(diào)度精度，在本次實驗中，將文獻[2]、文獻[3]、文獻[4]三種傳統(tǒng)方法作為實驗的對照組，與研究方法作對比，得到網(wǎng)絡資源調(diào)度精度結(jié)果。

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

圖6 不同方法調(diào)度精度對比

2)資源利用率

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

表2 資源利用率

3)負載均衡度

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

表3 節(jié)點負載均衡度

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