Mobile base stations location problem to fortification against natural disasters: A fuzzy approach

1 Introduction

In the last decade, mobile telecommunication networks have known an extraordinary development, due to connection among users.

Mobile communication networks are usually is partitioned into a number of hexagonal cells, each corresponding to a different cover zone, and associated to a given Base Station (BTS).

Each Base Station (BTS) contains the equipment for transmitting and receiving radio signals from the users of mobile phones. Each BTS is connected to one Base Station controller (BSC). BSC has tens or even hundreds of BTSs under its control. The BSC handles allocation of radio channels, receives measurements from the mobile phones, and controls handovers from BTS to BTS. Each BSC connected to one mobile switching center (MSC). Finally, each MSC serves a number of BSCs and the MSCs are interconnected in a meshed network [7]. A small sample network is illustrated in Fig. 1.

Usually, Base Station of phone systems are set up without special consideration of disasters or other disruptions. Natural disasters such as earthquakes have a strong impact on communications systems. when disruption of communications happen, people have trouble to contact each other. The failures of communications systems had different causes: interrupted electricity supply; misaligned microwave antennas between the cells (or Base Stations, or antennas) and the rest of the system; broken fiber optics lines, or plain destruction of Base Stations.

An optimization problem that could be used to locate cell phone Base Stations was formulated by Lee [4], whose Communications Design Problem was primarily designed for the location of radio and television transmitters. In 2000, Mathar and Niessen [6] formulate a variety of models that include transmitter locations and fixed and dynamic channel assignments. Touhami et al. [11] performed studies on the location of cell phone Base Stations and the selection of their transmitting power in 2006. In previous studies, the possibility of the destruction of a Base Station was not considered against natural disasters. In 2011, Eesilt et al. [12] presented a model for locating or strengthening of cell phone Base Stations to maximize service coverage when a numbers; natural disaster happens. In this model, a covering of customer sites is maximized before and after disasters, so this problem is formulated by multi objective programming. After happening of natural disasters, the cell phone system may face some problems such that there is no complete connection between customers while a percentage of system is applicable. For example some of people may not contact to each other but they can communicate by short messaging service (SMS). So, in our model covering parameters are considered as fuzzy numbers. In this case, we have a fuzzy multi objective programming. In 1965, Zadeh published his famous paper as fuzzy sets [5]. Zimmerman extended his fuzzy linear programming approach to multi objective linear programming in 1978 [3].

Diwekar [13] introduced several general methods such as, weighted methods, constraint method and goal programming for converting multi objective into a single objective optimization programming.

One particular way converting multi objective programming to single objective programming is fuzzy deal respected problem. Since most relevant papers have used this approach, we used it.

A Diversity of different exact and heuristic solution approaches have been developed to solve location problem. The exact solution approaches have been used to obtain the global optimal solution in location problems. A heuristic solution approach has been taken to yield a good solution with reasonable computational time. Since a location of Base Stations problem is NP-hard we use a metahueristic method to solve this problem. Due the fact that our considered problem is a discrete one and genetic algorithm and GRASP algorithm have been performed successfully for this type of optimization problems, we use them in our study.

Since some communication system exists in all countries, this paper considers an existing system, in which the task is for fortifying some of the Base Stations, to maximize a covered demands in case a single Base Station fails.

The paper is organized as follows: Section 2 contains Preliminaries. Section 3 presents the model. solving problem by combining of fuzzy method and metaheuristic algorithms considered Section 4. numerical results are obtained in Sections 5 and 6 discusses conclusions.

2 Preliminaries

In this section, we briefly review some basic concepts of fuzzy set theory and multi objective programming problem [1, 8].

Definition 1. Let X be the universal set. A ˜ is called a fuzzy set in X if A ˜ is a set of ordered pairs A ˜ = { ( x , μ A ˜ ( x ) ) | x ∈ X }(1) where μ A ˜ ( x ) is the membership function of x in A ˜. μ A ˜ ( x ) species the degree of membership of element x in fuzzy set A ˜.

A fuzzy set is often denoted by A ˜, but it is sometimes written as A for simplicity in the notation.

Definition 2. The α-level set of a fuzzy set A ˜ is defined as an ordinary set A _α for which the degree of its membership function exceeds the level α: A α = { x | μ A ˜ ( x ) ≥ α , α ∈ [ 0 , 1 ] }(2)

Definition 3. A triangular fuzzy number denoted by A ˜ = ( m , a , b ) has a membership function as follows (see Fig. 1): μ A ˜ ( x ) = { 1 - m - x a , m - a ≤ x ≤ m 1 - x - m b , m ≤ x ≤ m + b 0 o . w .(3)

The point m, with membership grade of 1, called a mean value and a,b are the left hand and right hand spreads of A ˜ respectively.

Also, for each α ∈ [0, 1] α-cuts of triangular fuzzy number of A ˜ is definded as: A ˜ α = [ m - a ( 1 - α ) , m + b ( 1 - α ) ](4)

In Eiselt et al. [2] the authors propose a model to determine location Base Station of mobile phone that should be fortified. To present this formulation, consider the following conventions. The subscript i in set I refer to the customer sites, j and l in set J denote the potential locations of the Base Stations that we may fortify. The parameter of model are as following:

p: the total number of facilities to be fortified;

w _i : the number of customers at site i;

q: the probability of failure of a fortified facility at each site; a ij = { 1 if site j can cover node i 0 o . w .

In addition, the variables are: y j = { 1 if BTS at site j is fortified 0 o . w . x i = { 1 if customer at site i is covered 0 o . w .

The value of binry variable z _il is 1, if site i is still covered even after a facility at site l is destroyed and otherwise 0;

v _l  ≥ 0: Total loss of customers if the facility at site l is destroyed.

We also define:

N i -= {set of sites j that not cover customer site i};

M _j  = {k|d _jk  ≤ minimum allowed distance between any pair of base stations}, d _jk is the distance between nodes j and k.

The model can then be formulated as follows [2]: Max Z 1 = ∑ i w i(5) Max Z 2 = ∑ i w i x i - ν(6) Max Z 3 = ∑ i w i x i - 1 p ∑ l v 1(7) s . t . ∑ j y j = p(8) x i ≤ ∑ j a ij y j ∀ i(9) z il ≤ 1 - 2 a il y l + ∑ j a ij y j ∀ l(10) z il = 1 ∀ l ∈ N i -(11) ν l = ∑ i w i ( 1 - z il ) ∀ l(12) ν ≥ ν l ∀ l ∈ J(13) y k + y j ≤ 1 ∀ j ∈ J , ∀ k ∈ M j(14) y j , x i , z il ∈ { 0 , 1 } ∀ j , l ∈ J , ∀ i ∈ I ∥(15) The first objective is the covering objective before disasters.

In the second objective, the number of customers covered in the worst-case loss (υ = max  υ _l ) after disasters is shown. In this case a Base Station which covers the largest number of customers, destroyed.

The last objective determines the number of customers covered in the average case, in which we assume that the single Base Station destroyed randomly.

Constraint (8) determine the sets of total number of facilities to fortify. Constraint (9) indicates a node i to be covered, only if the site is covered at least once by one facility. Consider constraint (10). The first sum on the right-hand side of constraint (10) shows the number of times that node i is covered from node l (which is either zero or one), while the second sum on the right hand side of constraint (10) determines the number of times that node i is covered from anywhere, including from site l. In constraint (11) a node l that does not cover customer i, then its destruction is not affected. Constraint (12) defines the loss in case node l is destroyed. Constraint (13) defines variable v. Constraint (14) enforces minimum separation between Base Stations, and finally, (15) denotes the specifications of the variables.

After happening of natural disasters, the cell phone system may face some problems such that there is no complete connection between customers while a percentage of system is applicable. In this case, knowing the value of the mentioned percentage is mamdatory rather knowing the possibility of the connection. So, we use fuzzy set theory and we define a ˜ ij as a fuzzy parameter that denotes the covering amount of site i by Base Station j, where μ a ˜ ij ( a ) ∈ [ 0 , 1 ] is its membership function.

Now, for converting a fuzzy problem to non-fuzzy problem, we use of concepts α-cuts.

Let a ˜ ij = ( a ij 1 , a ij 2 , a ij 3 ), be a triangular fuzzy number. The α-cut of a ˜ ij denoted by ( a ˜ ij ) α is: ( a ˜ ij ) α = [ a ij 1 - a ij 2 ( 1 - α ) , a ij 1 - a ij 3 ( 1 - α ) ](16)

In (16) a ij 1 - a ij 2 ( 1 - α ) = ( a ij ) α L is lower bound and a ij 1 + a ij 3 ( 1 - α ) = ( a ij ) α U is upper bound of ( a ˜ ij ) α .

The problem (5)–(15) by considering a ˜ ij as fuzzy parameter (that is called α _-  MOLP) is a nonlinear problem, because parameter a ˜ ij is treated as decision variables. To deal with such nonlinearities, we introduce the following set valued function T _j  (a _j ,  b _j ) = {y|a _j y ≥ b _j ,  j = 1, …,  n}. Then it can be easily verified that the following proposition is hold for T _j  (a _j b _j ), when y ≥ 0.

Proposition 1 [8]:

If a j 1 ≤ a j 2, then T j ( a j 1 , b j ) ⊂ T j ( a j 2 , b j ).

Therefore, through the use of Proposition 1, the constraint (9), (10) can be converted into the following constraint: x i ≤ ∑ j ( a ij ) α U y j ∀ i(17) z il ≤ 1 - 2 ( a il ) α U y l + ∑ j ( a ij ) α U y j ∀ l(18)

By replacement of this new constraints in problem (1)–(10), the following model is obtain: Max Z 1 = ∑ i w i Max Z 2 = ∑ i w i x i - v Max Z 3 = ∑ i w i x i - 1 p ∑ l v l(19) s . t . ( x , y , z ) ∈ X

Where X is as follow: ∑ j y j = p x i ≤ ∑ j ( a ij ) α U y j ∀ i z il ≤ 1 - 2 ( a il ) α U y l + ∑ j ( a ij ) α U y j ∀ l z il = 1 v l = ∑ i w i ( 1 - z il ) ∀ l v ≥ v l ∀ l ∈ J y k + y j ≤ 1 ∀ j ∈ J , ∀ k ∈ M j y j , x i , z il ∈ { 0 , 1 } ∀ j , l ∈ J , ∀ i ∈ I

Definition 4. t^* = (x^*,  y^*,  z^*) is said to be a pareto optimal solution if and only if there dose not exist another t ∈ X such that z _i  (t) ≤ z _i  (t^*) for all i ∈ I and z _i  (t) ≠ z _i  (t^*) for at least one j.

Definition 5. t^* is said to be an α-Pareto optimal solution to the α-MOLP if and only if there does not exist another t ∈ X set and a ∈ (a _ij )  _α such that z _i  (t) ≤ z _i  (t^*) i = 1, 2, 3 with strict inequality holding for at least one i.

Theorem 1. [8] If t^*is a unique optimal solution to (19), then t^* is an α-Pareto optimal solution to the α –MOLP.

In the sequel, to change the MOP problem to a SOP problem, we apply fuzzy programming. If we consider μ i L ( z i ( x ) ) as membership function corresponding to i th objective function, then by the fuzzy decision of Bellman and Zadeh [4] we have following problem: max min i = 1 , 2 , 3 { μ i L ( z i ( x ) ) }(20)

Now, if we use the following linear membership function corresponding to z _i  (x), μ i ( z i ( x ) ) = { 0 z i ( x ) ≥ z i L ; z i ( x ) - z i L z i U - z i L z i L ≥ z i ( x ) ≥ z i U ; 1 z i ( x ) ≤ z i U .(21)

In which:

z i L = z i ( x i ) = min x z i ( x ) , i = 1 , 2 , 3 ; z i U = max ( z i ( x 1 ) , z i ( x 2 ) , z i ( x 3 ) )(22)

Then the problem (19) now changes to the problem as follows: max λ(23) s . t . λ ≤ z i ( x ) - z i L z i U - z i L , i = 1 , 2 , 3 0 ≤ λ ≤ 1 ; ( x , y , z ) ∈ X . where the variable λ is degree of satisfaction of a solution, i.e., its membership level with respect to the decision set.

Problem (23) is a NP-hard problem. Thus we use metaheuristic methods such as genetic and grasp algorithm to solve it.

A Genetic Algorithm (GA)

Genetic algorithm is a metaheuristic algorithm which was first introduced by John Holland in 1960 [10]. This algorithm is essentially extended based on the principles of genetics and evolution phenomena.

Three main operators in the GA, i.e., selection, crossover and mutation, are applied to a random generated population of choromosomes in order to produce a new population with special features.

The following algorithm, discusses about the components of GA.

Algorithm 1: Genetic Algorithm

Step 0 Input prarmters: max-iteration, number of population, p _m ,  p _c .

Step 1 (Chromosome Encoding): The variables y _j is encoded as a list of binery numbers. For example for j = 5, y _j is shown in Fig. 3, in which 1 is indicated that a Base Station is fortified.

Step 2 (Initialization Procedure): This procedure begin by randomly generating an initial population of solutions.

Step 3 (Fitness Function): Each solution is evaluated according to a fitness function. The fitness function for problem (14)-(23) introduced is defined as: f fitness ( x ) = min ( μ 1 ( z 1 ( x ) ) , μ 2 ( z 2 ( x ) ) , μ 3 ( z 3 ( x ) )

Step 4 (Selection): The first step consists in selecting individuals for reproduction. This selection is done randomly with a probability depending on the relative fitness of the chromosomes so that best ones are often chosen for reproduction than poor ones.

Step 5 (Crossover): A crossover takes two parents and creates one or two children containing some of the genetic material of each parent that will form the next generation of solutions. The crossover rate p _c   (p _c  ∈ [0, 1]) represents the proportion of parents on which a crossover operator will act. The most commonly used rates are in the interval [0.45, 0.95].

Step 6 (Mutation): This operator takes one parent and randomly changes some of the entries in chromosome to create a child. The mutation rate p _m defines the probability to mutate each element of the representation. In general, small values are recommended for this probability (p _m  ∈ [0.001,  0.01]).

Step 7 (termination): This procedure repeats until stopping criterion satisfied.

Output: solutions y.

Greedy Randomized Adaptive Search Procedure(GRASP)

GRASP is a metaheuristic that was first introduced by Feo and Resende in 1989 [12]. In this publication GRASP was applied to the set covering problem. GRASP is a multi-start or iterative procedure where each iteration consists of two phases: construction and local search.

Step 0 Input a threshold parameter β.

Step 1 (Construction): In the construction phase, a feasible solution is iteratively constructed by adding one element at an iteration.

At each construction iteration, the choice of the next element to be added is determined by ordering all elements in a candidate list with respect to a greedy function. This function measures the benefit of selecting each element. The list of best candidates is called the restricted candidate list (RCL). For the construction of the RCL used in the first phase we consider a greedy function associated with each located Base Station (l) that is denoted by g (l) = ∑ _i w _i  (1 - z _il ). At any GRASP iteration, let g _min and g _max be, respectively, the smallest and the largest greedy function. The restricted candidate list is made up of BTSs with the best (i.e., the largest) greedy function. This list can be limited either by the number of BTS (cardinality-based) or by their quality (value-based). In the first case, it is made up of the t BTSs with the best coverage, where t is a parameter. The RCL is associated with a threshold parameter β ∈ [0 ;  1]. The restricted candidate list is formed by g (l) = [g _min ,  g _min  + β (g _max  - g _min )]. The case β = 0 corresponds to a pure greedy algorithm, while β = 1 is equivalent to a random construction. Each step of the constructive algorithm, a list of possible selection element is created and one is then selected randomly. The values of the remaining elements, which will be used when the next RCL is constructed, are updated and the process is repeated until a complete solution is obtained.

Step 2 (Local Search): Local search uses concept of solution neighborhood. A local search algorithm successively replaces the current solution by a better solution in its neighborhood, if one exists. It terminates with a locally optimal solution when there is no better solution in the neighborhood. For example the neighborhood of solutions at solution y = (0 1 0 1) can be considered as (1 1 0 1), (0 1 0 0), (0 0 0 1) and (0 1 1 1).

Output: solutions y.

In this section some instances are used. This instances are solved by GA and GRASP algorithm and the results compared with together.

6 Conclusion

In this paper, we deal with objective Mobil Base Station Location Problem in order to fortification. The objective of this problem is to maximize covering before and after happening of natural disasters.

In this paper, we suggested to addition fuzzy covering for model of Eiselt et al. [2] and converted MOP to SOP by fuzzy programming. Finally, we solved instances of SOP (23) by GA and GRASP algorithm and the results compared with together. The results show the performance of genetic algorithm is better than GRASP algorithm for this problem.