TELPAC: A Time and
Energy Efficient Protocol for Locating and Patching Coverage Holes in
WSNs <Abstract> Guaranteeing sufficient sensing coverage is of prime importance in wireless sensor networks. Unfortunately, due to many reasons such as natural disruptions, adversarial attacks, or energy depletion, the occurrence of coverage holes is unavoidable. In order to assure the quality of service, coverage holes should be patched (i.e. by deploying new sensors) as soon as they appear. The solutions in state-of-the-art protocols still incur time complexity and energy overhead that increase with the size of coverage holes. To avoid that issue, this paper introduces a novel protocol (namely, TELPAC) which efficiently locate the hole boundary and determine the patching locations. The main idea behind TELPAC is to approximate the hole by a polygon whose edges are aligned by a regular triangle lattice. Based on such approximation, the patching locations are then detected by using a regular hexagon tessellation. We theoretically prove that TELPAC can detect all coverage holes in the network. The simulation results show that the number of patching locations required by TELPAC is one of the smallest. Moreover, TELPAC can reduce more than 50% of the time consumed and energy overhead in comparison with the existing protocols. |