夏純中，宋順林

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

1 引言

近年來，數(shù)據(jù)網(wǎng)格憑借其強大的擴展能力被用于構(gòu)建企業(yè)級數(shù)據(jù)庫云平臺。例如，大型醫(yī)療集團信息集成平臺[1]利用數(shù)據(jù)網(wǎng)格對集團內(nèi)各醫(yī)療機構(gòu)分布異構(gòu)的醫(yī)療信息數(shù)據(jù)庫進行集成和共享；紅帽發(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)出社團性和層次性，即特定區(qū)域內(nèi)的用戶只對特定部分的數(shù)據(jù)最感興趣，而層次式數(shù)據(jù)網(wǎng)格可以很好滿足這一需求。

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

粒計算是一種通過對復(fù)雜問題進行?；纸?，從而降低問題復(fù)雜度的方法論，它是模擬人類在解決復(fù)雜問題時能夠由粗至細，多層次地觀察和分析問題的能力。張鈴和張鈸提出使用商空間理論對粒度空間進行描述。商空間理論通過保真原理和保假原理在論域元素上構(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)流量進行調(diào)度，保障不同優(yōu)先級業(yè)務(wù)的QoS的需求，此外調(diào)度算法還兼顧了數(shù)據(jù)網(wǎng)格整體節(jié)點負載和網(wǎng)絡(luò)流量的均衡，實現(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é)點組成一個層次化的樹狀網(wǎng)絡(luò)，根節(jié)點擁有全部數(shù)據(jù)副本，根節(jié)點將所有數(shù)據(jù)副本平均分配到各個二級節(jié)點，二級節(jié)點再將數(shù)據(jù)副本平均分配到下屬的三級節(jié)點。一級節(jié)點定期監(jiān)控各節(jié)點和各條鏈路的負載情況，采用特定算法分配各個節(jié)點的處理帶寬的能力，實現(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)先級最低，當系統(tǒng)繁忙時，可以暫停響應(yīng)。

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

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

2.2 問題形式化定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1 構(gòu)建商空間

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

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

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

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)度目標值Z(λ)最小。

算法步驟描述如下。

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

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

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

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

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

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

3.2.3 算法實例

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

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

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

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

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

(V2,E2)構(gòu)成商空間G2，其拓撲結(jié)構(gòu)如圖3所示。

圖3 G2商空間拓撲結(jié)構(gòu)

其流量分配矩陣為

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

其流量分配矩陣為

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

最后，使用等價類R(4)對G3進行劃分，得到最細粒度的商空間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é)點，商結(jié)構(gòu)[T]是原始網(wǎng)絡(luò)拓撲，假設(shè)商空間鏈有L層。原始問題存在最優(yōu)解，即在分層遞階商空間鏈中，最細粒度的空間([XL], [TL])存在最優(yōu)解。采用等價關(guān)系R(L-1)對其進行劃分，得到上一層商空間([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])中，求得一個當前最優(yōu)解，在該粒度空間最優(yōu)解的約束下，更細粒度的下級空間([XL+1],[TL+1])可以得到一個更優(yōu)解。假設(shè)該解不是最優(yōu)解，說明超出上級空間約束還有最優(yōu)解，將該最優(yōu)解的分量相加，由保真原理得到上級空間解就比之前求得的最優(yōu)解更優(yōu)，與之前的解是最優(yōu)解的假設(shè)矛盾。

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

3.3.2 收斂性分析

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

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

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

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

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

2) 設(shè)各個粒度網(wǎng)絡(luò)中最優(yōu)解的樣本空間的并必包含S，即其中Mi,t為第t代粒子i的樣本空間支撐集。QSHDGRA算法在每一層空間采用2個粒子群進行搜索，第一個粒子群保證搜索空間的收斂，第二個粒子群將保證種群多樣性，隨機搜索空間而不進行收斂，設(shè)第一個粒子群支撐集的并集為α，第二個粒子群支撐集的并集為β。由于第二個粒子群搜索的隨機性，必然存在整數(shù)t1，使得當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é)點數(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 仿真實驗與分析

4.1 仿真環(huán)境與實驗方法

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

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

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。當系統(tǒng)請求率小于800時，系統(tǒng)處于輕載，所有的請求基本都能夠及時響應(yīng)，不同QoS參數(shù)比下的3種業(yè)務(wù)的吞吐率大致相同，平均等待時間也大致相等。當系統(tǒng)請求率增大到1 200時，系統(tǒng)負載加大，不同QoS參數(shù)比下的3種業(yè)務(wù)吞吐率出現(xiàn)明顯差異。當α:β:γ=1:1:1時，3種業(yè)務(wù)的吞吐率仍然保持大致相當，但當α:β:γ=5:3:2 和α:β:γ=6:3:1時中，3種業(yè)務(wù)的吞吐率依次減少，業(yè)務(wù)平均等待時間依次增加。當系統(tǒng)請求率大于1 600時，已經(jīng)接近系統(tǒng)的滿載負荷，第一種參數(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)重載時，仍可以進一步提升響應(yīng)率。從圖6(b)中可以看出，在系統(tǒng)輕載時，兩者的平均響應(yīng)時間大致相當，當系統(tǒng)重載時，使用均衡參數(shù)時平均響應(yīng)時間會略大，這是由于平均響應(yīng)時間在目標函數(shù)中的比例已經(jīng)降低，系統(tǒng)向著全局吞吐率更大的目標進行優(yōu)化。

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

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

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

4.4 算法收斂速度分析

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

從圖 8(a)中可以看出，粒子群的種群數(shù)量由20增大到100時，QSHDGRA算法的收斂速度快于PSO算法，不過當種群數(shù)量大于60后，速度減少的幅度也相應(yīng)減小。在圖8(b)中，當?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ī)模擴大時，算法計算時間的變化。當網(wǎng)絡(luò)規(guī)模由15個節(jié)點增大到255個節(jié)點時，QSHDGRA算法的計算時間近似為PSO算法的一半，這是因為QSHDGRA算法可以利用商空間迅速收斂到最優(yōu)值，因此計算時間可以保持近似線性增長。

4.5 與其他算法比較分析

將本文的QSHDGRA算法和MinTime最小時間算法、Random算法的性能進行比較。MinTime最小時間算法在搜索副本節(jié)點時僅僅以最快完成時間為目標，Random算法則是隨機從副本節(jié)點中選擇一個節(jié)點獲取數(shù)據(jù)。從圖9(a)和圖9(b)中可以看出，當請求率在 800以下時，系統(tǒng)處于輕載，3種算法的效率差別并不顯著，QSHDGRA算法的吞吐率略優(yōu)于其他2種算法。隨著請求率增大到1 200時，3種算法效率出現(xiàn)明顯差別，MinTime算法最差，QSHDGRA算法最優(yōu)，而Random算法位于兩者之間。此時由于系統(tǒng)尚未滿載，三者的平均等待時間差別仍然近似相當。當請求率達到2 000時，系統(tǒng)處于重載時，QSHDGRA和其他2種算法的差別進一步拉大。Random算法之所以優(yōu)于MinTime算法是因為隨機選擇進度可以在一定程度上對實現(xiàn)節(jié)點的負載均衡，而QSHDGRA算法由于兼顧了系統(tǒng)整體節(jié)點處理能力和網(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ào)和模型的目標函數(shù)，實現(xiàn)了基于商空間的層次式最優(yōu)資源調(diào)度算法。仿真結(jié)果表明，該算法可以顯著提升系統(tǒng)的吞吐率，加快收斂速度，并具備線性擴展能力。本文提出的算法雖然具備分布式調(diào)度的特性，但仍然屬于一種全局控制算法。當全局調(diào)度節(jié)點不可用時，各節(jié)點如何分布協(xié)同實現(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.