Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

4.7 GEOROUTING WITH VIRTUAL AND TREE COORDINATES

The accuracy of exact geographic coordinates that is currently available is not sufficient to support the claimed performance of georouting algorithms. An alternative solution is to use virtual coordinates instead of real ones. The typical approach is to assign hop count distances to a certain set of landmark nodes as coordinates of sensor nodes, and define the distance between nodes as the sum of (absolute values of) differences in hop count toward these landmarks (this is also called Hamming distance). Greedy routing can be applied to these coordinates (Caruso et al., 2005). The problem, however, is that different nodes can have the same coordinates. The sensors are not properly sorted in such coordinates, and greedy routing may lead to a node that is local minima by Hamming distance. A resolution is proposed in Chavez et al. (2007) by adding tree coordinates to nodes, rooted from a landmark node. Greedy routing then proceeds by considering only neighbors that provide progress in tree coordinates. The combined set of two virtual coordinates then enables routing with guaranteed delivery.

Mitton et al. (2008) consider the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. They proposed HECTOR, a hybrid energy-efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted ...