Title :
A heuristic decomposition methodology for channel assignment problems in mobile communication systems
Author_Institution :
Dept. of Electr. & Electron. Eng., Imperial Coll. of Sci., Technol. & Medicine, London, UK
Abstract :
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.
Keywords :
cellular radio; channel allocation; computational complexity; graph theory; radiofrequency interference; NP-complete problem; base stations; cellular communications systems; channel assignment problems; channel assignment subproblems; computational advantage; heuristic decomposition methodology; interference graph; mobile communication systems; mutual interference patterns; Bandwidth; Base stations; Educational institutions; Interchannel interference; Large-scale systems; Mobile communication; NP-complete problem; Paper technology; Partitioning algorithms; Tree graphs;
Conference_Titel :
Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on
Print_ISBN :
0-7803-7589-0
DOI :
10.1109/PIMRC.2002.1046529