SWAPS:一种基于Small World的文件搜索算法  

Small World Based Adaptive Probabilistic Search (SWAPS) for Unstructured Peer-to-Peer File Systems

作　　者：冯国富[1] 毛莺池[1] 陆桑璐[1] 陈道蓄[1] 

机构地区：[1]南京大学计算机科学与技术系

出　　处：《计算机研究与发展》2006年第3期395-401,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60402027);国家"八六三"高技术研究发展计划基金项目(2001AA112090);国家"九七三"重点基础研究发展规划基金项目(2002CB312002)~~

摘　　要：资源发现是P2P应用所面临的最核心问题之一.无结构P2P方面的已有工作主要采用了查询消息泛洪和信息索引机制,这会造成严重的网络带宽负担以及巨大的索引维护开销.提出了一种无结构P2P环境下能够节约带宽、易维护的自适应搜索算法,即SWAPS.SWAPS根据用户的访问历史抽取用户的兴趣属性,并遵循用户的访问行为模式,以自发的方式组织基于用户兴趣属性的应用层SmallWorld覆盖网络,然后基于覆盖网络实现了高效的文件定位.分析了影响搜索性能的关键因素,针对Small World网络特点分别设计了基于兴趣度、基于本体距离和基于兴趣宽度等有效的查询消息转发策略.最后实验显示,SWAPS以其高成功率、低带宽消耗和很小的响应时间能够显著的提高搜索性能,而且对用户的访问行为体现出良好适应性.One of the essential problems in P2P is the strategy for resource discovery. Related methods in unstructured P2P systems either depend on the flooding and its variations or utilize various indices, which results in too much traffic load to forward messages or too expensive cost to maintain the indices. Presented in this paper is an adaptive, bandwidth-efficient and easy to maintain search algorithm for unstructured P2P file systems-small world based adaptive probabilistic search （SWAPS）. In SWAPS, the users＇ access interest attributes are mined based on ontology tree. And following the behavior patterns of users, interest attributes based small world overlay network is spontaneously constructed. The key factors influencing the locating performance in SWAPS are also analyzed and efficient routing algorithm （interest rank based, ontology distance based and interest breadth based） is designed. And the final simulation experiment shows that the small world based locating algorithm in unstructured P2P can remarkably improve the search efficiency with the small average path length, high success rates, very low bandwidth consumption and the eminent adaptability to access behaviors of the users.

关 键 词：P2P SMALL World 层次本体树 转发策略 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]