Tree Cover Based Geographic Routing with Guaranteed Delivery

For wireless ad hoc or sensor networks, non-flooding, guaranteed delivery routing protocols are preferred because of limited energy. In this paper we introduce TCGR, a tree cover based geographic routing protocol for wireless networks. We assign to each node a set of short labels such that nodes are embedded in a metric space induced by one or multiple trees. Based on the embedding, we use only greedy routing to deliver packets, i.e., packets are always forwarded to the neighbor closest to the destination. Unlike many previous geographic routing protocols, we guarantee a full success ratio in finding a route to the destination, if such a route exists in the network. Moreover, each node only needs to maintain a small amount of information, which is almost surely bounded by O(log² n) bits, and the label size and packet header size are also bounded by O(log² n) bits. Simulations show TCGR can achieve remarkable performance in both path stretch and node load.