Evolutionary Multi-Path Routing for Network Lifetime and Robustness in Wireless Sensor Networks

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.