Date Added: Jul 2009
Virtual Coordinate based Routing (VCR) is a class of simple scalable routing schemes for sensor networks. VCR relies on coordinates based on the number of hops to a set of anchors, rather than on geographical coordinates. Multiple nodes with identical coordinates and local minima encountered during routing degrade the performance of VCR. Properties of virtual coordinate systems are analyzed to provide insight into the nature of virtual coordinate space, and bounds are derived for path lengths. A new routing scheme, Convex Subspace Routing (CSR), is proposed. In contrast to existing VCR schemes that use backtracking or hill climbing techniques to overcome local minima, CSR avoids using anchors that cause local minima.