International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
April 2013, pp.
ISSN: 2088-8708
GA and ACO Algorithms Applied to Optimizing Location of Controllers in Wireless Networks Dac-Nhuong Le Hanoi University of Science.
Vietnam National University.
Hanoi.
Vietnam
Article Info
ABSTRACT
Article history:
Optimizing location of controllers in wireless networks is an important problem in the cellular mobile networks designing.
In this paper.
I present two algorithms based on Genetic Algorithm (GA) and Ant Colony Optimization (ACO) to solve it.
In the first algorithm, my objective function is determined by the total distance based on finding maximum flow in a bipartite graph using Ford-Fulkerson algorithm.
In the second algorithm.
I generate pheromone matrix of ants and calculate the pheromone content of the path from controller i to base station j using the neighborhood includes only locations that have not been visited by ant k when it is at controller i.
each step of iterations.
I choose good solutions satisfying capacity constraints and update step by step to find the best solution depending on my cost I evaluate the performance of my algorithms to optimize location of controllers in wireless networks by comparing to SA.
SA-Greedy.
LBGreedy algorithm.
Numerical results show that my algorithms proposed have achieved much better more than other algorithms.
Received Feb 1, 2013 Revised Mar 18, 2013 Accepted Mar 26, 2013 Keyword:
Terminal Assignment Optimal Location of Controllers Problem (OLCP) Genetic Algorithm Ant Colony Optimization Wireless Networks Copyright A 2013 Institute of Advanced Engineering and Science.
All rights reserved.
Corresponding Author:
Dac-Nhuong Le.
Faculty of Information Technology.
Haiphong University 171 Phan Dang Luu.
Kien An.
HaiPhong.
Vietnam Email: Nhuongld@hus.
INTRODUCTION
In a mobile communication network designing, base stations placement optimization is very important for cheaper and better customer services.
This issue is related to the problems of location of devices (Base station (BTS).
Multiplexers.
Switches, etc.
) .
The objective of terminal assignment problem (TA) .
involves with determining minimum cost links to form a network by connecting a given collection of terminals to a given collection of concentrators.
The capacity requirement of each terminal is known and may vary from one terminal to another.
The capacity of concentrators and the cost of the link from each terminal to each concentrator is also known.
The problem is now to identify for each terminal the concentrator to which it should be assigned, under two constraints: Each terminal must be connected to one and only one of the concentrators, and the aggregate capacity requirement of the terminals connected to any concentrator must not exceed the capacity of that concentrator.
The assignment of BTSs to switches .
problem introduced in .
In which it is considered that both the BTSs and controllers of the network are already positioned, and its objective is to assign each BTSs to a controller, in such a way that a capacity constraint has to be fulfilled.
In this case, the objective function is formed by two terms: the sum of the distances from BTSs to the switches, and also there is another term related to handovers, between cells assigned to different switches which must be minimized.
The optimal location of controller problem (OLCP) .
is selecting N controllers out of M BTSs, in a way that the objective function given by solving the corresponding TA with N concentrators and M-N terminals is minimal.
Both TA and OLCP are NP-Hard optimization problems so heuristic approach is a good choice.
A Simulated Annealing (SA) algorithm tackled the assignment of cells to controller problem.
Journal homepage: http://iaesjournal.
com/online/index.
php/IJECE A ISSN:2088-8708 The results obtained are compared with a lower bound for the problem, and the authors show that their approach is able to obtain solutions very close to the problemAos lower bound .
SalcedoSanz et al in .
introduced a hybrid heuristic consisting of SA and Greedy algorithm to solve the OLCP problem.
In .
, authors proposed a hybrid heuristic based on mixing genetic algorithm (GA).
Tabu Search (TS) to solving the BTS-controller assignment problem in such a way that terminal is allocated to the closest concentrator if there is enough capacity to satisfy the requirement of the particular terminal.
In the latest paper .
I have proposed a new algorithm based on Particle Swarm Optimization (PSO) .
In this paper.
I proposed two algorithms based on GA and ACO algorithms.
In the first algorithm, my objective function is determined by the total distance based on finding maximum flow in a transport network using Ford-Fulkerson algorithm.
In the second algorithm.
I generate pheromone matrix of ants and calculate the pheromone content of the path from controller i to base station j using the neighborhood includes only locations that have not been visited by ant k when it is at controller i.
At each step of iterations.
I choose good solutions satisfies capacity constraints and update step by step to find the best solution depends on my cost function.
The experimental results show that my algorithms proposed have achieved much better performance and easy more than previous algorithms.
The rest of this paper is organized as follows.
Section 2 presents the problem formulation and briefly introduces the main idea of OCLP proposed in .
Section 3 and section 4 present my new algorithm for location of controllers in a mobile communication network based on GA and ACO algorithms.
Section 5 presents my simulation and analysis results, and finally, section 6 concludes the paper.
PROBLEM FORMULATION
Let us consider a mobile communication network formed by M nodes (BTS.
, where a set of N controllers must be positioning in order to manage the network traffic.
It is always fulfilled that N<M, and in the majority of cases N AA M .
I start from the premise that the existing BTSs infrastructure must be used to locate the switches, since it saves costs.
Thus, the OCLP consists of selecting N nodes out of the M which form the network, in order to locate in them N controllers.
To define an objective function for the OCLP.
I introduce a model for the problem, based on the Terminal Assignment Problem .
The Terminal Assignment Problem The TA .
can be defined as follows:
Problem instance:
l1 , l2 ,.
, lM A N Terminals:
Weights:
w1 , w2 ,.
, wM A N Concentrators: r1 , r2 ,.
, rN Capacities:
p1 , p2 ,.
, pN Where, wi is weight, or capacity requirement of terminal li.
The weights and capacities are positive integers wi A min A p1 , p2 ,.
, pN A .
Ai A 1, 2.
M A N
The terminals and concentrator are placed in the Euclidean grid, i.
, li has coordinates .
i1, li.
and rj has is located at .
j1, rj.
Feasible solution: Assign each terminal to one of concentrator such that no concentrator exceeds its I use xI A A xI1 , xI2 ,.
, xIM A N A is a vector such that xIi A j means that terminal li has been assigned to concentrator rj, with xC is an integer such that 1 C xI C N .
Capacity of each concentrator must be satisfied:
Eu w A p , j A 1.
iEaR j Where.
R j A Ai | xIi A jA , i.
Rj represents the terminals that are assigned to concentrator rj.
Objective function: Find xC that minimizes:
M AN
F A xI A A Eu cost tij C min, j A 1, 2,.
i A1 IJECE Vol.
No.
April 2013: 221Ae229
IJECE
ISSN: 2088-8708
Where, cost tij A .
i1 A rj1 ) 2 A .
i 2 A rj 2 ) 2 is the distance between terminal li and concentrator rj.
It is important to note that in the standard definition of the TA, there is a major objective .
he minimization of the distances between terminals and concentrator.
, and a major constraint .
he capacity constraint of concentrator.
The Optimal Controller Location Problem The OCLPcomplete has to deal with two issues.
The first is selection of the N controllers in M nodes, and the second for each election, an associated TA.
This process can be seen in Figure 1.
Figure 1.
The Optimal Controller Location Problem Authors in .
used a Greedy algorithm to obtain this objective function that terminals are consequently allocated to the closest concentrator if there is enough capacity to satisfy the requirement of a particular terminal.
If the concentrator cannot handle the terminal, the algorithm searches for the next closest concentrator and performed the same evaluation.
The terminals are assigned to concentrators following the order in A A lM A N A - a random permutation of terminals.
That algorithm is called by SA-Greedy Quintero and S.
Pierre considered the following Lower Bound (LB) for the TA .
, as follows:
M AN
LB A Eu min A dik A i A1 The Lower Bound comes from the solution obtained by assigning each node i to the nearest controller k.
Hybrid Lower Bound- Greedy algorithm is called by LB-Greedy algorithm.
GENETIC ALGORITHM FOR THE OCLP
Initialization I consider configurations in the GA algorithm are sets of N nodes which will be evaluated as controller for the network.
The encoding of the configuration use a binary string with length M, say x A A x1 , x2 ,.
xM A where xi=1 in the binary string means that the corresponding node has been selected to be a controller, whereas xi=0 in the binary string means that the corresponding node is not a controller, but serve as BTS.
We must select N nodes to be the controllers of the network.
I use fully random initialization in order to initialize the individuals.
After the mutation, the individual x will have p 1s.
To ensure that all binary strings in individuals have exactly N 1s representing N controllers.
I present RepairIndividual functionas follows:
REPAIR INDIVIDUAL FUNCTION ALGORITHM
INPUT: The individual x A A x1 , x2 ,.
xM A has p 1s OUTPUT: The individualx will have exactly N 1s IFp<NTHEN Adds (N-.
1s in random positions ELSE Select .
-N) 1s randomly and removes them from the binary string
ENDIF
GA and ACO Algorithms Applied to Optimizing Location of Controllers in Wireless.
(Dac-Nhuong L.
A ISSN:2088-8708 Evaluation function After the mutation, each individual x has exactly N 1s representing N controllers.
Iwill construct a bipartite graph G A A I .
J .
E A corresponding individual x, where I A A1, 2,.
N A is the set of controllers.
J A A1, 2,.
M A N A is the set of BTSs and E is the set of edge connection between the controller ri and the BTS lj.
I find the maximum flow .
ax-flo.
of the bipartite graph G by adding two vertices S (Sourc.
and D (Destinatio.
is shown in Figure 2.
=1.
=1.
M-N)
c(S,r.
=pi c.
i,t.
=wj c.
i,D)=wi A A Figure 2.
The bipartite graph G = (I.
E) corresponding individual x The weight of the edges on the graph is defined as follows:
- The edges from vertex S to the controllers ri is capacity of riis c(S,r.
=pi, .
=1.
N).
- The edges from BTS lj to vertex D is weight of ljisc.
j,D)=wj, .
=1.
M-N).
- The edges from the controllers ri to the BTSs lj is c.
i,l.
=wi.
( A i , j A Ea E ) I find the max-flow satisfies capacity constraints given by the formula .
in graph G based on FordFulkerson algorithm .
The objective function is determined by the max-flow based on the total distance is given by:
N M AN
F A xA A Eu Eu i A1 j A1 i1 A l j1 ) 2 A .
i 2 A l j 2 ) 2 My Genetic Algorithm The pseudo-code of the GA algorithm using Ford-Fulkerson algorithm for the optimal location of controllers in a mobile communication network, as follows:
GENETIC ALGORITHM (GA)
BEGIN
INITIALISEpopulation with random candidate solutions.
REPAIR FUNCTION .
EVALUATEFUNCTION each candidate.
REPEAT
SELECT parents.
RECOMBINE pairs of parents.
MUTATION the resulting offspring.
REPAIR FUNCTION .
BUILD BIPARTITE GRAPH G = (I.
E).
FIND MAX_FLOW (G).
EVALUATE FUNCTION new candidates.
SELECT individuals for the next generation.
UNTIL (TERMINATION CONDICTION is satisfie.
END IJECE Vol.
No.
April 2013: 221Ae229
IJECE
ISSN: 2088-8708
ANT COLONY OPTIMIZATION FOR THE OCLP
Ant Colony Optimization The ACO algorithm is originated from ant behavior in the food searching.
When an ant travels through paths, from nest food location, it drops pheromone.
According to the pheromone concentration the other ants choose appropriate path.
The paths with the greatest pheromone concentration are the shortest ways to the food.
The optimization algorithm can be developed from such ant behavior.
The first ACO algorithm was the Ant System .
, and after then, other implementations of the algorithm have been developed .
Solving the OCLP based on ACO Similar GA algorithm above.
I use a binary string to encoding the ant k configuration, say k A A x1 , x2 ,.
xM A where xi=1 in the binary string means that the corresponding node has been selected to be a controller, whereas xi=0 in the binary string means that the corresponding node is not a controller, but serve as BTS.
We must select N nodes to be the controllers of the network.
I use fully random initialization in order to initialize the ant population.
After that, the ant k will have p 1s.
I present Ant_Repairfunction to ensure that all binary strings in ants have exactly N 1s representing N controllers.
In my case, the pheromone matrix is generated with matrix elements that represent a location for ant movement, and in the same time it is possible receiver location.
Each ant k has exactly N 1s representing N controllers is associated to one matrix.
ANT_REPAIR FUNCTION ALGORITHM
Input: The ant k A A x1 , x2 ,.
xM A has p 1s Output: The ant k will have exactly N 1s IF p<N THEN Adds (N-.
1s in random positions ELSE Select .
-N) 1s randomly and removes them from the binary string
ENDIF
I use real encoding to express an element of matrix Am*n .
here n is the number of controllers, m is number of BTS.
Each ant can move to any location according to the transition probability defined by:
pijk A A EEA ij EE EEA ij EE Eu EEA ij EE EEA ij EE l Ea N ik Where.
A ij is the pheromone content of the path from controller i to BTS j.
N ik is the neighborhood includes only locations that have not been visited by ant k when it is at controller i, ijis the desirability of BTS j, and it depends of optimization goal so it can be my cost function.
The influence of the pheromone concentration to the probability value is presented by the constant , while constant do the same for the desirability.
These constants are determined empirically and my values are =1, =10.
The ants deposit pheromone on the locations they visited according to the relation.
A new A A current A AEA kj Where AEA kj is the amount of pheromone that ant k exudes to the BTS j when it is going from controller i to BTS j.
This additional amount of pheromone is defined by:
AEA kj A .
In which, dij is the distance between controller i to BTS j is given by:
dij A .
i1 A l j1 ) 2 A .
i 2 A l j 2 ) 2 GA and ACO Algorithms Applied to Optimizing Location of Controllers in Wireless.
(Dac-Nhuong L.
A ISSN:2088-8708 The cost function for the ant k is the total distance between controllers to BTSs is given by:
N M AN
f k A Eu Eu .
i1 A l j1 ) 2 A .
i 2 A l j 2 ) 2 i A1 j A1 The stop condition I used in this paper is defined as the maximum number of interaction Nmax(Nmax is also a designed paramete.
The pseudo-code of ACO algorithm to solving OCLPas follows:
ACO Algorithm INITIALIZATION:
Algorithm parameters:A A 1.
A A 10 Ant population size: K.
Maximum number of iteration:NMax.
GENERATION:
Ant_Repair function .
:Ak Ea K .
Generating the pheromone matrix for the ant k.
Update the pheromone values and set x*=k.
i=1.
REPEAT
FORk = 1 TOKDO Computing the cost function for the ant k by the formula .
Computing probability move of ant individual by the formula .
IFf.
<f.
*)THEN Update the pheromone values by the formula .
Setx*=k.
ENDIF
ENDFOR
UNTILi>NMax EXPERIMENTS AND RESULTS The problems tackled In my experiments.
I have tackled several OCLP instances of different difficulty levels.
There are 10 OCLP instances with different values for N and M, and size networks shown in Table 1.
Table 1.
Main characteristic of the problems tackled Problem # Nodes (M) Controllers (N) Grid size 2 Parameters for the GA algorithm I have already defined my crossover probability as 0.
I will work with a population size of 500 and a mutation rate of pm = 1/m.
IJECE Vol.
No.
April 2013: 221Ae229
IJECE
ISSN: 2088-8708
Mygenetic algorithm to tackle these problems can be specified as below in Table 2.
Table 2.
Genetic algorithm specifications Representation Binary strings of length m Recombination One point crossover Recombination probability Mutation Each value inverted with independent probability pm per position Mutation probability pm Parent selection Best out of random two Survival selection Generational Population size Number of offspring Initialization Random Termination condition No improvement in last 100 generations Parameters for the ACO algorithm In my experiments.
I have already defined parameters for the ACO algorithm shown in Table 3.
Table 3.
The ACO algorithm specifications K = 100 Ant Population size Maximum number of interaction NMax = 500 Parameter =1, =10 4 Numerical Analysis I evaluate the performance of myalgorithms to optimize location of controllers in wireless networks by comparing to SA.
SA-Greedy.
LB-Greedy algorithm.
The experimental objective function results show in Table 4.
Table 4.
Results obtained in the OCLP instances tackled Prob.
SA-Greedy LB-Greedy ACO The results show that problems with the small grid size and small number of nodes such as problem #1, #2 and #3, all algorithms has approximate results.
However, when the problem size is large, the experimental results are considerable different such as problem #6, #7, #8, #9 and #10.
In some cases.
LB-Greedy.
SA-Greed.
GA and ACO algorithms choose the same set of nodes to be controllers, but the objective function results of GA or ACO are much better.
The results show that ACO has better properties compared to GA algorithm.
GA and ACO Algorithms Applied to Optimizing Location of Controllers in Wireless.
(Dac-Nhuong L.
A ISSN:2088-8708 Figure 3 shows the results of the simulator of solutions for the problem #4 given by SA.
SA-Greedy.
LB-Greedy.
GA and ACO algorithms.
Simulated Annealing .
SA-Greedy algorithm .
GA algorithm .
LB-Greedy algorithm .
ACO algorithm Figure 3.
Solutions for the problem #4 given by SA.
SA-Greedy.
LB-Greedy.
GA and ACO algorithms CONCLUSION AND FUTURE WORK In this paper.
Ih ave proposed two new algorithms based on Evolutionary Algorithm and Ant Colony Optimization for the optimal location of controllers in wireless networks, which is an important problem in the process of mobile communication network designing.
In the first algorithm, my objective function is determined by the total distance based on finding maximum flow in a bipartite graphusing FordFulkerson algorithm.
In the second algorithm.
I generate pheromone matrix of ants and calculate the pheromone content of the path from controller i to base station j using the neighborhood includes only locations that have not been visited by ant k when it is at controller i.
At each step of iterations.
I choose good solutions satisfies capacity constraints and update step by step to find the best solution depends on my cost I evaluate the performance of my algorithms to optimize location of controllers in wireless networks by comparing to SA.
SA-Greedy.
LB-Greedy algorithm.
Numerical results show that my algorithms proposed have achieved much better more than other algorithms.
Optimizing location of controllers in wireless networks with profit, coverage area and throughput maximization is my next research goal.
REFERENCES