Message Dissemination Using Lévy Flight 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 flight is a family of random walks whose the distance of a walk is chosen from the power law distribution. There are lots of works of Levy flight 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, all these works assume a continuous plane, so far. In this paper, we propose an algorithm for Levy flight and analyze the behavior of the algorithm on unit disk graphs. We also show the comparison of Levy flight with other random walks on the message dissemination problem. Our simulation results indicate that the proposed algorithm is significantly efficient to diffuse messages compared to the other random walks on unit disk graphs.