{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:18:24Z","timestamp":1791411504157,"version":"4.3.3"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,7,17]],"date-time":"2014-07-17T00:00:00Z","timestamp":1405555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61133006, 61321491, and 61373130"],"award-info":[{"award-number":["61133006, 61321491, and 61373130"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2014CB340300 and 2012CB316200"],"award-info":[{"award-number":["2014CB340300 and 2012CB316200"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"name":"program B for Outstanding Ph.D. Candidate of Nanjing University","award":["201301B014"],"award-info":[{"award-number":["201301B014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2014,11,7]]},"abstract":"<jats:p>In wireless sensor networks, the spanning tree is usually used as a routing structure to collect data. In some situations, nodes do in-network aggregation to reduce transmissions, save energy, and maximize network lifetime. Because of the restricted energy of sensor nodes, how to build an aggregation tree of maximum lifetime is an important issue. It has been proved to be NP-complete in previous works. As shortest path spanning trees intuitively have short delay, it is imperative to find an energy-efficient shortest path tree for time-critical applications. In this article, we first study the problem of building maximum lifetime shortest path aggregation trees in wireless sensor networks. We show that when restricted to shortest path trees, building maximum lifetime aggregation trees can be solved in polynomial time. We present a centralized algorithm and design a distributed protocol for building such trees. Simulation results show that our approaches greatly improve the lifetime of the network and are very effective compared to other solutions. We extend our discussion to networks without aggregation and present interesting results.<\/jats:p>","DOI":"10.1145\/2629662","type":"journal-article","created":{"date-parts":[[2014,7,22]],"date-time":"2014-07-22T15:08:20Z","timestamp":1406041700000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Building Maximum Lifetime Shortest Path Data Aggregation Trees in Wireless Sensor Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Mengfan","family":"Shan","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dijun","family":"Luo","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaojun","family":"Zhu","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaobing","family":"Wu","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,7,17]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"2465","article-title":"Lifetime analysis of reliable wireless sensor networks","volume":"88","author":"Baydere Sebnem","year":"2006","unstructured":"Sebnem Baydere , Yasar Safkan , and Ozlem Durmaz . 2006 . Lifetime analysis of reliable wireless sensor networks . IEICE Transactions on Communications 88 , 6, 2465 -- 2472 . Sebnem Baydere, Yasar Safkan, and Ozlem Durmaz. 2006. Lifetime analysis of reliable wireless sensor networks. IEICE Transactions on Communications 88, 6, 2465--2472.","journal-title":"IEICE Transactions on Communications"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-007-0035-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11599463_14"},{"key":"e_1_2_1_4_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic Efim A.","year":"1970","unstructured":"Efim A. Dinic . 1970 . Algorithm for solution of a problem of maximum flow in networks with power estimation . Soviet Mathematics--Doklady 11 , 1277 -- 1280 . Efim A. Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics--Doklady 11, 1277--1280.","journal-title":"Soviet Mathematics--Doklady"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880939"},{"key":"e_1_2_1_6_1","volume-title":"Johnson","author":"Gary Michael R.","year":"1979","unstructured":"Michael R. Gary and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. Macmillan Higher Education . Michael R. Gary and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Macmillan Higher Education."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2005.843543"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644040"},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","author":"Harvey Nicholas J. A.","unstructured":"Nicholas J. A. Harvey , Richard E. Ladner , L\u00e1szl\u00f3 Lov\u00e1sz , and Tami Tamir . 2003. Semi-matchings for bipartite graphs and load balancing . In Algorithms and Data Structures . Lecture Notes in Computer Science , Vol. 2748 . Springer , 294--306. Nicholas J. A. Harvey, Richard E. Ladner, L\u00e1szl\u00f3 Lov\u00e1sz, and Tami Tamir. 2003. Semi-matchings for bipartite graphs and load balancing. In Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 2748. Springer, 294--306."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.50"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM\u201913)","author":"Arefin Imon Sk Kajal","unstructured":"Sk Kajal Arefin Imon , Adnan Khan , Mario Di Francesco , and Sajal K. Das . 2013. RaSMaLai: A randomized switching algorithm for maximizing lifetime in tree-based wireless sensor networks . In Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM\u201913) . IEEE, Los Alamitos, CA, 2913--2921. Sk Kajal Arefin Imon, Adnan Khan, Mario Di Francesco, and Sajal K. Das. 2013. RaSMaLai: A randomized switching algorithm for maximizing lifetime in tree-based wireless sensor networks. In Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM\u201913). IEEE, Los Alamitos, CA, 2913--2921."},{"key":"e_1_2_1_12_1","unstructured":"Texas Instruments. 2007. CC2420 datasheet. Available at http:\/\/www.ti.com\/product\/cc2420.  Texas Instruments. 2007. CC2420 datasheet. Available at http:\/\/www.ti.com\/product\/cc2420."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195659"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236365"},{"key":"e_1_2_1_15_1","volume-title":"Cormen","author":"Leiserson Charles E.","year":"2001","unstructured":"Charles E. Leiserson , Ronald L. Rivest , Clifford Stein , and Thomas H . Cormen . 2001 . Introduction to Algorithms. MIT Press . Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, and Thomas H. Cormen. 2001. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644041"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2037497"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2013.6616114"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934947"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570751"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.116"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959072"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1530748.1530773"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70770"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 27th International Conference on Computer Communications (INFOCOM\u201908)","author":"Wu Yan","unstructured":"Yan Wu , Sonia Fahmy , and Ness B. Shroff . 2008b. On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm . In Proceedings of the 27th International Conference on Computer Communications (INFOCOM\u201908) . IEEE, Los Alamitos, CA, 356--360. Yan Wu, Sonia Fahmy, and Ness B. Shroff. 2008b. On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm. In Proceedings of the 27th International Conference on Computer Communications (INFOCOM\u201908). IEEE, Los Alamitos, CA, 356--360."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.45"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.175"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031498"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-005-4443-7"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 24th IEEE International Conference on Performance, Computing, and Communications (IPCCC\u201905)","author":"Ye Mao","year":"2005","unstructured":"Mao Ye , Chengfa Li , Guihai Chen , and Jie Wu . 2005 . EECS: An energy efficient clustering scheme in wireless sensor networks . In Proceedings of the 24th IEEE International Conference on Performance, Computing, and Communications (IPCCC\u201905) . IEEE, Los Alamitos, CA, 535--540. Mao Ye, Chengfa Li, Guihai Chen, and Jie Wu. 2005. EECS: An energy efficient clustering scheme in wireless sensor networks. In Proceedings of the 24th IEEE International Conference on Performance, Computing, and Communications (IPCCC\u201905). IEEE, Los Alamitos, CA, 535--540."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:30Z","timestamp":1750227210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,17]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,11,7]]}},"alternative-id":["10.1145\/2629662"],"URL":"https:\/\/doi.org\/10.1145\/2629662","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,17]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}