Bypassing holes in sensor networks: Load-balance vs. latency

This work addresses problems that arise when geographic routing is used in the presence of holes in wireless sensor networks. We postulate that relying on the existing algorithms for bypassing a coverage hole may cause more severe depletion of the energy reserves among the nodes at (or near) that hole's boundary. This, in turn, will render some of those nodes useless for any routing (and/or sensing) purposes, thereby effectively enlarging the size of existing hole and inducing longer communication delays for certain (source, sink) pairs. We propose heuristics that address these complementary problems: (1) relieving some of the routing-load for the nodes around the boundary of a given hole, for the purpose of extending their lifetime; and (2) reducing the latency of the packets-delivery by using routes that are within certain bounds from the route based on the shortest-path. Our approaches are based on the idea that some of the packets that would (otherwise) need to be routed along the boundary of a given hole, should instead start to deviate from their original path further away from that hole. To investigate the potential benefits, we introduce approximations of the hole's boundary with a rectangle, a circle and an ellipse, respectively. We derive the bounds on reducing the routing latency for these three approximations. Our experiments demonstrate that the proposed approaches not only increase the lifetime of the nodes along the boundary of a given hole and yield a more uniform depletion of the energy reserves in its vicinity, but also reduce the communication latency, compared to the traditional face routing.