A hybrid clustering and evolutionary approach for wireless underground sensor network lifetime maximization

Nguyen Thi TAM, Huynh Thi Thanh BINH, Dinh Anh DUNG, Phan Ngoc LAN, Le Trong VINH, Bo YUAN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

21 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)372-393
Number of pages22
JournalInformation Sciences
Early online date16 Jul 2019
Publication statusPublished - Dec 2019
Externally publishedYes

Bibliographical note

This 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


Dive into the research topics of 'A hybrid clustering and evolutionary approach for wireless underground sensor network lifetime maximization'. Together they form a unique fingerprint.

Cite this