# Research on the Station Layout Method of Ground-Based Pseudolite Positioning System Based on NSGA-II Algorithm

Authors: Li Yang; Kaiyuan Yang; Danshi Sun
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Given the problem that the existing method of station distributing the pseudosatellite system cannot ensure both its coverage and position in a situation of signal occlusion, it proposed a new stationary layout method with an elite strategy for a ground-based pseudosatellite positioning system based on the elite strategy of the nondominant genetic rankings (NSGA-II). The geometrical design of the pseudosatellite system is calculated by visual domain analysis and precision factors for the signal coverage age and base station. To optimize the algorithm, the NSGA-II algorithm is used. An earth pseudosatellite positioning system method of stationary distribution is obtained that simultaneously optimizes signal coverage and positioning accuracy. The algorithm is better distributed and has a certain superintendence compared with the traditional genetic algorithm.


---

## Body

## 1. Introduction

Ground-based pseudobase station is a kind of ground device placed on the ground and composed of ground transmitting base station and pseudolite receiver. It can provide users with continuous and highly reliable positioning, navigation, and other services. It has the characteristics of strong anti-interference ability, low cost, and high precision and is widely used in various fields. At present, with the application of ground-based pseudobase station positioning system in more and more scenes, in order to obtain positioning more accurately, relevant experts and scholars have done a lot of research on its coverage and geometric spatial layout. For example, in references [1, 2] based on square root UKF algorithm, the tracking and positioning ability of pseudolites is improved by optimizing the spatial layout of pseudolites. In references [3, 4] based on initial value filtering algorithm and second-order digital filter, GNSS assists pseudolite system positioning system to improve system signal coverage. Although the above methods have improved the signal coverage or positioning accuracy of the ground-based pseudolite system to a certain extent, on the whole, the above methods have only been optimized from a single aspect, and the research on the signal coverage and geometric layout of the ground-based pseudolite system is not comprehensive enough. Based on this, this study proposes a station deployment method for the ground-based pseudolite system based on the NSGA-II algorithm. Taking the coverage function and the accuracy factor as the objective functions [5–7], the NSGA-II algorithm is used for optimization, and the system signal coverage and positioning accuracy can be improved simultaneously [8–10]. In the station deployment method, experiments show that this method can effectively improve the signal coverage and positioning accuracy of the system and provide a new idea for the station deployment of ground-based pseudolite system in various scenes. The NSGA-II algorithm proposed in this paper has good research significance for base station location and signal accuracy and solves the problem of base station location and positioning. The second part of this paper introduces the basic content of the NSGA-II algorithm, the third part introduces the method of ground-based pseudolite positioning system station deployment, and the fourth part compares the application of the NSGA-II algorithm with the other three algorithms.


## 2. NSGA-II Algorithm

Recently, machine learning methods have been developed in many files, such as image processing [11, 12], remote sensing [13, 14], intelligent transportation [15], and other applications [16–18]. As a branch of machine learning, genetic algorithm has been used in many applications. And NSGA-II algorithm is a multiobjective optimization genetic algorithm, which is often used to solve multiobjective optimization problems. The basic idea is to obtain the optimal individual by simulating natural selection and evolution. The specific steps are as follows:Step 1.
Initialize the population. The initial population with scaleN is randomly generated, and the first generation of offspring population is obtained by non-dominated sorting, crossover and mutation operations.Step 2.
Merging the parent population and the offspring population and calculating the objective function value of each individual.Step 3.
After performing nondominant sorting on the merged population individuals, the crowding distance by Wang [19] is calculated by adopting the following formula:
(1)Li=∑k=1nfki+1−fki−1,where i represents an individual of the population; i+1 and i−1 denote the adjacent individuals of i; and fk· denotes the objective function.Step 4.
According to the crowded distance, the firstN individuals are reserved to form a new parent population.Step 5.
Judging whether the algorithm meets the termination condition, if the maximum iteration times are reached, selecting the optimal solution for output according to the utility function, and ending the algorithm.The above flow can be illustrated in Figure1.Figure 1
NSGA-II algorithm flow.The number of iterations is set according to experience or the difference between before and after iterations is less than the threshold to determine whether the number of iterations is met. Generally, setting a larger number of iterations is to achieve a better optimization effect.


## 3. Station Arrangement Method of Ground-Based Pseudolite Positioning System Based on NSGA-II Algorithm

### 3.1. Multiobjective Optimization Model of Ground-Based Pseudolite Base Station Layout

The layout scheme of ground-based pseudolite base stations is usually determined by the system signal coverage rate and the geometric layout of base stations. Therefore, the research is aimed at the most slippery coverage rate and the optimization of base station layout. If the coordinate of thei pseudolite base station is Si and there are N base stations, the mathematical model of ground-based pseudolite layout can be expressed as [20]
(2)Maximizef1Si=areaVS1,S2,⋯,Snarea,Maximizef2Si=gDOPS1,S2,⋯,Sn,where f1 represents the system signal coverage rate, areaVS1,S2,⋯,Sn reflects the system signal coverage rate and indicates the system signal coverage area; f2 represents the accuracy factor, reflecting the advantages and disadvantages of the system base station layout; and gDOPS1,S2,⋯,Sn indicates the positioning accuracy.


### 3.2. Objective Function Design

#### 3.2.1. Coverage Function Design

The signal coverage rate of pseudolite system is the ratio of the locatable area of pseudolite system to the target coverage area, which can be solved by visual domain analysis based on digital elevation model (DEM).Firstly, the locatable area of pseudolite system is determined. DEM data of longitude, latitude, and elevation terrain of the target area are imported and converted into a two-dimensional plane coordinate system relationship, as shown in Equations (3)–(5) [21].
(3)DEMx=DxijM×N,(4)DEMy=DyijM×N,(5)DEMz=DzijM×N,where M and N represent the two-dimensional size of the DEM data matrix; Dxij, Dyij, and Dzij represent the horizontal, ordinate, and height of the terrain raster data, respectively.Then, visual domain analysis is used to solve the signal coverage of each base station. Let the coordinates of the actual terrain base stationi be sixi,yi,zi, as follows:
(6)vi=aijM×N,where vi represents the visual field matrix of the base station i; when aij=1 or aij=0, aij=1 indicates that the base station is visible to the points (Dxij, Dyij, and Dzi), and when aij=0, it indicates that it is invisible; that is, the more the zeros in vi, the smaller the visible range and the smaller the signal coverage range.Finally, the coverage of all base stations is superimposed, as shown in the following equation:(7)v=∑i=1nvi=vijM×N,where vij≥0,N denotes the number of visual pseudolite base stations (Dxij, Dyij, and Dzi), where N denotes the number of base stations. When vij≥4, it means that the receiver can locate [22]. Therefore, for the convenience of processing, if the value of vij≤4 is set to 1 and the value of vij<4 is set to 0, then the matrix V is V¯. The set of all 1s in V¯ is the locatable area of the pseudolite system. Therefore, the coverage rate can be calculated by the following equation:
(8)Area=sumV¯M×N×100%,where sum represents summation. For the convenience of subsequent description, f1 is transformed into a minimization objective function and defined as
(9)f1=1area=M×NsumV¯×100%.


#### 3.2.2. Design of Accuracy Factor Function

Assuming that the number of sampling points isNp, the weight corresponding to each sampling point is Wi, and the precision factor (DOP) value is DOPi, the objective function f2 can be defined as
(10)f2=∑iNpwi×DOPi∑iNpwi.It can be seen from the formula that the smaller thef2 value, the higher the positioning accuracy in the pseudolite system area. Considering the influence of other factors on positioning accuracy, a global weighted DOP method based on multimatrix multiplication is proposed, as shown in Equation (11) [23]:
(11)M=∏imi=MijM×N,DOP=DM,f2=sumDOP⋅MsumM,where mi represents a condition matrix and m represents a dot multiplication matrix of a plurality of mi; DM denote whether DOPij is calculated according to Mij. If Mij=0, DOPij is not calculated; let DOPij=0; if Mij≠O, then DOPij is calculated. Set mi to
(12)m1=V¯,m2=1M×N,m3=10⋯100100⋮⋱⋮10⋯100101,where M1 represents the visual domain matrix of the current pseudolite system, which can prevent unlocatable points from being included in weighted DOP calculation; M2 represents the weight matrix, where all elements are 1; and M3 represents the sampling matrix, in which 1 represents the sampling point position and 0 represents the nonsampling point.


### 3.3. Design of Station Arrangement Method for Ground-Based Pseudolite Positioning System Based on NSGA-II

The purpose of the station arrangement method of the ground-based pseudolite positioning system based on the NSGA-II algorithm is to solve the coordinates of pseudolite base stations, so the station arrangement design can be carried out according to the following steps:Step 1.
Population initialization. The coordinates of all pseudolite base stations are sequentially added into a vector to form an individual chromosome vectorC:
(13)C=x1,y1,x2,y2,⋯,xn,yn,where xi and yi are the abscissa and ordinate of the base station, respectively, and their ranges are determined by DEM data. According to the above formula, the initial population Qo with the number of individuals Nv can be obtained.Step 2.
SelectNv pairs of parent from a parent population Qk according to a tournament mechanism and crossing each pair of parents in a multipoint crossing mode to generate a subpopulation Rk [24] of Nv offspring individuals.Step 3.
Randomly select individuals fromRk according to the mutation probability to perform multipoint mutation.Step 4.
CombineQk and Rk into a population Uk=2Nv, and determine a nondominant grade of each individual in that Uk population according to objective functions f1 and f2.Step 5.
Calculate the crowded distance of individual in the crowdedUk population, performing descending order sorting according to the nondominant grade and retaining the first Nv individuals.Step 6.
Calculate utility function valuesF of all noninferior solutions by adopting utility functions, such as Equation (14), and select the solution with the largest F value as the best site selection scheme for pseudolite base stations.
(14)F=C1×f1Xi−f1minf1max−f1min+C2×f2max−f2Xif2max−f2min,where C1 and C2 represent coefficients, C1+C2=1 and C1,C2∈0,1, which can be determined by preference. If C1>C2, it means that the base station layout scheme is more inclined to the base station layout scheme with high signal coverage; if C1<C2, it means that the base station layout scheme is more inclined to the base station layout scheme with high positioning accuracy. If C1=C2=0.5, the coverage and base station layout are relatively balanced, which is beneficial to the coverage and base station layout.


## 3.1. Multiobjective Optimization Model of Ground-Based Pseudolite Base Station Layout

The layout scheme of ground-based pseudolite base stations is usually determined by the system signal coverage rate and the geometric layout of base stations. Therefore, the research is aimed at the most slippery coverage rate and the optimization of base station layout. If the coordinate of thei pseudolite base station is Si and there are N base stations, the mathematical model of ground-based pseudolite layout can be expressed as [20]
(2)Maximizef1Si=areaVS1,S2,⋯,Snarea,Maximizef2Si=gDOPS1,S2,⋯,Sn,where f1 represents the system signal coverage rate, areaVS1,S2,⋯,Sn reflects the system signal coverage rate and indicates the system signal coverage area; f2 represents the accuracy factor, reflecting the advantages and disadvantages of the system base station layout; and gDOPS1,S2,⋯,Sn indicates the positioning accuracy.


## 3.2. Objective Function Design

### 3.2.1. Coverage Function Design

The signal coverage rate of pseudolite system is the ratio of the locatable area of pseudolite system to the target coverage area, which can be solved by visual domain analysis based on digital elevation model (DEM).Firstly, the locatable area of pseudolite system is determined. DEM data of longitude, latitude, and elevation terrain of the target area are imported and converted into a two-dimensional plane coordinate system relationship, as shown in Equations (3)–(5) [21].
(3)DEMx=DxijM×N,(4)DEMy=DyijM×N,(5)DEMz=DzijM×N,where M and N represent the two-dimensional size of the DEM data matrix; Dxij, Dyij, and Dzij represent the horizontal, ordinate, and height of the terrain raster data, respectively.Then, visual domain analysis is used to solve the signal coverage of each base station. Let the coordinates of the actual terrain base stationi be sixi,yi,zi, as follows:
(6)vi=aijM×N,where vi represents the visual field matrix of the base station i; when aij=1 or aij=0, aij=1 indicates that the base station is visible to the points (Dxij, Dyij, and Dzi), and when aij=0, it indicates that it is invisible; that is, the more the zeros in vi, the smaller the visible range and the smaller the signal coverage range.Finally, the coverage of all base stations is superimposed, as shown in the following equation:(7)v=∑i=1nvi=vijM×N,where vij≥0,N denotes the number of visual pseudolite base stations (Dxij, Dyij, and Dzi), where N denotes the number of base stations. When vij≥4, it means that the receiver can locate [22]. Therefore, for the convenience of processing, if the value of vij≤4 is set to 1 and the value of vij<4 is set to 0, then the matrix V is V¯. The set of all 1s in V¯ is the locatable area of the pseudolite system. Therefore, the coverage rate can be calculated by the following equation:
(8)Area=sumV¯M×N×100%,where sum represents summation. For the convenience of subsequent description, f1 is transformed into a minimization objective function and defined as
(9)f1=1area=M×NsumV¯×100%.


### 3.2.2. Design of Accuracy Factor Function

Assuming that the number of sampling points isNp, the weight corresponding to each sampling point is Wi, and the precision factor (DOP) value is DOPi, the objective function f2 can be defined as
(10)f2=∑iNpwi×DOPi∑iNpwi.It can be seen from the formula that the smaller thef2 value, the higher the positioning accuracy in the pseudolite system area. Considering the influence of other factors on positioning accuracy, a global weighted DOP method based on multimatrix multiplication is proposed, as shown in Equation (11) [23]:
(11)M=∏imi=MijM×N,DOP=DM,f2=sumDOP⋅MsumM,where mi represents a condition matrix and m represents a dot multiplication matrix of a plurality of mi; DM denote whether DOPij is calculated according to Mij. If Mij=0, DOPij is not calculated; let DOPij=0; if Mij≠O, then DOPij is calculated. Set mi to
(12)m1=V¯,m2=1M×N,m3=10⋯100100⋮⋱⋮10⋯100101,where M1 represents the visual domain matrix of the current pseudolite system, which can prevent unlocatable points from being included in weighted DOP calculation; M2 represents the weight matrix, where all elements are 1; and M3 represents the sampling matrix, in which 1 represents the sampling point position and 0 represents the nonsampling point.


## 3.2.1. Coverage Function Design

The signal coverage rate of pseudolite system is the ratio of the locatable area of pseudolite system to the target coverage area, which can be solved by visual domain analysis based on digital elevation model (DEM).Firstly, the locatable area of pseudolite system is determined. DEM data of longitude, latitude, and elevation terrain of the target area are imported and converted into a two-dimensional plane coordinate system relationship, as shown in Equations (3)–(5) [21].
(3)DEMx=DxijM×N,(4)DEMy=DyijM×N,(5)DEMz=DzijM×N,where M and N represent the two-dimensional size of the DEM data matrix; Dxij, Dyij, and Dzij represent the horizontal, ordinate, and height of the terrain raster data, respectively.Then, visual domain analysis is used to solve the signal coverage of each base station. Let the coordinates of the actual terrain base stationi be sixi,yi,zi, as follows:
(6)vi=aijM×N,where vi represents the visual field matrix of the base station i; when aij=1 or aij=0, aij=1 indicates that the base station is visible to the points (Dxij, Dyij, and Dzi), and when aij=0, it indicates that it is invisible; that is, the more the zeros in vi, the smaller the visible range and the smaller the signal coverage range.Finally, the coverage of all base stations is superimposed, as shown in the following equation:(7)v=∑i=1nvi=vijM×N,where vij≥0,N denotes the number of visual pseudolite base stations (Dxij, Dyij, and Dzi), where N denotes the number of base stations. When vij≥4, it means that the receiver can locate [22]. Therefore, for the convenience of processing, if the value of vij≤4 is set to 1 and the value of vij<4 is set to 0, then the matrix V is V¯. The set of all 1s in V¯ is the locatable area of the pseudolite system. Therefore, the coverage rate can be calculated by the following equation:
(8)Area=sumV¯M×N×100%,where sum represents summation. For the convenience of subsequent description, f1 is transformed into a minimization objective function and defined as
(9)f1=1area=M×NsumV¯×100%.


## 3.2.2. Design of Accuracy Factor Function

Assuming that the number of sampling points isNp, the weight corresponding to each sampling point is Wi, and the precision factor (DOP) value is DOPi, the objective function f2 can be defined as
(10)f2=∑iNpwi×DOPi∑iNpwi.It can be seen from the formula that the smaller thef2 value, the higher the positioning accuracy in the pseudolite system area. Considering the influence of other factors on positioning accuracy, a global weighted DOP method based on multimatrix multiplication is proposed, as shown in Equation (11) [23]:
(11)M=∏imi=MijM×N,DOP=DM,f2=sumDOP⋅MsumM,where mi represents a condition matrix and m represents a dot multiplication matrix of a plurality of mi; DM denote whether DOPij is calculated according to Mij. If Mij=0, DOPij is not calculated; let DOPij=0; if Mij≠O, then DOPij is calculated. Set mi to
(12)m1=V¯,m2=1M×N,m3=10⋯100100⋮⋱⋮10⋯100101,where M1 represents the visual domain matrix of the current pseudolite system, which can prevent unlocatable points from being included in weighted DOP calculation; M2 represents the weight matrix, where all elements are 1; and M3 represents the sampling matrix, in which 1 represents the sampling point position and 0 represents the nonsampling point.


## 3.3. Design of Station Arrangement Method for Ground-Based Pseudolite Positioning System Based on NSGA-II

The purpose of the station arrangement method of the ground-based pseudolite positioning system based on the NSGA-II algorithm is to solve the coordinates of pseudolite base stations, so the station arrangement design can be carried out according to the following steps:Step 1.
Population initialization. The coordinates of all pseudolite base stations are sequentially added into a vector to form an individual chromosome vectorC:
(13)C=x1,y1,x2,y2,⋯,xn,yn,where xi and yi are the abscissa and ordinate of the base station, respectively, and their ranges are determined by DEM data. According to the above formula, the initial population Qo with the number of individuals Nv can be obtained.Step 2.
SelectNv pairs of parent from a parent population Qk according to a tournament mechanism and crossing each pair of parents in a multipoint crossing mode to generate a subpopulation Rk [24] of Nv offspring individuals.Step 3.
Randomly select individuals fromRk according to the mutation probability to perform multipoint mutation.Step 4.
CombineQk and Rk into a population Uk=2Nv, and determine a nondominant grade of each individual in that Uk population according to objective functions f1 and f2.Step 5.
Calculate the crowded distance of individual in the crowdedUk population, performing descending order sorting according to the nondominant grade and retaining the first Nv individuals.Step 6.
Calculate utility function valuesF of all noninferior solutions by adopting utility functions, such as Equation (14), and select the solution with the largest F value as the best site selection scheme for pseudolite base stations.
(14)F=C1×f1Xi−f1minf1max−f1min+C2×f2max−f2Xif2max−f2min,where C1 and C2 represent coefficients, C1+C2=1 and C1,C2∈0,1, which can be determined by preference. If C1>C2, it means that the base station layout scheme is more inclined to the base station layout scheme with high signal coverage; if C1<C2, it means that the base station layout scheme is more inclined to the base station layout scheme with high positioning accuracy. If C1=C2=0.5, the coverage and base station layout are relatively balanced, which is beneficial to the coverage and base station layout.


## 4. Simulation Test

### 4.1. Experimental Scheme

In order to verify the application effect of the proposed algorithm in practical application, this experiment takes DEM data of about15.5km∗15.5km in a mountainous area of Hunan as an example and adopts four strategies to deploy pseudolite base stations. The specific strategies are as follows:Strategy 1.
Nine, 16, 25, 36, and 49 pseudolite base stations are evenly placed in the target area as a reference.Strategy 2.
Standard genetic algorithm is used to solve the station layout strategy, and only the system coverage rate is optimized.Strategy 3.
The standard genetic algorithm is used to solve the station layout strategy, and only the system base station set layout is optimized.Strategy 4.
This study uses the NSGA-II algorithm to solve the station deployment strategy and optimizes the system signal coverage and positioning accuracy at the same time.


### 4.2. Parameter Setting

The parameters of standard genetic algorithm and NSGA-II algorithm in strategies 2, 3, and 4 are set as follows: the number of populations is 80, the genetic algebra is 100, the crossover probability is 0.8, and the mutation probability is 0.01.


### 4.3. Case Analysis

#### 4.3.1. Algorithm Results

Using the above four strategies for simulation, the system coverage and weighted average HDOP results are shown in Tables1–4. As can be seen from the table, the coverage rate of strategy 1 is poor; even if the number of base stations reaches 49, its highest coverage rate is only 52; 2%, but its HDOP performs well due to its uniform distribution of base stations. Strategy 2 optimizes the coverage rate, so under the same number of base stations, its coverage rate is the largest compared with other strategies. Strategy 3 optimizes the layout of base station sets, so under the same number of base stations, its HDOP is the smallest and the positioning accuracy of the system is the best. Strategy 4 optimizes the coverage and positioning accuracy of the system at the same time, so compared with other strategies, this strategy has the highest comprehensive level of coverage and positioning accuracy.Table 1
Policy 1 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP98.25.51614.35.12523.44.33636.83.14952.22.8Table 2
Policy 2 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1052.532.31569.418.62081.127.22589.318.13094.112.63596316.54097.811.8Table 3
Policy 3 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1044.33.61552.53.22069.12.92573.42.53081.52.23587.71.94089.11.45Table 4
Policy 4 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1050.58.41566.46.12076.14.5258534.13092.53.83594.83.44096.83.2As can be seen from Tables1–4, the coverage rate is directly proportional to the number of base stations, while the weighted average HDOP is counterexample to the number of base stations. Therefore, the coverage rate and weighted average HDOP are inversely proportional. Therefore, the smaller the accuracy and the greater the coverage, the better the performance of the NSGA-II algorithm.


#### 4.3.2. Comparison of Algorithms

In order to verify the superiority of the proposed algorithm, the optimization effects of this algorithm and standard genetic algorithm are compared; that is, the optimization effects of strategy 2 and strategy 4 and strategy 3 and strategy 4 are compared.(1)
Comparison of optimization results between strategy 2 and strategy 4The optimization results of strategy 2 and strategy 4 are compared, and the results are shown in Figure2. As can be seen from the figure, the coverage rate of strategy 2 is relatively close to that of strategy 4, and the average coverage rate difference between the two is only 2.69%, indicating that the coverage rate of the two is basically the same. The HDOP of the two strategies is quite different. The HDOP of strategy 2 is obviously higher than that of strategy 4, which is about 4 times that of strategy 4, indicating that its positioning accuracy is low. With the increase of the number of base stations, the HDOP curve of strategy 2 fluctuates greatly, while the HDOP curve of strategy 4 decreases gently, which indicates that the optimization of coverage rate by standard genetic algorithm is divergent. On the whole, the coverage rate of strategy 2 is close to that of strategy 4, but the positioning accuracy of strategy 4 is higher, which indicates that the station deployment method of strategy 4 is better; that is, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm proposed in this study is better.
(2)
Comparison of optimization results between strategy 3 and strategy 4Figure 2
Comparison of optimization results of strategy 2 and strategy 4.The optimization results of strategy 3 and strategy 4 are compared, and the results are shown in Figure3. As can be seen from the figure, the coverage rate of strategy 3 and strategy 4 is quite different, and the average coverage rate of strategy 3 is reduced by 10, 68% compared with strategy 4. The HDOP of strategy 4 is about 1.8 times that of strategy 3; that is, the difference of positioning accuracy is small. Therefore, although the positioning accuracy of strategy 4 is slightly lower than that of strategy 3, its coverage rate is higher, which shows that the station deployment method under this strategy is better; that is, the pseudolite positioning system station deployment method based on the NSGA-II algorithm proposed in this study is better.Figure 3
Comparison of optimization results of strategy 3 and strategy 4.Through the above analysis, it can be seen that compared with the station deployment method based on traditional genetic algorithm, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm in this study can optimize the signal coverage rate and the geometric layout of base stations at the same time, and with the increase of the number of base stations, the signal coverage rate and positioning accuracy are improved more obviously.


### 4.4. Algorithm Performance Analysis

According to the above case analysis results, when the number of base stations is 25, the signal coverage and positioning accuracy can be maximized by using this algorithm. Therefore, in order to verify the performance of the proposed ground-based pseudolite positioning system station deployment method based on the NSGA-II algorithm, the proposed algorithm is used to deploy 25 ground-based pseudolite base stations as an example. When the number of basestations=25, the location of pseudolite base stations is shown in Figure 4.Figure 4
Schematic diagram of base station location when the number of basestations=25.According to the simulation results of station distribution, the forefront of Pareto is drawn, as shown in Figure5. Finally, the individual with f1=1.172 and f2=4.1 in the optimal solution set is selected as the preferred solution by using utility function. As can be seen from the figure, the forefront of this research algorithm is evenly dispersed, indicating that the algorithm has good performance; The range of Pareto solution set objective function f1 is [1.14, 1.23], indicating that the coverage range of the station deployment scheme is 81.3%~87.7%; The value range of the objective function f2 is [3.5, 6.3], indicating that the weighted average HDOP range corresponding to the Pareto optimal solution set is [3.5, 6.3].Figure 5
Pareto optimal solution set distribution of algorithm when the number of ground-based pseudolite basestations=25.


## 4.1. Experimental Scheme

In order to verify the application effect of the proposed algorithm in practical application, this experiment takes DEM data of about15.5km∗15.5km in a mountainous area of Hunan as an example and adopts four strategies to deploy pseudolite base stations. The specific strategies are as follows:Strategy 1.
Nine, 16, 25, 36, and 49 pseudolite base stations are evenly placed in the target area as a reference.Strategy 2.
Standard genetic algorithm is used to solve the station layout strategy, and only the system coverage rate is optimized.Strategy 3.
The standard genetic algorithm is used to solve the station layout strategy, and only the system base station set layout is optimized.Strategy 4.
This study uses the NSGA-II algorithm to solve the station deployment strategy and optimizes the system signal coverage and positioning accuracy at the same time.


## 4.2. Parameter Setting

The parameters of standard genetic algorithm and NSGA-II algorithm in strategies 2, 3, and 4 are set as follows: the number of populations is 80, the genetic algebra is 100, the crossover probability is 0.8, and the mutation probability is 0.01.


## 4.3. Case Analysis

### 4.3.1. Algorithm Results

Using the above four strategies for simulation, the system coverage and weighted average HDOP results are shown in Tables1–4. As can be seen from the table, the coverage rate of strategy 1 is poor; even if the number of base stations reaches 49, its highest coverage rate is only 52; 2%, but its HDOP performs well due to its uniform distribution of base stations. Strategy 2 optimizes the coverage rate, so under the same number of base stations, its coverage rate is the largest compared with other strategies. Strategy 3 optimizes the layout of base station sets, so under the same number of base stations, its HDOP is the smallest and the positioning accuracy of the system is the best. Strategy 4 optimizes the coverage and positioning accuracy of the system at the same time, so compared with other strategies, this strategy has the highest comprehensive level of coverage and positioning accuracy.Table 1
Policy 1 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP98.25.51614.35.12523.44.33636.83.14952.22.8Table 2
Policy 2 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1052.532.31569.418.62081.127.22589.318.13094.112.63596316.54097.811.8Table 3
Policy 3 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1044.33.61552.53.22069.12.92573.42.53081.52.23587.71.94089.11.45Table 4
Policy 4 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1050.58.41566.46.12076.14.5258534.13092.53.83594.83.44096.83.2As can be seen from Tables1–4, the coverage rate is directly proportional to the number of base stations, while the weighted average HDOP is counterexample to the number of base stations. Therefore, the coverage rate and weighted average HDOP are inversely proportional. Therefore, the smaller the accuracy and the greater the coverage, the better the performance of the NSGA-II algorithm.


### 4.3.2. Comparison of Algorithms

In order to verify the superiority of the proposed algorithm, the optimization effects of this algorithm and standard genetic algorithm are compared; that is, the optimization effects of strategy 2 and strategy 4 and strategy 3 and strategy 4 are compared.(1)
Comparison of optimization results between strategy 2 and strategy 4The optimization results of strategy 2 and strategy 4 are compared, and the results are shown in Figure2. As can be seen from the figure, the coverage rate of strategy 2 is relatively close to that of strategy 4, and the average coverage rate difference between the two is only 2.69%, indicating that the coverage rate of the two is basically the same. The HDOP of the two strategies is quite different. The HDOP of strategy 2 is obviously higher than that of strategy 4, which is about 4 times that of strategy 4, indicating that its positioning accuracy is low. With the increase of the number of base stations, the HDOP curve of strategy 2 fluctuates greatly, while the HDOP curve of strategy 4 decreases gently, which indicates that the optimization of coverage rate by standard genetic algorithm is divergent. On the whole, the coverage rate of strategy 2 is close to that of strategy 4, but the positioning accuracy of strategy 4 is higher, which indicates that the station deployment method of strategy 4 is better; that is, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm proposed in this study is better.
(2)
Comparison of optimization results between strategy 3 and strategy 4Figure 2
Comparison of optimization results of strategy 2 and strategy 4.The optimization results of strategy 3 and strategy 4 are compared, and the results are shown in Figure3. As can be seen from the figure, the coverage rate of strategy 3 and strategy 4 is quite different, and the average coverage rate of strategy 3 is reduced by 10, 68% compared with strategy 4. The HDOP of strategy 4 is about 1.8 times that of strategy 3; that is, the difference of positioning accuracy is small. Therefore, although the positioning accuracy of strategy 4 is slightly lower than that of strategy 3, its coverage rate is higher, which shows that the station deployment method under this strategy is better; that is, the pseudolite positioning system station deployment method based on the NSGA-II algorithm proposed in this study is better.Figure 3
Comparison of optimization results of strategy 3 and strategy 4.Through the above analysis, it can be seen that compared with the station deployment method based on traditional genetic algorithm, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm in this study can optimize the signal coverage rate and the geometric layout of base stations at the same time, and with the increase of the number of base stations, the signal coverage rate and positioning accuracy are improved more obviously.


## 4.3.1. Algorithm Results

Using the above four strategies for simulation, the system coverage and weighted average HDOP results are shown in Tables1–4. As can be seen from the table, the coverage rate of strategy 1 is poor; even if the number of base stations reaches 49, its highest coverage rate is only 52; 2%, but its HDOP performs well due to its uniform distribution of base stations. Strategy 2 optimizes the coverage rate, so under the same number of base stations, its coverage rate is the largest compared with other strategies. Strategy 3 optimizes the layout of base station sets, so under the same number of base stations, its HDOP is the smallest and the positioning accuracy of the system is the best. Strategy 4 optimizes the coverage and positioning accuracy of the system at the same time, so compared with other strategies, this strategy has the highest comprehensive level of coverage and positioning accuracy.Table 1
Policy 1 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP98.25.51614.35.12523.44.33636.83.14952.22.8Table 2
Policy 2 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1052.532.31569.418.62081.127.22589.318.13094.112.63596316.54097.811.8Table 3
Policy 3 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1044.33.61552.53.22069.12.92573.42.53081.52.23587.71.94089.11.45Table 4
Policy 4 base station coverage and HDOP relationship.
Number of base stationsCoverage (%)Weighted average HDOP1050.58.41566.46.12076.14.5258534.13092.53.83594.83.44096.83.2As can be seen from Tables1–4, the coverage rate is directly proportional to the number of base stations, while the weighted average HDOP is counterexample to the number of base stations. Therefore, the coverage rate and weighted average HDOP are inversely proportional. Therefore, the smaller the accuracy and the greater the coverage, the better the performance of the NSGA-II algorithm.


## 4.3.2. Comparison of Algorithms

In order to verify the superiority of the proposed algorithm, the optimization effects of this algorithm and standard genetic algorithm are compared; that is, the optimization effects of strategy 2 and strategy 4 and strategy 3 and strategy 4 are compared.(1)
Comparison of optimization results between strategy 2 and strategy 4The optimization results of strategy 2 and strategy 4 are compared, and the results are shown in Figure2. As can be seen from the figure, the coverage rate of strategy 2 is relatively close to that of strategy 4, and the average coverage rate difference between the two is only 2.69%, indicating that the coverage rate of the two is basically the same. The HDOP of the two strategies is quite different. The HDOP of strategy 2 is obviously higher than that of strategy 4, which is about 4 times that of strategy 4, indicating that its positioning accuracy is low. With the increase of the number of base stations, the HDOP curve of strategy 2 fluctuates greatly, while the HDOP curve of strategy 4 decreases gently, which indicates that the optimization of coverage rate by standard genetic algorithm is divergent. On the whole, the coverage rate of strategy 2 is close to that of strategy 4, but the positioning accuracy of strategy 4 is higher, which indicates that the station deployment method of strategy 4 is better; that is, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm proposed in this study is better.
(2)
Comparison of optimization results between strategy 3 and strategy 4Figure 2
Comparison of optimization results of strategy 2 and strategy 4.The optimization results of strategy 3 and strategy 4 are compared, and the results are shown in Figure3. As can be seen from the figure, the coverage rate of strategy 3 and strategy 4 is quite different, and the average coverage rate of strategy 3 is reduced by 10, 68% compared with strategy 4. The HDOP of strategy 4 is about 1.8 times that of strategy 3; that is, the difference of positioning accuracy is small. Therefore, although the positioning accuracy of strategy 4 is slightly lower than that of strategy 3, its coverage rate is higher, which shows that the station deployment method under this strategy is better; that is, the pseudolite positioning system station deployment method based on the NSGA-II algorithm proposed in this study is better.Figure 3
Comparison of optimization results of strategy 3 and strategy 4.Through the above analysis, it can be seen that compared with the station deployment method based on traditional genetic algorithm, the station deployment method of the pseudolite positioning system based on the NSGA-II algorithm in this study can optimize the signal coverage rate and the geometric layout of base stations at the same time, and with the increase of the number of base stations, the signal coverage rate and positioning accuracy are improved more obviously.


## 4.4. Algorithm Performance Analysis

According to the above case analysis results, when the number of base stations is 25, the signal coverage and positioning accuracy can be maximized by using this algorithm. Therefore, in order to verify the performance of the proposed ground-based pseudolite positioning system station deployment method based on the NSGA-II algorithm, the proposed algorithm is used to deploy 25 ground-based pseudolite base stations as an example. When the number of basestations=25, the location of pseudolite base stations is shown in Figure 4.Figure 4
Schematic diagram of base station location when the number of basestations=25.According to the simulation results of station distribution, the forefront of Pareto is drawn, as shown in Figure5. Finally, the individual with f1=1.172 and f2=4.1 in the optimal solution set is selected as the preferred solution by using utility function. As can be seen from the figure, the forefront of this research algorithm is evenly dispersed, indicating that the algorithm has good performance; The range of Pareto solution set objective function f1 is [1.14, 1.23], indicating that the coverage range of the station deployment scheme is 81.3%~87.7%; The value range of the objective function f2 is [3.5, 6.3], indicating that the weighted average HDOP range corresponding to the Pareto optimal solution set is [3.5, 6.3].Figure 5
Pareto optimal solution set distribution of algorithm when the number of ground-based pseudolite basestations=25.


## 5. Conclusion

To sum up, the station deployment method of the ground-based pseudolite positioning system based on the NSGA-II algorithm proposed in this study can improve the signal coverage and positioning accuracy of pseudolite base stations by optimizing the coverage rate and geometric layout of base stations. Compared with the standard genetic algorithm, the coverage rate of this algorithm is higher and the positioning accuracy is better. With the increase of the number of base stations, the superiority of this algorithm is more obvious, and the improvement effect of signal coverage rate and positioning accuracy is better. Although this algorithm has achieved some results, there are still some problems in practical application, such as not considering the influence of electromagnetic interference and other factors in the actual environment and not including the actual installation difficulty of the base station. Therefore, the next step will be to conduct in-depth research from these aspects in order to find a more accurate and effective method for the deployment of ground-based pseudolite systems.



---

*Source: 1520859-2021-08-15.xml*