淺談基于P2P的網(wǎng)絡(luò)教學(xué)系統(tǒng)節(jié)點(diǎn)信息收集算法

趙靜宇

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

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

一、TSNNIM算法的提出

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

二、TSNNIM算法原理分析

1.基本分析

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

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

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

2. TSNNIM算法

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

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

3. TSNNIM算法分析

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

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

4.多點(diǎn)隨機(jī)漫步算法

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

三、TSNNIM完整算法

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

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

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

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

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

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

四、系統(tǒng)驗(yàn)證

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

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

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

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