郑晓健，马晨誌

（1.昆明理工大学津桥学院电气与信息工程学院，云南昆明 650106；2.University of Wisconsin-Stevens Point，Wisconsin Stevens Point 54481，United States of America）

0 引言

近年来保障P2P 网络资源的持续有效性问题受到关注［1-3］，由于P2P 网络的节点自由地加入和退出网络［4］，使分布在网络中的资源经常处于不稳定状态，影响到网络服务的质量。尤其是节点的退出使网络中的资源量减少，资源需求节点获取资源失败，降低了系统的查询成功率，也影响到系统的可用性［5-6］。已有研究显示，采用资源备份技术可以提高查询成功率和可用性［7-8］。

混合型P2P 网络架构多采用被动式资源备份策略，通过系统服务节点监测资源节点发送的心跳消息来感知节点的在线状况，为了延续退出节点服务则通过切换到备份节点实现。研究表明此种方式在近99%的节点资源访问中有效，但也存在1.007%的访问失败情况。问题主要是既有方法对退出节点的发现机制不完善。系统服务节点发现节点退出的方法是定期（一般在每个监测周期结束时）检查是否存在超期未发心跳消息的节点。由于节点退出事件发生在系统服务节点监测周期内的某个时刻，该时刻至监测周期结束时系统发现节点的退出，中间存在一个时间差。如果节点退出发生在系统服务节点监测周期的开始阶段，加上转移节点服务到备份节点所耗费的时间，时间差值甚至会超过一个监测周期。在此段时间内退出节点的链接信息已经失效，需求节点按此访问资源将失败，本文将此现象称为颠簸问题（Bumpy problem）。实验显示，颠簸事件发生的几率低于1.007%，当局域网的规模较小，系统服务节点监测周期延长时颠簸事件发生率较高。

本文对颠簸问题进行了分析研究，提出一种基于资源环备份结构及节点状态监测的方法。将资源节点组织成为备份环，环上的节点在各自的心跳周期内对相链接的环节点随机发送问候消息，相互主动检测和回复在线状态。实验表明，该方法降低了被测节点的监测时间间隔，使检索盲区缩短，颠簸风险下降。

1 相关工作

颠簸事件发生的几率较低，相关研究较少。诸多研究在利用节点备份技术提高资源查询成功率［9-10］的同时，一定程度上降低了颠簸现象的发生。文献［5］提出感知服务质量的备份恢复算法，通过资源备份的分布情况和资源备份安全规则划分安全等级，给出分阶段资源备份恢复算法，结果表明，与直接资源备份恢复算法相比，可有效提高应用服务质量及数据安全保障能力；文献［6］采用主动策略查找稀有资源，通过获取资源的局部需求信息来备份资源，提高文件在网络中的流行度，从而提高稀有资源的查询成功率和可用性；文献［8］根据节点的存储能力和节点间的物理距离，选择存储空间充足和物理位置更近的节点备份资源，使维护消耗更低，检索成功率也得到改善；文献［9］将备份资源文件保存到在线时间更长的节点上，改善了网络资源动态变化时的适应性和服务质量；文献［11］提出动态备份资源分布式方法，按所设计的备份目录和信息获得资源的所有备份信息，对访问频率高和平均响应时间长的资源进行备份，提供用户访问特征和节点的实时带宽等信息，计算存放备份的节点，使备份的分布能够适应访问请求和网络带宽的动态变化；文献［12］提出将资源备份部署到网络中的骨干节点或骨干链路上，提高检索成功率。以上方法主要采用被动式方法备份文件，重点放在提高文件的检索成功率，能够改善系统检索性能并提高系统可用性，但由于P2P 网络所具有的动态性，备份节点随时可能退出网络造成资源检索失败，所以研究可持续且服务质量稳定的备份技术很有必要。

2 颠簸问题

P2P 网络中节点具有的动态性使网络资源文件的分布、数量及状况发生变化［13-14］，而节点呈现出5 种基本状态：加入态、在线态、刷新态、颠簸态和离线态，这些状态变化由相应的网络事件触发，其中颠簸状态为暂时性过程，随着节点的服务转移到备份节点上，原节点的服务将恢复，颠簸也将消失。本文进一步明确切换和颠簸的概念，分析颠簸的性质，根据相应性质提出减少颠簸的方法。

2.1 问题定义

设P=｛p1，p2，…，pi，…｝是网络中节点的有限集，1≤i≤n，n 为节点的总数目，∀pi∈P两次心跳的最大间隔时间为∆tq,0<∆tq。

定义1（切换）时间[t,th]内，t0时pi∈P退出网络，t+∆tq时pm∈P发现pi退出，系统将pi的服务转移到pb∈P，并在th时转移结束，则称时间[t0,th]内对pi切换或后切换。其中称t0∈[t,t+∆tq)为节点退出网络时间，同时也是切换开始时间，th为切换结束时间，[t0,t+∆tq]是节点退出发现期，(t+∆tq,th]是节点服务转移期，[t0,t+∆tq]∪(t+∆tq,th]⊆[t,th]是节点切换期。

定义2（颠簸）在时间[t,th]内对pi∈P切换期间，如果t1∈(t0,th]时∃pq∈P，请求pi的服务发生暂时性失败，则称pq在t1时产生颠簸。

2.2 颠簸事件性质

假设节点退出网络事件和资源需求节点的检索请求［15-17］相互独立。

性质1节点切换期间任何资源需求节点对该节点提出服务请求都将产生颠簸。

分析：设∀pi,pm,pb,pq∈P，∆tq是节点pm收到节点pi的心跳信号的最大时间间隔，t 是节点pm接收到节点pi心跳的时间，t+∆tq为节点pi的心跳到达pm的最大限制时间，th是节点pi的服务转移到节点pb的时间。

（1）若t0∈(t,t+∆tq]时节点pi退出网络，那么节点pm在[t0,t+∆tq]不会接收到节点pi的心跳消息。若t+∆tq时，pm仍然没有收到pi的心跳，pm将推断节点pi已经退出网络。

（2）在(]t+∆tq,th时段，节点pi的服务转移到节点pb，th之后节点pb接替pi提供资源服务。

（3）若在时间(t0,th]内∀pq∈P检索节点pi文件，那么由式（1）可知，在时间[t0,t+∆tq]内由于没有发现节点pi退出，所以检索到的还是节点pi的链接信息。另外由式（2）可知，在(t+∆tq,th]时间内，尽管已经发现节点pi退出，但还没有完成节点pi到节点pb的转移，所以不能提供pb的链接信息。因此在时间[t0,th]内，节点pq对节点pi文件的检索将失败。

性质2当节点退出网络时，访问该节点资源文件失败的概率与节点退出的概率密度函数以及节点切换期的长度有关。

分析：设∀pi∈P，节点pi退出网络的时间为连续型随机变量Q，Q 在(t1,t2)上的概率密度函数为f（q），t10。∃pq∈P向节点pi发送检索文件消息，检索时间为连续型随机变量R，R 在(t1,t2)上的概率密度函数为h（r），t1

在(t,t+ε)期间，网络中节点pq检索节点pi文件的概率为：

那么，在(t,t+ε)期间，当节点pi退出网络时，节点pq检索节点pi的文件概率为：

在式（3）中R 和Q 相互独立，即：

由性质1，(t,t+ε)时间段内如果发生对节点pi的检索事件，则检索失败。由式（4）可知检索失败的概率等于检索事件发生的概率，再由式（2）可知从节点退出网络到节点切换完成期间，检索节点pi中资源文件的概率与其概率密度函数、节点切换所用时间有关。

由此可知，检索的频度增加则颠簸的概率也会增大。

3 资源环备份结构

由颠簸的性质及其实验验证结果可知，假设节点退出事件随机性不变，由此颠簸发生的概率取决于切换期长度。采用资源节点的环备份结构，环节点间按链接关系在心跳周期内互发问候消息以相互监测，系统服务节点设置节点表和资源表，节点表用于保存环节点信息以供节点检索服务，资源表保存节点的资源文件信息以供资源检索服务。资源环备份结构如图1 所示。

Fig.1 Resource ring backup structure图1 资源环备份结构

3.1 节点加入环结构

节点加入网络分成两步：①节点加入资源环备份结构。建立节点与系统服务节点和首节点间的环链接，并以首节点为备份节点；②资源备份。节点的自治文件转存到备份节点。

节点加入环结构算法：

输入：节点pi，系统服务节点ps，首节点pb

输出：新系统环备份结构

（1）pi向ps发送请求插入消息Is；收到回复Rs后利用返回的信息pi向pb发送请求插入消息Ib；收到回复Rb后，在pi建立ps与pi和pb与pi链接信息，pi向ps发送请求刷新消息Us，转步骤（4）；如果未收到回复Rs||Rb，转步骤（5）；

（2）ps收到消息Is后，pb回复Rs；ps收到消息Us后查询和刷新节点表。

（3）pb收到消息Ib后，在pb建立pb与pi的链接信息，回复Rb。

（4）pi和pb开始交换资源文件，pb作为备份节点，返回加入节点成功。

（5）返回加入节点失败。

3.2 环节点间的监测与节点切换

与被动式监测模式不同，在环备份结构中每个节点监测相链接的2 个节点。节点在心跳周期内向相链接节点发送问候消息，收到消息后须立即回复，从而获知其在线状况，然后向系统服务节点通报被监视节点的在线状态；如果未收到问候的回复，环节点断定被监测节点已经退出网络，立即转换到备份并向系统服务节点通报。

环节点间的监测与节点切换算法：

输入：环节点pi，相链接节点pp，备份节点pn，系统服务节点ps

输出：节点在线状态

（1）pi心跳期内，pi向节点pp和pn发送问候消息H(p/n)。

（2）pp/pn收到消息H(p/n)后回复R(p/n)。

（3）pi收到回复R(p/n)后向ps发送L(p/n)消息，通报pp/pn在线。若pi未收到回复R(p/n)则向ps发送Q(p/n)消息，通报pp/pn退出。

（4）ps收到消息Q后更新调整节点表，反映新的环备份结构，安排新备份；ps收到消息L，刷新节点表。

环节点在每个心跳周期内向被监测节点发送一次或多次问候消息。如果环中有3 个及以上节点，则被监测节点可能会在其当前心跳周期内接收到两个及以上问候消息，因此各问候消息间的时间间隔小于等于心跳周期长度，所以利用环节点的心跳周期内的监测去发现节点退出，与系统服务节点的监测方法相比可以缩短监测盲区。

假设节点退出事件和对节点资源文件的检索事件独立，但并不能保证它们的交事件为空，即存在节点退出事件和对节点资源文件的检索事件同时发生的可能性。

性质3环监测中节点发生颠簸的概率小于等于系统服务节点监测时节点发生颠簸的概率。

分析：设节点在心跳周期中t∈[t0,tq]时接到相链接的环节点问候消息，所以[t0,t]⊆[t0,tq]，由概率的性质可知：

由式（5）可知，环监测中节点发生颠簸的概率小于等于系统服务节点监测时节点发生颠簸的概率。

4 实验结果与分析

4.1 实验设置

本节验证不同网络规模下［18-19］节点退出网络时检索该节点文件失败的概率与节点退出的概率密度函数，以及从节点退出到完成节点切换的时间关系。另外，用后切换与环备份节点间的监测与节点切换算法进行性能对比测试，以检验本文提出的环备份算法在降低颠簸事件中的有效性。本文测试平台采用Python 编程实现。

4.2 颠簸事件性质验证

为了呈现颠簸事件的特性，测试参数设置如下：节点心跳周期为1s，节点加入和退出网络事件在心跳周期内随机产生。随机挑选在线节点发送访问请求，访问事件产生频度为100 次/s，节点的切换时间设置5 组即1～5s，各种规模的测试时间为100s，测试节点数量设定为100～2 000，共20 组，颠簸事件测试结果如图2 所示。

Fig.2 Bumpy event test results图2 颠簸事件测试结果

测试结果证实了性质2 的结论，即在不同网络规模情况下，产生颠簸的概率与节点退出的概率密度函数以及从节点退出到完成节点切换的时间长短有关，而且当网络中节点规模较小而节点退出到切换到备份节点完成时间较长时，发生颠簸的几率较大，反之发生颠簸的几率较小，节点规模较大而访问频度不变时，颠簸几率较为接近，即当网络中节点规模逐渐增大时，节点退出到完成切换的时间即便较长，颠簸的增长会比较平缓。由此可以看到颠簸事件发生几率与检索事件发生率密切相关。

4.3 环备份监测算法有效性验证

为了验证环备份算法的有效性，将它与后切换进行比较。设置测试参数如下：节点加入和退出网络事件在心跳周期内随机产生，并且随机访问在线节点，系统服务节点的心跳周期和节点切换处理周期设为1s，各种节点规模的测试时间定为100s，且测试节点数量设定为100～2 000，共20 组，将访问节点频度分别为10 次/s、100 次/s、1000 次/s时，环备份和后切换发生颠簸事件的结果进行比较，测试结果如图3、图4、图5 所示。

由测试结果可以看出，后切换方法的颠簸发生率明显高于环备份方法，但随着访问频度的降低和节点数量的增加，两种方法颠簸事件的发生逐渐减少。实验证实了性质3 的结果，在不同网络规模下，环备份方法比后切换方法产生颠簸的概率明显要小。实验数据表明，颠簸事件平均降低50.894%。随着网络规模的增大，颠簸事件的发生几率在下降。另外，访问频度的实验结果对比也进一步证实了随着检索频度增加颠簸的概率也会增大。

Fig.3 Comparison of bumpy events between ring backup and post handover（1ms）图3 环备份与后切换颠簸事件比较（1ms）

Fig.4 Comparison of bumpy events between ring backup and post handover（10ms）图4 环备份与后切换颠簸事件比较（10ms）

Fig.5 Comparison of bumpy events between ring backup and post handover（100ms）图5 环备份与后切换颠簸事件比较（100ms）

4.4 算法的资源消耗和性能分析

环备份监测算法对节点的存储和网络带宽占用都有所增加。首先，每个节点要部署监测算法程序和工作存储，因此总的存储资源比后切换方式只在系统服务节点设置监测算法程序和工作存储时占用的存储量要大，两者存储资源占用为：Sc≈nSb，其中Sc为环备份监测算法对网络节点存储的占用，Sb为后切换方式占用系统服务节点存储，n 为网络节点数量。由于监测程序采用轻量化设计而且分散在各节点上，所以对系统性能影响不大。另外，由于环备份监测算法相互间要通过发送问候消息来监测节点状态，所以对网络带宽的消耗增加，在每个监测周期内相邻节点间的通信至少增加1 次，因此对网络带宽的消耗比后切换增加1 倍。

由图3、图4、图5 和测试数据可知，环备份的颠簸事件比后切换减少50.894%，性能提升明显。测试中也发现，随着网络规模的增加，需求节点对资源节点平均访问频率降低，两种方法的性能差距逐步缩小，但是环备份算法优势依然保持，表明算法性能稳定。

5 结语

为了提高非结构化P2P 网络［20］中资源文件的可用性，本文基于资源的备份技术，对节点的切换方法和产生颠簸的因素进行了研究。访问节点资源时颠簸事件影响着系统的可用性，而颠簸产生在系统服务节点监测节点状态时，退出节点的监测和节点的切换处理时段。为了减少颠簸现象发生，提出了一种环备份结构及其监测策略，实验结果证实，环备份结构及监测方法在降低颠簸事件发生上明显优于后切换方法。后续将在网络节点退出的预测方法和新的切换方法上深入研究，进一步减少节点颠簸现象和资源消耗，提高系统可用性。