{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:46Z","timestamp":1750308226017,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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":["SIGMOBILE Mob. Comput. Commun. Rev."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We consider a game that models the creation of a wireless ad hoc network, where nodes are owned by selfish agents. We study a novel cost sharing model in which agents may pay for the transmission power of the other nodes. Each agent has to satisfy some connectivity requirement in the final network and the goal is to minimize its payment with no regard to the overall system performance. We analyze two fundamental connectivity games, namely broadcast and convergecast. We study pure Nash equilibria and quantify the degradation in the network performance called the price of anarchy resulting from selfish behavior. We derive tight bounds on the price of anarchy for these games. We also study centralized network design. One of the most important problems in wireless ad hoc networks is the minimum-energy broadcast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent end-to-end latency bounds on the broadcasting time. However, the existing algorithms that minimize the broadcasting energy tend to produce solutions with high latency. In this paper we consider the problem of bounded-hop broadcast. We present approximation and heuristic algorithms for this problem.<\/jats:p>","DOI":"10.1145\/1055959.1055963","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"15-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Energy efficient communication in ad hoc networks from user's and designer's perspective"],"prefix":"10.1145","volume":"9","author":[{"given":"Alex","family":"Kesselman","sequence":"first","affiliation":[{"name":"Max Planck Institut f\u00fcr Informatik, Saarbrucken, Germany"}]},{"given":"Dariusz","family":"Kowalski","sequence":"additional","affiliation":[{"name":"Instytut Informatyki, Uniwersytet Warszawski, Warszawa, Poland"}]},{"given":"Michael","family":"Segal","sequence":"additional","affiliation":[{"name":"Ben Gurion University of the Negev, Beer-Sheva, Israel"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"C. Ambuhl A. E. F. Clementi M. Di Ianni N. Lev-Tov A. Monti D. Peleg G. Rossi and Riccardo Silvestri \"Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks \" Proc. of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04) pp. 418--427 2004.  C. Ambuhl A. E. F. Clementi M. Di Ianni N. Lev-Tov A. Monti D. Peleg G. Rossi and Riccardo Silvestri \"Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks \" Proc. of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04) pp. 418--427 2004.","DOI":"10.1007\/978-3-540-24749-4_37"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780617"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684562"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025146013151"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/570645.570667"},{"key":"e_1_2_1_6_1","first-page":"114","volume-title":"Networks lifetime and power assignment in ad hoc wireless networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03)","author":"Calinescu G.","year":"2003","unstructured":"G. Calinescu , S. Kapoor , A. Olshevsky and A. Zelikovsky , \" Networks lifetime and power assignment in ad hoc wireless networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03) , pp. 114 -- 126 , 2003 . G. Calinescu, S. Kapoor, A. Olshevsky and A. Zelikovsky, \"Networks lifetime and power assignment in ad hoc wireless networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03), pp. 114--126, 2003."},{"volume-title":"IEEE Wireless Communications and Networking Conference (WCNC'04)","author":"Calinescu G.","key":"e_1_2_1_7_1","unstructured":"G. Calinescu , S. Kapoor and M. Sarwat , Bounded Hops Power Assignment in Ad-hoc Wireless Networks,\" Proc . IEEE Wireless Communications and Networking Conference (WCNC'04) . G. Calinescu, S. Kapoor and M. Sarwat, Bounded Hops Power Assignment in Ad-hoc Wireless Networks,\" Proc. IEEE Wireless Communications and Networking Conference (WCNC'04)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24587-2_60"},{"key":"e_1_2_1_9_1","volume-title":"Localized minimum-energy broadcasting in ad-hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Cartigny J.","year":"2003","unstructured":"J. Cartigny , D. Simplot and I. Stojmenovic , \" Localized minimum-energy broadcasting in ad-hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03) , 2003 . J. Cartigny, D. Simplot and I. Stojmenovic, \"Localized minimum-energy broadcasting in ad-hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), 2003."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.20105"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00538-8"},{"key":"e_1_2_1_12_1","volume-title":"Modelling Incentives for Collaboration in Mobile Ad Hoc Networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03)","author":"Crowcroft J.","year":"2003","unstructured":"J. Crowcroft , R. Gibbens , F. Kelly and S. Ostring , \" Modelling Incentives for Collaboration in Mobile Ad Hoc Networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03) , 2003 . J. Crowcroft, R. Gibbens, F. Kelly and S. Ostring, \"Modelling Incentives for Collaboration in Mobile Ad Hoc Networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03), 2003."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/941079.941081"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796501"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1022630.1022644"},{"key":"e_1_2_1_17_1","first-page":"230","volume-title":"Approximating energy efficient paths in wireless multi hop networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03)","author":"Funke S.","year":"2003","unstructured":"S. Funke , D. Matijevic , and P. Sanders , \" Approximating energy efficient paths in wireless multi hop networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03) , pp. 230 -- 241 , 2003 . S. Funke, D. Matijevic, and P. Sanders, \"Approximating energy efficient paths in wireless multi hop networks,\" Proc. of the 11th European Symposium on Algorithms (ESA'03), pp. 230--241, 2003."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"e_1_2_1_19_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness,\" W","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson , \" Computers and Intractability: A Guide to the Theory of NP Completeness,\" W . H. Freeman , San Francisco , 1979 . M. R. Garey and D. S. Johnson, \"Computers and Intractability: A Guide to the Theory of NP Completeness,\" W. H. Freeman, San Francisco, 1979."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00223-0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00111-0"},{"key":"e_1_2_1_22_1","first-page":"404","volume-title":"Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99)","author":"Koutsoupias E.","year":"1999","unstructured":"E. Koutsoupias , C. H. Papadimitriou , \"Worst-case equilibria,\" Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99) , pp. 404 -- 413 , 1999 . E. Koutsoupias, C. H. Papadimitriou, \"Worst-case equilibria,\" Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99), pp. 404--413, 1999."},{"key":"e_1_2_1_23_1","first-page":"187","volume-title":"International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03)","author":"Krumke S.","unstructured":"S. Krumke , R. Liu , E. Lloyd , M. Marathe , R. Ramanathan and S. Ravi , \" Topology control problems under symmetric and asymmetric power thresholds,\" Proc . International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03) , pp. 187 -- 198 . S. Krumke, R. Liu, E. Lloyd, M. Marathe, R. Ramanathan and S. Ravi, \"Topology control problems under symmetric and asymmetric power thresholds,\" Proc. International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03), pp. 187--198."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/513800.513815"},{"key":"e_1_2_1_25_1","volume-title":"A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03)","author":"Michiardi P.","year":"2003","unstructured":"P. Michiardi and R. Molva , \" A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03) , 2003 . P. Michiardi and R. Molva, \"A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks,\" Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03), 2003."},{"key":"e_1_2_1_26_1","first-page":"536","volume-title":"Improved approximations for shallow-light spanning trees,\" Proc. of the IEEE Conf. on Foundations of Computer Science (FOCS'97)","author":"Naor J.","year":"1997","unstructured":"J. Naor and B. Schieber , \" Improved approximations for shallow-light spanning trees,\" Proc. of the IEEE Conf. on Foundations of Computer Science (FOCS'97) , pp. 536 -- 541 , 1997 . J. Naor and B. Schieber, \"Improved approximations for shallow-light spanning trees,\" Proc. of the IEEE Conf. on Foundations of Computer Science (FOCS'97), pp. 536--541, 1997."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00216-L"},{"key":"e_1_2_1_29_1","volume-title":"Principles and Practices,\" Prentice Hall","author":"Rappaport T. S.","year":"1996","unstructured":"T. S. Rappaport , \"Wireless Communications : Principles and Practices,\" Prentice Hall , 1996 . T. S. Rappaport, \"Wireless Communications: Principles and Practices,\" Prentice Hall, 1996."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/288235.288286"},{"key":"e_1_2_1_32_1","first-page":"808","volume-title":"Cooperation in wireless ad hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Srinivasan V.","year":"2003","unstructured":"V. Srinivasan , P. Nuggehalli , C. F. Chiasserini and R. R. Rao , \" Cooperation in wireless ad hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03) , pp. 808 -- 817 , 2003 . V. Srinivasan, P. Nuggehalli, C. F. Chiasserini and R. R. Rao, \"Cooperation in wireless ad hoc networks,\" Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), pp. 808--817, 2003."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020381720601"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020716919751"}],"container-title":["ACM SIGMOBILE Mobile Computing and Communications Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055959.1055963","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1055959.1055963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:28Z","timestamp":1750264288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055959.1055963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1055959.1055963"],"URL":"https:\/\/doi.org\/10.1145\/1055959.1055963","relation":{},"ISSN":["1559-1662","1931-1222"],"issn-type":[{"type":"print","value":"1559-1662"},{"type":"electronic","value":"1931-1222"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}