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

姜 濤

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

1 引言

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

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

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

(6)

當(dāng)i=j時設(shè)定aij=1。

以圖2(a)HCN網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為例，矩陣表達(dá)形式如下

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

(7)

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

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

2.3 確定適配因子

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

1)節(jié)點(diǎn)負(fù)載狀態(tài)確定

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

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

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

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

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

步驟4：建立節(jié)點(diǎn)負(fù)載估算模型。將上述結(jié)果輸入到模型當(dāng)中，進(jìn)行模型訓(xùn)練。

步驟5：利用訓(xùn)練好的模型預(yù)測連接節(jié)點(diǎn)的負(fù)載值。

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

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

2)資源占有率確定

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

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

(8)

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

3)適配因子確定

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

(9)

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

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

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

1)max-min算法

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

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

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

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

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

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

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

步驟7：結(jié)束。

2)蟻群算法

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

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

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

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

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

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

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

步驟7：結(jié)束。

3)混合算法

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

圖4 實(shí)驗(yàn)環(huán)境

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

表1 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)平臺

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

步驟1：初始化GridSim 庫

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

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

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

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

步驟6：啟動仿真。

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

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

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

3.4 結(jié)果分析

1)調(diào)度精度

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

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

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

2)資源利用率

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

表2 資源利用率

3)負(fù)載均衡度

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

表3 節(jié)點(diǎn)負(fù)載均衡度

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