淺談基于P2P的網絡教學系統節點信息收集算法

趙靜宇

目前,高等教育正處在向現代化、信息化發展的時代,網絡教學已經成為一種新的教學形式。網絡教學是基于Internet的一個平臺,其最基本的要求是將信息從教師端傳送到遠程的學生端,需要傳送的信息包括視頻、音頻、文本、圖片等數據,如何將這些信息資料有效地組織起來以達到更好的教學效果是網絡教學系統需要解決的一個重要問題。傳統的網絡教學系統大多數是基于C/S模式的,資源相對集中,當用戶過多時,存在服務器單節點失效、網絡帶寬瓶頸導致資源無法得到充分利用等缺陷,而基于P2P技術的網絡教學系統無疑是最佳選擇。

本論文通過模擬實驗分析幾類傳統節點算法的不足,得出網絡教學系統節點信息收集算法能有效地降低多余消息的產生,改善網絡運行環境。

一、TSNNIM算法的提出

在網絡教學系統中,需要查找大量的文本、音頻、圖像、視頻等信息,如何快速定位資源節點,是目前P2P網絡研究的主要課題。Flooding是應用在非結構化P2P網絡中的基本搜索方法。它具有響應時間短,搜索成功率高,可靠性好等優點;它的不足是會產生大量多余搜索消息,消耗帶寬等。根據泛洪和隨機漫步的特性,在此提出網絡教學系統節點收集算法(TSNNIM ,teaching system network node information-gathering method)。

二、TSNNIM算法原理分析

1.基本分析

對非結構化Gnutella系統進行的一項測試顯示:在Gnutella網絡中,95%以上的節點都可以在7 hops內被搜索到。相同請求消息可能被很多鄰居節點發到同一個節點上。除了第1個接收的消息,其余的都是多余消息。將一個請求消息經過的7hops分為兩個階段(低hops和高hops)。在低hops階段時,搜索覆蓋范圍相對廣,產生多余消息少;而在高hops階段時,情況相反。

任意一個拓撲圖形都可以以一個點為頂點將它變成一個金字塔結構。上面分析的結果也可以用金字塔狀結構想象出來。以發出請求消息的節點為頂點,將P2P網絡變為塔狀圖形。大部分的節點都在7層以內。在上層(低hops處),向外發送請求消息的節點數目相對較少,沒接到消息的節點相對較多。一個節點只從一個鄰居或很少鄰居處接收請求消息的情況比較多,一個節點向外發出請求消息而產生覆蓋面積相對比較廣,產生的多余消息比較少。在塔的下層(高hops),隨著越來越多的節點得到請求信息,一個節點越來越有可能從它多個鄰居節點處接收到請求消息,相對于請求消息的數量,請求消息的覆蓋面積變小,產生多余消息的數量大幅度的增加。

根據以上的分析,可以在上層對Flooding算法改進,限制多余信息產生;在下層當接收到請求消息的節點達到一定數量時,改用其他適當的搜索算法。級別相同的節點彼此間度數平衡。

2. TSNNIM算法

P2P網絡中每個節點都有網絡標示ID。每個節點都可以對它的鄰居節點進行不同的編號,區別不同的鄰居節點。當一個節點加入P2P網絡時,它會將自己的ID傳給它的鄰居節點,它的鄰居節點記錄該節點的ID,并為這個節點編號。同時它的鄰居節點也會將自己的ID傳給這個節點,這個節點記錄這些ID并分別為這些鄰居編號。這個節點再將它鄰居節點的ID和對它們的編號分別發給它的鄰居。它的鄰居節點也做同樣的步驟。圖l中將S,A兩個節點所存儲和標注的信息列在了表1中。

依據圖l和表l,當S節點向外發出請求消息。先向鄰居節點A,C發出請求。并且它會通知A節點不需要向C節點發出請求;它也會通知C節點不需要向A,D,F,H,I節點發出請求信息。當節點A接到請求信息后,如果需要向其他的鄰居節點發送請求消息,它會首先檢查看有沒有不需要發送的節點,發現節點C和節點S不需要發送。節點A只會向節點D,F,H,I發出請求信息;同時通知節點D不需要向節點C,F,H,I發送請求消息;同樣處理節點F、節點H和節點I。當節點C接到請求信息后,如果也需要向它的鄰居節點發送請求消息,它也會首先檢查看有沒有不需要發送的節點,發現節點S,A,D,F,H,I不需要發送,它沒有可發送的節點,就停止發送請求信息。其余的節點也這樣工作。

3. TSNNIM算法分析

假設每個節點都有k個子節點;計算利用上面的方法可以減少多余消息。任何一個節點和同層的其他節點相連或和下層的非子節點相連都會產生多余請求消息。如果一個節點與同層中的兄弟節點相連,利用上面的方法不會產生多余請求消息;如果一個節點與下層兄弟節點的子節點相連同時并與這個兄弟節點也相連,利用上面的方法也不會產生多余請求信息。

假設滿足一個條件:如果一個節點與下層兄弟節點的子節點相連,那么它就與這個兄弟節點相連。一個在m層的節點現在有多余的一條邊,這條多余的邊與同層節點或下層節點相連有 種可能性;滿足算法的條件,不產生多余請求消息的可能性有k+k2個。改進的比率就是(k+ k2)/( k + k( +1) )前3層總的改進概率是3*k/(k+ k2+ k3)*100%從上面的公式可以看出,當m和k增大時,改進的效率也隨之下降。雖然圖形和滿足的條件都是假設的,但是真實的圖形都是這種圖形的變形。改進的效率也是隨著圖形的變化而變化。但是無論什么圖形,都隨著m和k的增加,改進比率降低。

4.多點隨機漫步算法

當接收到請求消息節點達到一定數量時,改用隨機漫步算法。在網絡中,可以認為任何一個節點存儲一個文件的概率是相等的,一個節點存儲所希望的文件的概率是很低的,把它認為是小概率事件。但是當這樣的事件很多時,發生該事件的概率就會很高。例如,10 000個節點,每個節點可能有需要的文件的概率是0.001,那么根據伯努利公式1-p (q=1-p);搜索2400個節點能夠發現所需要的文件的概率是:1-C (0.001) (0.999) =90.9%。當一個節點使用隨機漫步向一個鄰居發送請求消息時,很難找到所需的文件,但是當很多節點同時向它們的鄰居發送請求消息時,發現的概率就會很高。例如:200個節點,各隨機漫步12步,可以近似的認為搜索了200×12=2400個節點。為了更有效的提高搜索命中率,可以把鄰居節點的度作為選擇鄰居的標準。

三、TSNNIM完整算法

步驟1 節點S首先列出可以發送到的網絡節點標示ID。

步驟2 列出它的一些不需要鄰居節點再發送的節點,確定這些節點分別屬于哪些鄰居。

步驟3 將請求信息分別發給鄰居,連同將不需要發送的節點也分別發給對應的鄰居節點,同時發送參數ttl=3和rdw=12。

步驟4 鄰居節點收到請求搜索消息時,它首先檢查消息ID看是否接收過這個請求消息,若沒接到過,標記這個請求信息ID,并檢查自己是否有所需的文件。如果有,回應請求節點。結束請求信息的發送。如果沒有,轉到步驟5。若以前接到過這個消息ID轉到步驟6。

步驟5 檢查傳來的參數ttl是否為0。若不為0,將m的標記減1。并查看是否有不需要發送的鄰居節點,若沒有,向鄰居節點發送請求消息;若有,去掉這些鄰居節點,再向鄰居節點發送請求消息,若ttl=0,轉到步驟6。

步驟6 查看參數rdw是否為0,如果是0,停止發送請求信息;如果不為0;將rdw減1。在可選鄰居中選擇度數最高的節點(若有兩個鄰居節點度數一樣高,按先進先出的規則),將這個選擇過的節點標為不可選節點。向所選的鄰居節點發送請求消息。如果已經沒有可選節點。停止發送請求信息。

四、系統驗證

模擬建立一個由10000個節點組成的P2P網絡。網絡中每一個節點和其他節點任意相連,各節點的度在2～10之間隨機的選取。將任意的一個節點作為源點向外發出請求信息。將要搜索的文件任意的放到10個節點上。分別用TSNNIM算法和泛洪算法搜索文件。改變不同的參數,比較兩種算法。在前4層上TSNNIM算法相對于泛洪算法在產生多余消息方面的改進比率是減少的多余消息比上Flooding算法產生的多余消息再乘以100%。在整個7層,比較本文提出的選擇算法相對于泛洪算法在產生搜索消息數量上的改進比率是選擇算法產生消息數量比上Flooding算法產生消息數量再乘以100%。從圖2中可以看出,在前4層,隨著節點平均度的增加,TSNNIM算法的改進比率也在增加。這主要是因為在網絡內節點數目不變化的情況下,單個節點的平均度增加,有利于不產生多余請求信息。同樣可改變節點的數量,其他參數不變。

從圖3可看出，改進的比率隨著節點數量的增加而下降，這可以理解為節點數的增加不利于限制多余消息的產生，或理解為k的增大導致了改進比率的下降。

從試驗數據可以看出，與FIooding相比較，TSNNlM算法的改進比率是7.1％。這個效率不是很高，但是在前4層產生的多余消息不是很多的情況下，降低后產生的多余消息是可以接受的。在整個7層上，使用本文提到的TSNNIM算法和Flooding算法在搜索文件時產生搜索消息的量進行比較，可以測得TSNNIM算法的改進比率是12.5％。

從圖4上可看出，改變節點的平均度，當節點的數量一定時，搜索成功率隨著節點平均度的增加沒有明顯的變化規律。這說明節點的度變化不明顯時，對搜索成功率不會有很大的影響。圖5顯示，隨rdw增加搜索的成功率也在提高，在rdw=12時，搜索成功率達到了85％。