一种无线mesh网络下P2P-VoD系统的资源查询算法

姜慧霖

(商丘师范学院计算机与信息技术学院，河南 商丘 476000)

0 引言

随着宽带网的普及，流媒体作为互联网中重要的数据业务而被广泛应用[1-7]。传统中心化服务器/客户端的系统模型受限于服务器带宽资源，无法满足大规模增长的用户需求，从而限制了流媒体业务的大规模应用[8]。P2P(Peer-to-Peer)技术很好地解决了上述问题[9]。网络中节点之间相互共享本地存储的流媒体资源能够大大减少服务器端带宽的压力。无线移动网络作为下一代网络的发展趋势之一，无线移动网络的流媒体技术已经得到了国内外众多学者的广泛研究[10-12]。无线mesh网络作为一种重要的无线移动网络，提供了一个低成本的Internet接入方式，通过增加mesh路由器的方式扩大无线网络的覆盖范围，多跳接入的方式使得mesh网络具有良好的可扩展性[11-12]。根据mesh网络的特性，这种快速便捷的接入Internet方式使得mesh能够为移动或非移动设备提供多种服务。然而，在大多数P2P-VoD(Peer-to-Peer Video-on-Demand)系统中[6，11]，为了支持用户的VCR操作，通常利用Gossip协议来查询用户所需要的资源。基于Gossip协议的资源查询方法不仅效率低(增加用户的播放等待延时)，而且会导致网络中散布着大量的查询消息，从而增加网络的负载。例如，文献[13]提出了一个在无线Ad Hoc网络下基于P2P的资源共享系统。该系统通过维护覆盖网络中节点行为能够提高资源共享效率。然而，通过交互消息维护移动节点，系统需要消耗大量的计算资源和带宽资源，同时泛洪的资源查询策略也加重了网络的负担。文献[8]提出了一个mesh网络下资源分享系统MESHCHORD(视频资源是一种特殊的资源)，利用位置感知技术，将位置相近的mesh路由器组织成为一个Chord结构。当移动节点查询所需要的资源时，通过Gossip协议散播查询者的查询消息，并利用跨层技术[8]，使每个移动节点在接收到查询消息后将该消息从数据链路层直接传递至应用层，从而判断是否能够为查询者提供服务。虽然MESHCHORD提高了资源查询效率并降低了网络的负载，但它也无法很好地解决Gossip协议所带来的查询效率低以及网络负载高的问题。

针对基于Gossip协议的资源查找算法中存在的不足，本文设计了一个mesh网络下P2P-VoD系统的资源查找算法。受文献[7]中资源分享系统结构的启发，本文所提出的算法也采用两层结构。如图1所示，利用Chord协议[7]和每个mesh路由器之间的物理距离(物理空间中的欧氏距离)来计算 key值(mesh路由器的位置可由“位置感知”方法获得，如文献[7]中所述)，将mesh路由器组织成为一个Chord环[14]，并作为顶层逻辑结构。环中每个元素的前驱与后继均与当前元素在物理空间中的距离最近;移动节点为底层结构。利用跨层的思想，当每个移动节点进入到一个mesh路由器的覆盖范围内时，该移动节点将自身所携带的资源信息发送给该mesh路由器，mesh路由器就能在本地构建一个可利用的资源列表。当移动节点需要查询资源时，将查询消息首先发送给mesh路由器，由mesh路由器为其查找距离最近且拥有资源的服务节点。

图1 两层的P2P-VoD系统

1 P2P-VoD系统设计

mesh网络下P2P-VoD系统中通常包含移动节点、mesh路由器及流媒体服务器等元素。

(1)移动节点不仅能够在物理空间中实现随机的位移，而且还能够通过一跳或多跳的方式接入并获取流媒体资源。当移动节点进入到mesh路由器的覆盖范围内，需要向mesh路由发送消息。如图2所示，根据跨层思想，移动节点除了要向mesh路由器提供本身的节点信息外，还需要提供本地存储的可利用的资源信息，也就是说，移动节点所传送的消息中不仅包含了自身IP层的信息，也包含了应用层的信息。每个移动节点Ni可以由一个三元组node=(IP，Res，MRIPL)表示，其中IP为移动节点的IP地址;Res为本地存储的资源，MRIPL为mesh路由器IP列表，表示移动节点位于MRIPL中元素的覆盖范围内。当Ni离开mesh路由器的覆盖范围后，也需要向该路由器发送离开消息。因此，移动节点进入或离开mesh路由器的通知消息emessage可被定义为一个二元组emessage=(flag，node)，其中flag为节点行为的标志位，当flag=0时，表明当前移动节点进入到mesh路由器覆盖范围，若flag=1，则表明当前移动节点离开mesh路由器覆盖范围;node为节点信息三元组。

图2 跨层示意图

(2)mesh路由器主要负责管理覆盖范围内的移动节点，并且接收来自于移动节点的请求消息，帮助移动节点查找请求的资源。可设MRS=(mr1，mr2，…，mrn)为一个非空有限集合，其中MRS为mesh路由器集合。每个mesh路由器mri都维护着一个三元组 mr=(IP，NL，chordT)，其中 IP 为 mesh路由器的IP地址;NL为在其覆盖范围内的移动节点列表，NL=(node1，node2，…，nodem)。chordT=(MI1，MI2，…，MIk)为mesh路由器需要维护的Chord结构信息，且，其中，IP 为 mesh路由器的IP地址;ResL为mesh路由器的资源列表，该列表通常由各个mesh路由器通过交互消息定时更新;key为mesh路由器的关键字，key的值由公式(1)得出:

其中DHT()为构建Chord环的分布式哈希函数[10]，该函数能够确保key在Chord环中的唯一性。dis为两个路由器之间在物理空间中的欧氏距离，其值可由公式(2)得出:

MRS中所有元素均可根据两个元素之间的物理距离来计算每个元素的key，并构建成为一个Chord环。此处构建一个基本的Chord环，具体的构建过程不再赘述。基于物理空间的欧氏距离来构建Chord环，主要是因为在无线网络中，通信双方的距离越近，在两者之间的通信路径上的中间节点越少，若两者均在彼此的信号覆盖范围内，那么两者之间则无中间节点(即一跳到达)，通信质量及数据传输效率即为最优。若存在多个资源拥有者，那么与请求者之间拥有距离最近的物理距离者为最优服务源。移动节点的请求消息req由一个二元组表示，即req=(IP，res)，其中IP为请求节点的IP，res为请求节点所需要的资源。

mesh路由器尽可能地为请求节点查找与其距离最近的mesh路由器下的资源拥有者。mesh路由器的返回消息resp中包含了含有请求资源节点的IP地址列表，即 resp=(IP1，IP2，…，IPk)。因此，mesh 路由器利用构建的Chord结构实现通信双方之间的物理距离最短，如图3所示。

图3 mesh网络资源共享示意图

(3)流媒体服务器主要负责为请求节点传输源数据。若在P2P网络中没有可利用的节点为资源请求者提供服务，则由服务器为该请求节点传输数据。则，video=(res1，res2，…，resm)，为一个非空有限集合，其中video为服务器中存储的流媒体资源集合，包含了m个流媒体资源。

2 流媒体资源的查询算法

下面将详细描述资源查询算法:

(1)当节点nodei需要获取资源resi时，根据三元组中存储的当前mesh路由器的IP地址向其发送请求消息reqi。

(2)mesh路由器mri收到reqi后，首先遍历本地的资源列表NL。若NL中存在能够满足nodei请求的资源拥有者nodej，则将nodej加入到结果集合resultset中。遍历结束后，将resultset中元素添加至返回消息resp中，并返回至nodei，执行(6)。

(3)若mesh路由器无法从本地查找出能够满足nodei的资源，则遍历chordT。遍历的优先级顺序为根据key值由小到大遍历。

(4)若chordT中包含了nodei所请求的资源，则mri将reqi转发至拥有该资源的mesh路由器mrj，由mrj为nodei查找拥有资源的移动节点，并将查询结果添加至resp中，并返回至nodei，执行(6)。

(5)若chordT中未包含nodei所请求的资源，则将reqi转发至chordT中 key值最大的元素 mrx，由mrx查找其余个mesh路由器。若查询成功，则将查询结果添加至resp中，返回nodei，执行(6);否则，通知nodei查询失败，由nodei请求服务器提供资源，执行(7)。

(6)nodei收到resp后，逐一向resp中元素发送连接请求，并准备接收数据。

(7)结束。

3 实验结果及分析

系统的仿真实验在NS2下完成。移动节点数量为500，在x=2000，y=2000的区域中随机移动，每个移动节点的无线信号覆盖范围为200单位距离，移动速度在0到20单位距离/秒随机分配，节点的移动方向为随机且停留时间为1秒，每个节点的带宽设置为2Mbps。在仿真中，系统设定100个节点随机请求不同资源;媒体服务器的数量为1;mesh路由器数量为9，信号覆盖范围为400单位距离;流媒体服务器中包含了20个资源，即m=20;mesh路由器与服务器的带宽分别为6Mbps和11Mbps;每个数据流的速率为450kbps;系统定义的4种消息大小均为500字节;仿真时间为300秒。本文从流媒体数据传输平均延时和丢包率以及资源查询响应时间3个方面与文献[7]进行了对比，并且设定两个系统的仿真环境相同。

图4 流媒体数据传输平均延时对比图

图5 流媒体数据传输平均丢包率对比图

图6 流媒体资源查询平均响应时间对比图

如图4所示，随着请求节点的数量不断增加，两个算法的流媒体数据传输延时也在不断增长。从曲线的高度及增长幅度来看，本文提出的mesh网络下P2P-VoD资源查询算法要明显低于MESHCHORD。这是因为mesh路由器能够为请求节点查找与其物理距离最近的资源拥有者，在数据传输过程中，数据所经历的中间节点数量(即数据被转发的次数)较低，从而数据传输延时也较低。MESHCHORD则通过Gossip协议泛洪查找资源，无法区分资源拥有者之间距离上远近。因此，MESHCHORD的曲线要高于本文所提出的算法。

如图5所示，根据在数据传输过程中统计每10个节点请求资源的传输的数据总量及丢失的数据包个数之比。本文所提出的算法在平均丢包率上也要好于MESHCHORD。这也是因为mesh路由器能够为请求节点查询与请求者距离最近的服务节点，近的物理距离能够减少数据在传输过程中的转发次数，从而减少了丢包率。图4与图5的数据是一致的。

图6显示了统计每10个请求的查询响应时间的平均值。在本文所提出的算法中，最好情况为若当前mesh路由器含有请求的资源时，则立刻返回至请求节点。最差情况为通过ChordT中key值最大元素查找全表的资源，请求被转发3次。而MESHCHORD依赖于Gossip协议进行泛洪查找，则查询响应时间无法被严格地限定。若资源与请求节点距离较远，那么泛洪消息需要经过多个节点散播才能被资源拥有者发现。若资源在其周围一跳范围内，则请求节点也可立刻获得所需要的数据。然而，所需要的资源存在一跳范围内的概率较低，因此，泛洪方法在查询效率上显然低于本文所提出的方法。

4 结束语

本文设计一个在mesh网络下P2P-VoD资源查询算法，主要用来解决在无线网络环境下使用Gossip协议进行资源查询所带来的查询效率低的问题。通过感知mesh路由器在物理空间中的位置，利用DHT算法将其组织成为一个Chord结构，不仅缩短了对资源请求消息的响应时间，而且减少数据的发送者和接收者之间的距离，提高数据的传输效率，减少数据传输的等待时延。下一步工作将提高流媒体数据在异构网络中的传输性能。

[1] Shen Z，Luo J，Zimmermann R，et al.Peer-to-peer media streaming insights and new developments[J].Proceedings of the IEEE，2011，99(12):2089-2109.

[2] 李海明，徐敬，黎燕飞.基于P2P视频点播技术的流媒体平台设计与开发[J].计算机与现代化，2011(4):57-60.

[3] 戴琦，夏青，顾春华，等.基于P2P的视频点播系统的设计与实现[J].计算机与现代化，2010(8):44-46.

[4] 袁雪萍，周芳，陈璐.基于Gossip协议的P2P流媒体算法优化[J].计算机与现代化，2010(10):139-141.

[5] 夏敏，吴中海，杨雅辉，等.基于Darwin的集群流媒体服务器系统的设计与实现[J].计算机与现代化，2009(5):19-22.

[6] Zhang X Y，Liu J C，Li B，et al.CoolStreaming/DONet:A data-driven overlay network for peer-to-peer live media streaming[C]//Proceedings of IEEE 24th Annual Joint Conference on Computer and Communications Societies.2005:2102-2111.

[7] Xu T Y，Chen J Z，Li W Z，et al.Supporting VCR-like operations in derivative tree-based P2P streaming systems[C]//Proc.of IEEE International Conference on Communications，2009.2009:1426-1430.

[8] Da Hora D N，Macedo D F，Oliveira L B，et al.Enhancing peer-to-peer content discovery techniques over mobile Ad Hoc networks[J].Computer Communications，2009，32(13-14):1445-1459.

[9] Oh H R，Wu D O，Song H.An effective mesh-pull-based P2P video streaming system using Fountain codes with variable symbol sizes[J].Computer Networks:The International Journal of Computer and Telecommunications Networking，2011，55(12):2746-2759.

[10] Tran D A，Minh Le，Hua K A.MobiVoD:A video-on-demand system design for mobile Ad Hoc networks[C]//2004 IEEE International Conference on Mobile Data Management.2004:212-223.

[11] Canali C，Renda M E，Santi P，et al.Enabling efficient peer-to-peer resource sharing in wireless mesh networks[J].IEEE Transactions on Mobile Computing，2010，9:333-347.

[12] 朱晓亮，王丽娜.无线Mesh网流媒体传输速率控制策略及模型[J].计算机应用研究，2009，26(3):991-993，1009.

[13] Klemm A，Lindemann C，Waldhorst O P.A special-purpose peer-to-peer file sharing system for mobile Ad Hoc networks[C]//IEEE 58th Vehicular Technology Conference.2003，4:2758-2763.

[14] Stoica I，Morris R，Karger D，et al.Chord:A scalable peer-to-peer lookup service for Internet applications[C]//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.2001:149-160.