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_32: This paper presents a model for analyzing the performance of transmission strategies in a multihop packet radio network where each station has adjustable transmission radius. A larger transmission radius will increase the probability of finding a receiver in the desired direction and contribute bigger progress if the transmission is successful, but it also has a higher probability of collision with other transmissions. The converse is true for shorter transmission range. We illustrate our model by comparing three transmission strategies. Our results show that the network can achieve better performance by suitably controlling the transmission range. One of the transmission strategies, namely transmitting to the nearest forward neighbor by using adjustable transmission power, has desirable features in a high terminal density environment.
  @cite_3: In multihop packet radio networks with randomly distributed terminals, the optimal transmission radii to maximize the expected progress of packets in desired directions are determined with a variety of transmission protocols and network configurations. It is shown that the FM capture phenomenon with slotted ALOHA greatly improves the expected progress over the system without capture due to the more limited area of possibly interfering terminals around the receiver. The (mini)slotted nonpersistent carrier-sense-multiple-access (CSMA) only slightly outperforms ALOHA, unlike the single-hop case (where a large improvement is available), because of a large area of "hidden" terminals and the long vulnerable period generated by them. As an example of an inhomogeneous terminal distribution, the effect of a gap in an otherwise randomly distributed terminal population on the expected progress of packets crossing the gap is considered. In this case, the disadvantage of using a large transmission radius is demonstrated.
summary: Most algorithms based on position awareness first try to deliver the packet using greedy techniques. For example, the simplest greedy routing technique @cite_28 will forward the packet to the neighbor closest to the destination. Most Forward Routing (MFR) @cite_3 and Nearest with Forwarding Progress (NFP) @cite_32 consider the projected distance on the source-destination line. MFR tries to get closer to the destination by sending the packet to the neighbor with maximum projected distance, while NFP suggests to adjust the transmission power by sending the packet to the neighbor with the smallest projected distance.