On hole approximation algorithms in wireless sensor networks

Abstract

Routing holes in sensor network are regions without operating nodes. They may occur due to several reasons, including cases caused by natural obstacles or disaster suffering areas. Determining the location and shape of holes can help monitor these disaster events (such as volcano, tsunami, etc.) or make smart, early routing decisions for circumventing a hole. However, given the energy limit of sensor nets, the determination and dissemination of the information about the exact shape of a large hole could be unreasonable. Therefore, there are some techniques to approximate a hole by a simpler shape.

In this paper, the authors analyze and compare two existing approximation approaches that are considered as the most suitable for the sensor network, namely the grid-based and the convex-hull-based approaches. And a new algorithm of the grid-based approach is also introduced. The performances of all the mentioned algorithms are under analysis and evaluation in both theoretical and experimental perspectives. The findings show that grid-based approach has advantages in saving network energy and providing a finer image of the hole while the convex hull approach is better for making a shorter hole-bypassing the route but not much.