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

引言

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

　　1.算法研究现状

　　p2p网络中的资源搜索算法是指将对特定资源的查询请求路由到目标节点集合的方法，即只要命中目标集中的任意节点，则路由过程结束。p2p网络的性能是靠搜索算法的优劣来决定的，当前对非结构化对等网络在搜索算法上的研究已经相当成熟，依照搜索策略，搜索算法分为两类：盲目搜索和启发式搜索。盲目搜索通过洪泛、随机游走的方式在网络中传播查询信息，将信息不断扩散给邻居节点，以此查询到想要的资源。在搜索的过程中，启发式搜索是利用节点存储的信息来帮助搜索过程，即每当查询信息到达时，先检索本地存储的信息，就可以较快地定位到响应该查询的节点，启发式搜索是以存储的代价交换网络流量和时延降低的算法。

　　1.洪泛：洪泛算法是一种简单的广播式搜索算法。该算法搜索的深度由ttl控制，搜索节点requester每传播一步ttl减1，如果ttl减到0还没有搜索到资源，则停止。访问节点数目的降低直接导致查询精度的下降和查询步数的增加，因此洪泛算法无法达到较优的搜索效率。

　　3.负载均衡算法：在非结构化p2p网络中由于底层网络拓扑结构化映射的，所以不需要进行精确的匹配，网络的负载不仅是源于对数据资源的请求，更重要的还来源于对计算资源的请求。这即是说，非结构化p2p网络可以更好的支持动态任务调度，即对最优执行节点的请求资源。基于非结构化p2p网络的负载分配算法主要有随机算法，负载扩散和负载迁移等。考虑整体网络的负载均衡，使得整个网络环境能更好的工作，但是由于没有考虑搜索效率故会导致搜索效率下降。

　　2.基于markov chain的搜索算法

　　基于非结构化p2p网络传统的搜索算法，虽然都能较好的完成对各类资源的搜索，但是存在一定的局限性及缺点。分析存在的问题：洪泛算法在搜索过程中产生了大量的网络冗余包，对网络本身造成一定的负担；随机漫步算法属于盲目搜索算法，其在搜索过程中是随机选择目标进行查询，并不能有较好的搜索成功率；一般意义上的路由缓存算法并不能实时的借鉴之前搜索的失败经验。

　　在本论文工作中，将马尔科夫链应用到搜索算法中，即在每一时态节点进行搜索查询时按照转移概率矩阵选择下一邻近节点，并在该过程中动态更新转移概率矩阵。提出一种基于马尔科夫链模型的资源搜索改进算法：1.根据节点兴趣确定本地节点转发到下一节点的一步转移概率；2.构造能够反映节点负载状况或负载处理能力的负载因子，并也将以此为基础作为节点选择的参考标准构造转移概率；3.以吸收态的马尔科夫链为基础构造能够收敛到转发因子极值点的随机采样模型（此处所说的转发因子：综合考虑兴趣因子及负载因子确定转发因子）。该算法将被设计为保证随机采样过程以最快的速度向转发因子极值收敛。

　　2.1基于兴趣服务的资源搜索

　　基于服务的p2p资源网络是系统控制流和数据流运行的自组织环境，构成系统的基础结构。p2p网络执行节点的加入、自组织、离开、资源搜索的负载分配均通过该非结构化p2p网络实现。

　　假设存在一个逻辑上的网络，基于一般意义上的p2p资源共享网络模型，其中的节点均与其他节点保持连接，以gnutella为例，连接的数量是由存储在节点上的资源数目所决定的。若节点p与q在网络中是直接连接的我们就说p的直接相连节点为q；同理，若节点p与q在网络中不是直接相连并且之间存在可访问的通路，我们就说p与q是间接相连。由此我们可以看到，p2p资源网络是对称的，且在任何时间选择节点建立连接或者解除连接。如图1所示。