基于超市模型的網(wǎng)格資源分配方法研究

摘要:針對網(wǎng)格資源管理中的資源分配問題，提出了一種基于超市模型的網(wǎng)格資源管理分配方法#65377;該方法能夠實現(xiàn)子資源的快速匹配，從而減少了網(wǎng)格管理開銷，更高效地分配了稀缺資源#65377;

關鍵詞:超市模型;信息超市;信譽度;資源匹配

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2007)10-0079-03

0引言

網(wǎng)格[1]作為一個集成的計算與資源環(huán)境，能夠吸收各種計算資源，將它們轉換成一種隨處可得的#65380;可靠的#65380;標準的且相對經(jīng)濟的計算能力#65377;其吸收的計算資源包括各種類型的計算機#65380;網(wǎng)絡通信能力#65380;數(shù)據(jù)資料#65380;儀器設備甚至有操作能力的人等各種相關資源#65377;網(wǎng)格資源管理與分配是網(wǎng)格計算中需要解決的關鍵問題#65377;從本質上說，大規(guī)模的網(wǎng)格具有分布性#65380;異構性#65380;自治性#65380;動態(tài)性的特點，而且網(wǎng)格的整體與部分之間存在一定的自相似性#65377;不用考慮地理位置不同所帶來的影響，網(wǎng)格可以高效地提供近乎于無限的計算能力#65380;存儲能力，還可以訪問各種工具器械#65380;可視化設備等各種資源#65377;因此，如何對網(wǎng)格資源進行合理的描述#65380;科學的組織和管理分配顯得尤為重要#65377;

網(wǎng)格計算還沒有正式的標準，但Globus Toolkit[2]已成為網(wǎng)格計算事實上的標準#65377;目前所有重大的網(wǎng)格項目都是基于Globus Tookit提供的協(xié)議與服務建設的#65377;開放網(wǎng)格服務結構OGSA是Global Grid Forum4的重要標準建議，被稱為是下一代的網(wǎng)格結構#65377;OGSA的目的就是要將grid的一些功能融合到Web service這個框架中#65377;OGSA是面向服務的結構，將所有事務(計算資源#65380;存儲資源#65380;網(wǎng)絡#65380;程序#65380;數(shù)據(jù)等)均表示成一個grid服務，且每個網(wǎng)格服務都具有標準的接口，屏蔽了網(wǎng)格服務的具體實現(xiàn)細節(jié)，因而對用戶是透明的#65377;環(huán)境中的所有組件都是虛擬化的，通過提供一個所有grid服務實現(xiàn)基礎的一致接口的核心集，可以使分級的#65380;更高級別的服務構建能夠跨多個抽象層，以一種統(tǒng)一的方式進行處理#65377;虛擬化還促使從多個邏輯資源實例到同一物理資源的映射，不考慮現(xiàn)實的服務組合以及一個VO內的基于低級資源組合的資源管理#65377;截至目前，網(wǎng)格資源經(jīng)濟模型的研究多限于價格機制對市場作用及網(wǎng)格資源的集中式搜索方面#65377;隨著網(wǎng)格計算的高速發(fā)展，迫切需要研究出一些新的更加適合網(wǎng)格體系結構的資源管理分配模型和算法#65377; 本文在已有的基于市場經(jīng)濟的網(wǎng)格資源管理模型[5]的基礎上，突出了促銷策略等因素在網(wǎng)格資源管理分配中的作用，能夠實現(xiàn)網(wǎng)格資源信息雙向傳遞，并構建了模型#65377;

1模型介紹

本文構建的模型與現(xiàn)實社會環(huán)境中超市的運營情況非常相似#65377;在市場經(jīng)濟環(huán)境中，資源消費者希望最小化費用，而資源所有者希望最大化投資回報#65377;模型抽象出三個實體，即資源消費者(用戶)#65380;資源提供者(公司)以及在用戶和公司之間起橋梁作用的資源(商品)交易市場——超市#65377;

在現(xiàn)實生活中，公司向超市提供商品，用戶從超市購買商品，超市負責從公司購買商品后賣給用戶并對銷售數(shù)據(jù)信息進行統(tǒng)計和分析，制訂促銷策略#65377;超市#65380;用戶#65380;公司三者之間存在著非常松散的耦合關系#65377;超市并不關心每個用戶的興趣愛好，而用戶也不用把自己的興趣告訴超市，超市完全靠對數(shù)據(jù)統(tǒng)計和分析為用戶提供更好的服務#65377;

在網(wǎng)格環(huán)境中，模型從上到下分為用戶層#65380;超市層和公司層，如圖1所示#65377;

1)用戶層

用戶層包括用戶和用戶代理兩部分#65377;用戶代理是網(wǎng)格資源消費者的軟件代理，支持不同的策略，能夠根據(jù)消費者的需求發(fā)現(xiàn)資源和調度應用，并且能夠管理所有與應用程序執(zhí)行有關的事務;接收用戶的資源請求，同時檢測能否在它所代理的用戶中找到#65377;信息查找的原則首先是在本地進行查詢，如果本地沒有該信息，系統(tǒng)自動到本地超市進行查詢#65377;網(wǎng)格探測器從網(wǎng)格資源超市獲取公司提供的資源目錄信息#65377;

2)超市層

超市層包括超市和信息服務代理兩部分#65377;超市是一個虛擬機構(一種在某些節(jié)點上運行的特殊服務)，超市中保存的是資源目錄信息稱為信息超市#65377;其中存放的信息主要是滿足本地用戶的需要#65377;超市負責對產品信息進行分類#65377;若本地用戶查詢的信息在本地超市不存在，則向其他超市發(fā)出請求，通過對其他超市的查詢得到商品信息，然后反饋給用戶#65377;超市為了獲得最大的效益，可根據(jù)自身得到的數(shù)據(jù)，對商品信息進行更新，根據(jù)市場策劃代理制訂的策略對商品進行促銷，即分析出目前系統(tǒng)中的稀缺資源，對它進行緩存，并將該資源發(fā)布到其他目錄節(jié)點上;同時，對中間節(jié)點的目錄進行適時更新#65377;信息服務代理主要負責動態(tài)收集公司的信息，并反映到全局數(shù)據(jù)庫中#65377;當有計算資源加入計算網(wǎng)格時，對應的銷售代理需向本管理域內的信息服務代理注冊;同樣，有計算資源退出計算網(wǎng)格時，需撤銷注冊#65377;用戶代理在獲得資源時需要向信息代理詢問當前資源的情況#65377;

按照網(wǎng)格資源類型對超市進行組織，將網(wǎng)格資源(服務)劃分為不同的部門，如計算部#65380;存儲部#65380;打印部#65380;程序部#65380;數(shù)據(jù)庫等#65377;在每個超市為每一個服務設置一個專門的部門，負責本類服務資源的調度#65377;超市及其下屬每個部門的業(yè)務按功能分為多個模塊#65377;模塊功能如下:

a)對外聯(lián)絡模塊，負責網(wǎng)格資源信息的發(fā)布，接收相關節(jié)點發(fā)送的目錄信息#65377;

b)內部業(yè)務處理模塊，負責管理信息，調用相關算法對公司的信譽度進行計算#65380;評價#65380;管理等#65377;

c)協(xié)調模塊，負責協(xié)調網(wǎng)格中超市及其部門之間的負載平衡，如圖2所示#65377;

這種自相似性組織結構方式，模塊功能明確，便于同部門內信息流通，提高了查找效率#65377;

3)公司層

公司層主要包括公司和銷售代理兩部分#65377;銷售代理是網(wǎng)格資源提供者的軟件代理，支持不同的策略，能夠根據(jù)公司的意愿發(fā)布資源，管理與接收應用程序執(zhí)行有關的事務#65377;首先公司為了最大化自身的收益，其商品不只存放在本地超市，而是根據(jù)市場需求將商品推銷到各地的超市#65377;生產者將信息放到超市后，可根據(jù)該信息帶來的收益決定是否將該信息放置在該超市，這樣可減少信息的冗余#65377;

事實上，本模型中的用戶和公司的地位是完全平等的，行為是完全一致的#65377;公司中的人員因需要購買商品而成為用戶，用戶也可以開公司，即在邏輯上被分為公司和用戶，在物理上可以是同一個節(jié)點(以下的敘述中節(jié)點均包括用戶和公司)#65377;可以認為網(wǎng)格環(huán)境中的所有節(jié)點由于具有統(tǒng)一的行為#65380;處于相同的地位，網(wǎng)格節(jié)點與節(jié)點之間是對等的(P2P結構)，節(jié)點間惟一的區(qū)別是提供相同資源能力和服務種類不同#65377;這種拓撲結構可以在有效的集中式搜索模式和自治性之間達到一種平衡;同時，也可以利用P2P的分布式搜索技術實現(xiàn)網(wǎng)格負載均衡，避免了系統(tǒng)的瓶頸問題，從而提高系統(tǒng)的性能#65377;

2促銷策略在模型中的實現(xiàn)

信譽度是指對節(jié)點集中的某節(jié)點能完成被期待完成任務的信任程度，它是隨時間而動態(tài)改變的#65377;該節(jié)點的信任度是建立在它過去一段時間內的表現(xiàn)的基礎上#65377;給每個節(jié)點定義一個信譽度，用來表示該節(jié)點提供的資源可靠程度#65377;信譽度值越大，資源越受歡迎#65377;每個節(jié)點均有以下幾個屬性:所有者#65380;可提供的資源種類及價格以及這種資源的信譽級別#65377;這些服務種類確定該節(jié)點的某一部分資源可以提供的服務功能，如存儲數(shù)據(jù)#65380;打印#65380;顯示等#65377;信譽代理在網(wǎng)格中負責更新信譽度列表，并根據(jù)信譽度計數(shù)器的值判斷是否添加#65380;刪除節(jié)點及節(jié)點屬性#65377;

在網(wǎng)格開始使用前，首先要對網(wǎng)格環(huán)境進行初始化，根據(jù)網(wǎng)格規(guī)模和地理位置人工部署中心節(jié)點，安裝并運行中心的系統(tǒng)軟件，使其成為中心節(jié)點(父中心)#65377;由于網(wǎng)格系統(tǒng)具有動態(tài)性，允許遠程節(jié)點自由加入和離開計算環(huán)境#65377;在以后的運行中，可以采用網(wǎng)格環(huán)境自動動態(tài)部署中心的方法來實現(xiàn)網(wǎng)格中心在整個網(wǎng)格環(huán)境中的合理部署#65377;

如果一個節(jié)點提供的資源下載次數(shù)較多，而且每次下載的速度#65380;可靠性等較高，則該節(jié)點的信譽度計數(shù)器值會相應地增加#65377;當累加到某一閾值時，就緩存該資源并把資源信息廣播到同部門的其他節(jié)點上#65377;同部門內搜索資源時，就很容易查找到，而不用逐級地搜索到父中心節(jié)點，同時可以選擇該節(jié)點為新的中心節(jié)點(子中心)，將系統(tǒng)軟件下載并安裝到該節(jié)點上#65377;當信譽度小于某一閾值時，子中心節(jié)點又被新的中心代替#65377;這樣，系統(tǒng)完全自治，信息在局部網(wǎng)格中雙向傳遞，減少信息在整個平臺中的查找時間，實現(xiàn)了資源的快速匹配#65377;這種做法類似于超市中的促銷策略，即不能只等待用戶去找需要的商品，適當?shù)臅r候可以開展一下促銷工作#65377;

4算法分析

本算法參考了文獻[3，4]的資源分配方法，發(fā)展了文獻[6]提出的基于信任度的網(wǎng)格計算資源分配算法，結合促銷的思想提出了適用于該模型的資源管理分配算法#65377;其基本思想比較簡單，查找局部最優(yōu)解，即根據(jù)一些信息找出隨機選擇的k個備選節(jié)點中信譽度最大#65380;消耗最小的節(jié)點進行促銷#65377;該算法引入信譽度概念，采用促銷策略避免了查找無關的節(jié)點;局部最優(yōu)解，總消耗相對較小;信譽度閾值檢查，使任務負載相對比較平衡;隨機選取k個節(jié)點，減少了算法執(zhí)行范圍;設定探測次數(shù)預定值，防止盲目循環(huán)，并使算法可根據(jù)系統(tǒng)變化實時響應任務#65377;

5結束語

本文采用基于促銷策略的超市模型，討論網(wǎng)格資源管理匹配和任務調度，提出了基于信譽度的資源促銷算法#65377;網(wǎng)格中采用了完全的節(jié)點自治管理，網(wǎng)格資源提供者不僅管理自己的局部資源，而且主動參與網(wǎng)格資源的匹配工作，當其信譽度達到一定級別后主動促銷，由被動地接收任務轉變成根據(jù)自身資源和負載情況主動決定是否參與執(zhí)行網(wǎng)格任務#65377;其實現(xiàn)了在最短的時間內找到所需的資源，減少了網(wǎng)格管理開銷，更高效地分配了稀缺資源，最大限度地挖掘了資源的潛在價值#65377;

參考文獻:

[1]FOSTER I， KESSELMAN C， TUECKE S. The anatomy of the grid:enabling scable virtual organizations[J].International Journal of Supercomputer Applications，2001，15(3):110.

[2]都志輝，陳渝，劉鵬.網(wǎng)格計算[M].北京:清華大學出版社，2002:56-58.

[3]HE Xiaoshan，SUN Xianhe，LASZEWSKI G von.QoS guided minmin heuristic for grid task scheduling[J].Comput Science Technology，2003，18(4):442-445.

[4]RANGANATHAN K，F(xiàn)OSTER I.Simulation studies of computation and data scheduling algorithms for data grids[J].Journal of Grid Computing，2003，1(1):25-28.

[5]曹鴻強，肖儂，盧錫城，等. 一種基于市場機制的計算網(wǎng)格資源分配方法[J].計算機研究與發(fā)展，2002，39(8):913-916.

[6]郭學理，楊慧，何鵬.一種基于信任度的網(wǎng)格計算資源分配模型[J].計算機應用研究

，2005，22(2):93-95.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”