基于商空間的層次式數(shù)據(jù)網(wǎng)格資源調(diào)度算法

夏純中，宋順林

（1.江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013；2.江蘇大學(xué) 信息化中心，江蘇 鎮(zhèn)江 212013）

1 引言

近年來，數(shù)據(jù)網(wǎng)格憑借其強(qiáng)大的擴(kuò)展能力被用于構(gòu)建企業(yè)級數(shù)據(jù)庫云平臺。例如，大型醫(yī)療集團(tuán)信息集成平臺[1]利用數(shù)據(jù)網(wǎng)格對集團(tuán)內(nèi)各醫(yī)療機(jī)構(gòu)分布異構(gòu)的醫(yī)療信息數(shù)據(jù)庫進(jìn)行集成和共享；紅帽發(fā)布的JBoss Enterprise Data Grid[2]更是將數(shù)據(jù)網(wǎng)格作為其企業(yè)云計算戰(zhàn)略的重要基礎(chǔ)構(gòu)件。層次式數(shù)據(jù)網(wǎng)格是一種常見的數(shù)據(jù)網(wǎng)格架構(gòu)，由于大規(guī)模分布式系統(tǒng)具有小世界特性，用戶在對數(shù)據(jù)的使用上呈現(xiàn)出社團(tuán)性和層次性，即特定區(qū)域內(nèi)的用戶只對特定部分的數(shù)據(jù)最感興趣，而層次式數(shù)據(jù)網(wǎng)格可以很好滿足這一需求。

在企業(yè)應(yīng)用領(lǐng)域，用戶對數(shù)據(jù)網(wǎng)格的服務(wù)質(zhì)量（QoS，quality of service）有著和科學(xué)計算截然不同的需求。網(wǎng)絡(luò)連接帶寬和不同網(wǎng)格節(jié)點(diǎn)處理能力的差異導(dǎo)致數(shù)據(jù)網(wǎng)格無法像傳統(tǒng)的企業(yè)數(shù)據(jù)中心那樣為業(yè)務(wù)系統(tǒng)提供實(shí)時、可靠的數(shù)據(jù)服務(wù)。層次式數(shù)據(jù)網(wǎng)格資源調(diào)度的目的就是為網(wǎng)格中各節(jié)點(diǎn)和不同級別業(yè)務(wù)分配帶寬，保障各級業(yè)務(wù)的服務(wù)質(zhì)量，并使系統(tǒng)整體資源利用率最優(yōu)。

層次式數(shù)據(jù)網(wǎng)格資源調(diào)度可以采用現(xiàn)有的數(shù)據(jù)網(wǎng)格調(diào)度算法，常見的數(shù)據(jù)網(wǎng)格調(diào)度算法大致分為 4類。1) 基于綜合指標(biāo)直接選擇法。Cheng[3]提出一種基于Min-Max的負(fù)載均衡算法，將文件和網(wǎng)絡(luò)帶寬分為Min和Max 2類，調(diào)度時根據(jù)文件所屬類別到相應(yīng)站點(diǎn)下載。Mistarihi等人[4]使用響應(yīng)時間、可靠性和安全構(gòu)成一個評價指標(biāo)，并使用層次分析法確定各指標(biāo)的權(quán)重。Du等人[5]提出了一種基于可靠度的指標(biāo)來減少任務(wù)完成時間和執(zhí)行代價。Qu等人[6]提出網(wǎng)絡(luò)負(fù)載和服務(wù)容忍度 2個目標(biāo)函數(shù)，使用權(quán)重因子平衡2個目標(biāo)函數(shù)。Tang等人[7]提出一種副本價格模型，模型綜合考慮了CPU、內(nèi)存、網(wǎng)絡(luò)的延時、帶寬和可靠性等多種因素，并通過拍賣協(xié)議選取傳輸代價最小的副本。2) 基于機(jī)器學(xué)習(xí)法。文獻(xiàn)[8,9]都采用神經(jīng)網(wǎng)絡(luò)構(gòu)建數(shù)據(jù)傳輸時間預(yù)測模型，使用日志數(shù)據(jù)中不同大小文件在不同網(wǎng)絡(luò)帶寬下的傳輸時間作為樣本對模型進(jìn)行訓(xùn)練。文獻(xiàn)[10]采用k-NN算法對不同節(jié)點(diǎn)磁盤IO和網(wǎng)絡(luò)延時下的文件下載時間進(jìn)行學(xué)習(xí)。文獻(xiàn)[11]中，Almuttairi等人提出基于K均值聚類對站點(diǎn)進(jìn)行分類，采用基于灰度的粗糙集理論解決安全、可靠性、成本和響應(yīng)時間等屬性不確定的問題。3) 基于時間序列法。Li等人[12]使用灰色理論預(yù)測副本響應(yīng)時間，并使用馬爾科夫鏈預(yù)測副本的可靠性。Wu等人[13]提出一種狀態(tài)模糊評估策略，并使用灰色GM(1,1)模型動態(tài)地預(yù)測服務(wù)時間。4) 基于進(jìn)化計算法。Munoz[14]提出基于粒子群優(yōu)化算法，根據(jù)網(wǎng)絡(luò)延遲和帶寬確定傳輸代價，使用訪問率和傳輸代價作為最優(yōu)化評價函數(shù)。Xiong[15]提出了副本選擇算法的 QoS模型，采用層次分析法分析不同 QoS指標(biāo)的重要程度，并以此作為不同指標(biāo)的權(quán)重向量。提出了一種基于MapReduce的并行遺傳算法加速運(yùn)算。算法主要考慮3個QoS指標(biāo)，即平均傳輸率、平均帶寬和可靠性。直接使用上述算法對層次式數(shù)據(jù)網(wǎng)格進(jìn)行調(diào)度時，由于算法中所有節(jié)點(diǎn)均在同一層面，當(dāng)網(wǎng)格節(jié)點(diǎn)數(shù)量很大時，極易出現(xiàn)以下2個問題：①算法難以保證系統(tǒng)全局最優(yōu)，這主要是由于算法缺少在不同粒度、不同層面上對網(wǎng)格流量進(jìn)行調(diào)度，沒有充分利用層內(nèi)和層間節(jié)點(diǎn)對不同優(yōu)先級的任務(wù)進(jìn)行優(yōu)化。②數(shù)據(jù)網(wǎng)格資源調(diào)度問題屬于NP問題，當(dāng)網(wǎng)格內(nèi)節(jié)點(diǎn)的數(shù)量較多時，全局資源調(diào)度算法收斂過慢，難以滿足企業(yè)應(yīng)用對數(shù)據(jù)實(shí)時性的要求。

粒計算是一種通過對復(fù)雜問題進(jìn)行粒化分解，從而降低問題復(fù)雜度的方法論，它是模擬人類在解決復(fù)雜問題時能夠由粗至細(xì)，多層次地觀察和分析問題的能力。張鈴和張鈸提出使用商空間理論對粒度空間進(jìn)行描述。商空間理論通過保真原理和保假原理在論域元素上構(gòu)造一系列不同粒度的商空間，形成一個分層遞階的商空間鏈，從而簡化原始問題的求解[16]。

本文首次引入粒計算的思想解決傳統(tǒng)數(shù)據(jù)網(wǎng)格資源調(diào)度算法在調(diào)度層次式數(shù)據(jù)網(wǎng)格時存在的問題，提出了一種基于商空間的層次式數(shù)據(jù)網(wǎng)格資源調(diào)度 QSHDGRA（quotient space theory based hierarchical data grid resource allocation）算法。其主要創(chuàng)新在于：采用商空間粒度計算的方法在不同粒度層面對數(shù)據(jù)網(wǎng)格系統(tǒng)流量進(jìn)行調(diào)度，保障不同優(yōu)先級業(yè)務(wù)的QoS的需求，此外調(diào)度算法還兼顧了數(shù)據(jù)網(wǎng)格整體節(jié)點(diǎn)負(fù)載和網(wǎng)絡(luò)流量的均衡，實(shí)現(xiàn)了系統(tǒng)資源利用的全局最優(yōu)化。

2 層次式數(shù)據(jù)網(wǎng)格模型

2.1 體系結(jié)構(gòu)

層次式數(shù)據(jù)組織是一種常見的數(shù)據(jù)管理方式。如圖1所示，在層次式數(shù)據(jù)網(wǎng)格中，所有節(jié)點(diǎn)組成一個層次化的樹狀網(wǎng)絡(luò)，根節(jié)點(diǎn)擁有全部數(shù)據(jù)副本，根節(jié)點(diǎn)將所有數(shù)據(jù)副本平均分配到各個二級節(jié)點(diǎn)，二級節(jié)點(diǎn)再將數(shù)據(jù)副本平均分配到下屬的三級節(jié)點(diǎn)。一級節(jié)點(diǎn)定期監(jiān)控各節(jié)點(diǎn)和各條鏈路的負(fù)載情況，采用特定算法分配各個節(jié)點(diǎn)的處理帶寬的能力，實(shí)現(xiàn)系統(tǒng)訪問性能的全局最優(yōu)化。

為了滿足企業(yè)應(yīng)用集成領(lǐng)域中不同業(yè)務(wù) QoS的要求，將數(shù)據(jù)網(wǎng)格的業(yè)務(wù)請求分為3種QoS級別：第一類業(yè)務(wù)優(yōu)先級最高，要求能夠立即響應(yīng)；第二類業(yè)務(wù)優(yōu)先級為中，允許在一定時間內(nèi)完成響應(yīng)；第三類業(yè)務(wù)優(yōu)先級最低，當(dāng)系統(tǒng)繁忙時，可以暫停響應(yīng)。

圖1 層次式數(shù)據(jù)網(wǎng)格節(jié)點(diǎn)組織

層次式數(shù)據(jù)網(wǎng)格有以下3個優(yōu)點(diǎn)。1) 網(wǎng)格數(shù)據(jù)具有高可靠性。根節(jié)點(diǎn)和各級節(jié)點(diǎn)的數(shù)據(jù)互為異地備份。每一個數(shù)據(jù)均有3個副本，且副本互為異地備份。2) 網(wǎng)格系統(tǒng)具有很好的容錯性。任何節(jié)點(diǎn)的單點(diǎn)故障都不會影響系統(tǒng)運(yùn)行。例如，當(dāng)根節(jié)點(diǎn)發(fā)生故障時，其他副本節(jié)點(diǎn)可繼續(xù)為用戶提供數(shù)據(jù)訪問服務(wù)。3) 網(wǎng)格系統(tǒng)具有負(fù)載均衡能力。根節(jié)點(diǎn)和各級節(jié)點(diǎn)構(gòu)成一個分布式虛擬集群。當(dāng)某個節(jié)點(diǎn)或某條路徑訪問負(fù)載過高時，系統(tǒng)會自動地將訪問請求分配到其他節(jié)點(diǎn)上。

2.2 問題形式化定義

在層次式數(shù)據(jù)網(wǎng)格有向圖G(V,E)中，采用M/M/1排隊模型定義系統(tǒng)資源調(diào)度問題。

定義1（節(jié)點(diǎn)請求平均等待時間）。單位時間內(nèi)到達(dá)節(jié)點(diǎn)j的請求數(shù)為λj，節(jié)點(diǎn)j的處理能力為μj，則節(jié)點(diǎn)j的平均請求等待時間為Tj為

定義2（節(jié)點(diǎn)資源利用率）。設(shè)Sj為單位時間內(nèi)到達(dá)節(jié)點(diǎn)j的請求數(shù)占其最大處理能力的比例，則該節(jié)點(diǎn)資源利用率為

定義3（網(wǎng)絡(luò)資源利用率）。設(shè)從節(jié)點(diǎn)i出發(fā)經(jīng)過路徑pij到達(dá)節(jié)點(diǎn)j的請求數(shù)為λij，從節(jié)點(diǎn)j出發(fā)經(jīng)過路徑pij到達(dá)節(jié)點(diǎn)i的請求數(shù)為λji，路徑pij的最大吞吐率為lij，則路徑pij的網(wǎng)絡(luò)資源利用率為

定義 4（請求流量矩陣）。用請求流量矩陣(λQoSm,ij)N×N(m=1,2,3)表示系統(tǒng)內(nèi)從節(jié)點(diǎn)i出發(fā)到達(dá)節(jié)點(diǎn)j的不同QoS級別流量的分配情況。3種QoS級別流量矩陣相加，即為節(jié)點(diǎn)i到j(luò)的流量。

定義5（系統(tǒng)資源調(diào)度的多目標(biāo)優(yōu)化問題）。層次式數(shù)據(jù)網(wǎng)格系統(tǒng)資源調(diào)度問題可以分為以下 3個子問題：一是為不同QoS級別用戶分配帶寬，使用戶平均請求等待時間最小化；二是節(jié)點(diǎn)負(fù)載利用率最大化。即充分利用冗余節(jié)點(diǎn)實(shí)現(xiàn)請求負(fù)載均衡，避免請求過分集中到某些節(jié)點(diǎn)上；三是網(wǎng)絡(luò)流量利用率最大化。即充分利用空余網(wǎng)絡(luò)鏈路，避免造成某些路徑流量過大，而另外一些路徑卻未充分使用。

綜上所述，系統(tǒng)資源調(diào)度的全局最優(yōu)化目標(biāo)為確定請求流量矩陣(λQoSm,ij)N×N使得不同 QoS級別業(yè)務(wù)的平均請求等待時間最小化，同時實(shí)現(xiàn)節(jié)點(diǎn)資源利用率和網(wǎng)絡(luò)資源利用最大化。

式(6)和式(7)使用信息熵衡量網(wǎng)格中節(jié)點(diǎn)負(fù)載的均衡度和路徑流量的均衡度。第一個約束條件表示系統(tǒng)請求流量守恒，第二個約束條件表示節(jié)點(diǎn)負(fù)載分配后的流量守恒，第三個約束條件保證隊列平均長度不會無限增大。

定義6（全局最優(yōu)目標(biāo)調(diào)和函數(shù)）。采用線性加權(quán)和法將定義5中的多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題，定義層次式數(shù)據(jù)網(wǎng)格系統(tǒng)全局最優(yōu)資源調(diào)度目標(biāo)函數(shù)為

式(9)是系統(tǒng)中各 QoS用戶請求的平均等待時間和網(wǎng)絡(luò)與節(jié)點(diǎn)資源利用均衡度的調(diào)和函數(shù)。

3 基于商空間的資源調(diào)度算法

3.1 傳統(tǒng)優(yōu)化算法及其弊端

本文的最優(yōu)化問題是一個非線性規(guī)劃問題，且屬于NP問題，采用啟發(fā)式計算的方法可以快速獲得最優(yōu)解。粒子群算法是一種常用的基于進(jìn)化計算的啟發(fā)式算法，其主要特點(diǎn)是個體數(shù)目少，計算簡單，頑健性好和可并行計算。使用粒子群算法首先要確定粒子的編碼方式和適應(yīng)度函數(shù)。本文以數(shù)據(jù)網(wǎng)格節(jié)點(diǎn)間的有向連接數(shù)作為解空間維度，每一維對應(yīng)一條有向連接，其取值為分配給該連接的請求流量。每個粒子對應(yīng)的D維向量X表示系統(tǒng)資源調(diào)度問題的一個解，適應(yīng)度函數(shù)為式(9)所定義的目標(biāo)函數(shù)。

粒子群算法在求解本文最優(yōu)化問題中暴露出以下的弊端：由于問題的解空間的向量維度太大，使得算法收斂到全局最優(yōu)值的速度非常緩慢, 并且極易陷入局部最優(yōu)值。

3.2 基于商空間的優(yōu)化算法

在層次化網(wǎng)格中，隨著網(wǎng)格節(jié)點(diǎn)數(shù)目的增多，節(jié)點(diǎn)間的連接數(shù)量呈幾何級數(shù)增長，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越來越復(fù)雜，資源調(diào)度算法的搜索空間也越來越大。本文的主要思想就是使用粒度計算的思想來簡化求解層次化網(wǎng)格最優(yōu)資源調(diào)度問題的復(fù)雜度。通過對原始最優(yōu)化問題進(jìn)行層層分解，在不同粒度、不同層面上對問題進(jìn)行優(yōu)化，以求加快求解速度，并獲得全局最優(yōu)值。

3.2.1 構(gòu)建商空間

給定一個L層的層次網(wǎng)格的網(wǎng)絡(luò)圖G(V,E)，用l(v)表示節(jié)點(diǎn)所屬的層次。根節(jié)點(diǎn)屬于第一層，即l1=1，其余各層次關(guān)系為l1<…< lk…

定義7等價關(guān)系R(lk)。

該等價關(guān)系的實(shí)質(zhì)是將某一級節(jié)點(diǎn)及其各自所有子節(jié)點(diǎn)看作一個整體，即一個粒子，和上級節(jié)點(diǎn)歸為同一等價類。當(dāng)li從1增大到k時，可以在各個級別層次上構(gòu)建不同粒度的網(wǎng)絡(luò)拓?fù)洌纬煞謱舆f階的商空間鏈。

3.2.2 資源調(diào)度算法

基于商空間的層次式數(shù)據(jù)網(wǎng)格資源調(diào)度算法形式化定義如下。

問題：給定層次式數(shù)據(jù)網(wǎng)格G(V,E)，確定其上的各優(yōu)先級業(yè)務(wù)的最優(yōu)請求流量矩陣(λQoSm,ij)N×N，使得系統(tǒng)全局資源調(diào)度目標(biāo)值Z(λ)最小。

算法步驟描述如下。

1) 構(gòu)建商空間。輸入原始層次化網(wǎng)格模型G，給出網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量V，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)E，各連接鏈路最大負(fù)載L和節(jié)點(diǎn)的最大負(fù)載S。根據(jù)網(wǎng)絡(luò)層次結(jié)構(gòu)確定等價關(guān)系R，并構(gòu)建分層遞階商空間鏈G1＞G2＞… ＞GL。

2) 確定求解最優(yōu)化算法的粒子群規(guī)模m和算法參數(shù)，包括慣性因子w、學(xué)習(xí)因子c和速度限值S。設(shè)定最大迭代次數(shù)n和迭代終止閾值ε。

3) 由于G1是將全體節(jié)點(diǎn)看作一個整體，沒有進(jìn)行劃分，因此從第二層商空間開始進(jìn)行遞歸求解。設(shè)k=2，轉(zhuǎn)到4)。

4) 在商空間Gk中，根據(jù)節(jié)點(diǎn)數(shù)量Vk和連接數(shù)量Ek構(gòu)建流量矩陣作為解向量Xk。使用粒子群算法完成一次搜索，求得本層粒子的一個最優(yōu)解。查看該空間是否有更細(xì)粒度的空間，如果有轉(zhuǎn)到5)，否則轉(zhuǎn)到6)。

5) 進(jìn)入更細(xì)一層商空間Gk+1，構(gòu)建流量矩陣，由于上一層空間的搜索有陷入局部最優(yōu)值的可能，因此本層使用2個粒子群按照不同的策略進(jìn)行搜索。第一個粒子群中增加上一層空間求得的最優(yōu)解作為本次求解的約束條件，即由上一層粒子分解而得的各粒子負(fù)載之和不能超出上一層粒子獲得的最優(yōu)分配值。第二個粒子群則不增加約束條件進(jìn)行搜索。當(dāng)2個粒子群分別完成最優(yōu)化搜索之后，比較其最優(yōu)解。如果不加約束條件的粒子群獲得的解更優(yōu)，則將該解合成為上一層空間的最優(yōu)解，重復(fù)步驟5)，跳轉(zhuǎn)到上一層空間重新搜索。如果加了約束條件的粒子群獲得的解更優(yōu)，則該最優(yōu)解為本層粒子的最優(yōu)解。查看本層是否有更細(xì)粒度的空間，如果有繼續(xù)5)，跳轉(zhuǎn)到下一層空間進(jìn)行搜索，否則轉(zhuǎn)到6)。

6) 此時已完成最細(xì)一層商空間，得到原始網(wǎng)絡(luò)空間的資源分配流量矩陣λQoSm。系統(tǒng)根據(jù)最優(yōu)值定義的請求流量矩陣調(diào)度各級QoS業(yè)務(wù)請求流量。

3.2.3 算法實(shí)例

下面結(jié)合一個例子來闡述算法過程，給出如圖2所示的層次化網(wǎng)絡(luò)。網(wǎng)絡(luò)共有15個節(jié)點(diǎn)，為了便于描述，網(wǎng)絡(luò)采用樹狀結(jié)構(gòu)。

圖2 商空間構(gòu)建過程

原始網(wǎng)絡(luò)中所有節(jié)點(diǎn)全體G1作為初始商空間，節(jié)點(diǎn)集記為V1。

首先使用等價類R(2)對原始空間進(jìn)行劃分，得到商空間G2，其商集V2如下。

這樣原始空間劃分成包含3個元素的粗粒度網(wǎng)絡(luò)圖，其邊集合為

(V2,E2)構(gòu)成商空間G2，其拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 G2商空間拓?fù)浣Y(jié)構(gòu)

其流量分配矩陣為

接下來，使用等價類R(3)對G2進(jìn)行劃分，得到商空間G3，其商集V3如下。

其流量分配矩陣為

同樣，使用 2個粒子群算法求得G3空間中的最優(yōu)解，第一個粒子群需要滿足G2空間已經(jīng)求得的最優(yōu)解的約束條件，即

最后，使用等價類R(4)對G3進(jìn)行劃分，得到最細(xì)粒度的商空間G4，其商集V4如下

由于該空間等同于原始問題空間，其求得最優(yōu)解就是原問題的最優(yōu)解。

3.3 算法分析

3.3.1 命題證明

命題 1對于層次式數(shù)據(jù)網(wǎng)格采用基于等價關(guān)系構(gòu)建的分層遞階商空間鏈，可以求得原始問題的最優(yōu)解。

證明對于原始網(wǎng)絡(luò)，商集[X]中的元素就是各個節(jié)點(diǎn)，商結(jié)構(gòu)[T]是原始網(wǎng)絡(luò)拓?fù)洌僭O(shè)商空間鏈有L層。原始問題存在最優(yōu)解，即在分層遞階商空間鏈中，最細(xì)粒度的空間([XL], [TL])存在最優(yōu)解。采用等價關(guān)系R(L-1)對其進(jìn)行劃分，得到上一層商空間([XL-1], [TL-1])，根據(jù)商空間的保真原理可知該空間中必包含原始問題的最優(yōu)解。反復(fù)應(yīng)用商空間保真原理可得最粗粒度商空間([X2], [T2])存在最優(yōu)解。由此可得原始空間最優(yōu)解必包含在各級空間的最優(yōu)解中，因此基于分層遞階商空間鏈逐層搜索可以求得原始問題的最優(yōu)解。

命題 2在分層遞階商空間中求解的過程，是一個逐步逼近最優(yōu)解的過程。

證明采用反證法。假設(shè)在某一粒度的空間([XL], [TL])中，求得一個當(dāng)前最優(yōu)解，在該粒度空間最優(yōu)解的約束下，更細(xì)粒度的下級空間([XL+1],[TL+1])可以得到一個更優(yōu)解。假設(shè)該解不是最優(yōu)解，說明超出上級空間約束還有最優(yōu)解，將該最優(yōu)解的分量相加，由保真原理得到上級空間解就比之前求得的最優(yōu)解更優(yōu)，與之前的解是最優(yōu)解的假設(shè)矛盾。

由此命題可以得出，如果要求出全局最優(yōu)解，那么每一層的解都必須是當(dāng)前層內(nèi)的全局最優(yōu)解。故此在算法中采用了雙粒子群，一個粒子群基于約束條件搜索，另一個粒子群不受約束搜索，這樣可以充分保證解空間的完備性。

3.3.2 收斂性分析

分析 QSHDGRA算法收斂性需要用到 Solis的隨機(jī)優(yōu)化算法以概率1收斂于全局最優(yōu)解的充分條件。

命題3假設(shè)QSHDGRA求解的目標(biāo)函數(shù)f是可測函數(shù)，其解空間S為可測集，那么，QSHDGRA算法以概率1收斂于全局最優(yōu)解。

證明由Solis收斂定理知，只需證明QSHDGRA滿足Solis收斂假設(shè)1和假設(shè)2即可。

1) QSHDGRA算法中商空間由粗到細(xì)的搜索過程是一個對搜索空間逐步壓縮的過程，每一層搜索的最優(yōu)值逐步逼近全局最優(yōu)值。迭代函數(shù)f可歸結(jié)為

其中，t為進(jìn)化代數(shù)，算法的解序列為可以保證其趨向最優(yōu)值，因而容易證明其滿足Solis收斂假設(shè)1。

2) 設(shè)各個粒度網(wǎng)絡(luò)中最優(yōu)解的樣本空間的并必包含S，即其中Mi,t為第t代粒子i的樣本空間支撐集。QSHDGRA算法在每一層空間采用2個粒子群進(jìn)行搜索，第一個粒子群保證搜索空間的收斂，第二個粒子群將保證種群多樣性，隨機(jī)搜索空間而不進(jìn)行收斂，設(shè)第一個粒子群支撐集的并集為α，第二個粒子群支撐集的并集為β。由于第二個粒子群搜索的隨機(jī)性，必然存在整數(shù)t1，使得當(dāng)t>t1時，β?S。因此，對于QSHDGRA算法，存在整數(shù)t2，使得t>t2時的任意 Borel子集A=Mi,t，則有v(A)>0，所以QSHDGRA算法滿足Solis收斂假設(shè)2。

綜合1)和2)，由Solis收斂定理可得QSHDGRA算法是一個全局收斂算法，能以概率1全局收斂。

3.3.3 復(fù)雜度分析

粒子群算法的收斂速度與其解空間規(guī)模相關(guān)，給定網(wǎng)絡(luò)G(V,E)，節(jié)點(diǎn)數(shù)量為n，解空間維度為m=n(n-1)，則收斂的時間復(fù)雜度為O(sm)，其中s為解向量中每一維度的取值范圍。基于等價關(guān)系商空間模型構(gòu)建L層分層遞階的商空間鏈G1＞G2＞…＞GL。設(shè)在商空間Gk中，解空間維度為mk，算法收斂的時間復(fù)雜度為，則整個算法的時間復(fù)雜度為在算法求解過程中，雖然解空間維度逐步增大，即m1＜m2＜…mL，但由于搜索空間不斷減小，每一維度的取值范圍也逐步減小，即s1＞s2＞…sL，因此最優(yōu)情況下，算法能夠以幾何速度收斂。

4 仿真實(shí)驗(yàn)與分析

4.1 仿真環(huán)境與實(shí)驗(yàn)方法

仿真實(shí)驗(yàn)采用GridSim仿真軟件。仿真網(wǎng)絡(luò)拓?fù)淙鐖D2所示：一級節(jié)點(diǎn)，即根節(jié)點(diǎn)1個；二級節(jié)點(diǎn)2個，采用100 Mbit/s專線和一級節(jié)點(diǎn)鏈接；三級節(jié)點(diǎn)4個，采用50 Mbit/s專線連接到所屬的二級節(jié)點(diǎn)；四級節(jié)點(diǎn)8個，采用10 Mbit/s專線連接到所屬的三級節(jié)點(diǎn)。各節(jié)點(diǎn)內(nèi)部網(wǎng)絡(luò)是1 000 Mbit/s網(wǎng)絡(luò)，各節(jié)點(diǎn)之間均采用虛鏈路實(shí)現(xiàn)路由連通。仿真文件大小為 1～5 MB之間的隨機(jī)值，系統(tǒng)共產(chǎn)生1 000個文件，按層次關(guān)系分布到各個節(jié)點(diǎn)中。系統(tǒng)采樣單位時間為 5 min，即300 s，系統(tǒng)請求率為每單位時間生成的請求數(shù)，節(jié)點(diǎn)處理能力的單位為每單位時間處理的事務(wù)數(shù)，四級節(jié)點(diǎn)的最大處理能力分別為300、200、120和80。

實(shí)驗(yàn)包含4個部分：首先分析了不同QoS參數(shù)對不同QoS服務(wù)吞吐率和響應(yīng)時間的影響；其次分析了全局均衡參數(shù)對系統(tǒng)整體性能的影響；接著分析了算法在不同種群數(shù)量、迭代次數(shù)和網(wǎng)絡(luò)規(guī)模下的收斂速度；最后將本文的 QSHDGRA算法和MinTime最小時間算法、Random算法的性能進(jìn)行了橫向比較。

4.2 不同QoS級別性能分析

首先比較不同 QoS參數(shù)對不同級別業(yè)務(wù)的吞吐率和平均響應(yīng)時間的影響。對式(9)中的均衡參數(shù)δ和ε取零，分別考察α:β:γ為1:1:1，5:3:2和 6:3:1 3種情況下性能差別。

從圖4和圖5中可以看出，隨著系統(tǒng)請求率由400增大到2 000，服務(wù)響應(yīng)率也相應(yīng)地由400增加到1 370。當(dāng)系統(tǒng)請求率小于800時，系統(tǒng)處于輕載，所有的請求基本都能夠及時響應(yīng)，不同QoS參數(shù)比下的3種業(yè)務(wù)的吞吐率大致相同，平均等待時間也大致相等。當(dāng)系統(tǒng)請求率增大到1 200時，系統(tǒng)負(fù)載加大，不同QoS參數(shù)比下的3種業(yè)務(wù)吞吐率出現(xiàn)明顯差異。當(dāng)α:β:γ=1:1:1時，3種業(yè)務(wù)的吞吐率仍然保持大致相當(dāng)，但當(dāng)α:β:γ=5:3:2 和α:β:γ=6:3:1時中，3種業(yè)務(wù)的吞吐率依次減少，業(yè)務(wù)平均等待時間依次增加。當(dāng)系統(tǒng)請求率大于1 600時，已經(jīng)接近系統(tǒng)的滿載負(fù)荷，第一種參數(shù)比下 3種業(yè)務(wù)吞吐率仍然近似相等，而后2種參數(shù)比下的吞吐率大致比例為5:3:2和6:3:1，且第二、三類業(yè)務(wù)的響應(yīng)時間明顯大于第一類業(yè)務(wù)。由此可見，QSHDGRA 算法通過調(diào)節(jié)參數(shù)α:β:γ可以控制不同優(yōu)先級業(yè)務(wù)的流量，從而保障高優(yōu)先級業(yè)務(wù)的吞吐率和相應(yīng)時間約束。

4.3 全局均衡性能分析

圖4 不同QoS參數(shù)比時各級別業(yè)務(wù)吞吐率比較

圖5 不同QoS參數(shù)比時各級別業(yè)務(wù)平均等待時間比較

本節(jié)分析全局均衡參數(shù)對系統(tǒng)性能的影響，即式(9)中的均衡參數(shù)δ和ε對系統(tǒng)吞吐率和平均等待時間的影響，公式中α:β:γ取固定值5:3:2。

從圖6(a)中可以看出，隨著系統(tǒng)請求率逐步增大，使用均衡參數(shù)比不使用均衡參數(shù)可以獲得更高的響應(yīng)率，即使在系統(tǒng)重載時，仍可以進(jìn)一步提升響應(yīng)率。從圖6(b)中可以看出，在系統(tǒng)輕載時，兩者的平均響應(yīng)時間大致相當(dāng)，當(dāng)系統(tǒng)重載時，使用均衡參數(shù)時平均響應(yīng)時間會略大，這是由于平均響應(yīng)時間在目標(biāo)函數(shù)中的比例已經(jīng)降低，系統(tǒng)向著全局吞吐率更大的目標(biāo)進(jìn)行優(yōu)化。

圖6 使用和不使用均衡參數(shù)下吞吐率和平均等待時間的比較

圖7顯示了使用均衡參數(shù)和不使用均衡參數(shù)時各節(jié)點(diǎn)服務(wù)響應(yīng)率的差別。此時系統(tǒng)請求率為1 200，處于輕載狀態(tài)。從圖中可以看出，使用均衡參數(shù)和不使用均衡參數(shù)相比，各級節(jié)點(diǎn)的負(fù)載更加平均。由此可見，全局均衡參數(shù)可以很好地平衡各個節(jié)點(diǎn)的工作負(fù)載，有效避免某些節(jié)點(diǎn)處于繁忙狀態(tài)，而另一些節(jié)點(diǎn)處于空閑狀態(tài)，從而進(jìn)一步提升系統(tǒng)整體的吞吐率。

圖7 使用和不使用均衡參數(shù)下各節(jié)點(diǎn)服務(wù)響應(yīng)率比較

4.4 算法收斂速度分析

本節(jié)分析 QSHDGRA算法和不使用商空間的PSO算法在不同種群數(shù)量、迭代次數(shù)和網(wǎng)絡(luò)規(guī)模對算法收斂速度的差別。

從圖 8(a)中可以看出，粒子群的種群數(shù)量由20增大到100時，QSHDGRA算法的收斂速度快于PSO算法，不過當(dāng)種群數(shù)量大于60后，速度減少的幅度也相應(yīng)減小。在圖8(b)中，當(dāng)?shù)螖?shù)由200增加到1 000時，QSHDGRA算法比PSO算法得到的適應(yīng)值更優(yōu)，且可以更快地收斂到最優(yōu)值。綜合圖 8(a)和 8(b)可得，種群數(shù)量為 60，迭代次數(shù)為600時，系統(tǒng)可以在可接受的時間內(nèi)獲得近似的最優(yōu)值。圖8(c)顯示了網(wǎng)絡(luò)規(guī)模擴(kuò)大時，算法計算時間的變化。當(dāng)網(wǎng)絡(luò)規(guī)模由15個節(jié)點(diǎn)增大到255個節(jié)點(diǎn)時，QSHDGRA算法的計算時間近似為PSO算法的一半，這是因?yàn)镼SHDGRA算法可以利用商空間迅速收斂到最優(yōu)值，因此計算時間可以保持近似線性增長。

4.5 與其他算法比較分析

將本文的QSHDGRA算法和MinTime最小時間算法、Random算法的性能進(jìn)行比較。MinTime最小時間算法在搜索副本節(jié)點(diǎn)時僅僅以最快完成時間為目標(biāo)，Random算法則是隨機(jī)從副本節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)獲取數(shù)據(jù)。從圖9(a)和圖9(b)中可以看出，當(dāng)請求率在 800以下時，系統(tǒng)處于輕載，3種算法的效率差別并不顯著，QSHDGRA算法的吞吐率略優(yōu)于其他2種算法。隨著請求率增大到1 200時，3種算法效率出現(xiàn)明顯差別，MinTime算法最差，QSHDGRA算法最優(yōu)，而Random算法位于兩者之間。此時由于系統(tǒng)尚未滿載，三者的平均等待時間差別仍然近似相當(dāng)。當(dāng)請求率達(dá)到2 000時，系統(tǒng)處于重載時，QSHDGRA和其他2種算法的差別進(jìn)一步拉大。Random算法之所以優(yōu)于MinTime算法是因?yàn)殡S機(jī)選擇進(jìn)度可以在一定程度上對實(shí)現(xiàn)節(jié)點(diǎn)的負(fù)載均衡，而QSHDGRA算法由于兼顧了系統(tǒng)整體節(jié)點(diǎn)處理能力和網(wǎng)絡(luò)能力的均衡性，雖然響應(yīng)時間略大于其他2種算法，但吞吐率也顯著優(yōu)于其他2種算法。

圖8 不同種群數(shù)量、迭代次數(shù)和網(wǎng)絡(luò)規(guī)模下算法收斂速度比較

圖9 QSHDGRA算法與其他算法性能比較

5 結(jié)束語

本文針對傳統(tǒng)數(shù)據(jù)網(wǎng)格調(diào)度算法在對層次式數(shù)據(jù)網(wǎng)格調(diào)度時出現(xiàn)的難以得到全局最優(yōu)值和收斂速度過慢問題，提出了一種基于商空間的層次式數(shù)據(jù)網(wǎng)格資源調(diào)度算法。定義了基于不同QoS業(yè)務(wù)請求的平均等待時間和網(wǎng)絡(luò)與節(jié)點(diǎn)資源利用均衡度的調(diào)和模型的目標(biāo)函數(shù)，實(shí)現(xiàn)了基于商空間的層次式最優(yōu)資源調(diào)度算法。仿真結(jié)果表明，該算法可以顯著提升系統(tǒng)的吞吐率，加快收斂速度，并具備線性擴(kuò)展能力。本文提出的算法雖然具備分布式調(diào)度的特性，但仍然屬于一種全局控制算法。當(dāng)全局調(diào)度節(jié)點(diǎn)不可用時，各節(jié)點(diǎn)如何分布協(xié)同實(shí)現(xiàn)資源調(diào)度將是下一步主要的研究方向。

[1] ZHANG J G, ZHANG K, YAN Y Y,et al.Grid-based implementation of XDS-I as part of image-enabled EHR for regional healthcare in Shanghai [J].International Journal of Computer Assisted Radiology and Surgery, 2011, 6(2):273-284.

[2] JBoss enterprise data Grid[EB/OL].http://www.jboss.com/edg6-earlyaccess/, 2012.

[3] CHENG K Y, WANG H H, WEN C H,et al.Dynamic file replica location and selection strategy in data grids[A].Proceedings of the 1st IEEE International Conference on Ubi-Media Computing and Workshops[C].Lanzhou, China, 2008.484-489.

[4] AL-MISTARIHI H H E, YONG C H.On fairness, optimizing replica selection in data grids[J].IEEE Transactions on Parallel and Distributed Systems, 2009, 20(8):1102-1111.

[5] DU W, CUI G H, LIU W.Reliability-aware replica selection for data-intensive applications on data grids[J].Information an International Interdisciplinary Journal, 2011, 14(12):3913-3920.

[6] QU M C, WU X H, LIAO M H,et al.A novel resource selection model for data grid based on QoS[J].New Trends and Applications of Computer-Aided Material and Engineering, 2011, 186:203-209.

[7] TANG B, ZHANG L.Optimal replica selection algorithm in data grid[J].Theoretical and Mathematical Foundations of Computer Science, 2011, 164:297-304.

[8] RAHMAN R M, BARKER K, ALHAJJ R.A predictive technique for replica selection in grid environment[A].Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid[C].Rio de Janeiro, Brazil, 2007.163-170.

[9] NASEERA S, MADHU MURTHY K V.Performance evaluation of predictive replica selection using neural network approaches[A].Proceedings of 2009 International Conference on Intelligent Agent and Multi-Agent Systems[C].Chennai, India, 2009.

[10] RAHMAN R M, ALHAJJ R, BARKER K.Replica selection strategies in data grid[J].Journal of Parallel and Distributed Computing,2008,68(12):1561-1574.

[11] ALMUTTAIRI R M, WANKAR R, NEGI A,et al.Replica selection in data grids using preconditioning of decision attributes by K-means clustering (K-RSDG)[A].Proceedings of the 2nd Vaagdevi International Conference on Information Technology for Real World Problems[C].Warangal, India, 2010.18-23.

[12] LI J.A replica selection approach based on prediction in data grid[A].Proceedings of the 3rd International Conference on Semantics,Knowledge, and Grid[C].Xi'an, China, 2007.274-277.

[13] WU C, Wu K G, CHEN M,et al.Dynamic replica selection services based on state evaluation strategy[A].Proceedings of the 4th ChinaGrid Annual Conference[C].Yantai, China, 2009.116-119.

[14] MUNOZ V M, VICENTE G A, CARBALLEIRA F G,et al.Emergent algorithms for replica location and selection in data grid[J].Future Generation Computer Systems-the International Journal of Grid Computing-Theory Methods and Applications, 2010, 26(7):934-946.

[15] XIONG R Q, LUO J Z, SONG A B,et al.QoS preference-aware replica selection strategy using mapreduce-based PGA in data grids[A].Proceedings of the 40th International Conference on Parallel Processing[C].2011.394-403.

[16] WANG X, DING S F.An overview of quotient space theory[J].Sports Materials, Modelling and Simulation, 2011, 187:326-331.