A Hole Avoiding Routing Protocol Using a Relative Neighborhood Graph for Wireless Sensor Networks

Abstract

In wireless sensor networks, ”holes” are difficult to find and avoid because of various actual geographical environments. A hole can form dynamically due to unbalanced deployment, failure or power exhaustion of sensors, animus interference, or physical barriers such as buildings or mountains. Hence, we propose a novel algorithm, the Relative Neighborhood Graph Hole Avoiding Routing protocol (RNGHAR), which uses relative neighborhood graphs (RNG) to model holes so that hole information can be collected in order to construct a routing path that avoids holes in advance. Therefore, event packets will be guided to avoid the hole and move along the shortest path from the source node to the sink node. Simulations show that the proposed method achieves good performance in terms of the average hop count, packet delivery success rate, and power consumption in comparison with existing protocols.