基于移动代理的结构化P2P网络模型

王永伟，樊建席，刘文军，沈海飞

（苏州大学 计算机科学与技术学院，江苏 苏州215006）

0 引 言

P2P网络改变了传统的C／S模式，使得拥有资源的用户可以与需求资源的用户直接连接进行资源的共享，将网络中的资源合理有效地组织利用起来。

P2P网络分为结构化P2P网络和非结构化P2P网络。结构化P2P网络区别于非结构化P2P网络的最大特点在于：结构化P2P网络都有一个严格的覆盖网拓扑结构［1］。在最短的时间内找到所需要的资源是P2P网络所需解决的首要问题。结构化P2P网络主要就是实现了资源的快速查找，典型的结构化 P2P网络协议有 Chord［2］，CAN［3］等。但是这些典型的拓扑模型没有考虑网络中的节点在处理能力和在线时长等方面的差异。若充分利用这种差异即异质性则可以对网络的性能做出极大的改善。此外，在如今的网络中，用户常希望在输入一些所需资源的某些特点以后能筛选出某一类资源，这就要求网络应具有语义查询的能力。

文献 ［4］考虑了节点的异质性，但是没有语义查询功能。文献 ［5］提出了基于双层P2P结构的语义服务发现模型。文献 ［6］改进了双层P2P网络模型并作了相关分析。将自组织和结构化P2P网络相结合可得到自组织网络，如文献 ［7，8］将生物激励算法用到结构化P2P网络Chord中，得到Self－Chord模型。文献 ［9］利用移动Agent预见性的处理负载问题达到负载均衡。文献 ［10］通过利用自组织的方式均衡负载。文献 ［11］给出了两层非结构化的语义发现模型。

本文结合网络中节点的异质性提出的一种基于移动代理的结构化 P2P网络模型 （mobile agent based structured P2Pnetwork：AS－P2P），在移动代理的作用下，AS－P2P不仅具有资源索引分类、模糊查询、负载均衡等优点，而且平均查找长度更短，更加能够适应网络的动态变化。

1 AS－P2P网络模型

1.1 相关定义

定义1 一般节点NP（normal peer），可以是网络中的任意节点。它可以随时加入和离开网络而只需要较少的网络修复操作。一般节点上存有资源供其它节点请求，也可以向其它节点请求资源。一般节点上存有自身资源的资源索引，这些资源索引项为 （key，Location（ID）），其中：key是数值型资源关键字，假设相似资源的key相近。是为此资源索引负责的超级节点的标识。

定义2 超级节点SP （super peer），是指在网络中在线时间长、处理能力强、可靠性高的节点。它主要负责若干个NP的资源请求和相应种类的资源索引。它负责维护的索引数据库为

其中：Location（key，NP）是资源关键字为key的资源所在的路径，如可由NP的IP地址和资源在NP上的路径组成。此外，每个SP还需要维护一个中心关键字CK（central key）以表征此超级节点所负责的索引项的资源种类，CK可以由下式得到其中：表示索引数据库中所有资源索引的关键字之和，表示资源索引项项数。超级节点还需要维护一个索引网络的路由表。

定义3 移动代理 MA （mobile agent），是运行在超级节点上的程序。它负责超级节点的索引数据库中资源索引项的转移。当超级节点的索引数据库有资源索引项更新时，便运行此程序。它把超级节点的索引数据库中离CK较远的键索引带离该超级节点并放置到合适的超级节点上。MA是实现资源索引分类的关键。

AS－P2P网络模型的上层为索引网络，是由在线时间长、处理能力强和可靠性高的超级节点组成的结构化P2P网络。网络中的超级节点在更新资源索引时运行移动代理程序，此程序负责索引网络中的资源索引的移动。一般节点组成下层网络，称为资源网络。资源网络的节点可以与任意的超级节点建立主仆关系，从而适应高度动态的网络环境。

1.2 一般节点上线和资源发布

一般节点可以是网络中的任意节点，它可以随意的加入网络并依附于超级节点。

1.3 节点下线和资源撤销

1.3.1 一般节点下线

一般节点NP下线时根据每项资源对应的资源索引项的找出对应的负责超级节点SP，然后向SP发送下线消息DOWN＿MSG，SP收到消息后把相应的资源索引项删除，并返回一个DOWN＿OK消息给NP，当NP收到所有资源的DOWN＿OK消息后正常下线，对应的资源也正常撤销。另外，SP周期性检测每个资源是否有效，以排除一般节点意外下线造成的资源无效的情况。

1.3.2 超级节点下线

当超级节点SP需要下线时，SP会把索引数据库中存储在SP上的资源索引删除，并按照上述一般节点下线时的操作删除SP在其他超级节点上的资源索引，然后在SP负责的一般节点NP中找到一个备选超级节点SPB，最后SP把索引数据库和路由表复制给SPB。SPB继承SP的ID号，并通知SP所负责的资源索引对应的资源所在的节点，现在由其负责该索引，SPB按照索引网络层所用的结构化P2P网络协议加入索引网络。至此，超级节点正常下线，对应的资源也正常撤销。

1.4 一般节点加入与离开索引网络

索引网络按照所有超级节点的CK从小到大排列，所以拥有相似CK的超级节点是相邻的。

1.4.1 一般节点加入索引网络

当一个超级节点SP的资源索引项过多，即超过设定的最高负载INDEX＿HIGH 时，SP在其负责的一般节点中选出一个备选超级节点设为SPB，作为SP的后继加入上层索引网络。SP将索引数据库中排序靠后的一半资源索引项复制给SPB。SP通知相应超级节点现由SPB负责相应的资源。这些操作结束以后，SP删除这些资源索引。SP和新加入的SPB都重新计算自己的CK。一个一般节点就成功加入索引网络成为超级节点。

1.4.2 超级节点离开索引网络

当某超级节点SP1的资源索引项过少，即低于设定的最低负载INDEX＿LOW 时，SP1向其邻居节点SP2发送一个INFO＿MSG消息询问SP2的索引数据库中的索引项的个数。SP1得到SP2的索引项个数以后，SP1比较自身的索引项数与SP2索引项数之和是否大于INDEX＿HIGH 。若SP1的索引项数大于SP2的索引项数，则由SP2将索引数据库中的前 （Index ＿SP2－Index ＿SP1）／2索引项转移给SP1，（其中，Index＿SP1和Index＿SP2是SP1和SP2的索引数据库中的索引项数）；否则，SP1把自己的索引项和负责的一般节点交由SP2负责。一个负载过低的超级节点成功离开索引网络成为一般节点。

1.5 超级节点上移动代理的工作过程

步骤1 当有新节点加入并由超级节点SPM 负责时，SPM的MA激活比较函数用以找出其索引数据库中与CK较远的对应的索引项，这可根据与的相似度函数确定

其中，key＿max是资源关键字的最大差。给定一个Ptake，当时，SPM 就找出关键字为key的资源索引项。

步骤2 MA复制步骤1找出的资源索引项，在路由表项中找到一个超级节点SP1，使得SP1的CK与索引项对应的资源关键字最近。MA与SP1建立连接，设SP1的CK为，计算。在SP1的路由表中找出超级节点SP2使其CK与key最相近，设SP2的CK 为CK2，计算。若f（key，CK1）＞f（key，CK2），则把key放置在SP1上；否则，与SP2建立连接。重复步骤2的前述过程，直到找到一个超级节点SPD，最终将key放置到SPD上。SPD根据索引项中包含的源ID号给SPM发送一个确认消息，SPM 再告诉该资源的拥有者NP，NP相应改动自己的资源索引，知道自己的资源是由SPD所负责的。然后SPM 删除此项资源索引。

步骤3 MA重复步骤2将所有资源索引安排给合适的超级节点，一次移动代理的工作过程结束。

2 AS－P2P网络模型的实验仿真和性能分析

2.1 平均查找长度

设网络中节点进行资源请求的概率相同，索引网络使用结构化P2P模型。设网络中总节点数为N，超级节点个数占总节点个数的比例为α，超级节点的个数为α＊N，一般节点的个数为（1－α）＊N。

定理 AS－P2P网络中的平均查找长度较传统结构化P2P网络模型更短。

证明 以索引网络层使用Chord为例，当超级节点查找资源时，直接在索引网络层进行查找，平均查找长度为log（α＊N）；当一般节点查找资源时，会向为其负责的超级节点发出请求，长度为1，之后由超级节点查找资源，平均查找长度为log（α＊N）；由于超级节点、一般节点占总节点个数的比例分别为α、1－α，因此在Chord中平均查找长度

在实际网络中，超级节点的比例α较小，所以平均查找长度log（α＊N）＋1－α相对于chord来说更小。相类似的，当索引网络层使用其它结构化P2P网络模型如CAN时，由于规模变小，平均查找长度也较传统结构化P2P网络模型也更短。

2.2 资源分类和语义查询

网络在多个移动代理的协同工作下，每个超级节点维护的索引数据库中，偏离该超级节点CK较远的资源索引项都会被转移到合适的超级节点的索引数据库中，即资源索引会按照资源种类被安放在相应超级节点的索引数据库中。

在稳定的网络中，各超级节点的索引数据库中，索引项关键字key都距离CK较近，它们属于相似资源。因此，一个超级节点是存储以CK为中心的一类资源，这达到资源索引分类效果。如果对于网络中的某个关键字key的资源请求没有找到，那么超级节点也可以返回索引数据库中与key相近的资源，因而可以实现语义查询。为评估超级节点的索引数据库中资源索引项的相似程度，现作如下定义。

定义4 超级节点上资源索引纯度ρ定义为

其中，CKi是超级节点i的关键字，N是超级节点i的索引数据库中资源索引项数，key＿max是资源关键字的最大差。

模拟实验参数如表1所示，其中资源关键字最大差为512，网络中超级节点的动荡时的资源纯度和执行移动代理后的资源纯度如图1所示。

表1 模拟实验参数

图1 超级节点的资源索引纯度

从模拟实验结果数据来看，资源键值均匀分布时，网络经过动荡后，部分超级节点的资源纯度下降；在移动代理程序运行作调整后，所有超级节点上的资源纯度又重新恢复到很高的状态，这表明网络具有资源索引分类的功能。

2.3 负载均衡

从一般节点加入索引网络和超级节点离开索引网络的过程来看，超级节点的资源索引项数会分布在INDEX＿LOW和INDEX＿HIGH 之间，从而实现超级节点上资源索引项的负载均衡。这对于网络性能和可靠性十分重要。例如，当一个超级节点存储的资源索引属于热门资源，那么对它的查询会很频繁，如果它存储的资源索引项过多，那么热点问题就很突出，而这里的负载均衡很好的解决了这个问题。若超级节点所负责的一般节点过多可通过向邻居超级节点转移部分一般节点的方式进行一般节点负载的均衡，且此操作不会影响上层的索引网络。

模拟实验参数如表1所示，网络动荡期及稳定后超级节点上拥有的资源索引项数如图2所示。

图2 超级节点上资源索引项的个数

从实验结果数据来看，资源键值均匀分布时，网络在有节点和资源的加入和离开后，部分超级节点索引数据库中的资源索引项数发生了较大变化；经过调整，超级节点上的资源索引项数都处于3000和7000之间，即分布在INDEX＿LOW 和INDEX＿HIGH 之间。这说明网络中超级节点上的资源负载是相对均衡的。

3 结束语

理论分析和模拟实验表明，充分利用节点的异质性，并选择使用双层网络结构后，AS－P2P具有对资源索引分类，负载均衡，能很好地适应网络的动态变化等优点。需要指出的是，AS－P2P没有考虑网络带宽因素。实际上，为了达到资源索引的分类，移动代理在网络中移动时会消耗索引网络带宽。后续的工作可以对移动代理的工作进行优化，以期以更小代价换取资源分类和负载均衡，这对于支持语义查询和后续的P2P网络扩展具有重要的作用。

［1］CHEN Guihai，LI Zhenhua.Peer－to－peer structure，application and design ［M］.Beijing：Tsinghua University Press，2007 （in Chinese）.［陈贵海，李振华.对等网络：结构、应用与设计［M］.北京：清华大学出版社，2007.］

［2］Stoica I，Morris R，Karger D.Chord：A scalable peer－to－peer lookup service for Internet applications ［C］／／ACM SIGCOMM，2001：149－160.

［3］Sylvia R，Paul F，Mark H，et al.A scalable contentaddressable network ［C］／／San DiegoCA， ACM SIGCOMM，2001：161－172.

［4］XIA Qizhi，XIE Gaogang，MIN Yinghua，et al.IS－P2P：Index－based structured P2Pnetworks ［J］.Chinese Journal of Computers，2006，29 （4）：604－607 （in Chinese）. ［夏启志，谢高岗，闵应骅，等.IS－P2P：一种基于索引的结构化P2P网络模型 ［J］.计算机学报，2006，29 （4）：604－607.］

［5］LIU Zhizhong，WANG Huaimin，ZHOU Bin.A two layered P2Pmodel for semantic service discovery ［J］.Journal of Software，2007，18 （8）：1925－1926 （in Chinese）.［刘志忠，王怀民，周斌.一种双层P2P结构的语义服务发现模型 ［J］.软件学报，2007，18 （8）：1925－1926.］

［6］MING Deting，LI Juan，QIU Xiaohong，et al.Simulation on improved two－tier hybrid P2Pnetwork model ［J］.Computer Engineering and Design，2009，30 （24）：5609－5611 （in Chinese）.［明德廷，李娟，邱晓红，等.改进的双层混合式P2P网络模型的仿真与分析 ［J］.计算机工程与设计，2009，30（24）：5609－5611.］

［7］Agostino F，Carlo M，Michela M.Self－chord：A bio－inspired algorithm for structured P2Psystems ［C］／／USA：IEEE／ACM Symposium on Cluster Computing and the Grid，2009：45－47.

［8］Agostino F，Emilio L，Carlo M，et al.Self－chord：A bio－inspired P2Pframework for self－organizing distrubuted systems［J］.IEEE／ACM Transactions on Networking，2010，18 （5）：1653－1658.

［9］LI Hui.An active load balancing algorithm for P2Psystems based on mobile agent ［J］.Microelectronics and Computer，2012，29 （11）：92－93 （in Chinese）.［李慧.一种基于移动代理的P2P系统主动负载均衡算法 ［J］.微电子学与计算机，2012，29 （11）：92－93.］

［10］Giuseppe V，Paul L S，Daniel J D，et al.A self－organized loadbalancing algorithm for overlay－based decentralized service networks［C］／／IEEE International Conference on Self－Adaptive and Self－Organizing Systems，2011：170－172.

［11］LIU Zhizhong，LIU YuLan，HE Yihui.A two－layered P2P model for semantic service discovery ［C］／／ New Trends in Information Science and Service Science，2010：42－45.