{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:22:42Z","timestamp":1750306962297,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T00:00:00Z","timestamp":1367366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0643587, CNS-1016829 and CNS-1116881"],"award-info":[{"award-number":["CNS-0643587, CNS-1016829 and CNS-1116881"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Methods for Discrete Structures"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","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":[[2013,5]]},"abstract":"<jats:p>In traditional routing, the routing tables store shortest paths to all other destinations and have size linear in the size of the network, which is not scalable for resource-constrained networks such as wireless sensor networks. In this article we show that by storing selectively a much smaller set of routing paths in the routing tables one can get low-stretch, compact routing schemes.<\/jats:p>\n          <jats:p>\n            Our routing scheme includes an approximate distance oracle with which one can obtain approximate shortest path length estimates to destinations. This distance oracle can be obtained, for example, by a landmark-based scheme, or in case of sensor networks, from the geographic distance between node locations. With an approximate distance oracle one can attempt\n            <jats:italic>greedy routing<\/jats:italic>\n            by forwarding to the neighbor whose estimate is closer to the destination. But there is no guarantee of delivery nor of the routing path length. We augment the distance oracle by storing, for each node\n            <jats:italic>u<\/jats:italic>\n            , routing paths to\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) strategically selected nodes that serve as intermediate destinations. These nodes are selected with probability proportional to 1\/\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>\u03c1<\/jats:sup>\n            , where\n            <jats:italic>r<\/jats:italic>\n            is the distance to\n            <jats:italic>u<\/jats:italic>\n            and \u03c1 is a suitable constant for the network. Then we derive a set of sufficient conditions to select the next step at each stage of routing, such that these conditions can be verified locally and guarantee 1+\u03b5 stretch routing on any metric. These conditions serve as the \u201cgreedy routing\u201d or local decision rule.\n          <\/jats:p>\n          <jats:p>\n            On graphs of bounded growth, our scheme guarantees 1+\u03b5 stretch routing with high probability, with an average routing table size of\n            <jats:italic>O<\/jats:italic>\n            (\u221an log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ). This scheme is favorable for its simplicity, generality, and blindness to any global state. It demonstrates that global routing properties could emerge from purely distributed and uncoordinated routing table design.\n          <\/jats:p>","DOI":"10.1145\/2480730.2480735","type":"journal-article","created":{"date-parts":[[2013,6,5]],"date-time":"2013-06-05T12:09:34Z","timestamp":1370434174000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Distributed and compact routing using spatial distributions in wireless sensor networks"],"prefix":"10.1145","volume":"9","author":[{"given":"Rik","family":"Sarkar","sequence":"first","affiliation":[{"name":"Free University of Berlin"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianjin","family":"Zhu","sequence":"additional","affiliation":[{"name":"Microsoft Inc, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Gao","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.72"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073978"},{"volume-title":"Land: Stretch (1 &plus","year":"2004","author":"Abraham I.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052199.1052206"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012319418150"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-006-9857-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159954"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05)","author":"Chan H. T.-H.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99)","year":"1999","author":"Cowen L. J.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127791"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00002-6"},{"volume":"1","volume-title":"Proceedings of the 24th Conference of the IEEE Communication Society (INFOCOM'05)","author":"Fang Q.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI'05)","author":"Fonesca R.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM'07)","author":"Funke S.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1182807.1182819"},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)","author":"Gupta A.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345953"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380796"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080810.1080818"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146412"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872044"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958506"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345931"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"volume-title":"Proceedings of the 4th USENIX Symposium on Networked System Design and Implementation (NSDI'07)","author":"Mao Y.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","first-page":"60","article-title":"The small world problem","volume":"2","author":"Milgram S.","year":"1967","journal-title":"Psychol. Today"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958501"},{"volume-title":"Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM'07)","author":"Nguyen A.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258523"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/938985.938996"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236413"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062736"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-008-9136-9"},{"volume-title":"Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM'07)","author":"Zhang F.","key":"e_1_2_1_42_1"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480730.2480735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2480730.2480735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:14Z","timestamp":1750235954000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480730.2480735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["10.1145\/2480730.2480735"],"URL":"https:\/\/doi.org\/10.1145\/2480730.2480735","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2013,5]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}