# Frequency Channel Assignment Problem

## 1 Introduction

Wireless communication constitutes one of the fastest growing industry segments in recent years, encompassing a number of application domains such as the cellular networks, *ad hoc* networks, ubiquitous and pervasive computing, sensor networks, and so on. One of the major concerns in most of these applications involves the availability of communication channels to satisfy the channel requirements for all users of a specific network or application type. In this survey paper, we attempt to address the *channel assignment problem* (CAP) in the context of two important classes of wireless networks - cellular mobile networks and cognitive radio networks.

Mobile computing, particularly over cellular networks, has emerged as an important topic of research because of the need for computing abilities even when people are on the move. Over the last decade, the number of such cellular network dependent mobile users has been increasing nearly exponentially. With the advances in technology, there has been an increasing demand from the mobile users for providing multimedia services like voice, text, still image, and video over wireless networks. On the other hand, the available bandwidth required for such multimedia data communication for a large number of mobile users is very much limited. Such a limited availability of the radio spectrum, signal distortion, and the interference caused by the environment and other mobile users impose an inherent bound on the capacity of such wireless networks. Therefore, developing methods to utilize the scarce radio spectrum efficiently is more critical than ever before.

Based on the application scenario, the common ways to design wireless networks are: (i) infrastructure-based network design such as the cellular structure approach, (ii) infrastructure-less networks such as *ad hoc* networks, and (iii) hybrid networks which uses a mix of infrastructure with *ad hoc* network architecture and can typically be found in many sensor network applications. In an infrastructure-based network design—such as the cellular networks, the geographical region under consideration is spatially divided into a number of cells—which can be either overlapping or non-overlapping. A base station is established in each cell, and each mobile station in the cell communicates through this base station *via* a channel assigned by the base station. Several techniques such as frequency division multiplexing (FDM), time division multiplexing (TDM), or code division multiplexing (CDM) can be used to divide the available radio spectrum into such channels. Further efficient techniques based on combining the above can also be designed to divide the radio spectrum into channels. A channel can simultaneously be used by multiple base stations, if their mutual separation is sufficient to satisfy the interference constraints.

As an alternative to either the cellular or the *ad hoc* network architecture, there has been a great deal of interest in recent times on wireless mesh networks (WMNs). WMNs may be considered to be somewhere in between infrastructure-based networks such as wireless local area networks (WLANs) and *ad hoc* networks with no preinstalled infrastructure support. In WMNs, the network consists of a set of *fixed* gateway nodes and a set of non-gateway nodes (either stationary or mobile). The non-gateway nodes must access a gateway node (similar to WLANs) in order to establish communication to the outside world. These non-gateway nodes can act as either hosts or as wireless routers - forwarding packets from other users (similar to *ad hoc* networks), enabling other non-gateway nodes to establish link with the gateway nodes in a multihop fashion, if required.

This fusion of *ad hoc* network and infrastructure-based network properties not only allows significant extension of the coverage area of the network, but also enables nodes in areas with poor signal propagation properties to contact the outside world with higher probability of success. The overall effect of such a deployment is thus a substantial reduction in the number of deployed gateway nodes in order to cover a zone and consequently, the overhead in installation, operational, and maintenance expenses.

Furthermore, such a network structure also allows for scalable operations—simply by adding new gateway nodes when/where required. The reliability also improves as multiple paths to gateway nodes are more common and re-routing of packets in case of node failures are handled as in *ad hoc* networks.

Because of the above-mentioned advantages, even traditional infrastructure-based networks such as cellular networks are beginning to look at possibilities of migrating to either WMN-based or WMN-like topologies 1–4. The promises are several: reducing infrastructure setup and maintenance cost, improving fault tolerance and robustness in the face of unnatural events such as disasters and natural calamities and enhancing network coverage, among others. However, with the use of a mesh architecture, the importance of the CAP becomes even more accentuated due to the increased probability of interference between the links of a WMN, as most applications of WMNs (e.g., dense sensor networks) tend to contain more links than either traditional cellular or *ad hoc* networks in an attempt to improve reliability through path diversity 4–7. As an example, Lan and Trang 8 have proposed a technique for channel assignment in WMNs with multiple channels and multiple radios at each node of the network for increasing the network throughput.

Interference is a function primarily of transmitter power, receiver sensitivity, antenna gains, and channel loss. Channel loss is a function of distance, frequency, and weather, and is quantified by the minimum acceptable signal-to-noise ratio (SNR). Assuming that most of these factors are already determined or beyond the ability to influence, the interference can be defined directly as a function of frequency and distance. Based on that, three types of interference are generally taken into consideration in the form of constraints: (i) *co-channel constraint* , due to which the same channel is not allowed to be assigned to certain pairs of cells simultaneously, (ii) *adjacent channel constraint* , for which adjacent channels are not allowed to be assigned to certain pairs of cells simultaneously, and (iii) *co-site constraint* , which implies that any pair of channels assigned to the same cell must be separated by a certain number of channels 9.

The task of assigning frequency channels to the cells satisfying the interference constraints and using as small bandwidth as possible is known as the *channel assignment problem* (CAP). In its most general form, the CAP is equivalent to the generalized graph-coloring which is a well-known NP-complete problem 10–12.

Quite similar to the mobile computing environment—which typically operates in licensed spectrum bands, with the explosive growth in the number of wireless devices operating in the unlicensed radio spectrum bands, a severe shortage of available, unlicensed radio spectrum has arisen in recent times. The multitude of wireless networks and protocols (e.g., Wi-Fi, Bluetooth, Zigbee, etc.) operating in the unlicensed bands and vying for their share of the spectrum to enable their respective operational parameters leads to interference and performance degradation for all. Interestingly though, while the unlicensed bands are heavily loaded, in contrast, there exists portions of the spectrum—particularly the licensed bands, that are relatively under utilized. As an example, recent studies by the *Federal Communication Commission* (FCC) 13 in US have shown that at any given time and in any given geographic locality, less than 10% of the available spectrum in the TV band (from 470 to 698 MHz) is utilized. Similar spectrum utilization statistics were observed in the UK by the regulatory body OFCOM and in other parts of Europe, as well as in other parts the world 14.

To exploit these under utilized parts of the spectrum (also referred to as *white spaces* or *spectrum holes*), the FCC thus advocates the development of a new generation of programmable, smart radios that can dynamically access various parts of the spectrum, including the licensed bands. Such radios would operate as *secondary users* in the licensed bands and are required to possess the capabilities of spectrum usage sensing, environment learning, and interference avoidance with the *primary users* of the licensed spectrum bands while simultaneously ensuring the *quality of service* (QoS) requirements of both the primary and secondary users.

Radios with such capabilities are referred to as *cognitive radios* (CRs). Cognitive radios are today widely accepted as the wireless technology of the future and it is envisioned that by 2015, most radios on portable devices (e.g., cellphones, Wi-Fi enabled notebook PCs, etc.) will possess some amount of cognitive capability 15.

In the context of networks operating in licensed bands, the ability to exploit unused parts of the spectrum can provide a multitude of additional benefits. Taking the case of cellular networks as an example, such frequency agility can dramatically reduce operational and deployment/licensing costs, increase the number of users that can be supported under a single base station and improve the operator's ability to provide guaranteed service through the intelligent exploitation of such large additional unused spectrum pool. Moreover, such cognitive radio based cellular networks can offer benefit in the event of attacks or natural disasters. While a conventional cellular system is centralized in nature and can only operate in licensed bands, a cognitive system is capable of establishing communications even if some network elements are out of order or the total requested bandwidth by the users exceeds the operator's licensed bandwidth. It is thus apparent that cognitive radios would play a pivotal role in the coming generations of wireless networks 14–23.

We describe below the CAP in these two types of networks. We begin with a discussion on the CAP under the framework of a cellular mobile network, followed by describing the motivations and challenges in channel assignment for cognitive radio networks.

## 2 Channel Assignment Problem in Cellular Mobile Networks

The available radio frequency spectrum is assumed to lie on a straight line which is divided in equal intervals, with each such interval being termed as a channel and numbered as 0, 1, 2, …, in the increasing order of their center frequencies. Thus, the frequency separation between two channels *i* and *j* can be abstracted as . The CAP in a cellular mobile network is then represented by means of a *channel assignment problem graph* (CAP graph) 24 as follows. Each call to a cell is represented by a node of the CAP graph and two nodes *i* and *j* are connected by an edge with weight *c*_{ij} , (*c*_{ij} > 0), where *c*_{ij} represents the minimum frequency separation requirement between a call in cell *i* and a call in cell *j* to avoid interference. Let us now consider the following example of CAP graph as presented in Reference 25.

*Example 1* . Figure 1(a) shows a CAP graph with 3 cells where channel demands on cells 0, 1 and 2 are 1, 2, and 2 respectively. Each node in Figure 1 is labeled as (*rs*) where *r* is the cell number at which a call is generated and *s* is the call number to this cell *r* . That is, the node (10) represents call 0 in cell 1. The frequency separation requirements for this example is given by the following matrix:

The edges of the CAP graph are labeled with weights according to this matrix *C* .

Let us now assume a simple channel assignment scheme where the channels are assigned to the nodes of the CAP graph in a specific order and a node will be assigned the channel corresponding to the smallest integer that will satisfy the frequency separation constraints with all the previously assigned nodes. Following this strategy, if the channels are assigned to the nodes of CAP graph in the order ((21), (00), (10), (11), (20)), as shown in Figure 1(b), the minimum bandwidth required will be 16. However, if the channels are assigned to nodes in the order ((20), (00), (10), (21), (11)), as shown in Figure 1(c), the minimum bandwidth required will be just 13. The label [*α* ] associated with each node of the CAP graph of Figure 1(b) and (c) indicates that the frequency channel *α* is assigned to that node.

It is clear from the above example that the ordering of the nodes has a strong impact on the required channel bandwidth. Suppose there are *m* nodes in the CAP graph. Therefore, the nodes can be ordered in *m* ! ways and hence for sufficiently large *m* , it is impractical to find the best ordering by an exhaustive search.

Channel assignment schemes can be classified into several categories. In the *fixed (or static) channel assignment problem* (FCA), the number of calls to each cell is known *a priori* and a number of nominal channels is permanently allocated to each cell for its exclusive use. In the simple uniform FCA, the same number of nominal channels is allocated to each cell. Since the traffic in cellular systems is mostly non-uniform, uniform allocation may result in poor channel utilization 26. To achieve a relatively better channel utilization, the number of channels allocated to each cell should depend on the expected traffic load in that cell. This technique is called non-uniform channel allocation 27, 28. Although simple, FCA schemes are not adaptive to temporal and spatial fluctuations of user demands and to overcome this drawback, *dynamic channel assignment* (DCA) schemes have been developed which may also tackle the problem of handoff requirements 29. In DCA, all channels are available to every cell and they are assigned to newly generated calls as and when required, provided they satisfy the interference constraints. Though DCA schemes provide flexibility and traffic adaptability at the cost of higher complexity, they are less efficient than FCA under high load situations 26, 30–32. To address this drawback under high load situation, many hybrid schemes by combining the benefits of both FCA and DCA have been developed. Both the FCA and DCA schemes can be implemented in centralized or distributed fashion. In centralized schemes, a channel is assigned by the central controller whereas in the distributed schemes, a channel is selected either by the base station at which the call is initiated or by the mobile itself 26. For the case where the base stations select the channel, each base station keeps the information about the currently available channels in its vicinity and also these information are updated by exchanging status information among these stations. In the other situation where the mobile terminals are allowed to select the channel, the mobile terminals choose the channels based on the local signal to signal interference measurements 26.

Because of the NP-completeness of the CAP, researchers attempted to develop more and more time-efficient heuristic or approximation algorithms for its solution which, however, cannot guarantee optimal solutions. A number of techniques based on neural networks 33–38, simulated annealing (SA) 39–41, tabu search 42–48, and genetic algorithms 25, 49–53, have been proposed to tackle this problem.

The cellular network is often modeled as a graph and the CAP has been formulated as a graph coloring problem by several authors 24, 25, 54–63. To judge the quality of the results obtained from these approximation algorithms and heuristics, it is extremely necessary to know the lower bounds on the minimum number of frequencies needed for a solution.

### 2.1 The General Model and Different Formulations of CAP

In general, CAP can be modeled by the following components 24, 54, 55:

Based on this model, a channel assignment problem *P* can be characterized by the triplet (X,W,C). A frequency assignment Φ for *P* is said to be *admissible* if *ϕ*_{ij} s satisfy the component 5 above for all *i* , *j* , where and . The *span S* (Φ) of a frequency assignment Φ is the maximum frequency assigned to the system. That is,

Thus, one possible formulation of CAP is to find an admissible frequency assignment with the minimum span , where . The objective of this formulation is to assign frequencies to the cells satisfying the frequency separation constraints in such a way that the required span becomes *optimal* . This formulation is commonly known as the *minimum span frequency assignment problem* . The advantage of this category of algorithms is that the derived channel assignment always fulfills all the interference constraints for a given demand. However, it may be hard to find an optimal solution in case of large and difficult problems, even with quite powerful optimization tools 25.

In an alternative formulation of CAP we look for the channel assignment where the span *B* of the system is given, which may even be smaller than the required lower bound on minimum span for the given problem. Depending on *B* , it may or may not be possible to satisfy all the channel demands of each cell unless *B* is sufficiently large. Given *B* , the approach is typically to formulate a cost function, such as the number of interference constraints violated, the number of calls blocked by a given channel assignment, and then tries to minimize this cost function. This formulation is commonly known as the *fixed spectrum frequency assignment problem* . The principal disadvantage of this formulation is that, in case of very hard problems, it is almost impossible to minimize the cost function to the desired value of zero with the minimum number of channels, 25.

There is, however, another class of problems of real-life importance known as the *perturbation-minimizing frequency assignment problem* (PMFAP) 64 which is described as follows. Assume that initially an assignment has been obtained for a given network to satisfy the required channel demands. After some time, demands of some of the cells may be changed due to either, (i) newly generated calls or, (ii) a handoff situation or, (iii) completion of some ongoing calls. The objective of this variant of CAP is to accommodate these small changes in demands; but while doing so, the number of changes in the existing assignment should be minimized, while meeting the desired QoS. This variant is particularly useful to address the short-term demand fluctuations that often arise in real-life scenarios.

### Lower Bounds

As mentioned in the earlier subsection, because of the complexity of the CAP, researchers attempted to solve the problem based on heuristic approaches or approximation algorithms. Many of these algorithms do not assess how far their results are away from the optimality, whereas some of them over-estimate the number of frequencies by more than 100% 65, 66. As a result, even if by some lucky coincidence, an optimal assignment is found, it may not be recognized as an optimal one unless one has the clear idea about the lower bound on the required bandwidth. In heuristic approaches like genetic algorithm (GA), the process usually terminates after a certain number of iterations. Hence, a prior idea about the lower bound on the required bandwidth will be very much useful in deciding the termination condition of these algorithms. Furthermore, in the approaches based on neural net, SA, and tabu search, the techniques typically start from some known lower bounds and then gradually improve the results through each iteration.

The problem of determining the lower bounds on bandwidth has been extensively studied by several authors 9, 24, 25, 60, 66–70. In Reference 67, a lower bound on bandwidth has been developed for CAP which considered exclusively the co-channel interference constraints. In Reference 66, Gamst presented some lower bounds on bandwidth for CAP taking the additional constraints for adjacent channel interferences and co-site interferences into account. Improving these results, Gamst *et al* . 68 presented some results on the lower bound which, however, did not explicitly include the co-site constraints. In Reference 9, the authors derived a lower bound which, in some cases, is tighter than those presented in Reference 66 considering all the co-channel, adjacent channel, and co-site constraints. In Reference 71, new lower bounds have been developed which are generalization of the bounds presented in References 9, 66. All these lower bounds are defined on a general network of arbitrary cell structure.

For the special case of hexagonal cellular networks, the problem of determining the lower bounds has been studied by several authors 25, 60. In this special type of hexagonal cellular networks, we say that a *k-band buffering* exists in the network if the channels assigned to any two calls in two cells which are more than distance *k* apart, do not interfere with each other. In other words, for a *k* -band buffering network, we need to define *k* + 1 constants to specify the constraints for avoiding channel interferences, where *s*_{i} , denotes the minimum gap between two channels assigned to two calls in two cells which are distance *i* apart. Clearly, . Authors in References 25, 60 have studied the problem of determining the lower bounds for a two-band buffering situation in hexagonal cellular networks using only the three parameters *s*_{0} , *s*_{1} , and *s*_{2} , where *s*_{0} , *s*_{1} , and *s*_{2} are the minimum frequency separations required to avoid interference for calls in the same cell, cells at distances 1 and 2, respectively. They have derived expressions for the lower bound on bandwidth for different relative values of *s*_{0} ,*s*_{1} , and *s*_{2} for both uniform and non-uniform demand situations. These lower bounds have been computed based on the minimum bandwidth requirement for assigning frequencies to a seven-node subgraph as shown in Figure 2. Note that every node in this subgraph is within distance 2 from each other. Therefore, under the two-band buffering scenario, the channels assigned to these nodes may interfere with each other if they are not sufficiently far apart. Most importantly, no frequency reuse is possible within this subgraph. Hence, the bandwidth requirement of this subgraph will give a lower bound on the bandwidth requirement for the whole cellular network which is not necessarily a tight one. For the uniform demand of only one channel per cell, the lower bound as derived in Reference 25 is () when , and () when . The corresponding assignments are shown in Figure 3(a) and 3(b) respectively, where the label (*α* , *β*) associated with a node indicates that a frequency () is assigned to that node. For the uniform demands of *w* (* w* ≥ 2) channels per cell, the corresponding lower bounds for are

- (1), when ,
- (2), when ,
- (3), when ,
- (4), when , and
- (5), when

For the case of , the corresponding lower bounds are:

- (1)(a) , when ,(b) , when ,
- (2), when ,
- (3), when ,
- (4), when , and
- (5), when .

The lower bounds for the non-uniform demands have been derived in Reference 60. These lower bounds are also based on the minimum bandwidth requirement for assigning frequencies to the seven node subgraph as shown in Figure 2. Let *w*_{i} represent the demand of node *i* and , . Then, the lower bound as derived in Reference 60 is given by the following expressions.

It has also been shown that these lower bounds are either equal to or tighter than those in References 9, 66, 68 when applied to the special cases of hexagonal cellular network with two-band buffering.

### 2.3 Channel Assignment Schemes

Several algorithms using neural networks 33–37, SA 39–41, tabu search 42–48 and GAs 25, 49–53, have been proposed to solve this problem. In the following subsections, we briefly discuss about each of these commonly used approaches.

(1) *Genetic algorithm based approach*: For solving an optimization problem using GA, the parameter set of the optimization problem is required to be coded as a finite-length string or chromosome over some finite alphabet *Q* . A fitness function is used to evaluate the fitness of different strings. A collection of *M* such strings or chromosomes is called a population. A simple GA is composed of three basic operators: (1) reproduction or selection, (2) crossover, and (3) mutation 72. GA starts with a randomly generated initial population and in each iteration, a new population is generated from the current population applying the above-mentioned three operators on the strings of the current population. The newly generated population is then used to generate the next population and so on. All the algorithms reported in References 25, 49–53 are broadly based on this approach. The differences in these approaches lie only in the representation of different steps mentioned above and its implementations.

For example, in Reference 49, the call list is represented by a string and the quality of the generated call list is evaluated following the *frequency exhaustive assignment* (FEA) strategy, which assigns calls to the minimum available frequencies, while satisfying the interference constraints. The authors started the procedure by estimating the lower bound *B* on bandwidth. If the algorithm does not find a solution with *B* , the value of *B* is incremented by 1 and the algorithm is repeated until a valid solution is derived. Thus, in this approach the computation time will be highly dependent on the proximity of the prior estimation of the lower bound on bandwidth to its optimal value. In Reference 25, the *elitist model* (EGA) 72 is utilized to solve the general CAP. After representing the CAP by means of a CAP graph, a random order of the nodes of the CAP graph is considered as a string *S* . Channels are assigned to the nodes of the CAP graph in a specific order and a node is assigned the channel corresponding to the smallest integer that satisfies the frequency separation constraints with all the previously assigned nodes. The maximum frequency required for a given ordering is then regarded as the fitness of that string, represented by the ordering. Let *S*_{b} be the best string (with respect to the fitness value) of the population generated up to iteration *t* . In this elitist model, if *S*_{b} or any string better than *S*_{b} is not present in the population generated in iteration (*t* + 1), *S*_{b} is included in the (*t* + 1)th population. This ensures that the population gets improved in successive iterations.

(2) *Simulated annealing based approach*: For solving an optimization problem using SA, the solution space of the problem must be represented as a state space. A suitable cost function has to be designed to evaluate the cost of a state. In each iteration, the SA considers some neighborhood *s* ′ of the current state *s* , and probabilistically decides between moving to the new state *s* ′ or staying in current state *s* . The definition of the neighborhood of a state is normally application-specific. The probability function which is a function of new state *s* ′, current state *s* and a global time varying parameter called temperature *T* , is chosen so that the system tends to move to the states of lower cost. However, in order to avoid getting stuck at a local minimum, higher cost states are sometimes accepted with some non-zero probability, meaning that the system may move to the new state even when it is worse than the current state. Temperature *T* is set high initially and it is gradually reduced according to some annealing schedule as the simulation proceeds, and becomes 0 when the process terminates. Typically the process terminates when a state that is good enough for the application is found or after a certain number of iterations has been completed. All the algorithms presented in References 39–41 are broadly based on this approach. The differences in these approaches lie in the representation of the state space, definition of the neighborhood of a state, and choice of the probability function. In general, the SA approach guarantees global optimal solution asymptotically, but the rate of convergence is rather slow.

For example, in Reference 41, SA is used to solve the fixed spectrum frequency assignment problem, where the number of constraint violations is regarded as the cost function. Neighborhood states are determined through selecting a random frequency at a randomly selected transmitter. The number of constraint violations is then calculated for the new state *E*_{new} as well as the current state *E*_{old} . The probability function is chosen in the standard way, resembling the exponential form of Metropolis's approach, .

Hurley *et al.*41 compared the performance of SA with the approaches based on tabu search and GAs for solving a set of fixed spectrum scenarios in military applications and found that the SA approach with smaller number of constraint violations compared favorably with the other two approaches. An SA based algorithm was developed in Reference 39 for the CAP with the objective of minimizing interference while simultaneously assigning a certain prescribed number of channels to each cell. Mathar *et al.*40 investigated several algorithms based on the SA approach and through simulation the authors showed that all variants gave good quality solutions when compared to the optimal results.

(3) *Tabu search based approach*: Tabu search is a local or neighborhood search procedure to iteratively move from a solution *x* to a solution *x* ′ in the neighborhood of *x* , until some stopping criterion has been satisfied 73. To escape from a local optimal solution and to prevent cycling, it modifies the neighborhood structure of each solution, as the search progresses. The solution admitted to a new neighborhood is then determined through an appropriate data structure, which is the *tabu list* containing the solutions that have already been obtained in the recent past. Tabu search then excludes solutions in the tabu list from the new neighborhood. Sometimes when it is deemed favorable, a tabu move can be overridden. Such aspiration criterion is used when a tabu leads to a solution better than the currently known best solutions. Most common stopping criterion is to stop the process when some threshold on acceptable solutions has been reached or a certain number of iterations has been completed. Tabu search is a relatively simple technique which can provide considerably improved results by defining proper rules tailored to specific problems. The disadvantage is that the performance is highly dependent on the fine-tuning of several parameters 74. All the algorithms presented in References 42–48 are broadly based on this approach. The differences in these approaches lie in the representation of the move, in the definition of neighborhood of a move, and in the way of defining a tabu move.

As an example, let us consider the tabu search used in Reference 45 for solving the fixed spectrum frequency assignment problem with the objective of minimizing the total interference. Let *N* be the number of calls to be assigned and be the *F* available frequencies. A frequency assignment is represented using an array of indexes where for . The neighbors of *f* are those assignments where the array of indexes differs in precisely one component. Let *f* ′ be another frequency assignment represented by []. Then, is a neighbor of *f* if there exists a *j* , , such that , and for all with *i* ≠ *j* we have . Each neighbor corresponds to a pair (*j* , ) with , , (). To illustrate this, let there be two frequencies and assume that four calls need to be assigned. Then is a frequency assignment where frequency 1 is assigned to calls 1 and 4, whereas frequency 2 is assigned to calls 2 and 3. Similarly, is a neighbor of . A move to a neighbor (*i* , ) is said to be a tabu if it does not satisfy the *recency* and *frequency* conditions. The recency condition specifies that *i* does not appear in any of the previous *r* moves, where *r* is some positive integer. The frequency condition specifies that the proportion of the number of times *i* has been changed over all iterations, does not exceed some given *s* , 0 < *s* < 1.

Lanfear 42 investigated a tabu search algorithm by formulating the radio relay network CAP as a generalized graph coloring problem. Their model involves coloring several graphs represented by the co-channel, adjacent-channel, and co-cite constraints. 43 implemented a tabu thresholding method and reported that it outperformed SA and GA on fixed spectrum channel assignment using simulated data sets. For the fixed-spectrum frequency assignment problem, in Reference 44, a robust tabu search algorithm with a dynamic tabu list is presented. The algorithm is tested on several test problems and the results show its effectiveness when solution quality is a more important criterion than solution speed. In reference 46, a reactive tabu search method 75 is applied and the performance of the algorithm is compared with the classical tabu search based method 47.

(4) *Neural network based approach*: Neural network based approaches use an energy function which contains the objective function as well as an individual term for each of the constraints of the problem. Therefore, defining an appropriate energy function is crucial for using neural networks. Moreover, the terms of the energy function compete among themselves for minimization. As a result, a trade-off between the constraints and objective may be required in most cases. The *Hopfield neural network* has been used for solving CAP by many authors 38. Several algorithms using neural networks 33–38, 76 have been proposed to solve the problem. In Reference 37, discrete competitive Hopfield neural network (DCHNN) is used for solving the CAP. The objective is to minimize the total interference in the entire cellular network. The DCHNN can always satisfy the problem constraint and therefore guarantee the feasibility of the solutions for the CAP. Furthermore, the DCHNN permits temporary energy increases to escape from local minima by introducing stochastic dynamics. In Reference 76, a multistage self-organizing channel assignment algorithm is proposed based on the Transiently Chaotic Neural Network (TCNN) for the CAP.

An inherent disadvantage of neural network based approaches is that they tend to converge to local optima, and hence optimal solutions cannot always be guaranteed. The neural network based approaches thus typically perform well only on unrealistic small test problems 74.

(5) *Graph-based algorithms*: The cellular network is often modeled as a graph and the CAP has been formulated as a graph coloring problem by several authors 24, 25, 54–63. In all these studies, the graph used to model the cellular network ignores the geometry of the network. Some authors 24, 58, 60–63 have, however, considered the geometry of the network and solved the CAP optimally in some cases. In Reference 58

## 0 thoughts on “Frequency Channel Assignment Problem”

-->