浅谈计算机资源搜索的具体算法

前言：本站为你精心整理了浅谈计算机资源搜索的具体算法范文，希望能为你的创作提供参考价值，我们的客服老师可以帮助你提供个性化的参考范文，欢迎咨询。

1概述

近年来，利用空间上的局部性即将拥有相似资源的节点聚集成簇，建立不同的兴趣域，实现资源的簇内和簇外搜索；文献中利用节点的信任度，提出一种激励机制，将查询消息转发到信任度高的节点；文献中引入空间向量模型，根据非结构化P2P网络中节点保存的资源信息将节点划分为不同的兴趣域，通过兴趣域进行资源搜索。文献采用分组思想，将P2P网络划分成不同的兴趣组，兴趣组中由中心节点进行统一管理，并且提出了备用中心节点，减少了单点失效对系统造成的危害；文献在P2P网络资源搜索中引入蚁群算法，利用节点信息素和蚁群的正反馈机制智能地选择下一跳路由。本文在以上研究的基础上，提出一种基于兴趣因子的蚁群资源搜索算法（AntColonyOptimizationBasedonInterestFactor，IACO），通过分析节点价值对资源搜索性能的影响，在蚁群算法中引入节点的兴趣因子，动态调整节点价值和信息素在计算转发概率时的权重关系，选择概率大的邻居节点进行消息转发，在非结构化P2P网络中实现了资源的智能查找。最后通过仿真实验对该算法的性能进行了验证。

2传统的蚁群算法蚁群算法

经研究发现，自然界中的蚂蚁在找寻食物时呈现一定的规律性，在这个过程中它们会留下一种类似于信息素的物质，用来指导后续蚂蚁的觅食行为，以后的蚂蚁会感知路径中的信息素浓度来指导自己的下一步搜索行为。所有的蚂蚁都会朝信息素浓度高的路径搜素，这种基于信息素的正反馈机制，使得某一路径上的信息素浓度越来越大，因此它被选择搜索的概率也逐渐变大，搜索的蚂蚁也就越多。蚂蚁的这种集体激励机制可以启发式的促使较短的路径优先被选择。研究发现蚂蚁的这种智能行为比较适合P2P这种动态网络的资源搜索。因此，蚁群算法被越来越多的应用于非结构化P2P网络的资源搜索中。文献在P2P网络资源搜索中引入蚁群算法，按照资源中的关键字将信息素分类，通过不同的信息素智能地选择下一跳路由。文献利用蚁群算法的正反馈机制，充分考虑了邻居节点度和邻居-邻居节点信息，降低了在搜索过程中形成环路的概率，减少了网络中的冗余消息量。通过研究发现当前这些算法并没有克服蚁群算法搜索初期资源查询效率低的问题，很少考虑到节点价值以及所要查询的资源与节点的兴趣之间的相似性对资源搜索的影响，而本文的研究则正是基于此展开的。

3相关描述

3.1节点价值

算法都是试探性的搜索，在相同的时间内资源搜索覆盖度越高，则搜索成功率也就越高。本文假定在非结构化P2P网络中的资源是随机分布的，资源搜索覆盖度指的是单位时间内搜索到的资源数量，其中节点的度数和共享资源数是决定资源搜索覆盖度的两个重要因素。非结构化P2P网络是一个巨大的动态网络，我们很难知道其中的一个节点相对于整个网络的“全局价值”，所以我们把一个节点在其邻居节点中的“局部价值”作为该节点的当前价值。非结构化P2P网络中的资源搜索因为在P2P网络中度数高的节点可以确保消息在下一跳转发到相对多的节点，而共享资源多的节点可以保证查询消息在当前查询到相对多的资源，这些都大大地增加了资源查询的命中概率。因此，用节点度数和拥有的资源数来表示该节点的价值，指导生成资源查询路径。

3.2兴趣因子

在资源搜索的不同阶段，为了动态调整节点价值和信息素在转发概率中的比重关系，提高资源的查询效率，本文在蚁群算法中引入了节点的兴趣因子，用兴趣因子来表示一个节点当前的查询请求与一段时间内历史记录表中记录的查询请求之间的相似度。经文献研究表明，P2P网络中的节点在资源查询时会呈现一定的特点，即节点感兴趣的内容往往会表现出一定的集中性，很多节点在一段时间内会对某一个主题的内容表现出一定的兴趣，因此，可以通过历史记录表来得到当前的查询请求与过去一段时间内该节点的查询请求之间的相似度，将这个相似度作为节点的“兴趣因子”，来决定节点价值和信息素之间的权重关系。如果兴趣因子比较大，则说明当前查询的资源在过去的一段时间内出现过的概率比较大，该资源在路径上留下的信息素会比较多，此时信息素在转发概率中所占的比重会比较大；反之，该资源在过去一段时间很有可能没有被请求过，则节点的价值所占的比重会比较大，查询消息会被转发到存在该资源可能性较大的节点上。在资源搜索过程中，查询请求中可以包含多个关键字，这些关键字往往可以表现出一定的兴趣，因此我们可以用兴趣域来分别表示当前查询请求和节点历史查询的兴趣类型。兴趣域用关键字出现的频率wi组成的特征向量d来表示，其中d=（w1,w2,…,wn），所以查询请求q的兴趣域用特征向量表示为NE（q）=（wq,1,wq,2,…,wq,n），节点j的兴趣域NE（j）=（wj,1,wj,2,…,wj,n），其中n表示关键字集合。在系统运行的初期，路径上的信息素浓度均为min，此时信息素浓度并不能很好的指导资源的查询，加入兴趣因子，提高节点价值在转发概率中的比重，可以更好的形成有效的查询路径，很好的解决了传统蚁群算法初期资源搜索效率低的缺点，保证了算法自始至终的有效性，提高了系统在整个搜索周期中的效率。P2P网络是一个动态的网络，网络中的节点和信息实时的发生变化，所以不同时间内节点的兴趣因子也不一样。为了保证节点兴趣因子的实时性，则需要实时更新节点历史记录表表中记录的信息。为节点每一次保存的历史记录增加更新时间戳，当节点的历史记录表存满数据时，则根据记录的更新时间戳将距离当前时间最久的记录置换出表外，以此来保证数据表中记录的实时性和动态性，确保在不同的查询阶段节点兴趣因子的实时性，使得IACO算法的效率和优势得到很好的保证。

作者:房佩闫向龙良梓吴晓军单位：陕西师范大学