Cluster-based Approach to Maximize Number of Users in Wireless Multi-Cell

In this paper, we consider the problem of maximizing the total number of users in a multi-cell wireless network subject to power and independent set constraints on the base stations (BSs). More precisely, we impose the condition that no two adjacent BSs can operate simultaneously due to interference requirements. We propose equivalent mixed integer linear and quadratic programming formulations for this problem and compute upper and lower bounds as well as optimal solutions for instances with up to 2000 users and 30 BSs so far. The equivalent quadratic model is obtained by penalizing the independent set constraints leading to a quadratic problem with non-convex objective function that is hard to solve. To overcome this difficulty, we derive an equivalent quadratic concave objective function which allows to solve the problem to optimality using CPLEX. Finally, we propose an efficient greedy heuristic. In our numerical experiments, we consider realistic disk graph based network instances with radial transmission ranges of 40 to 10 ms for each base station. Network deployments are generated randomly within an area of 50*50 ms2. Our preliminary numerical results indicate that for different instances, either the linear and/or the quadratic model allows to find the optimal solution more efficiently. Whilst the proposed greedy heuristic allows to obtain tight near optimal solutions for most part of the instances with gaps which are lower than 5% from the optimal solution and in less than one second.