{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:29:30Z","timestamp":1761611370165},"reference-count":22,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p> Mesh network topologies are becoming increasingly popular in battery-powered wireless sensor networks, primarily because of the extension of network range. However, multihop mesh networks suffer from higher energy costs, and the routing strategy employed directly affects the lifetime of nodes with limited energy resources. Hence when planning routes there are trade-offs to be considered between individual and system-wide battery lifetimes. We present a multiobjective routing optimisation approach using hybrid evolutionary algorithms to approximate the optimal trade-off between the minimum lifetime and the average lifetime of nodes in the network. In order to accomplish this combinatorial optimisation rapidly, our approach prunes the search space using k-shortest path pruning and a graph reduction method that finds candidate routes promoting long minimum lifetimes. When arbitrarily many routes from a node to the base station are permitted, optimal routes may be found as the solution to a well-known linear program. We present an evolutionary algorithm that finds good routes when each node is allowed only a small number of paths to the base station. On a real network deployed in the Victoria &amp; Albert Museum, London, these solutions, using only three paths per node, are able to achieve minimum lifetimes of over 99% of the optimum linear program solution\u2019s time to first sensor battery failure. <\/jats:p>","DOI":"10.1162\/evco_a_00151","type":"journal-article","created":{"date-parts":[[2015,5,7]],"date-time":"2015-05-07T18:18:10Z","timestamp":1431022690000},"page":"481-507","source":"Crossref","is-referenced-by-count":6,"title":["Hybrid Evolutionary Approaches to Maximum Lifetime Routing and Energy Efficiency in Sensor Mesh Networks"],"prefix":"10.1162","volume":"23","author":[{"given":"Alma A. M.","family":"Rahat","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard M.","family":"Everson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan E.","family":"Fieldsend","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSNIP.2007.4496896"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"B3","first-page":"370","volume-title":"Proceedings of the UK Performance Engineering Workshop","author":"Brander A. W.","year":"1995"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.833122"},{"key":"B5","volume-title":"Evolutionary algorithms for solving multi-objective problems","author":"Coello Coello C. A.","year":"2001"},{"key":"B6","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2001"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01197559"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2003.810733"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61723-X_1022"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/ISSNIP.2007.4496871"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/WI-IATW.2006.42"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1109\/PCCC.2011.6108088"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/ISDA.2005.15"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.040310.00002"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2006.1687734"},{"key":"B17","first-page":"1175","author":"Rahat A.A.M.","year":"2014","journal-title":"Proceedings of the Conference on Genetic and Evolutionary Computation"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1109\/49.779917"},{"key":"B19","first-page":"880","volume-title":"Proceedings of the IEEE International Conference on Networking, Sensing and Control","author":"Xue F.","year":"2006"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1109\/WCNC.2012.6214324"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581628"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:39Z","timestamp":1615586319000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/23\/3\/481-507\/1001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1162\/EVCO_a_00151"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00151","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}