張尚韜

（福建信息職業(yè)技術學院 計算機工程系，福建 福州 350003）

1　引言

網(wǎng)格技術就是為了實現(xiàn)不同地理位置的計算資源共享、信息資源共享、存儲資源共享、數(shù)據(jù)資源共享、專家資源共享、知識資源共享，而把互聯(lián)網(wǎng)整合成一臺巨大的超級計算機，網(wǎng)格概念的核心就是突破了以往強加在資源使用上的種種限制，使人們可以以一種全新的方式使用網(wǎng)格資源，解決更復雜的問題.而網(wǎng)格技術的這些不同于傳統(tǒng)網(wǎng)絡共享的優(yōu)點導致了網(wǎng)格的各種資源點具有很強的自主性、動態(tài)特征明顯、分布廣泛等特點.從這些網(wǎng)格資源的特點可以知道網(wǎng)格的資源管理機制必須要帶有新的特點和功能.即為了確保網(wǎng)格資源所有者的利益和整個環(huán)境的安全，必須要認真核對每個用戶的請求；通過提供給用戶統(tǒng)一的訪問接口，來隱藏網(wǎng)格資源的異構性；要為網(wǎng)格的用戶提供和保證服務質量，必須通過對網(wǎng)格資源動態(tài)性的屏蔽來實現(xiàn)；為了使資源能更好的為網(wǎng)格用戶服務，必須要遵守資源的策略和本地管理機制；因此，對網(wǎng)格資源的管理分配十分復雜，不能用傳統(tǒng)網(wǎng)絡的資源分配方式簡單解決.

2　基于集合競價的網(wǎng)格資源管理模型

Rajkumar Buyya提出了基于市場機制的網(wǎng)格資源分配基本體系結構GRACE（Grid Architecture for Computational Economy），該體系是基于計算經(jīng)濟方面最具有代表性的資源管理模型［1-5］.然而GRACE模型并不盡如人意，存在著很多缺陷，主要表現(xiàn)為三個問題：組件設計沒有與實際情況接軌、資源動態(tài)管理沒有與實際接軌、服務評價沒有與實際接軌.為了擴大資源交易的空間和資源交易的規(guī)模，并且能夠對大量的動態(tài)資源進行有效的管理，網(wǎng)格資源的管理就應該采用一些經(jīng)濟理論，比如采用發(fā)達的商品流通方式，又比如在資源交換時以商業(yè)為媒介.這樣資源代理就能充分的感受到網(wǎng)格資源的動態(tài)變化.網(wǎng)格資源的供應和需求，網(wǎng)格資源在資源市場的交易，以及網(wǎng)格資源的分配，都要通過“資源商人”來處理.經(jīng)過詳細的研究，我們發(fā)現(xiàn)網(wǎng)格資源種類繁多，資源所提供的信息量非常大，而且網(wǎng)格資源實時的在進行動態(tài)變化，這些特點有點類似于目前的證券交易市場，通過對證券市場的調(diào)查研究，我們將證券市場中常用到的集合競價原理引入到網(wǎng)格資源管理中來，提出一種基于集合競價的網(wǎng)格資源管理模型［6-14］CBGRM（Centralized Biding Grid Resource Management）模型.

2.1　模型構造

CBGRM模型主要由用戶，資源請求代理，資源提供代理，資源采購商，資源交易中心和網(wǎng)格銀行構成.其結構如圖1.1所示.

圖1　.1CBGRM模型

CBGRM模型各要件定義如下：

1）用戶（Grid User—GU）：表示網(wǎng)格中所加入的合法用戶，與現(xiàn)實的證券交易過程中的買入者相類似；

2）資源請求代理（Grid Resource Broke—GRB）：資源請求代理實際上包含了六個模塊的內(nèi)容，分別是：資源的查詢、資源價格的決策、資源等級的審定、代理的出價、日常調(diào)度和探測異常.與現(xiàn)實中的證券交易公司代理進行證券交易相類似；

3）資源提供代理（Grid Resource Provider Broker—GPB）：也類似于證券公司，包括資源信息發(fā)布、資源分配、服務信息統(tǒng)計和代理競價等模塊；

4）資源采購商（Grid Resource Collector—GRC）：該部分包括資源采購、資源信息、資源調(diào)度和異常探測等模塊；

5）資源交易中心（Grid Resource Trade Center—GTC）：類似于國家的滬、深證券交易所，實際上也是網(wǎng)格資源的交易中心，是資源交易市場的主體，組成的單元包括：集合競價成交交易單元、過程交易單元、結算單元和信息統(tǒng)計黨員.是過程交易和過程結算的場所，是虛擬化的；

6）網(wǎng)格銀行（Grid Bank—GB）：采用網(wǎng)格幣作為資源使用的支付方式，記錄提供者和全部網(wǎng)格中的用戶的財富，當然這是一種虛擬財富，與現(xiàn)實生活中的商業(yè)銀行相類似.

此模型的工作流程如圖1.2所示：

圖1　.2 CBGRM模型開作流程

1）用戶向資源請求代理提出資源使用申請，資源請求代理根據(jù)用戶作業(yè)的要求查詢資源信息目錄，尋找合適資源；

2）用戶等級審定

（1）若用戶具有優(yōu)先級，則其注冊屬性值PID=1；

（2）不具有優(yōu)先級的用戶PID=0；

（3）對本次免費提供資源的提供者，給予下一次使用資源時不需競價的優(yōu)先級PID=2.

3）價格決策

（1）PID=1 or 2的用戶，無須此步驟；

（2）PID=0的用戶需要向GRB輸入本次資源消費的預算要求，如時間限制，費用限制等，由價格決策單元根據(jù)價格決策算法得出用戶的最優(yōu)出價；

4）交易雙方參與集合競價，完成資源成交和結算

用戶和資源提供者分別通過GRB和GPB在資源交易中心參與集合競價，交易成交后，GPB根據(jù)交易價格，按用戶出價正比例分配資源；

5）異常探測處理

在任務的執(zhí)行過程中，GRB和GRC需要不停的探測任務執(zhí)行的情況，如發(fā)生突然中斷等情況立即采取應急措施，重新撮合交易，并將事件報告資源交易中心，記錄入資源使用信息統(tǒng)計目錄；

2.2　模型調(diào)度算法分析

首先定義模型中的參數(shù).

Bk：表示網(wǎng)格資源類型k接收到的用戶出價的總數(shù).

在這里，我們引入了柯布-道格拉斯效用函數(shù)，主要使用了其負數(shù)的形式.網(wǎng)格用戶的最主要目的是使作業(yè)的執(zhí)行時間和費用最小化.根據(jù)函數(shù)我們可以知道用戶效率的降低與費用和作業(yè)時間的升高成正比.依據(jù)柯布-道格拉斯效用函數(shù)的負數(shù)形式，我們推導出網(wǎng)格用戶效用的函數(shù)公式如（2.4）：

效用函數(shù)（2.4）的含義為：為了完成作業(yè)，在S秒內(nèi)，網(wǎng)格用戶花費了R個網(wǎng)格貨幣.

我們分兩種常見情況進行討論，第一種情況是，網(wǎng)格用戶在沒有時間限定的情況下，用限定的花費，盡可能快的完成作業(yè).第二種情況是，網(wǎng)格用戶在沒有花費限定的情況下，在限定的時間內(nèi)，花費盡可能少的完成作業(yè).在這兩種常見的情況下，假設服務提供者的底線是Eil，那么這兩種情況用戶的總出價必須高于Eil.

首先分析第一種情況，網(wǎng)格用戶在沒有時間限定的情況下，用限定的花費.也就是限定費用條件下的情況.則如果要使效用函數(shù)Ui得到最大值，也就是盡可能快的完成作業(yè)，那么公式可以表示為

總的來看，有兩個約束條件，第一個約束條件，所有K個任務被網(wǎng)格中的第i個網(wǎng)格用戶執(zhí)行，這個過程中產(chǎn)生的總費用，要比用戶的預算Ei??；第二個約束條件，假設服務提供者的底線是Eil，那么所有用戶任務的總出價必須高于Eil.

首先考慮第一個約束條件，則第i個用戶的第一個任務的最優(yōu)出價為

根據(jù)上面的步驟，我們也可以得到在網(wǎng)格中第k個任務的網(wǎng)格用戶i的最優(yōu)出價.

現(xiàn)在我們考慮第二個約束條件.如果需要所有用戶任務的總出價必須高于服務提供者的底線，則

則上述的計算結果是最優(yōu)的分配方法，如果

則表明用戶出價不能滿足資源提供者的利益，該出價作廢.Ui的最大化公式改為

則第i個用戶的第一個任務的最優(yōu)出價為：

其中，

同理可求得出針對類型k任務的出價bik.

再考慮時間限制條件下的情況.在該種情況下，

第i個用戶的第一個任務的最優(yōu)出價為：

其中，

根據(jù)上面的步驟，我們也可以得到在網(wǎng)格中第k個任務的網(wǎng)格用戶i的最優(yōu)出價.

現(xiàn)在我們考慮第二個約束條件.如果需要所有用戶任務的總出價必須高于服務提供者的底線

則上述的計算結果是最優(yōu)的分配方法，如果

則，由于前面已知Ui為凸函數(shù)，則Ui的最大化公式改為

出價函數(shù)如式2.10.

但是實際中并非所有用戶都愿意接受系統(tǒng)計算得出的最優(yōu)出價.可能存在某些用戶非常急于盡快完成任務，所以得到最優(yōu)出價后，愿意再提高出價，以高于最優(yōu)出價的價格成交，或者有些用戶不愿接受該最優(yōu)出價，想以更低的價格使用資源.

這里將針對用戶理性問題，利用進化博弈論的方法來構造網(wǎng)格資源分配中的出價策略，這個出價策略針對于有限理性用戶.為了使用戶出價策略達到均衡，提高用戶的理性程度，將引入動態(tài)學習的過程，而后調(diào)整策略.通過反復的博弈，實現(xiàn)網(wǎng)格資源的分配更合理，博弈過程與現(xiàn)實更加接近.

進化博弈理論強調(diào)動態(tài)調(diào)整的整個過程，這個過程也就是系統(tǒng)達到均衡的過程.均衡的路徑被均衡所依賴，也就是說系統(tǒng)的均衡是達到均衡過程的函數(shù).本文所采用的是單群體復制動態(tài)機制.

復制動態(tài)方程（replicateddynamicequation）表示為式（2.14）：

式中，xi表示個體在群體中所占比例，這個個體具體是指純戰(zhàn)略si是在時刻t時選擇的；dxi/dt表示xi隨時間變化的比例值；f( )si,x表示個體所得的期望效用，是群體中選擇純戰(zhàn)略si；f( )x,x表示群體中，群的平均期望效用，f( x ,x ) =∑xif(si,x).當復制動態(tài)方程式等于零的時候，這個位置就是均衡點，所以使用復制動態(tài)方程式可以得到進化博弈最終的均衡.

為了使研究的問題簡單化，我們把網(wǎng)格用戶用戶看成是兩個用戶群體，當然這里主要的網(wǎng)格用戶是指出價博弈的用戶，在博弈系統(tǒng)中網(wǎng)格用戶都是有限理性的一方.假設每個在出價博弈過程中的網(wǎng)格用戶，都有兩種選擇權利，即選擇最優(yōu)的出價戰(zhàn)略權利也稱為主導戰(zhàn)略或者不選擇最優(yōu)出價稱為變導戰(zhàn)略，這樣進行出價博弈的網(wǎng)格用戶，根據(jù)主導戰(zhàn)略出價和變導戰(zhàn)略出價得到的效用由式（2.15）計算.

其中Ri(bi)表示第i個出價用戶分配到的資源分額；Ei(Ri(bi))表示第i個用戶對資源的期望值.

從上可以構造出一個完整的博弈框架，該博弈框架可以表示成雙變量的矩陣，如表2.1所示.從表上可以看出，博弈中的網(wǎng)格用戶不管是在網(wǎng)格用戶1還是在網(wǎng)格用戶2得出的結果相同，主要是因為兩個博弈方從戰(zhàn)略角度和從利益角度看都是互為對稱關系.

表2.1中，出價B表示選擇最優(yōu)的出價戰(zhàn)略，而B/k表示不選擇最優(yōu)出價戰(zhàn)略.E（l/2）-B代表的是效用水平，當博弈過程中網(wǎng)格用戶均選擇最優(yōu)出價戰(zhàn)略時獲得的值.E（l/2）-B也是代表的是效用水平，當博弈過程中網(wǎng)格用戶不均選擇最優(yōu)出價戰(zhàn)略時獲得的值.E(k/(k+1))-B是表示選擇最優(yōu)出價戰(zhàn)略用戶遇到不均選擇最優(yōu)出價戰(zhàn)略用戶所獲得的效用水平.E(1/(k+1))-B/k是表示不選擇最優(yōu)出價戰(zhàn)略用戶遇到均選擇最優(yōu)出價戰(zhàn)略用戶所獲得的效用水平.

表2　.1 網(wǎng)格用戶出價策略效用矩陣

根據(jù)該矩陣計算出效用代人復制動態(tài)方程，令其等于零，可解出復制動態(tài)方程的穩(wěn)定點，即在復制動態(tài)過程中采用選擇最優(yōu)的出價策略B或不選擇最優(yōu)出價策略B/k的用戶比例x穩(wěn)定不變的水平.為了方便記憶，我們這里將選擇最優(yōu)的出價策略B統(tǒng)一稱為主導策略，將不選擇最優(yōu)出價的策略B/k統(tǒng)一稱為變異策略根據(jù)復制動態(tài)方程式，我們得以得出最多三個穩(wěn)定點，分別是：

x′=0.表示著用戶群體中的所有網(wǎng)格用戶都采用選擇最優(yōu)的出價策略B，也就是主導策略B.

x′=1.表示著用戶群體中的所有網(wǎng)格用戶都采用不選擇最優(yōu)的出價策略B/k，也就是異導策略B/k.

其中，

意味著網(wǎng)格用戶的出價博弈將有一個混合策略均衡.

1）當a＞0，a+b＜ 0時，得出b＜ 0；

即

表示采用變異策略的用戶占優(yōu)勢，則采用變異策略的用戶會越來越多，最終達到都采用變異策略B/k的穩(wěn)定狀態(tài).

2） 當a＜0，a+b＞ 0時，得出b＞ 0；

即

表示采用主導策略的用戶占優(yōu)勢，則采用主導策略的用戶會越來越多，最終達到都采用主導策略B的穩(wěn)定狀態(tài).

3　仿真分析

為了驗證CBGRM模型分配算法的有效性，我們將CBGRM模型的各個功能使用Gridsim平臺編碼實現(xiàn)，并在此模型上運行費用限制、時間限制調(diào)度策略，將之與傳統(tǒng)GRACE模型進行對比.

（1）費用限制條件下資源分配情況

圖3　.1 資源使用情況對比

可以得出結論，在CBGRM模型下，費用限制條件下調(diào)度結果是所有的任務數(shù)量計算能力都能與R2、R3、R4、R10相匹配.而R2、R3、R4、R10代表的是4個MIPS性價比最高的資源.這樣在CBGRM模型下，調(diào)度即滿足了機器的負載均衡，又滿足了網(wǎng)格用戶的QoS需求，而且還達到了預期的目標.反觀傳統(tǒng)的GRACE模型，很多計算能力比較弱的的資源，分配的任務數(shù)量反而更多.總的來看，雖然傳統(tǒng)的GRACE模型和新的CBGRM模型消費預算相同，但是新的CBGRM模型調(diào)度的結果更加合理，資源和計算能力能更好的匹配，與預期效果更接近.從用戶的QoS需求和任務執(zhí)行時間上來看，新的CBGRM模型也優(yōu)于傳統(tǒng)的GRACE模型.可見，新CBGRM模型的從資源管理和調(diào)度策略來看，比傳統(tǒng)的GRACE模型更先進.

（2）時間限制條件下資源分配情況

圖3　.2 資源使用情況對比

從圖3.2可以看到，在傳統(tǒng)的GRACE模型中，大部分的作業(yè)數(shù)量都集中在R1資源上運行，這造成了資源分配極大的不均衡.而從新的CBGRM模型來看，作業(yè)數(shù)量分布在R1到R10各個資源上運行，資源分配比較均衡.這表明CBGRM模型具有資源均衡分配，也就是負載均衡的能力，也再次看出，新的CBGRM模型資源調(diào)度算法的先進性和優(yōu)越性.

4　結語

本文設計了基于集合競價的網(wǎng)格資源管理模型，對模型的分配算法進行了詳細的分析，最后進行了CBGRM模型與GRACE模型的對比實驗.實驗證明，在價格限制和時間限制兩種資源調(diào)度需求下CBGRM模型都優(yōu)于GRACE模型.表明本文設計的網(wǎng)格資源管理模型調(diào)度策略是可行的，在提供用戶QoS服務、資源分配的負載均衡和費用預算等方面都優(yōu)于傳統(tǒng)的GRACE模型.