硕士学位一种分布式资源定位机制研究

学校代码：10254密级：论文编号：上海海事大学SHANGHAI MARITIME UNIVERSITY硕士学位论文MASTER DISSERTATION论文题目： 一种分布式资源 定位机制研究 学科专业： 计算机应用技术 作者姓名： 夏振华 指导教师： 史小宏 副教授 完成日期： 二一零年五月 论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其它人或其学校代码：10254密 级：论文编号：它机构已经发表或撰写过的研究成果。其它同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。作者签名： 日期：论文使用授权声明本人同意上海海事大学有关保留、使用学位论文的规定，即：学校有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布论文的全部或部分内容，也可以采用影印、缩印或者其它复印手段保留论文。保密的论文在解密后遵守此规定。作者签名： 导师签名： 日期：摘 要摘 要分布式系统由一系列分散的网络节点组成，在各个节点间进行资源和信息的交流，最重要的问题之一就是资源的定位，这也是最难实施的机制之一。本文分析了国内外分布式资源定位研究现状与分布式资源定位的相关内容，包括现有的资源定位发现机制以及小世界模型概念，阐述了幂律和小世界模型对资源定位机制的影响。我们提出了 CARLM(Clusting And Agent Based Resource Location Model)模型，它以日本大阪大学的分布式框架 PIAX 为基础。CARLM 是基于网络拓扑的资源定位模型，在覆盖网络中利用聚类技术把节点分成多个兴趣簇，每个兴趣簇是一个逻辑类似的小组；并给出了 Cluster 的形成、维护策略以及本地缓存信息。 在 CARLM 模型的基础上扩展一个基于聚类和 Agent 的分布式资源定位算法 FCB：网络内任一结点在发起资源查询请求时，搜索 Agent 首先查看结点所在簇内其他结点是否能满足查询请求，使用泛洪查询方法；当簇内查询得不到满足时，簇内结点通过转发结点向簇外结点发送资源请求消息，并使用蚁群算法。泛洪算法和蚁群算法配合使用，目的是在 Agent 迁移中实现进一步的性能提高：泛洪在簇内可以实现快速的资源发现而不会产生太多的信息量；聚类使得关联节点间逻辑距离缩短；蚁群算法使得 Agent 向着资源丰富的节点移动；在簇外对迁移路径进行选择时，又利用了概率选择的方法，使搜索 Agent 向着资源丰富的节点移动的同时又不至于使某条资源丰富的路径堵塞。为了验证本文提出的模型和算法，我们在 Peesim 仿真平台和 AgentSpace 上进行了资源定位模拟实验，对泛洪算法和 FCB 以及没有利用蚁群算法的 FCB进行了查询信息量、平均查找成功率以及平均跳数的性能的对比，实验表明算法 FCB 更有效。关键词：资源定位，小世界，CARLM，FCB，蚁群算法， 移动 Agent ABSTRACTABSTRACTThe distributed system consists of a number of decentralized network nodes that are capable of sharing resources and informations. One of the most important functions in distributes system is the location of resources, and it is one of the hardest targets to achieve.In this thesis, we firstly outlines the current research status about the resource location of distributes system at home and abroad, and then introduced the distributed resources location-related content, including the existing resource location discovery mechanism and the concept of small-world model ,and describe the impact on the resource location mechanism which the power-law and small-world model have.We propose CARLM model (Clusting And Agent Based Resource Location Model), which is bases on the distributed system framework PIAX that is proposed on the University of Osaka, Japan. CARLM is based on the network topology, which uses clustering technology to put nodes into several clusters in the overlay network, each cluster is a logically similar groups; and then we describe the Cluster formation, maintenance strategy and the local cache information.we expand a clustering and Agent-based distributed resource location algorithm FCB: when any node within the network launch a request, the search Agent examines other nodes in the same Cluster to see whether the nodes are able to satisfy the query request or not, in which uses the flooding method; When the inquiry is not satisfied in cluster, the forward node sends the resource request message to the node outside the cluster, in which uses the ant colony algorithm. The conjunction of Flooding algorithm and ant colony algorithm is to achieve the further performance improvement in the Agent migration. The Flooding can locate the resource quickly without creating too many messages in the cluster; Clustering makes the logical distance between correlated nodes shorter. Integrating ACO is expected to ABSTRACTstrengthen the connections to resource-rich nodes. When selecting the link between nodes, we use probabilistic selection to make the Search Agent migrate to the resource-rich nodes without rendering the path of a certain resource-rich link block.In order to verify the proposed model and algorithm, we make the simulated experiment of resource location in PeerSim and AgentSpace, and compare our approach FCB with flooding algorithm and FCB without ACO in terms of Querying traffic, Average Success rate and Average Hop count. And the experiment shows that the FCB algorithm is more effective.Keywords： Resource Discovery, Small-World, CARLM, FCB, ACO, Mobile Agent目 录目 录第一章 绪论 .11.1 分布式资源定位研究现状 .11.1.1 资源定位发展过程 .11.1.2 国内研究情况 .21.1.3 国外研究情况 .31.2 本文研究工作 .41.3 本文的组织结构 .5第二章 分布式网络资源定位 .72.1 资源定位 .72.1.1 组成部分 .72.1.1.1 资源描述 .72.1.1.2 资源信息组织 .82.1.1.3 资源请求处理 .102.1.1.4 资源选择 .102.1.2 资源发现的要素和类型 .112.1.2.1 网格中的资源发现 .122.1.2.2 P2P 网络中的资源发现 .122.1.2.3 移动自组网中的资源发现 .142.1.2.4 其他分布式系统中的资源发现 .142.2 现有资源定 位技术 .152.2.1 集中式发现机制 .152.2.2 分布式结构化发现机制 .162.2.3 半分布式发现机制 .172.2.4 基于移动 Agent 的分布式资源定位方法 .172.2.5 分布式非结构化发现机制 .182.3 小 世界模型 .192.3.1 小世界和幂律特性 .19目 录2.3.2 小世界拓扑生成方法 .212.3.3 小世界模型对资源定位技术的影响 .222.3.4 基于小世界模型的资源定位策略 .232. 4 本章小结 .23第三章 分布式资源定位模型 CARLM .243.1 CARLM 设计思想 .243.2 CARLM 系统模型 .253.3 覆盖网络 .273.3.1 节点关联度定义 .283.3.2 Cluster 形成 .293.3.3 Cluster 维护 .323.4 本地缓存信息 .333.4.1 节点本地 IA 信息 .333.4.2 节点管理表 NMT .333.4.3 历史路径信息 .343.5 本章小结 .34第四章 CARLM 模型中资源定位机制 FCB.354.1 蚁群聚类思想 .354.1.1 Clusting .354.1.2 Ant Colony Optimization.364.2 资源定位机制 FCB .384.2.1 FCB 算法 .394.2.2 簇内路由算法 .404.2.3 簇外路由算法 .414.3 CARLM 中资源搜索策略 .444.4 算法分析 .46目 录4.5 本章小结 .47第五章 资源定位实验 .495.1 实验环境 .495.2 实验执行 .505.3 算法性能比较 .545.3.1 查询信息量 .545.3.2 平均查找成功率 .555.3.2 平均跳数 .565.4 本 章小结 .57第六章 总结与展望 .586.1 本文工作总结 .586.2 展望 .59致谢 .60参考文献 .61攻读学位期间发表的学术论文 .64第一章 绪论1第一章 绪论1.1分布式资源定位研究现状1.1.1资源定位发展过程随着互联网在世界各地进行快速传播，它经常被用来人类的各种交互活动。在各种应用软件间进行的用户交互要求软件能够与网络社区进行交流信息和资源。传统客户机浏览器模式仅能体现真实世界的情况，如视频流媒体服务的出现。在服务器上进行密集的访问会带来瓶颈问题。对等网络系统可以提供一个解决这个问题的方法。分布式系统是由一系列分散的网络节点组成的，这些节点能够分享资源，而不需要中央服务器的支持。已经存在很多应用，如 IP 电话，内容交付网络(CDN)和分布式计算都采用了分布式技术，并把它运用到基本的通信系统中。分布式系统在各个节点间进行资源和信息的交流。分布式系统包括一个覆盖网络，其中节点可以相互交流并分享彼此的资源。在这里， “资源”指的是由网络节点提供的各种服务。分布式系统中最重要的问题之一就是资源的定位，而这也是最难实施的机制之一。Napster 公司通过提供索引服务的中央服务器来解决这个问题 1。但是，这种服务器的问题是，如果出现错误就可能使整个网络瘫痪。因此，不含有任何中央服务器的分布式系统是当前的分布式系统发展领域的研究重点。著名的分布式系统 Gnutella2，采用消息 Flooding 来定位资源。这种系统的优点是简单，但它对于大型网络系统是不切实际的，因为仅仅 Flooding 的资源发现消息就很容易使整个网络达到饱和状态。为了解决这个问题，分布式哈希表(DHT)被提出并使用 3 4 5 6。虽然 DHT 是最有前途的方法之一，并且它能提供对分布式系统的快速资源查找效率(计算复杂度为 O(log n)，但是它具有下列缺点：1) 由于 DHT 的基本机制是映射关键字到节点，所以很难找到基于多个关键字的对象或对象中的内容，2)是很难找到与给定的一个关键字或一组关键字相关的多个节点。换句话说，基于 DHT 的资源查找方法过于僵化导致处理不够灵活和查询不够智能。为了减轻 DHT 系统的僵化，一些分布式系统利用信息 Flooding 进行对象第一章 绪论2的查找，以补充 DHT 的不足 7。由于消息 Flooding 会产生密集的通信量，它对那种间歇性网络连接的移动通信环境是不适合的。由于 DHT 在拓扑结构的维护上存有严重的问题，目前对分布式系统的研究侧重于控制和约束信息 Flooding 技术。整个 Gnutella 系统采用了一个叫做动态查询(DQ) 的受控 Flooding 技术，其中，DQ 技术预测了一个合适的生存期(TTL)值，以减少网络流量负载 8。Jian 等提出了一个加强的 DQ 技术，它采用一种置信区间的方法，使它能够进一步减少网络流量负载 9。另一方面，移动 Agen