tailieunhanh - On hole approximation algorithms in wireless sensor networks

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 convexhull-based approaches. | Journal of Computer Science and Cybernetics, , (2014), 377–396 DOI: ON HOLE APPROXIMATION ALGORITHMS IN WIRELESS SENSOR NETWORKS NGUYEN PHI LE, NGUYEN KHANH-VAN Hanoi University of Science and Technology lenp@; vannk@ 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 sensornets, 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 convexhull-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 shorter hole-bypassing route but not much. Keywords. Wireless sensor networks, routing holes, load balancing, energy efficiency. 1. INTRODUCTION Wireless sensor networks (WSN) have a wealth of applications. Especially, they are widely used in monitoring and investigating certain landscapes or environments which may be too large or remote for deploying wired network infrastructure or of too harsh conditions that are not suitable for traditional surveillance by human beings. Different from early wired networks,