Dispersion with connectivity in wireless mesh networks

We study a multi-objective access point dispersion problem, where the conflicting objectives of maximizing the distance and maximizing the connectivity between the agents are considered with explicit coverage (or Quality of Service) constraints. We model the problem first as a multi-objective model, and then, we consider the constrained single objective alternatives, which we propose to solve using three approaches: The first approach is an optimal tree search algorithm, where bounds are used to prune the search tree. The second approach is a beam search heuristic, which is also used to provide lower bound for the first approach. The third approach is a straightforward integer programming approach. We present an illustrative application of our solution approaches in a real wireless mesh network deployment problem.