改进蚁群算法在P2P网络资源搜索中的应用*

赵开新，魏 勇，王东署

（1.河南机电高等专科学校，河南 新乡 453002；2.郑州大学电气工程学院，郑州 450001）

改进蚁群算法在P2P网络资源搜索中的应用*

赵开新1，魏 勇1，王东署2

（1.河南机电高等专科学校，河南 新乡 453002；2.郑州大学电气工程学院，郑州 450001）

针对P2P网络搜索算法中冗余查询消息过多，资源搜索效率低的问题，提出了基于改进蚁群算法的P2P资源搜索算法，算法中在选择邻节点查询时，综合考虑到本地资源情况、邻节点资源情况、邻节点资源相似度等因素，尽量避开了资源搜索中的恶意节点，并改进了基本蚁群算法的状态转移规则，从而避免了查询消息的盲目发送。仿真实验表明，与传统资源搜索算法K-radom-walks和Flooding相比，该算法在搜索命中率和带宽利用率方面有明显提高。

改进蚁群算法，P2P，资源搜索，查询消息

0 引言

P2P技术已经广泛应用于科学计算、即时消息传递和资源共享等领域，其中应用最广泛的是资源共享，而资源搜索机制的好坏在很大程度上决定了P2P网络资源共享的成功与否，因此，有效的资源搜索机制是P2P网络发展和应用的核心技术之一［1-2］。P2P网络中节点可以自由地加入或退出，资源分散地分布在网络中各节点，每个节点既可以从其它节点获得资源，也可以为其他节点提供资源，这使P2P网络中资源处于不断的动态变化中，增加了P2P网络资源搜索技术的难度［3-4］，因此，有必要对P2P资源搜索技术进行研究，以便更准确、高效地搜索到用户所需资源，本文把改进蚁群算法的思想引入到P2P资源搜索过程中，缩小了查询信息的转发范围，减少了查询信息的转发量，提高了P2P网络带宽利用率和资源搜索效率。

1 P2P网络的资源搜索

1.1 P2P网络的搜索机制

P2P网络可以被看成由许多节点组成的一个无向图，无向图中的顶点由动态加入或者离开的节点组成，顶点中存放着各种共享资源，网络中顶点之间的66连线组成了图中的搜索路径，若两个顶点之间有直连线，说明两顶点是相邻节点，当用户提交资源搜索请求时，源节点首先在本地进行资源查找，若找到，把搜索结果返回给用户，否则，该节点把该资源查询信息转发给其相邻的一个或多个节点，若邻节点存在着所搜索的资源，则把该资源立即返回给用户。否则，将资源查询消息向其邻节点继续转发，直至找到所搜索的资源或者遍历完所有节点而所搜索的资源没有被找到［5-6］。

1.2 P2P网络的搜索机制存在的问题

P2P网络中由于节点不断地加入或离开，使得网络的拓扑结构不断发生变化，如何准确定位到所查找的资源是P2P网络资源共享的一个难点［7-8］，现有的资源搜索机制主要以泛洪和随机漫步为主，泛洪搜索机制存在着查询盲目性，并会在网络中产生大量的查询信息而占用网络中大量的带宽，随机漫步算法随机向K个邻节点转发查询信息，减少了查询信息的转发量，但K个节点的选择仍然具有盲目性，导致搜索效率不如泛洪好，并且对网络中的恶意节点行为考虑不足。

2 改进蚁群算法在P2P网络中的应用

2.1 问题分析

P2P网络资源搜索模型，可以看作一个由多个蚁穴和连接这些蚁穴的通路共同构成的网络。在此网络中进行资源搜索类似于蚂蚁寻找食物，每一只搜寻食物的蚂蚁相当于一个查询信息，待搜索的资源看作蚂蚁寻找的食物，存储待搜索的资源节点看作食物源。蚂蚁从蚁穴寻找食物的过程，就是用户发送资源请求在P2P网络中搜寻资源的过程，蚂蚁在寻找食物的过程中选择下一个节点时，会根据各路径上信息素浓度，选择一条离食物最近路径进行搜索，当蚂蚁找到了搜寻食物的最佳路径，也就找到了资源搜索的最佳路径。

2.2 蚁群算法的改进

基本蚁群算法存在着时间复杂度大，容易出现停滞等缺陷，并且在资源搜索的过程中过分依赖信息素浓度，导致过早地生成最优路径，易得出局部最优解，并且P2P网络中搜索路径的选择不仅依靠信息素的浓度，还要考虑到节点资源相似度，网络中是否存在恶意节点等。所以需要对基本蚁群算法进行改进后，才能应用到P2P网络资源搜索过程中。

2.2.1 信息素浓度的更新

在P2P网络中，选择邻节点搜索时不仅要考虑到节点信息素浓度，还需考虑节点资源的相似度，令P1为：

其中τij是路径eij上的信息素浓度，ηij是路径的启发式因子，即节点资源的相似度，φ为信息素衰减因子，改进后的信息素局部更新如式（2）。

令P2为：

其中Sgbest为全局最优路径信息素，信息素的全局更新公式如式（4）。

其中ρ为信息素挥发因子，当蚂蚁每完成一次搜索后，所经过路径上的信息素都会挥发，此机制可以使蚂蚁尽量探索未访问过的路径，避免了算法的早熟现象，具有较高τ和η的路径又会被优先遍历。

2.2.2 恶意节点的惩罚

如果网络中存在着恶意的服务节点，那么在资源搜索时要尽量避开，这可以通过对路径上的信息素值进行修改进行实现，根据恶意节点离本节点的距离不同，可以对各条路径设置不同的惩罚力度，本文定义的距离因素如式（5）。

式（5）中L是整个路径的实际长度，dij是从本节点到目标节点的距离，惩罚后的信息素值如式（6）。其中φ为信息素惩罚因子。

2.2.3 蚂蚁状态的转移规则

位于节点i的蚂蚁根据式（7）选择下一节点j，其中j为从式（8）给出的概率分布选出的一个随机变量［9-10］。

式（7）中q为大于0小于1的一个随机数，值的大小决定下一个节点选择是在已经过的较优路径上，还是未探索的新的路径上，q0是确定选择某个最有希望访问的节点概率，当q≤q0时，由启发信息和信息素浓度共同决定下一个节点的选择，当q＞q0时，由基本蚁群算法选择下一个待搜索的节点，引导算法趋向收敛。蚁群算法转移规则的改进，避免了蚂蚁仅根据信息素浓度选择路径，增强了算法的随机搜索性能，扩大了搜索范围，有效避免了算法过早陷入局部最优。

2.3 相关描述

把改进的蚁群算法应用到P2P网络资源搜索中，网络中的每个节点，需要存储3个表，分别是本地共享资源表、资源缓存表和信息素表，其中本地共享资源表，保存本地共享的所有资源，包括资源ID，资源分类名，关键词以及关键词在该资源中的权重等信息，资源缓存表保存近期被本地用户访问过的非本地资源的实际节点地址，当多次访问同一资源信息时，用户可以从该表中直接找到该资源所在的节点获得所需资源。信息素表是一个M×N的二元矩阵，其中，M表示最近由此节点发起或由其他邻节点转发过的所查询关键字的总数，N表示当前节点Pi所有邻节点个数，矩阵中的值τkn表示节点Pi到邻节点Pn路径上关于关键词k的信息素浓度的大小，ηkn表示点Pi在邻节点Pn上所获资源与所查找资源的相似度，其取值在0和1之间，初始阶段所有节点间关键词K的信息素值为最小值Kmin，资源相似度ηkn为0，如表1所示。

表1 信息素表

2.4 算法的步骤

Step1：节点i收到关键字为K的资源查询信息时，首先在本地查询共享资源表、资源缓存表，若找到了所要搜索的资源，则执行步骤Step5。否则执行步骤Step2。

Step2：根据公式状态转移式（7）、式（8）选择下一个待搜索的节点j，当蚂蚁到达节点j后，首先查询j节点共享资源表、资源缓存表，若找到了所要搜索的资源，则执行步骤Step5，否则，搜索蚂蚁将自己刚访问过的节点加入到自己的禁忌表中，根据信息素表中信息素和节点相似度选择下一个节点。

Step3：每个节点经过一个t时间间隔，通过式（2）、式（4）进行信息素的挥发操作。

Step4：若网络中的节点都已被遍历，并没有找到所搜索的资源则搜索失败，算法结束。

Step5：生成返回蚂蚁，沿原路反馈给源节点，并根据式（2）、式（4）修改搜索路径上各节点关键字为K的信息浓度τ和节点资源相似度η，源节点蚂蚁根据反馈的路径，去搜索所需的资源，搜索算法结束。

3 仿真实验

实验中采用均匀随机图作为网络拓扑，设非结构化网络中有5 000个网络对等体节点，在5 000个节点中随机选择1 000个节点放置查询资源，P2P网络中共有50种不同的资源，随机给每个节点分配20个资源，蚁群算法中信息启发算子α和期望启发算子β分别为0.5，0.6；信息素挥发因子ρ=0.65，信息素衰减因子φ=0.5，仿真实验中搜索算法分别采用改进的蚁群算法（Improved ant），随机漫步算法（K-radom-walks）和泛洪算法（Flooding），从搜索的命中率、搜索的平均响应时间和网络带宽利用率3个方面，来比较3种搜索算法的性能。

图1 搜索命中率

由图1可以看出，在搜索的初始阶段，与K-radom-walks、Flooding算法相比，改进的蚁群算法的搜索命中率提高并不明显，但随着系统时间的推移，改进蚁群算法搜索命中率增加的速度明显大于K-radom-walks和Flooding，并且最后保持一个较高的命中率状态，因为随着时间的推移，节点根据本地存储的共享资源表、资源缓存表和信息素表的信息找到了搜索资源的较优路径，所以搜索效率有明显的提高，而K-radom-walks、Flooding算法中查询消息的转发路径存在一定的盲目性，查询消息的转发路径不会根据历史查询信息进行动态调整，所以搜索的命中率和系统运行的时间相关性不大。

图2 平均发送查询消息数

由图2可以看出，Flooding算法平均发送的查询消息量最大，K-radom-walks次之，改进蚁群算法最少，因为Flooding将查询消息发给自己所有的邻节点，而K-radom-walks将查询消息发给K个邻节点，所以查询消息量有所减少，而改进的蚁群算法利用信息素参数来指导节点选择概率大的路径进行搜索，且有自我学习的功能，并能够尽量避免恶意节点，减少查询信息的转发量，从而提高了带宽的利用率。

图3 平均响应时间

由图3可以看出，在资源数相同的情况下，Flooding算法所需平均响应时间最短，而K-radom-walks最长，改进的蚁群算法位于两者之间。由于Flooding算法向所有邻节点转发查询信息，所以能够也在较短时间内得到响应，但这种响应时间短是以发送大量查询包，占用大量带宽为代价的。而K-radom-walks算法由于是随机选择K个邻节点进行转发查询包，所以这种查询的盲目性的代价是响应速度的降低。而改进的蚁群算法利用信息素来指导查询消息的转发，并通过对恶意节点进行惩罚，尽量避开了查询概率小的节点和路径，因此，可以在发送较少查询信息的情况下，快速查询到满足条件的资源，从而减少了查询的响应时间。

4 结束语

针对P2P网络搜索算法存在的冗余查询消息占用大量网络带宽，搜索效率降低的问题，提出了一种基于改进蚁群算法的P2P网络搜索算法，算法中在查询节点的选择时，综合考虑本地资源情况、邻节点资源的情况、邻节点资源的相似度，以及邻节点是否恶意节点的情况，从而避免了查询消息的盲目发送，提高了搜索的效率。仿真实验证明，与传统资源搜索算法K-radom-walks和Flooding相比，随着时间的推移本文提出的算法搜索命中率和带宽利用率有了明显提高，而资源的平均响应时间本文提出的算法比Flooding算法稍有增加，因此，降低资源平均响应时间，是本算法进一步改进的方向。

［1］黄海.p2p网络技术研究现状与展望［J］.计算机科学，2012，39（6）：178-183.

［2］钱宁，吴国新.无结构化P2P网络资源搜索机制研究综述［J］.计算机科学，2010，37（4）：7-10.

［3］高磊.基于信任迭代的P2P网络信任管理模型［J］.计算机工程，2012，38（19）：92-95.

［4］周莲英，闫报.p2p网络中基于蚁群算法的资源搜索研究［J］.计算机工程与设计，2012，33（1）：32-35.

［5］彭建，周欢.非结构化p2p网络资源搜索改进算法［J］.计算机工程与设计，2012，33（11）：4071-4075.

［6］黎梨苗.基于优先权的P2P网络信任模型［J］.计算机工程，2013，39（5）：148-151.

［7］陈珊珊.P2P网络中基于权重因素的信任模型［J］.计算机应用，2013，33（6）：1612-1614.

［8］陈光喜.基于改进粒子群算法的P2P流媒体数据调度策略［J］.计算机应用，2013，33（4）：931-934.

［9］李春秀.基于蚁群算法的非结构化P2P网络资源搜索策略［J］.计算机工程与应用，2012，48（4）：97-99.

［10］蔡康.基于改进型蚁群算法的P2P网络资源搜索的研究［J］.电信科学，2013（3）：34-42.

［11］雷磊，周青松.基于小生境遗传算法的干扰资源调度研究［J］.现代防御技术，2014，42（1）：94-99.

Study on Resource Search in P2P Networks Based on Improved Ant Algorithm

ZHAO Kai-xin1，WEI Yong1，WANG Dong-shu2
（1.Henan Mechanical and Electrical Engineering College，Xinxiang 453002，China；
2.Electrical Engineering School of Zhengzhou University，Zhengzhou 450001，China）

For many redundant messages resources search algorithm and low efficiency issues in P2P network，the P2P resource search algorithm based on improved ant colony algorithm is proposed in this paper.The local resources，the neighbor node resources，the neighbor node resource similarity factors in selecting query neighbor are considered，avoiding the malicious node in resources searching as far as possible.And the basic ant colony algorithm state transition rules is improved.Query messages blind sending is avoiding.Simulation results shows the algorithm in search hit rate and bandwidth utilization improved obviously compare with traditional resource search algorithm K-radom-walks and Flooding.

improved ant colony algorithm，peer-to-peer，resource search，query message

TP391.41

A

1002-0640（2015）05-0139-04

2014-03-05

2014-04-17

国家自然科学基金（61174085）；高等学校博士学科点专项科研基金资助项目（20114101110005）

赵开新（1979- ），男，河南项城人，硕士。研究方向：路径规划技术、计算机网络技术。