Lagrangian relaxation approach for low complexity channel assignment in multi-cell wlans

The Channel assignment problem for multi-cell WLANs is important due to the lack of free available channels. Usually, this problem can be formulated as a mixed integer linear program (MILP) which requires high combinatorial complexity. In this paper, a lagrangian relaxation technique is used in order to transform the MILP into a low complexity linear program. Simulation results show that the proposed channel assignment algorithm provides significant reduction in complexity compared to the MILP counterpart at the expense of insignificant increase in total interference-sum at Access Points (APs). It is also suggested that the benefits of reduced complexity outweigh the increased interference.