趙靜宇

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

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

一、TSNNIM算法的提出

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

二、TSNNIM算法原理分析

1.基本分析

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

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

根據(jù)以上的分析,可以在上層對Flooding算法改進,限制多余信息產(chǎn)生;在下層當接收到請求消息的節(jié)點達到一定數(shù)量時,改用其他適當?shù)乃阉魉惴?。級別相同的節(jié)點彼此間度數(shù)平衡。

2. TSNNIM算法

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

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

3. TSNNIM算法分析

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

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

4.多點隨機漫步算法

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

三、TSNNIM完整算法

步驟1 節(jié)點S首先列出可以發(fā)送到的網(wǎng)絡節(jié)點標示ID。

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

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

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

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

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

四、系統(tǒng)驗證

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

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

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

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