Int. J. Communications, Network and System Sciences, 2011, 4, 727-734
doi:10.4236/ijcns.2011.411089 Published Online November 2011 (http ://www.SciRP.org/journal/ijcns)
Distributed Frequency Assignment Using Hierarchical
Cooperative Multi-Agent System*
Jamal Elhachmi, Zouhair Guenoun
Laborat ory o f Electronics an d Tele communi c at i on s , Mohammadia School of Engineers (EMI), Rabat, Morocco
Received June 21, 201 1; revised July 20, 2011; accepted August 11, 2011
Abstract
Recent demand for wireless communication continues to grow rapidly as a result of the increasing number of
users, the emergence of new user requirements, and the trend to new access technologies. At the same time,
the electromagnetic spectrum or frequencies allocated for this purpose are still limited. This makes solving
the frequency assignment problem more and more critical. In this paper, a new approach is proposed using
self-organizing multi-agent systems to solve distributed dynamic channel-assignment; it concerns distribu-
tion among agents which task is to assign personal station to frequencies with respect to well known con-
straints. Agents only know their variables and the constraints affecting them, and have to negotiate to find a
collective solution. The approach is based on a macro-level management taking the form of a hierarchical
group of distributed agents in the network and handling all RANs (Regional Radio Access Network) in a lo-
calized region regardless of the operating band. The approach defines cooperative self-organization as the
process leading the collective to the solution: agents can change the organization by their own decision to
improve the state of the system. Our approach has been tested on PHEADEPHIA benchmarks of frequency
assignment Problem. The results obtained are equivalent to those of current existing methods with the bene-
fits that our approach shows more efficiency in terms of flexibility and autonomy.
Keywords: Dynamic Frequency Assignment, Optimization Problem, Multi-Agent System, Artificial
Intelligence
1. Introduction
With growth in the demand of mobile telephone services,
the efficient use of available spectrum is becoming in-
creasingly important. The studies of a frequency assign-
ment problem (also called a channe l assignment problem)
in cellular mobile systems are so abundant [1-5]. Various
Artificial Intelligent (AI) techniques, includin g con straint
satisfaction, simulated annealing, neural networks, taboo
search, and genetic algorithms, have been applied to this
problem [6-12].
An overview of the frequency assignment problem is
as follows: For an existing set of, geograp hically d iv ided,
regions (called cells—typically hexagonal), frequencies
(channels) must be assigned to each cell according to the
number of call requests. Three types of electro-magnetic
separation constraints exist.
 Co-channel constraint: the same frequency cannot be
assigned to pairs of the cells that are geographically
close to each other.
 Adjacent channel constraint: similar frequencies can-
not be simultaneously assigned to adjacent cells.
 Co-site constraint: any pair of frequencies assigned to
the same cell must have a certain separation.
The goal is to find a frequency assignment that satis-
fies the above constraints using a minimum number of
frequencies (more precisely, using the minimum span of
the frequencies). It must be noted that there exist several
variations of frequency assignment problems. The bench-
mark problems provided by the EUCLID-project Com-
binatorial Algorithms for Military Applications (CALMA)
project are well-known in the constraint satisfaction/
optimization research community. This type of problem
arises from a military application, and geographical in-
formation including cells is not described in the problem
specification. Constraint satisfaction/optimization tech-
niques can solve this type of problem quite efficiently.
The objectives of this paper are twofold. First, present
*Laboratory of Electronics and Telecommunications-Mohammadia
School of Engineers, Rab at, Morocco.

J. ELHACHMI ET AL. 728
and formulate the problem of frequency assignment.
Second, establish a perspective of resolution based on the
application of Hierarchical Multi-Agents System (HMAS)
for an intel ligent resources management that al lows insert-
ing dynamically the new li nks in the basi n of the net work.
Unlike centralized conventional methods our approach
provides a distributed management framework, which
deals with intelligent behavior which is the product of
cooperative activity of several agents to fill the limits of
classical Artificial Intelligence (AI) for solving this
complex problem. Through a passage of individual be-
havior to collective behavior characterized by a distrib-
uted control of distributed among entities (agents) gov-
erned by simple rules. Instead of representing each call
as a variable, we represent a cell as a variable that has a
very large domain. Furthermore, we determine the vari-
able value step by step instead of determining a variable
value at one time. To each cell is associated a coopera-
tive agent that handles the assignment of a frequency.
Within a Radio Area Network-RAN (Regional Radio
Access Network) and at each step, an agent is elected by
all its neighbors. The election is based on empirical rules
for calculating the degree of separation of an agent, the
degree of saturation and the improvement claimed by the
neighbors for an assignment. The elected agent assigns
the smallest frequency in the spectrum that meets all its
constraints. In the case of a non permitted assignment,
the agent may be ser ved by a neighboring RAN, through
a mechanism of cooperation between supervisor agents
of both RANs. If no proposal has been received, the su-
pervisor agent can make a Taboo Search for an improve-
ment in the overall assignment in the associated RAN.
The rest of this paper is organized as follows. In Sec-
tion II, we review the research contributions in the area
frequency assignment. In Section III, we formulate the
frequency assignment problem. In Section IV, we de-
scribe our resolution approach to this problem that util-
izes hierarchical multi-agent system. Section V is re-
served to show experimental evaluations using standard
benchmark. Finally, Section VI concludes our work with
a comparison to other current research and a projection
for future issues.
2. Related Work
The current challenges in radio networks are: to ensure
an efficient and full use of radio frequency resources and
multimedia applications, Connect at best anywhere, any-
time and with any network. Customize the more power-
ful features stimulated by the increasing consumers’ de-
mand. Find solutions for the mobile business. And tend
toward several access technologies whose assignment is
local and continuously and independently updated, ren-
dering impossible any overall control. This lead to a very
interesting and pertinent issue for radio spectrum is dy-
namic spectrum assignment problem.
This problem is one of the most studied problems in
the literature, particularly multiple variants algo rithms are
proposed for s ol vi ng t hi s p ro bl em [1,5,7,10, 11, 13 -1 6].
The problem starts from some networks initial con-
nections (namely robust) to develop progressively the
subsequent connections according to the operational
change of communication needs and taking into account
the constraints of disturbances wit h all initial connections.
Constraint satisfaction techniques are a board family
of greedy algorithm that guarantees an exhaustive search
in the search space of a complete solution. But in some
cases it can be impossible or impractical to solve these
problems completely and the time and effort required to
the search may be prohibitive, and the most straightfor-
ward way for solving such problems using constraint
satisfaction techniques would be to represent each call as
a variable (belonging to the domain of available frequen-
cies), then to solve the problem as a generalized graph-
coloring problem [7]. However, solving real-life, large-
scale problems’ using this simple formulation seems
rather difficult without avoiding the symmet ries between
calls within one cell [2].
Unlike greedy methods, meta-heuristics seek to find
an optimal solution with a good compromise in a rea-
sonable time. These techniques are nowadays widely
used; such as the following techniques that have become
popular: Simulated Annealing (SA), Taboo search (TS),
and Genetic Algorithms (GAs).
The taboo search technique is based on the intelligent
search and embraces more efficient and systematic forms
of direction of search.
The simulated annealing techniqu e (SA) is a stochastic
computational technique used for solving big optimiza-
tion problem such as frequency assignment problem, by
determining the global minimum value of an objective
function with various degrees of freedom subject to the
problem in a reasonable amount of time. This technique
is more efficient than the Taboo search technique; its
advantages are its gen erality and its cap ab ility to move to
states of higher energy. On the other hand the Taboo
Search (TS) presented her does not support this feature.
This is why TS cannot run away from likely local min-
ima and normally results inferior configurations [6].
Another way of the problem resolution consists of
representing a cell as a variable that has a wide area of
values, and tries to determine the value of this variable
step by step instead of determining a value for this vari-
able at one time.
Recently, neural networks have been considered one
of these ways for the channel assignment problems. The

J. ELHACHMI ET AL.729

advantages of the algorithm are its inherent parallelism,
its property to detect areas of different problem difficulty
without heuristics, and the possibility of extending the
algorithm to ‘soft’ interference criteria. One major dis-
advantage of a neural network is that it gives the local
optimal value rather than the global optimal value. And
the solution varies depending on the initial values [17].
Genetic Algorithms (GA) have an advantage over
Neural Networks or Simulated Annealing in that genetic
algorithms are generally good in finding very quickly an
acceptably good global optimal solution to a problem [1];
even if, genetic algorithms do not guarantee to find the
global optimum solution to the problem. In this algo-
rithm, the cell frequency is not fixed before the assign-
ment procedures as in the previously reported channel
assignment algorithm using neural networks [17]. But
the Genetic algorithms are expensive in computing time,
as they handle multiple solutions simultaneous ly.
3. Frequency Assignment Problem
Formulation
A frequency assignment problem can be formalized as
follows:
Let be a set of n transceivers (TRXs),

12
,, ,
n
Ttt t

and let

12
,,,
k
iii i
F
fff N be the set of valid fre-
quencies that can be assigned to a transceiver i
tT

,
(the cardinality of Fi could be different to
each TRX). Furthermore, let be a
set of given sectors (or cells) of cardinality m. Each
transceiver i is installed in exactly one of the m
sectors and is denoted as
1, ,in

12
,,,
m
SSS S
S
tT

i
St

.
The set of constraints is represented by a m* m matrix
called matrix of compatibility:



*
,
ii
mm
M  . The
two elements ij

and ij

of a matrix entry

,,
ij ij
Mij


  are numerical values greater than or
equal to zero and they represent the mean and standard
deviation respectively, of a Gaussian probability distri-
bution used to quantify the interferences ratio (C/I) when
sector i and j operate on a same frequency. Therefore, the
higher the mean value is, the lower interferences are, and
thus it will have a superior communicatio n quality.
A solution to the problem lies in assigning to all the
TRXs (ti) a valid frequency from its domain (Fi), in order
to minimize the following cost function:
 
,,,
sig
tTuTut
CpC ptu

 (1)
where Csig will compute the co-channel interferences (Cco)
and the adjacent-channel interferences (Cadj) for all sec-
tor t and u, in which the transceiv ers t and u are installed,
that is, s(t) and s(u), respectively.
12 n
pFF F

 denotes a solution (or frequency
plan) , wher e


pt
ii
F

is the frequency assigned to the
transceiver ti. Moreover, tu
s
s

and tu
s
s

are the inter-
ference matrix values at the entry M(st, su) for the sectors
st and su. In order to obtain the Csig cost from Equation
(1), the following conditions are considered:
 

 

 
if ,2
,if, 0,
,if, 0,
0otherwise
tu
tu tu
tu
tu tu
tu
cos stu
ss ss
adjs stu
ss ss
Kptpu
pt pu
Css
pt pu
Css
ss






0
2











(2)
where K, being a very large value, is defined in the con-
figuration file of the network. The K value makes it un-
desirable to allocate the same or adjacent frequencies to
TRXs that are installed in the same sector. In our ap-
proach to solve this problem, this restriction was incor-
porated in the creation of the new solution (frequency
plan) produced by the algorithm. Therefore, we assure
that the solution does not have this severe penalty, which
causes the most undesirable interferences as shown in [1]
and [3].
4. Resolution Approach and Development
The approach comes in the form of a group of distributed
agents in the network where each regional network is
overseen by a supervisor agent. That it combines an
agent to each cell called a station agent.
4.1. Station Agent
An agent can be defined as a computer system located in
an environment and which can act autonomously and
flexibly to achieve the objectives for which it was de-
signed [12] .
To each link li is associated an agent Ai responsible of
assigning a value fi in its domain Di.
Two data are sufficient to characterize the agent out-
side its environment:
First, the frequency value of the corresponding link:
The agent chooses among the values in the frequency
domain corresponding to this link: for each Ai in A, the
ii
f
D

, where is the frequency domain of li.
i
Second, the difficulty of an agent defined as a quanti-
tative measure that reflects the current status of this agent.
It is the decision criterion used to choose an agent. It is
represented in the form of two essential and sufficient
entities that are the degree of separation and the degree
of saturation, and it is the criterion used to select the
elected agent.
D
These two entities are intuitively and experimentally

J. ELHACHMI ET AL. 730
determined.
For any agent i
A
A, we note the degree of
separation of the corresponding link li as the sum of the
incident constraints values to stations.

i
DA
For each Ai in A,

where
iijij
ij
DACC C








.
The degree of saturation at step p is determined from
the banned intervals for those links that are not yet as-
signed. It can be deduced by the number of unsatisfied
constraints.
For i
A
A, NIS(Ai) is the number of unsatisfied con-
straints with its value fi:

, for each such as 0 and 0
iijj jij
ij
NIS ACAfC









.
At step p and for each Ai in A, D_SATp(Ai) = NIS(Ai)
The agent who has the greatest degree of saturation
will be considered as the most on difficulty.
Each agent operates in a physical environment; it is its
frequency domain. Even though these domains may be
identical between several agents, these domains are not
shared.
Similarly an agent has an unshared copy of constraints
that allows it to be independent of other agents.
The social Environment consists of all neighbors of an
agent from which it has only a partial view. It knows
about its neighbors only their values and their difficulties.
It has no idea abou t its neighbor s’ con strain ts, views, and
domains. The communication is performed by sending
messages and a mailbox is associated with each agent
that stores the received messages fro m other agen t s [18].
The neighborhood of an agent Ai is defined by all
agents connected by a constraint to this agent.
For each Ai in A,


0,
ij ijij
VAA ACC C 

straints is permanent. Any change of view leads to an
e degree of
sa
ugh cooperation, the random does
no
d at
th
, the agent deactivates: he re-
po
ill carry out the cycle (elec-
tio
avior of an agent can be presented as follows:
ne all of these neighbors
.
Any change of view leads to an immediate update of
the state of constraints. The agent will be in a consistent
state at any time.
Behavior:
The behavior of an agent takes place in three phases:
One the one time and through the communication
mechanism between the agent and its neighbors that is
supposedly in place and robust, conducted by messages,
where each message reaches in a finite time. And that
each agent always handles the messages it receives, the
agent manages to know the degree of saturation and val-
ues of agents in its neighborhood. Then decide if it
moves or not. At the end of a movement, the corre-
sponding environment is maintained.
The agent is autonomous, homogeneous in its behav-
ior than its performance with those neighbors. Consis-
tency between the view of the agent and its local con-
immediate update of the state of constraints.
Thus an agent will be able to calculate th
turation as soon as he knows the value of the agents in
its neighborhood. These conditions are not blocking the
measure in which agents communicate their information
once they have them.
Note here that, thro
t play a role as might be the case for other methods.
This is not to randomly select an agent to explore more
options. But rather to select an agent from among those
agents considered equals which all lead to a good solu-
tion. So the agent with the greatest difficulty will try to
improve its situation since he was elected. This phase
marks one of the aspects of cooperation: agents let act
the agent the greatest difficulty if it isn't the elected.
The next phase is only possible for an agent electe
e previous phase. The elected agent will select and
assign a value that considers the best for him and his
neighbors from his private domain of values. And one
that minimizes the sum of local cost constraints, based
on its current information.
At the end of this phase
rted to his neighborhood and his supervisor that he
will not participate in the next election as one of its
neighbors have not been elected. This egalitarian policy
for the election allows any neighbor with the less diffi-
culty to have the opportunity to be elected. While it is
disabled, if one of its neighbors is elected, the agent is
still invited to the assignment session: such deactivation
is a result of the last phase.
Once booted, the agents w
n, decision and assignment) but they can not finish
themselves. It is the supervisor agent who will take over
this task when the execution time limit is reached or a
termination criterion is achieved: an overall objective
corresponding to the results already kn own for this prob-
lem [19].
The beh
Step 1:
//determi
Determine V(Ai);
V(Ai) ={Aj

A (j

i)/C0}
/ epfor an agent
ij 
/calculate itsdegre of searation
Calculate D(Ai);
For all Aj

V(Aij

i) ()
E
//it Ai is the largest D(Ai) then it is the
Ai sendsD(Ai) to Aj;
Ai Receives D(Aj) ;
nd For
f the Agen
elected
If {

Aj

V(Ai), D(Ai) > D(Aj) }
Tnhe Ai is elected;
Ai: fi  f such as

J. ELHACHMI ET AL.731
(A) such as
f
//aff tDomain
A
go
Eceives f
//requency of the elected agent
E
St late D_SATp(A) step p ( ):do
EV(A)/D_SATp(A) > D_SATp(A) }
E_SATp(A) =
A) } then A is elected ;
Di AjV(Ai) such
ij i
//affects the f
ds f to all A
f = min {fi, fi Di ji
j 0 and |fi – > C(Cij tre)};
ectshe frequency f, Di the Ai frequency
/A
isV ufj| ij
Ai sends fi to all AjV(Ai) ;
i
to step 3;
deactivates;
lse
Re j
eceives the fr
go to step 2;
nd If
ep 2:
Calcu i
//the degree of saturation on
For all Aj V(Ai) such as fi = 0 ji
Ai sends D_SATp(Ai) to Aj;
Ai receives D_SATp(Aj) ;
nd For
If {Aj i ji
Then Go to Step 2;
lse If {Aj V(Ai) /Dj
D_SATp(i)}
If {D(Ai) > D(Aj i
Ai: fi  f such as
f = min {fi , fi  / 
as fj0 and|fi – fj| > C (Cij s true)};
requency fi, Di the Ai frequency
Domain
Ai sen i j

V(A) ;
El o to Step 2;
En
E
E
as
i A(A) such as
–| >C frequency Do-
ds f to all AV(A ) ;
E
St ation of the agent
4.2. Supervisor Agent
The supervisor agent is first in charge of the cooperation
ents associated to stations: called sta-
RAN data associated to station agents:
and collecting responses (until triggering a
gent can communicate with other re-
so
a blockage, a Taboo search is performed
on
in our forthcoming
5. Results
We have tested our approach of hierarchical multi agents
ems/Philadelphia/ and in [20]),
ulated based on an area in
Ph
nducted on an Intel Pentium
In
i
Ai deactivates;
go to step 3;
se
G
d If
nd If
lse
Aj is elected;
Ai: fi  f such
f = min {fi,fiD/j i
fj0 and | fi fj Cij (ij is true)};
V
//affects the frequency f, Di the Ai
main
Ai senij i
Ai deactivates; 
go to step 3;
nd If
ep 3:
//Elimin
Exit;
between other neighbors RANs supervisor agents. Sec-
ond, the supervisor agent oversees the management of
assignments by:
 Initializing ag
tion agents.
 Sending all
associated Frequency Domain, re-use matrix, stations
rentals.
 Holding
timeout). In case of a non permitted assignment
within its RAN, the agent may resort to another su-
pervisor agent.
The supervisor a
urces outside of its frequency domain through a coop-
eration procedure similar to all supervisor agents of
various RANs.
In the case of
the overall allocation to achieve an optimal allocation
of all stations of the associated RAN.
This part will be considered in details
publications.
System (HMAS) simulated at a RAN level for the fre-
quency assignment problem (FAP), such as it is modeled
on the web page of the site of the Research Institute of
Zuse Institute Berlin ZIB dedicated to an area on Phila-
delphia-Pennsylvania
(http://fap.zib.de/probl
which have been used widely in previous researches in-
cluding [1,14,15].
These problems are form
iladelphia, Pennsylvania. The network consists of 21
cells as shown in Figure 1.
Our experiments were co
side (with 4 GB of RAM). There are many variations
for setting constraints and demands and several compet-
ing teams of researchers have worked on the same in-
stances of problem. We present in Table 1 the para meter
setting used in some approaches and adopted by ours
evaluations.
Figure 1. Cellular geometry of philadelphia problems.

J. ELHACHMI ET AL. 732
Instance Nc acc Cii Demand Vector
Table 1. Specification for philadelphia pr oblems.
P1 12 2 5 Case 1
P2 7 2 5 Case 1
P3 12 2 7 Case 1
P4 7 2 7 Case 1
P5 12 2 5 Case 2
P6 7 2 5 Case 2
P7 12 2 7 Case 2
P8 7 2 7 Case 2
P9 12 2 5 Case 3
P10 12 2 5 Case 4
In this table, “Nc” means the square of required dis-
ta
77 28 13 15 31 15 36 57
28 5 8 12 25 30 25 30 40 40 45 20 30 25 15
15 16 16 16 30 36 104 154 56 26 30 6 2 30
72 2 32 60 72 208 308 112 52 60
12 ed with our approach.
W
lis
Instance LAS
nce for co-channel constraints, assuming that the dis-
tance between adjacent cells is 1. For example, if Nc = 12,
while cell 1 and cell 5 can use the same frequency (the
distance is 4), cell 1 and cell 4 cannot (the distance is 3).
“acc” represents the separation required for adjacent
channel constraints, and “Cii” represents co-site con-
straints. The demand vectors used in the table are as fol-
lows (case 3 and case 4 are obtained by multiplying 2
and 4 to case 1, respectively):
Case 1: (8 25 8 8 8 15 1 8 52
8 10 13 8)
Case 2: (5 5
30 20 20 25)
Case 3: (16 50
114 56 16 20 26 16)
Case 4: (32 100 32 3
4 60 144 22 8 11 2 32 40 52 32).
Table 2 shows the results obtain
e consider the theoretical lower-bounds as it repre-
sented in [1,5,20], and we use the best solution obtained
so far. Ours results are compared with results of the best
tree methods, from seven reported methods. The tree me-
thods are: First, a constraint satisfaction method (CS) and
second a Neural network (NN).the third a Simulated An-
nealing (SA). The last row in the table shows our results.
To the extent of the authors' knowledge, the best pub-
hed results for these problems have been obtained by
FASoft [1,9,15,20]. FASoft is an integrated package of
various methods for solving frequency assignment prob-
lems, such as heuristic sequential methods, methods us-
ing constraint satisfaction techniques, Simulated An-
nealing, GA, Tabu search, etc. We show the results ob-
tained with Simulated Annealing (SA) and Tabu search
(TS) reported in [9]. These two methods are the most
Table 2. Comparaison of solution quality.
ower bounds CS NN SE HM
P1 427 427 427 460 427
P2 427 427 427 447 427
P3 533 533 536 536 533
P4 533 533 533 533 533
P5 258 258 283 283 258
P6 253 253 270 270 253
P7 309 309 310 310 309
P8 309 309 310 310 309
P9 856 856 … … 856
P10 17141714… … 1714
fficient among the various components of FASoft. Fur-
2, our algorithm obtains opti-
m
orithm
in
e
thermore, we show the best results obtained with a set of
heuristic sequential methods (SE) reported in [5], and the
results obtained with neural networks (NN) reported in
[6], and the results obtained with a constraint satisfaction
method (CS) repor ted in [1] (“...” in the table means that
the result is not reported).
As shown in the Table
al solutions for all instances. Moreover, this method
can obtain better or equivalent solutions compared with
existing methods for all problem instances,
To examine the efficiency of the proposed alg
larger-scale problems, we show the evaluation results
for the benchmark problems presented in [15,19]. There
are 7*7 symmetrically placed cells (49 cells in all) in
these problems. Problem parameters are described in
Table 3, where “Cij” is the minimal frequency separation
between any pair of cells whose distance is less than
c
N, except for adjacent cells. The demand vector is:
4 11 13 15 23 21 25 19 20 21 17 10 18 27 23 29 10
17 16 22 14 19 14 22 27 28 25 30 1 4 18 28 26 12 10 27
29 11 18 24 24 20 25 12 22 25 29 19 14). This vecto r is
randomly generated from a uniform distribution between
10 and 30. There are 976 calls in total. Table 4 shows
the results obtained with our new method (hybrid Taboo
search). For comparison, we show the results described
in [15], i.e., the results obtained using neural networks
(NN), and the best results obtained with a constraint sat-
isfaction method (CS).
Since the optimality of the obtaine
(19 1
d solution is guar-
anteed, and the execution time for these instances is very
short, our approach obtains much better solutions than
those of NN and CS for all instances and a very high-
quality solutions are obtained within a reasonably short
running time.

J. ELHACHMI ET AL.733
ification for Kim’s benchmark proble ms.
Instance cij ii
Table 3. Spec
N C acc C
K1 7 1 1 3
K2 7 2 3 5
K3 7 3 4 7
Table 4. Comparison of solution quality.
Instance CS NN SE HMAS
K1 168 168 178 164
K2 422 435 473 408
K3 619 630 673 594
6. Conclusions and Future Issues
In this algorithm, we represent a link as a variable with a
rimental evaluations using real standard bench-
m
ll-suited to this prob-
le
7. Acknowledgements
The authors are grateful to all members of the Laboratory
8. References
[1] M. da S. Maximiano, M. A. Vega-Rodríguez, J. A. Gómez-
very large domain, and determine the variable value dy-
namically and step by step. Which is handled by a com-
puter system located in the environment and can act
autonomously and flexibly to achieve the objectives for
which it was designed. Furthermore, we have developed
a powerful cell-ordering heuristic and introduced the
limited discrepancy search to cope with large-scale pro-
blems.
Expe
ark problems showed that for most of the problem in-
stances, our approach can find better or equivalent solu-
tions compared with existing current optimization meth-
ods. These results imply that paradigm of distributed
agents is capable of solving realistic application prob-
lems, if we choose the appropriate problem representa-
tion, and provides a conceptual framework for modeling
and simulating a complex system.
Furthermore, it is particularly we
m and offers distinct advantages compared to existing
methods. It incorporates an extra macro-level manage-
ment and handling all RANs in a localized region re-
gardless of the operating band, where each regional net-
work is overseen by a supervisor. It shows more effi-
ciency in terms of flexibility and autonomy. It is con-
tinuously adaptable for a new insertion if a reallocation
of radio frequency resources must be made. Since the
system can be added to, modified and reconstructed,
without the need for detailed rewriting of the application.
This system also tends to be rapidly self-recovering and
failure proof, usually due to the heavy redundancy of
components and the self managed features. We can say
that our approach is justified by: Adapting to reality,
cooperation, the integration of expertise incomplete,
modularity, effectiveness and reliability. Our future work s
also include evolutionary multi-agent algorithms that are
stronger, introducing the hybrid genetic algorithms with
iterative improvement of search.
of Electronics and Telecommunications in Mohammadia
School of Engineers (EMI) for the contribution of their
ideas, and for the contribution of such an approach and
who, in one way or another, have helped to improve it.
Pulido and J. M. Sánchez-Pérez, “A Hybrid Differential
Evolution Algorithm to Solve a Real-World Frequency
Assignment Problem,” International Multiconference on
Computer Science and Information Technology, Wisia,
20-22 October 2008, pp. 201-205.
doi:10.1109/IMCSIT.2008.4747240
[2] M. Yokoo and K. Hirayama, “Frequency Assignment for
Bounds for a Class of Fre-
Cellular Mobile Systems Using Constraint Satisfaction
Techniques,” Principles and Practice of Constraint Pro-
gramming, Lecture Notes in Computer Science, Vol.
1713, 1999, pp. 490-491.
[3] A. Gamst, “Some Lower
quency Assignment Problems,” IEEE Transactions on
Vehicular Technology, Vol. 35, No. 1, 1986, pp. 8-14.
doi:10.1109/T-VT.1986.24063
[4] J. K. Hao, R. Dorne and P. Galinier, “Tabu Search for
Frequency Assignment in Mobile Radio Networks,”
Journal of Heuristics, Vol. 4, No. 1, 1998, pp. 47-62.
doi:10.1023/A:1009690321348
[5] K. N. Sivarajan, R. J. McEliece and J. W. Ketchum, “Chan-
nel Assignment in Cellular Radio,” Proceedings of 39th
IEEE Vehicular Technology Society Conference, San
Francisco, 1-3 May 1989, pp. 846-850.
doi:10.1109/VETEC.1989.40173
[6] N. Funabiki, N. Okutani and S. Nishikawa, “A Three-
. Grindal, “Automatic Frequency As-
ment: Theory and Appli-
stage Heuristic Combined Neural Network Algorithm for
Channel Assignment in Cellular Mobile Systems,” IEEE
Transactions on Vehicular Technology, Vol. 9, No. 2,
2000, pp. 397-403.
[7] M. Carlsson and M
signment for Cellular Telephones Using Constraint Sat-
isfaction Techniques,” Proceedings of the Tenth Interna-
tional Conference on Logic Programming, MIT Press
Cambridge, 1993, pp. 647-663.
[8] W. K. Hale, “Frequency Assign
cation,” Proceedings of the IEEE, Vol. 68, No. 12, 1980,
pp. 1497-1513. doi:10.1109/PROC.1980.11899
[9] S. Hurley, D. H. Smith and S. U. Thiel, “FASoft: A Sys-
tem for Discrete Channel Frequency Assignment,” Radio
Science, Vol. 32, No. 5, 1997, pp. 1921-1939.
doi:10.1029/97RS01866

J. ELHACHMI ET AL. 734
d S. U. Thiel, “Improving Heu-[10] D. H. Smith, S. Hurley an
ristics for the Frequency Assignment Problem,” Euro-
pean Journal of Operational Research, Vol. 107, No. 1,
1998, pp. 76-86. doi:10.1016/S0377-2217(98)80006-4
[11] D. Kunz, “Channel Assignment for Cellular Radio Using
Neural Networks,” IEEE Transactions on Vehicular Tech-
nology, Vol. 40, No. 1, 1991, pp. 188-193.
doi:10.1109/25.69987
[12] N. Funabiki and Y. Takefuji, “A Neural Network Parallel
Algorithm for Channel Assignment Problems in Cellular
Radio Networks,” IEEE Transactions on Vehicular Tech-
nology, Vol. 41, No. 4, 1992, pp. 430-437.
doi:10.1109/25.182594
[13] J. Elhachmi and Z. Guenoun, “Frequency Assignment for
ishra, “Fundamentals of Cellular Network Plan-
Cellular Mobile Systems Using a Hybrid Tabu Search,”
Journal of Telecommunications, Vol. 8, No. 1, 2011, pp.
11-15.
[14] A. R. M
ning and Optimisation: 2G/2.5G/3G... Evolution to 4G,”
Wiley, Hoboken, 2004, pp. 21-54.
doi:10.1002/0470862696
[15] F. Luna, C. Blum, E. Alba and A. J. Nebro, “ACO vs
ET Docket No. 03-322 Notice of Proposed Rule
J. Durillo, “Solving
EAs for Solving a Real-World Frequency Assignment
Problem in GSM Networks,” ACM, New York, pp. 94-
101,
[16] FCC,
Making and Order, December 2003.
[17] F. Luna, A. J. Nebro, E. Alba and J.
Large-Scale Real-World Telecommunication Problems
Using a Grid-Based Genetic Algorithm,” Engineering
Optimization, Vol. 40, No. 11, 2008, pp. 1067-1084.
doi:10.1080/03052150802294581
[18] F. Cornet, “Etude d’un Problème D’Allocation de Fré-
enoun, “A Multi-Agent System for
Quences par Systèmes Multi-Agents Adaptatifs,” Re-
search Master IARCL Report, Université Paul Sabatier,
Toulouse, June 2006.
[19] J. Elhachmi and Z. Gu
Resource Management in GSM Cellular Networks,” In-
ternational Symposium on Distributed Computing and
Artificial Intelligence, Advances in Intelligent and Soft
Computing, Vol. 91, 2011, pp. 99-106.
doi:10.1007/978-3-642-19934-9_13
[20] R. Haralick and G. L. Elliot, “Increasing Tree Search
Efficiency for Constraint Satisfaction Problems,” Artifi-
cial Intelligence, Vol. 14, No. 1, 1980, pp. 263-313.
doi:10.1016/0004-3702(80)90051-X