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_28: Abstract : Digital packet networking technology is spreading rapidly into the commercial sector. Currently, most networks are isolated local area networks. This isolation is counterproductive. Within the next twenty years it should be possible to connect these networks to one another via a vast inter network. A metropolitan inter network must be capable of connecting many thousand networks and a national one several million. It is difficult to extend current inter networking technology to this scale. Problems include routing and host mobility. This report addressed these problems by developing an algorithm that retains robustness and has desirable commercial characteristics.
  @cite_13: In this article we propose several new progress based, localized, power, and cost aware algorithms for routing in ad hoc wireless networks. These algorithms attempt to minimize the total power and or cost needed to route a message from source to destination. In localized algorithms, each node makes routing decisions solely on the basis of location of itself, its neighbors and destination. The new algorithms are based on the notion of proportional progress. A node currently holding the packet will forward it to a neighbor, closer to destination than itself, which minimizes the ratio of power and or cost to reach that neighbor, and the progress made, measured as the reduction in distance to destination, or projection along the line to destination. First, we propose Power Progress, Iterative Power Progress, Projection Power Progress, and Iterative Projection Power Progress algorithms, where the proportional progress is defined in terms of power measure. The power metrics are then replaced by cost or power-co...
  @cite_33: Suppose that a traveler arrives to the City of Toronto, and wants to walk to the famous CN-Tower, one of the tallest free-standing structures in the world. Assume now that our visitor, lacking a map of Toronto, is standing at a crossing from which he can see the CN-tower, and several streets S1, . . . , Sm that he can choose to start his walk. A natural (and most likely safe assumption), is that our visitor must choose to walk first along the road that points closest in the direction of the CN-tower, see Figure 1. A close look at maps of numerous cities around the world, show us that the previous way to explore a new, and unknown city will in general yield walks that will be close enough to the optimal ones to travel from one location to another. In mathematical terms, we can model the map of many cities by geometric graphs in which street intersections are represented by the vertices of our graphs, and streets by straight line segments. Compass routing on geometric networks, in its most elemental form yields the following algorithm:
summary: Greedy routing algorithms can easily be extended by taking into account power consumption. Power aware greedy routing in most cases tries to minimize the ratio of the energy consumed by a transmission to the progress made. The progress is the distance reduction towards the destination. This cost over progress (COP) power-aware framework is first introduced in @cite_13 . If the cost is equal for all connections, we obtain the simple greedy algorithm as already discussed above @cite_28 . If the cost of a connection is proportional to the distance between the nodes, the resulting routing is similar to compass routing @cite_33 .