基于流行度及最小访问代价的MP2P协同缓存优化策略＊

周欣欣，余镇危

（1.中国矿业大学机电与信息工程学院，北京100083；2.东北电力大学信息工程学院，吉林 吉林132012）

1 引言

随着无线通信技术的快速发展、移动设备性能的不断提高与普及，移动用户随时随地交换和处理信息成为现实，结合无线技术和点对点P2P（Peerto－Peer）计算的移动对等网 MP2P（Mobile Peerto－Peer Networks）成为了当前无线网络的研究热点。然而，由于移动网络环境所固有的缺陷和特点，如节点的频繁移动、移动设备能量和资源的短缺、无线连接的不可靠以及有线的通信带宽等特点，为移动P2P网络带来了巨大的技术挑战，如何在移动P2P网络上实现高效的数据存取是一个非常值得研究的问题。研究表明，高效的协同缓存策略能够大大降低用户的反应时间和服务延迟、减少网络通信开销、节省移动设备的电能消耗、增大网络的吞吐率，既提高了移动数据访问的性能，又增加了网络的可用性。因此，有必要针对移动P2P网络的特点设计适合的协同缓存策略。

鉴于此，本文针对移动P2P网络，提出一种基于数据流行度的分布式协同缓存优化策略，其主要思想是：通过计算数据的流行度以及获取数据的访问代价，节点优先缓存那些具有较高流行度，并且能够使网络访问代价最大程度降低的数据。同已有的缓存替换策略相比，该算法通过节点间的协作缓存，降低了全网数据访问代价，从而提高了网络数据的吞吐量，提高了网络的可用性和可扩展性。

本文组织如下：第2节给出相关工作，第3节给出问题定义及分布式缓存优化策略，第4节是仿真实验及结果分析，第5节是结束语。

2 相关工作

所谓协同缓存（Cooperative Caching），即通过将“热点”信息缓存于不同的节点，移动用户可以仅通过访问周围最近的缓存节点获取服务而省去了访问信息源节点的消耗，从而大大降低网络开销，提高网络数据存取效率。

Nuggehalli P等［1］证明了求解最优缓存放置机制是一个NP完全问题。Tang B等［2］证明了在缓存空间大小的限制下，求解最优缓存放置机制同样是一个NP完全问题。牛新征等［3］利用蚁群算法中蚂蚁通过信息素留存寻找最优路径的机制，构造了基于信息素的缓存替换模型。Acharya［4］提出了PIX策略，通过计算数据信息的访问频率和广播频率的关系得到数据替换函数，从而做出替换决定。Khanna［5］则基于访问趋势未知的假定提出了Gray替换算法，将数据访问历史和数据获取时间开销作为分析参数。文献［6～8］讨论了无线多跳网络中的缓存策略，但是他们的策略没有将数据在网间的流行度因素考虑进去。另外，其他缓存策略使用的类似树形的层次结构，或者网络中没有骨干节点，但这些策略没有充分考虑节点扰动因素，或者有些需要额外的基础设施支持。而本文提出的策略不需要任何额外的基础设施支持。

3 基于流行度及最小访问代价的分布式协同缓存优化策略

3.1 问题定义

网络模型定义为图G＝ （V，E），其中V ＝｛v1，v2，…，vn｝为网络节点集合，E是边的集合，边e＝ （vi，vj）∈E ，其中 （vi，vj）∈E表示节点vi、vj彼此在对方的无线发射范围内，其中每个节点v∈V有一定的缓存空间Cv（Cv为缓存片段个数）。

将文件分划为n个片段，记为S＝ （s1，s2，…，sn），其中：

定义1 定义流行度函数p（i）。设每个片段的流行度分别为p（1），p（2），…，p（n）。设To为系统的起始时间；T1（i）为片段i被首次访问的时间；Tr为系统当前时间；Ni为片段i自To以来被访问的总次数，则定义片段i的流行度p（i）＝Ni／（Tr－T1（i））。

定义2 定义节点v获取片段si的代价函数dv（i）。如果si存储在本地缓存中，dv（i）是0；如果某一节点w缓存了si，则dv（i）是从节点v到节点w的跳数；如果si是由内容服务器提供，则dv（i）等于内容服务器接入代价。

重新写出公式（1），定义K，令：

其中，D（i）是网络中所有节点获得片段si的平均代价。

定义3 定义标志函数Xv，w（i）。当节点v发现节点w 缓存有片段si，则Xv，w（i）＝1；否则为0。

定义4 定义标志函数Yv（i）。若节点v从内容服务器上获得片段si时，则Yv（i）＝1；否则为0。

定义5 定义代价函数zv，w是由节点v到节点w的跳数。

因此，重新给出D（i）：

由于每个节点要么从某一个节点获取特定片段，要么从内容服务器上获得，因此有：

缓存优化问题就转变成在约束条件下求最小片段访问代价函数，即：

3.2 分布式协同缓存优化策略

本节提出的协同缓存优化策略能够根据数据的流行度分布式地缓存数据。每个节点保持一个段路由表，类似于网络路由表，每个段路由表包含SEGMENT、NEXT＿HOP和COST 字段，如表1所示。SEGMENT是数据片段的ID。NEXT＿HOP是到达该片段的最短路径上的下一跳节点ID，如果该段是本地缓存，就记做LOCAL。如果该段在一定跳数范围内不能查询到，记为SERVER。COST是与路由相关联的代价花费：当下一跳是LOCAL（即片段在本地缓存中）时，COST为0；当下一跳是节点时，COST是到达数据提供者的总跳数（即缓存该段的最近的节点）；当下一跳是SERVER时，COST是一个常数，表示服务器访问成本。例如，在表1中，获取片段ID为2和3的成本分别是1和6。

Table 1 NODE 1segment routing table表1 NODE 1段路由表

当新节点加入网络时，要执行以下步骤：

步骤1 广播一个“加入”消息，通过收到邻居节点的应答消息，建立邻居节点列表，广播节点的段路由表。

步骤2 节点根据已知的段路由表计算到每个数据片段的最短路径，创建自己的段路由表，即若该节点的某一邻居节点以代价K获得片段si，则加入节点将以K＋1的代价获取si，并将下一跳设置为该邻居。除此之外，加入节点也可能通过访问内容服务器来获取该片段，服务器接入代价为α。加入节点只需在所有选择中找出最便宜的访问代价，并建立路由表项。

步骤3 加入节点也可能根据已知信息创建新的最短路径，在新的路由表中，若片段si相对应的成本为K，那么该节点的邻居节点将以代价K＋1获取si，并将下一跳设置为该加入节点，同时将更新信息发送给它的所有邻居节点。

步骤4 通过贪心算法，加入节点决定缓存哪些片段对自己及邻居最有利，即加入节点会选择那些能够最大程度降低网络访问代价的片段缓存。在计算缓存片段si后所降低的网络访问代价中，也考虑到片段si在网络中的流行度p（i）因素。

步骤5 如果一个加入节点决定缓存片段si，那么它能够以代价0来获取该段，并且它的直接邻居以代价1获取该片段。假设加入节点有m个直接邻居，则在加入节点本身以及它的邻居节点表中si的代价记做Ki0，Ki1，…，Kim。当计算完片段的流行度权重后，加入节点缓存si可以节省的访问代价为：

然而，如果一个邻居节点已经缓存了片段si，它的代价不应当再被进一步减少变成－1，而应当是0。将这种邻居节点的数目记做θi，则缓存si实际减少的代价Ri应当为：

公式（6）中的各个分量都能够从段路由表中得到，缓存每个片段所降低的代价都能够通过计算得到。目标是通过计算Ri，找到Maxmize Ri的片段进行缓存，从而达到降低网络整体访问代价，提高网络吞吐量和可用性的目的。

加入阶段和缓存阶段之后，节点定期发布它的段路由表。当其他节点侦听到这一发布信息后，以类似步骤3的方式通过交叉对比自己的表以及接收到的表来更新自己的本地段路由表，从而各节点做出缓存策略。

如果节点超过发布周期仍然侦听不到某一邻居节点，则认为该邻居节点失效或者已经离开网络。如果失效的邻居节点是该节点段路由表中的下一跳节点，则该节点通过重新计算形成新的段路由表。

节点的离开或失效可能导致段路由表的冲突。例如，当节点v侦听到节点w的发布信息，对于节点v的段路由表中NEXT＿HOP是节点w并且代价为K，但是在节点w发布的段路由表中，同样的片段代价可能会出现K－1或者更少的代价。在这种情况下，节点v中导致冲突的表项失效，需要重新计算并形成新的段路由表。

通过以上分析可以看出，无论是节点加入阶段还是发布阶段，节点的每个缓存决策对于整个网络来讲，都有一个至少是1的代价的降低。因此，作为节点的加入和通信，网络花费将会达到一个本地最小。另一方面，文中提出的分布式缓存策略不依赖于任何路由协议，可以在路由请求和应答消息中捎带段路由表信息，因此可以进一步减少整个网络的通信开销。

4 仿真结果分析

4.1 仿真环境

为了验证缓存优化策略的有效性，利用网络仿真软件NS－2对其进行了仿真实验。实验中，所有节点随机加入网络，并且节点的通信范围是固定的，每个节点的发布周期是固定的，网络规模为400m×400m的正方形区域，节点的移动符合随机停靠点（Random Waypoint）模型［9］，节点数目为100，节点的通信距离为30m，广播周期为1秒，节点平均生命周期为100分钟，每个文件分割片段数为15个，节点缓存片段数为4个，服务器获取数据代价为6。下面将文中提出的缓存优化策略与LRU和LFU算法进行分析比较。

4.2 仿真结果分析

在仿真实验中，分别对网络代价开销、平均时延、平均跳数以及缓存容量等进行性能上的分析比较。图1是三种算法的平均网络代价比较。从图1可以看出，随着网络节点数目的增多，文中所提策略的平均网络代价要小于另外两种算法，这是由于随着网络节点数量的增多，有更多的用户缓存和共享数据段。图2是数据访问平均时延的比较，可以看出，LRU和LFU两种算法的平均时延均要高于本文提出的算法。

Figure 1 Comparison of network cost图1 网络代价比较

图3 是获取缓存片段的平均跳数，结果显示，90%以上的缓存片段可以在本地或者一跳邻居处获得，因此可以大大减小网络开销以及延迟。图4是节点缓存容量对网络代价的影响，如图4显示，随着缓存容量的增大，网络平均代价开销显著降低，这表明文中提出的缓存策略具有较高的灵活性。

Figure 2 Comparison of average latency图2 网络延迟比较

本文提出的算法在缓存时考虑到片段的流行度以及所产生的网络代价最小等因素，能够将流行度高的数据优先缓存，并且要缓存那些能够最大限度减少网络代价花费的数据，因此在网络开销、访问时延等方面均获得了较好的结果。

5 结束语

本文提出了移动P2P网络协同缓存优化策略，该策略能够综合考虑数据在网络中的流行度因素，并且能够使全网数据访问代价最低，提高了节点数据获取效率，降低了数据访问时延，提高了网络可用性及可扩展性。仿真实验结果表明，文中提出的策略具有高效率、低成本及高可扩展性的特点，取得了较好的结果。

本文提出的算法对服务器获取数据代价采取了固定值，并没有对该服务器代价进行系统研究；另外，实验中没有考虑节点的任意加入和退出等网络的不稳定性对算法造成的影响，因此下一步的工作主要着重解决以上几个问题。

［1］ Nuggehalli P，Srinivasan V，Chiasserini C.Energy－efficient caching strategies in ad hoc wireless networks［C］∥Proc of the 4th ACM International Symposium on Mobile Ad Hoc Networking＆Computing，2003：25－33.

［2］ Tang B，Gupta H，Das S.Benefit－based data caching in ad hoc networks［J］.IEEE Transcations on Mobile Computing，2008，3（7）：289－304.

［3］ Niu Xin－zheng，She Kun，Qin Ke，et al.A cooperative caching optimized policy of mobile peer－to－peer networks［J］.Journal of Computer Research and Development，2008，45（4）：656－665.（in Chinese）

［4］ Acharya A，Alonso R，Franklin M，et al.Broadcast disks：Data management for asymmetric communications environments［C］∥Proc of ACM SIGMOD Conference on Management of Data，1995：199－210.

［5］ Khanna S，Liberatore V.On broadcast disk paging［J］.SIAM Journal on Computing，2000，29（5）：1683－1702.

［6］ Ting Y－W，Chang Y－K.A novel cooperative caching scheme for wireless ad hoc networks：Groupcaching［C］∥Proc of International Conference on NAS，2007：62－68.

［7］ Yin L，Cao G.Supporting cooperative caching in ad hoc networks［J］.IEEE Transcations on Mobile Computing，2006，5（1）：77－89.

［8］ Dogar F R，Phanishayee A，Pucha H，et al.Ditto：A system for opportunistic caching in multi－hop wireless networks［C］∥Proc of the 14th ACM International Conference on Mobile Computing and Networking，2008：279－290.

［9］ Burgess J，Gallagher B，Jensen D，et al.Maxprop：Routing for vehicle－based disruption tolerant networks［C］∥Proc of IEEE Infocom Bacelona，2006：1－11.

附中文参考文献：

［3］ 牛新征，佘堃，秦科，等.移动P2P网络的协作缓存优化策略［J］.计算机研究与发展，2008，45（4）：656－665.