浅谈基于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％。