摘要：由于每次查找資源都必須先訪問網格信息中心，在獲得資源和節點的對應關系之后再去訪問資源所在的節點進行確認，這就會形成性能瓶頸和單點崩潰的問題。分布式查找算法通過資源管理系統之間各自的相互作用，來決定哪個資源適合作業執行。
1相關工作
1.1網格資源查找方法在Globus中主要采用的兩種查找算法是集中式查找和分布式查找算法[2]。集中式查找，即以統一的策略管理位于一個或多個域中的資源，整個網格系統擁有一個全局的網格信息中心，該信息中心存儲著所有資源節點的位置信息和資源與資源節點的對應關系。然而，由于此算法在起點處不知道所要查找資源和資源所在節點的對應關系，所以只能依次查找每個節點來判斷資源所在的位置，最壞情況下可能需要訪問完所有的節點后才會查找到所需的資源，其時間復雜度和對網絡帶寬造成的影響都不能容忍。所以，在網格系統中，如何進行高效的查詢處理，減小網絡消耗，仍是資源發現急需解決的問題。
1.2 P2P技術
P2P是一種實現資源共享的分布式技術，與網格在動態性和異構性方面具有相同的特點。P2P系統中的參與者既是資源提供者，又是資源獲取者。這是一種新的獲取信息的方式，用戶的電腦既是客戶端，又是服務器。這是一個徹底\"去中心化\"的檔案交換架構。P2P技術的特征之一就是弱化服務器的作用，甚至取消服務器，P2P將導致信息數量、成本資源都向網絡中各節點均勻分布，而且交互性、即時性好，符合一對一的特點。P2P技術最大好處就是解決了客戶機/服務器C/S(Client/Server)結構中由于終端節點的不斷增加而產生的帶寬瓶頸問題，而在P2P的分布式網絡中每個節點都是資源提供者，從一定程度上來說，節點越多則速度越快[3，4]。基于P2P的這些特性，本文引入了P2P系統的分散資源發現思想，以提高發現方法的開放性。
2資源發現方法描述
2.1資源表示資源表示是所有資源發現服務的重要組成部分，資源發現的過程就是用戶提交的請求與資源表示實例之間的匹配過程。在網格環境中為了提高資源發現的效率，需要對資源的表示方式進行精心設計。因此，用資源ID，資源類型ClassID以及資源關鍵字Key三個數據項表示資源。利用分布式哈希表DHT將網格資源節點按其提供服務的類型分類，用ClassID標志資源的類型，不同類的資源信息間不存在聚類和比較，將同類資源的不同屬性或狀態映射為Key、ClassID，每個資源表示為ClassID+Key的1個映射。查找的請求(request)也映射為ClassID+Key。其數據結構形式如下。
Typedef struct resourse
{Int resourse ID;//全局惟一的資源ID號Int ClassID;//資源類型Int Key;//資源關鍵字}3.2基于類型的資源組織為了更有效的提高資源發現的效率，設計了一個基于區域的網絡結構，如圖1所示。
在圖1中，網格系統被劃分為許多可供搜索的區域，每個區域由一個域中心節點CN(Center Node)和若干簡單節點SN(SimpleNode)組成，它們之間有著各種連接關系。
2.3 DHT傳播策略
DHT系統消除了集中式的索引服務器，查找又具有很高的效率，在一定程度上解決了系統規模和查找效率的矛盾，在P2P系統中，其不足之處是查詢完全基于結點ID精確匹配，因此很難支持模糊和較為靈活的查詢。在本文的資源發現體系結構中，基于資源分類的組織形式使P2P層等同于以\"資源類型\"這一唯一屬性維系的P2P網絡，而該層次上的傳播查找沒有模糊查詢的需求，僅需要針對資源類型進行匹配，本文基于Chord這一比較成熟的DHT方法來實現P2P層的傳播策略。每個CN節點都有一個m位的標識，該標識由哈希函數SHA-1對節點的資源類型值哈希轉換得到，將標識對2m取模后順序排列，各節點都被映射到一個大小為2m的環狀邏輯空間中。如圖2所示。每個節點除了維護其前驅和后繼節點之外，還需維護一個指針表(finger table)。指針表中最多含有m個表項，節點n的指針表中第i項是圓環上標識大于或等于n+2i-1的第一個節點。圖3給出了節點3的指針表。
2.4基于資源區域的網格資源發現算法基于上述資源表示以及資源域的劃分，本文在區域之間引入DHT的傳播策略進行資源查找，采用集中式資源查找算法在區域內查找與請求相匹配的最佳資源。該方法基于以下假設[6]。
假設1：對于每一個網格資源，都有唯一的網格資源類型。
假設2：結點覆蓋拓撲在一次資源發現過程或一次資源信息更新過程中的變化可以忽略不計，且資源信息在一次資源發現過程中保持有效和穩定。
假設1中，假設一個網格資源只有唯一的類型是為了表述的方便。在該假設下，同時具有多種類型的資源被視為多個類型唯一的不同資源。相對于整個拓撲的演化過程而言，一次資源發現或信息更新的時間是非常短的，假設2的意義在于簡化了資源發現的描述與建模，為比較不同的資源發現方法提供了一個共同的基礎。
2.4.1算法描述
基于資源區域的劃分和假設，提出基于資源區域的網格資源發現算法GRDARR(GridResource Dicovery Algorithm Based on Re-source Region)，算法描述如下：Input:查找請求request.
Output:最佳資源.
Begin(1)向網格系統發送要查找的資源請求;(2)根據資源表示確定資源ClassID;(3)SHA-1對ClassID進行哈希轉換;(4)根據DHT傳播策略進行查找匹配，得到在P2P層上符合請求要求的CN節點;(5)檢查CN節點的自身負載情況;(6)if(負載情況符合)(7){根據集中式查找方法對區域內的資源進行匹配查找;將符合條件的最佳資源的信息返回給用戶;}(8)else將請求轉發給同類資源的其它CN節點;(9)重復(5);End3.4.2算法時間復雜度分析假設資源類型數為nt，資源區域內資源個數為nv，資源返回數為k，(1)用戶請求在域間查找資源時，最壞的情況下用戶請求遍歷環狀邏輯空間中的所有節點，請求與P2P層節點比較的次數為nt。(2)用戶請求在域內查找資源時，當域內的所有資源滿足資源請求時，比較次數為nv，所以算法的時間復雜度為O(nt+nv)。
2.4.3算法實例
根據GRDARR算法描述，本文通過實例來說明資源的查找算法。
如圖4是一個m=4的環，環中分布著6個節點，環中存儲了3個關鍵字，即校園網格被劃分為3個具有相同類型的資源區域，用戶請求資源類型為T，關鍵字為K，
