Abstract
In this paper, we examine the problem of assigningcalls in a cellular mobile network to channels in the frequencydomain. Such assignments must be made so that interferencebetween calls is minimized, while demands for channels aresatisfied. A new nonlinear integer programming representationof the static channel assignment (SCA) problem is formulated.We then propose two different neural networks for solving thisproblem. The first is an improved Hopfield neural network whichresolves the issues of infeasibility and poor solution quality whichhave plagued the reputation of the Hopfield network. The secondapproach is a new self-organizing neural network which is ableto solve the SCA problem and many other practical optimizationproblems due to its generalizing ability. A variety of test problemsare used to compare the performances of the neural techniquesagainst more traditional heuristic approaches. Finally, extensionsto the dynamic channel assignment problem are considered.
Index Terms— Channel assignment, combinatorial optimization,Hopfield neural network, self-organizing neural network.
I. INTRODUCTION
OVER RECENT years, we have seen a steady increasein the popularity of cellular mobile communication systems.The fact that the electromagnetic spectrum available forthis purpose is a limited resource places severe limitationson the size and performance of such systems. Careful designof a network is necessary to ensure efficient use of theavailable spectrum. A competitive communications industryalso forces the network design to accommodate certain performancecriteria. Operators of such networks need to assigna caller from a certain region to a channel within the frequencyspectrum in such a way that the probability of the signal-tointerferenceratio (SIR) being below some predefined limitis low. Potential interferences to this call come from threepossible sources: another caller within some range using thesame channel (a co-channel interference); another caller in anadjacent region using an adjacent channel in the frequencydomain (an adjacent channel interference); and another callerwithin the same region using another channel within somerange (a cosite interference). The combinations of regionsand channels which cause interferences are determined by theradio frequency (RF) propagation (obtained from the regional topography and morphostructure) and the spatial density ofthe expected traffic. Specialized programs have been createdfor the purpose of calculating these relationships [20]. Theexpected traffic in a particular region can also be used topredict the demand for channels.The channel assignment problem (CAP) is then to assignthe required number of channels to each region in such a waythat interference is precluded and the frequency spectrum isused efficiently. Clearly, there are two steps to achieving thisassignment successfully. The first is the design process, wherefuture traffic is forecast and the assignments are made to satisfythe requirements for the immediate future. This is a staticchannel assignment (SCA) since the assignment of channelsto regions is made only once and remains fixed. As the trafficincreases, however, it will become increasingly difficult tomaintain performance standards with this network. A moredynamic assignment strategy will need to be employed whichpermits rearrangement of assignments in an on-going adaptiveenvironment. The task of any dynamic channel assignment(DCA) procedure is dependent, to a large extent, on the successor otherwise of the initial SCA, and it is for this reason thata great deal of research has focused on this static designproblem.It has been shown that the SCA problem is a generalizedgraph coloring problem [42] and is therefore NP-hard. Manyheuristic techniques have been devised for solving the SCAproblem [3], [9], [38]. Research has also been carried out onthe theoretical components of the problem, including obtaininglower bounds for the number of channels necessary to obtainan interference-free assignment [18], [21]. Hopfield neuralnetworks have been used to solve the SCA problem [17],[32], [33], although the types of energy function chosen are ofthe Hopfield–Tank kind [29] which involve many terms andconsequently result in infeasibility and poor solution quality.This is the conclusion reached by Kunz [33].In this paper, we reformulate the SCA problem as a generalizedquadratic assignment problem, treating the noninterferenceconstraints as soft constraints in the objective functionand the demand satisfaction constraints as hard constraints.The advantage of this approach is that a solution whichminimizes the severity of any interferences will always befound, which is particularly useful if the demands and constraintsare such that no interference-free solution exists.This reformulation is described in Section II. In Section III,we briefly survey the existing techniques for solving theSCA problem, and describe simulated annealing and steepestdescent heuristics which minimize our reformulated problem.


Download full report
http://ieeexplore.ieeeiel1/49/11978/0055...ber=552073