Convex Subspace Routing (CSR): Routing via anchor-based convex virtual subspaces in sensor networks

Convex Subspace Routing (CSR) is a novel approach for routing in sensor networks using anchor-based virtual coordinates. Unlike geographical routing schemes that require physical location information of nodes, obtaining which is often difficult, error-prone and costly, the Virtual Coordinate (VC) based schemes simply characterize each node by a vector of shortest hop distances to a selected subset of nodes known as anchors. Even though VC based routing (VCR) schemes benefits from having connectivity information implicitly embedded within the VCs, VCs lack the directional information available with physical coordinates. The major issues affecting routing using VCs are addressed. Due to local minima problem in the virtual space, the VCR schemes rely on backtracking or hill climbing techniques to overcome the local minima. Convex Subspace Routing, in contrast, avoids using anchors that cause local minima. It dynamically selects subsets of anchors that define subspaces to provide convex distance functions from source to destination. Consequently, it is less sensitive to anchor placement and over anchoring, and does not require tracking route history for backtracking, resulting in shorter packet lengths and energy efficient operation. Three techniques for selection of convex subspaces are proposed and evaluated. Performance evaluation for several different network topologies indicates that CSR significantly outperforms the existing VCR scheme, Logical Coordinate Routing (LCR), while being competitive with geographic coordinate based Greedy Perimeter Stateless Routing (GPSR), even though latter makes use of node location information.