Solving Minimum Power Broadcast Problem in Wireless Ad-Hoc Networks Using Genetic Algorithm

Abstract

A novel permutation encoded genetic algorithm (GA) is proposed for solving the minimum power broadcast (MPB) problem in wireless ad-hoc networks. The problem has been proven to be non-deterministic polynomial (NP) complete, and diverse heuristic algorithms were reported to solve this problem recently. In this study, the MPB problem has been mathematically formulated to a constrained optimisation problem using a graph representation, and a GA-based approach is developed to cooperate with a deterministic greedy-like algorithm to obtain the MPB tree. The powerful search capability of GA is a key factor in improving the system performance in terms of the total consumption power. A variety of simulations were conducted to examine the performance of the proposed GA approach, and the results indicate that the proposed GA approach significantly outperforms the greedy-based broadcast incremental power (BIP) algorithm and exhibits competitive search strength compared with other recently proposed optimisation methods.