一種改進的Chord模型及其應用

楊盛峰

（長江大學計算機科學學院，湖北 荊州434023；荊州軍分區鐘鼓樓干休所，湖北 荊州434020）

王 焱

（鄖陽師范高等專科學校教育系，湖北 十堰442000）

點對點技術（peer－to－peer，P2P）又稱對等互聯網絡技術，充分挖掘了網絡節點的空閑資源，極大提高了網絡資源的使用效率，受到學術界和企業界的普遍關注。根據P2P網絡的組建方式不同，一般將P2P網絡分為結構化P2P網絡和非結構化P2P網絡，結構化P2P網絡主要通過分布式哈希表DHT（DHT，Distributed Hash Table）實現，能夠快速對目標資源進行定位。非結構化P2P網絡對資源的搜索主要是基于泛洪算法，消耗較多的系統資源。當前國內外最新研究表明，P2P網絡的拓撲結構既不是確定性的結構化網絡，也不是隨機的非結構化網絡。根據Small Worl d模型和冪規律［1］，考慮了結構化網絡和非結構化的特點，在原有Chor d模型的基礎上，提出了一種改進的Chor d模型，并將改進的Chor d模型應用到遠程教育系統中，以便提高遠程教育系統的資源利用效率和資源搜索速度。

1 Chord模型

Chor d模型是基于環形結構建立的，該模型中的每個關鍵字和節點都分別擁有一個m比特的標識符。資源關鍵字標識符K通過哈希關鍵字取得，而環節點標識符N則通過哈希節點的IP地址取得，然后將資源關鍵字分配到等于或者最接近的環形節點上。Chor d模型中節點的分配是從邏輯上實現的，節點在網絡中的地位是完全平等的，共同承擔系統的負載任務，查找具有確定性，而且還具有較好的可擴展性［2］。但也存在沒有考慮節點的物理關系、沒有考慮到節點的實際能力大小和負載不均衡等方面的缺點［3］，導致資源利用效率較低，存在一些資源的搜索時間過長的現象。

2 改進的Chor d模型

2.1 改進Chord模型的基本思想

改進Chor d模型的基本思想是在原Chor d模型的基礎上充分考慮了節點的實際能力和物理位置，將模型內的節點分為群首節點、群節點、備份節點，同一區域的節點構成一個群組。其定義如下：

1）群組 根據網絡中節點的相對位置，劃分多個不同的群組，將位置較近的劃分到一個群組中。2）群首節點 根據節點的運行速度、存儲容量、穩定程度和在線時間等性能指標選擇出一個群組中性能最優的節點為群首節點，其功能主要是負責所在群組節點的事務。

3）備份節點 又稱次群首節點，在同一群組中，備份節點的性能僅次于群首節點，高于其他節點的性能。

4）群節點 又稱普通節點，在同一群組中除群首節點和備份節點外的節點。

2.2 改進Chor d模型群組劃分

改進Chord模型中需要將節點分為多個群組，群組的劃分可以通過空間劃分法和時間劃分法2種方法來實現。空間劃分法劃分群組的原理是通過IP地址的特點來實現的，根據IP地址的網絡部分和主機部分的值由哈希函數生成節點標識符，根據節點標識符網絡部分的哈希值判斷該節點是否在位于同一群組。時間劃分法的實現首先選定合適的若干界標點，界標點的個數根據實際情況決定，界標點個數越多，其群組數就越多。界標點確定后分別計算網絡中的每個節點與這些界標點的傳輸時間間隔，將傳輸時間間隔按升序或降序排序，順序相同的節點說明其在一個局部范圍內，將其劃分成一個群組，將順序相近的群組劃分成相鄰的群組。通過空間劃分法和時間劃分法保證了改進Chor d模型中的節點的邏輯位置與物理位置的一致，減少了原有Chor d模型資源交換平均跳轉數和網絡的通信代價。

2.3 改進的Chor d模型設計

改進Chor d模型是一種分層結構，由主環和子環組成。根據上述2種群組劃分法將節點分成不同的群組，每個群組形成一個子環，物理位置相近的子環相互連接構成主環。改進后的Chor d模型有效的考慮了節點的物理位置和節點的性能差異，并且充分利用緩存技術，將熱點資源的索引信息寫入到所有群首結點的緩存區，其查詢大多數能夠在子環中實現。子環中節點的個數由實際網絡的結構決定。改進模型中群首節點、群節點和備份節點的數據結構如下［4］：

1）群首節點數據結構 群首節點負責管理所在群組節點的運行，同時不同子環節點的通信也是通過群首節點建立聯系的，其數據結構主要包括雙重路由表，熱點資源信息表和心跳次數表。①雙重路由表是指在群首節點中既包括了主環的路由表，也包括了所在子環的路由表，其定義方法遵循原Chor d模型的定義方法。②熱點資源信息表主要為快速查找熱點資源而建立的索引信息表。首先判斷一定時間內訪問次數是否大于事先規定的臨界值，如果大于臨界值，該資源就為熱點資源，然后將其信息記錄在熱點資源信息表上，信息表的具體結構為《關鍵字、節點標識符、熱點資源所在節點IP》。③心跳次數表的主要用來判斷在一定時間期間內群首結點的前趨節點、后繼節點和備份節點是否處于生命活動周期。心跳發送節點定期的向心跳接受接點發送消息，表示發送接點處于生命活動周期，如果大于一定時間時期未發送一次消息，說明該發送節點已經離開網絡，此時應對網絡結構進行調整。心跳次數表的數據結構為《備份節點未發消息次數、前趨節點未發消息次數、后繼節點未發消息次數》。

2）群節點數據結構 群節點是子環內的節點，在一個子環內除群首節點和備份節點上，其余節點均為普通節點，其數據結構主要由子環路由表、資源訪問次數信息表和附加信息表組成。①子環路由表：與原Chor d模型路由定義方法一致。②資源訪問次數信息表：通過資源的訪問次數來確定該資源是否為熱點資源，若為熱點資源，就將其索引信息寫入群首結點，其數據結構為《資源號、資源被訪問次數》。③附加信息表：其主要記錄子環中群首節點和備份節點的相關信息，為網絡結構的調整提供信息。

3）備份節點數據結構 備份節點的主要功能是備份所在子環中群首節點的信息，當群首節點離開網絡時將備份節點調整到主環，取代當前子環群首節點的功能，其數據結構包括子環路由表、資源訪問次數信息表和群首節點備份表。子環路由表和資源訪問次數信息表與群節點的結構一致，不需重新定義。群首節點備份表用來備份當前子環群首節點的主環路由表、熱點資源信息表和心跳次數表。如果存在一個子環中只有1個節點，則該子環中只有群首節點，沒有其他類型的節點。

3 改進Chord模型在遠程教育系統的應用

3.1 基于改進Chord模型的遠程教育系統

現代遠程教育是隨著現代信息技術的發展而產生的一種新型教育方式［5］，目前中小學的網絡帶寬有限，特別是農村中小學的校園網絡帶寬更低［6］。由于教育資源網絡的層次性、動態性和異構性特點［7］，遠程教育系統采用改進的Chor d模型結構，根據區域的不同，選擇多個區域中心服務器，系統中讓多個節點同時承擔中心服務器的功能。按照區域將計算機分組，每個區域選出一個群首節點作為區域中心服務器進行分組管理，區域中心服務器的功能主要是維護所在區域的在線計算機，區域內的所有計算機都需要在區域中心服務器上注冊，并且退出網絡時，還需要發送消息告知區域中心服務器自己需要離開網絡，區域中心服務器注銷該節點的信息，并將消息傳送給其他節點。遠程教育系統的備份服務器在區域中心服務器失效時代替區域中心服務器的功能，具體的遠程教育系統構建方式如圖1所示。

在該遠程教育系統中，任何一臺計算機都有可能成為服務器，也都有可能成為客戶機。根據遠程教育系統的工作流程一般將遠程教育系統分為遠程教育系統管理模塊、電子白板教學模塊、課堂實時交流模塊、在線練習模塊、遠程教育資源下載模塊和評價反饋等模塊。基于新模型的遠程教育系統可擴展性好，健壯性強，具有很高的資源利用效率，是遠程教育系統的有效解決方案。

3.2 基于改進Chord模型的遠程教育系統的資源搜索方法

基于改進Chord模型的遠程教育系統的物理網絡與邏輯網絡保持一致，并將熱點信息資源的索引信息保持在每個群首節點中，這種使得大多數的資源查找能夠在同一區域節點中完成，能夠有效的提高查詢效率。根據新的遠程教育系統的特點，資源查找需考慮不同搜索節點的類型，然后選擇不同的搜索算法實現資源查找。

由于模型中存在3種類型的節點，備份節點和普通節點的資源算法一致，群首節點采用單獨的搜索算法。因此，整個資源搜索分為以下2種情況：①如果提出搜索資源請求的計算機是區域中心計算機，則通過區域中心計算機搜索算法對目標資源進行搜索。②如果提出搜索請求的計算機是備份計算機或者是普通計算機時，首先通過單Chor d協議搜索算法在搜索計算機所在子環中搜索目標資源，如果子環中沒有目標資源則將查找消息發送到本地區域中心計算機，由區域中心計算機完成目標資源搜索。

上述搜索過程中子環內的計算機搜索目標資源方法與原Chor d模型搜索算法保持一致，區域中心計算機搜索算法相對較為復雜，其搜索算法如下：①首先在區域中心計算機的熱點資源緩存查找目標資源，如果發現目標資源，則返回目標資源計算機標識，搜索結束，否則轉下一步繼續搜索；②檢查當前子環區域中心計算機是否存在目標資源，有則返回當前區域節點計算機標識，搜索結束，否則繼續轉下一步；③按順時針方向發送搜索消息，遍歷整個主環上所有的群首結點及與每個群首結點相連的子環節點，遍歷過程中如果發現目標資源信息，查詢自動結束；④如果遍歷完主環和子環的所有的計算機，沒有發現目標資源，則返回未發現目標資源的消息。

圖1 基于改進Chor d模型的遠程教育系統

3.3 性能分析

為了比較基于改進Chor d模型的遠程教育系統與基于原Chord模型的遠程教育系統的性能，筆者選擇查詢延時作為主要性能評價指標，對新舊系統進行了多次比較，基于改進Chor d模型的遠程教育系統的性能良好，平均查詢延時值明顯變小，具有明顯的優勢。表1顯示了5組不同計算機數量的的查詢延時對比。表1數據表明，改進的Chor d模型更加符合當前遠程教育系統的實際情況，弱化了遠程教育系統服務器的功能，并有效的改善了遠程教育用戶間實時交流和資源利用問題。改進Chor d模型的應用實現了遠程教育資源高效率查詢，提高了遠程教育系統的服務質量。

表1 新舊系統平均查詢延時對比

［1］張文，趙子銘.P2P網絡技術原理與C＋＋開發案例［M］.北京：人民郵電出版社，2008.

［2］盧衛青，張振宇 .基于物理拓撲的雙向搜索Chord路由［J］.計算機工程，2009，35（22）：117－118.

［3］張建偉，劉思 .基于蟻群優化算法的Chor d模型［J］.計算機工程，2012（4）：100－103.

［4］王焱.P2P網絡的資源搜索方法研究及其在遠程教育系統中的應用［D］.武漢：湖北工業大學，2011.

［5］陳平平，譚定英 .完全對稱的P2P技術在高校遠程教育中的應用研究［J］.計算機工程與設計，2010，31（7）：1495－1499.

［6］劉方愛 邢長明 .教育資源共享網絡體系結構及其關鍵策略［J］.計算機科學，2009（9）：96－99.

［7］陳坤，劉方愛，邢長明 .一種基于分層P2P結構的教育資源網格檢索模型［J］.山東大學學報（理學版），2008（11）：72－76.