Computer Engineering and Applications 计算机工程与应用 2011，47（19） 113 一种对等网络分层管理资源定位模型 张 颖 1，2，周 娅 1，黄桂敏 1，朱晓姝 2 ZHANG Ying1，2，ZHOU Ya1，HUANG Guimin1，ZHU Xiaoshu2 1.桂林电子科技大学，广西 桂林 541004 2.玉林师范学院，广西 玉林 537000 1.Guilin University of Electronic Technology，Guilin，Guangxi 541004，China 2.Yulin Normal University，Yulin，Guangxi 537000，China ZHANG Ying，ZHOU Ya，HUANG Guimin，et al.Peer-to-Peer network resource locating model of Computer Engineering and Applications，2011，47（19）：113-117. layer-management. Abstract：According to the feature of Small World situation in network and the principle of data stream locality，this paper designs a peer-to-peer network resource locating model of layer-management based on Kademlia.It makes the most use of re- configuration of Kademlia’s topological structure and priority visiting of neighbouring physical nodes to increase efficiency of visiting nodes and optimize routing location.Simulation tests indicate that inherits the merits of Kademlia，and it is superior to original Kademlia model in routing location and average logic path length. Key words：layer-management；peer-to-peer network；resource locating；super node the designed model 摘 要：通过研究网络中小世界现象特征与数据流局部性特点，基于 Kademlia 协议设计了一种对等网络分层管理资源定位模 型。模型通过重构 Kademlia 协议的网络拓扑结构，利用物理邻近节点访问优先的方法，来提高节点访问效率并优化节点的路由 选择。仿真结果表明，设计的模型在继承了 Kademlia 模型优点的基础上，在节点路由选择和节点查找的平均逻辑路径长度等方 面的性能均优于 Kademlia 模型。 关键词：分层管理；对等网络；资源定位；超级节点 DOI：10.3778/j.issn.1002-8331.2011.19.031 文章编号：1002-8331（2011）19-0113-05 文献标识码：A 中图分类号：TP393 1 前言 对等网络（Peer-to-Peer，P2P）是分布式系统与计算机网络 相结合的产物，早期的 P2P 系统（如 Napster）采用集中式网络 拓扑结构，其资源的访问通过一个目录服务器来引导，虽然部 分解决了客户/服务器（Client/Server，C/S）结构中客户访问量 大的服务器拥塞问题，但是目录服务器也存在着客户访问量 大的拥塞问题。为了彻底解决这个问题，研究人员设计出非 结构化 P2P 协议，例如 Gnutella 和 Freenet，但是由于它们采用 了洪泛传送模式，容易导致网络拥塞。为了更进一步解决非 结构 P2P 的这个问题，研究人员又设计出结构化 P2P 协议，例 如 Chord、CAN、Pastry、Kademlia 等。 Kademlia 是一种采用异或运算机制的结构化 P2P 协议，它 是由美国纽约大学的 Petar P.Maymounkov 和 David Mazieres 在《Kademlia：A Peer-to-Peer Information System Based on the XOR Metric》一篇论文中提出来的。目前，主流的 P2P 系 统大多数都采用它作为自己的核心检索协议，例如 eMule、Bit- Comet、BitSpirit 和 Azureus 等。当然，Kademlia 协议也存在着 一些问题，研究人员针对这些问题提出了一些改进方法与意 见，例如：文献[1]在借鉴 T-Man 协议的基础上，提出了快速构 建结构化 Kademlia 网络的算法，优化了 k 桶的生成和它的更新 算法；文献[2]针对于P2P系统对热点查询效率的需要和Kadem- lia 路由模型缓存策略的不足，设计了一种基于快速索引表具 有二次及多次查找的 Kademlia 路由算法，有效地支持了对热 点资源的分析判断功能和记忆功能。文献[3]改进了 Kademlia 的节点退出算法，节点在退出网络时会主动通知附近节点自己 失效信息，能够及时更新路由表，减少对失效节点的访问，从而 缩短搜索时间。文献[4]在Kademlia基础上结合IPv6地址，提出 了一个改进的 TMK（Topology-Matched Kademlia）模型，该模 型能很好地解决逻辑网络与物理网络的失配问题，减小节点的 路由表空间，缩小网络查询响应时延。因此，本论文在研究 Kademlia存在的一些问题基础上，通过分析相关对 Kademlia的 改进研究，通过在 Kademlia 中引入域的概念，将物理距离近的 节点组成一个域，根据节点能力差异，把节点分为超级节点和普 通节点，最终构建了一种对等网络分层管理资源定位模型，简 称 LRL-KAD，并在 OMNeT++仿真工具上对 Kademlia 与 LRL- KAD 进行了对比仿真实验，验证它们之间的资源定位性能。 基金项目：广西自然科学青年基金资助项目（No.桂科青 0832101）。 作者简介：张颖（1980—），女，讲师，主要研究方向为对等网络、网络安全等；周娅（1966—），女，教授；黄桂敏（1965—），男，教授；朱晓姝（1973—）， 女，副教授。E-mail：lingboying@126.com 收稿日期：2009-09-23；修回日期：2010-09-16 

114 2011，47（19） Computer Engineering and Applications 计算机工程与应用 2 Kademlia 方面的问题： Kademlia 通过独特的异或算法来测量网络中节点之间的 距离，在一种全新的 DHT 拓扑结构基础上，用一个 160 位 ID 值 作为标志符来唯一标识网络中节点，而ID值的生成采用SHA-1 函数，SHA-1 函数输入值可以是节点 IP 地址，也可以是一个随 机数。同样，网络中每个共享文件也有一个由 SHA-1 函数产 生的 160 位的特征值，这个文件的共享信息就被存储在节点 ID 等于这个特征值的节点上。网络中的信息都是以<关键字， 值>的形式保存在节点上。 2.1 距离概念 在 Kademlia 中，任意两个节点之间的距离是由这两个节 点的 ID 异或运算得到。由于异或运算的单向性，保证了在对 一个<关键字，值>条目查找时，不管是从哪个节点发出的请 求，最终都可以汇聚到相同的路径中。这样在节点的查找行 为中，通过缓存<关键字，值>条目就可以提高节点的查找效率 与查询速度。 2.2 k 桶与路由表 在 Kademlia 中，每个节点的路由表采用“k 桶”结构来记录 其他节点的路由信息。k 桶是一个信息列表，每个节点都有 160 个 k 桶，从 k-bucket[0]到 k-bucket[159]。对于任意节点 i（0≤ i<160），k-bucket[i]都记录了与其距离在[2i，2i+1）之间的其他节 点信息，其中包括节点的 IP 地址、UDP 端口、节点 ID，并且每 个 k 桶最多能够存放 k 条节点信息。k 桶内节点排列顺序是按 照最后联系时间排序，即：最近联系的节点放在 k 桶尾部，最早 联系的节点放在 k 桶头部。一般而言，对于比较小的 i 值，k 桶 通常是空的（因为没有合适的节点存在其中），对于比较大的 i 值，k 桶节点数可以达到 k 的大小。k 桶结构如图 1 所示。 head 距离[1，2） null 距离[2，4） null k-backet[0] k-backet[1] k-backet[2] … k-backet[159] … 图 1 k 桶结构图 距离[4，8） null tail 距离？ null （1）网络节点经过散列后，物理位置信息被破坏，来自同 一个子网的多个节点的逻辑距离可能很远，路由过程要跨越多 个广域网节点，导致应用系统响应时间长，降低了网络速度； （2）没有考虑网络节点实际能力的差异，没有服务质量保 证，网络效率低； （3）网络不可控制，可管理性差，给实际应用带来一定困难。 针对上述 Kademlia 协议存在的问题，在研究 Kademlia 协 议及相关研究者的成果基础上，设计了一种基于分层管理的 LRL-KAD 模型，来解决 Kademlia 协议存在的上述问题，下面 详细介绍 LRL-KAD 模型的具体内容。 3.1 设计思想 依据互联网中小世界现象特征与数据流的局部性特点， 设计了一种基于分层管理的 LRL-KAD 模型，设计思想如下： （1）引入域的概念，将物理距离近的节点组成一个域。 （2）根据节点的能力差异，把节点分为超级节点和普通节点。 （3）在每一个域内选出一个超级节点，负责这个域内普通 节点的资源定位和发布；将每个域选出的超级节点作为一层， 即超级节点层；剩下的普通据节点作为另一层，即普通节点 层；所有节点的资源定位首先在所在域内进行，若失败，则请 求所在域超级节点在毗邻域之间查找。 3.2 LRL-KAD 模型 如图 2 所示，LRL-KAD 模型根据节点的 IP 地址将物理距 离较近的节点划分为一个域，然后在这个域中找到一个能力 较强的节点作为本域的超级节点。超级节点之间的关系是分 布式的，每个超级节点都用一个 k 桶来存放网络中其他超级节 点的信息。为了便于管理，同一个域中每个普通节点都将自 己本身能够贡献的信息（例如能够提供哪些文件用于共享）发 给本域的超级节点，超级节点会根据域内普通节点提供的信 息在本地建立域内资源列表（如图 3 所示）。 超级节点 1 超级节点 2 超级节点 n … 超级节点层 普通节点层 2.3 k 桶更新 当节点 x 收到从节点 y 发出的一个 RPC 消息时，提取节点 y 的<关键字，值>里的“值”更新节点 x 的 k 桶中节点 y 对应的 路由信息，具体步骤如下： ⊕ （1）计算节点 x 和节点 y 的距离：d（x，y）=x 分别代表节点 x 和节点 y 的 ID 值； y，其中 x 和 y （2）对节点 x 的第[lb d]个桶进行更新操作； （3）如果节点y的“值”已在k桶中，则把它移到k桶的尾部； （4）如果节点 y 的“值”没有被记录在 k 桶中，则执行如下 操作： ①如果 k 桶未满，则直接把节点 y 的“值”插入 k 桶尾部； ②如果 k 桶已满，则选择 k 桶头部的记录项（假如是节点 z） 并 PING 节点 z，如果节点 z 未响应，则从 k 桶中移除节点 z 的 “值”，并把节点 y 的“值”插入 k 桶尾部；如果节点 z 响应，则把 节点 z 的“值”移到 k 桶尾部，同时忽略节点 y 的“值”。 3 LRL-KAD 模型 域 1 域 2 域 n 图 2 LRL-KAD 模型 … ID 共享文件名 属性 图 3 域内资源列表格式 图 3 提供了文件共享的普通节点的 ID，“共享文件名”顾 名思义，“属性”是指共享的文件具有的是否允许下载、是否允 许更改等特征。 在 LRL-KAD 模型中，每个节点的 ID 都用 2n 位表示（n 的 大小由网络规模来决定），其中的高 n 位用来区别不用的域（称 之为“域间 ID”），低 n 位用来区别域内节点（称之为“域内 ID”）。为了区别普通节点与超级节点，把所有超级节点的低 n 位全部设置成为 0。公式（1）是超级节点的计算公式，它通过 一个普通节点的 ID 来换算出它所在域的超级节点的 ID： y = x Ù 11 高n位 00 低n位 （1） 文献[5-7]在研究 Kademlia 协议时，发现它存在如下几个 其中 y 是超级节点 ID，x 是普通节点 ID。 

张 颖，周 娅，黄桂敏，等：一种对等网络分层管理资源定位模型 2011，47（19） 115 3.3 信息存储 在 LRL-KAD 模型中，共享文件的信息均以<关键字，值> 的形式存储。假设在节点 ID 为 2n 位的网络中，节点 A 提供文 件 f 的共享，那么这条共享信息“关键字=f，值={节点 A 的 ID， 节点 A 的 IP，节点 A 的 Port}”将被存放到与文件名哈希后相关 的某个节点上。设这个节点的域间 ID 对应的十进制值是 X， 域内 ID 对应的十进制值是 Y，则 X 和 Y 的值由以下公式获得： （2） X=hash1（文件名）=（文件名）mod 2n Y=hash2（文件名）=[（文件名）mod N]+1 （3） 说明：（1）公式（3）中的 N 表示域间 ID 为 X 的超级节点所 辖域内普通节点的个数； （2）公式（2）和（3）中的“文件名”如果是英文字符则取其 ASCII 码对应的十进制值，如果是中文字符则取其国标码对应 的十进制值；如果是多个字符，则按原有顺序直接连续获得其 ASCII 码串或国标码串对应的十进制值。例如，文件名为 a 对 应的 ASCII 码为 01100001，十进制值为 65；文件名为 ab 的文件 对应的 ASCII 码串为 01100001 01100010，十进制值为 24 930。 （3）当超级节点个数达不到网络上限时，会发生用公式 （2）计算出的域间 ID 为 X 的超级节点不存在的情况。例如在 8 位 ID 的网络中（n=4），只有 5 个超级节点（域间 ID 对应的十进 制值分别为 0、1、2、3、4），而某文件名计算出的 X 值为 6，此时 将根据具体网络情况取最接近 6 的值 4。 因此，域间 ID=X，域内 ID=Y 的这个节点上会形成一张“文 件索引字典”存储文件 f 的共享信息，格式如图 4 所示。 关键字 ID 值 IP Port 图 4 文件索引字典 图 4 中，“值”部分包含的 ID、IP、Port 分别指提供文件共享 节点的 ID、IP 和 Port。例如，除节点 A 提供文件 f 的共享外，节 点 B 也提供文件 f 的共享，则相关节点上形成的文件索引字典 如表 1 所示。 表 1 文件索引字典举例 关键字 f f ID A 的 ID B 的 ID 值 IP A 的 IP B 的 IP Port A 的 Port B 的 Port 3.4 路由查询 当普通节点发出查询时，首先会把查询信息发给本域的 超级节点，接到查询请求的超级节点会先在域内资源列表里 进行查询，如果发现域内有相匹配的目标文件，则把存储目标 文件的节点信息返回给发出查询的源节点；如果域内没有与 目标文件相匹配的资源，则向其他超级节点发出查询请求，做 毗邻域间查询。 假如普通节点 x 要查找文件名为 f 的文件，LRL-KAD 模型 按照如下递归操作进行路由查找，如果初始发出查询的节点 为超级节点，则可以从第（2）步开始进行路由查找。 （1）利用公式（1）计算普通节点 x 对应的超级节点 y，并由 普通节点 x 向超级节点 y 发送查询文件 f 的请求； （2）超级节点 y 在域内资源列表的“共享文件名”一项里查 询是否有文件 f。若有，则把提供文件 f 共享的节点的信息返 回给节点 x；若无，则转到下一步； （3）超级节点 y 使用公式（2）计算出文件 f 的共享信息所在 的节点 ID（称之为目标节点 ID），计算出的 X 即为目标节点的 域间 ID，也就是目标节点所属超级节点的域间 ID。由于超级 节点的域内 ID 全部为 0，所以能够确定目标节点所在域的超 级节点 ID（设为 s）； ⊕ （4）计算超级节点 y 到超级节点 s 的距离：d（y，s）=y （5）从超级节点 y 的第[lb d]个 k 桶中取出α个超级节点的 信息，同时进行查找操作。如果这个 k 桶中的信息少于α个，则 从附近多个桶中选择距离最接近 d 的总共α个超级节点（这里α 为系统优化而设立的一个参数，主要作用是调节每步查询的 并发度）； s； （6）对于接受到查询操作的每个超级节点，如果发现自己 就是超级节点 s，则回答自己是最接近超级节点 s 的；否则测量 自己和超级节点 s 的距离，并从自己对应的 k 桶中选择α个超级 节点的信息给超级节点 y； （7）超级节点 y 对新接收到的每个超级节点都再次执行查 找操作，此过程不断重复执行，直到每一个分支都有超级节点 响应自己是最接近节点 s 的。没有迅速响应的超级节点将被 迅速排除出候选列表，直到其响应； （8）通过上述查找操作，超级节点 y 得到了 k 个最接近超级 节点 s 的超级节点信息； （9）超级节点 y 向这 k 个最接近超级节点 s 的超级节点发 送查询请求； （10）接收到查询请求的超级节点（设为 m）在自己的域内 资源列表的“共享文件名”一项里查询是否有文件 f。若有，则 把提供文件 f 共享的节点的信息返回给超级节点 y；若无，使用 公式（3）计算出目标节点的域内 ID，从而得到目标节点的完整 ID（设为 w），并向节点 w 发送查询文件 f 的请求； （11）节点 w 收到超级节点 m 发来的查询文件 f 的请求后， 在自己的文件索引字典的“关键字”一项中查询是否有 f。若 有，则把“关键字”=f 的所有条目返回给超级节点 m，并由此超 级节点把这个消息转发给超级节点 y；若无，则返回给超级节 点 m 一个查询失败的消息； （12）超级节点 m 将收到的查询结果返回给超级节点 y； （13）超级节点 y 将收到的查询结果返回给普通节点 x； （14）普通节点 x 若收到查询成功的消息，则从“关键字”=f 的所有条目中选择一条，并提取条目中的“值”（这个“值”包括 提供文件 f 共享的节点 ID、IP 和 Port），与提供文件 f 共享的节 点建立 http 互联，进行文件下载；若收到查询失败的消息，则结 束查询。 下面将用一个简单的例子来进一步说明 LRL-KAD 模型 如何进行资源查询与定位。 图 5 是一个简单的 8 位 ID 的 LRL-KAD 模型，为方便起见 节点 ID 用 16 进制数表示，00、10、20、30、40、50 分别为 6 个超 级节点，01、02、03 分别是超级节点 00 所辖域内的普通节点， 31、32、33 分别是超级节点 30 所辖域内的普通节点，51、52 分 别是超级节点 50 所辖域内的普通节点。由于只有 8 位 ID，所 以超级节点的 k 桶参数取 3，并行查询参数α取 1。超级节点 00、30、50 的域内资源列表如表 2 所示，普通节点 32 的文件索 引字典如表 3 所示。 假设普通节点 01 要查找文件 c，其查询操作过程如下： （1）普通节点 01 使用公式（1）计算出所在域的超级节点的 ID 为 00，则 01 向 00 发送查询文件 c 的消息。超级节点 00 收到 

116 2011，47（19） Computer Engineering and Applications 计算机工程与应用 33 （7） 3 （5） （6） 32 2 4 （4） 5 31 （2） 51 52 （9） （1） 0 （3） 1 （8） 01 03 02 图 5 LRL-KAD 模型中的资源定位示例 表 2 超级节点 00、30、50 的域内资源列表 （a）超级节点 00 的域内资源列表 ID 01 02 03 共享文件名 属性 d h e 只允许下载 只允许下载 只允许下载 （b）超级节点 30 的域内资源列表 ID 31 32 33 共享文件名 属性 b g f 只允许下载 只允许下载 只允许下载 （c）超级节点 50 的域内资源列表 ID 51 52 共享文件名 属性 a c 只允许下载 只允许下载 表 3 普通节点 32 的文件索引字典 关键字 c 值 ID 52 IP Port 52 的 IP 52 的 Port 这个消息后，在 00 的域内资源列表的“共享文件名”一项里查 询是否有文件 c 的信息。 （2）由于超级节点 00 在自己的域内资源列表中未查找到 文件c的信息，则转到毗邻域之间查询。首先00利用公式（2）计 算出文件 c 的共享信息存储的位置，X=hash1（c）=（c）mod 24= 67 mod 8=3，说明文件 c 的共享信息存储在超级节点 30 的域 内。然后 00 在它的 k 桶查找 30 的信息，假设 00 的 k 桶内没有 30的信息，则00会在k桶内查找最接近30的其他超级节点。在 这里假设找到的超级节点是20，则00向20发出查询30的请求。 （3）超级节点 20 收到超级节点 00 发来的查询消息，就会 在它的k桶内查询30的信息，假设20的k桶内有30的信息（包括 ID、IP、Port），则 20 会向 00 返回一个消息，其中包含 30 的信息。 （4）超级节点 00 收到 20 返回的消息，就可以向 30 发出查 询文件 c 的消息。 （5）超级节点 30收到 00发来的查询消息，则在 30的域内资 源列表的“共享文件名”一项中查询是否有 c。结果未查到有 c， 然后超级节点 30 使用公式（3）计算出 Y=hash2（c）=[（c）mod3]+ 1=（67 mod 3）+1=2，则超级节点 30 向域内的普通节点 32 发出 查询文件 c 的请求。 （6）普通节点 32 收到超级节点 30 的消息后，在 32 的文件 索引字典里查找“关键字”=c 的条目，然后把找到的信息返回 给超级节点 30。 （7）超级节点 30 将收到的信息返回给超级节点 00。 （8）超级节点 00 将收到的信息返回给普通节点 01。 （9）普通节点 01 根据返回的信息通过 HTTP 协议与普通 节点 52 其建立互连，从节点 52 下载所需文件 c。 因此，从图 5 示例可以更加进一步了解到 LRL-KAD 模型 实现原理：LRL-KAD 模型首先考虑了节点的物理地址，用域 的概念将不同地点的节点进行了划分。然后根据节点能力的 不同引入超级节点和普通节点的概念，将模型划分为两层，把 查询先控制在域内，只有域内没有资源时才进行域间查询。 这样一来，就在一定程度上避免了舍近求远情况的发生，并且 能在一定的范围内控制远程网络带宽的占用，同时提高了查询 的传输速率，有效提升了整个网络的性能。为了检验LRL-KAD 模型的实际性能，下面将介绍在 OMNeT++基础上，采用 Visu- al Studio 2005 标准版对 LRL-KAD 模型的仿真实现。 4 仿真实验 在对 LRL-KAD模型的仿真实验中，LRL-KAD模型的节点 规模采用 16 位 ID，共有 65 536 个节点。由于考虑到 LRL-KAD 模型基于Kademlia协议设计，对LRL-KAD模型的仿真实验时， 在 OMNeT ++基础上参考 Kademlia 协议，采用 Visual Studio 2005 标准版构建了一个与 Kademlia 协议对应的 Kademlia 模 型，通过对比 Kademlia 模型与 LRL-KAD 模型在相同网络环境 下的查询平均逻辑路径长度仿真实验数据，来评估 LRL-KAD 模型实际性能。仿真实验参数表见表 4 所示，图 6 所示是 LRL- KAD 模型的仿真实验框图。 表 4 仿真实验参数表 网络规模 节点数/个 仿真时间/h TTL 16 位 ID 65 536 6 7 开始 初始化网络 查询是否达到 预设时间 是 结束 否 tag？ tag=0 Start（） tag=1 Query1（） tag=2 Query2（） tag=3 tag=4 Back2（） Back1（） 图 6 LRL-KAD 模型仿真框图 在图 6 中，tag 是消息的标志位：tag=0 表示一个发向网络 中任意节点开始新一次查询的消息；tag=1 表示一个普通节点 向所在域的超级节点发送的查询消息；tag=2 表示一个超级节 点在域内资源列表中找不到目标文件时，向另一个超级节点 发送的查询消息；tag=3 表示一个超级节点在域间查询找到目 标文件后，向发起查询的普通节点返回的消息；tag=4 表示一 个超级节点返回给另一个超级节点域间查询结果的消息。其 中：Start（）、Query1（）、Query2（）、Back1（）、Back2（）分别表示 处理 5 种消息的方法，下面详细介绍它们的具体内容如下： Start（）方法是在收到开始新一次查询的消息时调用的方 法，主要作用是初始化新消息和在任意节点开始一次新的查询； Query1（）方法是由超级节点调用的方法。当一个域的超 

张 颖，周 娅，黄桂敏，等：一种对等网络分层管理资源定位模型 2011，47（19） 117 6 4 2 ） 数 跳 （ 度 长 径 路 辑 逻 均 平 6 4 2 ） 数 跳 （ 度 长 径 路 辑 逻 均 平 0 1 2 3 4 5 6 0 1 2 3 4 5 6 时间/h 时间/h 图 7 Kademlia 模型的平均逻辑路径 图 8 KRL-KAD 模型的平均逻辑 长度随时间变化图 路径长度随时间变化图 级节点收到本域内的普通节点发来的查询消息时，将会首先 在本域内查询是否有目标文件，如果有则将拥有目标文件的 节点的“值”传回给源节点，如果没有就向域间的其他超级节 点发送查询请求； Query2（）方法是一个超级节点收到另一个超级节点的查 询请求时调用的方法。主要作用是先查找自己的域内是否有 目标文件，如果有则返回拥有目标文件的节点的“值”给源超 级节点，如果没有则在自己的 k 桶内找到最接近目标节点的 k 个节点的“值”返回给源超级节点； Back1（）方法是在普通节点处调用的方法。当一个最初 发出查询的普通节点收到本域的超级节点返回的目标节点的 “值”时，它会通过网络与目标节点建立 HTTP 链接，然后传送 文件。 Back2（）方法是当一个发出域间查询的超级节点在收到 其他超级节点返回给自己消息时调用的方法。如果返回的消 息里有目标节点的“值”，则把这个值返回给发出查询的源节 点；如果返回的消息里没有目标节点的“值”，则继续向返回的 最接近目标节点的其他节点发送查询请求。 在仿真实验中，采用相同的网络情况下对 Kademlia 模型 与 LRL-KAD 模型进行对比仿真，并收集 6 小时内两个模型平 均逻辑路径长度随时间变化的仿真数据（如图 7、图 8 所示）。 其中，逻辑路径长度指每次从查询开始到这次查询结束所经 历的跳数，平均逻辑路径长度取的是每 100 次查询得到的逻辑 路径长度的平均值。 图 7 是 Kademlia 模型查询时平均逻辑路径长度随时间变 化的图，从图 7 中可以看出：由于 Kademlia 协议本身所具有的 收敛性，查询的平均逻辑路径是随着时间的增加而逐步减少 的，图 7 中每一个点都是查询 100 次得到的总路径的平均值， 由于是在不同的节点产生的值，所以用不用形状的点表示。 图 8 是 LRL-KAD 模型查询时平均逻辑路径长度随时间变 化的图，从表 5 可以看出：LRL-KAD 模型的收敛性明显优于 Kademlia 模型，这主要是因为划分了域之后减小了查询的范 围，从而使平均逻辑路径减少，同时也防止了网络中普遍的 “搭便车”行为，使用户可以优先从和自己物理距离近的其他 节点下载所需的信息，而平均逻辑路径的减少则意味着网络 通信消耗的降低和查询响应时间的减少。 表 5 分时段两模型平均逻辑路径长度变化比较表 时间 Kademlia 模型 LRL-KAD 模型 0～1 6.36 5.56 1～2 6.02 4.01 2～3 5.33 2.90 3～4 4.87 2.35 4～5 4.53 2.02 5～6 4.21 1.91 5 结束语 Kademlia 模型存在忽略网络节点的物理位置和节点能力 差异等缺点，本文设计的 LRL-KAD 模型引入了域和分层的概 念，在一定程度上避免了资源定位时舍近求远情况的发生，并 且能在一定的范围内控制远程网络带宽的占用，同时提高了 查询的传输速率，很好地解决了 Kademlia 模型存在的问题，有 效提升了整个网络的性能。下一步的工作是研究域的规模对 网络性能的影响及超级节点失效情况等问题。 参考文献： [1] 张昊，戴长华，张翀.一种构建 Kademlia 网络拓扑的高效算法[J].计 算机应用研究，2009，26（2）：534-536. [2] 张学魁.基于 DHT 的 P2P 网络路由算法的研究[D].成都：西华大学， 2008. [3] 张铮，侯宾，吕玉琴，等.在扰动状态下 Kademlia 协议搜索过程性能 分析及优化[J].中国电子科学研究院学报，2008，3（6）：604-607. [4] 马志新，潘伟国，田中彬，等.TMK：一种解决拓扑匹配的 DHT 模 型[J].网络与通信，2009，25（2/3）：139-141. [5] Steiner M，En-Najjary T，Biersack E W.Exploiting KAD：Possible uses and misuses[J].ACM SIGCOMM Computer Communication Review，2007，37，（5）：65-67. [6] Stutzbach D，Rejaie R.Improving lookup performance over a widely- deployed DHT[D].University of Oregon，Daniel Stutzbach，Reza Rejaie，2006. [7] Li J，Stribling J，Morris R，et al.Bandwidth-efficient management of DHT routing tables[C]//Networked Systems Design and Im- plementation.Boston：[s.n.]，2005：3-10. [8] Maymounkov P，Mazieres D.Kademlia：A peer-to-peer information system based on the XOR metric[C]//Proceedings of 1st Interna- tional Workshop on Peer-to-Peer Systems.Cambridge：[s.n.]， 2002：53-65. [9] Brunner R.A performance evaluation of the Kad-protocol[D].In- stitut Eurecom in France，Rene Brunner，2006. [10] Idserda J.TCP/IP modelling in OMNeT++[D].University of Twente， Jeroen Idserda，2004. [11] Baker M，Lakhoo R.Peer-to-peer simulators[D].University of Read- ing，Mark Baker，Rahim Lakhoo，2007. [12] Naicken S，Basu A，Livingston B，et al.A survey of peer-to-peer network simulators[C]//The Seventh Annual Postgraduate Sym- posium.Liverpool：[s.n.]，2006：3-8. [13] Mallanda C，Suri A，Kunchakarra V，et al.Simulating wireless sen- sor networks with OMNeT++[D].Louisiana State University，2005.