A hybrid clustering and evolutionary approach for wireless underground sensor network lifetime maximization
Abstract 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.
Inf. Sci.