{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:58Z","timestamp":1750307038847,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001870","name":"Foundation For Polish Science","doi-asserted-by":"publisher","award":["HOMING PLUS\/2010-2\/4"],"award-info":[{"award-number":["HOMING PLUS\/2010-2\/4"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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 \u223c 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.<\/jats:p>","DOI":"10.1145\/2240092.2240099","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:21:06Z","timestamp":1347402066000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A case for hierarchical routing in low-power wireless embedded networks"],"prefix":"10.1145","volume":"8","author":[{"given":"Konrad","family":"Iwanicki","sequence":"first","affiliation":[{"name":"University of Warsaw, Warszawa, Poland"}]},{"given":"Maarten","family":"Van Steen","sequence":"additional","affiliation":[{"name":"VU University Amsterdam, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2012,8,2]]},"reference":[{"volume-title":"Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'00)","author":"Amis A. D.","unstructured":"Amis , A. D. , Prakash , R. , Vuong , T. H. P. , and Huynh , D. T . 2000. Max-min d-cluster formation in wireless ad hoc networks . In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'00) . 32--41. Amis, A. D., Prakash, R., Vuong, T. H. P., and Huynh, D. T. 2000. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'00). 32--41.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Bandyopadhyay S.","unstructured":"Bandyopadhyay , S. and Coyle , E. J . 2003. An energy efficient hierarchical clustering algorithm for wireless sensor networks . In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03) . 1713--1723. Bandyopadhyay, S. and Coyle, E. J. 2003. An energy efficient hierarchical clustering algorithm for wireless sensor networks. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03). 1713--1723.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/313239.313282"},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. MIT-LCS-TR-837","author":"Chen B.","year":"2002","unstructured":"Chen , B. and Morris , R . 2002 . L&plus;: Scalable landmark routing and address lookup for multi-hop wireless networks. Tech. Rep. MIT-LCS-TR-837 , Massachusetts Institute of Technology , Cambridge, MA . Chen, B. and Morris, R. 2002. L&plus;: Scalable landmark routing and address lookup for multi-hop wireless networks. Tech. Rep. MIT-LCS-TR-837, Massachusetts Institute of Technology, Cambridge, MA."},{"key":"e_1_2_1_5_1","volume-title":"Tech. Rep. TR04-433","author":"Du S.","year":"2004","unstructured":"Du , S. , Khan , A. , PalChaudhuri , S. , Post , A. , Saha , A. K. , Druschel , P. , Johnson , D. B. , and Riedi , R . 2004 . Self-organizing hierarchical routing for scalable ad hoc networking. Tech. Rep. TR04-433 , Rice University , Houston, TX . Du, S., Khan, A., PalChaudhuri, S., Post, A., Saha, A. K., Druschel, P., Johnson, D. B., and Riedi, R. 2004. Self-organizing hierarchical routing for scalable ad hoc networking. Tech. Rep. TR04-433, Rice University, Houston, TX."},{"volume-title":"Proceedings of the 12th USENIX Workshop on Hot Topics in Operating Systems (HotOS XII).","author":"Dutta P.","unstructured":"Dutta , P. and Culler , D . 2009. Mobility changes everything in low-power wireless sensornets . In Proceedings of the 12th USENIX Workshop on Hot Topics in Operating Systems (HotOS XII). Dutta, P. and Culler, D. 2009. Mobility changes everything in low-power wireless sensornets. In Proceedings of the 12th USENIX Workshop on Hot Topics in Operating Systems (HotOS XII).","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the Sixth ACM Workshop on Hot Topics in Networks (HotNets-VI).","author":"Fonseca R.","unstructured":"Fonseca , R. , Gnawali , O. , Jamieson , K. , and Levis , P . 2007. Four-bit wireless link estimation . In Proceedings of the Sixth ACM Workshop on Hot Topics in Networks (HotNets-VI). Fonseca, R., Gnawali, O., Jamieson, K., and Levis, P. 2007. Four-bit wireless link estimation. In Proceedings of the Sixth ACM Workshop on Hot Topics in Networks (HotNets-VI).","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05)","author":"Fonseca R.","unstructured":"Fonseca , R. , Ratnasamy , S. , Zhao , J. , Ee , C. T. , Culler , D. , Shenker , S. , and Stoica , I . 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets . In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05) . 329--342. Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C. T., Culler, D., Shenker, S., and Stoica, I. 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05). 329--342.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/978-3-642-00224-3_6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/11776178_15"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1460412.1460415"},{"volume-title":"Proceedings of the 7th IEEE International Conference on Networked Sensing Systems (INSS'10)","author":"Iwanicki K.","unstructured":"Iwanicki , K. and Azim , T . 2010. Experimentally studying the sensornet point-to-point routing techniques spectrum . In Proceedings of the 7th IEEE International Conference on Networked Sensing Systems (INSS'10) . 6--13. Iwanicki, K. and Azim, T. 2010. Experimentally studying the sensornet point-to-point routing techniques spectrum. In Proceedings of the 7th IEEE International Conference on Networked Sensing Systems (INSS'10). 6--13.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/978-3-642-00224-3_7"},{"volume-title":"Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09)","author":"Iwanicki K.","unstructured":"Iwanicki , K. and van Steen, M. 2009b. On hierarchical routing in wireless sensor networks . In Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09) . 133--144. Iwanicki, K. and van Steen, M. 2009b. On hierarchical routing in wireless sensor networks. In Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09). 133--144.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"crossref","unstructured":"Johnson D. B. and Maltz D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing T. Imielinski and H. F. Korth Eds Vol. 353. Springer US New York NY 153--181.  Johnson D. B. and Maltz D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing T. Imielinski and H. F. Korth Eds Vol. 353. Springer US New York NY 153--181.","key":"e_1_2_1_18_1","DOI":"10.1007\/978-0-585-29603-6_5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/345910.345953"},{"volume-title":"Proceedings of the Second USENIX Symposium on Networked Systems Design and Implementation (NSDI'05)","author":"Kim Y.-J.","unstructured":"Kim , Y.-J. , Govindan , R. , Karp , B. , and Shenker , S . 2005. Geographic routing made practical . In Proceedings of the Second USENIX Symposium on Networked Systems Design and Implementation (NSDI'05) . 217--230. Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. 2005. Geographic routing made practical. In Proceedings of the Second USENIX Symposium on Networked Systems Design and Implementation (NSDI'05). 217--230.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","first-page":"155","article-title":"Hierarchical routing for large networks","volume":"1","author":"Kleinrock L.","year":"1977","unstructured":"Kleinrock , L. and Kamoun , F. 1977 . Hierarchical routing for large networks . Comput. Netw. 1 , 3, 155 -- 174 . Kleinrock, L. and Kamoun, F. 1977. Hierarchical routing for large networks. Comput. Netw. 1, 3, 155--174.","journal-title":"Comput. Netw."},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/1273445.1273450"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/872035.872044"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.5555\/850937.852501"},{"volume-title":"Proceedings of the 3rd USENIX Symposium on Networked Systems Design and Implementation (NSDI'06)","author":"Leong B.","unstructured":"Leong , B. , Liskov , B. , and Morris , R . 2006. Geographic routing without planarization . In Proceedings of the 3rd USENIX Symposium on Networked Systems Design and Implementation (NSDI'06) . 339--352. Leong, B., Liskov, B., and Morris, R. 2006. Geographic routing without planarization. In Proceedings of the 3rd USENIX Symposium on Networked Systems Design and Implementation (NSDI'06). 339--352.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP'07)","author":"Leong B.","unstructured":"Leong , B. , Liskov , B. , and Morris , R . 2007. Greedy virtual coordinates for geographic routing . In Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP'07) . 71--80. Leong, B., Liskov, B., and Morris, R. 2007. Greedy virtual coordinates for geographic routing. In Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP'07). 71--80.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07)","author":"Mao Y.","unstructured":"Mao , Y. , Wang , F. , Qiu , L. , Lam , S. S. , and Smith , J. M . 2007. S4: small state and small stretch routing protocol for large wireless sensor networks . In Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07) . 101--114. Mao, Y., Wang, F., Qiu, L., Lam, S. S., and Smith, J. M. 2007. S4: small state and small stretch routing protocol for large wireless sensor networks. In Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07). 101--114.","key":"e_1_2_1_27_1"},{"unstructured":"MoteLab. 2005. Harvard sensor network testbed. http:\/\/motelab.eecs.harvard.edu\/.  MoteLab. 2005. Harvard sensor network testbed. http:\/\/motelab.eecs.harvard.edu\/.","key":"e_1_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/958491.958501"},{"volume-title":"Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99)","author":"Perkins C. E.","unstructured":"Perkins , C. E. and Royer , E. M . 1999. Ad-hoc on-demand distance vector routing . In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99) . 90--100. Perkins, C. E. and Royer, E. M. 1999. Ad-hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99). 90--100.","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/1031495.1031508"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/938985.938996"},{"volume-title":"Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09)","author":"Sarkar R.","unstructured":"Sarkar , R. , Yin , X. , Gao , J. , Luo , F. , and Gu , X. D . 2009. Greedy routing with guaranteed delivery using Ricci flows . In Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09) . 121--132. Sarkar, R., Yin, X., Gao, J., Luo, F., and Gu, X. D. 2009. Greedy routing with guaranteed delivery using Ricci flows. In Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN'09). 121--132.","key":"e_1_2_1_33_1"},{"volume-title":"Proceedings of the 5th ACM Workshop on Hot Topics in Networks (HotNetsV). 31--36","author":"Srinivasan K.","unstructured":"Srinivasan , K. , Dutta , P. , Tavakoli , A. , and Levis , P . 2006. Some implications of low-power wireless to IP routing . In Proceedings of the 5th ACM Workshop on Hot Topics in Networks (HotNetsV). 31--36 . Srinivasan, K., Dutta, P., Tavakoli, A., and Levis, P. 2006. Some implications of low-power wireless to IP routing. In Proceedings of the 5th ACM Workshop on Hot Topics in Networks (HotNetsV). 31--36.","key":"e_1_2_1_34_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/1460412.1460416"},{"unstructured":"Stathopoulos T. Girod L. Heidemann J. and Estrin D. 2007. Centralized routing for resource-constrained wireless sensor networks. Tech. rep. University of California Los Angeles CA.  Stathopoulos T. Girod L. Heidemann J. and Estrin D. 2007. Centralized routing for resource-constrained wireless sensor networks. Tech. rep. University of California Los Angeles CA.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the 1st Annual ACM Workshop on Mobile Ad Hoc Networking and Computing (MobiHoc'00)","author":"Subramanian L.","unstructured":"Subramanian , L. and Katz , R. H . 2000. An architecture for building self-configurable systems . In Proceedings of the 1st Annual ACM Workshop on Mobile Ad Hoc Networking and Computing (MobiHoc'00) . 63--73. Subramanian, L. and Katz, R. H. 2000. An architecture for building self-configurable systems. In Proceedings of the 1st Annual ACM Workshop on Mobile Ad Hoc Networking and Computing (MobiHoc'00). 63--73.","key":"e_1_2_1_37_1"},{"volume-title":"Proceedings of the 7th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'98)","author":"Thaler D.","unstructured":"Thaler , D. and Ravishankar , C. V . 1998. Distributed top-down hierarchy construction . In Proceedings of the 7th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'98) . 693--701. Thaler, D. and Ravishankar, C. V. 1998. Distributed top-down hierarchy construction. In Proceedings of the 7th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'98). 693--701.","key":"e_1_2_1_38_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/52325.52329"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/958491.958494"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2240092.2240099","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2240092.2240099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:52Z","timestamp":1750238452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2240092.2240099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2240092.2240099"],"URL":"https:\/\/doi.org\/10.1145\/2240092.2240099","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}