Research on Site Planning of Mobile Communication Network

Yunshuo Chen, Fanqiang Fu^*

Zunyi Vocational and Technical College, Zunyi, China.

DOI: 10.4236/jamp.2022.109181                

Abstract

With the development of 5G technology, network communication has become the most commonly used tool in People’s Daily life and production. Due to the huge user base, the problem of site selection of communication network has become more and more complex. This paper mainly studies the problem of mobile communication network site planning, using 0 - 1 planning knapsack model, heuristic algorithm, simulated annealing algorithm and other methods, combined with MATLAB software to effectively solve the location of site coordinates and the type of base station selection, give the optimal results of site selection. It has certain guiding significance to mobile communication network site planning.

Keywords

Mobile Communication, Knapsack Model, Heuristic Algorithm, Simulated Annealing Algorithm, MATLAB Software

1. Introduction

With the rapid development of the Internet, mobile communication technology has achieved unprecedented development. Mobile communication has become the main way for people to communicate. Industries and enterprises hope to reduce costs, improve market response efficiency and labor productivity through mobile communication technology. However, how to choose the location of the base station to maximize the coverage of the site and minimize the cost has become the most critical problem of the mobile communication system. The location and configuration of early base stations were usually selected by network engineers based on personal experience and field measurements, but this was often far from the actual optimal site. Although the emergence of digital maps provides favorable information to network engineers, they can only be used for coverage analysis and prediction, which still needs repeated verification by engineers [1]. Therefore, how to carry out base station planning has attracted extensive attention of experts at home and abroad.

In 2001, Jin K.H. et al. proposed a new representation method to describe the location of the base station with real numbers by introducing a new genetic operator on the base station planning problem, which could describe not only the location of the base station, but also the number of base stations. Experimental simulation results show that the algorithm can find the nearly optimal base station layout and the effective number of base stations [2]. In 2002, K. Tutschku presented an engineering approach to demand-based wireless network design for cellular mobile communication systems. A new discrete population model is used to describe traffic, and then the concept of demand node is proposed. The transmitter localization task can be formulated as the maximum coverage localization problem (MCLP) by using this concept, and the MCLP problem is solved by the greedy heuristic set cover base station positioning algorithm (SCBPA) [3]. In 2004, Sheng Zhong et al. proposed a base-station distribution planning Algorithm for CDMA network based on cost control based on Genetic Algorithm. The algorithm takes into account many planning objectives and requirements in the actual project of CDMA network planning, and can find the base station distribution scheme that meets the needs of CDMA network construction. Experimental results show that the algorithm can further reduce the possibility of falling into local optimal solution, and also improve the convergence speed [4]. In 2005, Larry Raisanen et al. used greedy algorithms to select and configure base station locations in the NP-hard optimization problem of antenna placement, while comparing the capabilities of four state of the art multi-objective genetic algorithms, giving the results and performance discussion of the algorithms [5]. In 2009, Cunxiang Chen et al. proposed an improved search direction based on the idea of particle swarm optimization (PSO) algorithm, and applied the improved algorithm to the research of base station distribution planning. The simulation results show that the improved algorithm can improve the base station coverage and reduce the economic cost [6]. In 2016, Ying Chao et al. proposed a base station planning optimization method based on accelerated genetic algorithm on the base station distribution planning problem. Compared with the traditional algorithm, the algorithm has fast convergence speed, high accuracy of the optimal solution, avoids premature convergence, and can effectively provide the optimal base station location distribution scheme in line with the requirements of network construction [7].

In the past decades, although there has been a lot of in-depth research on the problem of mobile communication network site planning, and many excellent results have been achieved, the research on this problem still has very important application value in view of the large user base of network communication, high social attention and large economic benefits.

The first section of this paper mainly introduces the background of network site planning and the research status at home and abroad; the second section mainly gives the paper’s needs to solve the problem; the third section mainly gives the hypothesis of the model for solving the problem; the fourth section mainly introduces the model establishment process and the results obtained in the problem solving; the fifth section mainly summarizes the advantages and disadvantages of the model.

2. The Question Is Raised

The rapid development of mobile communication technology and the increasing operation scale bring about more and more complex communication network. With the development of 5G, the bandwidth of communication is getting larger and larger, but the coverage area of base stations is getting smaller and smaller, which makes the number of base stations needed to cover the same area become more and more.

The site selection problem is: according to the coverage situation of the network antenna, a certain number of points can be selected for the weak coverage area of the network, so that the coverage problem of the weak coverage area of the network can be solved after building a new base station on these points (for details, see Question D of the 12^th MathorCup University Mathematical Modeling Challenge in China).

Issues to be discussed: according to the given information and the attached data, the site planning is conducted, so that 90% of the total business volume of the weak coverage points is covered by the planned base station. Given the coordinates of the selected site and the base station types selected for each site.

3. Model Hypothesis

1) Assume that the screened data can reflect the overall base station construction.

2) It is assumed that the influence of subjective factors is ignored when considering the construction cost.

3) Assume that the data indicators given in the title are objective and true.

4. Model Establishment and Solution

4.1. Abbreviations and Acronyms

As for the selection of base stations, the selection of base stations can only be selected or not selected, so it belongs to the 0 - 1 knapsack planning problem. It is necessary to select the items with the highest value within a certain weight range, so the base station with the largest service volume is preferentially selected, and the objective function is solved by the heuristic algorithm. See Figure 1 for the problem solving flow chart.

4.2. Data Cleaning

Firstly, the coordinates of the existing weak coverage points are cleaned according to the two-norm formula. According to the formula:

Figure 1. Problem solving flowchart.

${\Vert P-P_0\Vert }_2=\sqrt{{\left(x-x_0\right)}^2+{\left(y-y_0\right)}^2}\le 10$ (1)

On the basis of the existing base station, the weak coverage points with threshold less than 10 are eliminated, and the calculation results are shown in Table 1 below.

Considering the service quantity and computational efficiency of each weak coverage point, we screened out the weak coverage points with service quantity less than 1 and removed them, and 56,925 data were deleted from 182,807 data. The data visualization after cleaning is shown in Figure 2 and Figure 3.

4.3. Model Establishment

The base station location problem is classified as the knapsack problem [8]. For this problem,n base stations need to be selected (the total price of the base station is the cost, which is the knapsack capacity), and the service quantity of base station j is w_j and the cost is s_j. Assume that both the service quantity and service cost of the base station are non-negative, and the maximum total service quantity is W.

So that 90% of the total traffic of the weak coverage point is covered by the planned base station. For planning the choice of macro base station or micro base station, 0 - 1 variables are introduced: $p_i,q_i$.

Make it satisfied:

$p_i,q_i=\{\begin{array}{l}0,\text{dicates that the base station is not selected}\\ 1,\text{Indicates that the base station is selected}\end{array}$

Let $V\left(i,j\right)$ represent the maximum base station service quantity of j that can

Table 1. Solving Euclidean distance results for existing base stations and weak coverage points.

Figure 2. Weak coverage point visualization.

Figure 3. Data cleaning comparison.

be selected among the first i base stations, then the dynamic programming function can be obtained as follows: $V\left(i,0\right)=V\left(0,j\right)$ put the first i items into knapsack with capacity 0 and 0 items into knapsack with capacity j, and the value is 0.

$V\left(i,j\right)=V\left(i-1,j\right),j<w_j$. If the service quantity of the ith base station is greater than the total service quantity $j<w_j$, the maximum service quantity obtained by selecting the first i base stations is the same as that obtained by selecting the first $i-1$ base stations, that is, base i is not selected.

1) If the i^th base station is selected, the total service volume of the base station is equal to the value of the first $i-1$ base station in the backpack with the capacity of $j-w_i$ plus the service volume of the CTH base station v_i;

2) If the i^th base station is not selected, the service volume in the new base station is equal to the value obtained by loading the previous $i-1$ base station into the backpack with capacity j. Take the more valuable of the two. Then consider each iteration:

Step 1: Select only the first base station to determine the maximum value of the total service volume under various circumstances;

Step 2: Select only the first two base stations to determine the maximum value that can be obtained by the total service volume under various circumstances;

……

Step n: Select only the top n base stations to determine the maximum value that can be obtained by the total service volume under various circumstances.

Finally, $V\left(n,W\right)$ is the maximum value obtained when loading n items into a knapsack of capacity W.

In order to get the $V\left(n,W\right)$, need to push forward to $V\left(n-1,W\right)$. If $V\left(n,W\right)>V\left(n-1,W\right)$, is the first n base station into the backpack, $n-1$ base station before loading capacity of $W-w_j$ backpack. Otherwise, the NTH base station is not loaded into the knapsack and the first $n-1$ base stations are loaded into the knapsack with capacity W.

Until it is determined whether the first base station is selected. On this basis, a 0 - 1 integer programming model with maximum business volume is established. The decision variables, objective functions and constraints in the model are as follows:

Decision variable: coordinates of new base station;

Objective function: the total business volume of the new base station;

Constraint condition:

1) The Euclidean distance between the new base station and the weak coverage point is less than 30 or 10;

2) The threshold between two new base stations or between the new base station and the weak coverage point is not less than 10;

3) The choice of base station is 0 or 1;

4) For each weak coverage point, the sum of macro base stations or micro base stations should be less than or equal to 1.

To sum up, we can obtain the basic model as follows:

$\max W={\displaystyle {\sum }_{i=1}^n{w}_j{p}_i}+{\displaystyle {\sum }_{i=1}^n{w}_j{q}_i}$ (2)

$\text{s}\text{.t}\{\begin{array}{l}{\displaystyle {\sum }_{i,j=1}^n{w}_j\ast p_i}+{\displaystyle {\sum }_{i,j=1}^n{w}_j\ast q_i}\ge 6350607\\ p_i=0,1\\ q_i=0,1\\ \sqrt{{\left(x-x_0\right)}^2-{\left(y-y_0\right)}^2}\le 30,\left(x\text{and}y\text{belong to Acer stations}\right)\\ \sqrt{{\left(x-x_0\right)}^2-{\left(y-y_0\right)}^2}\le 10,\left(x\text{and}y\text{belong to the microbase station}\right)\end{array}$

4.4. The Simulated Annealing Algorithm Solves the Dynamic Programming Model

In view of the particularity of the problem in this paper, the simulated annealing algorithm is selected as the solution method [9]. The simulated annealing algorithm has two layers of cycles. In cycle 1, a new solution is generated by repeated iteration. At any temperature in the cooling process, a new solution is generated by random disturbance, and the change of the objective function value is calculated to determine whether it is accepted or not. Loop two: slow cooling and repeat the iterative process. After the iteration is completed at a fixed temperature, the temperature is slowly lowered so that the algorithm may converge to the global optimal solution.

Due to the relatively high initial temperature of the algorithm, through the iterative process of loop 1, the new solution that increases E may be accepted with a certain probability at the beginning, so that the local minimum can be jumped out. In addition, although the receiving function is very small at low temperature, it is still possible to accept worse solutions. Therefore, the best feasible solution (the historical optimal solution) encountered in the annealing process is also recorded, and it is output together with the last accepted solution before the termination of the algorithm, so as to avoid missing the optimal solution.

In application, the annealing process is controlled by a set of initial parameters, namely the cooling Schedule, whose core is to make the system reach quasi-equilibrium as far as possible, so that the algorithm can approach the optimal solution in limited time. The cooling progress parameters of the simulated annealing algorithm are shown in Table 2.

The solution flow chart of the simulated annealing algorithm is shown in Figure 4.

Table 2. Simulated annealing cooling schedule.

Figure 4. Flowchart of simulated annealing algorithm.

Parameter selection:

1) Selection of control parameter T_i and initial value T₀

We choose T_i for each time the system cools down. The solution corresponding to each control parameter T_i is x_i According to the preliminary analysis of the global optimal solution and search range, combined with the size of the problem, we choose the initial value T₀ to be 0.5.

2) Decay function of control parameter R_i

Because of the particularity of this case, we construct a special attenuation function to “cool down” the program

$\{\begin{array}{l}{T}_{i+1}=T_i-1\left(T_i\ge 1\right)\\ T_{i+1}=T_i-0.1\left(T_i<1\right)\end{array}$

Commonly used attenuation function of $T_{i+1}=\alpha T_i,i=0,1,2,\cdots$ , which can be α value of 0.5 ~ 0.99.

3) Markov chain length [10]

It is known that the length of Markov chain should be selected to reach a quasi-equilibrium state at each value of the control parameters. For simple cases, $L_i=100n$ can be set directly. Here we set $n=5,L_i=500$.

4) Acceptance function

$p\left(i\Rightarrow j\right)=\{\begin{array}{l}1,\text{if}f\left(i\right)\le f\left(j\right)\\ {\text{e}}^{\frac{f\left(i\right)-f\left(j\right)}{k{L}_i}},\text{else}\end{array}$

In the case of high temperature where L_i is relatively large, the denominator of the index is relatively large, and it is x_i negative index at this time, so the acceptance probability is close to 1, that is, the new solution x_j, which is worse than the current solution A, may also be accepted, thus providing the possibility to jump out of the local optimal solution.

5) Stop conditions

$L_i=L_f=0.1$

At high temperature, a wide area search has been conducted enough to find the region where the best solution may exist, while at low temperature, a local search has been conducted enough to find the global optimal solution, so L_f is set to a small enough number. Finally, the values of the cooling schedule are shown in Table 3.

Table 3. Simulated annealing cooling schedule.

Finally, MATLAB [11] [12] was used for programming and solving. The iterative results are shown in Figure 5.

After iteration, the calculation results are shown in Table 4 and Table 5.

Figure 5. Simulated annealing iteration results change.

Table 4. Acer station operation result.

Note *: due to the limited space, only 15 base station coordinate points are displayed

Table 5. Site selection of micro-base station coordinates.

Note *: due to the limited space, only 12 base station coordinate points are displayed.

Finally, it is calculated that 3302 macro base stations and 216 micro base stations need to be built, and the total cost is 33236. The proportion of the business volume of new base stations in the total business is 91.087%. The Euclidean distance is enlarged by 30 times for visual analysis, As shown in Figure 6 and Figure 7.

Thus, the site selection scheme meets the requirements.

5. Comments on the Model

The site planning problem is a typical dynamic programming—0 - 1 knapsack model, take heuristic algorithm dynamic solve to meet the limitation conditions site coordinate location and base station type selection, in the process of using the simulated annealing algorithm, simulated annealing algorithm compared with previous approximate algorithm, running efficiency is high and less by the initial conditions constraints, but if the index data volume will be affected on convergence speed, the algorithm may find local optimal solution optimal, the result is not the global optimal.

Figure 6. Acer station distribution visualization.

Figure 7. Visualization of micro-base station distribution.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Wang, W.T. (2015) Research on Modeling and Algorithm of Base Station Location Optimization Problem in Wireless Communication Network. Northeastern University, Boston.
[2]	Jin, K.H., Park, B.S., Yong, S.C., et al. (2001) Genetic Approach with a New Representation for Base Station Placement in Mobile Communications. Vehicular Technology Conference IEEE, Atlantic City, 2001, 2703-2707.
[3]	Tutschku, K. (2002) Demand-Based Radio Network Planning of Cellular Mobile Communication Systems. Proceedings. IEEE INFOCOM ‘98, the Conference on Computer Communications. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, 2002, 1054-1061.
[4]	Zhong, S., Wang, C.J. and Wang, G.X. (2004) Application of Genetic Algorithm in CDMA Network Base Station Distribution Planning. Post and Telecommunications Design Technology, 6, 9-13.
[5]	Raisanen, L. and Whitaker, R.M. (2005) Comparison and Evaluation of Multiple Objective Genetic Algorithms for the Antenna Placement Problem. Mobile Networks and Applications, 10, 79-88. https://doi.org/10.1023/B:MONE.0000048547.84327.95
[6]	Chen, C.X. and Wang, J.F. (2009) Application of Particle Swarm Optimization Algorithm in Base Station Distribution Planning. Computer & Telecommunications, 6, 45-46.
[7]	Chao, Y., Qin, X.Z. and Cao, C.L. (2016) Application of Accelerated Genetic Algorithm in Mobile Communication Base Station Planning. Journal of Xinjiang University: Natural Science Edition, 33, 94-98+101.
[8]	Wang, Q.F. and Liang, D.L. (2013) An Algorithm for Solving 0-1 Knapsack Problem. Computer Technology and Development, 30, 33-37+57.
[9]	Zhang, J. and Yang, X.L. (2017) Mobile Communication Network Self-Planning Based on Simulated Annealing Algorithm. Computer Engineering, 34, 5.
[10]	Jiang, Z.J., Zhao, X.S., You, X.H., et al. (2007) A Dynamic RAU Selection Model for Remote Antenna Elements in Distributed Radio Mobile Communication System. Journal of Electronics and Information Technology, 29, 305-309.
[11]	Han, Z.G. (2009) Mathematical Modeling Method and Its Application. Higher Education Press, Beijing.
[12]	Jiang, Q.Y. (1987) Mathematical Models. 2nd Edition, Higher Education Press, Beijing.