A heuristic decomposition methodology for channel assignment problems in mobile communication systems

The paper puts forward an efficient ´first decompose, then solve´ solution strategy for channel assignment problems (CAP) in cellular communications systems. The underlying objective of the decomposition technique is that the interference graph (IG) developed for an intractable CAP be broken down into sub-graphs (channel assignment sub-problems, CASPs) of lower complexity and dimensionality by identifying the mutual interference patterns among base stations (BSs). The IG decomposition problem itself is NP-complete. A heuristic decomposition methodology is presented. The motivation for developing the heuristic technique is to bi-partition the IG using minimal computational resources. However, no guarantee of the global optimality of the partitioning solution obtained using the proposed decomposition technique is provided. The small-scale CASP associated with each subgraph developed is then solved using a conventional method (see Ali, S.Z. and Turner, L.F., Proc. IEEE 54th VTC, vol.l, p.389-93, 2001). The collection of solutions to the subproblems is the solution to the large-scale original CAP. The application of the proposed decomposition technique to a number of CAPs demonstrates the computational advantage associated with using the proposed methodology.