基于教育資源網格的信息檢索策略
2009-01-01 00:00:00楊林張永勝邢長明
計算機應用研究 2009年4期
（山東師范大學 信息科學與工程學院， 濟南 250014）
摘 要：通過對教育資源網格的研究，提出了邏輯層次式模型，并對資源檢索過程進行分析；然后從過濾冗余信息的角度出發，提出了一種基于路由標注的信息檢索策略，有效減少冗余信息的產生，節省網絡帶寬。最后通過理論分析和模擬實驗表明，該策略可以有效地減少教育資源網格中信息檢索的通信開銷。
關鍵詞：教育資源網格；信息檢索；路由標注；洪泛法
中圖分類號：TP311文獻標志碼：A
文章編號：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
為解決教育資源分布式共享問題，教育資源網格平臺提供了一種無縫的、集成的資源共享和協作環境，其目標是協調網格中資源的使用，以便及時地響應網格用戶的資源請求；同時高效的檢索策略是提高教育資源網格系統可擴展性、可用性和降低用戶延遲的有效手段?，F存的分布式信息檢索通常采用洪泛（flooding）機制[1]。該機制實現簡單，任意節點將接收到的檢索消息轉發給其所有鄰居節點以保證查詢請求被盡可能地發送到系統覆蓋的每一個節點上，不過節點多次收到同一檢索消息，檢索報文個數被指數級放大，產生大量的冗余信息，造成嚴重的帶寬消耗。為緩解這種情況，可采用為消息報文增加“跳步”限制的方法，即為每個消息報文設定一個time-to-live(TTL)值，隨著跳步的增加，TTL減少，當TTL為0時，檢索消息停止傳播。然而TTL的選擇具有盲目性，若TTL過大時，產生大量的冗余信息；若TTL過小，消息覆蓋范圍有限。
針對消息傳遞或檢索方法，文獻[1~3]分別從控制消息發送范圍、創建評價函數和拓撲優化等角度提出了相應的算法。文獻[1]研究了基于謠言(Rumor或Gossip)機制的消息傳遞策略，節點總是以概率p決定是否向其鄰居節點傳遞消息，雖可減少部分冗余開銷，但性能參數p的選擇是一個折中的結果；文獻[2]利用相關度及用戶興趣作為評價函數在Internet上進行啟發式搜索，需要計算大量相關數據來創建評價函數；文獻[3]通過構造SRDM提出改進的分布式hash表（DHT）算法，但只適合結構化P2P網絡。基于以上研究，本文的主要工作為：提出邏輯層次式的教育資源網格架構，并描述了信息檢索過程；從查詢請求轉發時過濾冗余信息的角度提出一種基于路由標注的信息檢索策略，減少通信開銷；通過理論分析和模擬實驗與flooding算法進行比較，表明本文策略的有效性。
1 教育資源網格體系架構
1.1 教育資源網格模型
教育資源網格由物理分散的多個計算機節點組成，分散的節點之間通過網絡連接在一起，可以進行資源互訪和共享；在邏輯空間中可抽象為層次模型，分為中心節點（center node，CN）、管理節點（management node，MN）和資源節點（resource node，RN）。具體拓撲結構如圖1所示。
模型最上層由中心節點和管理節點組成，所有的管理節點都連向中心節點；第二層劃分為各個域，管理節點處于邏輯中心位置，連接各個資源節點；最低層是資源節點，包括所有的用戶和資源服務提供者。
a）中心節點，負責全局統一管理，響應管理節點的信息查詢，以便用戶對不同子域內資源的查詢與訪問，所有的管理節點都連接中心，并將它們的信息注冊在上。
b）管理節點，負責維護其轄域內的資源節點，記錄本域內的資源節點信息，響應用戶以及其他管理節點轉發的信息查詢。
c）資源節點，包括用戶和資源提供者，兩者在一定情況下可互相轉換，用戶提出查詢請求，資源提供者實時地向上層節點發送本地資源的動態變化，以便及時更新。
1.2 信息檢索描述
本文討論的教育資源網格中的信息檢索是指：當一個網格用戶發出檢索請求時，通過各域間的MN節點進行消息傳遞，盡可能地查詢網格系統中的資源信息以獲得最大數量的可用資源。
信息檢索過程描述如下:
a）網格用戶向其所在域的MN發送查詢請求。
b）MN收到請求后，檢查本域內的資源列表同時將查詢請求向其相鄰的MN進行轉發。一且找到合適的資源，就發送確認請求到該資源請求節點。
c）接收到查詢請求的MN都會檢查自己的列表。如果其中某個MN找到了合適的資源，就返回一個確認消息到原MN；同時這些MN繼續將請求轉發至各自相鄰的其他MN。
d）如果經過若干跳，最后沒有找到合適的資源，請求將會被轉發至CN，然后在全局范圍內尋找合適的資源；若請求總是得不到滿足，則由CN發送一個失敗消息至原MN，然后再轉發至資源請求者。
查詢請求在相鄰MN的轉發過程中，采用flooding機制必然經過大量重復節點。那么采用什么方法盡量減少冗余消息，節約網絡帶寬？下文從這個角度提出基于路由標注的信息檢索策略。
2 基于路由標注的信息檢索策略
2.1 相關問題分析
定義1 檢索節點是指在檢索過程中參與傳播查詢請求的節點，記為v。
定義2 教育資源網格中節點v的度d是指與此節點相連的鄰居節點數。
定義3 平均每個查詢請求在一次檢索過程中轉發的次數為查詢傳輸開銷，則
f=1/RNi=1mi(1)
其中：R為查詢請求可達的節點數；mi為節點i轉發的查詢請求個數；N為網格中滿足查詢轉發的節點個數。由式（1），在圖2(a)中，查詢請求初始轉發節點為A，進行一次請求轉發的傳輸開銷為2/3≈0.6；圖2(b)中為4/3≈1.3。
定義4 假設滿足轉發的節點個數為N，在某一次檢索過程中查詢請求可到達的節點數為R，則在該次檢索中覆蓋率C定義為
C=R/N（2）
在Gnutella[4]系統中，由于消息的傳遞與更新均通過基于洪泛（flooding）機制，如果節點第一次收到某條檢索消息時，則此節點會將消息轉發給所有的除消息來源以外的鄰居節點，若系統中節點的平均度為，由式（1），其傳輸開銷fflooding為
fflooding=1/N[1+Ni=1(di-1)]=1/N+1/NNi=1(di-1)≈-1（3）
其中：di為節點i的度數即鄰居節點數。
對于泛洪機制若不考慮TTL限制，其覆蓋度Cflooding=1。
2.2 策略的提出
策略的設計思想：在教育資源網格的信息檢索過程中，初始轉發節點在報文頭部添加發送了查詢請求的鄰節點信息，之后節點在轉發查詢請求時，首先查看報文頭部即檢查自己的鄰居節點是否在路由標注中，如果存在則說明已經向該節點發送過查詢請求，不再向此節點轉發；否則就向此節點轉發該消息。報頭的路由標注一經更改則該節點立即通知其鄰節點以減少冗余信息。算法描述如下:
Sv：表示路由標注后的目標節點集合；
Nv：表示節點v的鄰節點集合；
Routing Label Algorithm (v， message )
if the node. vi receives the message firstly
//初始轉發的節點向目標集合添加鄰節點信息并轉發消息；
{send the message to every neighbor. vi and Sv=Sv∪Nvi;}
while (vj∈Nvi，j≠i)/*收到查詢請求的節點檢查路由標注，向不在目標集合的節點轉發信息*/
{check neighbor. vj∈Sv or not;
if (vx∈Nvj∧(vx is not in Sv))
{send the message to vx and Sv=Sv∪Nvj;}
send Sv to neighbor. vj;
}
if (all neighbor. vj is in Sv)/*當某節點的鄰節點都在目標集合時，轉發結束*/
endwhile;
endif;
end.
現將本策略與flooding作簡單的實例比較分析，如算法描述，節點集合{① ② ③ ④ ⑤}。其中①為查詢請求發起節點。
在圖3(a)中，采用flooding機制，根據拓撲結構的連接路由轉發，第一輪①向其鄰節點轉發查詢請求如下：①→②，①→③，①→④；第二輪傳輸時接收到查詢請求的② ③ ④分別向其鄰節點轉發如下：②→③，②→④，②→⑤；③→②，③→④，③→⑤；④→②，④→③，④→⑤；第三輪轉發如下：⑤→③，⑤→④。整個過程中共產生轉發信息14條， fflooding=2。
圖3(b)中，采用基于路由標注的檢索策略，第一輪①在向其鄰節點轉發時，將目標節點集和自身{② ③ ④ ①}添加到路由報文，查詢請求的轉發如下：①→②，①→③，①→④；第二輪② ③ ④向其鄰節點轉發時首先查看報文中標注的節點，只向沒有接收到查詢請求的⑤轉發并將其加入目標節點集：②→⑤，③→⑤，④→⑤；此時已接收到的節點集為{② ③ ④ ① ⑤}，⑤將不再向任何節點轉發查詢請求。整個過程共產生轉發信息六條，大大過濾了冗余信息，減少了系統的通信開銷，節約了傳輸帶寬。
2.3 路由標注的報頭格式
Internet上的每臺主機和路由器均有唯一的IP地址，因此可將IP信息作為節點標志添加在路由標注的報文中［5］，如圖4所示。第一部分是添加路由標注的節點信息，第二部分即為查詢請求消息。
由于在報頭添加了相應的節點信息，報文變長并隨著目標節點集的增多而加大。為減少報頭長度加大帶來的信息過量的額外開銷，可利用文獻[5，6]提出的Bloom filter存儲算法壓縮節點路由標注信息，Bloom filter是用來表示集合、支持集合元素查詢的一種簡潔結構，它對集合元素的表示只需要少數幾個比特，能夠大大縮減報文長度。
3 理論分析及模擬實驗
3.1 理論分析
首先假設教育資源網格中轉發查詢請求的節點數為N即覆蓋率C=1，共存在E條邊，節點的平均度為d且=2E/N。根據文獻[7]中的引理2，圖中邊的條數E，可以由一個關于節點數N和指數e的函數計算得出：
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無直接關系。
顯然，flooding機制中所轉發的查詢請求個數為
FMsgtotal=Ni=1(di-1)=N(-1)（6）
基于路由標注的檢索策略中，每一次新加入目標集合的節點都在下一輪的轉發中被刪除，檢索過程中轉發的查詢請求個數為
LMsgtotal=Ni=1(di-vi)=N-Ni=1vi （7）
其中：vi為節點i的鄰節點中已加入目標集合的節點個數。
3.2 模擬實驗
利用VC++開發模擬工具，驗證本文算法的有效性。首先由模擬器產生出教育資源網格的參與轉發查詢請求的節點分布（圖5），然后在節點個數分別為200~1 000內，依據冗余信息數和系統傳輸開銷兩個指標，比較本文算法L_flooding和flooding算法的性能。為了提高實驗數據的精確度，每次結果數據均取10次相同實驗的平均值。實驗結果如圖6、7所示。
從實驗結果得出，在同等系統規模下，本文策略產生的冗余消息數比flooding機制減少近1/3，且其傳輸開銷明顯優于flooding，即可節省大量網絡帶寬，能夠適用于分布式系統的信息檢索。
4 結束語
本文在研究教育資源網格架構的基礎上，為了減少檢索過程中冗余消息的產生，通過在消息報文中添加節點信息，提出了一種基于路由標注的信息檢索策略。通過實例分析和仿真實驗表明，該策略不降低算法覆蓋度的情況下，能夠有效減少由于flooding引起的冗余傳輸開銷，節省網絡帶寬，能夠適用于教育資源網格中的信息檢索。
參考文獻：
［1］
竇文，王懷民.模擬Rumor傳播機制的無結構P2P網絡中廣播機制的研究[J].計算機研究與發展，2004，41(9):1460-1465.
[2]劉弘，劉希玉.一種Web信息的啟發式檢索方法[J].小型微型計算機系統，2003，24(3):427-429.
[3]張龍，李巍，李云春.基于改進DHT算法的分布式資源發現模型的研究[J].計算機應用研究， 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］謝鯤，張大方，謝高崗，等.基于軌跡標簽的無結構P2P副本一致性維護算法[J].軟件學報，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，FALOUTSOS P，FALOUTSOS 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.
