（山東師范大學(xué) 信息科學(xué)與工程學(xué)院， 濟(jì)南 250014）

摘 要：通過對(duì)教育資源網(wǎng)格的研究，提出了邏輯層次式模型，并對(duì)資源檢索過程進(jìn)行分析；然后從過濾冗余信息的角度出發(fā)，提出了一種基于路由標(biāo)注的信息檢索策略，有效減少冗余信息的產(chǎn)生，節(jié)省網(wǎng)絡(luò)帶寬。最后通過理論分析和模擬實(shí)驗(yàn)表明，該策略可以有效地減少教育資源網(wǎng)格中信息檢索的通信開銷。

關(guān)鍵詞：教育資源網(wǎng)格；信息檢索；路由標(biāo)注；洪泛法

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1484-03

Information retrieval strategy based on education resource grid

YANG Lin，ZHANG Yong-sheng，XING Chang-ming

(College of Information Science Technology， Shandong Normal University， Jinan 250014， China)

Abstract:Based on the research of education resource grid，this paper proposed a logic education resource grid model. Through analyzing the process of information retrieval in education resource grid，presented an information retrieval strategy based on routing label in order to reduce redundancy information and save network bandwidth. The result of the experiments shows that this strategy can effectively reduce the communication cost in education resource grid.

Key words:education resource grid; information retrieval; routing label; flooding

為解決教育資源分布式共享問題，教育資源網(wǎng)格平臺(tái)提供了一種無縫的、集成的資源共享和協(xié)作環(huán)境，其目標(biāo)是協(xié)調(diào)網(wǎng)格中資源的使用，以便及時(shí)地響應(yīng)網(wǎng)格用戶的資源請求；同時(shí)高效的檢索策略是提高教育資源網(wǎng)格系統(tǒng)可擴(kuò)展性、可用性和降低用戶延遲的有效手段?，F(xiàn)存的分布式信息檢索通常采用洪泛（flooding）機(jī)制[1]。該機(jī)制實(shí)現(xiàn)簡單，任意節(jié)點(diǎn)將接收到的檢索消息轉(zhuǎn)發(fā)給其所有鄰居節(jié)點(diǎn)以保證查詢請求被盡可能地發(fā)送到系統(tǒng)覆蓋的每一個(gè)節(jié)點(diǎn)上，不過節(jié)點(diǎn)多次收到同一檢索消息，檢索報(bào)文個(gè)數(shù)被指數(shù)級(jí)放大，產(chǎn)生大量的冗余信息，造成嚴(yán)重的帶寬消耗。為緩解這種情況，可采用為消息報(bào)文增加“跳步”限制的方法，即為每個(gè)消息報(bào)文設(shè)定一個(gè)time-to-live(TTL)值，隨著跳步的增加，TTL減少，當(dāng)TTL為0時(shí)，檢索消息停止傳播。然而TTL的選擇具有盲目性，若TTL過大時(shí)，產(chǎn)生大量的冗余信息；若TTL過小，消息覆蓋范圍有限。

針對(duì)消息傳遞或檢索方法，文獻(xiàn)[1~3]分別從控制消息發(fā)送范圍、創(chuàng)建評(píng)價(jià)函數(shù)和拓?fù)鋬?yōu)化等角度提出了相應(yīng)的算法。文獻(xiàn)[1]研究了基于謠言(Rumor或Gossip)機(jī)制的消息傳遞策略，節(jié)點(diǎn)總是以概率p決定是否向其鄰居節(jié)點(diǎn)傳遞消息，雖可減少部分冗余開銷，但性能參數(shù)p的選擇是一個(gè)折中的結(jié)果；文獻(xiàn)[2]利用相關(guān)度及用戶興趣作為評(píng)價(jià)函數(shù)在Internet上進(jìn)行啟發(fā)式搜索，需要計(jì)算大量相關(guān)數(shù)據(jù)來創(chuàng)建評(píng)價(jià)函數(shù)；文獻(xiàn)[3]通過構(gòu)造SRDM提出改進(jìn)的分布式hash表（DHT）算法，但只適合結(jié)構(gòu)化P2P網(wǎng)絡(luò)。基于以上研究，本文的主要工作為：提出邏輯層次式的教育資源網(wǎng)格架構(gòu)，并描述了信息檢索過程；從查詢請求轉(zhuǎn)發(fā)時(shí)過濾冗余信息的角度提出一種基于路由標(biāo)注的信息檢索策略，減少通信開銷；通過理論分析和模擬實(shí)驗(yàn)與flooding算法進(jìn)行比較，表明本文策略的有效性。

1 教育資源網(wǎng)格體系架構(gòu)

1.1 教育資源網(wǎng)格模型

教育資源網(wǎng)格由物理分散的多個(gè)計(jì)算機(jī)節(jié)點(diǎn)組成，分散的節(jié)點(diǎn)之間通過網(wǎng)絡(luò)連接在一起，可以進(jìn)行資源互訪和共享；在邏輯空間中可抽象為層次模型，分為中心節(jié)點(diǎn)（center node，CN）、管理節(jié)點(diǎn)（management node，MN）和資源節(jié)點(diǎn)（resource node，RN）。具體拓?fù)浣Y(jié)構(gòu)如圖1所示。

模型最上層由中心節(jié)點(diǎn)和管理節(jié)點(diǎn)組成，所有的管理節(jié)點(diǎn)都連向中心節(jié)點(diǎn)；第二層劃分為各個(gè)域，管理節(jié)點(diǎn)處于邏輯中心位置，連接各個(gè)資源節(jié)點(diǎn)；最低層是資源節(jié)點(diǎn)，包括所有的用戶和資源服務(wù)提供者。

a）中心節(jié)點(diǎn)，負(fù)責(zé)全局統(tǒng)一管理，響應(yīng)管理節(jié)點(diǎn)的信息查詢，以便用戶對(duì)不同子域內(nèi)資源的查詢與訪問，所有的管理節(jié)點(diǎn)都連接中心，并將它們的信息注冊在上。

b）管理節(jié)點(diǎn)，負(fù)責(zé)維護(hù)其轄域內(nèi)的資源節(jié)點(diǎn)，記錄本域內(nèi)的資源節(jié)點(diǎn)信息，響應(yīng)用戶以及其他管理節(jié)點(diǎn)轉(zhuǎn)發(fā)的信息查詢。

c）資源節(jié)點(diǎn)，包括用戶和資源提供者，兩者在一定情況下可互相轉(zhuǎn)換，用戶提出查詢請求，資源提供者實(shí)時(shí)地向上層節(jié)點(diǎn)發(fā)送本地資源的動(dòng)態(tài)變化，以便及時(shí)更新。

1.2 信息檢索描述

本文討論的教育資源網(wǎng)格中的信息檢索是指：當(dāng)一個(gè)網(wǎng)格用戶發(fā)出檢索請求時(shí)，通過各域間的MN節(jié)點(diǎn)進(jìn)行消息傳遞，盡可能地查詢網(wǎng)格系統(tǒng)中的資源信息以獲得最大數(shù)量的可用資源。

信息檢索過程描述如下:

a）網(wǎng)格用戶向其所在域的MN發(fā)送查詢請求。

b）MN收到請求后，檢查本域內(nèi)的資源列表同時(shí)將查詢請求向其相鄰的MN進(jìn)行轉(zhuǎn)發(fā)。一且找到合適的資源，就發(fā)送確認(rèn)請求到該資源請求節(jié)點(diǎn)。

c）接收到查詢請求的MN都會(huì)檢查自己的列表。如果其中某個(gè)MN找到了合適的資源，就返回一個(gè)確認(rèn)消息到原MN；同時(shí)這些MN繼續(xù)將請求轉(zhuǎn)發(fā)至各自相鄰的其他MN。

d）如果經(jīng)過若干跳，最后沒有找到合適的資源，請求將會(huì)被轉(zhuǎn)發(fā)至CN，然后在全局范圍內(nèi)尋找合適的資源；若請求總是得不到滿足，則由CN發(fā)送一個(gè)失敗消息至原MN，然后再轉(zhuǎn)發(fā)至資源請求者。

查詢請求在相鄰MN的轉(zhuǎn)發(fā)過程中，采用flooding機(jī)制必然經(jīng)過大量重復(fù)節(jié)點(diǎn)。那么采用什么方法盡量減少冗余消息，節(jié)約網(wǎng)絡(luò)帶寬？下文從這個(gè)角度提出基于路由標(biāo)注的信息檢索策略。

2 基于路由標(biāo)注的信息檢索策略

2.1 相關(guān)問題分析

定義1 檢索節(jié)點(diǎn)是指在檢索過程中參與傳播查詢請求的節(jié)點(diǎn)，記為v。

定義2 教育資源網(wǎng)格中節(jié)點(diǎn)v的度d是指與此節(jié)點(diǎn)相連的鄰居節(jié)點(diǎn)數(shù)。

定義3 平均每個(gè)查詢請求在一次檢索過程中轉(zhuǎn)發(fā)的次數(shù)為查詢傳輸開銷，則

f=1/RNi=1mi(1)

其中：R為查詢請求可達(dá)的節(jié)點(diǎn)數(shù)；mi為節(jié)點(diǎn)i轉(zhuǎn)發(fā)的查詢請求個(gè)數(shù)；N為網(wǎng)格中滿足查詢轉(zhuǎn)發(fā)的節(jié)點(diǎn)個(gè)數(shù)。由式（1），在圖2(a)中，查詢請求初始轉(zhuǎn)發(fā)節(jié)點(diǎn)為A，進(jìn)行一次請求轉(zhuǎn)發(fā)的傳輸開銷為2/3≈0.6；圖2(b)中為4/3≈1.3。

定義4 假設(shè)滿足轉(zhuǎn)發(fā)的節(jié)點(diǎn)個(gè)數(shù)為N，在某一次檢索過程中查詢請求可到達(dá)的節(jié)點(diǎn)數(shù)為R，則在該次檢索中覆蓋率C定義為

C=R/N（2）

在Gnutella[4]系統(tǒng)中，由于消息的傳遞與更新均通過基于洪泛（flooding）機(jī)制，如果節(jié)點(diǎn)第一次收到某條檢索消息時(shí)，則此節(jié)點(diǎn)會(huì)將消息轉(zhuǎn)發(fā)給所有的除消息來源以外的鄰居節(jié)點(diǎn)，若系統(tǒng)中節(jié)點(diǎn)的平均度為，由式（1），其傳輸開銷fflooding為

fflooding=1/N[1+Ni=1(di-1)]=1/N+1/NNi=1(di-1)≈-1（3）

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

對(duì)于泛洪機(jī)制若不考慮TTL限制，其覆蓋度Cflooding=1。

2.2 策略的提出

策略的設(shè)計(jì)思想：在教育資源網(wǎng)格的信息檢索過程中，初始轉(zhuǎn)發(fā)節(jié)點(diǎn)在報(bào)文頭部添加發(fā)送了查詢請求的鄰節(jié)點(diǎn)信息，之后節(jié)點(diǎn)在轉(zhuǎn)發(fā)查詢請求時(shí)，首先查看報(bào)文頭部即檢查自己的鄰居節(jié)點(diǎn)是否在路由標(biāo)注中，如果存在則說明已經(jīng)向該節(jié)點(diǎn)發(fā)送過查詢請求，不再向此節(jié)點(diǎn)轉(zhuǎn)發(fā)；否則就向此節(jié)點(diǎn)轉(zhuǎn)發(fā)該消息。報(bào)頭的路由標(biāo)注一經(jīng)更改則該節(jié)點(diǎn)立即通知其鄰節(jié)點(diǎn)以減少冗余信息。算法描述如下:

Sv：表示路由標(biāo)注后的目標(biāo)節(jié)點(diǎn)集合；

Nv：表示節(jié)點(diǎn)v的鄰節(jié)點(diǎn)集合；

Routing Label Algorithm (v， message )

if the node. vi receives the message firstly

//初始轉(zhuǎn)發(fā)的節(jié)點(diǎn)向目標(biāo)集合添加鄰節(jié)點(diǎn)信息并轉(zhuǎn)發(fā)消息；

{send the message to every neighbor. vi and Sv=Sv∪Nvi;}

while (vj∈Nvi，j≠i)/*收到查詢請求的節(jié)點(diǎn)檢查路由標(biāo)注，向不在目標(biāo)集合的節(jié)點(diǎn)轉(zhuǎn)發(fā)信息*/

{check neighbor. vj∈Sv or not;

if (vx∈Nvj∧(vx is not in Sv))

{send the message to vx and Sv=Sv∪Nvj;}

send Sv to neighbor. vj;

}

if (all neighbor. vj is in Sv)/*當(dāng)某節(jié)點(diǎn)的鄰節(jié)點(diǎn)都在目標(biāo)集合時(shí)，轉(zhuǎn)發(fā)結(jié)束*/

endwhile;

endif;

end.

現(xiàn)將本策略與flooding作簡單的實(shí)例比較分析，如算法描述，節(jié)點(diǎn)集合{① ② ③ ④ ⑤}。其中①為查詢請求發(fā)起節(jié)點(diǎn)。

在圖3(a)中，采用flooding機(jī)制，根據(jù)拓?fù)浣Y(jié)構(gòu)的連接路由轉(zhuǎn)發(fā)，第一輪①向其鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢請求如下：①→②，①→③，①→④；第二輪傳輸時(shí)接收到查詢請求的② ③ ④分別向其鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)如下：②→③，②→④，②→⑤；③→②，③→④，③→⑤；④→②，④→③，④→⑤；第三輪轉(zhuǎn)發(fā)如下：⑤→③，⑤→④。整個(gè)過程中共產(chǎn)生轉(zhuǎn)發(fā)信息14條， fflooding=2。

圖3(b)中，采用基于路由標(biāo)注的檢索策略，第一輪①在向其鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)，將目標(biāo)節(jié)點(diǎn)集和自身{② ③ ④ ①}添加到路由報(bào)文，查詢請求的轉(zhuǎn)發(fā)如下：①→②，①→③，①→④；第二輪② ③ ④向其鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)首先查看報(bào)文中標(biāo)注的節(jié)點(diǎn)，只向沒有接收到查詢請求的⑤轉(zhuǎn)發(fā)并將其加入目標(biāo)節(jié)點(diǎn)集：②→⑤，③→⑤，④→⑤；此時(shí)已接收到的節(jié)點(diǎn)集為{② ③ ④ ① ⑤}，⑤將不再向任何節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢請求。整個(gè)過程共產(chǎn)生轉(zhuǎn)發(fā)信息六條，大大過濾了冗余信息，減少了系統(tǒng)的通信開銷，節(jié)約了傳輸帶寬。

2.3 路由標(biāo)注的報(bào)頭格式

Internet上的每臺(tái)主機(jī)和路由器均有唯一的IP地址，因此可將IP信息作為節(jié)點(diǎn)標(biāo)志添加在路由標(biāo)注的報(bào)文中［5］，如圖4所示。第一部分是添加路由標(biāo)注的節(jié)點(diǎn)信息，第二部分即為查詢請求消息。

由于在報(bào)頭添加了相應(yīng)的節(jié)點(diǎn)信息，報(bào)文變長并隨著目標(biāo)節(jié)點(diǎn)集的增多而加大。為減少報(bào)頭長度加大帶來的信息過量的額外開銷，可利用文獻(xiàn)[5，6]提出的Bloom filter存儲(chǔ)算法壓縮節(jié)點(diǎn)路由標(biāo)注信息，Bloom filter是用來表示集合、支持集合元素查詢的一種簡潔結(jié)構(gòu)，它對(duì)集合元素的表示只需要少數(shù)幾個(gè)比特，能夠大大縮減報(bào)文長度。

3 理論分析及模擬實(shí)驗(yàn)

3.1 理論分析

首先假設(shè)教育資源網(wǎng)格中轉(zhuǎn)發(fā)查詢請求的節(jié)點(diǎn)數(shù)為N即覆蓋率C=1，共存在E條邊，節(jié)點(diǎn)的平均度為d且=2E/N。根據(jù)文獻(xiàn)[7]中的引理2，圖中邊的條數(shù)E，可以由一個(gè)關(guān)于節(jié)點(diǎn)數(shù)N和指數(shù)e的函數(shù)計(jì)算得出：

E=[1/2(e+1)](1-1/Ne+1)N（4）

將式（4）代入=2E/N，得到

=[1/（e+1）](1-1/Ne+1) →1/（e+1）(N→∞)（5）

從上可以看出與N無直接關(guān)系。

顯然，flooding機(jī)制中所轉(zhuǎn)發(fā)的查詢請求個(gè)數(shù)為

FMsgtotal=Ni=1(di-1)=N(-1)（6）

基于路由標(biāo)注的檢索策略中，每一次新加入目標(biāo)集合的節(jié)點(diǎn)都在下一輪的轉(zhuǎn)發(fā)中被刪除，檢索過程中轉(zhuǎn)發(fā)的查詢請求個(gè)數(shù)為

LMsgtotal=Ni=1(di-vi)=N-Ni=1vi （7）

其中：vi為節(jié)點(diǎn)i的鄰節(jié)點(diǎn)中已加入目標(biāo)集合的節(jié)點(diǎn)個(gè)數(shù)。

3.2 模擬實(shí)驗(yàn)

利用VC++開發(fā)模擬工具，驗(yàn)證本文算法的有效性。首先由模擬器產(chǎn)生出教育資源網(wǎng)格的參與轉(zhuǎn)發(fā)查詢請求的節(jié)點(diǎn)分布（圖5），然后在節(jié)點(diǎn)個(gè)數(shù)分別為200~1 000內(nèi)，依據(jù)冗余信息數(shù)和系統(tǒng)傳輸開銷兩個(gè)指標(biāo)，比較本文算法L_flooding和flooding算法的性能。為了提高實(shí)驗(yàn)數(shù)據(jù)的精確度，每次結(jié)果數(shù)據(jù)均取10次相同實(shí)驗(yàn)的平均值。實(shí)驗(yàn)結(jié)果如圖6、7所示。

從實(shí)驗(yàn)結(jié)果得出，在同等系統(tǒng)規(guī)模下，本文策略產(chǎn)生的冗余消息數(shù)比flooding機(jī)制減少近1/3，且其傳輸開銷明顯優(yōu)于flooding，即可節(jié)省大量網(wǎng)絡(luò)帶寬，能夠適用于分布式系統(tǒng)的信息檢索。

4 結(jié)束語

本文在研究教育資源網(wǎng)格架構(gòu)的基礎(chǔ)上，為了減少檢索過程中冗余消息的產(chǎn)生，通過在消息報(bào)文中添加節(jié)點(diǎn)信息，提出了一種基于路由標(biāo)注的信息檢索策略。通過實(shí)例分析和仿真實(shí)驗(yàn)表明，該策略不降低算法覆蓋度的情況下，能夠有效減少由于flooding引起的冗余傳輸開銷，節(jié)省網(wǎng)絡(luò)帶寬，能夠適用于教育資源網(wǎng)格中的信息檢索。

參考文獻(xiàn)：

［1］

竇文，王懷民.模擬Rumor傳播機(jī)制的無結(jié)構(gòu)P2P網(wǎng)絡(luò)中廣播機(jī)制的研究[J].計(jì)算機(jī)研究與發(fā)展，2004，41(9):1460-1465.

[2]劉弘，劉希玉.一種Web信息的啟發(fā)式檢索方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2003，24(3):427-429.

[3]張龍，李巍，李云春.基于改進(jìn)DHT算法的分布式資源發(fā)現(xiàn)模型的研究[J].計(jì)算機(jī)應(yīng)用研究， 2007，24(12):313-316.

[4]RIPEANU M.Peer-to-peer architecture case study:Gnutella network[C]//Proc of the 1st International Conference on Peer-to-Peer Computing.Linkoping:IEEE Computer Society，2001:99-100.

［5］謝鯤，張大方，謝高崗，等.基于軌跡標(biāo)簽的無結(jié)構(gòu)P2P副本一致性維護(hù)算法[J].軟件學(xué)報(bào)，2007，18(1):105-116.

[6]MITZENMACHER M.Compressed Bloom filters[J].IEEE/ACM Trans on Networking，2002，10(5):604-612.

[7]FALOUTSOS M，F(xiàn)ALOUTSOS P，F(xiàn)ALOUTSOS C.On Power-law relationships of the Internet topology[C]//Proc of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication.New York:ACM Press，1999:251-262.