Hole Approximation-Dissemination Scheme for Bounded-Stretch Routing in Sensor Networks

The routing stretch in a sensor network with a large hole can be controlled if the network nodes have certain information about the hole location and shape, possibly by using some mechanism for hole boundary approximation and information dissemination. However, a finer approximation (for smaller stretch) leads to higher cost of dissemination, which could be unaffordable for the sensors. We provide an insightful analysis to this fundamental trade-off of the hole approximation problem, using a geometric model. Based on this we discuss an efficient approximation-dissemination scheme using a natural, heuristic approximation technique. For reasonable conditions (network is dense enough apart from the hole), we assure that the routing stretch is under a predefined threshold > 1 while the dissemination cost is also under tight control. Our initial experiment results also confirm that our approach is significantly more efficient and economical, compared to existing proposals.