{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:41:50Z","timestamp":1750308110714,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>In this paper we show how to use stochastic estimation methods to investigate topological properties of sensor networks as well as the behavior of dynamical processes on these networks. The framework is particularly important to study problems for which no theoretical results are known, or cannot be directly applied in practice, for instance, when only asymptotic results are available. We also interpret Russo's formula in the context of sensor networks and thus obtain practical information on their reliability. As a case study, we analyze a localization protocol for wireless sensor networks and validate our approach by numerical experiments. Finally, we mention three applications of our approach: estimating the number of pivotal sensors in a real network, minimizing the number of such sensors for robustness purposes during the network design and estimating the distance between successive localized positions for mobile sensor networks.<\/jats:p>","DOI":"10.1145\/1187436.1216580","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":0,"title":["A framework for probabilistic numerical evaluation of sensor networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Pierre","family":"Leone","sequence":"first","affiliation":[{"name":"University of Geneva, Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose","family":"Rolim","sequence":"additional","affiliation":[{"name":"University of Geneva, Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Albuquerque","sequence":"additional","affiliation":[{"name":"Ecole d'Ing\u00e9nieurs de Gen\u00e8ve, Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Mazza","sequence":"additional","affiliation":[{"name":"University of Geneva, Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(01)00302-4"},{"key":"e_1_2_1_2_1","volume-title":"Proc. of the 1st Int'l Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS","volume":"3121","author":"Aspnes J.","year":"2004"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1214\/aoms\/1177728794","article-title":"Approximation methods which converge with probability one","volume":"25","author":"Blum J.","year":"1954","journal-title":"Ann. Math. Statist."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1214\/aoap\/1050689601","article-title":"Covering algorithms, continuum percolation and the geometry of wireless networks","volume":"13","author":"Booth L.","year":"2003","journal-title":"Annals of Applied Probability"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/98.878533","article-title":"Gps-less low cost outdoor localization for very small devices","volume":"7","author":"Bulusu N.","year":"2000","journal-title":"IEEE Personal Communications Magazine"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1214\/aoms\/1177728072","article-title":"On a class of stochastic approximation processes","volume":"27","author":"Burkholder D.","year":"1956","journal-title":"Ann. Math. Statist"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1142\/S0129626403001550","article-title":"A comparative study of protocols for efficient data propagation in smart dust networks","volume":"13","author":"Chatzigiannakis I.","year":"2003","journal-title":"Parallel Processing Letters"},{"volume-title":"Proc. of the 5th European Wireless Conf. on Mobile and Wireless Systems Beyond 3G. 344--350","author":"Chatzigiannakis I.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1023\/B:MONE.0000048551.54039.f0","article-title":"Efficient and robust protocols for local detection and propagation in smart dust networks","volume":"10","author":"Chatzigiannakis I.","year":"2005","journal-title":"Mobile Network and Applications"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Chayes J. and Chayes L. 1987. The mean-field bound for the order of parameter of bernoulli percolation. In Percolation theory and ergodic theory of infinite particle systems (Minneapolis Minn. 1984--1985). IMA Vol. Math. Appl. vol. 8. Springer New York. 49--71. Chayes J. and Chayes L. 1987. The mean-field bound for the order of parameter of bernoulli percolation. In Percolation theory and ergodic theory of infinite particle systems (Minneapolis Minn. 1984--1985). IMA Vol. Math. Appl. vol. 8. Springer New York. 49--71.","DOI":"10.1007\/978-1-4613-8734-3_5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1214\/aoms\/1177728716","article-title":"On a stochastic approximation method","volume":"25","author":"Chung K.","year":"1954","journal-title":"Ann. Math. Statist."},{"volume-title":"Tech. Rep. LSI-02-72-R, Universitat Politecnica Catalunya.","year":"2002","author":"Diaz J.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","volume-title":"Proc. of the 2nd Int'l Workshop on Experimental and Efficient Algorithms (WEA","volume":"2647","author":"Diaz J.","year":"2003"},{"key":"e_1_2_1_14_1","unstructured":"Grimmett G. 1999. Percolation 2nd ed. A Series of Comprehensive Studies in Mathematics vol. 321. Springer Verlag New York. Grimmett G. 1999. Percolation 2nd ed. A Series of Comprehensive Studies in Mathematics vol. 321. Springer Verlag New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Grimmett G. and Stirzaker D. 2001. Probability and Random Processes 3rd ed. Oxford University Press Oxford. Grimmett G. and Stirzaker D. 2001. Probability and Random Processes 3rd ed. Oxford University Press Oxford.","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"volume-title":"Proc. of the 2002 Winter Simulation Conference. 370--376","author":"Hsieh M.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Leone P. Nikoletseas S. and Rolim J. 2005. An adaptative blind algorithm for energy balanced data propagation in wireless sensor networks. Submitted to DCOSS. 10.1007\/11502593_6 Leone P. Nikoletseas S. and Rolim J. 2005. An adaptative blind algorithm for energy balanced data propagation in wireless sensor networks. Submitted to DCOSS. 10.1007\/11502593_6","DOI":"10.1007\/11502593_6"},{"volume-title":"Translations of Mathematical Monographs.","author":"Nevel'son R. H.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Meester R. and Roy R. 1996. Continuum percolation. Cambridge University Press Cambridge. Meester R. and Roy R. 1996. Continuum percolation. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511895357"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Motawni R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge. Motawni R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511814075"},{"volume-title":"MOBICOM'03","author":"Rao A.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins H.","year":"1951","journal-title":"Ann. Math. Statistics"},{"key":"e_1_2_1_23_1","first-page":"229","article-title":"A note on percolation","volume":"56","author":"Russo L.","year":"1981","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandt Gebiete"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1214\/aoms\/1177706619","article-title":"Asymptotic distributions of stochastic approximation procedures","volume":"29","author":"Sacks J.","year":"1958","journal-title":"Ann. Math. Statist."},{"volume-title":"Tutorial on Wireless Sensor Networks, Mobicom","year":"2002","author":"Srivastava M.","key":"e_1_2_1_25_1"},{"volume-title":"Tutorial on Wireless Sensor Networks, Mobicom","year":"2002","author":"Srivastava M.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1214\/aoms\/1177699069","article-title":"An extension of the robbins-monro procedure","volume":"38","author":"Venter J.","year":"1967","journal-title":"Ann. Math. Statist."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216580","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1216580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216580"}},"subtitle":["A case study of a localization protocol"],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":27,"alternative-id":["10.1145\/1187436.1216580"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1216580","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}