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.
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.
@cite_4 @cite_23 @cite_2
1993248613 2170977078 2098596524
This paper considers the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. We propose Hector, a hybrid energy efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted tree coordinates, and the other is based on hop distances toward several landmarks. In our algorithm, the node currently holding the packet forwards it to its neighbor that optimizes ratio of power cost over distance progress with landmark coordinates, among nodes that reduce landmark coordinates and do not increase tree coordinates. If such a node does not exist then forwarding is made to the neighbor that reduces tree based distance and optimizes power cost over tree distance progress ratio. Our simulations show the superiority of our algorithm over existing alternatives while guaranteeing delivery, and only up to 30 additional power compared to centralized shortest weighted path algorithm. 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. We present gradient landmark-based distributed routing (GLIDER), a novel naming addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic locations are not necessarily known), and that each node can communicate wirelessly with some of its geographic neighbors - a common scenario in sensor networks. We develop a protocol which in a preprocessing phase discovers the global topology of the sensor field and, as a byproduct, partitions the nodes into routable tiles - regions where the node placement is sufficiently dense and regular that local greedy methods can work well. Such global topology includes not just connectivity but also higher order topological features, such as the presence of holes. We address each node by the name of the tile containing it and a set of local coordinates derived from connectivity graph distances between the node and certain landmark nodes associated with its own and neighboring tiles. We use the tile adjacency graph for global route planning and the local coordinates for realizing actual inter- and intra-tile routes. We show that efficient load-balanced global routing can be implemented quite simply using such a scheme. 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.