Using VNS for the Optimal Synthesis of the Communication Tree in Wireless Sensor Networks

We investigate the NP-hard problem of finding an optimal spanning tree in a given undirected weighted graph, which occurs while minimising the power consumption of data transmission in radio networks. We proposed new heuristics and conducted an a posteriori analysis. All of the proposed methods showed high effectiveness, but it is worth noting a hybrid genetic algorithm using variable neighbourhood search (VNS) as mutations.