Abstract
Wireless sensor networks frequently use multi-path routing schemes between nodes and a base station. Multi-path routing confers additional robustness against link failure, but in battery-powered networks it is desirable to choose paths which maximise the overall network lifetime — the time at which a battery is first exhausted. We introduce multi-objective evolutionary algorithms to find the routings which approximate the optimal trade-off between network lifetime and robustness. A novel measure of network robustness, the fragility, is introduced. We show that the distribution of traffic between paths in a given multi-path scheme that optimises lifetime or fragility may be found by solving the appropriate linear program. A multi-objective evolutionary algorithm is used to solve the combinatorial optimisation problem of choosing routings and traffic distributions that give the optimal trade-off between network lifetime and robustness. Efficiency is achieved by pruning the search space using k-shortest paths, braided and edge disjoint paths. The method is demonstrated on synthetic networks and a real network deployed at the Victoria & Albert Museum, London. For these networks, using only two paths per node, we locate routings with lifetimes within 3% of those obtained with unlimited paths per node. In addition, routings which halve the network fragility are located. We also show that the evolutionary multi-path routing can achieve significant improvement in performance over a braided multi-path scheme.
DOI
10.1016/j.adhoc.2016.08.005
Publication Date
2016-12-01
Publication Title
Ad Hoc Networks
Volume
52
Publisher
Elsevier
ISSN
1570-8705
Embargo Period
2024-11-22
First Page
130
Last Page
145
Recommended Citation
Rahat, A., Everson, R., & Fieldsend, J. (2016) 'Evolutionary multi-path routing for network lifetime and robustness in wireless sensor networks', Ad Hoc Networks, 52, pp. 130-145. Elsevier: Available at: https://doi.org/10.1016/j.adhoc.2016.08.005
