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 demonstrating its merits, there has been little work evaluating it in actual sensornet settings. This article 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 that 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: an average of ∼ 1.25 and a 99th 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 scalability at least an order of magnitude better than compact routing, and at the same time, in terms of routing stretch, its performance is within 10--15% of that of compact routing; in addition, this performance can further be tuned to a particular application. Finally, we also identify a number of practical issues and limitations of which we believe sensornet developers adopting hierarchical routing should be aware.