Share This Article:

A Genetic Algorithm for Overall Designing and Planning of a Long Term Evolution Advanced Network

Abstract Full-Text HTML XML Download Download as PDF (Size:1343KB) PP. 355-370
DOI: 10.4236/ajor.2016.64033    1,391 Downloads   2,162 Views   Citations

ABSTRACT

In the mobile radio industry, planning is a fundamental step for the deployment and commissioning of a Telecom network. The proposed models are based on the technology and the focussed architecture. In this context, we introduce a comprehensive single-lens model for a fourth generation mobile network, Long Term Evolution Advanced Network (4G/LTE-A) technology which includes three sub assignments: cells in the core network. In the resolution, we propose an adaptation of the Genetic Evolutionary Algorithm for a global resolution. This is a combinatorial optimization problem that is considered as difficult. The use of this adaptive method does not necessarily lead to optimal solutions with the aim of reducing the convergence time towards a feasible solution.

1. Introduction

Since the advent of telecommunication networks; it is from the 90s that the mobile radio industry has experienced significant developments in terms of technology and subscriber. The success of wireless technologies and mobile communications has determined the existence of a variety of standards that allow users to access a range of services provided [1] . Each technology seeks to achieve a certain step, a certain type of customer with specific needs. If in the very first mobile network the service provided was that of voice only [2] [3] . The current trend is a diversity of applications and new services such as multimedia applications, voice over IP, IPTV and videoconference [4] . Integrating such services added to the explosive growth in subscribers in recent years led to increasing demand of bandwidth [5] . Long Term Evolution Advanced (LTE-A) standardised by ITU (Interna- tional Telecommunication Union) on October 2010 as Fourth Generation Mobile Network Technology defined by the 3GPP Consortium (The 3rd Generation Partnership Project) [6] [8] enables transparent management of high speed mobility compared to other previous technologies with high-speed, broadband coverage, low latency and high quality voice service management using a flat architecture all in IP (Internet Protocol) [7] - [9] . The deployment of this technology compatible with the 2G technology (GSM-GPRS) and 3G (UMTS) provides mode circuit-switched telephony. But the demand in terms of throughput related to the development of mobile terminals (smartphone, tablet, smartphone, …) [9] , forces mobile network operators to offer only packet-switched services by adopting LTE Advanced flat architecture based on an IP network [10] .

The LTE architecture, named Evolved Packet System (EPS) shown in Figure 1, consists of the Evolved Packet Core (EPC), which is the core network and the E-UTRAN for Evolved UMTS Terrestrial Radio network which is the access network. E-UTRAN is divided into cells. Each cell has a centralized base station called eNode-B which may be interconnected by X2 interface (optional). It is connected to the core network, the EPC, by the S1 interface precisely to the MME (Mobility Management Entity) in the control plane (Control) and the SGW (Serving GateWay) in the user plane (data plan). The essential functioning of the EPC is provided by three entities namely: MME, SGW and the access gateway to the data network (PGW: Packet data GateWay), S5 interface permits to interconnect S-GW and PGW equipment in the plans of control and data. In addition, we have two entities of the control plane, the flows regulation control function and pricing: (Policy Control and Charging Rules Function: PCRF), the entity contains the rules for modulating bandwidth and applying a pricing (depending on the time, the user’s credit and his subscription type) and the Home Subscriber Server (HSS) that is a central database containing customer information, location information of mobile, etc. [11] - [13] .

Planning a mobile network is to identify all the hardware and software of these systems, positions them, interconnect them and uses them optimally, respecting, among other things, a series of constraints linked to the quality of service [14] .

The network planning process is a complex issue both long and expensive which is performed before the networking service. To reduce the complexity, there is a multitude of proposed models in the literature, often subdivided into sub-problem and solved separately. The model concerning the allocation of cells to the core network switches has been most studied in 2G [15] - [17] and 3G [18] - [20] , the sub-problem in the access network [21] - [23] and the sub-problem of the core network [24] [25] . Other authors have proposed a sequential approach in different sub-problems that do not necessarily lead to a better solution.

Solving by sub-problem the planning process, the interactions between the different levels of the network are not taken onto account. Local optimization of the network is observed at the expense of other parts. St. Hilaire in [26] reports that there is an interest to conduct a comprehensive planning by integrating all sub-problems in a same model. This model takes into account all the aspects of the problem and provides fairly good results.

Figure 1. LTE network architecture with defined interfaces [12] .

Network planning based on the LTE will require new approaches taking into account the VoLTE (Voice over LTE) which enables to route the packet-switched telephony on IP in LTE network [10] . In this context, it should be developed new planning models that allow optimal deployment by reducing the link costs and costs of rotations due to the high mobility of users to facilitate a good transmission of data packets according to quality mechanisms of differentiated service between the core network of the Advanced 4G LTE network all IP and the mobile terminal.

There are four types of potential deployment architectures of the LTE-A technology core network (EPC) [8] (see Table 1).

The rest of the document is organized according to the following plan. We will first consider the different planning models in literature, and then the problem description followed of modelling and the implementation of the model. The presentations computational results will be analyzed. Finally, the conclusion and the presentation of the prospects for further work will conclude this document.

2. Related Work

The mobile network planning is the subject of intense research activity because of the expansion of technological standards.

In the literature, there are several planning models. They usually depend on three factors: technology, network architecture and finally the approach to solve the planning model in question.

For the first generation (1G), second-generation (2G) and third generation (3G) networks, a series of research conducted aimed in most cases to reduce equipment costs under the constraint of quality of service provided. The models are often subdivided into three problems in order to reduce the complexity.

- The sub-problem of cell planning [15] - [19] .

- The sub-problem of access network planning [21] - [23] .

- The sub-problem of core network planning [24] [25] .

However, some researchers have proposed comprehensive planning models in order to mathematically formalize the entire network by integrating all the problems raised under a unique model and fully resolved [26] .

Although researches on the design and 5G tests in laboratories are expanding when the first deployments of this technology are planned by 2020 [27] - [32] , it seems useful to clarify that it still is not officially defined in 2016. Not with standing researches on enhancing the deployment policy of the fourth generation networks (4G/LTE-A), which aims are to ensure high quality services, are ongoing.

The Long Term Evolution Advanced Technology is relatively new with a new engineering (provision of all services by the IP route or packet switching), many different approaches to planning LTE network are available in the literature Most planning models proposed deal largely with Access Network (E-UTRAN).

e.g. Zuozhou Li and Li Shudong, in [33] propose a model based primarily on the position of the base stations (eNode B) and their power allocation. For the allocation of the power base stations, they use the theory of cooperative games and Simulations demonstrate that it is convergence and improve the performance due to the update of power and interference price per iterate.

Kurt Majewski and Michael Koonert, in [34] maintains that planning an LTE network depends on the load calculation of a cell load and its capacity by the formula of Shannon -Hartley on the Uu air interface access network. To recall, the Shannon-Hartley theorem states the maximum speed at which information can be transmitted over a noisy communication channel.

Table 1. Potential deployment architectures [8] .

On the other hand, J. Gu. et al. in [35] propose a planning approach based on traffic using an iterative process of radio parameters such as transmission power and bandwidth of the system, and optimization settings as the inclination of the eNode B down and the distance between the selected locations sites.

In the same vein, Li et al. [36] propose sizing models based on bandwidth on the S1-U interface considering the amount of traffic generated and the number of users in a cell. The main objective is to minimize the cost of the network, while maintaining a certain level of quality of different services.

As for Jailani et al. [37] they realize a research study in Malaysia to collect data using the tool NPO (Network Performance Tool); In particular, they used meters and traffic indicators to conduct their study. The document provides an approach for sizing the LTE traffic on the basis of voice traffic during periods of high density to evaluate network performance. Unfortunately, the presented approach only deals with the voice traffic and other parameters such signalling, video or other applications are not considered.

In order to overcome the shortcomings in the models [35] - [37] mentioned above, Dababneh D. et al. [38] propose a planning model that can generate traffic profiles taking into account aspects such as realistic signalling in the control plane and bandwidth.

All previously listed planning models are for the radio access network including the traffic realized. However, some authors as S. Germine [39] proposes a hybrid model of planning an LTE network made of a UMTS third generation network (Universal Mobile Telecommunications System). This maxim model using the UMTS equipment in place while minimizing the costs associated with the addition of those constituting the 4G network. Though it is truly a major development in terms of technology, it does not offer the advantage of IP packet or channel switching telephony due to the presence in the model of the heart of the UMTS network offering the circuit switched voice

On the other hand Eunice A. et al. in [40] design a multi-objective model of global planning cells in core network of mobile networks fourth generation, but it is suitable for WiMax technology.

Also Xueyi L. et al. In [41] propose a multi-objective model adapted to a heterogeneous network of fourth generation 4G for planning base stations and fixed with an evolutionary algorithm of maximizing coverage and capacity base stations while minimizing costs links constituting the addition of base stations.

Pasandideh, MR and Marc St-Hilaire in [42] had the idea to put a new model of network planning wholly IP with a realistic traffic but it is only compatible with a third technology networks generation, namely UMTS.

Finally, Dababneh et al. [43] have recently proposed another automatic planning model of the core network (EPC) of an LTE network by minimizing a cost function composed of links of costs and interfaces and installation costs of the MME, SGW, PGW HSS and PCRF solved with CPLEX optimization.

Analysis of the work presented in the literature

As we have seen, there are various models developed to assist the planner in his decision making and minimize network costs. However, most of the models for 4G/LTE-A are not complete, they are treated separately by optimizing part of the network at the expense of others ignoring the interactions between the different parts of the network or whether they relate to another technology other than the Long Term Evolution Advanced.

In the current context where the deployment of this technology is underway in most countries around the world; And if we offered a comprehensive planning model that integrates all the parts of the problem since the cells in the heart network connections minimizing costs and operations due to handover to enable mobile operators to offer all the services there including voice packet switch?

In the following section, we will define the problem and the mathematical model.

3. Problem Definition

3.1. Analysis of the Problem

It is obvious that the deployment of the technology Long Term Evolution Advanced (LTE-A) requires a thorough study on the assessment of network performance (wide coverage, high speed, mobility management at high speed ...). These studies will allow better sizing operators of the network so that the constraints on the quality of service are met. This is most important with the convergence to an IP network while where all services are offered via a single support IP-based switching.

In this paper, we propose a comprehensive framework for planning a network 4G/LTE-A, otherwise, a planning cell in the heart network through the access network. It takes into account the principles of managing the mobility of users established in the specifications of technology Long Term Advanced. This model although complex to the advantage of offering a complete solution and has the advantage of preserving the interactions between different parts of the network. In the resolution, we will use the genetic evolutionary algorithm.

3.2. The Network Architecture

The 4G LTE-Advanced network is a flat network all IP. The geographical area is divided into small area called hexagonal cells, the centre of which is the eNode B which may be interconnected via the X2 interface, themselves connected to the SGW in the user plan (through the S1-U interface) and the control plan MME to the S1-MME interface. The SGW are connected to the MME in the control plan by the S11 interface and PGW user plan by the S5 interface. The PGW are connected to other external networks by SGi interface (Figure 2).

In this article, we propose a comprehensive planning model of LTE Advanced network architecture based on a “centralized control, distributed bearer” [8] fully resolved by considering three assignments in the user plane.

The functional entity centralized control of MME is responsible for:

-To treat signalling exchange between the handheld and the EPC;

-To establish a user session and select the SGW and PGW entities that will be used to implement the data transport channel during a query.

Thus we abstract equipment HSS and PCRF (Figure 1) for the following reason. This equipment though in the core network is located at a higher level and is entities of the control plane. Indeed, entities: eNode B, MME, SGW and PGW can communicate directly with each other without having to make round trips with top-level equipment. Moreover, they are not involved in the data transfer plan.

3.3. The Planning Problem

The problem of an Advanced LTE mobile network planning is a complex issue. However to make it affordable, it can be divided into three sub problems compared to three levels in the architecture of the network 4G/LTE-A of Figure 2: Cell planning, radio access network planning and core network planning.

-Cells planning is to interconnect the eNode B together with the X2 interface (optional). This sub problem is to minimize the total cost of the network by minimizing the costs of connection and costs associated with handoff operations;

-Planning the access network is to assign the eNode B to SGW through the S1-U interface in the data plan. This sub problem is to get a better latency (optimizing link costs between these two entities and reduce the costs of complex operations of handoff following a change of SGW);

-Core network planning is to interconnect the SGW to PGW through the S5 interface in the user plan (data plan). The objective of this sub-problem is protocol to reduce costs of network to enable reliable transmission of data packet transport IP over the whole network.

Figure 2. 4G/LTE-A network architecture.

4. Formulation of the Mathematics Model

4.1. Assumptions

To model our problem, the following assumptions about the network architecture must be considered:

The network consists of n eNode B installed in each one of the network cells, s SGW and pPGW which are respectively identified by the indices 1 to 3 so that:

- I = { 1 , 2 , 3 , , n } the set of eNode B.

- J = { 1 , 2 , 3 , , s } the set of SGW.

- K = { 1 , 2 , 3 , , p } the set of PGW.

- To each eNode B in the center of a cell is connected to a single SGW and can be interconnected with other eNode B in cells;

- Each is connected to a SGW and PGW one;

- Each SGW and PGW to a well determined capacity;

- The position of the eNode B, SGW and PGW are known;

- The total capacity of the links connected to an entity (SGW and PGW)cannot exceed the capacity of this entity (bit per second).

Finally, the problem of global planning is divided into three sub problems:

The interconnection of the eNode B among them, the assignment of the eNode B to PGW, and SGW assignment to PGW.

4.2. Mathematical Model

Consider the constant parameters:

C i i 11 : The link cost between eNode B i (i є I) and eNode B i' (i' є I) withi ≠ i'.

C i j 12 : The link between the eNode B i (i є I) and the SGWj (j є J).

C j k 23 : The link between the SGW j (j є J) and thePGW k (k є K).

h 11 i i : The cost ofhandoffoperation per unit time between the eNode B i and i' with no change of SGW.

h 11 i i : The cost of a handoff complex operation per unit of time report between the eNode B i and i' without SGW.

h 21 i i : The cost of single handoff operation per unit time between the eNode B i and i' involving a change of SGW.

h 21 i i : The cost of handoff complex operation per unit time between the eNode B i and i' involving a change of SGW.

Φ 11 i i = h 11 i i h 11 i i represents the reduced cost per unit of time of a complex handoff between two eNode B i and i' with SGW not changing.

Φ 21 i i j = h 21 i i h 21 i i represents the reduced cost per unit of time of a complex handoff between eNode B i and i' with a change of SGW.

ω 2 j : The maximum capacity of the entity SGW J in (bps: bit per second).

ω 3 k : The maximum capacity of the entity PGW k in (bps: bit per second).

γ 12 i j : The data volume supported by the interface S1 between the eNode B i and entity SGW j.

γ 23 j k : The data volume supported by the interface S5 between the entities SGW j and PGW k.

Consider the following decisions variables:

x 11 i i = { 1 if theeNodeB i ( i I ) isconnectedtotheeNodeB i ( i I ) et i i 0 otherwise

x 12 i j = { 1 if theeNodeB i ( i I ) isconnectedtoSGW j ( j J ) 0 otherwise

x 23 j k = { 1 if theentitySGW j ( j J ) isconnectedto theentityPGW k ( k K ) 0 otherwise

To better understand the cost incurred by a handoff operation with change of SGW, we define the following additional variables:

z 12 i i j and y 12 i i : representing the cost allocation of eNode B i I et i I au SGW j J .

So

z 12 i i j = x i j 12 x i j 12 ; i i ; i e t i I e t j J (1)

So that:

y 12 i i = j J z 12 i i j ; i i ; i e t i I e t j J , (2)

y 12 i i = { 1 iftheeNodeB i and i ( i i ) arebothconnectedtoonlyasingle andsame SGWamongthe j ( j J ) SGW 0 otherwise

The total cost of the objective function F is the sum of total depreciation costs of connections and reduced costs per unit time of the handoff operations throughout the network defined below:

F = i I i I i i c 11 i i x 11 i i + i I j J c 12 i j x 12 i j + j J k K c 23 j k x 23 j k + i I i I i ϕ 11 i i ( 1 x 11 i i ) + i I i I i i Φ 12 i i ( 1 y 12 i i ) (3)

Then it will minimize the cost function F defined in (3) under the following constraints:

§ The constraints on the uniqueness of the assignments:

- Each SGW is interconnected to one and a single other eNode B

i I x 11 i i = 1 ; i I (4)

- Each eNode B must be assigned to only one SGW

j J x 12 i j = 1 ; i I (5)

- Each SGW must be assigned to one PGW

k K x 23 j k = 1 ; j J (6)

§ The constraint on the ability of nodes (SGW and PGW)

The network is flat in IP. There is only one type of traffic flowing across the network. The data are carried by IP. The signalling messages in the MME control plane are not taken into account.

The constraints on the ability of these different nodes are defined below:

§ The Constraint on the ability of SGW: The amount of data coming from i eNode B should not exceed the capacity of SGW.

i I γ 12 i j x 12 i j ω 2 j ; j J (7)

§ The Constraint on the ability of PGW: The amount of data coming from j SGW does not exceed the capacity of the p PGW.

j J γ 23 j k x 23 j k ω 3 k ; k K (8)

§ Nonlinear constraints

Relation (1) is nonlinear. Therefore, the problem cannot be solved with traditional methods of linear programming. Thus Merchant and Senguptain [44] [45] proposed a set of equivalent stresses. So relation (1) is equivalent to:

z 12 i i j x 12 i j ; i i and i , i I ; j J (9)

z 12 i i j x 12 i j ; i i and i , i I ; j J (10)

z 12 i i j x 12 i j + x 12 i j 1 ; i i and i , i I ; j J (11)

z 12 i i j 0 with ( i i and i ; i I ) and j J (12)

Summary of the planning problem formulation

The proposed model is an objective function of cost minimization under the constraints:

- From the uniqueness of assignment between entities located at each level of the architecture;

- From SGW and PGW nodes Capacity in the data plane user of the core network.

Thus, we have:

Min F = i I i I i i c 11 i i x 11 i i + i I j J c 12 i j x 12 i j + j J k K c 23 j k x 23 j k + i I i I i ϕ 11 i i ( 1 x 11 i i ) + i I i I i i Φ 12 i i ( 1 y 12 i i ) (3)

i I x 11 i i = 1 ; i I (4)

j J x 12 i j = 1 ; i I (5)

k K x 23 j k = 1 ; j J (6)

i I γ 12 i j x 12 i j ω 2 j ; j J (7)

j J γ 23 j k x 23 j k ω 3 k ; k K (8)

z 12 i i j x 12 i j ; i i and i , i I ; j J (9)

z 12 i i j x 12 i j ; i i and i , i I ; j J (10)

z 12 i i j x 12 i j + x 12 i j 1 ; i i and i , i I ; j J (11)

z 12 i i j 0 with ( i i and i ; i I ) and j J (12)

(3) Reflects the objective function to minimize: The first three terms respectively represent, the total cost allocations between the eNode B in the cells, the total cost of the eNode B and SGW assignments in the access network and the total cost of the SGW and PGW assignments in the core network. The fourth and fifth terms respectively represent the reduced cost per unit of time of complex handoff without involvement of the SGW in the cells, and the reduced cost per unit of time of complex handoff with a change of SGW in the access network.

(4), (5) and (6) represent the constraints linked to the assignments uniqueness and we only successively have an eNode B that can only be interconnected to one and only one other eNode B in the cells, each eNode B should be assigned to one and only one SGW finally in the core network each SGW must be assigned to one and only one PGW. (7) and (8) impose the constraint on the capacity of PGW and SGW.

Finally constraints (9), (10), (11) and (12) are linearized to be equivalent to (1) to reduce the problem to an integer programming [44] [45] .

Despite the transmutations carried out, the problem of allocation in an LTE-A network is still quite complex to solve. In the following section, we study the complexity of the model established in (3) to show that it is more convenient to use a heuristic to solve our model to obtain a feasible solution close to the optimum in a reasonable computation time.

Complexity Study of the Planning Model

The study of the complexity of the mathematical model set up in (3) is influenced by the three (3) levels seen in the architecture and the numbers of equipment available (Figure 2).

Indeed, it’s about making a triple assignment, first the interconnection between eNode B in the cells, and then a sub allocation of eNode B in the sub SGW access network, and finally a sub allocation of SGW the PGW at the core network level. And by analyzing more closely the second sub assignment, with the eNode B to PGW in terms of data users plane in the access network, we notice that it is similar to the cell assignment problem to switches in work carried out for second generation mobile networks [44] [45] where the authors show the equivalence of this problem to the partitioning of graphs. Thus by analogy, each cell served by an eNode B will be considered a vertex of the graph. Transaction costs of handovers due to mobility of users between each pair of nodes represent, in this case, an arc connecting two vertexes of the graph. In fact, this assignment problem in this context belongs to the class of NP-hard problems that are well known in operational research: the transport problem or concentrator’s location [46] [47] and the partitioning of graphs [48] [49] . Their resolution by an enumerative method usually leads to an exponential growth of the execution time. We must exclude the use of an exact method.

In our case, we have in the first eNode B n sub assignment that we want to connect at the cell level, which will require an algorithm with exhaustive enumeration of combination analysis to solve part of the problem. Then we must also affect the eNode B n to SGW s in the sub access network, which will also focus on examining sn combinations, finally the assignment of s SGW top PGW at the core network level will also focus on examining another ps combinations. With this computing time which raises exponentially, we would not be able to find a solution in a reasonable time. On this basis, we concluded that we are faced with a hard-NP problem. Therefore, we search rather close to the optimum solution by developing heuristics or metaheuristics for its practical problem solving in a reasonable computing time.

Among the known heuristics, we have chosen the genetic algorithm approach presented in the next section.

5. Approach of Resolution by Genetic Algorithm

The genetic algorithm belongs to the class of evolutionary algorithms developed separately and almost simultaneously, by different scientists:

- The evolutionary programming (L. Fogel 1966) [50] ;

- Strategies of evolution (J. Rechenberg 1973) [51] ;

- Genetic algorithms (J. Holland 1975) [52] .

The objective is to obtain a feasible solution to an optimization problem when it cannot be solved with an exact method in a reasonable time. From 1990, these three fields have been grouped under the Anglo-Saxon term of Evolutionary Computation.

In our article, we treat genetic algorithms based on Neo-Darwinism that is the union of the theory of evolution and modern genetics. They are built on different techniques derived from it: crossing, mutation, selection...

5.1. Adaptation of the Genetic Algorithm Method

Genetic algorithms all follow the same principle [53] and the method used in this article is no exception. We distinguish a coding principle of the element of the population (chromosome), a creation phase of the initial population, an alteration phase of that population by genetic operators, an evaluation phase of each member of this population, selecting the best elements (based on the principle that only the best will be able to reproduce). Every generation is supposed to provide the most efficient components than previous generations.

Intuitively, a large population with a large number of generations must be able to lead to a more refined solution hoping that the last generation will contain the right solution, however, is not necessarily the best.

5.2. Coding of Chromosome

In our adaptation, we chose to make a non-binary coding of chromosomes [54] .

Each chromosome of the population defines a feasible solution of the problem

For example, for our case, assuming a network 7 eNode B, 4 SGW and PGW 3.

A representation of the chromosome in Figure 3 is a constituent of the population that defines a feasible solution of the problem considered.

Each chromosome being a configuration after three sub assignments would be:

- The length of the chains in the cells and the access network is equal to the number of eNode B because all eNode B should be interconnected and be assigned to the SGW.

- The length of the chains at the heart network is equal to the number of SGW because all the SGW must be assigned to PGW.

Thus, the length of the chromosome for our adaptation is equal to twice the number of eNode B added to the number of SGW.

Figure 3. Representation of a chromosome for a 7 eNode B, 4 SGW and 3 PGW network.

The reading of chromosomes is from left to right; so:

- The first bit of chromosome contains the number of an eNode B to which the eNode B 1 is connected.

- The eighth bit contains the number of a SGW which the eNode B 1 is assigned in the access network.

- The fifteenth bit contains the number of a PGW which is assigned a SGW in the heart network.

This configuration represents a given topology (one assignment scheme) and respects the constraints of single assignment but not the constraint on the ability of the switches (SGW and PGW).

5.3. Formation of the Initial Population

The first member of the initial population is that obtained when the three sub assignments are made according to the metric of the smallest Euclidean distance. When an entity to allocate (eNode B respectively SGW) is equidistant from two or more other entities (eNode B respectively PGW), is assigned to the first in the order specified by the problem. This first chromosome is created deterministically. The other elements (chromosomes) of the population are randomly created respecting the principle of non-duplication (each chromosome is unique). This principle ensures heterogeneity of the population, thus good coverage of space to explore.

The population size is fixed and must be inferior or equal to all possible assignments to maintain the principle of unduplicated population.

Therefore, they must verify the feasibility of each solution, that is to say, the constraint on the ability of the switches. Indeed, in every generation, the population must be made feasible solution after application of genetic operators so that the latest generation of the best contains chromosomes than those of previous generations.

5.4. Crossing Operator

The operation is to create two new solutions (children) exchanging one or more genes of two existing solutions (Parents).

To do so, we randomly generate an integer in each of the intervals:

-[1, number of eNode B], at the cell level and the access network.

-[1, number of SGW], in the core network.

These numbers will match the crossing position for the two selected parents’ chromosomes. Each crossing new solutions are created. The new solutions will be retained if they are feasible.

5.5. Mutation Operator

Mutation is the process whereby the value of a random gene in a chromosome is regenerated. This process occasionally occurs in a genetic algorithm. By randomly changing the value of a bit in a string, the mutation is useful to bring genetic material that would have been forgotten by operators of selection and breeding. This operator mutates, under a certain probability, elements of the population.

To do so, a mutation position is identified by randomly generating a positive integer in the following intervals:

-[1, number of eNode B], at the cell level and the access network.

-[1, number of SGW], in the core network.

Then, the variable corresponding to the selected position is randomly generated within the following ranges:

-[Min_N˚ eNode B, max_N˚ eNode B], at the cell level.

-[Min_N˚ SGW, max_N˚ SGW], in the access network.

-[Min_N˚ PGW, PGW max_N˚], in the core network.

NB: min_N˚ and max_N˚ are respectively the values that can take the various entities.

5.6. The Function to Be Optimized

A key element of the genetic algorithm is the evaluation function or fitness of the individual that is the cost of the network configuration it represents. It is on this basis rests the choice of candidates.

The evaluation is to determine whether the chromosomes meet the constraint on the ability of switches and to determine which has the lowest cost while respecting the constraint of capacity switches.

5.7. The Selection Operator

The objective of the selection operator is to build a new population from the population obtained after application of the mutation and crossover. Overall, we want to calculate a probability of selection for each individual of the population is even higher than the value of his fitness is good. The percentage is calculated for each chromosome compared to the total fitness.

The simplest way to define the probability of selection is to make it directly proportional to its fitness.

Let f(i) the value of the fitness of individual i (i = 1, 2...total pop). One can then define ps(i), the individual probability of selecting i, as follows:

p s ( i ) = f ( i ) k = 1 T o t a l _ p o p f ( k )

Once the selection probabilities are calculated for all individuals in the population, it remains to be using it to build the next population.

The generation number is set initially. In every generation a new population is created. The size of the population is kept for each generation. Figure 4 indicates the pseudo genetic code.

Figure 4. Genetic code pseudo of our adaptation.

By the same principle, starting from a population of initial solution (checking the capacity of the switches), propagation is by growing two individuals and is applied to the two individuals chosen generic operators: the crossing and mutation. Reproduction gives two children who are placed in the new population. Repeating playback until we have completed the new (the size of the population should remain constant).

Once reached, we replace the old population by the new one, and the process is repeated according to the number of generation set.

NB: In every generation, we save the best individual and at the end we chose the best.

6. Results

6.1. Experimentation Background

The performance of the adaptation of the genetic algorithm is based essentially on a good choice of its parameters. In the absence of actual data, our experiment was performed by considering a number of tests generated by a Matlab program.

We will make considerations as in some previous work. The cost of link between the various entities is proportional to the distance separating them, with a coefficient of proportionality equal to unity [44] [45] .

- Traffic Modelling

Traffic in a telecommunications network is the volume of information transported or processed by the network. Unlike the 3G UMTS technology in a 4G/LTE-A network, there is only one type of traffic that transport data in packet form between the EPC and the mobile terminal. And as users’ behaviour is random, we consider that traffic follows a Markov chain in continuous time through a process of birth and death. As there are no mathematical laws to model accurately the behaviour of the packet-switched traffic in a 4G network, suppose that all the cells in our network are considered queues M/M/1 forming a Jackson network [55] .

Thus, the process of arrival of data packets is fish αi rate and tenure of the cell follows an exponential law of parameter μi ( and μi is strictly positive). A steady state (μi.i ≤ 1).

To facilitate the generation of data for our simulations, we make the assumptions below:

- The fi data rates from a cell i with mean gamma distribution and variance equal to unity.

- The service time (residence time: for example, the talking time or download time of a file) data within cells are distributed according to an exponential law of parameter equal to unity.

- If a cell j has neighbour k, [0,1] is divided into k + 1 in k intervals by choosing random number uniformly distributed between 0 and 1. At the end of the period of service in the cell j, the data packets may either be transferred to the ith neighbour ( i = 1 , 2 , 3 , , k ) with a probability of transfer equal to the length of the ith interval, be closed with a probability equal to the length of the k + 1th interval.

To find the volume of data and the coherent succession rate, the αi rate data in cells at equilibrium are obtained by solving the following system:

f i = α i j = 1 n α i r i j a v e c i = 1 , 2 , , n

where n is the number of network cells and rij, the probability of handover between cells i and j.

fi being the traffic data rate from cell i.

It is selected as the data volume of an eNode B, the average length of its queue.

The succession rate is defined by: hij = firij.

・ All sSGW have the same capacity packet M0 calculated as follows for the purposes of the simulation:

M 0 = 1 s ( 1 + k 100 ) i = 1 n f i

where k is uniformly distributed between 10 and 50, which ensures an overall surplus of 10 to 50% of the capacity of SGW compared to the data volume of the eNode B.

・ All p PGW have the same capacity M1 calculated as follows:

M 1 = 1 p ( 1 + k 100 ) i = 1 n M 0

where k' is uniformly distributed between 10 and 50, which ensures an overall surplus of 10% to 50% of the capacity of PGW relative to the volume data from the SGW.

6.2. Experiment Plan

In order to verify the performance of our adaptation, a series of experiment was performed.

Considering a network of 15 eNode B-7 SGW-5 PGW, we generated the data needed to experience using a program Matlab R2015b. The program is executed on a computer whose characteristics are: Intel®Core™ i3-3110M CPU@2.40 GHz 2.40 GHz.

The parameters used for the simulation of our adaptation are:

- Population size: 80.

- Number of generation: 45.

- Crossing probability: 0.9.

- Mutation probability: 0.2.

- Inversion probability: 0.25.

We executed our adaptation respecting the simulation parameters set out above (Test N˚1).

The results show that the algorithm performs well because the optimum is reached in the last generation (Figure 5).

Figure 5. Evolution of the optimal value over generations.

Figure 5 shows the variation of the optimum of 45 generations in the genetic process for a network of 15 eNode B, 7 SGW and PGW 5.

Comment: We note that the process starts with a value of 1207.2 units in the first generation. This optimum undergoes an increase of 0.25% or an evaluation of 1210.2 units in the second generation from the optimum value to the first generation.

A marked improvement in the optimum value of 0.42% was observed in the third generation or an evaluation of 1205.1 units. From the third generation, the algorithm performs very well, and we get good value for the optimum in the 45th generation of 870.2 units, an improvement of 27.79% and 27.91% compared to the optimum of the first generation. This improvement is due to the fact that only feasible solutions were chosen to form a new population.

Study of the influence of the population on the optimum value

2nd series of experiments with a population equal to 60 chromosomes (Figure 6).

Figure 6. Evolution of the optimum value for a population of 60 chromosomes.

Comment: We note that keeping the same parameters except the population size this time that equals 60 (Test N˚. 2). We obtain the optimum in the 45th generation of a value of 942.8 units except that it is not better compared with that found previously in Figure 5.

3rd series of experiments for an estimated population of 40 chromosomes (Figure 7).

Figure 7. Evolution of the optimum value for a population of 40.

Comment: We repeated this same experience to a size of the estimated population of 40 chromosomes (Test No. 3), made the observation that if the algorithm performs well but also the optimum value is degraded; an increase of 14.76% relative to the optimum test N˚ 1 of the first experiment and 5.92% relative to the optimum test N˚2 of the second experiment.

Thus, a large population ensures good exploration of the search space, which allows to have a refined optimal solution. However, a small population could lead so quickly to a good solution provided that operators are judiciously applied.

Finally, the experiments have shown that the processing time increases with a growth in population, this is probably due to the heterogeneity of the members in population.

Thus, concerning the search space, the algorithm explores the neighbourhood of each feasible solution to determine the global optimum.

7. Conclusion

In this article, we proposed a mathematical model to solve the problem of a mobile Long Term Evolution Advanced network planning which we have solved with the genetic algorithm in a global context by considering three sub assignments. The genetic approach we proposed provides an optimal solution after a number of generations. However, it depends on the size of the population. It is observed that the bigger the exploration space is the more we hope to have a refined solution. However, it is important to note that our approach to the design of the model excludes the interfaces defined in the architecture of control plan of an LTE-A network [12] . This aspect is a forward looking view that could integrate this model to provide a comprehensive planning.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Bertrand, B. , Moustapha, D. , Etienne, S. , Souleymane, O. and Boko, A. (2016) A Genetic Algorithm for Overall Designing and Planning of a Long Term Evolution Advanced Network. American Journal of Operations Research, 6, 355-370. doi: 10.4236/ajor.2016.64033.

References

[1] Hamal, S. (2013) Analysis on 4G Technology. International Journal of Advanced Research in Computer Science and Software Engineering (IJARCSSE), 3, 624-628.
[2] Ekiz, N., Salih, T., Kücükoner, S. and Fidanboylu, K. (2005) An Overview of Handoff Techniques in Cellular Network. World Academy of Science, Engineering and Technology, 6, 1-4.
[3] Kassar, M., Kervella, B. and Pujolle, G. (2008) An Overview of Vertical Handoff Decision Strategies in Heterogeneous Wireless Networks. Computer Communications, 31, 2607-2620.
http://dx.doi.org/10.1016/j.comcom.2008.01.044
[4] Bouguen, Y., Hardouin, E. and Wolff, F.-X. (2012) LTE et les réseaux 4G. Groupe Eyrolles, 2012, Chapitre 19, Page 414, 539 Pages.
[5] Bouvero, A. (2013) Accélérer la transition vers les services 4G-LTE, Les cahiers de l’ARCEP N° 10-mai 2013: 2013 année clé pour la 4G. Page 3.
[6] ITU-T confers 4G Statuts to 3GPPLTE, 3gpp.org, 20 Otocbre 2010.
[7] Niger, Ph., Del Burgo, St., Jounay, F., Kortebi, R., Michau, B., Lemoine, B., Jobert, S., Duprez, M. and Le Clech, F. (2009) LTE Transport Architectural Framework and Scenarios. Technical Report, France Telecom Group.
[8] CISCO (2014) Top 10 Considerations for a Successful 4G LTE Evolved Packet Core Deployment, Document ID: 1458683850466698. Update: May 01.
[9] CISCO (2016) Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2015-2020. Document ID: 1454457600809267. Updated: Feb 01.
[10] Jonghwan, H. (2015) A High Performance VoLTE Traffic Classification Method Using HT Condor. IFIP/IEEE International Symposium on Integrated Network Management (IM).
[11] Coupechoux, M. and Martins, P. (2013) Vers les systèmes radiomobiles de 4e génération. De l’UMTS au LTE. Collection iris. Springer-Verlag France, Paris.
http://dx.doi.org/10.1007/978-2-8178-0085-1
[12] 3GPP (2011) General Packet Radio Service (GPRS) Enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) Access. TS 23.401.
[13] Martín-Sacristán, D., Monserrat, J.F., Cabrejas-Penuelas, J., Calabuig, D., Garrigas, S. and Cardon, N. (2009) On the Way towards Fourth Generation Mobile: 3GPPLTE and LTE Advanced. EURASIP Journal on Wireless Communications and Networking, 2009.
http://dx.doi.org/10.1155/2009/354089
[14] Pierre, S. (2003) Réseaux et systèmes informatiques mobiles: Fondements, architectures et applications. Presses inter Polytechnique.
[15] Rajalakshmi, K., et al. (2010) Hybridizing Iterative Local Search Algorithm for Assigning Cells to Switch in Cellular Mobile Network. International Journal of Soft Computing, 5, 7-12.
[16] Salcedo-Sanza, S. and Yaob, X. (2008) Assignment of Cells to Switches in a Cellular Mobile Network Using a Hybrid Hopfield Network-Genetic Algorithm Approach. Applied Soft Computing, 8, 216-224.
http://dx.doi.org/10.1016/j.asoc.2007.01.002
[17] Goudosa, K., Konstantinos, B., Christos Bachtsevanidis, B. and Sahalos, J.N. (2010) Cell-To Switch Assignment in Cellular Networks Using Barebones Particle Swarm Optimization. IEICE Electronics Express, 7, 254-260.
http://dx.doi.org/10.1587/elex.7.254
[18] Diallo, M.M. and Pierre, S. (2010) A Tabu Search Approach for Assigning Node Bs to Switches in UMTS Networks. IEEE Transactions on Wireless Communications, 9, 1350-1359.
http://dx.doi.org/10.1109/TWC.2010.04.080764
[19] St-Hilaire, M. and Liu, S. (2011) Comparison of Different Meta-Heuristics to Solve the Global Planning Problem of UMTS Networks. Computer Networks, 55, 2705-2716.
http://dx.doi.org/10.1016/j.comnet.2011.05.008
[20] Yang, J., Aydin, M.E., Zhang, J. and Maple, C. (2007) UMTS Base Station Location Planning: A Mathematical Model and Heuristic Optimisation Algorithms. IET Communications, 1, 1007-1014.
http://dx.doi.org/10.1049/iet-com:20060495
[21] Juttner, A., Orban, A. and Fiala, Z. (2005) Two New Algorithms for UMTS Access Network Topology Design. European Journal of Operational Research, 164, 456-474.
http://dx.doi.org/10.1016/j.ejor.2003.11.027
[22] Lauther, U., Winter, T. and Ziegelmann, M. (2003) Proximity Graph Based Clustering Algorithms for Optimized Planning of UMTS Access Network Topologies. 10th International Conference on Telecommunications, 2, 1329-1334.
http://dx.doi.org/10.1109/ictel.2003.1191628
[23] Charnsripinyo, C. and Tipper, D. (2005) Topological Design of 3G Wireless Backhaul Networks for Service Assurance. 5th International Workshop on Design of Reliable Communication Networks, 16-19 October 2005, 115-123
http://dx.doi.org/10.1109/drcn.2005.1563853
[24] Ricciato, D., Pilz, R. and Hasenleithner, E. (2006) Measurement-Based Optimization of a 3G Core Network: A Case Study. 6th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking, 4003, 70-82.
http://dx.doi.org/10.1007/11759355_9
[25] Harmatos, J. (2002) Planning of UMTS Core Networks. 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2, 740-744.
http://dx.doi.org/10.1109/PIMRC.2002.1047320
[26] St-Hilaire, M. (2006) Planification Globale des réseaux mobiles de troisième génération. Thèse-PhD (Génie Informatique), Département génie Informatique, Ecole Polytechnique de Montréal.
[27] Pujolle, G. (2014) Les Réseaux-2014, Eyrolles. 8é édition, février 2014, 425.
[28] Osseiran, A., et al. (2014) Scenarios for the 5G Mobile and Wireless Communications: The Vision of the METIS Project. IEEE Communications Magazine, 52, 26-35.
http://dx.doi.org/10.1109/MCOM.2014.6815890
[29] Lu, L., Chen, Y., Guo, W.T., Yang, H.L., Wu, Y.Q. and Xing, S.S. (2015) Prototype for 5G New Air Interface Technology SCMA and Performance Evaluation. China Communications, 12, 38-48.
http://dx.doi.org/10.1109/CC.2015.7386169
[30] Ekram, H. and Monowar, H. (2015) 5G Cellular: Key Enabling Technologies and Research Challenges. IEEE Instrumentation & Measurement Magazine, 18, 11-21.
http://dx.doi.org/10.1109/MIM.2015.7108393
[31] Mona, J., Ali Imran, M., Tafazolli, R. and Tukmanov, A. (2016) 5G Backhaul Challenges and Emerging Research—A Survey. IEEE Access, 4, 1743-1766.
http://dx.doi.org/10.1109/ACCESS.2016.2556011
[32] Chih-Lin, L. (2016) New Paradigm of 5G Wireless Internet. IEEE Journal on Selected Areas in Communications, 34, 474-482.
http://dx.doi.org/10.1109/JSAC.2016.2525739
[33] Li, Z., and Li, S. (2011) LTE Network Planning Based on Game Theory. International Conference on Computer Science and Service System (CSSS), Nanjing, 27-29 June 2011, 3963-3966.
[34] Majewski, K. and Koonert, M. (2010) Conservative Cell Load Approximation for Radio Networks with Shannon Channels and Its Application to LTE Network Planning. 2010 6th Advanced International Conference on Telecommunications (AICT), Barcelona, 9-15 May 2010, 219-225.
http://dx.doi.org/10.1109/aict.2010.9
[35] Gu, J., Ruan, Y., Chen, X. and Wang, C. (2011) A Novel Traffic Capacity Planning Methodology for LTE Radio Network Dimensioning. IET International Conference on Communication Technology and Application (ICCTA), October 2011, 462-466.
[36] Li, X., Toseef, U., Dulas, D., Bigos, W., Gorg, C., Timm-Giel, A. and Klug, A. (2013) Dimensioning of the LTE Access Network. Telecommunication Systems, 52, 2637-2654.
http://dx.doi.org/10.1007/s11235-011-9593-2
[37] Jailani, E., Ibrahim, M. and Ab Rahman, R. (2012) LTE Speech Traffic Estimation for Network Dimensioning. IEEE Symposium on Wireless Technology and Applications (ISWTA), Bandung, 23-26 September 2012, 315-320.
http://dx.doi.org/10.1109/iswta.2012.6373868
[38] Dababneh, D., St-Hilaire, M. and Makaya, C. (2015) Data and Control Plane Traffic Modelling for LTE Networks. Mobile Networks and Applications, 20, 449-458.
http://dx.doi.org/10.1007/s11036-015-0631-2
[39] Germine, S. (2011) Planification d’un réseau de quatrième génération à partir d’un réseau de troisième génération. Mémoire (Génie Informatique) Département génie Informatique et génie logiciel, Ecole polytechnique de Montréal.
[40] Lemamou, E.-A., Chamberland, S. and Galinier, P. (2013) A Reliable Model for Global Planning of Mobile Networks. Computers & Operations Research, 40, 2270-2282.
http://dx.doi.org/10.1016/j.cor.2013.03.017
[41] Liang, X.Y., Liu, H.L. and Wang, Q. (2015) 4G Heterogeneous Networks Base Station Planning Using Evolutionary Multi-Objective Algorithm. 11th International Conference on Computational Intelligence and Security (CIS), Shenzhen, 19-20 December 2015, 248-252.
[42] Pasandideh, M.R. and St-Hilaire, M. (2013) Automatic Planning of 3G UMTS All-IP Release 4 Networks with Realistic Traffic. Computers & Operations Research, 40, 1991-2003.
http://dx.doi.org/10.1016/j.cor.2013.02.017
[43] Dababneh, D., St-Hilaire, M. and Makaya, C. (2015) Automatic Planning of Long Term Evolution Evolved Packet Core Networks. 6th International Conference on Network of the Future (NOF 2015), Montreal, 30 September-2 October 2015, 1-5.
http://dx.doi.org/10.1109/NOF.2015.7333302
[44] Merchant, A. and Sengupta, B. (1994) Multiway Graph Partitioning with Applications to PCSB Networks. Proceedings IEEE INFOCOM 94 the Conference on Computer Communications, 2, 593-600.
http://dx.doi.org/10.1109/INFCOM.1994.337682
[45] Merchant, A. and Sengupta, B. (1995) Assignment of Cells to Switches in PCS Networks. IEEE/ACM Transactions on Networking, 3, 521-526.
http://dx.doi.org/10.1109/90.469954
[46] Skorin-Kapov, J. (1989) Tabu Search Applied to the Quadratic Assignment Problem. ORSA Journal on Computing, 2, 33-45.
http://dx.doi.org/10.1287/ijoc.2.1.33
[47] Klincewicz, J.G. (1991) Heuristics for the p-Hub Location Problem. European Journal of Operation Research, 53, 25- 37.
http://dx.doi.org/10.1016/0377-2217(91)90090-I
[48] Sanchis, L.A. (1989) Multiple-Way Network Partitioning. IEEE Transactions on Computers, 38, 62-81.
http://dx.doi.org/10.1109/12.8730
[49] Kemighan, B.W. and Lin, S. (1970) An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49, 291-307.
http://dx.doi.org/10.1002/j.1538-7305.1970.tb01770.x
[50] Fogel, L., Owens, A.J. and Walsh, M.J. (1966) Artificial Intelligence through Simulated Evolution. Wiley, New York.
[51] Rechenberg, I. (1965) Cybernetic Solution Path of an Experimental Problem. Royal Aircraft Establishment Library Translation.
[52] Holland, J. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
[53] Goldberg, D.-E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Don Mills.
[54] Gondim, R.-L.P. (1996) Genetic Algorithm and the Location Area Partitioning Problem in Cellular Networks. Proceeding of Vehicular Technology Conference 1996, Atlanta, 29-30 April-1 May 1996, 1835-1838.
http://dx.doi.org/10.1109/vetec.1996.504075
[55] Kleinrock, L. (1975) Queuring Systems 1: Theory. Wiley, New York.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.