Proposal of an Efficient Blind Search Utilizing the Rendezvous of Random Walk Agents

摘要

A blind search in a network is used to discover a target node without detailed knowledge on the network. Because of its simplicity and the robust against network uncertainty, the blind search has been widely utilized by diverse applications in different types of networks (e.g., unstructured P2P (Peer-to-Peer) networks, ICNs (Information Centric Networks), mobile ad-hoc networks, and social networks). One of the major drawbacks of the blind search is its inefficiency; i.e., a large number of message exchanges is unavoidable for shortening the search time. In this paper, we propose an efficient blind search method utilizing the rendezvous of multiple random walkers, whose transition probabilities are adjusted based on our analysis results. Through simulation experiments, we show that the performance of the proposed search method is comparable with the flooding, which is the fastest but the least efficient method among blind search methods, and that it requires much smaller message exchanges than the flooding. We also show that the proposed search method works more effectively in scale-free networks than in non-scale-free networks.