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_4: Landmark Routing is a set of algorithms for routing in communications networks of arbitrary size. Landmark Routing is based on a new type of hierarchy, the Landmark Hierarchy. The Landmark Hierarchy exhibits path lengths and routing table sizes similar to those found in the traditional area or cluster hierarchy. The Landmark Hierarchy, however, is easier to dynamically configure using a distributed algorithm. It can therefore be used as the basis for algorithms that dynamically configure the hierarchy on the fly, thus allowing for very large, dynamic networks. This paper describes the Landmark Hierarchy, analyzes it, and compares it with the area hierarchy.
  @cite_23: Hierarchical routing is a promising approach for point-to-point routing with very small routing state. While there are many theoretical analyses and high-level simulations demonstrating its benefits, there has been little work to evaluate it in a realistic wireless sensor network setting. Based on numerous proposed hierarchical routing infrastructures, we develop a framework that captures the common characteristics of the infrastructures and identifies design points where the infrastructures differ. We then evaluate the implementation of the framework in TOSSIM and on a 60-node testbed. We demonstrate that from the practical perspective hierarchical routing is also an appealing routing approach for sensor networks. Despite only logarithmic routing state, it can offer low routing stretch: the average of ∼1.25 and the 99-th percentile of 2. Moreover, a hierarchical routing infrastructure can be autonomously bootstrapped and maintained by the nodes. By exploring the design points within our framework, the hierarchy maintenance protocol can optimize different metrics, such as the latency of bootstrapping and repairing the hierarchy after failures or the traffic volume, depending on the application requirements. Finally, we also identify a number of practical issues which we believe the applications employing hierarchical routing should be aware of.
  @cite_2: A scalable object location service can enable users to search for various objects in an environment where many small, networked devices are attached to objects. We investigate two hierarchical, self-configuring or unattended approaches for an efficient object location service. Each approach has its advantages and disadvantages based on the anticipated load. The first approach, SCOUT-AGG, is based on aggregation of object names. The second approach, SCOUT-MAP, is based on indirection, where information about an object is stored at the locator sensor for the object. The relative efficiency of SCOUT-AGG and SCOUT-MAP can be characterized by the query to mobility, update rate of the system. SCOUT-AGG performs better for low query to update rate but its performance deteriorates in general relative to SCOUT-MAP as the queries to update rate increases. The rate of performance deterioration depends on query specificity (i.e., queries for a specific object or for any object of a particular type). SCOUT-MAP generally exhibits better load balancing than SCOUT-AGG for various scenarios. We support the above results through simple analytical modeling and simulation.
summary: An alternative way for delivery guarantee can be obtained by hierarchical addressing, see for example @cite_4 . Tsuchiya solves this problem by allowing nodes to self configure their addresses. The protocol uses a hierarchical set of landmark nodes that periodically send scoped route discovery messages. A node's address is the concatenation of its closest landmark at each level in the hierarchy. The overhead of route setup can be reduced to @math and nodes only hold state for their immediate neighbors and their next hop to each landmark. However, this requires a protocol that creates and maintains this hierarchy of landmarks and appropriately tunes the landmark scopes. Recent proposals adopting this approach have been fairly complex @cite_2 in contrast to our design goal of configuration simplicity, see also @cite_23 for an overview.