International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1971
ISSN 2229-5518
Anil Goyal, Shiv Krishan Joshi ,Surbhi Gupta
Abstract--This paper deals with a design problem for a network of Mobile Communication Services (MCN). The goal is to assign cells to switches in a MCS Network in an efficient manner .It is a NP-Hard problem. W e consider three types of costs. One is the cost of handoff between cells. The other is the cost of cabling or trunking between a cell and its associated switch. The third cost is switching cost which includes the cost for transferring a call to other switch. The problem is constrained by the capacity of switch and assignment of a cell to a unique switch. Firefly algorithm is implemented in this paper along with heuristics method to solve the problem of assignment of cells to switches and results are compared with that of Particle Swarm Optimization and Firefly Algorithm.
Index Terms-- Cell to switch assignment, Firefly algorithm, Heuristics, MCS, Particle swarm optimization, Optimization.
————————————————————
ince the last decades, there have been significant advances in the development of mobile communication systems. Now a day the mobile networks are migrating towards broadband services based on high speed wireless access technologies [1]. Even though significant improvement to communication infrastructure has been aimed in the mobile industry, the issues concerning the assignment of cells to switches in order to minimize the cabling cost, handoff cost and switching cost in a reasonable time still remain challenging. The same problem is addressed in this paper. Our motive is to minimize three costs namely: cabling cost, handoff cost and switching cost. Cabling cost involves the consumption of resources while maintaining communication
link between two users [2].
The handoff caused by a subscriber movement from one cell to another, involves not only the modification of the location of the subscriber in the database but also the
————————————————
Anil Goyal is currently pursuing master’s degree program in electronics
engineering in PEC University of Technology, India. E-mail:
Shiv Krishan Joshi is currently pursuing master’s degree program in
electronics engineering in PEC University of Technology, India. E-mail:
Surbhi Gupta is currently pursuing master’s degree program in
electronics engineering in PEC University of Technology, India. E-mail:
execution of a fairly complicated protocol between switches
Switch1 and Switch2 as shown in fig.1.The handoff cost
between cell A and cell B is less because it involves only Switch1 and also the handoff is simple while handoff between cell A and cell C is complex and the handoff cost is also more as it involves two switches i.e. Switch1 and Switch2 Therefore, there are two types of handoffs, one involves only one switch and the other involves two switches. Intuitively, the cells among which the handoff frequency is high should be assigned to the same switch as far as possible to reduce the cost of handoffs. Merchant [3] gave a comprehensive description about handoffs. Switching cost occurs when two user which are communicating belong to different MSCs. However, since the call handling capacity of each switch is limited, this should be taken as a constraint. Incorporating the cabling cost, handoff cost and switching cost that occurs when a call is connected between a cell and a switch, we have an optimization problem[4], called the cell to switch assignment problem.
This paper presents idea to solve the problem of assignment of cells to switches using Firefly Algorithm given In 2008,byXin-She Yang [5] along with Heuristics method used by Bhaskar Sen Gupta in 1995 [3]. In next section the mathematical formulation has been done for this problem. In the next section it is shown how firefly algorithm and Heuristic method can be implemented for this problem.
The problem of assignment of cells to switches was first introduced by Arif Merchant and Bhaskar Sengupta [3] in
1995. The assignment of cell to the switches is an NP-Hard
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1972
ISSN 2229-5518
problem, having an exponential complexity (n cells and m switches). He introduced two types of costs namely handoff cost and cabling cost. He also proposed a heuristic method to solve this problem. Now in this paper another cost called Switching cost [6] is introduced which is the cost for transferring a call form one switch to another. Thus in this paper we have an optimization problem for minimizing the above costs which is stated as follows:
Assign all the cells in a geographical area to the available number of switches in order to minimize the total cost which is the sum of cabling cost, handoff cost and switching cost maintaining the following two constraints.
1) Each cell must be assigned to exactly one switch and
2) Each switch has some limited capacity and assignment of
cells must be done in such a way so that the total load on the switch should not exceed the capacity of the switch.
Fig1. Handoff from B to C is more expansive than B to A.
The assignment of cell to the switches is an NP-Hard problem, having an exponential complexity (n cells and m switches) [6].
• Let no. of cells be ‘ n’ and no. of switches be ‘m’
• hij – handoff cost between cell i and cell j
• cik – cabling cost between cell i and switch k
• dij – distance between cell i and switch (MSC) j
• Mk – call handling capacity of switch k
• λi - No of communication in cell i
• Yij – 1 if cell I and j are assigned to same switch and 0 otherwise.
• Xik – 1 if cell I is assigned to switch k and 0 otherwise.
1) Each cell must be assigned to exactly one switch
𝑚
� 𝑥𝑖𝑘 = 1, 1 ≤ 𝑖 ≤ 𝑚 … (1)
𝑘=1
2) Each switch has some capacity
𝑛
� 𝜆𝑖 𝑥𝑖𝑘 ≤ 𝑀𝑘 , 1 ≤ 𝑘 ≤ 𝑚 … (2)
𝑖=1
1) Total Cabling Cost: this is formulated as a function of distance between base station and switch and number of
calls that a cell can handle per unit time [8]. 𝑐𝑖𝑗 (𝜆𝑗 ) isthe
cost of
Fig 2: Mapping representation for CSA problem[7]
cabling per kilometre which is also modelled as a function of the number of calls that a cell can i handles as:
𝑐𝑖𝑗 = 𝐴𝑖𝑗 + 𝐵𝑖𝑗 𝜆𝑗 … (3)
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1973
ISSN 2229-5518
𝑚
� 𝑐𝑖𝑗 (𝜆𝑗 )𝑑𝑖𝑗 𝑥𝑖𝑗
𝑗=1
𝑓𝑜𝑟 𝑖
= 1,2, … 𝑛 … (4)
Total Cost: So our objective is to minimize the total cost which can be formed by the summation of all three costs. The objective function is given by:
2) Total handoff cost: we consider two types of handoffs,
𝑚
one which involves only one switch and another which
𝑛 𝑛
� 𝑐𝑖𝑗 (𝜆𝑗 )𝑑𝑖𝑗 𝑥𝑖𝑗 + � � ℎ𝑖𝑗 (1 − 𝑦𝑖𝑗 )
involves two switches. The handoff that occurs between
cells that belong to the same switch consume much less network resources than what occurs between cells that
belongs to two different switches.
𝑗=1
𝑖=1 𝑗=1
𝑚
+ � 𝛽𝑖 𝐹𝑖 (𝛽𝑖 )
𝑖=1
… (9)
𝑛 𝑛
� � ℎ𝑖𝑗 (1 − 𝑦𝑖𝑗 )
𝑖=1 𝑗=1
… (5)
Assigning cells to switches in cellular mobile network being an NP-hard problem and enumerative search methods are not appropriate to solve large sized instances of this problem There are various methods available for assigning cell
3) Total Switching Cost: let βi is the total no
of calls MSC i can handle per unit time and Fi (βi ) is the cost function of switching a call in MSC i.
Thus the load at MSC is given by:
𝑛
𝛽𝑖 = � 𝜆𝑗 𝑥𝑗𝑖 , 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖 = 1 … 𝑚 … (6)
𝑗=1
Fi (βi ) involves both the cost of switching and the cost of maintaining a call at MSC. Thus Fi (βi ) can be represented as:
𝐹𝑖 (𝛽𝑖 ) = 𝛼⁄(𝜇𝑖 − 𝛽𝑖 ) 𝛽𝑖 < 𝜇𝑖 … (7)
Where 𝜇𝑖 denote the call switching capacity of MSC i
and α is a constant.
The total switching cost involved is defined by:
𝑚
to switches like, heuristic approaches, like Genetic Algorithm
[4] [9], Ant Colony Optimization [10] and Particle Swarm
Optimization [11] have been developed for this kind of
problem. All these algorithms considered only cabling cost and handoff cost except [6] and [12] .
In this paper Firefly Algorithm[5] along with the Heuristic Method[3] is implemented and results are compared with Firefly Algorithm alone as used in[12] and with the
Particle Swarm Optimization as used in [11].
Firefly algorithm is developed by Xin-She Yang [5] in
2008 which is inspired by the mutual attraction of fireflies
based on the absorption of light and distance between two
fireflies. Algorithm considers that each firefly has fixed
position in the space and it always move towards a greater light source, then is his own.
Firefly algorithm idealizes some of the characteristics of the firefly behavior. They follow three rules:
1) All the fireflies are unisex,
2) Each firefly is attracted only to the fireflies, that are brighter
than itself; strength of the attractiveness is proportional to the firefly’s brightness, which attenuates over the distance; the brightest firefly moves randomly and,
3) Brightness of every firefly determines its quality of solution;
in most of the cases, it can be proportional to the objective
function.
� 𝛽𝑖 𝐹𝑖 (𝛽𝑖 )
𝑖=1
… (8)
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1974
ISSN 2229-5518
Heuristic Method is used to find out the best initial solution as given in[3] and we assign this best solution to one firefly and all other p-1 fireflies are assigned random values.
The steps for implementation of algorithm are as follows: Step 1
• Initialize the number of cells (n), switches (m) and number of fireflies (p) in the solution space.
• Initialize p-1 fireflies randomly and assign the initial best solution to one firefly as obtained by the Heuristic Method.
• Initialize position of cells and switches randomly in the search space.
• Calculate distance between each cell and switch. Step 2
• Generate the assigned matrix (xij ) for each firefly where each particle is between 0 and 1.
• The row of the matrix represents switches and column represents cells.
Step 3
• Obtain solution matrix from the assigned matrix by making the largest value of each column to 1 and all other are set to 0.
Step 4
• Calculate the total cost based on this solution matrix.
Step 5
• On the basis of this new cost the brightest firefly is found which has the minimum cost for the assignment.
• Now update the position of all other fireflies based on the attractiveness of best firefly and also on the basis of distance and randomness of fireflies.
• Now update the position of best firefly randomly.
• Repeat step 3 to 5 until stopping criterion is met.
To test the effectiveness of Firefly Algorithm for the cell assignment problem, we design and conduct a series of experiments. All the experiments are done using a MATLAB code for various cases of cells and switches for firefly algorithm. Regarding the test problems, we assume that the cells lie on a hexagonal grid of roughly equal dimensions in 2 dimensions. The parameters used for firefly algorithm are number of cells (n), number of switches (m) and number of fireflies (p).
Values of constants used are as follows:
• Randomness, α=1
• Absorption coefficient, β=1
• Brightness at source=1
The parameters used in the initialization of problem are:
• handoff cost between two cells= 0 to 14 per hour
• constant A used in cabling cost=1
• constant B used in cabling cost=0.001
• call handling capacity of a switch=98000
• constant α used in switching cost=40
• number of communication in a cell=0 to 200 per hour
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1975
ISSN 2229-5518
iterations is increased. The CPU time requirement is less in case of firefly algorithm as compared to PSO.
2. As the number of fireflies is increased in the solution space the probability of convergence to the global minima in comparatively lesser number of iterations is increased. But this will increase the complexity in the execution and CPU time requirement.
Motion of fireflies is best for the above values of α, β
and γ. For lesser values of these parameters the change in
250000
200000
150000
100000
50000
0
Total Cost Firefly + Heuristic Method
Total Cost
Firefly
Total Cost
PSO
the assignment is very low. As the number of cells and switches is increased the final cost value also increased and with these large problem instances it is taking more number of iterations and more time. We have conducted experiments to find the minimum total cost by repeating the experiments for
5, 10, 15 times for each set of parameters. These experiments
reveals that the optimum cost obtained in each execution is
always nearer to the average cost.
Table 6.1 shows the minimized cost for different cases of cells and switches. It also compare the minimized cost by the three algorithms: Firefly along with Heuristics Method, Firefly and PSO and from this list we can see that comparatively lesser cost is found using Firefly along with Heuristics Method and so it is better in terms of finding minimum cost. Form experiments it is noted that the total minimized cost can be reduced with larger number of iterations and also with larger number of fireflies.
From the experiments performed we can conclude that firefly algorithm along with Heuristics Method can be implemented successfully for the assignment of cells to the switches. The following conclusions can be drawn:
1. As the number of fireflies is increased the probability of finding the minimum cost and in less number of
200000
180000
160000
140000
120000
100000
80000
60000
40000
20000
0
2, 25 2,
100
2,
200
Total Cost Firefly + Heuristic Method
Total
Cost
Firefly
Total Cost PSO
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1976
ISSN 2229-5518
400000
350000
300000
250000
200000
150000
100000
50000
0
5, 25 5,
100
5,
200
Total Cost Firefly + Heuristic Method
Total Cost
Firefly
Total Cost
PSO
[3] Arif Merchant and BhaskarSengupta, Assignment of cells to switches in PCS network, IEEE Transections on Networking, Vol 3 No 5, pp 521-
526, Oct 1995.
[4] P. Bhattacharjee, D. Saha, A. Mukherjee, “Heuristics for Assignment of Cells to Switches in a PCSN: A Comparative Study”, Intl. Conf. on Personal Wireless Communications, Jaipur, India, 1999, pp. 331–334.
[5] Xin-She Yang, “Firefly Algorithm For Multimodal Optimization”,
Luniver Press, 2008.
450000
400000
350000
300000
250000
200000
150000
100000
50000
0
10,
25
10,
100
10,
200
Total Cost Firefly + Heuristic Method
Total Cost
Firefly
Total Cost
PSO
[6] Siba K. Udgata, U. Anuradha, G. Pawan Kumar, Gauri K. Udgata, Assignment of Cells to Switches in a Cellular Mobile Environment using Swarm Intelligence, IEEE International Conference on Information Technology, 2008, pp 189-194.
[7] Cassilda Maria RibeiroAníbal Tavares Azevedo Rodolfo Florence Teixeira Jr.,” Problem of Assignment Cells to Switches in a Cellular Mobile Network” via Beam Search Method, WSEAS TRANSACTIONS on COMMUNICATIONS,2010.
[8] ShxyongJianShyua, B.M.T. Linb, TsungShenHsiaoa, “Ant colony
[1] P. Bhattacharjee, D. Saha, A. Mukherjee, Heuristics for assignment of cells to switches in a pcsn: a comparative study:, Intl. Conf. on Personal Wireless Communications, Jaipur, India,1999, pp. 331-334.
[2] SyamMenon, Rakesh Gupta, Assigning cells to switches in cellular network by incorporating a pricing mechanism into simulated annealing, IEEE Transetions on system, men and cybernetics, Part B, Vol. 34, No. 1, pp. 558-565, Feb 2004.
optimization for the cell assignment problem in PCS networks”, march,
2005.
[9] T. Shigeyoshi, G. Ashish, Genetic Algorithm with a Robust Solution
Searching Scheme,IEEE Transections on Evolutionary Computation, pp.
201-208, 1997.
[10] Dorigo M, Maniezzo V, Colorni A, The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man and Cybernetics-Part B, Vol 26(1), pp. 29-41, 1996.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 1977
ISSN 2229-5518
[11] James Kennedy, Russell Eberhart Particle swarm optimization, Proc. IEEE Int'l. Conf. on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995, pp.1942-1948.
[12] Deepak Sharma, Rajesh Kumar and Shrikant , Assignment of Cellto Switches using Firefly Algorithm ,International Journal of Electronics and Communication Engineering & Technology (IJECET), October- December (2012), pp. 211-218
IJSER © 2013 http://www.ijser.org