一种基于文件路由表的移动P2P文件共享系统

樊里略 苏文莉，陈 佳

(遵义师范学院计算机科学系，中国 遵义 563002)

近年来，大量用户移动性应用的需求和移动应用环境的逐渐成熟，研究者开始关注具有更强分布性、更广参与性和更具有对等自治特征的移动P2P网络环境[1-5]．随着移动设备的逐渐增多，P2P系统作为目前Internet的重要应用，将在移动环境中得到更广泛的应用和发展．在有线Internet中，大多数P2P系统的操作都是依赖于节点间应用层的连接，形成一个应用层覆盖网[6]，通常这些连接都是静态的，只要系统中的两个节点之间保持着连接即可．而在移动环境下保持静态的覆盖网连接是不可能的，覆盖网拓扑不能反映底层移动网络拓扑．尽管覆盖网拓扑的节点在系统中的驻留时间内是静态的，但是因为节点的移动性，拓扑是频繁变化的[7]，这将会影响文件共享系统的性能．

本文通过分析移动P2P网络的特点，提出一种移动环境下的P2P文件共享系统(Mobile P2P File Sharing System，M-P2PFS)．P2P文件共享系统需要高效准确的文件搜索算法和稳定的文件传输协议，因此本文基于应用层覆盖网应用本地文件路由表进行文件搜索和文件传输，以保障节点准确的查询到所需文件并能完整的下载．

通常P2P文件共享系统的关键技术主要有2个：一是传输查询消息和搜索结果的文件搜索算法，另一个是下载匹配查询消息的文件传输协议[8]．文件搜索一直是P2P系统研究的热点之一，有线网络中典型的P2P系统如Gnutella 0.4采用完全分布式的文件搜索策略[9]，文件查找采用泛洪机制，随着查询请求的增加，消息数量呈指数增长，网络拥塞和带宽浪费严重，查询效率也得不到保障．尽管如此，Gnutella还是得到了广泛的应用和发展，很多研究提出了许多改进算法来减少洪泛算法的缺点，如Modified-BFS[10]算法在转发查询消息时不转发给所有邻居节点，而是随机选择k个邻居节点进行转发，这样来减小冗余信息．文献[11]的一种搜索算法称为Random Walk，查询者随机选取k个邻居来转发查询消息，然后邻居节点选取一个自己的邻居依次继续转发，使用这种搜索算法，在搜索过程中产生的消息数量显著减少．上述这些搜索算法都是基于参与节点能够保持静态连接的覆盖层网络．而与有线网络不同，在移动环境中，由于节点的移动性和系统中节点随时动态地加入和退出，系统覆盖层网络不能保持静态的连接．因此，传统有线网络中的P2P搜索算法不能直接应用于移动环境下．我们提出一种移动环境下P2P文件共享系统，应用节点的本地文件路由表进行文件搜索，完成文件传输，通过理论和实验分析可知该系统能保障节点准确的搜索到所需文件并能完整稳定的下载．

1 M-P2PFS中的文件搜索过程

M-P2PFS系统中每个移动节点维护一个本地信息库，由储存在本地系统中的文件组成．M-P2PFS为在信息库中的所有文件提供搜索功能．每个文件有一个独一无二的文件标示ID，另外每个节点维护一个文件路由表，用来为文件传输存储可选的下一跳．节点在查询处理过程中不断更新文件路由表．

在文件搜索过程中，定义两种类型的消息，一种类型是查询消息用Query表示，包括查询串，查询串由一个或者多个关键字组成，另一种类型是响应消息用Response表示，包括一个或多个匹配查询的文件标示ID．

由图1可以直观理解应用文件路由表的搜索过程．假设有5个节点1，2，3，4，5，当节点在彼此的无线传输范围之内时，就认为节点之间可以相互建立连接．每个节点有一个本地信息库和一个文件路由表．如图1所示，每个节点边上的上面的长方形表示本地信息库，下面的表示文件路由表．

(a) 节点1发起查询请求 (b) 节点2发送响应消息 (c) 节点3,4,5发送响应消息图1 文件搜索过程示意图

图1(a)显示节点1发起一个查询请求消息Query，Query包含了文件a，b，c，d的关键字，也就是节点1发起查找文件a，b，c，d的请求．查询消息Query的转发借鉴移动Ad hoc网络中的组播和广播协议，通过链路层洪泛分布到整个系统．节点2在搜索本地信息库后，发送一个包含了文件a和b标示(这里就用a和b表示文件的标识，文件c,d,e也一样)的响应消息给节点1方向的节点2的下一跳节点，这里即节点1，如图1(b)，节点1在文件路由表中保存文件a和b的路由信息，即在文件路由表中节点2作为文件a和b的下一跳节点．另外节点4和节点5分别发送包含文件b,c,d和a,b,c标示的响应消息给节点1方向的下一跳节点即节点2和节点3，如图1(c)所示．节点2接收到来自4和5的消息后，在转发响应消息之前，要对消息携带的文件标示进行检查，文件c和d是节点2没有的文件，则节点2在文件路由表中存储文件c和d的路由信息．因为节点2之前已经发送过带有文件a和b标识的响应消息，则这里只转发带有文件c和d标识的响应消息．节点1收到响应消息后，在文件路由表存储文件c和d的下一跳路由信息，即文件c和d的下一跳路由节点是节点2如图文件路由表所示c:2，d:2．节点3完成的工作同节点2类似，转发带有文件a,b,c标识的响应消息，因此节点1的文件路由表中文件a,b,c的下一跳节点又多了节点3可选．

从图1(c)可以看出，节点2的文件路由表中不仅存储了节点4作为文件c的下一跳路由节点，还存储了节点5，在文件路由表中增加冗余并不会增加额外的传输开销．在节点文件路由表中存储文件冗余路由信息是为了在节点移动的情况下，保证接收方能稳定地接收到完整文件，在文件传输过程中有详细介绍．文件搜索过程结束后，节点1选择匹配的文件下载．

2 M-P2PFS中文件传输过程

移动环境中，由于节点的移动，使得节点在下载文件过程中可能出现文件传输中断等现象，导致节点不能下载到完整的文件．因此，接收方能够在整个文件传输过程中保持对传输过程的完整控制是非常重要的．

本文提出一种文件分块请求传输协议，其基本思想是：把要传输的文件分隔成大小相同的块，文件接收节点沿着文件路由表提供的路由路径发送一个数据块请求消息，当请求消息到达一个本地信息库存有匹配文件的节点时，就返回带有该请求数据块的消息给文件接收者．文件接收者收到返回的数据块后，继续发送下一个文件数据块请求，直到整个文件被完整下载．

我们通过图2(a)来阐述文件传输机制．假设节点1要下载文件c．文件c的第一个文件数据块的数据请求消息发送到存储有文件c方向的下一跳节点，如节点1的文件路由表中所示，节点2和节点3．在有多个下一跳路由节点的情况下，根据节点之间的延迟来选择，优先选择延迟较小的节点，这里优先选择节点2．(文件路由表中，文件的路由信息按延迟进行排序如c:2,3，表示节点到文件c方向的下一跳节点2的延迟要比到节点3的延迟小)．节点2的本地信息库没有文件c，因此节点2根据本地文件路由表信息转发数据请求信息给文件c方向最适合的下一跳节点，这里选择节点4．节点4的本地信息库存有文件c，沿着节点1方向返回带有请求文件块的消息给下一跳节点，再由节点2转发给节点1．接下来节点1继续发送下一个文件c的数据块请求，直到整个文件被完整下载．

M-P2PFS中文件传输控制和数据传输都是在冗余路由中选择最适合的路由，由于在文件传输过程中会存在节点移动，或者节点的加入退出等，因此，文件路由表中的路由信息可能发生变化，这就要求能提供一种高效的传输机制来解决路由失败问题．

以图2(b)为例，假设在文件c的传输过程中，由于节点4发生了移动，不在节点2的通信范围之内了，节点2和节点4的链接失败．节点2一旦发现链路失败，就在本地文件路由表中删除节点4而发送文件块的数据请求消息给现在更适合的文件c的下一跳节点即节点5．因此，节点2在本地解决了链路失败问题，而没有影响到其他节点，这显然比通过发起全局路由发现来解决链路失败要好．而在文件接收者1节点看来，并没有感觉到文件传输过程中有链路失败．

(a) 节点1发起文件传输请求 (b) 节点4发生移动时的文件传输图2 文件传输机制示意图

3 系统性能分析

为了分析M-P2PFS系统的性能，我们用网络模拟器NS-2[8]设计模拟实验，同广泛应用的P2P文件共享系统Gnutella进行比较，主要比较两种系统中采用的搜索机制和文件传输机制的性能．

模拟实验参数设置见表1．总共设置60个节点，其中移动节点40个，移动节点的传输范围都设置为100 m，在一个900 m×900 m范围内，节点按Random waypoint移动模型进行移动，移动速度在[0,1]m·s-1之间平均选择．当节点到达一个随机选择的目的时，停留60 s，然后继续移动到下一个目的地．每个移动节点共享10个文件且节点每隔20 s发起一次查询请求．为了评估文件传输效率，随机选择一个节点执行100次不同文件的成功下载．

表1 模拟实验参数设置

P2P文件共享系统中，最重要的一个性能是文件搜索准确率，即对于一个查询请求返回的响应结果的质量评估．这里用接收到的标识唯一的文件数量同总共接收到的匹配查询的文件总数的比值来表示查询准确率．图3给出了文件搜索准确率的比较，纵坐标表示搜索准确率，横坐标表示移动共享系统中节点的数量．

从图3中可以看出，随着节点的增加，两种方法的文件搜索准确率都在增加，这是由于节点的增加使得系统的连通率增加，节点直接彼此通信的几率增加，因而文件搜索的准确性自然也会随之增加．但是在Gnutella中，节点增加到一定数量后出现了搜索准确率下降的情况，在前文我们提到过Gnutella的覆盖层网络是静态链接，没有考虑实际物理网路中节点的移动性，而当节点移动后，存在链路断开等问题，必然会影响到文件搜索的效率．

为了分析在文件传输过程中，由于节点移动可能导致的文件发送者发生改变时对文件传输效率的影响，这里比较了文件传输成功率，即节点成功完整的下载到的文件数与发起的文件传输请求数之比．图4给出了两种系统中随着系统中节点数量的增加，文件传输成功率的变化．

图3 文件搜索效率比较 图4 文件传输效率比较

从图4中可以看出，系统中节点较少时，由于系统连通率不高，两种系统的文件传输成功率都很低．随着节点数量的增加，M-P2PFS系统能够稳定完整地完成40%以上的传输，则其能够通过完成较多的文件传输为用户提供更好的满意度．

4 结语

本文在移动P2P文件共享系统中设计基于本地文件路由表的搜索机制和文件分块传输协议，解决了由于节点的移动性导致的传统有线网络中覆盖网静态链接的不足，使得在有节点移动的情况下，文件传输能自

适应调整，保证了文件下载的稳定性和完整性．通过模拟实验验证了M-P2PFS系统具有较好的性能，能保证较高的文件搜索准确率和文件传输成功率．在移动环境下的文件共享系统中，由于移动节点链路带宽非常有限，因此文件搜索和传输都不能过多的占用带宽资源，否则会造成网络拥塞等，因此下一步我们将研究系统的带宽消耗和移动环境下怎样有效地利用有限的带宽等网络资源的课题．

参考文献：

[1] 欧中洪, 宋美娜,战晓苏,等.移动对等网络关键技术[J].软件学报,2008,19(2):404-418.

[2] The washington times online. http://www.washshingtontimes.com/20040303-094741-3574r.htm.2004.

[3] 蔡俊亚.一种基于服务构件模型的自适应方法[J].湖南师范大学自然科学学报，2011，34(1)：48-51.

[4] MEIER R, CAHIIL V, NEDOS A,etal. Proximity-based service discovery in mobile ad hoc networks[J].Lecture Notes Computer Sci,2005,3545:1147-1149.

[5] ZHHN T, WINTER R, SCHILLER J. Simple, efficient peer-to-peer overlay clustering in mobile ad hoc networks:proc of the 12th IEEE Int’l Conf on Network Protocols, Washington DC, October 05-08[C]. Washington DC:IEEE Computer Society, 2004.

[6] WANG C, LI B. Peer-to-peer overlay networks: a survey[A].Technical Report, Department of Computer Science, HKUST, 2003.

[7] HUANG C M, HSU T H, HSU M F. Network-aware P2P file sharing over the wireless mobile networks[J]. Select Areas Commun, 2007, 25:204-210.

[8] SAROIU S, GUMMADI P K, GRIBBLE S D. A measurment study of peer-to-peer file sharing systems:proc of the multimedia computing and networking[C]. San Jose, SPIE, 2002.

[9] Gnutella[EB/OL]. http://www.gnutella.com,2001.

[10] KALOGERAKI V, GUNOPULOS D, ZEINALIPOUR-YAZTI D. A local search mechanism for peer-to-peer networks:proc of the 11th Int’l Conf on information and knowledge management[C]. New York: ACM Press, 2002.

[11] CHRISTOS G, MILENA M, AMIN S. Random walks in peer-to-peer networks: Algorithms and evaluation[J].Perform Evalu, 2006, 63(3):241-263.

[12] 徐雷鸣,庞 博,赵 耀.NS与网络模拟[M].北京:人民邮电出版社,2003.