摘要：由于每次查找資源都必須先訪問網(wǎng)格信息中心，在獲得資源和節(jié)點的對應(yīng)關(guān)系之后再去訪問資源所在的節(jié)點進行確認，這就會形成性能瓶頸和單點崩潰的問題。分布式查找算法通過資源管理系統(tǒng)之間各自的相互作用，來決定哪個資源適合作業(yè)執(zhí)行。

　　1相關(guān)工作

　　1.1網(wǎng)格資源查找方法在Globus中主要采用的兩種查找算法是集中式查找和分布式查找算法[2]。集中式查找，即以統(tǒng)一的策略管理位于一個或多個域中的資源，整個網(wǎng)格系統(tǒng)擁有一個全局的網(wǎng)格信息中心，該信息中心存儲著所有資源節(jié)點的位置信息和資源與資源節(jié)點的對應(yīng)關(guān)系。然而，由于此算法在起點處不知道所要查找資源和資源所在節(jié)點的對應(yīng)關(guān)系，所以只能依次查找每個節(jié)點來判斷資源所在的位置，最壞情況下可能需要訪問完所有的節(jié)點后才會查找到所需的資源，其時間復(fù)雜度和對網(wǎng)絡(luò)帶寬造成的影響都不能容忍。所以，在網(wǎng)格系統(tǒng)中，如何進行高效的查詢處理，減小網(wǎng)絡(luò)消耗，仍是資源發(fā)現(xiàn)急需解決的問題。

　　1.2 P2P技術(shù)

　　P2P是一種實現(xiàn)資源共享的分布式技術(shù)，與網(wǎng)格在動態(tài)性和異構(gòu)性方面具有相同的特點。P2P系統(tǒng)中的參與者既是資源提供者，又是資源獲取者。這是一種新的獲取信息的方式，用戶的電腦既是客戶端，又是服務(wù)器。這是一個徹底\"去中心化\"的檔案交換架構(gòu)。P2P技術(shù)的特征之一就是弱化服務(wù)器的作用，甚至取消服務(wù)器，P2P將導(dǎo)致信息數(shù)量、成本資源都向網(wǎng)絡(luò)中各節(jié)點均勻分布，而且交互性、即時性好，符合一對一的特點。P2P技術(shù)最大好處就是解決了客戶機/服務(wù)器C/S(Client/Server)結(jié)構(gòu)中由于終端節(jié)點的不斷增加而產(chǎn)生的帶寬瓶頸問題，而在P2P的分布式網(wǎng)絡(luò)中每個節(jié)點都是資源提供者，從一定程度上來說，節(jié)點越多則速度越快[3，4]?；赑2P的這些特性，本文引入了P2P系統(tǒng)的分散資源發(fā)現(xiàn)思想，以提高發(fā)現(xiàn)方法的開放性。

　　2資源發(fā)現(xiàn)方法描述

　　2.1資源表示資源表示是所有資源發(fā)現(xiàn)服務(wù)的重要組成部分，資源發(fā)現(xiàn)的過程就是用戶提交的請求與資源表示實例之間的匹配過程。在網(wǎng)格環(huán)境中為了提高資源發(fā)現(xiàn)的效率，需要對資源的表示方式進行精心設(shè)計。因此，用資源ID，資源類型ClassID以及資源關(guān)鍵字Key三個數(shù)據(jù)項表示資源。利用分布式哈希表DHT將網(wǎng)格資源節(jié)點按其提供服務(wù)的類型分類，用ClassID標志資源的類型，不同類的資源信息間不存在聚類和比較，將同類資源的不同屬性或狀態(tài)映射為Key、ClassID，每個資源表示為ClassID+Key的1個映射。查找的請求(request)也映射為ClassID+Key。其數(shù)據(jù)結(jié)構(gòu)形式如下。

　　Typedef struct resourse

　　{Int resourse ID;//全局惟一的資源ID號Int ClassID;//資源類型Int Key;//資源關(guān)鍵字}3.2基于類型的資源組織為了更有效的提高資源發(fā)現(xiàn)的效率，設(shè)計了一個基于區(qū)域的網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。

　　在圖1中，網(wǎng)格系統(tǒng)被劃分為許多可供搜索的區(qū)域，每個區(qū)域由一個域中心節(jié)點CN(Center Node)和若干簡單節(jié)點SN(SimpleNode)組成，它們之間有著各種連接關(guān)系。

　　2.3 DHT傳播策略

　　DHT系統(tǒng)消除了集中式的索引服務(wù)器，查找又具有很高的效率，在一定程度上解決了系統(tǒng)規(guī)模和查找效率的矛盾，在P2P系統(tǒng)中，其不足之處是查詢完全基于結(jié)點ID精確匹配，因此很難支持模糊和較為靈活的查詢。在本文的資源發(fā)現(xiàn)體系結(jié)構(gòu)中，基于資源分類的組織形式使P2P層等同于以\"資源類型\"這一唯一屬性維系的P2P網(wǎng)絡(luò)，而該層次上的傳播查找沒有模糊查詢的需求，僅需要針對資源類型進行匹配，本文基于Chord這一比較成熟的DHT方法來實現(xiàn)P2P層的傳播策略。每個CN節(jié)點都有一個m位的標識，該標識由哈希函數(shù)SHA-1對節(jié)點的資源類型值哈希轉(zhuǎn)換得到，將標識對2m取模后順序排列，各節(jié)點都被映射到一個大小為2m的環(huán)狀邏輯空間中。如圖2所示。每個節(jié)點除了維護其前驅(qū)和后繼節(jié)點之外，還需維護一個指針表(finger table)。指針表中最多含有m個表項，節(jié)點n的指針表中第i項是圓環(huán)上標識大于或等于n+2i-1的第一個節(jié)點。圖3給出了節(jié)點3的指針表。

　　2.4基于資源區(qū)域的網(wǎng)格資源發(fā)現(xiàn)算法基于上述資源表示以及資源域的劃分，本文在區(qū)域之間引入DHT的傳播策略進行資源查找，采用集中式資源查找算法在區(qū)域內(nèi)查找與請求相匹配的最佳資源。該方法基于以下假設(shè)[6]。

　　假設(shè)1：對于每一個網(wǎng)格資源，都有唯一的網(wǎng)格資源類型。

　　假設(shè)2：結(jié)點覆蓋拓撲在一次資源發(fā)現(xiàn)過程或一次資源信息更新過程中的變化可以忽略不計，且資源信息在一次資源發(fā)現(xiàn)過程中保持有效和穩(wěn)定。

　　假設(shè)1中，假設(shè)一個網(wǎng)格資源只有唯一的類型是為了表述的方便。在該假設(shè)下，同時具有多種類型的資源被視為多個類型唯一的不同資源。相對于整個拓撲的演化過程而言，一次資源發(fā)現(xiàn)或信息更新的時間是非常短的，假設(shè)2的意義在于簡化了資源發(fā)現(xiàn)的描述與建模，為比較不同的資源發(fā)現(xiàn)方法提供了一個共同的基礎(chǔ)。

　　2.4.1算法描述

　　基于資源區(qū)域的劃分和假設(shè)，提出基于資源區(qū)域的網(wǎng)格資源發(fā)現(xiàn)算法GRDARR(GridResource Dicovery Algorithm Based on Re-source Region)，算法描述如下：Input:查找請求request.

　　Output:最佳資源.

　　Begin(1)向網(wǎng)格系統(tǒng)發(fā)送要查找的資源請求;(2)根據(jù)資源表示確定資源ClassID;(3)SHA-1對ClassID進行哈希轉(zhuǎn)換;(4)根據(jù)DHT傳播策略進行查找匹配，得到在P2P層上符合請求要求的CN節(jié)點;(5)檢查CN節(jié)點的自身負載情況;(6)if(負載情況符合)(7){根據(jù)集中式查找方法對區(qū)域內(nèi)的資源進行匹配查找;將符合條件的最佳資源的信息返回給用戶;}(8)else將請求轉(zhuǎn)發(fā)給同類資源的其它CN節(jié)點;(9)重復(fù)(5);End3.4.2算法時間復(fù)雜度分析假設(shè)資源類型數(shù)為nt，資源區(qū)域內(nèi)資源個數(shù)為nv，資源返回數(shù)為k，(1)用戶請求在域間查找資源時，最壞的情況下用戶請求遍歷環(huán)狀邏輯空間中的所有節(jié)點，請求與P2P層節(jié)點比較的次數(shù)為nt。(2)用戶請求在域內(nèi)查找資源時，當(dāng)域內(nèi)的所有資源滿足資源請求時，比較次數(shù)為nv，所以算法的時間復(fù)雜度為O(nt+nv)。

　　2.4.3算法實例

　　根據(jù)GRDARR算法描述，本文通過實例來說明資源的查找算法。

　　如圖4是一個m=4的環(huán)，環(huán)中分布著6個節(jié)點，環(huán)中存儲了3個關(guān)鍵字，即校園網(wǎng)格被劃分為3個具有相同類型的資源區(qū)域，用戶請求資源類型為T，關(guān)鍵字為K，