Evolutionary Multi-Path Routing for Network Lifetime and Robustness in Wireless Sensor Networks
Ad Hoc Networks
Reason for embargo
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.
Part of this work was supported by a Knowledge Transfer Partnership awarded to the University of Exeter and the IMC Group Ltd (KTP008748). We would like to thank Martin Hancock (Technical Director, The IMC Group Ltd.), and Neil Lundy (Engineering Manager, The IMC Group Ltd.) for their support and contributions. We would also like to thank Boris Pretzel (Chief Scientist, Victoria & Albert Museum), and Bhavesh Shah (Scientist, Victoria & Albert Museum), for facilitating the real network test.
This is the author accepted manuscript. The final version is available from Elsevier via the DOI in this record.
Available online 22 August 2016