Wireless capacity maximization: A constrained genetic approach

Given a number of wireless links, this paper addresses the problem of maximizing the network capacity, i.e., the number of links that can be activated simultaneously. Solving this problem under the physical signal-to-noise-plus-interference (SINR) model has been demonstrated to be NP-hard. Previous studies focused, almost exclusively, on approximation algorithms with guaranteed performance ratios. Although such algorithms have tremendous theoretical value, their surprisingly low approximation ratios limit their practicality. This paper solves the problem using another alternative: the genetic algorithm meta-heuristics. The main challenge in using genetic algorithms is to successfully handle optimization constraints, because the original algorithm was designed for unconstrained problems. To this end, we devise a novel constraint handling mechanism that theoretically guarantees finding feasible and optimal solutions. Our numerical results illustrate the efficiency of the proposed approach, and its superiority over existing methods.