一種混合式網格資源發(fā)現(xiàn)模型

李琳娜，鐘冬望，王 芬

（武漢科技大學冶金工業(yè)過程系統(tǒng)科學湖北省重點實驗室，湖北武漢，430065）

網格作為一種分布式計算環(huán)境，目的在于利用互聯(lián)網把分散在不同地理位置的各種可用空閑資源整合起來，實現(xiàn)計算資源、存儲資源、數(shù)據(jù)資源、軟件資源、知識資源、專家資源等的全面共享，最終實現(xiàn)網絡虛擬環(huán)境中的資源共享和協(xié)同工作［1］。網格本質上是一個基礎設施，它允許位置無關的資源和服務獲取，這些資源和服務是由地理上分布的機器和網絡提供的。支持這種位置無關計算的一個基本操作就是資源發(fā)現(xiàn)，即如何有效地發(fā)現(xiàn)資源，為上層的資源調度、資源應用提供一個透明的全局資源視圖［2］。為了建立分布式、易擴展、性能好的資源發(fā)現(xiàn)機制，國內外學者已進行了相關的研究和探討［3－6］。何秀強等［5］通過借鑒P2P的思想，采用分布式資源發(fā)現(xiàn)方法解決了集中式發(fā)現(xiàn)機制中的系統(tǒng)瓶頸和查詢效率低的問題。但是，在網格環(huán)境下，如果采用完全分布式架構，由于資源數(shù)量巨大，資源請求消息擴散將會給網絡帶來很大負荷。這就要求進一步優(yōu)化分布式資源發(fā)現(xiàn)機制，混合式的資源發(fā)現(xiàn)機制應運而生。本文提出了一個改進的基于層次結構的混合式資源發(fā)現(xiàn)模型，并對其體系結構、資源信息共享方式及消息擴散機制進行說明和論證。

1 分層體系結構

混合式資源發(fā)現(xiàn)模型將傳統(tǒng)網格中所使用的集中式網絡拓撲結構與P2P網絡中的分布式網絡拓撲結構有機融合在一起，形成一種邏輯上分層、層間彼此邏輯獨立的資源查詢和消息擴散方式［7］。這種基于層次結構的模型將網格中的各種資源、服務及用戶組織成3個層次：最底層是各種資源、服務及用戶；上面一層是機構（IS），底層的資源、服務及用戶按其物理位置或管理策略分為不同機構；最上面一層是虛擬組織（VO），若干個機構根據(jù)它們所提供的資源和服務類型及屬性，加入具有相似屬性的VO。在這個層次結構模型中，同一個VO內的各個機構之間，以及各個VO之間，都是平坦的關系，它們通過網絡聯(lián)系在一起，如圖1所示。圖1中，SN為VO的超級節(jié)點。

圖1 基于層次結構的網格資源發(fā)現(xiàn)模型Fig.1 Resource discovery model based on layer

2 資源信息共享協(xié)議

由于網格中的資源、服務具有分布廣泛、動態(tài)變化的特點，為了保證查詢請求的成功率，必須正確維護成員結點的信息，并及時向外部擴散本地資源及服務信息，以使得網格中各個節(jié)點所掌握的異地信息及時得到更新。在混合式資源發(fā)現(xiàn)模型中，采用了一種兩層的信息共享協(xié)議：第一層是在同一VO內的覆蓋網絡上建立信息共享關系并進行信息擴散，交換彼此的資源及服務信息；第二層則是在網格內的所有VO之間構造的覆蓋網絡上建立信息共享關系并進行信息擴散，交換彼此的服務屬性信息。

2.1 虛擬組織內構建覆蓋網絡

循環(huán)移數(shù)結構覆蓋網絡構建方式的核心思想就是按照所有節(jié)點的統(tǒng)一編號，將與節(jié)點距離為2的整數(shù)冪的節(jié)點加為其鄰居節(jié)點，構建成循環(huán)移數(shù)結構的覆蓋網絡。在本模型中各虛擬組織內部就采用這種策略構造覆蓋網絡。為了在VO內構建這種循環(huán)移數(shù)結構的覆蓋網絡，設計了一個信息共享協(xié)議，在協(xié)議中有兩種類型的消息：neighbor消息和accept消息。消息的描述及算法如下：

（1）neighbor消息。一個機構加入VO時要在該VO的SN上注冊，由SN分配一個ID序號，將所有SN構成一個新環(huán)，然后從初始節(jié)點（ID＝0）開始的所有節(jié)點按順時針方向向與自身相隔為2的整數(shù)冪的節(jié)點發(fā)送neighbor消息。neighbor算法如下：

（2）accept消息。當一個節(jié)點收到neighbor消息時，則向對方發(fā)送accept消息，告知對方已接受它為鄰居，并將對方信息保存在本地。accept算法如下：

2.2 虛擬組織間構建覆蓋網絡

由于VO之間交換的消息主要是各個VO的資源屬性信息，而且各個VO的超級節(jié)點SN通常都是由性能較穩(wěn)定的節(jié)點擔當，所以考慮在VO之間構建的覆蓋網絡可以采用信息全共享策略。所有SN的資源屬性信息進行相互復制，各個SN節(jié)點上都存儲了所有SN節(jié)點的資源屬性信息。

3 消息擴散協(xié)議

為了實現(xiàn)資源信息節(jié)點之間的信息共享及資源請求消息在資源信息節(jié)點上的擴散，針對分層結構模型，采用了兩層消息擴散協(xié)議。將整個網絡中大規(guī)模的消息擴散劃分成以虛擬組織為邏輯單位的分區(qū)域消息擴散。在各個區(qū)域內部要想提高消息擴散的效率，必須設計出高效可靠的消息擴散算法。現(xiàn)有的消息擴散算法存在的主要問題是減少冗余消息和保證消息擴散可靠性之間的矛盾，如何解決這一矛盾是優(yōu)化消息擴散算法的關鍵。

3.1 問題描述

在討論算法之前，以循環(huán)移數(shù)結構覆蓋網絡為基礎做下面的假設：

假設1：覆蓋網絡的規(guī)模為N＝2n。

假設2：每個節(jié)點都有一個對應的ID。

假設3：每個節(jié)點只知道與其直接相連的鄰居節(jié)點的信息。

定義1：覆蓋網絡中節(jié)點v的度d（或鄰居數(shù)）是指此節(jié)點相連的鄰居節(jié)點個數(shù)。

定義2：消息從初始節(jié)點擴散到覆蓋網絡中的每一個節(jié)點的過程為一次消息擴散。

定義3：平均每節(jié)點在一次消息擴散中轉發(fā)消息的個數(shù)為消息擴散開銷f，

式中：mi為節(jié)點i轉發(fā)的消息個數(shù)；N為覆蓋網絡規(guī)模（節(jié)點個數(shù)）。

消息擴散若基于洪泛（flooding）機制，當節(jié)點收到消息時，如果該消息是第一次到達，則將消息轉發(fā)給其除消息來源以外的所有鄰居節(jié)點，系統(tǒng)中節(jié)點的平均鄰居數(shù)為k，則其消息擴散開銷為

式中：ki為節(jié)點i的度數(shù)，即鄰居數(shù)。

在規(guī)模為N＝2n的移數(shù)循環(huán)結構覆蓋網絡中，若采用洪泛機制，顯然ki＝2n－1，則其消息擴散開銷為

定義4：當節(jié)點收到消息后，再次收到相同的消息為冗余消息。

定義5：平均每個節(jié)點在一次消息擴散中收到的冗余消息個數(shù)為消息冗余傳輸開銷D。

對于循環(huán)移數(shù)結構覆蓋網絡，其消息冗余傳輸開銷為

下面給出一個在循環(huán)移數(shù)結構覆蓋網絡中使用洪泛算法的消息擴散過程實例。在圖2所示結構中，若以ID＝0節(jié)點為初始節(jié)點開始進行消息擴散，一次消息擴散過程需要輪轉發(fā)。

圖2 洪泛算法消息擴散過程示例Fig.2 Example of message expanding based on flooding algorithm

第一輪初始節(jié)點0向它的所有鄰居節(jié)點轉發(fā)消息：

第二輪節(jié)點1，2，4，6，7向其鄰居節(jié)點（除初始節(jié)點）轉發(fā)消息：

一次消息擴散過程中共產生25條消息，其中18條為冗余消息，其消息冗余傳輸開銷為2.3，即平均每個節(jié)點接收2個冗余消息。雖然在此結構中由于設置了合適的轉發(fā)跳數(shù)（在規(guī)模為N＝2n循環(huán)移數(shù)結構中，跳數(shù)為就可以覆蓋整個網絡），使得冗余消息傳輸開銷已經大大減少，但是仍然還存在消息冗余嚴重的現(xiàn)象。大量冗余消息的產生，來自盲目的洪泛，該算法中每輪的傳輸都只排除一個節(jié)點（消息來源節(jié)點）。如在第二輪中，1、2、4、6、7都是0的鄰居節(jié)點，所以它們之間相互轉發(fā)的消息都是冗余消息。

由上面的分析討論可知，現(xiàn)有的消息擴散算法的消息冗余傳輸開銷很大，占用了大量網絡帶寬，所以減少冗余消息的傳輸是改進消息擴散算法的關鍵問題。

3.2 M－flooding消息擴散算法

在循環(huán)移數(shù)結構覆蓋網絡中，如果鄰接雙方知道對方已經接收到此消息，就不再轉發(fā)該消息給對方；如果能夠記錄這些已經接收消息的節(jié)點，并將該信息放在消息頭中發(fā)送給其他節(jié)點，使其他節(jié)點不再發(fā)送此消息到已經記錄過的節(jié)點，就可大大減少消息冗余，這就是改進算法的出發(fā)點。

每輪傳輸時，可以在傳輸?shù)南笪闹蓄A留一個節(jié)點軌跡標記，將每次發(fā)送的目標鄰居節(jié)點集記錄在此標記中，收到消息后，首先檢查節(jié)點軌跡標記，消息只發(fā)往不在標記中的鄰節(jié)點，這樣就可以避免消息在近鄰節(jié)點間的冗余傳輸。

如在圖2所示算例中采用這種消息擴散算法，其消息擴散過程如圖3所示。由圖3中可見：

第一輪：初始節(jié)點0將其所有鄰居節(jié)點和自身，即｛0，1，2，4，6，7｝作為節(jié)點軌跡添加到消息頭，并向其所有鄰居節(jié)點轉發(fā)消息：0→1，0→2，0→4，0→6，0→7。

第二輪：節(jié)點1，2，4，6，7收到消息后，首先檢查其鄰居節(jié)點是否已記錄在節(jié)點軌跡標簽，只向不在標簽中的節(jié)點轉發(fā)消息：1→3，1→5，2→3，4→3，4→5，6→5，7→3，7→5。

同時在標簽中記錄新的節(jié)點，這樣便減少了12條冗余消息。可見帶標記的洪泛算法雖然思路簡單，卻可以有效減少傳輸冗余。

圖3 M－flooding算法的消息擴散過程Fig.3 Example of message expanding based on M－flooding algorithm

4 結語

本文提出混合式網格資源發(fā)現(xiàn)模型，是對現(xiàn)有資源發(fā)現(xiàn)機制和P2P技術的融合。但本文目前所做的工作僅在于理論上的探討，沒有考慮網絡本身的復雜情況，如在循環(huán)移數(shù)結構覆蓋網絡的構建過程中，沒有把節(jié)點之間消息的傳遞時間作為鄰居節(jié)點的考慮因素。因此，在后續(xù)工作中，將結合網格技術的最新發(fā)展，在更復雜的網絡結構上研究該模型的有效性。另外對于所提出的消息擴散算法還可以進一步優(yōu)化。

［1］ Ian Foster，Carl Kesselman.The grid：blueprint for a new computing infrastructure［M］.San Francisco：Morgan Ksufmann Publishers，1998：593－621.

［2］ 徐志偉，馮百明，李偉.網格計算技術［M］.北京：電子工業(yè)出版社，2004：59－126.

［3］ 徐志偉.基于P2P和服務質量的語義Web服務發(fā)現(xiàn)［J］.計算機技術與發(fā)展，2009，19（12）：25－28.

［4］ 李文娟，史維峰.基于分布式的語義Web服務發(fā)現(xiàn)新模型［J］.計算機技術與發(fā)展，2009，19（12）：108－112.

［5］ 何秀強，王寅峰，董小社，等.基于P2P技術的網格資源發(fā)現(xiàn)中的覆蓋網絡的構建［J］.微電子學與計算機，2005，22（7）：19－23.

［6］ Czajkowski K，F(xiàn)itzgerald S，F(xiàn)oster I.Grid information services for distributed resource sharing［C］／／Proc of the 10th IEEE HPDC，Washington DC：IEEE Computer Society Press，2001：181－194.

［7］ 熊金波，謝艷輝，張珊珊.基于DSOF的網格資源發(fā)現(xiàn)模型研究［J］.計算機工程與設計，2009，30（23）：5 317－5 320.