A Case for Hierarchical Routing in Low-Power Wireless Embedded Networks

Hierarchical routing has often been mentioned as an appealing point-to-point routing technique for wireless sensor networks (sensornets). While there is a volume of analytical and high-level simulation results demon-strating its merits, there has been little work evaluating it in actual sensornet settings. This paper bridges the gap between theory and practice. Having analyzed a number of proposed hierarchical routing protocols, we have developed a framework that captures the common characteristics of the protocols and identifies design points at which the protocols differ. We use a sensornet implementation of the framework in TOSSIM and on a 60-node testbed to study various trade-offs hierarchical routing introduces as well as to compare the performance of hierarchical routing with the performance of other routing techniques, namely shortest-path routing, compact routing, and beacon vector routing. The results show that hierarchical routing is a compelling routing technique also in practice. In particular, despite only logarithmic routing state, it can offer small routing stretch: the average of ∼1.25 and the 99-th percentile of 2. It can also be robust, minimizing the maintenance traffic or the latency of reacting to changes in the network. Moreover, the trade-offs offered by hierarchical routing are attractive for many sensornet applications when compared to the other routing techniques. For example, in terms of routing state, hierarchical routing can offer at least an order of magnitude better scalabilit