王劍釗,劉佳娜

(1.黑龍江中醫(yī)藥大學(xué)醫(yī)學(xué)信息工程學(xué)院,黑龍江 哈爾濱 150040; 2.哈爾濱職業(yè)技術(shù)學(xué)院,黑龍江 哈爾濱 150040)

隨著在線課程技術(shù)和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展,各大高校紛紛開設(shè)大規(guī)模開放在線課程(MOOC,massive open online course),對互聯(lián)網(wǎng)資源和帶寬構(gòu)成嚴(yán)重挑戰(zhàn),如何在互聯(lián)網(wǎng)資源有限的環(huán)境下,為MOOC提供高效和準(zhǔn)確的在線課程查詢操作成為推動(dòng)和普及MOOC的關(guān)鍵因素[1]。自適應(yīng)查詢處理器(AQP,adaptive query processing)作為MOOC的核心組件對平衡系統(tǒng)負(fù)載、映射查詢方案具有決定性作用。傳統(tǒng)的查詢調(diào)度算法主要考慮提高查詢速度[2],對于系統(tǒng)負(fù)載平穩(wěn)問題并未考慮。而實(shí)際應(yīng)用中,由于MOOC查詢的大規(guī)模和應(yīng)用固定性特點(diǎn)[3],為了降低系統(tǒng)資源成本,必須要求AQP考慮查詢系統(tǒng)負(fù)載的平衡問題。為提高查詢效率和平衡系統(tǒng)負(fù)載,提出一種基于生物地理學(xué)優(yōu)化算法(BBO,biogeography-based optimization)優(yōu)化平衡負(fù)載的自適應(yīng)查處調(diào)度器(BAQP,balanced adaptive query processing)在線課程查詢算法,通過優(yōu)化查詢期望代價(jià)矩陣(QEC,query expected cost)實(shí)現(xiàn)在線課程最優(yōu)化查詢和調(diào)度。

1 BBO算法

BBO算法通過模擬棲息地之間的物種遷移進(jìn)行尋優(yōu),將棲息地視為所要優(yōu)化問題的可能解,運(yùn)用棲息地的適應(yīng)度指數(shù)(HSI,habitat suitability index)評價(jià)每個(gè)解集的好壞,尋優(yōu)時(shí),首先隨機(jī)產(chǎn)生多個(gè)棲息地NP作為所要優(yōu)化問題的初始解,之后通過棲息地之間的物種遷移進(jìn)行信息交換,增加棲息地的物種多樣性,提高棲息地的HSI,從而獲得所要優(yōu)化問題的最優(yōu)解。該算法主要步驟如下。

1.1 算法初始化

初始化BBO算法參數(shù):棲息地最大變異率和最大遷入率分別為mmax和I,棲息地最大遷出率為E,每個(gè)棲息地可容納的最大物種數(shù)量為Smax,隨機(jī)產(chǎn)生NP個(gè)棲息地[5],即

xij=xjmin+(xjmax-xjmin)×rand,

(1)

其中:xij為棲息地Xi=[xi1,xi2,…,xiD]的第j維解變量;xjmax、xjmin分別為第j維變量的上限和下限值。

1.2 遷移

通過遷移實(shí)現(xiàn)棲息地之間的信息交換,可以實(shí)現(xiàn)解空間的廣域搜索。由BBO算法基本原理可知,棲息地的HSI和物種多樣性成正比例關(guān)系,棲息地的HSI越高,其可容納的物種數(shù)量越多,所以物種數(shù)量Si和棲息地Xi之間存在一定的數(shù)學(xué)映射關(guān)系,根據(jù)HSI值的大小對Xi重新排序,原來的棲息地Xi被賦值新的i值,重新排序之后的棲息地Xi的物種數(shù)量Si[6]為

Si=Smax-i,i∈{1,2,…,NP}

(2)

棲息地Xi的遷入率λi和遷出率μi分別為

(3)

1.3 變異

通過變異操作[7]可以模擬某一棲息地發(fā)生自然災(zāi)害或者突發(fā)疾病,導(dǎo)致HSI發(fā)生改變,結(jié)合遷入率λi和遷出率μi可以計(jì)算出棲息地Xi的物種概率Pi,即

(4)

由BBO算法原理可知,變異率mi與物種概率Pi存在反比例關(guān)系,所以棲息地Xi的變異率[8]mi為

(5)

其中:mmax為棲息地的最大變異率;Pmax為物種概率的最大值。

2 BAQP模塊結(jié)構(gòu)

BAQP[9-10]的系統(tǒng)負(fù)載平衡主要通過5個(gè)模塊自適應(yīng)實(shí)現(xiàn),5個(gè)模塊分別為監(jiān)測模塊、預(yù)測模塊、規(guī)劃模塊、執(zhí)行模塊和反饋模塊。BQAP模塊結(jié)構(gòu)如圖1所示。

圖1 BAQP模塊結(jié)構(gòu)Fig.1 BAQP module structure

監(jiān)控模塊與元數(shù)據(jù)服務(wù)和反饋執(zhí)行信息模塊連接,分別接收數(shù)據(jù)資源動(dòng)態(tài)信息、靜態(tài)信息和反饋執(zhí)行信息,同時(shí)將查詢處理任務(wù)和元數(shù)據(jù)服務(wù)的資源信息提交給評估模塊處理。

評估模塊與監(jiān)控模塊相連接,其可以根據(jù)系統(tǒng)設(shè)定的資源狀態(tài)閾值預(yù)測和判斷查詢系統(tǒng)的內(nèi)存剩余、系統(tǒng)CPU、網(wǎng)絡(luò)I/O的下一階段資源狀態(tài)和服務(wù)器用戶量負(fù)載,判定該資源是否參與查詢算法調(diào)度規(guī)劃,提高查詢系統(tǒng)的執(zhí)行效率。

規(guī)劃模塊通過調(diào)度算法根據(jù)目標(biāo)函數(shù)實(shí)現(xiàn)最優(yōu)或者次優(yōu)方法的查詢規(guī)劃。執(zhí)行模塊根據(jù)規(guī)劃模塊的計(jì)算結(jié)果,監(jiān)督各個(gè)模塊的進(jìn)度執(zhí)行情況,并將查詢情況反饋給監(jiān)控模塊。

反饋模塊收集查詢執(zhí)行的動(dòng)態(tài)實(shí)時(shí)信息,并將反饋執(zhí)行信息提交給監(jiān)控模塊。

3 在線課程查詢優(yōu)化算法

BAQP的核心組成部分是查詢優(yōu)化算法,其可以為查詢系統(tǒng)提供動(dòng)態(tài)查詢和資源調(diào)度映射方案,其涉及如下定義[11-12]:

資源單元:在線課程查詢時(shí),分配給查詢的最小資源數(shù)量,記作R;消耗資源單元量:一個(gè)請求消耗的資源單元數(shù)量,記作Q(i);時(shí)間單元:查詢時(shí)查詢占用時(shí)間的最小單元,記作t。

若可提供的資源量為R={R1,R2,…,Rn},查詢消耗的資源量為Q={Q1,Q2,…,Qn},QEC(i,j)為查詢?nèi)蝿?wù)Q(i)在資源R(j)上的資源負(fù)載耗費(fèi)比值,其可表示為

QEC(i,j)=α×Nct(i,j)+β×work_load(i,j),

(6)

其中:α、β為權(quán)值,可以取靜態(tài)值或者動(dòng)態(tài)值,并且α+β=1;Nct(i,j)為子查詢Q(i)在資源R(j)上的帶寬負(fù)載耗費(fèi)比值;work_load(i,j)為查詢i在資源j上服務(wù)端資源負(fù)載耗費(fèi)比值。Nct(i,j)公式為

Nct(i,j)=Rbandwidth(j)/Qbandwidth(i),

(7)

work_load(i,j)公式為

(8)

其中:Rbandwidth(j)、Qbandwidth(j)分別為帶寬資源單元和帶寬消耗資源單元;work_load(i,j,k)為查詢i和資源j的CPU、內(nèi)存和服務(wù)器的查詢資源耗費(fèi)單元量/資源單位量。

4 基于BBO-QEC的在線課程查詢算法

4.1 適應(yīng)度函數(shù)

在線課程查詢時(shí),為了平衡查詢資源之間的負(fù)載以及降低負(fù)載的消耗,運(yùn)用BBO算法對BAQP的期望代價(jià)矩陣QEC(i,j)進(jìn)行優(yōu)化。當(dāng)QEC(i,j)越大時(shí),說明查詢該課程所耗費(fèi)的資源單元量越多,同時(shí)耗費(fèi)的負(fù)載代價(jià)也越大。因此BBO-QEC的適應(yīng)度函數(shù)為

Min QEC(i,j)=α×Nct(i,j)+

β×work_load(i,j)。

(9)

4.2 算法流程

基于BBO-QEC的在線課程查詢算法流程為:

Step1讀取查詢課程隊(duì)列Q={Q1,Q2,…,Qn}和QEC矩陣;

Step2BBO算法初始化:mmax、I、E、Smax以及種群規(guī)模N和最大迭代次數(shù)Iter,隨機(jī)產(chǎn)生NP個(gè)棲息地作為初始種群;

Step3根據(jù)適應(yīng)度函數(shù)式(9)計(jì)算每個(gè)棲息地的HSI,并進(jìn)行降序排列,計(jì)算降序排列之后棲息地Xi的遷入率λi、遷出率μi和物種數(shù)量Si;

Step4根據(jù)遷入率λi和遷出率μi進(jìn)行遷移操作;

Step5結(jié)合遷入率λi和遷出率μi可以計(jì)算出棲息地Xi的物種概率Pi,之后確定棲息地Xi的變異率mi;

Step6根據(jù)變異率mi進(jìn)行變異操作;

Step7判斷算法終止條件,若當(dāng)前迭代次數(shù)t>Iter,則輸出最優(yōu)查詢方案;反之,返回Step3～Step7。

5 實(shí)證分析

5.1 模擬環(huán)境

為驗(yàn)證新算法的有效性和可靠性,建立如下在線課程查詢模擬環(huán)境:

(1) 建立資源隊(duì)列R={R1,R2,…,R4},Rk=[Rcpu(k),Rmemory(k),Rload(k),Rnet(k)],其中k=4,[0,300]之間隨機(jī)生成大小為4×4的資源剩余單元量矩陣;

(2) 建立在線課程查詢隊(duì)列Q={Q1,Q2,…,Q5},Qi=[Rcpu(i),Qmemory(i),Qload(i),Qnet(i)],其中i=5,[0,30]之間隨機(jī)生成大小為5×4的資源消耗單元量矩陣;

(3) 通過(1)～(2),結(jié)合公式(6)建立大小為5×4的QEC矩陣;

(4) 對比BBO-QEC、Min-Min算法和Max-Min算法,并輸出計(jì)算結(jié)果。

Min-Min算法[13]是首先映射小的任務(wù),并且映射到執(zhí)行快的機(jī)器上。執(zhí)行過程具體可以描述為:計(jì)算要參與映射事件的每個(gè)任務(wù)在各個(gè)機(jī)器上的期望完成時(shí)間,找到每個(gè)任務(wù)的最早完成時(shí)間及其對應(yīng)的機(jī)器;從中找出最小且最早完成時(shí)間的任務(wù),將該任務(wù)指派給獲得它的機(jī)器;指派完成后,更新機(jī)器期望就緒時(shí)間并將已完成映射的任務(wù)從任務(wù)集合中刪除。重復(fù)上面的過程,直到所有的任務(wù)都被映射完。

Max-Min算法[14]與Min-Min算法類似。同樣要計(jì)算每一任務(wù)在任一可用機(jī)器上的最早完成時(shí)間,不同的是Max-Min算法首先調(diào)度大任務(wù),任務(wù)到資源的映射是選擇最早完成時(shí)間最大的任務(wù)映射到所對應(yīng)的機(jī)器上。

5.2 評價(jià)方法

在MOOC系統(tǒng)中,當(dāng)查詢?nèi)蝿?wù)滿足其最低資源單元量時(shí),在線課程查詢能夠流暢執(zhí)行。因此,評價(jià)在線課程查詢調(diào)度算法的性能主要考慮查詢調(diào)度方案是否可以平衡系統(tǒng)資源,降低系統(tǒng)負(fù)載消耗,而不是考慮傳統(tǒng)的時(shí)間消耗或者執(zhí)行速度。

若資源i的負(fù)載消耗系數(shù)值定義為

(9)

系統(tǒng)的總體負(fù)載消耗系數(shù)makeload為

makeload=max(TR),

(10)

其中:makeload為所有負(fù)載消耗系數(shù)值的最大值,其值越小則說明算法的平衡系統(tǒng)的能力越強(qiáng),系統(tǒng)整體負(fù)載越小。

5.3 結(jié)果分析

BBO算法設(shè)置:最大變異率mmax=0.01、I=E=1、Smax以及種群規(guī)模N=30和最大迭代次數(shù)Iter=100,NP=100。靜態(tài)權(quán)值和動(dòng)態(tài)權(quán)值的對比結(jié)果分別如圖2和圖3所示。靜態(tài)權(quán)值和動(dòng)態(tài)權(quán)值查詢性能誤差對比分別見表1和表2。

圖2(a)為靜態(tài)權(quán)值環(huán)境下5任務(wù)和4資源10次隨機(jī)運(yùn)行實(shí)驗(yàn)的makeload值對比圖;圖2(b)為靜態(tài)權(quán)值環(huán)境下100任務(wù)和20資源10次隨機(jī)運(yùn)行實(shí)驗(yàn)的makeload值對比圖。由圖2(a)和圖2(b)以及表1可知,整體情況下,BBO-QEC的makeload值小于Min-Min和Max-Min算法,從而說明BBO算法較Min-Min和Max-Min算法具有更強(qiáng)的系統(tǒng)負(fù)載平衡能力和較低的系統(tǒng)負(fù)載率,可以有效降低系統(tǒng)消耗系數(shù)。

圖2 靜態(tài)權(quán)值查詢性能對比Fig.2 Static weighted value query performance comparison

圖3 動(dòng)態(tài)權(quán)值查詢性能對比Fig.3 Dynamic weighted value query performance comparison

表1 靜態(tài)權(quán)值查詢性能誤差對比

表2 動(dòng)態(tài)權(quán)值查詢性能誤差對比

圖3(a)為動(dòng)態(tài)權(quán)值環(huán)境下5任務(wù)和4資源10次隨機(jī)運(yùn)行實(shí)驗(yàn)的makeload值對比圖;圖3(b)為動(dòng)態(tài)權(quán)值環(huán)境下100任務(wù)和20資源10次隨機(jī)運(yùn)行實(shí)驗(yàn)的makeload值對比圖。由圖3(a)和圖3(b)及表3可知,整體情況下,BBO-QEC的makeload值小于Min-Min和Max-Min算法,從而說明BBO算法較Min-Min和Max-Min算法具有更強(qiáng)的系統(tǒng)負(fù)載平衡能力和較低的系統(tǒng)負(fù)載率,可以有效降低系統(tǒng)消耗系數(shù)。

6 結(jié)論

為解決MOOC系統(tǒng)查詢負(fù)載均衡問題,降低系統(tǒng)負(fù)載率,在BAQP的基礎(chǔ)上,提出一種基于BBO算法優(yōu)化QEC的在線課程查詢調(diào)度算法。選擇系統(tǒng)的總體負(fù)載消耗系數(shù)作為評價(jià)指標(biāo),運(yùn)用BBO算法優(yōu)化獲取在線課程的最優(yōu)查詢方案。通過靜態(tài)權(quán)值和動(dòng)態(tài)權(quán)值不同任務(wù)和資源查詢調(diào)度性能對比可知,BBO算法較Min-Min和Max-Min算法具有更強(qiáng)的系統(tǒng)負(fù)載平衡能力和較低的系統(tǒng)負(fù)載率,可以有效降低系統(tǒng)消耗系數(shù)。