advanced
Journal Information
Journal Information
   Description
   Editorial Board
   Guide for Authors
   Ordering

Contents Services
Contents Services
   Regular Issues
   Special Issues
   Authors Index

Links
Links
   FEI STU Bratislava
   SAS Bratislava

   Feedback

[07-08, 2003] 

Journal of Electrical Engineering, Vol 54, 07-08 (2003) 169-181

A DECOMPOSITION TECHNIQUE FOR FIXED CHANNEL ASSIGNMENT PROBLEMS IN CELLULAR MOBILE RADIO NETWORKS

Syed Zahid Ali

   The Fixed Channel Assignment (FCA) problem is of major importance in the design of cellular mobile radio networks, and belongs to the class of NP-complete optimisation problems. The known exact solutions to FCA problems are strictly limited by the size of the problem to be solved. In this paper, a new powerful solution approach to the FCA problem is proposed. The underlying principle of the proposed approach is first to transform and then to decompose the original intractable FCA problem into a set of several small-size and weakly interconnected FCA sub-problems by using a special heuristic. This decomposition procedure reduces significantly the complexity of the original FCA problem. The set of small-size FCA sub-problems so obtained is then solved optimally using a sequential Branch and Bound algorithm. The set of solutions obtained for the FCA sub-problems is then the guaranteed optimal solution for the original FCA problem. Computational results obtained using intractable benchmark problems confirm that the proposed approach can be applied successfully to real-world FCA problems.

Keywords: optimisation, decomposition, graph theory, communication channel


[full-paper]


© 1997-2019  FEI STU Bratislava