Abstract
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 & 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.
DOI
10.1162/evco_a_00151
Publication Date
2015-09-01
Publication Title
Evolutionary Computation
Volume
23
Issue
3
Publisher
MIT Press - Journals
ISSN
1530-9304
Embargo Period
2024-11-22
First Page
481
Last Page
507
Recommended Citation
Rahat, A., Everson, R., & Fieldsend, J. (2015) 'Hybrid Evolutionary Approaches to Maximum Lifetime Routing and Energy Efficiency in Sensor Mesh Networks', Evolutionary Computation, 23(3), pp. 481-507. MIT Press - Journals: Available at: https://doi.org/10.1162/evco_a_00151
