We present a novel geographical routing scheme for spontaneous wireless mesh networks. Greedy geographical routing has many advantages, but suffers from packet losses occurring at the border of voids. In this paper, we propose a flexible greedy routing scheme that can be adapted to any variant of geographical routing and works for any connectivity graph, not necessarily Unit Disk Graphs. The idea is to reactively detect voids, backtrack packets, and propagate information on blocked sectors to reduce packet loss. We also propose an extrapolating algorithm to reduce the latency of void discovery and to limit route stretch. Performance evaluation via simulation shows that our modified greedy routing avoids most of packet losses.
Geographical routing requires addresses based on geographical coordinates: a node must obtain its location either with a dedicated physical device (e.g. GPS) or through a more complex algorithm, e.g. by estimating the position with respect to its neighbors. propose to construct a local coordinate system for each node and determine the coordinates of its neighbors @cite_3 . Then, they aggregate the local coordinate systems into global coordinates. The authors assume the distance to each neighbor known, but usually it is difficult to obtain. follow a similar approach, but based on the of packets coming from neighbors @cite_5 . A pragmatic approach to this problem is to assume that a subset of mesh routers know their exact positions via GPS devices and other nodes can compute their positions with respect to its neighbors @cite_8 .
@cite_5 @cite_3 @cite_8
2130137998 2109764756 2100465929
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. It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available. 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. 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.