P2P网络是一种应用层的分布式网络，网络中各节点地位是对等的。按照资源组织与定位方法，可以将其分为结构化P2P网络^{[1, 2, 3]}和非结构化P2P网络^[4]。其中，由于非结构化P2P网络的简单性和高鲁棒性使其得到了深入的研究和广泛的应用。

以Gnutella为代表的非结构化P2P网络，是一种没有特定拓扑结构的覆盖网，通常建立在随机图上，使用基于洪泛的查询算法进行资源搜索。节点通常把资源存储在本地，也可将其备份到其他节点，以提高资源搜索的效率^{[5, 6]}。由于没有拓扑结构上的约束，在节点频繁加入和撤离的动态环境中，非结构化P2P网络表现出良好的性能，并且仅需较少的维护开销。由于每一次查询都是在本地进行评估，所以它支持任意复杂类型的查询，如语义查询等。非结构化P2P网络采用基于洪泛的查询机制进行资源搜索。在洪泛的过程中，节点在有限的TTL内，不断地向所有的邻居节点转发消息，直至查询到所需的结果或TTL变为0。洪泛的优点是响应时间短、覆盖范围广以及可靠性高，但洪泛会在网络中产生大量的冗余消息，不仅增加了节点处理负担，还会占用大量的网络带宽^[7]。因此，如何在有效进行资源搜索的同时，降低冗余消息量，提高系统的可扩展性和稳定性，是非结构化P2P网络的一个核心问题。

针对上述问题，许多研究工作者尝试通过改进洪泛算法^{[8, 9, 10, 11]}，以提高非结构化P2P网络的可扩展性。这些方法不再盲目地向所有邻居节点转发消息，而是有策略地选择部分邻居节点转发消息。例如，随机漫步算法^[12]每次随机选择k个邻居节点转发消息，其搜索过程持续至查询到所需的结果或TTL变为0。这样就减少了洪泛搜索产生的网络流量，但另一方面往往会产生较大的搜索延迟，并且搜索过程有可能丢失节点。另外一种优化策略是通过改变P2P网络结构，以达到提高搜索效率的目的，其典型如树形结构的P2P网络^{[13, 14, 15]}。在这样的系统中，由于网络结构为树形，洪泛时消息到达任意节点仅一次，从而避免了冗余消息的产生。如果树的拓扑结构是稳定的，且消息丢失率较低，则树形结构的P2P网络具有良好的性能。然而，在节点频繁加入和撤离的动态环境中，树的结构经常会被分割，造成大量消息的丢失。因此，为了获得良好的可靠性，树形结构P2P网络需要探测消息丢失并从中恢复，这会导致恢复信息的延迟。尤其当故障频繁发生时，还会引起相当大的开销，这些都会限制系统的可扩展性。树形结构P2P网络的另一问题是负载不均衡，树的内部节点承载了几乎所有的转发负载，而叶子节点却不分担负载。文献[16]提出，将非结构化P2P网络建立在结构化P2P网络之上，利用其结构提高洪泛的性能。文献[17]提出了一种基于生成树的洪泛算法，该算法保证遍历N个节点的系统只需要N-1个消息。但由于该算法基于chord^[3]，很大程度上受其协议的限制，生成树的度数较低，消息传播延迟较大。由于chord邻居表中每一个表项仅维护1个节点，故当节点失效时，洪泛会导致大范围的节点丢失。动态环境中，其性能和可靠性高度依靠底层chord 协议的维护能力。因此，由于协议的语义规定了覆盖网节点应如何连接，在结构化P2P网络上建立非结构化P2P网络的思想并不适合高度结构化的DHT协议。

为此，本文提出了一种改进的非结构化P2P网络洪泛搜索机制FIFSM(forwarding interval based flooding search mechanism)。此机制借鉴结构化网络的策略，为每一个节点分配唯一的标识符，并建立有结构的邻居表。此外，在洪泛查询消息(下文简称查询消息)中添加2个字段，用于限制节点的转发范围。FIFSM机制的实现主要包括2个部分：洪泛算法和网络维护策略。FIFSM洪泛算法通过为消息分配不相交的转发区间，使其沿着一棵生成树的结构传播，避免消息环路的产生，从而避免冗余查询消息。邻居表中添加了冗余节点，消息转发过程中，如果遇到失效节点，选择冗余节点转发消息，降低节点失效造成消息丢失的可能，以提高洪泛算法的容错能力。FIFSM采用高效的网络维护策略，通过3种任务周期性地维护覆盖网，保证了资源搜索的低延迟，提高了动态环境中资源搜索的成功率，使其维护开销随着节点变动率的增加而降低。

在FIFSM机制中，本文定义了标识符空间、邻居表、以及前向和后向节点。

FIFSM机制使用一致性哈希函数^[18]为节点分配一个m位的标识符，m必须足够大，以保证2个节点标识符是唯一的。标识符空间是以2^m为模依次排列的一个标识符圆环。在标识符空间中，以任意一个点x为中心，把距离x大小为2^m-1的点称作x的界点，记作M(x)。图1展示了以0为中心且m=3的标识符空间。

图 1 标识符空间

图选项

在FIFSM机制中，对任意节点x都要维护2个邻居表，分别记录标识符空间中顺时针和逆时针方向x到M(x)区间中的邻居节点。邻居表有m-1个邻居表项，其中，第i个表项包含变量start、end、interval和neighbors。start为标识符空间中与节点x相对距离为的标识符，end为标识符空间中与节点x相对距离为2ⁱ的标识符，[start,end]表示第i个表项所属的区间。interval为起点是2^i-1，终点是2ⁱ的区间，neighbors为第i个表项的邻居节点列表，其节点数受限于节点冗余度H。邻居表相关变量的定义如表1所示。

在FIFSM机制中，节点x除了要维护邻居表以外，还需要维护它的前向节点和后向节点。前向节点是节点x沿逆时针方向的第一个节点，记作predecessor(x)。后向节点是节点x沿顺时针方向的第一个节点，记作successor(x)。如图2所示，对于节点N₀，它的前向节点predecessor(N₀)=N₇，它的后向节点successor(N₀)=N₁。

图 2 环状拓扑结构

图选项

定义1 转发区间是标识符空间中的一段连续的区间，用于限制消息的转发范围。转发区间定义为 ，其中，LL是转发区间的左边界，RL为转发区间的右边界。

定义2 洪泛的消息定义为message(Info,LL,RL)，其中，LL和RL为消息中添加的2个m位的字段，表示消息的转发区间，Info表示消息的内容。

在传统的洪泛算法中，节点收到消息后，盲目地向所有邻居节点转发消息，导致消息的重复到达，产生大量的冗余消息。在FIFSM的洪泛算法中，节点收到消息后，仅向转发区间内的部分邻居节点转发消息，当转发区间内不存在邻居节点时，则停止转发。如图3所示，其中图3a)为节点之间的连接关系，图3b)展示了洪泛时消息的转发过程，图中的区间为节点的转发区间。例如，当节点5发起洪泛时，它选择邻居节点2，4，6，0发送消息，当节点2收到消息后，它向转发区间 中的邻居节点3转发消息。节点3收到消息后，发现转发区间中不存在节点，则停止转发，其他节点与之类似。从图中可以看出，节点之间的转发区间是不相交的，且每次转发后，节点不会出现在之后的转发区间中，保证了节点上消息的不重复到达，避免了冗余信息的产生。图3c)展示了洪泛过程中消息的传播路径。可以看出，消息的传播路径是1棵生成树，消息到达任意节点仅1次。

图 3 洪泛生成树的生成过程

图选项

FIFSM的洪泛算法不仅能实现全网洪泛，也可以针对特定的范围进行洪泛，本文称之为范围洪泛。

1)全网洪泛

对于当前节点x，分别从邻居表的每一个表项中选择一个邻居节点，对于从表项i中选出的邻居节点y，把表项i的start和end赋予消息m的LL和RL字段，并向节点y发送消息m。如果表项j不存在邻居节点，即neighbors为空，则将表项j所属的区间[start,end)并入下一个节点的转发区间中。

2)范围洪泛

对于当前节点x，在邻居表中找到一个目的范围［LL,RL)内的邻居节点y，向它发送一个封装了［LL,RL)的消息m，节点y收到消息m后就会在该范围内进行洪泛。

节点y收到消息m后，对于邻居表中属于转发区间［LL,RL)内的表项i，检查其neighbors是否为空，如果不为空，则从neighbors中选出一个邻居节点z，把表项i的start和end赋予消息m的LL和RL字段，向邻居节点z发送消息m。如果表项i不存在邻居节点，即neighbors为空，则将表项i所属的区间［start,end)并入下一个节点的转发区间中。

假设洪泛过程中消息的每一次转发都成功，且不存在失效节点，以下从节点丢失和消息冗余两方面进行算法可行性分析。

1)节点丢失节点x转发消息时，存在以下4种情况，如图4所示。在图4a)中，x的前向和后向节点都位于转发区间［LL,RL)中，在图4b)和图4c)中，x的前向或后向节点位于转发区间［LL,RL)中，对于这3种情况，x的前向和后向节点至少有一个位于转发区间中，所以节点x可以把消息转发出去，不丢失节点。在图4d)中，x的前向和后向节点都不在转发区间［LL,RL)中，由于前向和后向节点是离x最近的节点，因此［LL,RL)内不存在其他节点，节点x停止转发，不丢失节点。综上，该算法能够保证遍历所有的节点而不会出现节点丢失的现象。

图 4 消息转发的情况

图选项

2) 消息冗余

该算法保证了节点之间具有不相交的转发区间，且被访问过的节点不会出现在之后的转发区间中，从而保证了每个节点收到且仅仅收到1次相同的消息，不会产生冗余消息。

P2P网络的环境是高度动态的，需要在频繁加入和撤离节点时保证网络的稳定性。网络维护主要包括两部分：节点的加入和撤离以及邻居表的维护。

节点n加入网络时，需要通过外部机制联系到一个在线的节点，由该节点在全网洪泛一个节点连接请求。如果一个节点能够接受节点n作为邻居节点，则该节点就会直接发送回复消息给节点n，最后它们将对方添加到各自的邻居表中。在FIFSM搜索机制中，当节点y收到节点x的连接请求时，在如下2种条件之一发生的情况下，节点y会主动连接节点x：①邻居表项的节点数没有达到节点冗余度H;②节点x是节点y的前向或后向节点。

而节点n撤离网络时，会发送“leave”消息给它的邻居节点，当这些节点收到“leave”消息时，便将节点n从其邻居表中删除。

在动态环境下，邻居表中可能出现失效节点、前向和后向节点不一致以及空邻居表项，会降低FIFSM搜索机制的性能。为此，本文提出了3种任务，分别解决相应问题。其中，fault detector负责探测失效节点并修复邻居表，SP fixer负责维护前向和后向节点的一致性，connect task负责为节点增加新的连接。

1)fault detector

节点的故障撤离会导致邻居表中失效节点的产生，为了探测失效节点并修复邻居表，fault detector周期性地(60 s)向邻居节点发送“Are you there!”的探测消息，然后等待回复，如果在几次询问后仍未收到某个节点的回复，便向它发送“leave”消息，并把该节点从邻居表中移除。

2)SP fixer

节点加入网络后，由于网络的动态性，节点之间维护的前向和后向节点可能不一致。在图5a)中，节点a，b，c依次排列在节点标识符空间中，节点a维护的后向节点是c，而节点c维护的前向节点是b而不是a，即节点a的后向节点和节点c的前向节点不一致。这种情况下，节点a会在范围 内发起洪泛，当节点b收到消息后，发现节点a是自己的前向节点，则主动与节点a建立连接，这样节点a的后向节点和节点b的前向节点都实现了更新。同理，图5b)展示了节点c的前向节点的维护过程。

图 5 前向和后向节点的维护策略

图选项

3)connect task

在动态的网络中，节点的频繁撤离会造成节点邻居表中空表项的产生，即该表项的邻居节点数为0，不利于查询消息的高效转发，增加洪泛搜索的延迟。为了降低洪泛搜索的延迟，需要为邻居表增加连接。connect task会定期地检查邻居表中的每一个表项，并根据表项的邻居节点数进行相应处理。

1)当邻居节点数为0时，connect task会主动在该表项所属的区间［start,end]内洪泛。同时，接受来自其他节点的连接请求。

2)当邻居节点数不为0且小于H时，connect task不会主动洪泛。但它仍然接受来自其他节点的连接请求。

3)当邻居节点数达到H时，connect task既不主动洪泛，也不接受来自其他节点的连接请求。

为了评估FIFSM搜索机制的性能，本文在OMNET++^[19]仿真平台上，建立了FIFSM搜索机制的仿真模型(以下简称为FIFSM模型)，并进行了一系列的实验。实验中，我们采用大小为2¹⁵的标识符空间。

为了评估FIFSM洪泛算法的有效性和容错能力，本文进行了2组实验。实验开始后，所有的节点依次加入网络，并在实验过程中保持在线状态。

为了把FIFSM洪泛算法与传统的洪泛算法进行对比，本文参考Gnutella 0.4协议，在OMNET++平台上建立了Gnutella的仿真模型，并在相同的条件下进行实验。实验中，我们设置不同的网络规模，节点数N从2³到2¹⁴依次增长，选择不同的节点发起洪泛，观察是否所有的节点都被访问到了，并统计产生的消息数。图6为FIFSM模型和不同度数的Gnutella模型中洪泛遍历所有节点产生的消息数对比实验结果，其中，度数指Gnutella中每个节点的连接数。从图中可以看出，在相同的网络规模下，Gnutella模型产生了比FIFSM模型更多的消息，并随着网络规模和度数的增大而大幅度增加，而N个节点的FIFSM模型中仅产生N-1个消息。这是由于传统的洪泛算法会产生大量冗余消息，而FIFSM洪泛算法不产生任何冗余消息。

图 6 洪泛遍历所有节点的消息数

图选项

在FIFSM洪泛算法中，查询消息携带了接收节点的转发区间，查询消息的丢失会导致该转发区间内节点的丢失。为了评估FIFSM洪泛算法在故障环境下的容错能力，本文定义α和β，分别代表链路故障下的丢包率和失效节点率。实验中，我们设置N=1 000和4 000。

实验中，我们设置丢包率α在0.1% ~ 0.6%范围内，α=0.1%表示1 000个消息会有1个消息丢失。节点加入网络后，我们让每个节点都发起1次洪泛，统计节点被访问到的次数，并计算丢失的节点数。图7为不同α对应的节点丢失率曲线。

图 7 链路故障下洪泛的节点丢失率

图选项

从图中可以看出，随着α的增加，节点丢失率呈线性增长，而且随着节点数的增加，节点丢失率也随之增加。可以看出，消息的丢失对搜索的成功率有着很大的影响，实际网络中，可以采用TCP作为传输层协议，保证消息传输的可靠性，避免链路故障造成的消息丢失的现象。

为了评估FIFSM洪泛算法对节点故障的容错能力，实验中，令节点以β的比率故障离开，造成节点失效的情况，我们统计30 s内若干次洪泛后丢失的节点数。图8展示了N=1 000的网络，在不同的H和β下节点的丢失率曲线。

图 8 节点故障下洪泛的节点丢失率

图选项

从图中可以看出，当H=1时，节点的丢失率随着β的增大而迅速增加，但随着H的增大，节点丢失率显著降低。当H=4时，节点的丢失率几乎为0。这是因为邻居表采用了冗余节点机制，每一个表项的邻居节点数可以达到H。当节点转发消息的时候，如果遇到失效节点，可以选择其他的冗余节点转发消息。假设节点失效概率为p，则1次转发失效的概率为p^H。因此随着H的增大，FIFSM洪泛算法的容错能力也随之提高。

为了评估动态环境下FIFSM机制的搜索成功率、维护开销以及搜索延迟，根据文献[20]的策略，本文建立了动态的网络环境。我们在网络中随机指定一部分节点为“保留节点”，它们在实验的过程中不离开网络，始终保持在线状态。其他的节点则为“非保留节点”，这些节点在实验开始后，以0.5的概率选择是否加入网络。这样，网络初始化后，非保留节点有大约一半处于在线状态，一半处于非在线状态。在实验过程中，每隔一段时间，实验中设置为60 s，“非保留节点”以概率 选择是否从在线状态转换到非在线状态，反之亦然，这样我们就建立了一个变动率为λ的动态网络。本文针对不同的λ值进行实验，实验的运行时间设置为3 600 s。

为了评估动态环境中FIFSM机制的搜索成功率，实验设置SP fixer工作周期为20 s，实验开始后，网络中的在线节点每10 s发起1次洪泛，“保留节点”将记录被访问到的次数，同时，我们还将记录所有节点的总洪泛次数，于是就可以计算出实验过程中每个“保留节点”的命中率，即访问次数占总洪泛次数的百分比。通过对所有“保留节点”的命中率取平均值，则近似得到在当前λ的动态环境下洪泛的节点命中率。图9展示了N=1 000和4 000时，λ在[0,0.3]范围内的动态环境下，洪泛时节点的命中率曲线。从图中可以看出，随着λ的增大，节点命中率逐渐降低，但均保持在99.9%以上，并且不随网络规模的增大而剧烈变化，保持了动态环境下的高度可靠性。

图 9 动态环境下节点的命中率

图选项

为了评估FIFSM的网络维护开销，实验中，我们主要统计节点平均每分钟收到的控制消息数，这里的控制消息主要指SP fixer和connect task产生的控制消息。

设SP fixer工作周期为20 s，connect task工作周期为60 s，节点个数 ，图10为不同λ下的控制消息数曲线。从图中可以看出，SP fixer产生的控制消息数保持在7个左右，这是因为SP fixer仅在当前节点的前向和后向节点区间之内洪泛控制消息，所以消息不会被大范围转发。此外，connect task产生的控制消息数则随着λ的增加而逐渐减小，因为当节点加入网络的时候，会在全网进行洪泛，与网络中的节点建立连接，增加其邻居表的饱和度。虽然节点的离开可能会导致其他节点空路由表项的产生，但由于每个表项的节点数最多可以达到节点冗余度H，降低空表项产生的可能，因此随着λ的增大，节点的加入越多，connect task洪泛的次数也随之减少。综上，在动态环境中，FIFSM 的维护开销随着节点变动率λ的增加而降低，大大减少了网络维护开销。

图 10动态环境中FIFSM的维护开销

图选项

为了评估FIFSM机制在动态环境中的搜索延迟，我们分别在 、0.15、0.25的动态环境中进行实验。设connect task的工作周期为60 s，实验开始后，在线节点在每个固定的时间间隔(10 s)后发起一次洪泛，统计查询消息经历的跳数，实验结果如表2所示。表2的第一列为实验运行的参数，包括节点变动率λ﹑节点数N和节点冗余度H。第二列至第五列为不同跳数范围内包含的消息数占总消息数的比例。最后一列为所有消息的平均跳数。实验结果表明，在N=1 000和4 000的不同λ的动态网络中，消息的跳数主要集中在8跳以内，平均跳数均小于5跳。对比实验<0.15,1 000,1>和<0.15,1 000,4>以及<0.15,4 000,1>和<0.15,4 000,4>的结果可知，在相同的N和λ下，随着H的增大，消息的平均跳数也随之减少。综上，FIFSM机制在动态环境中具有较低的洪泛搜索延迟。

本文提出了一种改进的非结构化P2P网络洪泛搜索机制-FIFSM，其主要内容和贡献包括:(1)提出了在非结构化P2P网络中使用一致性哈希函数为节点分配标识符，建立结构化的邻居表的优化策略，并在邻居表中增加冗余节点，提高洪泛算法在节点失效时的容错能力。(2)提出并实现了基于转发区间的洪泛算法，避免了冗余消息的产生，降低了洪泛搜索的代价。另外，增加了范围洪泛的功能，以降低特定范围内搜索的开销。(3)提出了高效的网络维护机制，其维护开销随着网络动态程度的增加而降低。实验结果表明，FIFSM机制不仅降低了非结构化P2P网络基于洪泛的资源搜索的开销，提高了非结构化P2P网络的可扩展性，并且能够在动态环境中保持高度的稳定性和可靠性。未来的工作将考虑节点之间的实际物理距离，建立与底层物理网络更加匹配的覆盖网拓扑，利用节点之间的邻近性，进一步降低FIFSM洪泛搜索的消息延迟，合理利用网络带宽。