| 摘要: |
| 降低搜索过程中产生的大量网络开销,是非结构P2P 网络重点研究内容之一.泛洪算法和随机查找算法简单且易于实现,但其在搜索过程中产生的大量冗余消息是造成大量网络开销的主要原因.针对这一问题,提出一种受限搜索机制(restricted forward search algorithm,简称RFSA),定义了搜索路径和冗余搜索路径,引入本地消息索引缓存机制,通过节点对消息的受限接收,消除节点对消息的重复接收与转发;利用搜索过程中携带的实时搜索路径信息,选择未出现在搜索路径中的邻居节点对消息进行转发,消除冗余搜索路径的产生.从理论上分析了RFSA 所产生的消息数目和网络开销.模拟实验分别从网络开销、查询点击率、搜索覆盖率和产生的冗余消息数目等方面对受限机制下和非受限机制下的泛洪算法和随机查找算法进行了对比分析,结果表明,在搜索覆盖率和查询点击率基本相同的情况下,受限机制下的泛洪算法和随机查找算法能够减少大量冗余消息的产生,降低了网络开销. |
| 关键词: Peer-to-Peer 非结构网络 受限搜索 冗余搜索路径 |
| DOI：10.3724/SP.J.1001.2013.04359 |
| 分类号: |
| 基金项目:国家自然科学基金(60872051);北京市教育委员会共建项目 |
|
| Limited Search Mechanism for Unstructured Peer-to-Peer Network |
|
MEI Hong-Yan1,2, ZHANG Yu-Jie1,2, MENG Xiang-Wu1,2, MA Wen-Ming1,2
|
|
1.Beijing Key Laboratory of Intelligent Telecommunications (Beijing University of Posts and Telecommunications), Beijing 100876, China;2.School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
|
| Abstract: |
| Reducing the network overhead generated during the search is important in the study of unstructured P2P network. Flooding and random walks are simple and easily implemented. However, a large number of redundant messages generated in the search process are the main reason of producing excessive network overhead. An effective limited search mechanism RFSA (restricted forward search algorithm) is proposed. The search path and redundant search path are defined. As the query messages reaching the node are received by introducing the local messages index caching mechanism, the repeat messages forwarding are eliminated. Using the real-time search path information carried in the search process, the neighbor notes that do not appear in the search path are selected to forward the query messages. Theoretically, the number of messages and network overhead generated by the RFSA. In the simulation, comparative analysis of the limited search mechanism and non-limited mechanism flooding and random walk algorithm is done in the network overhead, query hit rate, search coverage rate, and the number of redundant messages, etc. The results show that this method reduces the generation of a great number of redundant messages, and cuts down the network overload. |
| Key words: peer-to-peer unstructured network limited search redundant search path |
