Wireless Underground Sensor Networks (WUSNs) have attracted significant interest in recent years because of their applications in various fields. The major difference between WUSNs and terrestrial wireless sensor networks is that their signals travel through multiple layers: soil, air and a medium interface. As communications in heterogeneous channels result in more transmission loss, a solution is to deploy relay nodes to relay traffic from sensors to base stations/sinks. However, this poses several new challenges, including load balancing and transmission loss minimization in heterogeneous environments. This paper considers the problem of deploying relay nodes to prolong network lifetime under load balancing constraints. This problem can be formalized using a Mixed Integer Linear Programming model as a basis to achieve lower bound solutions. We show that the problem is NP-hard as it can be reduced to the Set Cover Problem. Two novel methods are proposed. The first is a hybridisation of a clustering heuristic and an exact algorithm using a maximum flow with min-max cost formulation. The second is an evolutionary approach to further improve our initial results. Experimental validation on a large set of benchmarks indicates that the proposed methods perform better than the existing methods. © 2019 Elsevier Inc.
Bibliographical noteThis research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number DFG 102.01–2016.03 and Shenzhen Peacock Plan (Grant no. KQTD2016112514355531 ).
- Evolutionary algorithms
- Load balancing
- Network lifetime
- Wireless underground sensor networks