2.1

Selection and processing of research subjects

In this paper, the existing network coverage in the Nanping area of Nan ‘an District, Chongqing, China (as shown in the figure below, where the red part was the weak coverage area) was selected as the object of study. For the purpose of calculation, the area was divided into small grids, and only the center point of each grid was considered. In total, the area was divided into 2500*2500 grids, i.e., 2500*2500 points.

Figure 1.

The existing network coverage in the Nanping area of Nan’an District, Chongqing

2.2

The idea of binary mask

In the process of building the model in this paper, we found that the coverage of the base station and the limited area of the threshold had the same characteristics, which was that the center point of a certain area can affect the state of all the points around a certain range at the same time. Before the operation and processing, if we could integrate each such area into a whole through this characteristic, we would greatly reduce the number of operations in our solution process. Therefore, This paper proposes an idea for the operation of matrices based on a template such as the binary mask in the field of image processing, named the idea of binary mask.

The idea was essentially the construction of a matrix model that represents some specific weights in terms of differences in the values of the elements at each position, an example of which is given.

In this case, a binary mask-sized area on the area matrix, which was all 0, is changed to the desired value at the same time. The value of each element in the binary mask could be adjusted to suit the actual function.

2.3

Multi-objective planning modeling

2.3.1

Determination of the objective function

The coverage range of the macro base station was 30 and the cost was 10, the coverage range of the micro base station was 10 and the cost was 1. Therefore, the multi-objective planning model had two optimization objectives, the first optimization objective was the total cost of macro base stations and micro base stations should be as low as possible, the mathematical expression was:

Where h_i,,w_i denoted the i^th macro base station and the i^th micro base station, respectively, and j,k denote the corresponding number of stations.

The second objective to be optimized was for the base station to cover the weak coverage area with the highest possible total service volume, expressed as:

where S was the total business volume in the weak coverage area.

To apply the algorithm better, a certain simplification of the objective function was needed to reduce the dual objective to a single objective, which was handled by dividing the total cost by the proportion of business volume covered to obtain an expression for the unit cost under the coverage proportion.

2.3.2

Determination of Constraints

The threshold distance not only limited the distance between the new base station and the original base station to no less than 10, but also includes the distance between the new base station and the new base station to no less than 10, from which the following constraints could be obtained.

2.4

Differential Evolution (DE) algorithm

The DE algorithm was a heuristic random search algorithm based on population differences. The basic principle of this algorithm was similar to the genetic algorithm. Meanwhile, it could avoid to some extent the shortcomings of the genetic algorithm variant approach. The DE algorithm process could be summarized in four steps: initialization, mutation, crossover and selection.

2.4.2

Variation operations

The mutation operation was an extremely important part of the DE algorithm. It was the signature difference compared to the genetic algorithm, which first randomly selected two individuals from the population to perform the following operation.

Where i,j was the j^th individual of the dimension and m,n are two random integers in the range 1 and N.

2.4.3

Crossover operation

2.4.4

Select operation

The specific flow chart of the algorithm is as follows.

Figure 2.

Flow chart of differential evolution algorithm

The differential evolution algorithm had several advantages over traditional optimization algorithms.

• ● Good generality and ease of integration with multiple models to create better models for better processing results.

• ● The relatively small number of control parameters and the relative simplicity of the DE principle made it easier to implement and operate accordingly.

• ● The algorithm was highly adaptable, robust and had excellent global search capabilities.

• ● There was a certain degree of parallelism within the algorithm, so that the DE algorithm was able to demonstrate superior computational efficiency when performing large-scale processing, greatly reducing the time cost of solving the problem.

3.1

Data filtering

The siting of new base stations should be based on the existing network base station layout. The same grid could not be used to establish more than one base station at the same time, and the distance between the different base stations must be greater than the threshold 10. Therefore, we needed to filter the points in the area using the coordinates of the existing base stations to get all the coordinates of all the base stations that could be set up under the threshold conditions.

First, a 21*21 binary mask matrix was defined based on the length of the threshold at a distance of 10. Because the threshold limits the original base station to a circle with a radius of 10, the matrix was defined as having the center point as the origin, with all elements at a radius of 10 units as 0, and elements at the other edges as 1. In terms of a 5*5 matrix, this was roughly expressed as:

Create a 2,500*2,500 area matrix, where all elements were initialized to 1. Set the coordinates of all existing base stations to all the centroids in the area matrix and overlap them with the binary mask centroids, then perform logical sum operations by bit, at which the points with a value of zero were the unreasonable points screened out by the threshold condition that could not be built with new base stations. At last, name the matrix as the threshold matrix A_M.

3.2

Screening results

After calculation, we found 418,417 unreasonable points. The number of points that can build a new base station is a total of 5,831,583 points, which greatly reduces the amount of computation we need to build and solve the model next. To make the data more intuitive, we have visualized the results as follows.

Figure 3.

Diagram of the threshold range of existing network base stations

Where the blue dots indicate the area covered by the original base station, then all the points in the blank area were the points where a new base station could be established after filtering.

The differential evolution algorithm required initialization of the population and was sensitive to the initial values, requiring us to randomize the site selection state. We decided to use a Monte Carlo model with the idea of binary mask for this step.

3.3

Confirmation of the initial value of the DE algorithm

The differential evolution algorithm required initialization of the population and was sensitive to the initial values, requiring us to randomize the site selection state. We decided to use a Monte Carlo model with the idea of binary mask for this step.

3.4

Solution of the differential evolution algorithm

The optimal initial value was used as the initialized population of the differential evolution algorithm. The final result after optimization was obtained based on the constraint and objective function iterative variation operation, crossover operation and selection operation for a total of 186 micro-base stations and a total of 1930 macro-base stations, for a total of 2116 new base stations, as shown below.

Figure 4.

Scatter plot of new base stations

Where red dots indicate macro base stations and blue dots indicate micro base stations. The site selection results were obtained to verify the coverage requirement of 90% of the total service volume of the weak coverage points, at which point we again used the binary mask idea used in the data screening. The new macro base station and the micro base station were assigned a binary mask matrix according to their respective coverage areas. However, unlike the data screening, the circular area was assigned a value of 1 and the edge area was assigned a value of 0. Then the binary mask was logically oriented with the new base stations in the area by bit, so that even if there were duplicate coverage areas, they were only assigned a value of 1, avoiding duplicate summation of data. At the end of the operation, the points with a value of 1 in the whole area were added up and divided by the total number of services, giving a coverage of 91.2% of the total number of services.