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.
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.
@cite_9
2145957138
We propose an energy efficient routing protocol, VCost, for sensor networks. We assume that nodes are unaware of their geographic location thus, VCost assigns virtual coordinates to nodes as follows. Based on the node hop count distances from a set of landmarks, our method computes a distance metric to obtain the node's virtual coordinates. VCost, then uses these coordinates to route packets from node u to node v, in its neighborhood, such that the ratio of the cost to send a message to v to the progress in the routing task towards the destination is minimized. Compared to existing algorithms that use virtual locations, our simulation shows that VCost improves significantly energy consumption and preserves the small percentage of successful routings.