基于Kademlia的结构化对等网络原理及其应用
对等网络（Ｐ２Ｐ）技术通过在物理网络上构建覆盖网络（ｏｖｅｒｌａｙｎｅｔｗｏｒｋ），采用特定的路由及查找策略，共享节点（ｎｏｄｅ）资源（ｃｐｕ，存储，带宽），在协同计算、内容存储、内容共享与分发、即时通讯等领域得到了大规模应用。Ｐ２Ｐ技术研究集中在四个方面：覆盖网的构建技术，内容定位与搜索技术，内容下载技术，其它辅助技术。按照覆盖网的构建方式，通常将Ｐ２Ｐ网络分为结构化与非结构化网络，非结构化对等网络（Ｕｎ－ＳｔｒｕｃｔｅｄＰ２Ｐ）基于随机方式构建，采用ＢＦＳ（宽度优先搜索）类或ＤＦＳ（深度优先搜索）类算法进行内容定位与搜索，典型代表如Ｇｎｕｔｅｌｌａ［１］［１］，而结构化对等网络（ＳｔｒｕｃｔｅｄＰ２Ｐ）主要基于ＤＨＴ（ＤｉｓｔｒｉｂｕｔｅｄＨａｓｈＴａｂｌｅ，分布式哈希表）技术构建，在内容定位与搜索效率上比非结构化对等网络更高，典型代表如Ｃｈｏｒｄ，ＣＡＮ，Ｐａｓｔｒｙ，Ｋａｄｅｍｌｉａ等［１，２］。
１．Ｋａｄｅｍｌｉａ的理论基础
１．１ＤＨＴ（ｄｉｓｔｒｉｂｕｔｅｄｈａｓｈｔａｂｌｅ，分布式哈希表）技术
哈希表是利用哈希函数在Ο（１）量级时间内存取（ｋｅｙ，ｖａｌｕｅ）对的表状数据结构［１，３］。哈希表有三个元素：一是Ｋｅｙ，是任意有意义的标识，如文件名，ｉｐ地址等，二是ｖａｌｕｅ，其与ｋｅｙ相关，如具体的文件内容，三是哈希函数ｈａｓｈ（ｋｅｙ），作用是将ｋｅｙ集合映射到存储的（ｋｅｙ，ｖａｌｕｅ）集合。哈希表的重要特征之一是单向性，即若给定ｘ，则找到ｋｅｙ使满足ｘ＝ｈａｓｈ（ｋｅｙ）的计算是不可行的；第二特征是存取算法的理想量级为Ο（１）；第三是哈希表形成了统一的映射地址空间，操作简单，只有插入、删除、查找三种基本操作，因而在计算机系统和数据库系统中得到了广泛应用。
ＤＨＴ（分布式哈希表）是构建结构化对等网络的理论基础。结构化对等网络的资源（节点、文件等）被映射到统一的地址空间（集合）中，从全局看，资源分布在一个哈希表中，关键问题是如何构建和存储哈希表，通常是将哈希表空间被分割成许多连续的局部空间，并按照特定规则分布到节点中。
１．２ＸＯＲｍｅｔｒｉｃ（异或运算）
二进制的异或运算定义为的１ＸＯＲ１＝０，１ＸＯＲ０＝１，０ＸＯＲ１＝１，０ＸＯＲ０＝０。异或有一个重要的性质：设ａ，ｂ，ｃ为任意三个数．则：（ａＸＯＲｂ）＝（ａＸＯＲｃ）当且仅当ｂ＝ｃ，这保证了在Ｋａｄｅｍｉｌａ中，节点可以通过Ｘｏｒ运算确定邻居节点的距离并进行排序。
２．Ｋａｄｅｍｌｉａ系统描述
在Ｋａｄｅｍｉｌａ中，以节点间距离为基础，每个节点通过ｋ－ｂｕｃｋｅｔ保存邻居节点，并按照消息的刷新策略更新ｋ－ｂｕｃｋｅｔ以获得整个网络的局部视图，在此基础上，节点通过ｎｏｄｅ＿ｌｏｏｋｕｐ机制定位新的邻居节点和搜索资源信息。Ｋａｄｅｍｉｌａ通过ＵＤＰ协议进行消息和数据的传输。
２．１覆盖网的构建
２．１．１节点与资源信息
在Ｋａｄｅｍｌｉａ系统中，节点用ｎｏｄｅＩＤ标识，其长度为１６０位，所有ｎｏｄｅｉｄ形成一个地址空间并保证其不相同，ｎｏｄｅｉｄ是ｋａｄｅｍｌｉａ系统的基础。至于如何得到ｎｏｄｅｉｄ，ｋａｄｅｍｌｉａ并没有说明，这在各种实现的软件系统中自由定义；资源由固定长度的ｋｅｙ标识，通常ｋｅｙ由文件通过ｈａｓｈ函数获得，如ＳＨＡ１，所有ｋｅｙ形成一个地址空间。这样，在ｋａｄｅｍｌｉａ中有２个地址空间，所有节点组成ｎｏｄｅｉｄ地址空间，所有文件资源组成ｋｅｙ地址空间。
２．１．２距离（ｄｉｓｔａｎｃｅ）和ｋ－ｂｕｃｋｅｔ
Ｋａｄｅｍｌｉａ中，定义距离为任意２个ｋｅｙ或ｎｏｄｅｉｄ做异或运算的结果，ｄ（ｘ，ｙ）＝ｘＸＯＲｙ，距离是ｋａｄｅｍｌｉａ中其他操作的基础。节点用联系人表标识其他节点，包含ｎｏｄｅｉｄ，ｉｐ地址，ｐｏｒｔ端口。每个节点维护着ｌｏｇＮ个联系人表（通常为１６０个），每个表中包含与本节点相同距离的联系人信息，其中第ｉ个表包含距离为２ｉ￣２ｉ＋１的ｋ个联系人，通常ｋ为２０，这样的表称为ｋ－ｂｕｃｋｅｔ。
每个ｋ－ｂｕｃｋｅｔ中，联系人按照联系时间顺序排列，最先联系的在头部，最近联系的在尾部，ｋ－ｂｕｃｋｅｔ是动态的，通常保存在１个小时内有联系的联系人。当收到一个节点（ｎｅｗｎｏｄｅ）消息（２．２．２中的ｎｏｄｅ＿ｌｏｏｋｕｐ）时，计算距离并刷新ｋ－ｂｕｃｋｅｔ：（１）如果ｎｅｗｎｏｄｅ在对应的ｋ－ｂｕｃｋｅｔ中，将其位置移动到此ｋ－ｂｕｃｋｅｔ尾部；（２）如果ｎｅｗｎｏｄｅ不在对应的ｋ－ｂｕｃｋｅｔ中且该ｋ－ｂｕｃｋｅｔ未满（节点数＜ｋ），将其添加到此ｋ－ｂｕｃｋｅｔ尾部；（３）如果ｎｅｗｎｏｄｅ对应的ｋ－ｂｕｃｋｅｔ已满，则向该ｋ－ｂｕｃｋｅｔ头部联系人发送ＰＩＮＧ消息，如果收到回复，则将回复的联系人位置移动到尾部，否则抛弃并将ｎｅｗｎｏｄｅ添加到尾部。通过运用消息和定时的ｋ－ｂｕｃｋｅｔ刷新策略，每个节点保存着不同距离的在线联系人信息，获得整个网络的局部视图，即局部ｎｏｄｅｉｄ地址空间，并且仅当节点不在线后才抛弃，这保证了局部视图的稳定，能有效防止Ｄｏｓ攻击。
２．１．３（ｋｅｙ，ｖａｌｕｅ）的分布存储
如１．１节所述，构建结构化Ｐ２Ｐ的关键问题是如何构建和存储哈希表，ｋａｄｅｍｌｉａ通过基于距离的ｋ－ｂｕｃｋｅｔ机制来构建和存储哈希表，并在此基础上存储ｋｅｙ（资源信息）。简言之，ｋｅｙ被存储在距离（通过ＸＯＲ运算）此ｋｅｙ最近的节点上，这通过ｋａｄｅｍｌｉａ的ＳＴＯＲＥ（ｋｅｙ，ｖａｌｕｅ）操作实现。在某一时刻，ｋａｄｅｍｌｉａ中多个节点保存了多个ｋｅｙ，这对资源搜索是至关重要的。
２．２定位和搜索
２．２．１基本原语操作
定位和搜索是Ｐ２Ｐ系统的核心问题，在Ｋａｄｅｍｌｉａ中，定义４种基本原语操作ＲＰＣ：ＰＩＮＧ，ＳＴＯＲＥ，ＦＩＮＤ＿ＮＯＤＥ，ＦＩＮＤ＿ＶＡＬＵＥ，其中ＰＩＮＧ用来探测一个节点是否在线，ＳＴＯＲＥ（ｋｅｙ，ｖａｌｕｅ）让接收者存储（ｋｅｙ，ｖａｌｕｅ）信息，以便进行资源搜索，ＦＩＮＤ＿ＮＯＤＥ定位节点，ＦＩＮＤ＿ＶＡＬＵＥ搜索资源。所有的ＲＰＣ消息都带有一个１６０位的随机ＲＰＣＩＤ，由发送者产生，接收者在响应每一个消息的时候，返回的消息里面都必需拷贝这个ＲＰＣＩＤ。目的是防止地址伪造［１］．［４］。
ＦＩＮＤ＿ＮＯＤＥ（或者称为ＦＩＮＤ＿ＣＬＯＳＥ＿ＮＯＤＥ）以１６０位ＩＤ作为参数，接收者必须返回自己知道的ｋ个距离ＩＤ最近的联系人信息（如果它所有的ｋ－ｂｕｃｋｅｔ联系人也不够ｋ个，则返回所有联系人信息）。ＦＩＮＤ＿ＶＡＬＵＥ和ＦＩＮＤ＿ＮＯＤＥ类似，只有一点不同，如果接收者先前已经收到一个带有此ｋｅｙ的ＳＴＯＲＥＲＰＣ，则将另一参数ｖａｌｕｅ返回给发送者，否则结果与ＦＩＮＤ＿ＮＯＤＥ一样。
２．２．２查找算法ｎｏｄｅ＿ｌｏｏｋｕｐ
Ｋａｄｅｍｉｌａ的节点查找算法（ｎｏｄｅ＿ｌｏｏｋｕｐ）基于上述４个操作原语来进行，其目的是找到ｋ个距离查找ＩＤ最近的节点，此算法为递归算法，其算法思想如下：（１）初始节点从其距离最近的ｋ－ｂｕｃｋｅｔ中取出ａ个（通常ａ为３）联系人，作为候选名单（ｓｈｏｒｔｌｉｓｔ），并向其做并行、异步ＦＩＮＤ＿＊操作，如果候选联系人在线或在规定时间内响应，将返回ｋ或少于ｋ个联系人，将这些联系人加入到ｓｈｏｒｔｌｉｓｔ中，否则，从ｓｈｏｒｔｌｉｓｔ中删除此联系人；（２）再从ｓｈｏｒｔｌｉｓｔ中选取ａ个此前未联系过的候选联系人，进行（１）的步骤；（３）如果一轮下来未找到距离更近的候选人，则向ｋ个距离较近的且未联系过的联系人发送ＦＩＮＤ＿＊操作；（４）查询结束的条件是：返回的联系人不比ｓｈｏｒｔｌｉｓｔ和对应ｋ－ｂｕｃｋｅｔ中联系人的距离更近或者已经返回了ｋ个在线的候选联系人。
最后，此节点得到了ｋ个在线的距离ＩＤ最近的联系人或者搜索资源（ｖａｌｕｅ），在此并行过程中，ｓｈｏｒｔｌｉｓｔ是动态更新的，每轮ＦＩＮＤ＿＊操作都会将返回的联系人同ｓｈｏｒｔｌｉｓｔ中的候选联系人进（下转第４１４页）
基于Ｋａｄｅｍｌｉａ的结构化对等网络原理及其应用
平小艳１陈华２史小春３
（１，２康定名族师范高等专科学校四川康定６２６００１；３．四川工程职业技术学院四川德阳６１８０００）
【摘要】Ｋａｄｅｍｉｌａ是第三代Ｐ２Ｐ（Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ，对等网络）技术，是一种构建结构化对等网络的机制，基于ＤＨＴ（ＤｉｓｔｒｉｂｕｔｅｄＨａｓｈＴａｂｌｅ，分布式哈希表）和ＸＯＲ（异或运算）实现了覆盖网（ＯｖｅｒｌａｙＮｅｔｗｏｒｋ）的构建和节点快速定位以及资源的精确搜索，在新一代Ｐ２Ｐ软件如ＢｉｔＴｏｒｒｅｎｔ和ＯｖｅｒＮｅｔ等中得到了广泛应用。
【关键词】结构化对等网络；Ｋａｄｅｍｌｉａ；ＤＨＴ；应用
４１５
（上接第４１５页）行比较，使ｓｈｏｒｔｌｉｓｔ中的联系人距离ＩＤ更近，直到不能再近或者已经达到ｋ个。
２．２．３节点的加入和退出
节点加入到Ｋａｄｅｍｉｌａ时，首先获得一个其他联系人信息，并将其加入到相应的ｋ－ｂｕｃｋｅｔ中，执行ｎｏｄｅ＿ｌｏｏｋｕｐ（自己的ＩＤ）以刷新所有ｋ－ｂｕｃｋｅｔ，至此，节点获得了整个网络的局部视图。节点退出Ｋａｄｅｍｉｌａ时，如果断线，则其他节点在刷新ｋ－ｂｕｃｋｅｔ时会抛弃此节点；否则向其他节点发送退出消息，其他节点刷新ｋ－ｂｕｃｋｅｔ。
２．２．４发布、
存储和搜索（ｋｅｙ，ｖａｌｕｅ）在查找算法基础上，（ｋｅｙ，ｖａｌｕｅ）对的存储就非常简单，通过ｎｏｄｅ＿ｌｏｏｋｕｐ（ｋｅｙ）找到ｋ个距离ｋｅｙ最近的节点（联系人），向其发送ＳＴＯＲＥ操作。搜索（ｋｅｙ，ｖａｌｕｅ）对的过程同ｎｏｄｅ＿ｌｏｏｋｕｐ一样，如果成功则返回ｖａｌｕｅ，并向距离ｋｅｙ最近的未返回ｖａｌｕｅ的节点发送ＳＴＯＲＥ操作，否则返回ｋ个距离近的节点。
３．Ｋａｄｅｍｉｌａ的应用
建立在ＤＨＴ和Ｘｏｒ运算基础上的Ｋａｄｅｍｉｌａ系统提供一种高效的分布式存储和定位机制，自ＰｅｔａｒＭａｙｍｏｕｎｋｏｖ和ＤａｖｉｄＭａｚｉèｒｅｓ在
２００２年提出后［１，４］
，在许多ｐ２ｐ软件中得到了应用，如ｏｖｅｒｎｅｔ、ｅｍｕｌｅ、ｒｅｖｃｏｎｎｅｃｔ、ｂｉｔｔｏｒｒｅｎｔ及其衍生软件、ｒｅｔｒｏｓｈａｒｅ、ｓｈａｒｋｙｐｙ等［１，２］。Ｋａｄｅｍｉｌａ基于ＤＨＴ构建，故拥有ＤＨＴ对等网络的优点，即：系统结构具有高鲁棒性，关键字精确搜索，节点高效定位，平均步长为Ｏ（ＬｏｇＮ），系统在动态环境下产生的消息少。其缺点是未考虑系统的异构性即节点的能力（ＣＰＵ，存储，带宽）是不同的，并存在逻辑拓扑与物理拓扑的匹配问题。
在Ｐ２Ｐ的具体实现中，通常将Ｋａｄｅｍｉｌａ作为基础设施层，负责覆盖网的构建和路由，而具体的应用如内容分发和下载则建立在其之上。如在ＢｉｔＴｏｒｒｅｎｔ中的Ｋａｄｅｍｉｌａ实现［１，５］，路由表仍然参照标准的ｋ－ｂｕｃｋｅｔ实现，并定义了ＫＲＰＣ协议和ＤＨＴｑｕｅｒｉｅｓ（包含ＰＩＮＧ、ＦＩＮＤ＿ＮＯＤＥ、ＧＥＴ＿ｐｅｅｒｓ、ＡＮＮＯＵＮＣＥ＿ＰＥＥＲＳ）实现定位和查找，而ＢｉｔＴｏｒｒｅｎｔ中的下载仍然采用标准的协议和策略，即Ｔｉｒ－ｆｏｒ－Ｔａｔ（针锋相对）策略和片段优先算法。使用Ｋａｄｅｍｉｌａ机制的ＢｉｔＴｏｒｒｅｎｔ实现了Ｔｒａｃｋｅｒｌｅｓｓ，即不需要Ｔｒａｃｋｅｒ服务器也能进行文件的快速分发和下载。标准ｅＭｕｌｅ［１，６］协议实现了完整的Ｋａｄｅｍｉｌａ机制，其定义了关键词字典（ｋｅｙ，文件信息列表）和文件索引字典（文件ｋｅｙ，拥有者列表），并将字典分布式存储。文件下载过程如下：首先节点通过任一关键词或其组合查询关键词字典，得到该匹配关键字的文件ＳＨＡ１校验值，再通过该校验值查询文件索引字典，从而获得所有提供该文件下载的网络节点，再以分段下载方式去这些节点下载文件。
Ｋａｄｅｍｉｌａ
除了在内容分发和下载领域得到广泛应用，在流媒体［１，７］［１，８］、
语音ＶｏＩＰ［１，９］等其他领域的实际应用研究也取得了进展。【
参考文献】［１］Ｇｎｕｔｅｌｌａ．ｈｔｔｐ：／／ｗｗｗ．ｇｎｕｔｅｌｌａ．ｏｒｇ
［２］Ｋａｄｅｍｌｉａ．ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｋａｄｅｍｌｉａ
［３］熊继平．对等网络中路由机制及关键技术研究［Ｄ］．中国科技大学，２００６．４［４］ＰｅｔａｒＭａｙｍｏｕｎｋｏｖ，ＤａｖｉｄＭａｚｉèｒｅｓ．Ｋａｄｅｍｌｉａ：ＡＰｅｅｒ－ｔｏ－ｐｅｅｒＩｎｆｏｒｍａｔｉｏｎ
ＳｙｓｔｅｍＢａｓｅｄｏｎｔｈｅＸＯＲＭｅｔｒｉｃ［Ｃ］．ＩＰＴＰＳ２００２，ＬＮＣＳ２４２９，２００２：５３－６５．［５］ＤＨＴＰｒｏｔｏｃｏｌＩｎＢｉｔＴｏｒｒｅｎｔＢＥＦ．ｈｔｔｐ：／／ｗｗｗ．ｂｉｔｔｏｒｒｅｎｔ．ｏｒｇ／ｂｅｐｓ／ｂｅｐ＿０００５．ｈｔｍｌ
［６］ＫａｄｅｍｌｉａＩｎｅＭｕｌｅ．ｈｔｔｐ：／／ｗｗｗ．ｅｍｕｌｅ－ｐｒｏｊｅｃｔ．ｎｅｔ／
［７］Ｗｕ，ＪｉｅＬｉｕ．ＫａｄＳｔｒｅａｍｉｎｇ：ＡＮｏｖｅｌＫａｄｅｍｌｉａＰ２ＰＮｅｔｗｏｒｋ－ＢａｓｅｄＶｏＤＳｔｒｅａｍｉｎｇＳｃｈｅｍｅ［Ｃ］．ＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，２００７．ＣＩＴ２００７．７ｔｈＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ．２００７：４０５－４１０
［８］ＤｅｓｉｇｎａｎｄＬｕ，ＺｈｉＨｕｉＺｈａｎｇ．ＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆａＮｏｖｅｌＰ２Ｐ－ＢａｓｅｄＶＯＤＳｙｓｔｅｍＵｓｉｎｇＭｅｄｉａＦｉｌｅＳｅｇｍｅｎｔｓＳｅｌｅｃｔｉｎｇＡｌｇｏｒｉｔｈｍ［Ｃ］．ＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，２００７．ＣＩＴ２００７．７ｔｈＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ．２００７：５９９－６０４
［９］ＸｉａｏＷｕ，ＣｕｉｙｕｎＦｕ．ＡｎＩｍｐｒｏｖｅｄＫａｄｅｍｌｉａＰｒｏｔｏｃｏｌＩｎａＶｏＩＰＳｙｓｔｅｍ［Ｃ］．ＮｅｔｗｏｒｋａｎｄＰａｒａｌｌｅｌＣｏｍｐｕｔｉｎｇＷｏｒｋｓｈｏｐｓ，２００７．ＮＰＣＷｏｒｋｓｈｏｐｓ．ＩＦＩＰＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ．２００７：９２０－９２８．
作者简介：平小艳（１９８２—），女，大学本科，主要研究方向：ｐ２ｐ网络，多媒体技术。
陈华（１９７９—），男，硕士，主要研究方向：分布式计算，软件工程。史小春（１９７８—），男，大学本科，主要研究方向：计算机教学。
［责任编辑：韩铭］
科●
科
图２工作人员进入辐射区通信协议流程
当工作人员退出辐射区时，需要将剂量信息（剂量累计量与最大
剂量率等）上传到服务器的数据库中，同样先通过读出器与接口板的通信，将数据上传接口板暂存，等待工作站轮询到本机时进行数据上传。
工作人员退出辐射区通信协议流程如下图所示：
图３
工作人员退出辐射区通信协议流程
３．结论
本系统是一个网络化个人剂量监控系统，它主要是在原有单机版个人剂量监控系统的基础上，通过接口板硬件电路的设计与系统通信协议的开发，完成了个人剂量监控系统的网络化。该系统具有简单实用、成本低廉、可靠性高的特点，同时对单机版剂量监控系统具有很好的兼容性。【
参考文献】［１］汪晓平，钟军等编著．ＶｉｓｕａｌＢａｓｉｃ网络通信协议分析与应用实现［Ｍ］．北京：
人民邮电出版，２００３．
［２］（美）ＳｔｅｖｅｎＨｏｌｚｎｅｒＶｉｓｕａｌＢａｓｉｃ６．０技术内幕［Ｍ］．详实翻译组译北京：机械工程出版社，１９９９．
［３］喻维纲用ＶＢ６．０实现ＰＣ机对多台流量计远程数据采集与监控仪器仪表标准化与计量［Ｊ］２００２．６．
［４］崔巍编著．数据库系统及应用（第二版）［Ｍ］．北京：高等教育出版社，２００４．［５］李长林．ＶｉｓｕａｌＢａｓｉｃ串口通信技术与典型实例［Ｍ］．北京：清华大学出版社，
２００６．
［６］扈啸，周旭升．单片机数据通信技术从入门到精通［Ｍ］．西安：西安电子科技大学出版社，２００３．
［７］洪毅峰，鲍鹏飞，徐向东．采用轮询存储法实现点对多点的无线数据传输［Ｊ］．２００５．１．
［责任编辑：张艳芳］
●
４１４