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

《非结构化p2p网络基于马尔科夫链的搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、搜索信息来选取k个邻居节点发送query信息，每路query信息被称为一个RandomWalker。每个RandomWalker都分配一个TTL值，且每路RandomWalker直接与原始搜索节点Requester保持联系。若查询过程中发现目标资源，则原路返回所需要的信息。相比于洪泛算法，随联盟机漫步算法是用时间换空间的有效算法。该算法由于包含了查询资源的查询经验信息，相对搜索准确度提高，并且也缩短了相对搜索路径长度。　　3.负载均衡算法：在非结构化P2P网络中由于底层网络拓扑结构化映射的限制，所以不需要进行精确的匹配，网络的负载不仅是源于对数据资源的请求

5、，更重要的还来源于对计算资源的请求。这即是说，非结构化P2P网络可以更好的支持动态任务调度，即对最优执行节点的请求资源。基于非结构化P2P网络的负载分配算法主要有随机算法，负载扩散和负载迁移等。考虑整体网络的负载均衡，使得整个网络环境能更好的工作，但是由于没有考虑搜索效率故会导致搜索效率下降。　　2.基于MarkovChain的搜索算法　　基于非结构化P2P网络传统的搜索算法，虽然都能较好的完成对各类资源的搜索，但是存在一定的局限性及缺点。分析存在的问题：洪泛算法在搜索过程中产生了大量的网络冗余包，对网络本身造成一定的负担；随机漫步算法属于盲目搜索算法，其

6、在搜索过程中是随机选择目标进行查询，并不能有较好的搜索成功率；一般意义上的路由缓存算法并不能实时的借鉴之前搜索的失败经验。　　在本论文工作中，将马尔科夫链应用到搜索算法中，即在每一时态节点进行搜索查询时按照转移概率矩阵选择下一邻近节点，并在该过程中动态更新转移概率矩阵。提出一种基于马尔科夫链模型的资源搜索改进算法：1.根据节点兴趣确定本地节点转发到下一节点的一步转移概率；2.构造能够反映节点负载状况或负载处理能力的负载因子，并也将以此为基础作为节点选择的参考标准构造转移概率；3.以吸收态的马尔科夫链为基础构造能够收敛到转发因子极值点的随机采样模型。该算法将

7、被设计为保证随机采样过程以最快的速度向转发因子极值收敛。　　基于兴趣服务的资源搜索　　基于服务的P2P资源网络是系统控制流和数据流运行的自组织环境，构成系统的基础结构。P2P网络执行节点的加入、自组织、离开、资源搜索的负载分配均通过该非结构化P2P网络实现。　　假设存在一个逻辑上的网络，基于一般意义上的P2P资源共享网络模型，其中的节点均与其他节点保持连接，以Gnutella为例，连接的数量是由存储在节点上的资源数目所决定的。若节点p与q在网络中是直接连接的我们就说p的直接相连节点为q；同理，若节点p与q在网络中不是直接相连并且之间存在可访问的通路，我们就

8、说p与q是间接相连。由此我们可以看到，P2P资源网络是对称的，且在