非结构化P2P网络基于马尔科夫链的搜索算法研究

1、非构造化P2P网络基于马尔科夫链的搜索算法研究非构造化P2P网络基于马尔科夫链的搜索算法研究引言P2P网络Peer-t-Peer技术的应用极大地改变了当前互联网的形态。在电子商务、语音效劳、分布式计算、流媒体、文件共享等应用领域，P2P网络技术展示出很强的优势，以并行传输、分布式资源共享、对等协作、自组织等特点，使用户享受了更高的可用带宽、更优质的效劳质量和更丰富的资源。P2P网络的目的本质上是资源共享，所以找到定位资源是资源共享的前提。无构造化P2P网络在覆盖网上采用的组织方式为完全随机图，节点与共享资源之间、甚至节点之间均无任何确定的关系。因此，在非构造化P2P网络上进展资源搜索是一个挑战

2、性问题。而我们将要研究的利用马尔科夫链特性改良的概率搜索算法在减少网络冗余包、平衡网络流量、对稀缺资源的有效搜索以及进步各类资源搜索效率等方面都有很好的奉献。1.算法研究现状P2P网络中的资源搜索算法是指将对特定资源的查询恳求路由到目的节点集合的方法，即只要命中目的集中的任意节点，那么路由过程完毕。P2P网络的性能是靠搜索算法的优劣来决定的，当前对非构造化对等网络在搜索算法上的研究已经相当成熟，按照搜索策略，搜索算法分为两类：盲目搜索和启发式搜索。盲目搜索通过洪泛、随机游走的方式在网络中传播查询信息，将信息不断扩散给邻居节点，以此查询到想要的资源。在搜索的过程中，启发式搜索是利用节点存储的信息

3、来帮助搜索过程，即每当查询信息到达时，先检索本地存储的信息，就可以较快地定位到响应该查询的节点，启发式搜索是以存储的代价交换网络流量和时延降低的算法。1.洪泛：洪泛算法是一种简单的播送式搜索算法。该算法搜索的深度由TTL控制，搜索节点Requester每传播一步TTL减1，假如TTL减到0还没有搜索到资源，那么停顿。访问节点数目的降低直接导致查询精度的下降和查询步数的增加，因此洪泛算法无法到达较优的搜索效率。2.随机漫步：这种方法对洪泛的搜索宽度作了一定改良。与洪泛算法不同的是，搜索节点Requester根据每个节点上缓存的历史搜索信息来选取k个邻居节点发送query信息，每路query信息被

4、称为一个Randalker。每个Randalker都分配一个TTL值，且每路Randalker直接与原始搜索节点Requester保持联络。假设查询过程中发现目的资源，那么原路返回所需要的信息。相比于洪泛算法，随本文由论文联盟搜集整理机漫步算法是用时间换空间的有效算法。该算法由于包含了查询资源的查询经历信息，相对搜索准确度进步，并且也缩短了相对搜索途径长度。3.负载平衡算法：在非构造化P2P网络中由于底层网络拓扑构造化映射的限制，所以不需要进展准确的匹配，网络的负载不仅是源于对数据资源的恳求，更重要的还来源于对计算资源的恳求。这即是说，非构造化P2P网络可以更好的支持动态任务调度，即对最优执行

5、节点的恳求资源。基于非构造化P2P网络的负载分配算法主要有随机算法，负载扩散和负载迁移等。考虑整体网络的负载平衡，使得整个网络环境能更好的工作，但是由于没有考虑搜索效率故会导致搜索效率下降。2.基于arkvhain的搜索算法基于非构造化P2P网络传统的搜索算法，虽然都能较好的完成对各类资源的搜索，但是存在一定的局限性及缺点。分析存在的问题：洪泛算法在搜索过程中产生了大量的网络冗余包，对网络本身造成一定的负担；随机漫步算法属于盲目搜索算法，其在搜索过程中是随机选择目的进展查询，并不能有较好的搜索成功率；一般意义上的路由缓存算法并不能实时的借鉴之前搜索的失败经历。在本论文工作中，将马尔科夫链应用到

6、搜索算法中，即在每一时态节点进展搜索查询时按照转移概率矩阵选择下一邻近节点，并在该过程中动态更新转移概率矩阵。提出一种基于马尔科夫链模型的资源搜索改良算法：1.根据节点兴趣确定本地节点转发到下一节点的一步转移概率；2.构造可以反映节点负载状况或负载处理才能的负载因子，并也将以此为根底作为节点选择的参考标准构造转移概率；3.以吸收态的马尔科夫链为根底构造可以收敛到转发因子极值点的随机采样模型此处所说的转发因子：综合考虑兴趣因子及负载因子确定转发因子。该算法将被设计为保证随机采样过程以最快的速度向转发因子极值收敛。2.1基于兴趣效劳的资源搜索基于效劳的P2P资源网络是系统控制流和数据流运行的自组织环境，构成系统的根底构造。P2P网络执行节点的参加、自组织、分开、资源搜索的负载分配均通过该非构造化P2P网络实现。假设存在一个逻辑上的网络，基于一般意义上的P2P资源共享网络模型，其中的节点均与其他节点保持连接，以Gnutella为例，连接的数量是由存储在节点上的资源数目所决定的。假设节点p与q在网络中是直接连接的我们就说p的