Hybrid Evolutionary Approaches to Maximum Lifetime Routing and Energy Efficiency in sensor mesh networks
Rahat, Alma As-Aad Mohammad
Everson, Richard M.
Fieldsend, Jonathan E.
Mesh network topologies are becoming increasingly popular in battery powered wireless sensor networks, primarily due to the extension of network range. However, multi-hop 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 multi-objective routing optimisation approach using hybrid evolutionary algorithms to approximate the optimal trade-off between 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 which 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 & 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’s time to first sensor battery failure.
Knowledge Transfer Partnership awarded to the University of Exeter and the IMC Group Ltd,
Copyright © 2015 The MIT Press
This is the manuscript version of the article accepted for publication in Evolutionary Computation
Vol. 23, Iss. 3, 19 September 2015, pp. 481-507