Abstract
In order to solve the contradiction between spectrum resource and system capacity in the mobile communication system and the radius of the housing estate has been decreasing, the microcell has appeared. In this article, the scheme which combined ray tracing and genetic algorithm were studied to solve the problem of urban microcellular network planning. The author used the ray tracing to calculate the propagating characteristics of the micro-cellular scene in a precise way and the genetic algorithm to find the specific location of the urban microcellular base station. And at the same time, basing on the characteristics of the site selection of the urban microcellular base station, the improved genetic algorithm which proposed in the literature was adopted. The final study shows that basing on the simulation of urban microcells, combining with the scheme of the ray tracing and improving genetic algorithm can solve the problem of urban microcell location.
Introduction
The rapid development of personal communications requires that mobile communication systems have higher system capacity, while wireless spectrum resources are extremely scarce. To solve the contradiction between wireless spectrum of scarce resources and the increasing system capacity, the concept of district division has been put forward. And meanwhile, cell radius has been reducing constantly, and the micro honeycomb and microcellular have been come out. Network planning issues are very important for microcellular system design, such as base stations site selection. To solve this problem, it is necessary to accurately predict the propagation characteristics of the micro-cellular scenes.
The statistical model is used to predict the propagation characteristics of the radio waves in the scenes of macro cellular. The statistical model is based on a large number of measured results. In a typical macro-cellular scene, the transmitting antenna is higher than the surrounding buildings, and the receiving antenna is blocked by a large number of obstacles. For this scenario, the statistical model can be used to obtain the accurate prediction results of the radio wave propagation characteristics [1] But in the micro honeycomb and microcellular scenes, the transmitting antenna is lower than the surrounding buildings. The statistical model cannot accurately predict the radio wave propagation characteristics of microcellular scenes, and it is not suitable for the network planning of micro-cellular scenes.
In order to solve the above problems, the researchers proposed a ray tracing model which was based on geometrical optics to accurately predict the propagation characteristics of the micro-honeycomb scenes. Ray tracing can identify all possible propagation paths between sending and receiving antenna in the micro-cellular scenes, And according to the theory of electromagnetic wave propagation, ray tracing can calculate the range, the phase position, the angle and delay information of each ray that reaches the receiving antenna. Now, the ray tracking model is used to predict radio wave propagation characteristic of the dense urban areas. For example, considering the complex urban communication environment, Huawei company in Hong Kong UMTS commercial network in wireless network planning uses the ray tracing to make an accurate network planning and effectively control the interference,. The average value of the difference of the predicted results and the actual coverage test results was 0.05 dB and the standard deviation was 7.13 dB. This indicates that the prediction accuracy of the ray tracking model is very high.
State of the art
Based on the accurate prediction of the radio wave propagation characteristics, the optimal solution of the multi-objective NP hard programming problem can be obtained by intelligent search algorithm. One of the characteristics of multi-objective planning problems is that the solution is often more than one, but the equilibrium solution of a group of compromises between multiple targets, which is often referred to as Pareto optimal solution set. The performance evaluation index of intelligent search algorithm is the representative Pareto solution set [2] which can obtain more and more uniform distribution. That people commonly use intelligent search algorithms can be divided into two categories: genetic algorithms and non-genetic algorithms. Aiming at different communication scenarios (macro honeycomb, microcells), domestic and foreign scholars have put forward a lot of solutions to solve the base station location problem by using genetic algorithm or non-genetic algorithm. Genetic algorithms have great advantages in addressing the location of base stations, but there are problems, such as, late searching dully and premature convergence (easily converge to local optimal solution instead of global optimal solution). Through continuously improve coding method, fitness function, selection operator, crossover operator and mutation operator of genetic algorithm, the researchers propose many improved genetic algorithms that can quickly converge to the global optimal solution, some of them are popular, such as, SPEA2, NSGA-II, PESA and SEAMO [3]. An improved genetic algorithm can be used to search the optimal solution of base station location problem with faster global convergence rate. The following are introduced about the application status of genetic algorithm in the site selection of macro cell and microcellular base stations.
The improved genetic algorithm is fast and efficient, but it is easy to converge to the local optimal solution instead of the global optimal solution. Some scholars have proposed an improved genetic algorithm which comprehensively consider of the volume of business, the fraction of coverage and cost about outdoor micro cell. The improved genetic algorithm is used to encode the 3d vector distribution of the number and location of base station and the emission power of base station, and adopts the selection operator which can guarantee optimal capacity and the climbing operator which can prevent local convergence. The improved genetic algorithm can converge to the global optimal solution, but the simulation time is longer.
Methodology
Analysis of the propagation characteristics of radio waves under urban microcells
On the basis of accurately predicting the propagation characteristics of the urban micro-cellular scene and the further problem is the site selection problem. However, the problem is difficult to make multi-objective NP. Genetic Algorithm (based Algorithm, GA) is random searching method which learns from the evolution of biology, and it has inherent parallelism and good global searching ability. And at the same time, it can automatically obtain and guide the planning of search space. Experience shows that genetic algorithm is very effective to solve the hard programming problems about multi-objective NP [4]. This article imitation researches the application of genetic algorithm in base station location.
All this time, network planning issues have been a hot topic in domestic and foreign researchers, such as base station site selection. In order to solve the problem about cell site placement, the wave propagation characteristics of the scene need to be accurately predicted. Aim at solving the problem of the network planning in different scenarios, the prediction model of the wave propagation characteristic is shown in Table 1.
Radio wave propagation prediction model for different propagation scenarios
Radio wave propagation prediction model for different propagation scenarios
As shown in Table 1, the statistical model is applicable to predict the wave propagation characteristics of macrocell but it is not applicable to microcell. Aiming at this problem, many scholars have proposed many different prediction methods which was based on specific location. It includes measured equation of invariance (Measured Equation of Invariance, MEI), finite-difference time-domain method (Finite Differential Time Domain, FDTD) and ray tracing method which has been based on geometrical theory of diffraction and uniform theory of diffraction. MEI and FDTD are numerical computation method and their prediction accuracy is high, but the computation is large, the simulation time is long. Therefore, MEI and FDTD are seldom used to predict the wave propagation characteristics of urban microcellular scenes. However, ray tracing can overcome the shortcomings of statistical model well, and it can predict accurately and quickly the propagation characteristics of the urban microcellular scene. In order to reduce computational complexity, ray tracing can be combined with artificial neural networks [5].
Free space propagation is the simplest transmission mechanism. Strictly speaking, the free space is the vacuum, but the infinite space which is full of homogeneous and non-destructive medium is called free space. The space has many traits, for example, the space is isotropic, specific conductance σ is 0 and relative dielectric constant ɛ
r
and relative permeability μ
r
are 1. In the propagation process, the radio waves will not show the phenomena of refraction, diffraction, reflect and scattering. Therefore, the propagation loss which is due to the diffusion of the radio waves is only considered. In free space, if the emitter is a spherical wave radiation energy, Receiving power P
r
at the receiving point is:
In this formula, G
t
and G
r
are the gain of transmitting antennas and receiving antennas; λ is the wavelength; D is the propagation distance between the transmitting antennas and the receiving antennas; It is a system loss factor that is independent of propagation. Free space propagation loss P
L
can be defined as the path loss under the free space propagation model
In formula (2), we can see that propagation loss (attenuation) in free space only has to do with the working frequency f and the propagation distance d. When f or d doubles, free space propagation loss P L (dB) will add 6 dB.
There are many advantages when the genetic algorithms are used to solve multi-objective programming problems, such as group searching and global search, and it is very suitable for solving the problem of siting of urban microcellular base station. However, in the optimization process, the genetic algorithm is not able to overcome the problems of slowly searching and premature convergence, and the calculation is larger, the simulation time is longer. Therefore, to fast converge the global optimal solution of the base station location problem, suitable improved genetic algorithm is needed. The running flow of genetic algorithm is shown in Fig. 1.
Flowchart of genetic algorithm.
Firstly, the author introduces the solution of the location of microcellular base station. Then, according to the characteristics of the location planning of the urban microcellular base station, the global optimal solution for selecting the location of the base station is selected by using the appropriate improved genetic algorithm. This improved genetic algorithm has optimized the traditional genetic algorithm from coding method selection, initializing population, designing fitness function and improving genetic operator, and it has faster convergence speed. And meanwhile, it can effectively avoid the problems of late searching dully and premature convergence [6]. Finally, giving a simulation example, this example applies the scheme which combines ray tracing and the above genetic algorithm to solve the siting of urban microcellular base station. The results show that the scheme is feasible in the cell site placemen problem.
The traditional genetic algorithm uses the selection probability which is proportional to the individual fitness to determine the chance of the genetic inheritance of individual genes in the current population to the next generation. To evaluate this probability correctly, the fitness of all individuals must be non-negative. Therefore, for different types of problems, it is necessary to predetermine the conversion rules of the objective function value to the individual fitness value.
Proportional selection operator makes use of probable value what is proportional to the individual fitness to decide the possibility of genetic inheritance. Let’s say the population is M and the fitness of individual i is f i so that the probability P i that the individual i is selected and it shows in equation (3).
The individual choice probability is given, and then generate the evenly distributed random number between [0,1] to decide which of the individual to take part in two mating. If the individual selection probability is large and it’s likely to be selected multiple times, so its genetic genes are likely to expand in the population; If the individual selection probability is small and the probability of being selected is small, so its genetic genes may be phased out.
Genetic algorithm is an efficient, parallel and global search method. This algorithm can automatically acquire and accumulate the characters of search space during the search process and adaptively control of the search process to obtain the optimal solution. Genetic algorithms use the principle that is survival of the fittest to produce successively the scheme about an approximate optimal solution in the potential solution population.
In each generation of genetic algorithms, the individual was selected based on the individual fitness value in the problem domain and the reconstruction method borrowed from natural genetics and then we have a new approximation. This process will lead to individual evolution in the population, and the new individuals that we get have a better environmental adaptability than the original individuals [7]. For different problems, the researchers have been designed different coding methods to represent the feasible solutions to the optimization problem, and many different coding forms put forward to simulate the biological characteristics of different environments. Thus, in this way, different coding methods and different genetic operators constitute different genetic algorithms. Table 2 is a comparison of the terminology of genetic algorithm and the language of natural genetics.
Comparison of basic expressions in natural genetics and genetic algorithms
Comparison of basic expressions in natural genetics and genetic algorithms
In order to quickly obtain the optimal solution for the location planning of urban microcellular base station, the author has been further studied the improved genetic algorithm. The genetic algorithm is based on John Holland’s Schema Theorem and Building Block Hypothesis. Schema Theorem ensures that the samples of the superior model (the better solution of genetic algorithm) are increasing exponentially to meet the probability of the genetic algorithm search the global optimal solution; Building Block Hypothesis indicates that the genetic algorithm has the ability to search the global optimal solution, and it can generate a model that is high order, long haul and high average fitness. Finally, global optimal solution is generated. Schema Theorem and Building Block Hypothesis explain the working mechanism and mathematical characteristics of genetic algorithm [8].
To fit John Holland’s Schema Theorem and Building Block Hypothesis, the coding method of genetic algorithm that is used to site selection about urban microcellular base station must meet the following four conditions:
P1: A genome contains not only the location of all base stations, but also the number of base stations;
P2: A chromosome represents the location of a base station;
P3: The base station may be placed in an infinite position, so the site selection should have numerous options;
P4: A base station with a similar geographic location should have similar genotypes.
To satisfy the above conditions, The coding method selected in this paper is shown in Fig. 2.
Schematic diagram of real coding method.
A genome can be used as a vector g = (c1, c2, …, c k ), K is the maximum number of base stations allowed, chromosome c k = (x k , y k , z k ) represents the location of the k base station. The above design meets the conditions P1 and P2. If the l base station does not exist, chromosome c l will be set as NULL. And in order to meet the conditions P3 and P4, x k , y k and z k must be real number, and x k ∈ [Xmin, Xmax], y k ∈ [Ymin, Ymax], z k ∈ [Zmin, Zmax].
To test the convergence and stability of the algorithm, make a city college town as the target area to plan base station layout. Let’s say the neighborhood is about 1400 m×1400 m, the base station uses an omnidirectional antenna and its cover area is circular area. For the city, the base station coverage radius of the microcellular network is 100 m∼1000 m, its cost is measured by the number of base stations [9]. First, the GAOT genetic algorithm toolbox function is used to optimize the base station layout and get the strength of every point in the community. he required parameters are shown in Table 3.
Parameters of GAOT simulation of traditional genetic algorithm
Parameters of GAOT simulation of traditional genetic algorithm
If the community has three base stations to cover, so the length of the individual is 4, and the initial population size is 10. The population corresponds to the layout of 10 base stations, with the reverse order cross and increasing the reversion of the mutation factor, the best coverage will be 92.24% after 10 generations of evolution. Now, the base station layout is (1125.8268, 518.3140), (574.0611, 1214.0243), (249.4222, 198.3717). If you do not increase the second inversion inverse mutation factor, the best coverage of the 10 generations is 90.56%.
In the scenario modeling process, the roof is assumed to be flat and ignores doors and windows and surrounding trees. If a transmitting antenna is located at the center of the scene, and that the position of the receiving antenna relative to the transmitter is shown in Fig. 3. The simulation parameters are set as follows: The transmitting antennas and receiving antennas are all ideal antennas; Transmitting antennas and receiving antennas are vertically polarized mode; The working frequency is 900 MHz; Tthe launch power is 10 W; If the materials on the surface of each building are the same, its conductivity is 0.01 S/m, the magnetic conductivity is 1 H/m, and the dielectric constant is 5 F/m; Receiving antenna height is 1.5 m; The launch antenna height is 15 m. A ray tracing model is used to obtain the transmission path of all the radiation between the transmitting antenna and the receiving antenna, in an outdoor micro-cellular environment, The software considers directing glare, reflect, diffraction and some combinations about reflect and diffraction.
3d solid view of urban microcellular.
When the radio waves travel through wireless channels, due to stop of the obstacles between transmit and receive antenna, the transmitting signal will reach the receiver along the different propagation path [10]. Different ray paths have different phases and ranges, and the receiver is reached with different incident Angle and propagation delay which causes the extending about the angle of receiving the signal and delay.
In this paper, the propagation characteristics and channel model of urban microcellular cell are analyzed firstly, and it mainly introduces this deterministic prediction method of the ray tracing of radio wave propagation. Then, on this basis, a suitable improved genetic algorithm has been used, and applies it to urban microcells, and a simulation example of using the genetic algorithm and ray tracing to solve the base station location is presented. The main work of this article includes the following: with the location of urban microcellular base station, study the solution that is based on ray tracing and genetic algorithm. Because the traditional genetic algorithm has the problem of late searching dully and premature convergence, this paper has been introduced the improved genetic algorithm, this algorithm optimizes traditional genetic algorithms by coding method selection, designing fitness function and improving genetic operator, and it has a faster convergence rate. What’s more, it can effectively avoid the problems of late searching dully and premature convergence. Aiming at the concrete scene simulation of urban microcell, this paper has been studied the effectiveness of genetic algorithm and ray tracing method.
The urban wireless network planning system developed in this paper should be further improved, for example, the global convergence rate of genetic algorithm is improved for microcellular network planning. And meanwhile, in view of indoor communication environment, the visualization software of indoor network planning which is based on ray tracking and genetic algorithm can be developed.
Footnotes
Acknowledgments
The study was supported by the foundation of Scientific and Technological Research Project in Guangxi Universities of Guangxi Education Department KY2015YB516.