Resource Exploration Using Levy Walk on Unit Disk Graphs

摘要

Random walks play an important role in computer science, spreading a wide range of topics in theory and practice, including networking, distributed systems, and optimization. Levy walk is a family of random walks whose distance of a walk is chosen from the power law distribution. There are lots of works of Lévy walk in the context of target detection in swarm robotics, analyzing human walk patterns, and modeling the behavior of animal foraging in recent years. According to these results, it is known as an efficient method to search in a two-dimensional plane. However, most of the works assume a continuous plane. In this paper, our simulation results indicate that Lévy walk on unit disk graphs is more efficient than other random walks on the resource exploration problem. This result means that Lévy walk can detect illegal data in large-scale delay tolerant sensor networks in realistic time.