A scalable logical coordinates framework for routing in wireless sensor networks

Routing is one of the key challenges in sensor networks that directly affects the information throughput and energy expenditure. Geographic routing is the most scalable routing scheme for statically placed nodes in that it uses only a constant amount of per-node state regardless of network size. The location information needed for this scheme, however, is not easy to compute accurately using current localization algorithms. In this paper, we propose a novel logical coordinate framework that encodes connectivity information for routing purposes without the benefit of geographic knowledge, while retaining the constant-state advantage of geographic routing. In addition to efficiency in the absence of geographic knowledge, our scheme has two important advantages: (i) it improves robustness in the presence of voids compared to other logical coordinate frameworks, and (ii) it allows inferring bounds on route hop count from the logical coordinates of the source and destination nodes, which makes it a candidate for use in soft real-time systems. The scheme is evaluated in simulation demonstrating the advantages of the new protocol.