  We introduce and evaluate a very simple landmark-based network partition
technique called Hierarchical Bipartition Routing (HBR) to support routing with
delivery guarantee in wireless ad hoc sensor networks. It is a simple routing
protocol that can easily be combined with any other greedy routing algorithm to
obtain delivery guarantee. The efficiency of HBR increases if the network is
sparse and contains obstacles. The space necessary to store the additional
routing information at a node u is on average not larger than the size
necessary to store the IDs of the neighbors of u. The amount of work to setup
the complete data structure is on average proportional to flooding the entire
network log(n) times, where n is the total number of sensor nodes. We evaluate
the performance of HBR in combination with two simple energy-aware geographic
greedy routing algorithms based on physical coordinates and virtual
coordinates, respectively. Our simulations show that the difference between
using HBR and a weighted shortest path to escape a dead-end is only a few
percent in typical cases.
