text: 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.
  @cite_9: In this paper we consider the problem of constructing a coordinate system in a sensor network where location information is not available. To this purpose we introduce the virtual coordinate assignment protocol (VCap) which defines a virtual coordinate system based on hop distances. As compared to other approaches, VCap is simple and have very little requirements in terms of communication and memory overheads. We compare by simulations the performances of greedy routing using our virtual coordinate system with the one using the physical coordinates. Results show that the virtual coordinate system can be used to efficiently support geographic routing.
summary: Our second greedy routing protocol is based on virtual coordinates which we will define by four landmark nodes denoted by @math , @math , @math , and @math . These four landmark nodes are selected similarly as in VCap (virtual coordinate assignment protocol) from @cite_9 . The first landmark node @math is one of the nodes with maximum @math -distance to an arbitrary node @math . The second landmark node @math is one of the nodes with maximum @math -distance to @math . The third landmark node @math is one of the nodes for which [d^ (C,A)+d^ (C,B)-2 |d^ (C,A)-d^ (C,B)| ] is maximum. And finally, the fourth landmark node @math is one of the nodes for which [d^ (D,C)-|d^ (D,A)-d^ (D,B)| ] is maximum. Since will consider energy efficient routing, we use the @math -distances instead of hop distances @cite_9 for the computation of the virtual addresses.