Improving Genetic Algorithm to Solve Multi-objectives Optimal of Upgrading Infrastructure in NGWN

Published Online November 2013 in MECS

The Next Generation Wireless Networks (NGWNs) are expected to provide high data rate and optimized quality of service to multimedia and real-time applications over the Internet Protocol networks to anybody, anywhere, and anytime. The wireless network infrastructure consists of equipment required by mobile network operators to enable mobile telephony calls or to connect fix subscribers by radio technology. The interacting layers architecture of next generation wireless network is shown in Fig.1.

The PSTN-cloud covers all network elements to make a standard telephone call, while the data network cloud includes the Internet, Intranets, and other IP based networks [1]. The architectural building blocks enabling mobile telephony are:

• •    The core network : comprised of the mobile switching centers (MSC), the packet data serving nodes (PDSN), and home agents (HA), and

• •    The base station subsystem (BSS) also known as the radio access network, consisting of base station controllers (BSC), base transceiver stations (BS), and mobile stations (MS).

Fig. 1: The next generation wireless network infrastructure

Corresponding to the architectural building blocks of a wireless network, are three types of interconnects [2]. These are (1) mobile device to BS interconnect, which includes both forward and reverse radio links, (2) the BS to BSC interconnect, which is called the backhaul, and (3) BSC to MSC interconnect. The known hierarchical capacitated concentrator location problem, which is an extension of the concentrator location problem to multiple levels and a classical research issue in the telecommunications literature [3-6]. In [7], the authors studied the base station location and service assignment problem in a W-CDMA. A greedy strategy to optimal positioning of BSs for cellular radio networks and capacity planning of UMTS networks studied in [8-9]. A Tabu search and Genetic algorithm approach to cellular capacity expansion to maximizing the coverage area and minimizing the number of transmitters is presented in [10-11]. Yu et al in [12] proposed a set covering algorithm for given traffic and finding optimal solution configuration in a CDMA network. An alternate approach to capacity planning and expansion is introduced for 3G network system capacity without an increase in BSs using a cell splitting approach [13].

In latest papers [14-18], I have proposed a novel Particle Swarm Optimization and Ant Colony Optimization and Genetic algorithms to optimal location of controllers in wireless networks and centralized wireless access network. In this paper, I focus on the Multi-Objectives Optimization of Upgrading Infrastructure (MOOUI) in NGWN and propose a new Genetic algorithm to solve it. The rest of this paper is organized as follows: Section 2 presents the MOOUI problem formulation. Section 3 presents my new algorithm to solve it based on GA algorithm. Section 4 is my simulation and analysis results, and finally, section 5 concludes the paper.

• II.    Problem Formulation

In this section, I assume that network topology has m mobile users, n base stations, and p base station controllers. I introduce the following notation:

Table 1: Notation definition

Notation	Meaning
M	Index set of Mobile user locations: M = { MS i , V i = 1.. m }
N	Index set of all Base Station (BS): N = N 1 О N 2 = { BS;, V j = 1.. n } N 1: Index set of existing BS; N 2: Index set of potential BS
P	Index set of Base Station Controllers (BSC): P = P1 О P 2 = { BSCk , V k = 1.. p } P 1: Index set of existing BSC; P 2: Index set of potential BSC
T j	Set of types available for BS , V j' e N
S	[ 1 if commonditytypeisvoice Set of commodity types: s = 1 | 2 if commonditytypeisdata
Nt	Index set of all BS of type t. N , = N 1 , 0 N 2 ,
Ds i	Demand of commodity type s for mobile user MS , , V i e M
MaxBS _ Cap	Maximum capacity of BS, of type t , V j e N , .
MaxBSC _ Cap	Maximum capacity of BSCk , V k e P
dij t	Distance of mobile user MS, from BS ^ of type t V i e M , V j e Nt
MaxBS _ Cov jt	Maximum coverage range for BS of type t
cost_connect	Cost of connecting BS of type t to BSCk
cost_install	Cost of installing BSC k , V k e P 2
cost_upgrade	Per channel cost of upgrading BS^ , V j' e N 1
cost_setup	Cost of constructing and connecting BS,, V j' e N 2

The MOOUI problem in NGWN has two steps the initial assignment of MSs to BS and the connection of BS to BSC and capacity expansion and traffic increase with constraint specifies that:

• •    Each mobile user MS i will be assigned to exactly one base station BS j of type t

• •    Mobile users are within that base stations’ maximum range MaxBS _ Cov

• •    At most one base station of type t can exist at location j

• •    if a base station BS j is operated, it has to be connected to a BSC k and the BSC has to be active.

The capacity constraints of the model, in which we argue that BSs must have the necessary capacity to accommodate traffic demand of all demand types s for all MSs assigned to it and the BSC must have the necessary capacity to accommodate all BSs assigned to it.

Fig. 2: The Initial Assignment step with indicator variables

In the first step, I use the indicator variables are:

⁸ k =1 1

if BSC isoperatedininitialassigment 0 otherwise

«3,

1 if BS of type t is operated 0 otherwise

в 3k =

Fig.2 shows an example of an existing initial assignment that each mobile user can be assigned to only one BS, while each BS has to be connected to a single BSC.

1 if BS oftype t isconnectedto BSC 0 otherwise

Fig. 3: The assignment after capacity expansion and traffic increase with decision variables

In the second step, I use the decision variables are:

[ 1 if mobile user MS, is connected to BS, X,, = ^                          i                      j

^J'   I 0 otherwise

J 1 if BSj of type ‘ is connected to BSC_k k I 0 otherwise

J 1 if BSj of type t isoperated j I 0 otherwise

J 1 if BSC_k isoperated ^k I 0 otherwise

Fig.3 illustrates an assignment after capacity expansion and traffic increase, and indicates the respective decision variables. New wireless BSS infrastructure equipment with BS and BSC in red shades.

The objective of MOOUI is to minimize the total cost of expanding an initial wireless BSS to accommodate increased traffic demand. The MOOUI problem can be defined as follows:

np

Min ( ZZZ cost_connect_№ ( Y,, - p j, )

J = 1 k = 1 t e T

+ Z cost_install _k ( W_k - 3 _k )

k e P₂

+ Z cost upgrade , I Z MaxBS _ cap_jt ( Z_jt - a j e N ।                       ( t e Tj

+ zzcost_setup Z ) j e N2 ‘ e Tj‘ '

Subject to:

n

ZZXj. = 1, Vi = 1..m(9)

J=1 ‘ eTj djjXji < MaxCovZ, V i = 1.. m, J = 1.. n, t e T (10) ij      ijt                                jt     jtj

Z Zj, <  1, V J = 1.. n ‘ e T j	(11)
Z <1 z Y Jk , V J = i.7n , t e T j k = 1	(12)
YJ k <  W k , V k = 1.. p , J = 1.. n , t e T j	(13)

ZZZDjXj

i=1 s=1            ‘                                    ‘‘

ZZ Z Yj.k < MaxBSC _ Cap, x Wfc, Vk = 1..P(15)

J=1 t eTj‘

X_y. e{0,1}, Yjtk e{^0,1},

Zj e{0,1}, Wk e{0,1}

V i = 1.. m ,j' = 1.. n, k = 1.. p, t e T

• III.    A New Genetic Algorithm for the MOOUI

• A.    Represent and decode an individual

In this section, I present a new genetic algorithm for the MOOUI problem with two populations POP and POP .

• •    The encoding of the POP_X configuration is by means of matrix X = (xj )n_xm ,  (i = 1..n,J' = 1..m) where

xi =1 means that mobile user MSi has been connected to base station BS , and otherwise, xi =0.

• •    The encoding of the POPY configuration is by means of matrix Y = (y _jk )mp, (j' = 1..m, k = 1..p) , where y k=1 means that base station BS has been connected to base station controller BSCk, and otherwise, y k=0.

• B.    Initialization

I use fully random initialization in order to initialize the individuals POP ensure that the individual x satisfies constraints in (9)(10)(14) and (16). Each individual x, I fully random initialization in order to initialize the individuals POP ensure that the individual y satisfies constraints in (12)(13)(15) and (16).

• C.    Crossover Operator

This operator minics the mating process in the nature. To do crossover in POP , two individuals are picked first and two integer numbers (i, )(crossover point is xi ) are generated randomly between [1,n] and [1,m] (where n is number of MSs and m is number of BSs). Then the offspring is generated by interchanging the second halves of its parent, as illustrated in Fig.4.

In the crossover stage, the algorithm examines all pairs of individuals. It begins with the pairs that include the individual with a higher fitness value until the population size becomes twice of the original size. Similar, I apply crossover operator to POP .

Parents

\

x

x

x

x x20

x₂₁

x10

x_i0

V

Childrent

I xn 0

x_n0

nm )

г nm

n

N0

Fig. 4: An example of crossover operator for population POP_X

nm

• D.    Mutation Operator

The mutation operation is one kind of random change in the individual of POP_X . In my algorithm, pointwise mutation is adopted, in which one gene in the individual is changed with a certain probability, referred to as the mutation probability. This operator allows the algorithm to search for new and more feasible individuals in new corners of the solution spaces. To do mutation, an individual is randomly selected from the BS and the selected BS is called the mutation point, as illustrated in Fig.5.

		Parents					Ch ldrent
x10	x11	x1j	■•  x1 m '		r x10	x11	x1j	x1 m
x 20	x21	x2j	x2m		x 20	x21	x2j	x 2 m
				^
x0	x1	...   xj = r •■	x m		x0	x1	...  xj = r .	'-
I xn 0	xn0	xn0	xnm ,		< xn 0	xn0	xn0	xnm 1

Fig. 5: An example of mutation operator for population POP

The mutation stage is implemented until either population size becomes twice of the original size or all individuals in the current generation are examined. Similar, I apply mutation operator to POP .

F. My GA algorithm proposed

The pseudo-code of my algorithm as follows:

A NEW GENETIC ALGORITHM FOR THE MOOUI

BEGIN

INITIALISE population POP_X with random candidate solutions;

REPEAT

• 1.    SELECT parents in POP_X ;

• 2.    RECOMBINE pairs of parents in POP ;

• 3.    CROSSOVER the resulting offspring in POP_X ;

• 4.    MUTATION the resulting offspring in POP_X ;

• 5.    FOR each each candidate x e POP_X DO

  • 5.1    INITIALISE

• 5.2.    SELECT parents in POP_Y ;

• 5.3.    RECOMBINE pairs of parents in POP_Y ;

• 5.4.    CROSSOVER the resulting offspring in POP_Y ;

• 5.5.    MUTATION the resulting offspring in POP_Y ;

• 5.6.    COMBINE Solution

• 6.    EVALUATE FUNCTION new solutions s by formula (8);

• 7.    SELECT individuals x for the next generation;

Population POP_Y with random candidate

Solutions y e POP follows candidate x e POP_X ;

s = {(x, y) | x e POP, y e POP }

UNTIL (TERMINATION CONDICTION is satisfied)

END

• IV. Experiments and Results

• A. Simulation Conditions

In the simulation, I have tackled several MOOUI instances of different difficulty levels. There are 10 MOOUI instances with values for M, N and P shown in Table II. I have already defined parameters GA algorithm to tackle these problems can be specified as below in Table III.

• E.    Evaluation function

After the mutation, each solution s = {(x,y) | x e POPx ,y e POPy } is satisfies constraints in (9)-(16). The cost function of solution s computed by formula (8).

Table 2: Main characteristic of the problems tackled

		Base Stations				Base Stations Controllers
Problem #	Mobile Users (M)	N	N1	N2	Types	P	P1	P2	Types
(1)	10	4	3	1	1	3	2	1	1
(2)	20	5	3	2	2	4	3	1	2
(3)	30	6	3	3	3	4	2	2	3
(4)	40	7	3	4	3	5	2	3	3
(5)	50	10	6	4	3	5	2	3	3
(6)	60	15	10	5	4	10	5	5	4
(7)	70	15	8	7	4	10	6	4	4
(8)	80	20	10	10	5	15	10	5	5
(9)	90	25	15	10	7	15	8	7	6
(10)	150	40	20	20	10	20	10	10	7

Table 3: The GA Algorithm Specifications

Representation	Matrix X = (Xj ) nxm , Y = (yjk )„xp
Recombination	One point crossover
Recombination probability	70%
Mutation	Each value inverted with independent probability pm per position
Mutation probability	Pm = V m
Parent selection	Best out of random two
Survival selection	Generational
Population size	POPX= POP = 500
Number of offspring	500
Initialization	Random
Termination condition	No improvement in last 100 generations

• B.    Numerical Analysis

I evaluate the performance of my algorithms to optimize of capacity expansion with multi-objectives.

The experiment was conducted on Genuine Intel® CPU Duo Core 3.0 GHz, 2 GB of RAM machine. I ran experiment GA algorithm implemented using C language.

Fig. 6: Comparing value of capacity expansion in the MOOUI instances tackle

Comparing values of objective function between initial solution and optimal solution shown in Fig.6 with Population size POPX=POPY=500 and termination condition is 100 generations. Fig.7 shown time processing of MOOUI instances tackle.

Fig. 7: Time processing MOOUI instances tackle

The results show that problems with the small number of M, N, P such as problem #1, #2, #3, #4 and #5, algorithm has approximate optimal results fast with small interactions. However, when the problem size is large, the optimal results may be slower such as problem #6, #7, #8, #9 and #10. Convergence speed is not the same and depend on the distribution of parameters data. Fig.8 show an existing initial assignment of problem #3.

MS20

MS14

MS4

MS10

BS3

;MS19

MS3

BS4

BSC2

MS27

MS18

MS25

MS13

MS12.

MS8

BS2 '

MS11

в MS1 =(6.12,10.66)

3 MS2 = (6.84, 5.62)

3 MS3 = (13.76, 9.46)

3 MS4 = (11.19, 9.98)

3 MS5 = (8.92,9.38)

3 MS6 = (6.86,6.55) Э М57 = (8, 6) 3 MS8 = (8.34,3.7) 3 MS9 = (9.52,7.26) 3 MS10 = (5.66, 9.66} Э MS11 =(12.24,9.62) 3 MS12 = (8.98, 345} 3 MS13 = (7.18,4.3) 3 MS14 = (10.22,10.48) Э MS15 = (6.5,8.29) 3 MS16 = (11.34,11.53) . 3 MS17 = (5.53, 8.12)

3 MS18 = (12.06,6.53) J MS19 = (843, 8.72) 3 MS20 = (7.32,11.26) 3 WS21 = (9.8,4.02) 3 MS22 = (13.42,10.7) 3 MS23 = (9.28, 6.24) 3 MS24 = (10.14, 6.12) 3 MS25 = (7.14, 4.84} 3 MS26 = (9.83,8.27) 3 MS27 = (10.57,742} 3 MS28 = (11.14,6.4) 3 MS29 = (10.99,5.02) 3 MS30 = (7.02,7.46}

3 BS1 =(6.38,7.63)

3 BS2 = (11.83,10.62)

3 BS3 = (6.78,9.32) J BS4 = (11.14, 8.28) J BS5 = (10.12, 6.7}

3 BS6 = (8.64,4.92)

8 BSC1 =(5.64,5.74)

3 BSC2 = (12.85,74} J BSC3 = (10.06, 11.16} J BSC4 = (8.3, 7.27)

•. MS22

BSC3 eMS16

MS17Z

• №15'

MS30

вйс) / иву .(Й82" " Л

......... ESC4

ms6

MS5

MS28

X „ I , ; MS29 iBs6xMS21 -

/ -X>*. MS-24

MS26

MS9

MS1

Fig. 8: An existing initial assignment of problem #3

In which, there are three types of base station are:

• • Type 1: (BS1,BS6)

• • Type 2: (BS2,BS3)

• • Type 3: (BS4,BS5)

• •    BS2, BS3 BSC2, BSC4 are existing BSCs;

• • BSC1, BSC3 are potential BSCs;

• •    BS3, BS4, BS6 are existing BSs;

• •    BS1, BS2, BS5 are potential BSs.

• •    MS6, MS16, MS22, MS29 are not connected.

Fig.9 show an optimal solution with BSC2 is replaced by BSC3, BS4 is replaced by BS2 and BS5. BS1 is added and connect to BSC4. Red edges are replace connections and black edges are existing connections.

Fig. 9: An optimal capacity expansion of problem #3

To evaluation the effect of population size and number of iterations to the value of the objective function. I consider the problem #3 with the iterations can vary from 100 to 500 and fixed population size is 500, comparing results are shown in Fig.10 and Fig.11.

Fig. 10: Comparing objective function values of pro.#3 with different number of interactions

Fig. 11: Comparing time processing of problem #3 with different number of interactions

To comparing the problem #3 with the population size can vary from 500 to 1000 and fixed iterations size is 100, comparing results are shown in Fig.12 and Fig.13.

110.00     115.00     120.00     125.00     130.00     135.00     140.00     145.00

Objective function values

Fig. 12: Comparing objective function values of problem #3 with different population size

Fig. 13: Comparing time processing of problem #3 with different population size

The experimental results show that the algorithm can be implemented with the big number of interactions and large population size in polynomial time. From this result, I confirmed that this is a promising approach to solve this problem.

• C.    Applied to planning of upgrade infrastructure in telecommunication networks in Haiphong city

Haiphong is a city located on the edge of the Red River in Vietnam. Also known as the ‘city of flame flowers’, it is a beautiful city and a major industrial and commercial hub. Home to a populace of about 1,600,000 people, Haiphong is the third most populated city in Vietnam. According to Strategies to development Post and Telecommunications in City Haiphong from 2009 to 2020 of Department of Information Communication   [21-22],   switching network in Haiphong most use the system switchboards switched channels as task switching local voice traffic. In addition, NGWN is in the process to deploy converged voice networks, data and fixed networks, mobile networks into a common, provide new services based on NGN for subscribe on the city. Present in the Haiphong city area has 06 mobile suppliers networking:

• (1)    Vinaphone network of telecommunications services company GPC construction and management. Existing network has a mobile switchboard and 110 mobile stations broadcasting, mainly installed using common infrastructure and management  with

stations of Telecommunications Institute Haiphong.

• (2)    MobiFone network of Mobile Information Center 5th build and manage, the network currently has 94 stations broadcasting mobile. Mainly been installed at stations telecommunications, postal districts, individual organizations on City area.

• (3)    Viettel Mobile Network of Viettel Telecom build, manage and organize the business in the city. Existing network has 260 stations broadcast mobile revenue, mainly installed at the organizations and individuals in the city.

• (4)    EMobile Network of Telecommunications and Information Power Company build and manage. Existing network has 79 stations broadcasting on mobile city.

• (5)    SFone Network by ST telecom (units of SPT) to build and manage. Existing network has 42 stations broadcasting on mobile city. Installed at the post office districts and othe organizations or individuals in the area.

• (6)    HT-Mobile Networks by Hanoi communications Joint Stock Company construction and management. Network has 19 mobile stations on the city installed at post offices and other organizations and individuals in the area. HT-Mobile has currently switching technology, from CDMA technology to GSM technology and renamed as Vietnam Mobile brand.

Current status using common infrastructure mobile network (using the common antenna system column, etc), home station on the city quite limited. Local payment of only about 50 points below the general use of the network infrastructures between the mobile business (mainly between Mobilephone and Vinaphone installed in telecommunication stations, the postal districts in the center). Internet in the Haiphong city was build up by four companies and providers service: VNPT Haiphong Telecommunication, Viettel, EVN and FPT. Total Internet subscribers in the city in 2007

reached 39,197 subscribers, 2.14 densities (subscribers per 100 people). Up to this point, currently 200 access points (Hub and DSLAM) has been installed in the city. Haiphong Telecommunications: installing 200 access points (DSLAM). Total installed capacity of 68,150 ports, capacity to use port 50,586. FPT: 14 Hub installations, the total installed capacity of 4296 port, use port 3440. There are also access points of Viettel and EVN. Current status of internet in the city has widely developed: 110/143 far provided broadband Internet service; All district centers that provide broadband Internet. Other area suburban districts: Due to economic conditions, terrain conditions or by the need to use the service activity, a number of remote area not provided service of broadband internet access.

I have applied the proposed algorithm to optimize the cost of upgrading infrastructure in telecommunication networks in Haiphong city based on current infrastructure. My goal is built plan towards achieving service radius as required in the district for minimum the cost of upgrading and investment. Experimental data used in multi-objective optimization cost upgrade network infrastructure with current allocations of mobile stations and internet network access points in Haiphong City are given in Table IV.

Table 4: Experimental data used to upgrading network infrastructure in Haiphong city

Ord	District	Number of Access Point	Total Stations	Vina phone	Mobile phone	Viettel	HT Moble	EVN	SFone	Service radius Average
1	Ngo Quyen	53	64	16	13	24	2	6	3	0.14
2	Le Chan	39	63	11	9	25	2	9	7	0.25
3	Hong Bang	32	47	7	10	16	2	6	6	0.31
4	Kien An	7	32	5	4	13	2	5	3	0.54
5	Hai An	11	45	5	9	21	1	6	3	0.86
6	Duong kinh	5	14	4	2	5	0	2	1	1.02
7	Do Son	5	32	8	3	12	2	5	2	0.65
8	An Duong	15	45	9	6	18	1	7	4	0.83
9	An Lao	12	32	5	5	16	1	4	1	1.07
10	Cat Hai	3	40	8	4	21	1	4	2	1.60
11	Kien Thuy	6	29	6	4	12	2	3	2	1.09
12	Thuy Nguyen	15	80	14	15	32	2	12	5	0.98
13	Tien Lang	4	41	5	5	23	1	5	2	1.21
14	Vinh Bao	6	38	6	5	21	0	5	1	1.23
15	Bach Long Vi	1	2	1	0	1	0	0	0	0.71
	Total	214	604	110	94	260	19	79	42	0.90

V. Conclusions

In this paper, I propose a new genetic algorithm based on a combination of two populations to solve multi-objective optimization infrastructure upgrade problem in NGWN. My network topology model has two levels in which mobile users are sources and both base stations and base station controllers are concentrators with objective function is the costs of connection from sources to concentrators. The experimental results show that this approach is appropriate and effective. I have applied this algorithm to planning of upgrade infrastructure in telecommunication networks in Haiphong to towards achieving service radius as required in the district for minimum the cost of upgrading and investment.