Target guiding self-avoiding random walk with intersection algorithm for minimum exposure path problem in wireless sensor networks

Abstract

Abstract To solve minimum exposure path (MEP) problem in wireless sensor networks more efficiently, this work proposes an algorithm called target guiding self-avoiding random walk with intersection (TGSARWI), which mimics the behavior of a group of random walkers that seek path to their destinations in a strange area. Target guiding leads random walkers move toward their end points, while self-avoiding prevents them from taking roundabout routes. Route intersections further accelerate the speed of seeking connected paths. Dijkstra algorithm (DA) is applied to solve MEP problem in a sub-network formed by multiple connected paths that walkers generate (called TGSARWI DA). Simulations show that the path exposure found by TGSARWI DA is very close to that by DA in the global network (Global DA), whereas the time complexity of computation is much lower. Compared with existing heuristic algorithms such as physarum optimization algorithm (POA), our algorithm shows higher generality and efficiency. This algorithm also exhibits good robustness to the fluctuations of parameters. Our algorithm could be very useful for the solution to MEP problem in fields with large- or high-density sensors.

Keywords

• Minimum exposure path
• Target guiding
• Self-avoiding random walk
• Intersection
• Time complexity of computation
• Robustness