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

发布时间：2018-04-18 10:48

本文选题：非结构化P2P网络 + 资源搜索　；参考：《北京交通大学》2015年硕士论文

【摘要】：对等网络(P2P)技术是互联网的研究热点,普遍应用于资源共享、协同工作及实时通讯等领域。非结构化P2P网络具有拓扑结构简单、支持模糊查询和搜索机制容易实现等优点,得到了广泛的应用。现有的非结构化P2P资源搜索算法主要是基于泛洪的改进算法及启发式算法,这种算法主要存在两方面问题：(1)产生大量的查询冗余包,对网络造成了一定的带宽负担;(2)由于采用盲目搜索,搜索效率较低。针对泛洪搜索算法存在的不足,论文主要研究工作体现在以下两个方面。论文提出了基于节点兴趣因子的资源搜索算法。该算法将Markov Chain模型应用到资源搜索的路径选择问题中,并引入节点兴趣因子的概念,根据节点兴趣因子确定状态转移概率。该算法在转发请求查询包时,选择最能发回查询反馈包的节点作为下一跳,保证了随机采样过程能以较快的速度向目标资源节点转移,即发出请求节点能快速搜索到被请求资源。仿真实验表明,相较于传统的泛洪算法,该算法用更少的搜索跳数获得更高的资源搜索成功率。基于节点兴趣因子的资源搜索算法仅考虑节点的兴趣,并未考虑网络的负载均衡问题,网络中的资源搜索任务集中在部分拥有热点资源的节点上,因此随着资源搜索任务的增加,网络将不能保证搜索性能。在前边工作的基础上,为解决负载问题,论文引入了负载因子的概念,提出了一种结合节点兴趣的负载均衡资源搜索算法。该算法综合考虑了节点兴趣及负载情况,以这两类转发因子构建Markov Chain的转移概率矩阵,使得查询沿着转发因子增大的方向扩展采样。通过仿真实验表明,该算法具有较高的搜索效率和较为均衡的网络负载。
[Abstract]:P2P (Peer-to-Peer Network) technology is a hot topic in Internet research. It is widely used in the fields of resource sharing, collaborative work and real-time communication.Unstructured P2P network has been widely used because of its simple topology, easy implementation of fuzzy query and search mechanism.The existing unstructured P2P resource search algorithms are mainly based on the improved flooding algorithm and heuristic algorithm. This algorithm has two main problems: 1) generate a large number of redundant query packets.Because of blind search, search efficiency is low.In view of the shortcomings of flooding search algorithm, the main research work of this paper is as follows.A resource search algorithm based on nodal interest factor is proposed in this paper.The algorithm applies the Markov Chain model to the path selection problem of resource search, and introduces the concept of nodal interest factor, and determines the state transition probability according to the nodal interest factor.When forwarding the request query packet, the algorithm selects the node most capable of sending back the query feedback packet as the next hop, which ensures that the random sampling process can transfer to the target resource node at a faster speed.That is, send the request node can quickly search the requested resources.The simulation results show that compared with the traditional flooding algorithm, the algorithm achieves a higher success rate with less search hops.The resource search algorithm based on the interest factor of nodes only considers the interests of the nodes, and does not consider the load balancing problem of the network. The resource search tasks in the network are concentrated on some nodes with hot resources.Therefore, with the increase of resource search tasks, the network will not guarantee the search performance.In order to solve the load problem, this paper introduces the concept of load factor, and proposes a load balancing resource search algorithm combined with node interest.In this algorithm, the interest and load of nodes are considered synthetically, and the transfer probability matrix of Markov Chain is constructed by using these two kinds of forwarding factors, so that the query can be sampled in the direction of increasing the forwarding factor.The simulation results show that the algorithm has high search efficiency and balanced network load.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02

【参考文献】