{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:26Z","timestamp":1775638526867,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-00-87022EIA-02-05116"],"award-info":[{"award-number":["CCR-00-87022EIA-02-05116"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["99-10-8"],"award-info":[{"award-number":["99-10-8"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>Sensor nodes are very weak computers that get distributed at random on a surface. Once deployed, they must wake up and form a radio network. Sensor network bootstrapping research thus has three parts: One must model the restrictions on sensor nodes; one must prove that the connectivity graph of the sensors has a subgraph that would make a good network; and one must give a distributed protocol for finding such a network subgraph that can be implemented on sensor nodes.<\/jats:p>\n          <jats:p>Although many particular restrictions on sensor nodes are implicit or explicit in many papers, there remain many inconsistencies and ambiguities from paper to paper. The lack of a clear model means that solutions to the network bootstrapping problem in both the theory and systems literature all violate constraints on sensor nodes. For example, random geometric graph results on sensor networks predict the existence of subgraphs on the connectivity graph with good route-stretch, but these results do not address the degree of such a graph, and sensor networks must have constant degree. Furthermore, proposed protocols for actually finding such graphs require that nodes have too much memory, whereas others assume the existence of a contention-resolution mechanism.<\/jats:p>\n          <jats:p>\n            We present a formal Weak Sensor model that summarizes the literature on sensor node restrictions, taking the most restrictive choices when possible. We show that sensor connectivity graphs have low-degree subgraphs with good\n            <jats:italic>hop-stretch<\/jats:italic>\n            , as required by the Weak Sensor model. Finally, we give a Weak Sensor model-compatible protocol for finding such graphs. Ours is the first network initialization algorithm that is implementable on sensor nodes.\n          <\/jats:p>","DOI":"10.1145\/1597036.1597040","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Bootstrapping a hop-optimal network in the weak sensor model"],"prefix":"10.1145","volume":"5","author":[{"given":"Martin","family":"Farach-Colton","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohan J.","family":"Fernandes","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ and Universidad Rey Juan Carlos, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aiello W. Chung-Graham F. and Lu L. 2002. Random Evolution of Massive Graphs. Kluwer Academic Publishers Dordrecht 97--122.   Aiello W. Chung-Graham F. and Lu L. 2002. Random Evolution of Massive Graphs. Kluwer Academic Publishers Dordrecht 97--122.","DOI":"10.1007\/978-1-4615-0005-6_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(01)00302-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/839294.843425"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/1428076"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/1428077"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 781--790","author":"Barri\u00e8re L."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778433"},{"key":"e_1_2_1_9_1","volume-title":"Bluetooth: Connect Without Cables","author":"Bray J.","year":"2001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000193"},{"key":"e_1_2_1_11_1","first-page":"290","article-title":"On random graphs--i","volume":"6","author":"Erd\u00f6s P.","year":"1959","journal-title":"Publicationes Matematicae"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_73"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"4619","author":"Farach-Colton M."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01181430"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 18th International Parallel and Distributed Processing Symposium.","author":"Ferraguto F."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007441"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Gupta P. and Kumar P. R. 1998. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis Control Optimization and applications: A Volume in Honor of W. H. Fleming. Birkhauser Boston 547--566.  Gupta P. and Kumar P. R. 1998. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis Control Optimization and applications: A Volume in Honor of W. H. Fleming. Birkhauser Boston 547--566.","DOI":"10.1007\/978-1-4612-1784-8_33"},{"key":"e_1_2_1_19_1","unstructured":"Karl H. and Willig A. 2003. A short survey of wireless networks. Tech. rep. TKN-03-018 Technical University Berlin.  Karl H. and Willig A. 2003. A short survey of wireless networks. Tech. rep. TKN-03-018 Technical University Berlin."},{"key":"e_1_2_1_20_1","volume-title":"Annual Conference on Computing and Combinatorics.","author":"Kleinberg J."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Kumar V. S. A."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE Symposium on Ad Hoc Wireless Networks.","author":"Law C."},{"key":"e_1_2_1_23_1","first-page":"175","article-title":"Topology Control in Wireless Ad Hoc Networks. Wiley-IEEE Press","volume":"6","author":"Li X.-Y.","year":"2004","journal-title":"Chapter"},{"key":"e_1_2_1_24_1","volume-title":"Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communication","author":"Miller B.","year":"2000"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073842"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Muthukrishnan S."},{"key":"e_1_2_1_28_1","volume-title":"International Conference on Parallel Processing.","author":"Nakano K."},{"key":"e_1_2_1_29_1","unstructured":"Parthasarathy S. and Gandhi R. 2004. Fast distributed well connected dominating sets for ad hoc networks. Tech. rep. CS-TR-4559 Computer Science Department University of Maryland.  Parthasarathy S. and Gandhi R. 2004. Fast distributed well connected dominating sets for ad hoc networks. Tech. rep. CS-TR-4559 Computer Science Department University of Maryland."},{"key":"e_1_2_1_30_1","volume-title":"Random Geometric Graphs","author":"Penrose M."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199909)15:2%3C145::AID-RSA2%3E3.0.CO;2-G"},{"key":"e_1_2_1_32_1","unstructured":"Ponduru V. A. S. and Bharathidasan A. 2003. Sensor networks: An overview. Tech. rep. University of California Davis.  Ponduru V. A. S. and Bharathidasan A. 2003. Sensor networks: An overview. Tech. rep. University of California Davis."},{"key":"e_1_2_1_33_1","unstructured":"Rentala P. Musunuri R. Saxena U. and Gandham S. 2001. Survey on sensor networks. http:\/\/citeseer.ist.psu.edu\/479874.html.  Rentala P. Musunuri R. Saxena U. and Gandham S. 2001. Survey on sensor networks. http:\/\/citeseer.ist.psu.edu\/479874.html."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024916.1024920"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2001.916654"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/98.878532"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/989459.989473"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/565702.565708"},{"key":"e_1_2_1_39_1","volume-title":"Hawaii International Conference on System Sciences (HICSS).","author":"Wang Z."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2006.1637928"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the IEEE International Conference on Communications.","author":"Zaruba G. V."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597040","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1597036.1597040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:10Z","timestamp":1750249090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1597036.1597040"],"URL":"https:\/\/doi.org\/10.1145\/1597036.1597040","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}