Research And Application Of An Enginerring-Oriented Heursitic Algorithm For Frequency Assignment

Recently, with the rapid development of the numbers of the subscribers in the mobile cellular networks, such as GSM and CDMA networks, higher demands for mobile communications operators are increasing. The frequency spectrum is quite limited in mobile communication networks; thus how to make good use of frequency resource is a critical issue in network planning and optimizing and needs effective solutions to frequency assigning, frequency planning and optimizing.Frequency planning and optimizing can be reduced to the Channel Assignment Problem (CAP).CAP is one type of classical combinatorial optimization problem. It requires reducing co-channel and adjacent-channel interference between the cells as low as possible, while allocating the limited frequencies to the cells in networks. The previous researches on CAP have a trait in common that the discrete compatibility matrix is used to describe the interference relationships between the cells and then the channels are assigned on the basis of the compatibility matrix. The object of channel assignment is that each cell gets sufficient channels and disobeys channel interval constraints as less as possible.The GSM networks in practice can provide the continuous interference data between the cells. Therefore, frequency assignment aims to make the total amount of interference between the cells as low as possible. We design an Engineering-oriented Heuristic Algorithm for Frequency assignment (EHAF, for short). EHAF does not make use of the compatibility matrix employed in traditional CAP models. Through the NCS measurement report from Ericsson OSS, the algorithm obtains statistic data of co-channel and adjacent-channel interference between the cells and creates co-channel and adjacent-channel interference tables. Subject to the constraints, i.e. Co-Channel Constraint (CCC), Adjacent Channel Constraint (ACC) and Co-site Constraint (CSC), and in line with several heuristics, EHFA allocates frequencies to the cells to ensure that the total amount of co-channel and adjacent-channel interference between the cells as low as possible. By means of EHFA, the programming language C#, MapInfo GIS and SQL server 2005, we developed a frequency planning and optimizing system.We applied EHFA to frequency optimizing of GSM networks in Yunfu and Huizhou, Guangdong Province. Compared with the artificial schemes of frequency assignment, the assignment results produced by EHFA not only met the frequency demand of each cell, but also reduced the total amount of interference between the cells. It achieved the purpose of frequency optimizing and met the mobile communications operators' requirements.