An Approach to BTS Localization using Optimization Techniques

An Approach to BTS Localization using Optimization Techniques

Ankita Awasthi

Dept. of Telecom Engineering,AITEM Amity University

Noida, India

Neha Arora

Dept. of Telecom Engineering,AITEM Amity University

Noida, India

AbstractOptimization means to have maximum capacity, better quality and reduced cost. The growth of wireless communication is increasing as the need for better services has been increased in between the customers. This has led the researchers to work on the Radio Coverage. Radio Coverage in general gets affected by Antenna arrangements, Location of BTS and also the Performance of Base Station. This paper considered as how to locate the Optimal location of Base Station Transceiver (BTS), so that with minimum number of BTS, maximum number of user can be covered at less infrastructural cost. The idea of Using Evolutionary algorithm is quite effective and efficient as these algorithms are developed by modeling the behavior of different swarm of animals and insects eg ants, bees & birds. These algorithms can be used to determine the Optimal Location of BTS. In this paper, ABC algorithm is being used to localize BTS so as to cover maximum number of Subscriber. The results are then also compared with GA algorithm.

KeywordsArtifical bee Colony(ABC),Genetic Algorithm,Base Transeiver Station(BTS),Monile Station(MS),Cellular Mobile Communication

1. INTRODUCTION

   The increasing growth in using mobile services with more and more carriers that are joining the market has triggered the need for system Optimization and radio network planning. There are several factors that are involved in design of network that are coverage, traffic, topography, propagation features and system capacity. The location of cell can be determined on the basis of the number of cells, the coverage performance, traffic distribution and the propagation environment. The design parameters at the mobile unit and the base station cannot be specified unless the allocation of cell is completed. Cell planning is not a onetime task as it is very important that design should be continuously updated based on the mobile network scenario and as a result such provision must be added in the design tool.

   Many studies have been done in the area of network planning in terms of the coverage analysis, channel assignment, routing and propagation but few studies [1],[2] have been carried out in the area of the cell planning for the cost effective system design. In conventional cellular planning the traffic was less and the planning is done according to the Frequency reuse pattern. For example in [3], the author has main concentration on the strategies of channel allocation and also discussed about as how sectoring can be used so as to achieve better performance of system. Cell planning tool

   basically need to be adaptive and the tools should have provision for constant estimation of scenario and correction of the design. With set covering problem approach this becomes too cumbersome and it lead to insufficient implementation.

   When cellular concept was proposed, regular frequency reuse pattern is used for selecting BTS locations. With the growth in cellular technology, it is becoming important for cellular operators to have a network which is not only better in term of quality of service but also profitable than the others. The cost involved in setting up a network and the quality of service offered is directly proportion to the number of BTS installed, more BTS, more is the cost but better coverage at more infrastructure cost.[1]

   The Placement of BTS is an important job for network design, the reason being the frequency channel become increasingly congested and propagation environment become more complex. Suboptimal placement of BTS will not only increase the cost but also reduction in spectrum efficiency. In order to cope up with the need of rapid wireless system deployment, research effort have been put into develop over the past few years.[4]

   In this paper main focus is on the problem of locating the best suitable position for the base station so as to meet the traffic demand. Here in this paper the Optimizations techniques are being used to determine optimal location of the BTS. Two algorithms that are ABC(Artificial Bee Colony Algorithm) and Genetic algorithm are being used by considering certain parmeters.ABC is a search algorithm to localize the BTS so as to cover maximum number of subscriber. The performance of ABC algorithm is also compared with GA. Genetic algorithm (GA) is one of the traditional technique for determining the optimal location of BTS.

   The rest of paper is organized as follows: The next section gives detail description about cell planning problem. In section III we present clustering approach for determining the cell location and base station placement. Section IV presents ABC algorithm while section V presents the GA algorithm. In section VI problem Statement is discussed. In section VII comparative simulation results are obtained with ABC and GA are presented for comparative analysis. Finally a conclusion has been discussed in the last section.

2. CELL PLANNING

   A cell is the area that is covered by base station transmitter which is the basic geographical unit of the cellular system. The cells can be classified according to their sixe such as macro cells range from 1 to 30 Km and that of Pico cell ranging from 10 to 200m. Cell planning address the problem of placing the base station and specifying the parameters for every base station so that the optimal system performance is achieved and the system cost is minimized. The performance and the costs are characterized by:

   Coverage: The radio signal coverage must be guaranteed and holes in the coverage area should be avoided.

   Capacity: In each cell, a sufficient number of channels must be available in order to meet its traffic demand for new calls and handoffs.

   Transmission quality: The ratio of carrier to interference power(C/I) of radio channels must satisfy the requirements of transmission quality

   Cost: The deployment cost that is the cost of putting the required number of base stations cost of transmitting power. For cell planning, the area to be planned is discretized, the resolution depending on the type of cells being planned.

   The cells are drawn for convenience as hexagons. The edges of the hexagons represent the theoretical equal power boundaries between cells assuming that every BTS radiates the same power, propagation is homogenous in every cell and all the BTS are similarly sited in either the centre or at the corner of every cell [5]. However the reality of the coverage pattern will be somewhat different and can fully determine using propagation planning tools coupled with a detailed study of the service area and fields measurement.

3. CLUSTERING MODULE :

   Clustering is used to categorize or group similar data items together. The problem of cell planning can be modeled as a clustering problem where the aim is to cluster the demand node such that they accord to a certain set of properties. The set of properties being: minimum signal strength should be guaranteed over the whole area and cell capacity should not exceed the maximum capacity of a base station. This

   modeling enables the application of standard techniques

   of colony consists of employed artificial bees and the second half includes the onlooker bees. For every food source, there is only one employed bee. In another words, number of employed bees is equal to the number of food sources. The employed bee of an abandoned food source ecomes a scout. The search carried out by the artificial bees can be summarized as follows:

   Employed bees determine a food source within the neighborhood of the food source in their memory.

   Employed bees share their information with the onlookers, within the hive and then the onlooker selects one of the food sources.

   Onlookers select food source within the neighborhood of the food source chosen by them.

   An employed bee of which the source has been abandoned becomes a scout and starts to search a new food source randomly. [7]

   In the algorithm, one half of the population consists of employed bees and another half consists of onlooker bees. During each cycle, the employed bees try to improve the food source based on the nectar amount available at the food source. An employed bee whose food source is exhausted becomes a scout bee. The scout bee then search for new food source.[9].

   The position of food source is representing solution for the optimization problem. The nectar amount of the food source is the fitness of the solution. Each solution is represented using D dimensional vector. Here D is the number of Optimization parameters. Initially SN solutions are generated randomly, where SN equals the number of employed bees. Let MCN be the maximum number of cycles that the algorithm would run. During each cycle, the employed and onlookers bees improve the solution through the neighbor search. A new solution vi in the neighborhood of existing solution xi is produced as follows:

   vij= xij + ij(xij – xkj) (1)

   Where k=1,2,SN and is the random number between[-1,1] and j=1,2,..D, k and j are chosen randomly.A greedy selection is then performed between xi and vi.

   developed for clustering. There are basically two types of

   p =

   (2)

   clustering methods: Hierarchical and partitional clustering[6]

   i

   =1

   Hierarchical clustering proceeds by merging small cluster into large one or by splitting large clusters.Partitional Clustering on the other hand attempts to decompose the data

   set into set of disjoint clusters. The cell planning can be

   Fitness is calculated as

   fiti=

   1

   1+i

   0

   (3)

   modeled in a better way using partitional clustering as we are not only interested in the local structure of the cluster (involving traffic capacity and signal strength aspects) But global structure (involving the transmission quality (C/I) of clusters also. Here in this paper first BTS are placed on the basis of Euclidean distance & then Optimization is performed.

4. ARTIFICIAL BEE COLONY ALGORITHM:

   ABC algorithm, introduced by Karaboga in 2005[7]. In ABC algorithm, the colony of artificial bees contains three groups of bees: Employed bees, onlooker and scout bees. First half

   1 + 0

   Fitness function = (1/ Path loss x attenuation) received power

   1 (4)

   The onlooker bees are placed on food source using roulette wheel selectionmethod [8]. An onlooker bee thus chooses a food source at position xi with a probability Pi calculated as follows:

   ABC algorithm flow chart:

   1. Generate the initial solutions (Position of food sources) randomly and evaluate them.

   2. For each solution xi, determine a neighbor vi using (1) and perform greedy selection between xi and vi.

   3. Calculate the probabilities for the solution using (2).

   4. Use the Roulette wheel selection method to place the onlookers on the food sources and improve the corresponding solutions.

   5. Determine the abandoned solution and replace it with new randomly produced solution.

   6. Record the best solution obtained till now.

   7. Repeat steps 2 to 6 until MCN cycles are completed.

      Figure 1: ABC flowchart

5. GENETIC ALGORITHM:

   Genetic algorithm sophisticated nature has made it an efficient searching tool as it found application in complicated problems in business,pattern recognition, scheduling etc[10].The application of Genetic algorithm in solving the telecommunications Challenges can be justified by the fact that optimal services are generic in nature; GA is an optimization tool capable of giving optimum results in situations where there are many conflicting options, this is because it has capability to search large spaces efficiently without the need for derivative information. They operate on a population of potential solutions applying the principle of survival of the fittest to produce, hopefully, better and better approximation to solution. They produce high quality solution because they are independent of the choice of the initial configuration[11].

   Figure 2: GA Flow Chart

   Initialization:

   Initially many individual solutions are randomly generated to form an initial population covering the entire range of possible solution.

   Selection:

   During each successive step, a portion of the existing solution is selected to breed a new generation. Individual solutions are selected through fitness-based process like roulette wheel selection, where fitter solution are more likely to be selected. Reproduction:

   The next step is to generate a second generation population of solutions from those selected genetic operators: Crossover (recombination) and mutation. For each new solution to be produced, a pair of parent solution is selected for breeding from the pool selected previously. New set of parents are selected each time and the process continues until a new population of solutions of appropriate size is generated.

   Termination:

   This process is repeated until a termination condition has been reached. Here the fixed number of generation reached is taken as the criteria for the termination of the program [12]. Code:

   Choose initial population Repeat

   Evaluate the individual fitness of a certain proportion of the population

   Select pairs of best ranking individuals to reproduce. Breed new generation through crossover and mutation. Continue until terminating condition.

6. PROBLEM STATEMENT:

   Main objective of the paper is to optimally locate BTS covering maximum area with minimum interference. This problem can be stated as given a colony size with potential subscriber density distribution, identify the optimal cell geometry and location of BTSs. Our problem is to optimize location of BTS with respect to each MS using ABC and genetic algorithm.ABC algorithm is used to localize BTS so

   as to cover maximum number of subscriber. The results of ABC are then compared with Genetic Algorithm. Path loss, Received Power and the attenuation are the parameters, that are considered during the process of optimization. The fitness of solution is selected on the basis of three parameters: (a) Power received, Pr (b) Path loss, Lp (c) Attenuation A[13].

   Lp = 66.55 +(26.16)log10 fc -13.82log10 hb 3.2log1011.75 hm

   + 44.9 -6.55log10 hb log10 d

   Attenuation (A) = 42.6 + 20log10f + 26 log10 d Pr = 10log10(Pt) abs(Lp).

7. RESULTS AND SIMULATIONS:

   This simulation is carried out using MATLAB 2007 a. Coverage area taken is 100 X 100.Once the site coordinates are evolved, the next step is to calculate the path loss, received power and the attenuation. The simulation is carried out using following parameter settings: Transmit power 500mW,frequency 850 MHz, BTS antenna Height hBTS is 20 to 200m and MS antenna height hMS is 1 to 10m. No of required BTS are 4 and No. of MS taken are 25.

   Figure 3: Random Location of MS & BTS

   Figure 4:Cluster formation

   Figure 5:Optimized BTS using ABC algorithm

   Figure 6: Optimized BTS using GA

   Figure 7: Fitness verses Iteration for ABC

   Figure 8: Power,Path Loss & Attenuation using GA

   Figure 9:Power,Path Loss & Attenuation using ABC

   Parameters	UsingABC algorithm	Using GA
   Received Power	678.320	379.110
   1096.470	611.756
   882.251	475.753
   686.623	387.280
   Path loss	-705.320	157.66
   	-1123.463	259.765
   	-909.5212	264.108
   	-713.623	162.978

   TABLE I:COMPARISON OF RESULT PARAMETER BETWEEN GA & ABC

8. CONCLUSION :

The aim of this paper is to optimize BTS using an Optimization Technique. The technique used here is ABC that works efficiently to determine optimal location of BTS by considering parameters like Received power, path loss and attenuation. The result of this Optimization technique is also compared with GA algorithm. The comparison is showing that ABC is giving better result in term of received power and path loss.It means that ABC is more efficient and effective technique in providing Optimal location of BTS with maximum coverage.

REFERENCES

1. [1].K. Tutschku Demand-based radio network planning of cellular mobile communication system. In INFOCOM 98 Seventeenth Annual Joint Conference of the IEEE computer and Communications Socities. Proceedings. IEEE,volume 3,pages 1045-1061,IEEE,1998.

2. [2].X. Huang U. Behr and W.Wiesbeck, A new approach to automatic base station placement in mobile networks, in proceedings of International Zurich seminar on broadband Communication, pp. 301-306,2000a.

3. [3].P.Assunaco,R.Estevinho and L.M Correja, Assessment of Cellular Planning methods for GSm,conftele 2001,Figueira da Foz.

4. [4] R. Mathar and T.Niessen.Optimum positioning of base stations for cellular network.Wireless Networks,6(6):421- 428,2000.

5. [5]J.Laiho,A.Wacker and T. Novosad,Radio network planning and Optimization for UMTS,1st edition,J.wiley and Sons Ltd,India,2002

6. [6] K.Alsabti,S.Ranka and V.Singh, An efficient K-Means Clustering Algorithm.,Proc. of High Performance Data Mining,1988.

7. [7].D. Karaboga and B. Basturk, A powerful and efficient algorithm for numerical function Optimization:Artificial bee colony (abc) algorithm, Journal of Global optimization,39(3): 459-471,2007

8. [8].D.E Goldberg and K. Deb A comparative analysis of selection schemes used in genetic algorithm Urbana,51:61801- 2996,1991.

9. [9].H. Narasimhan, Parallel artificial bee colony (pabc) algorithm In nature & Biological Inspired Computing, NaBIC 2009. World congress on pages 306-311.IEEE,2009.

10. [10] Hishamuddin J.(2011)lecture notes on Genetic Algorithm,Faculty of Mechanical Engineering Universiti Teknologi Malaysia.

11. [11] Tomonobu Senjyu, Daisuke Hatashi,Naomitsu Urasaki,Toshihisa Fubabashi, Optimum Configuration for renewable generating Systems in Residence using genetic Algorithm, IEEE trans on Energy Conversion,Vol. 21, No. 2,pp. 459-466, June 2006.

12. [12] Ioannis G. Damousis, Anastasios G. Bakirtzis, and Petros S. Dokopoulos, Network-Constrained Economic Dispatch using Real coded Genetic Algorithm, IEEE trans on power Systems, Vol. 18, No. 1, pp 198-205, February 2003.

13. [13]S.R Saunders M. hata, Empherical Formula for Propagation Loss in land Mobile radio Service, IEEE Transaction on Vehicular