{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T22:10:57Z","timestamp":1759961457633,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T00:00:00Z","timestamp":1183248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2007,7]]},"abstract":"<jats:p>Distributed wireless systems (DWSs) are emerging as the enabler for next-generation wireless applications. There is a consensus that DWS-based applications, such as pervasive computing, sensor networks, wireless information networks, and speech and data communication networks, will form the backbone of the next technological revolution. Simultaneously, with great economic, industrial, consumer, and scientific potential, DWSs pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize the lifetime of the network using only local information, while preserving network connectivity. We start by introducing the care-free sleep (CS) Theorem that provides provably optimal conditions for a node to go into sleep mode while ensuring that global connectivity is not affected. The CS theorem is the basis for an efficient localized algorithm that decides which nodes will go to into sleep mode and for how long. We have also developed mechanisms for collecting neighborhood information and for the coordination of distributed energy minimization protocols. The effectiveness of the approach is demonstrated using a comprehensive study of the performance of the algorithm over a wide range of network parameters. Another important highlight is the first mathematical and Monte Carlo analysis that establishes the importance of considering nodes within a small number of hops in order to preserve energy.<\/jats:p>","DOI":"10.1145\/1275986.1275988","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Techniques for maintaining connectivity in wireless ad-hoc networks under energy constraints"],"prefix":"10.1145","volume":"6","author":[{"given":"Farinaz","family":"Koushanfar","sequence":"first","affiliation":[{"name":"Rice University, Houston, Texas"}]},{"given":"Abhijit","family":"Davare","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley, California"}]},{"given":"David T.","family":"Nguyen","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley, California"}]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley, California"}]},{"given":"Miodrag","family":"Potkonjak","sequence":"additional","affiliation":[{"name":"University of California Los Angeles, Los Angeles, California"}]}],"member":"320","published-online":{"date-parts":[[2007,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/288235.288256"},{"key":"e_1_2_1_2_1","volume-title":"Ascent: Adaptive self-configuring sensor networks topologies","author":"Cerpa A.","year":"2002","unstructured":"Cerpa , A. and Estrin , D . 2002 . Ascent: Adaptive self-configuring sensor networks topologies . In IEEE Infocom . vol. 3 . 1278--1287. Cerpa, A. and Estrin, D. 2002. Ascent: Adaptive self-configuring sensor networks topologies. In IEEE Infocom. vol. 3. 1278--1287."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Cerpa A. Wong J. Kuang L. Potkonjak M. and Estrin D. 2005a. Statistical model of lossy links in wireless sensor networks. In Information Processing in Sensor Networks (IPSN). 81--88. Cerpa A. Wong J. Kuang L. Potkonjak M. and Estrin D. 2005a. Statistical model of lossy links in wireless sensor networks. In Information Processing in Sensor Networks (IPSN). 81--88.","DOI":"10.1109\/IPSN.2005.1440900"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062741"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.126534"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.363126"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016542229220"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.302"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363143"},{"key":"e_1_2_1_10_1","unstructured":"Garey M. and Johnson D. 1979. Computer And Intractability: A Guide To The Theory Of NP-Completeness. W. H. Freeman San Francisco CA. Garey M. and Johnson D. 1979. Computer And Intractability: A Guide To The Theory Of NP-Completeness. W. H. Freeman San Francisco CA."},{"volume-title":"ACM\/IEEE Design Automation Conference (DAC). 253--259","author":"Ghosh A.","key":"e_1_2_1_11_1","unstructured":"Ghosh , A. , Devadas , S. , Keutzer , K. , and White , J . 1992. Estimation of average switching activity in combinational and sequential circuits . In ACM\/IEEE Design Automation Conference (DAC). 253--259 . Ghosh, A., Devadas, S., Keutzer, K., and White, J. 1992. Estimation of average switching activity in combinational and sequential circuits. In ACM\/IEEE Design Automation Conference (DAC). 253--259."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1012102"},{"volume-title":"IEEE International Conference on Mobile Ad-hoc and Sensor Systems. 570--572","author":"Han B.","key":"e_1_2_1_13_1","unstructured":"Han , B. , Fu , H. , Lin , L. , and Jia , W . 2004. Efficient construction of connected dominating set in wireless ad hoc networks . In IEEE International Conference on Mobile Ad-hoc and Sensor Systems. 570--572 . Han, B., Fu, H., Lin, L., and Jia, W. 2004. Efficient construction of connected dominating set in wireless ad hoc networks. In IEEE International Conference on Mobile Ad-hoc and Sensor Systems. 570--572."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.811318"},{"key":"e_1_2_1_15_1","unstructured":"Kasten O. 2001. Measurements of energy consumption for digitan 2 mbps wireless lan module (ieee 802.11\/2mbps). http:\/\/www.inf.ethz.ch\/~kasten\/research. Kasten O. 2001. Measurements of energy consumption for digitan 2 mbps wireless lan module (ieee 802.11\/2mbps). http:\/\/www.inf.ethz.ch\/~kasten\/research."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/871506.871623"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.084.024"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266268"},{"volume-title":"Fifty Challenging Problems in Probability With Solutions","author":"Mosteller F.","key":"e_1_2_1_19_1","unstructured":"Mosteller , F. 1965. Fifty Challenging Problems in Probability With Solutions . Addison-Wesley , Reading, MA . Mosteller, F. 1965. Fifty Challenging Problems in Probability With Solutions. Addison-Wesley, Reading, MA."},{"volume-title":"Simulation and the Monte Carlo Method","author":"Rubinstein R.","key":"e_1_2_1_20_1","unstructured":"Rubinstein , R. 1981. Simulation and the Monte Carlo Method . Wiley , New York . Rubinstein, R. 1981. Simulation and the Monte Carlo Method. Wiley, New York."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/513800.513817"},{"key":"e_1_2_1_22_1","unstructured":"Silberschatz A. Galvin P. and Gagne G. 2003. Operating system concepts: Windows xp update. Silberschatz A. Galvin P. and Gagne G. 2003. Operating system concepts: Windows xp update."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379016"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.980024"},{"key":"e_1_2_1_25_1","unstructured":"WolframResearch. 2001. Mathematica 4.1 symbolic programming. http:\/\/www.wolfram.com\/products\/mathematica\/index.html. WolframResearch. 2001. Mathematica 4.1 symbolic programming. http:\/\/www.wolfram.com\/products\/mathematica\/index.html."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/313239.313261"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/381677.381685"},{"volume-title":"Symposium on Foundations of Computer Science (FOCS). 374--382","author":"Yao F.","key":"e_1_2_1_28_1","unstructured":"Yao , F. , Demers , A. , and Shenker , S . 1995. A scheduling model for reduced cpu energy . In Symposium on Foundations of Computer Science (FOCS). 374--382 . Yao, F., Demers, A., and Shenker, S. 1995. A scheduling model for reduced cpu energy. In Symposium on Foundations of Computer Science (FOCS). 374--382."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2003.09.008"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275986.1275988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1275986.1275988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:58:00Z","timestamp":1750258680000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275986.1275988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["10.1145\/1275986.1275988"],"URL":"https:\/\/doi.org\/10.1145\/1275986.1275988","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2007,7]]},"assertion":[{"value":"2007-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}