李琳娜，鐘冬望，王 芬

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

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

1 分層體系結(jié)構(gòu)

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

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

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

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

2.1 虛擬組織內(nèi)構(gòu)建覆蓋網(wǎng)絡(luò)

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

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

（2）accept消息。當(dāng)一個(gè)節(jié)點(diǎn)收到neighbor消息時(shí)，則向?qū)Ψ桨l(fā)送accept消息，告知對(duì)方已接受它為鄰居，并將對(duì)方信息保存在本地。accept算法如下：

2.2 虛擬組織間構(gòu)建覆蓋網(wǎng)絡(luò)

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

3 消息擴(kuò)散協(xié)議

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

3.1 問題描述

在討論算法之前，以循環(huán)移數(shù)結(jié)構(gòu)覆蓋網(wǎng)絡(luò)為基礎(chǔ)做下面的假設(shè)：

假設(shè)1：覆蓋網(wǎng)絡(luò)的規(guī)模為N＝2n。

假設(shè)2：每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的ID。

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

定義1：覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)v的度d（或鄰居數(shù)）是指此節(jié)點(diǎn)相連的鄰居節(jié)點(diǎn)個(gè)數(shù)。

定義2：消息從初始節(jié)點(diǎn)擴(kuò)散到覆蓋網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)的過程為一次消息擴(kuò)散。

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

式中：mi為節(jié)點(diǎn)i轉(zhuǎn)發(fā)的消息個(gè)數(shù)；N為覆蓋網(wǎng)絡(luò)規(guī)模（節(jié)點(diǎn)個(gè)數(shù)）。

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

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

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

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

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

對(duì)于循環(huán)移數(shù)結(jié)構(gòu)覆蓋網(wǎng)絡(luò)，其消息冗余傳輸開銷為

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

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

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

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

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

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

3.2 M－flooding消息擴(kuò)散算法

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

每輪傳輸時(shí)，可以在傳輸?shù)南?bào)文中預(yù)留一個(gè)節(jié)點(diǎn)軌跡標(biāo)記，將每次發(fā)送的目標(biāo)鄰居節(jié)點(diǎn)集記錄在此標(biāo)記中，收到消息后，首先檢查節(jié)點(diǎn)軌跡標(biāo)記，消息只發(fā)往不在標(biāo)記中的鄰節(jié)點(diǎn)，這樣就可以避免消息在近鄰節(jié)點(diǎn)間的冗余傳輸。

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

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

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

同時(shí)在標(biāo)簽中記錄新的節(jié)點(diǎn)，這樣便減少了12條冗余消息?？梢妿?biāo)記的洪泛算法雖然思路簡單，卻可以有效減少傳輸冗余。

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

4 結(jié)語

本文提出混合式網(wǎng)格資源發(fā)現(xiàn)模型，是對(duì)現(xiàn)有資源發(fā)現(xiàn)機(jī)制和P2P技術(shù)的融合。但本文目前所做的工作僅在于理論上的探討，沒有考慮網(wǎng)絡(luò)本身的復(fù)雜情況，如在循環(huán)移數(shù)結(jié)構(gòu)覆蓋網(wǎng)絡(luò)的構(gòu)建過程中，沒有把節(jié)點(diǎn)之間消息的傳遞時(shí)間作為鄰居節(jié)點(diǎn)的考慮因素。因此，在后續(xù)工作中，將結(jié)合網(wǎng)格技術(shù)的最新發(fā)展，在更復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)上研究該模型的有效性。另外對(duì)于所提出的消息擴(kuò)散算法還可以進(jìn)一步優(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］ 徐志偉，馮百明，李偉.網(wǎng)格計(jì)算技術(shù)［M］.北京：電子工業(yè)出版社，2004：59－126.

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

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

［5］ 何秀強(qiáng)，王寅峰，董小社，等.基于P2P技術(shù)的網(wǎng)格資源發(fā)現(xiàn)中的覆蓋網(wǎng)絡(luò)的構(gòu)建［J］.微電子學(xué)與計(jì)算機(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的網(wǎng)格資源發(fā)現(xiàn)模型研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（23）：5 317－5 320.