On hole approximation algorithms in wireless sensor networks


  • Le Phi Nguyen Ha Noi University of science and technology
  • Van Khanh Nguyen Ha Noi University of science and technology




Wireless sensor networks, routing holes, load balancing, energy efficiency.


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.


Metrics Loading ...

Author Biographies

Le Phi Nguyen, Ha Noi University of science and technology

Phi Le Nguyen received the degree “Engineer in Information and Communication” from the University of Tokyo in 2007, the degree “Master of science in Frontier Informatics” from the University of Tokyo in 2010.

She is presently working as a lecturer as well as studying a doctor course at Hanoi University of Science and Technology. His main research interest is Algorithms and Theoretical Models for Computer Networks and Distributed Computing.

Email: lenp@soict.hust.edu.vn

Van Khanh Nguyen, Ha Noi University of science and technology

Khanh-Van Nguyen is a Senior Lecturer at the School of Information and Communication Technologies (SoICT) of Hanoi University of Science and Technology (HUST), where he leads the Software Engineering and Distributed Computing Lab (SEDIC Lab). He received his Ph.D. degree in Computer Science from the University of California, Davis (2006) and also spent one post-doctoral year (2007-08) as a CNRS researcher at University Paris 7 & 11. His main research domain is algorithms and theoretical models for computer networks and distributed computing.

Email: vannk@soict.hust.edu.vn




How to Cite

L. P. Nguyen and V. K. Nguyen, “On hole approximation algorithms in wireless sensor networks”, JCC, vol. 30, no. 4, p. 377, Dec. 2014.



Computer Science