動態網格下的資源發現算法

摘要：提出了一種網格環境下動態資源的表示方法——矩陣表示法，同時研究了矩陣表示法下的資源查找和更新算法，該算法充分考慮了資源屬性的動態性。由于矩陣計算不用操作資源的原始數據，從而提高了查找的效率，不僅能夠進行精確匹配的查詢也能進行范圍查詢。在路由查詢時，只要參考本地信息就可給出準確的路由選擇。矩陣表示資源還簡化了動態資源的更新過程，使資源信息能夠及時接近真實的網格環境。

關鍵詞： 網格; 對等網; 動態資源

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1361-03

查找與應用程序匹配的資源是網格系統的一個基本問題。為了運行網格應用程序，必須給應用程序分配滿足一定條件的可用資源。目前網格系統中基本采用集中式的資源發現方法[1，2]，但集中式的資源發現方法不具有擴展性，服務器容易成為網絡的瓶頸，容易發生單點失效的問題。Peer－to－peer(P2P)系統是一種較好的分布式系統，具有很好的可擴展性，已有大量研究[3，4]表明P2P系統能夠很好地支持動態網格環境下的資源發現。本文假設網格項目的一個虛擬組織(virtual organization，VO)以具有超級節點的P2P網絡方式管理，由類似超級節點的作業管理系統(workload manage system，WMS)[5]負責管理分布式資源的索引信息。WMS擁有這些資源的詳細信息，同時負責為用戶選擇相匹配的資源。最近的研究表明網格和P2P在資源發現領域的協同發展是可行的[4]。但現在流行的P2P系統中處理的一般都是靜態資源，采用的查詢技術主要是基于靜態信息的精確查詢。算法中認為這些資源很長時間才可能改變，而且主要通過某些關鍵字進行精確查找。目前的網格系統也假設網格虛擬組織是一個靜態實體，但事實上，虛擬組織中的資源是動態的。因為網格中的用戶請求的資源具有隨時間變化的特點(如CPU利用率、剩余磁盤空間等)，并需要針對資源特征進行范圍查詢(如查找內存大于512 MB的資源)。下一代的網格應該向動態性方向發展，應能夠解決網格中資源信息的動態變化，且支持一定的范圍查詢和基于屬性的查詢。P2P算法需要經過一定的修改才能夠直接用于網格中的動態資源查找。文獻[5]中提出用位圖來表示資源，解決了網格環境下動態資源的表示以及查詢和資源更新。然而位圖不能很好地表示資源的多個屬性值，查詢和更新時需要對每個屬性的位圖進行操作，因此實現時較繁瑣，不容易達到預期目標。

基于以上問題，本文提出一種新的網格資源表示方法，使用矩陣來表示資源，依據資源的屬性建立一個二維空間，使得坐標空間把資源空間分成不同的區域，每個區域利用矩陣中的一個元素來表示。采用矩陣來表示資源意味著用簡化的信息來代替原始信息， 使查詢中的匹配過程得到了簡化，從而提高了效率。本文還提出了基于這種資源表示下的資源發現和更新算法。該算法考慮了資源屬性值具有隨時間不斷變化的特點，根據資源屬性進行精確查詢和范圍查詢。 每個節點可以根據存儲的鄰居節點的簡略信息，只作少量計算就可以做出準確的路由選擇，大大減少了網絡的負擔。

1動態資源發現模型結構

假設網格系統由n個資源組成{R1， R2，…，Rn}，可以分為多個互不相交的子集合，每個子集合由一個不同的WMS控制著。每個資源用一個屬性來描述，這樣可以把滿足某種要求的屬性作為查詢條件來查找自己需要的資源。每個屬性有相應的屬性值，用A[R]表示資源R的屬性A的值。在實際網格開發中主要需要兩種資源，即計算資源(computing element，CE)和存儲資源(storage element，SE)。每個CE可能包含以下屬性[6]:CPU的速度(CPU speed)、CPU的數目(CPU num)、內存大小(RAM size)、最近10 min等待的作業平均數目(waitingjobs)、最近10 min CE的利用率(utilization)等。每個SE可能包含以下屬性：SE的總存儲量(capacity)、可利用磁盤空間(free space)等。

用戶運行作業需要定位和得到資源。對于一個給定的作業，用戶需要查詢系統中滿足特定條件的一個或多個資源。例如，一個查詢條件Q= {R|R∈{R1， R2，…， RN}， CPU speed≥2．0 GHz，RAM size≥512 MB，utilization10≤0．3}。其中：Q表示查找一個計算資源，要求該資源的CPU速度至少是2．0 GHz，內存至少512 MB，最近10 min內作業的利用率最多0．3。

為了能高效地查找網格中與查詢條件匹配的資源，本文提出了如下的資源表示方法。首先考慮資源R有兩個屬性A和C的情況，屬性A的值A[R]的取值為[a， b]，屬性C的值C[R]的取值為[c， d]，那么這類資源可以用坐標表示。其中：橫軸代表屬性A；縱軸代表屬性C。在屬性A的域中選擇a1，a2，…，ai共i個關鍵點，使得a=a0＜a1＜…＜ai-1＜ai=b；C的域內選擇c1，c2，…，cj共j個關鍵點，使得c=c0＜c1＜…＜cj-1＜cj=d，這樣就可以確定i×j個小區間。每個資源必然屬于其中的一個區域，如圖1所示。

這樣可以采用一個j×i的矩陣來表示一個資源或查詢條件，也可以用來表示資源的集合。例如，如果某個資源屬性A[R]∈[a2，a3]，C[R]∈[c3，c4]，那么用如下矩陣M(R)(稱為資源矩陣)來表示該資源:

如果要確定某個資源R是否滿足查詢M(Q)時，只需檢查M(R)∧M(Q)是否為0。如果M(R)∧M(Q)= 0，表示資源R不能滿足查詢Q；如果M(R)∧M(Q)≠0，則表示資源R滿足查詢Q。

對于一個資源集合，也可以利用資源集合中每個資源對應的資源矩陣合取來表示該資源集合所擁有的資源。同理，可以用這個資源集合對應的資源矩陣合取某個查詢矩陣來確定資源集合中是否有滿足該查詢的資源。如果合取矩陣的結果為0，表示該資源集合中沒有滿足查詢的資源；如果結果不為0則表示該資源集中有滿足查詢的資源。

采用矩陣來表示資源，就是用簡化的信息來代替原始信息。在查找過程中直接進行矩陣運算就可以確定某資源是否滿足查詢要求和資源集合是否存在滿足查詢要求的資源。由于無須對原始數據進行操作，能極大地提高查詢響應速度。

假設所有的WMS組成一個無向圖的網狀覆蓋網絡，每個WMS中的W存儲有自己所直接控制的資源詳細信息，并存儲有鄰居節點上資源的簡略信息。用Nb(W)來表示網絡上與W直接相連的鄰居節點的集合。對于W的每個鄰居節點W′，用MW(W′)表示W′及其鄰居節點(不包含W)上的所有資源矩陣的析取所得的矩陣，根據上文有

這樣，在查詢過程中，如果查詢W′及其鄰居節點中是否有所需要的資源，只需檢查MW(W′)∧M(Q)是否為0。若結果為0則無須訪問W′，從而減輕了網絡負擔，提高了查找效率。

上面所描述的是對于由兩個屬性來確定資源矩陣的方法，當資源由m個屬性來確定時，可以用橫軸上資源的m個屬性，縱軸上資源的(m-1)個屬性來確定資源矩陣，每個屬性根據自己的范圍和特點來選擇自己的關鍵點。

圖2表示了橫軸的m個屬性A1，A2，…，Am與縱軸上的A2，…，Am屬性劃分的資源空間，每兩個屬性可以如圖1那樣確定一個資源。為了避免屬性區間的重復考慮，圖2只需用一個類似上(下)三角的分塊矩陣表示即可。如果屬性多的話矩陣的階數會比較高，但是由于元素非0即1，并不會影響查詢效率;同時又是一個稀疏矩陣，只要使用特殊的存儲方法，并不會占用大量存儲空間。

2動態資源發現

2．1查詢過程

筆者認為資源檢索是一個范圍查詢，用戶提出的查詢都是尋求屬性值在一個給定范圍內的資源。一個用戶提交自己的查詢要求M(Q)給一個WMS后，WMS查詢自己所管理的資源中是否滿足查詢要求的資源，并搜集網絡上其他節點返回的應答。某個資源R是否滿足查詢條件Q通過計算M(R)∧M(Q)來決定。如果M(R)∧M(Q)=0表示資源R不能滿足查詢條件Q；如果M(R)∧M(Q)≠0表示資源R滿足查詢條件的要求。是否把查詢條件發送給鄰居節點W′的條件通過計算M(Q)∧MW(W′)來決定。如果M(Q)∧MW(W′)=0表示該鄰居節點上沒有滿足查詢要求的資源，則不發送給該節點;如果M(Q)∧MW(W′)≠0表示該節點有滿足要求的資源，則將查詢要求發送給該節點。

整個查詢過程描述如下:

當W接收到網絡中鄰居節點發來的查詢請求時，W查詢自己所管理的資源中是否有滿足查詢要求的資源。如果有滿足要求的資源，返回一個查詢成功的信息。查詢過程中采用類似于廣度優先搜索算法，每個WMS在查詢自己管理范圍內資源的同時，并向鄰居節點發出查詢要求。為了防止查詢條件Q廣播到整個網絡，查詢Q只發送給存在滿足查詢條件資源的鄰居節點，而不是廣播給所有鄰居節點。這種方法與有指導的廣度優先遍歷有些相似[7]，但是本文中并不依賴于歷史查詢的統計數據。因為本文考慮的資源屬性值是動態變化的，系統的統計信息并不能提供準確的信息。

下面給出算法1，主要描述查詢是如何在圖中路由，以及每個WMS是如何處理查詢請求的。

算法1W處理查詢的過程

本文提出的查詢算法中，只用通過計算MW(W′)∧M(Q)就可以知道鄰居節點W′中是否有滿足查詢的資源，從而只把查詢請求提交給滿足查詢要求的鄰居節點，即當MW(W′)∧M(Q)≠0時才把查詢請求發送給W′，不需要查詢鄰居節點就可以給出準確的路由選擇。這就保證了查詢請求僅發送給所有滿足條件的節點。這樣既減少了網絡的負擔，同時也提高了查詢效率。

2．2資源矩陣的更新

對于某種資源，它的某些屬性值是固定的，但有些屬性值可能隨時發生變化。在現實中，屬性值的變化是有限的，如任意兩個連續變化的值之間的變化范圍很小。當資源R的屬性值發生變化時，控制資源R的W首先需要計算資源更新后的資源矩陣。如果更新后的資源矩陣等于原來的矩陣則不需要更新，如果新計算的資源矩陣與原來的資源矩陣發生了變化則需要執行更新，并把更新的信息發送給所有鄰居節點。如果R′是資源R更新后的結果，是否需要更新取決于M(R)∧M(R′)的結果。如果M(R)∧M(R′)=0表示該資源需要更新；如果M(R)∧M(R′)≠0則該資源不需要更新。控制資源R的W通過執行算法2來進行更新。

3模擬實驗與分析

利用Java語言對網格的資源發現算法進行了模擬實驗。為了實驗方便，假設網格系統中有七個WMS，每個WMS中均含有四個資源節點。為了對比分析，同時實現了P2P泛洪資源發現算法。

資源發現過程中涉及的節點數和邊數是資源發現性能評價的兩個重要參數。在實驗中利用Java隨機函數生成兩個隨機數作為網格資源模擬系統和P2P模擬系統資源請求節點及資源節點，記錄發現過程中涉及的節點數和邊數。這樣反復實驗20次，以模擬實驗結果的平均值作為最后實驗結果。

資源發現模擬系統與P2P模擬系統平均涉及節點數的比較如圖3所示。新的網格資源發現模擬系統與P2P泛洪發現算法模擬系統涉及邊數的比較如圖4所示。

通過圖3和4可以看出，新的查找算法在查找過程中無論涉及的節點數和邊數都比泛洪算法有所降低，因此整個系統的效率將大大提高。

4結束語

本文提出了一種網格環境下動態資源的新的表示方法、資源發現以及資源更新算法。考慮到動態資源實際情況中有些屬性值是連續變化、有些是非連續的特點，用資源矩陣來表示資源，使得矩陣計算代替了原始數據的操作，提高了查詢效率。當需要對查詢作路由選擇時，根據本節點存儲的鄰居節點的簡略信息就可以進行準確的路由選擇，減少了網絡的負擔。在更新資源信息時，當資源屬性值在某個范圍之內變化時不需要更新，資源屬性值變化超出了某個范圍才產生更新信息來更新資源矩陣。這樣簡化了資源的變化模型，提高了更新的效率，比周期性地更新資源更能接近資源的實際情況。本文提出的算法不僅能夠滿足基于屬性的精確查詢，還能適應動態資源的范圍查詢。

參考文獻：

[1]RIPEANU M， BOWMAN M， CHASE J S. Globus and planetLab resource management solutions compared[C]//Proc of the 13th IEEE International Symposium on High Performance Distributed Computing. 2004:246-255.

[2]ZOU Hong－bo， JIN Hai， HAN Zong－fen. A virtual－service－domain based bidding algorithm for resource discovery in computational grid[C]//Proc of IEEE/WIC/ACM International Conference on Web Intelligence. 2005:50-53.

[3]RISSON J， MOORS T. Survey of research towards robust peer－to－peer networks search， UNSW－EE－P2P－1－1[R]. Sydney: University of New South Wales， 2004.

[4]TALIA D， TRUNFLO P. Toward a synergy between P2P and grids[J]. IEEE Internet Computing， 2003，7(4):94-95.

[5]MARZOLLA M， MORDACCHINI M， ORLANDO S. Resource discovery in a dynamic grid environment[C]//Proc of the 16th International Workshop on Database and Expert Systems Applications. 2005:356-360.

[6]GONG Yi－li， LI Wei， SUN Yu－zhong. A C/S and P2P hybrid resource discovery framework in grid environments[C]//Proc of International Conference on Parallel Processing. 2005:261-268.

[7]YANG B， GARCIA－MOLINA H. Improving search in peer－to－peer networks[C]//Proc of the 22nd Int Conference on Distributed Computing Systems(ICDCS’02).[S.l.]: IEEE Computer Society， 2002.

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