An Improved Genetic Algorithm for UWB Localization

Xianzhi Zheng

School of Computer Science and Technology, Shandong University of Technology, Zibo, China.

DOI: 10.4236/jcc.2022.1010001                

Abstract

The UWB localization problem can be mapped as an optimization problem, which can be solved by genetic algorithm. In the localization process, the traditional fitness function does not include the ranging information between tags, resulting in insufficient ranging information and limited improvement of the localization accuracy. In view of this, an improved genetic localization algorithm is proposed. First, a new fitness function is constructed, which not only includes the ranging information between the tag and the base station, but also the ranging information between the tags to ensure that the ranging information is fully utilized in the localization process. Then, the search method based on Brownian motion is adopted to ensure that the improved algorithm can speed up the convergence speed of the localization result. The simulation results show that, compared with the traditional genetic localization algorithm, the improved genetic localization algorithm can reduce the influence of the ranging error on the localization error and improve the localization performance.

Keywords

Location, Improved Genetic Algorithm, Localization Accuracy, UWB

1. Introduction

Ultra wide band (UWB) localization technology [1] [2] [3] provides good location information for location-based service applications and has encouraged their widespread use. During the UWB localization process, the localization problem is treated as an optimization problem. This problem is then commonly solved using genetic optimization algorithms [4] [5] [6] or particle swarm optimization (PSO) algorithms [7] [8] [9]. Genetic optimization algorithms are typically preferred because they offer stronger global convergence and are more robust. For example, Literature [10] proposed a UWB localization algorithm based on genetic optimization, which can well realize global search. Literature [11] proposed an indoor positioning optimization algorithm combining genetic algorithm and RBF neural network to improve positioning accuracy. The fitness of an individual in the genetic optimization algorithm is a measure of the individual’s viability in a population. This is used to distinguish whether an individual is “good” or “bad”. However, for the above positioning, this is only based on the ranging information between the base station and the tag. The ranging information between tags is not considered. This amounts to an incomplete use of ranging information and limits positioning accuracy. Therefore, an improved genetic localization algorithm is proposed, which can make full use of ranging information, combined with Brownian motion search, avoid falling into a local optimal solution, and improve the convergence speed and localization accuracy.

2. Traditional Genetic Localization Algorithm

In a UWB localization system, let us assume that the location of the base station is $\left(u_k,y_k\right)$ and the location of the tag is $\left(x,y\right)$. The actual distance between the

tag and the k-th base station is $\sqrt{{\left(x-u_k\right)}^2+{\left(y-v_k\right)}^2}$ and the ranging distance

is $d_k$. According to the ranging distance data, a localization equation set can be established:

$\{\begin{array}{l}{d}_1=\sqrt{{\left(x-u_1\right)}^2+{\left(y-v_1\right)}^2}+e_1\\ ⋮\\ d_k=\sqrt{{\left(x-u_k\right)}^2+{\left(y-v_k\right)}^2}+e_k\\ ⋮\\ d_K=\sqrt{{\left(x-u_K\right)}^2+{\left(y-v_K\right)}^2}+e_K\end{array}$ (1)

where $e_k$ denotes the ranging error.

If we now randomly generate N populations and let the n-th individual be located as $X^{\left(n,l\right)}=\left(x^{\left(n,l\right)},y^{\left(n,l\right)}\right)$ $n\in \left(1,\cdots ,N\right)$ , from Equation (1), its fitness function will be [12]:

$f\left(X^{\left(n,l\right)}\right)=\frac{1}{K}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{\left(\sqrt{{\left(x^{\left(n,l\right)}-u_k\right)}^2+{\left(y^{\left(n,l\right)}-v_k\right)}^2}-d_k\right)}^2}$ (2)

From Equation (2), it can be observed that the fitness function is only related to the ranging information between the tag and the base station. This conventional genetic localization algorithm can only determine the position of a single tag by genetic manipulation such as selection, crossover, and mutation operations.

3. Improved Genetic Localization Algorithm

In traditional genetic localization algorithm, the ranging information between the tags is not utilized, although this can reduce localization errors. Thus, an improved genetic localization algorithm is proposed, which can make full use of all the ranging information to improve the accuracy.

Let us take a UWB network with I tags and K base stations. Let the location of the i-th tag is $\left(x_i,y_i\right)$ $i\in \left(1,2,\cdots ,I\right)$ and the location of the k-th base station is $\left(u_k,v_k\right)$ $k\in \left(1,2,\cdots ,K\right)$. $e_{i,k}$ and ${e^{\prime }}_{i,j}$ indicates the tag-to-base station ranging error and tag-to-tag ranging error, respectively. The actual distance between the i-th tag and the k-th base station is $\sqrt{{\left(x_i-u_k\right)}^2+{\left(y_i-v_k\right)}^2}$ and the measured distance is given by $d_{i,k}$. The actual distance between the i-th tag and the j-th tag is $\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ and the measured distance is given by ${d^{\prime }}_{i,j}$.

From this, we can build the following mathematical model for localization:

$\{\begin{array}{l}{d}_{1,1}=\sqrt{{\left(x_1-u_1\right)}^2+{\left(y_1-v_1\right)}^2}+e_{1,1}\\ ⋮\\ d_{i,k}=\sqrt{{\left(x_i-u_k\right)}^2+{\left(y_i-v_k\right)}^2}+e_{i,k}\\ ⋮\\ d_{I,K}=\sqrt{{\left(x_I-u_K\right)}^2+{\left(y_I-v_K\right)}^2}+e_{I,K}\\ {d^{\prime }}_{1,2}=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}+{e^{\prime }}_{1,2}\\ ⋮\\ {d^{\prime }}_{i,j}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}+{e^{\prime }}_{i,j}i<j\\ ⋮\\ {d^{\prime }}_{\left(I-1\right),I}=\sqrt{{\left(x_{\left(I-1\right)}-x_I\right)}^2+{\left(y_{\left(I-1\right)}-y_I\right)}^2}+{e^{\prime }}_{\left(I-1\right),I}\end{array}$ (3)

The specific steps are as follows:

Step 1. Randomly initialize the population, such as the population size, individual length etc. Let the n-th individual’s location be denoted as $X^{\left(n,l\right)}=\left(x_1^{\left(n,l\right)},y_1^{\left(n,l\right)},\cdots ,x_I^{\left(n,l\right)},y_I^{\left(n,l\right)}\right)$. From Equation (3), its fitness can be established as follows:

$\begin{array}{c}f\left(X^{\left(n,l\right)}\right)=\frac{1}{K_2}{\displaystyle \underset{i=1}{\overset{I}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{\left(\sqrt{{\left(x_i^{\left(n,l\right)}-u_k\right)}^2+{\left(y_i^{\left(n,l\right)}-v_k\right)}^2}-d_{i,k}\right)}^2}}\\ +\frac{1}{K_2}{\displaystyle \underset{i=1}{\overset{I-1}{\sum }}{\displaystyle \underset{\begin{array}{l}j=1\\ j>i\end{array}}{\overset{I}{\sum }}{\left(\sqrt{{\left(x_i^{\left(n,l\right)}-x_j^{\left(n,l\right)}\right)}^2+{\left(y_i^{\left(n,l\right)}-y_j^{\left(n,l\right)}\right)}^2}-{d^{\prime }}_{i,j}\right)}^2}}\end{array}$ (4)

where, $K_2=C_I^1{C}_K^1+C_I^2$ is the number of distances measured, and C means combination in mathematics.

Step 2. Calculate the fitness value of each individual and find the best individual.

Step 3. Generate a new population through selection, crossover, and mutation operations.

Step 4. The search method based on Brownian motion [13] [14] [15] is adopted to ensure that individuals can jump out of the local optimal solution and find the global optimal solution. Based on the Brownian motion search method, the location update equation is

$X^{\left(n,l+1\right)}=X^{\left(n,l\right)}+R_B$ (5)

R_B is the step size of the search method based on Brownian motion determined by a normally distributed probability density function with mean μ= 0

and adaptive variance ${\sigma }^2=0.1+\frac{Lmax-1}{Lmax}$ , where 1 is the number of iterations,

Lmax is the max number of iterations.

Step 5. Update fitness value and group.

Step 6. Go to Step 2 until the maximum evolution number is reached. After the evolution has ended, all of the locations of the tags can be calculated.

Unlike Equation (2), the fitness function in Equation (4), takes into account the ranging information between the tags, thus improving localization precision. By employing the new method, all of the tags locations can also be calculated at the same time. Figure 1 shows the flow chart of the localization process.

Figure 1. Localization flowchart.

4. Experimental Results and Analysis

To verify the localization performance of our proposed algorithm, we carried out simulations and compared its performance against the traditional genetic algorithm, trilateral localization algorithm and the PSO algorithm. In the simulation it is assumed that I tags are randomly distributed in a D*D square localization area, where D is the edge length value. The four anchor nodes are respectively located at the four top corners of the localization area. The main parameters for the genetic algorithm and the improved algorithm are: population size N= 30; maximum number of iterations L₁ = 200; probability of select P_g = 0.95; probability of crossover P_c = 0.7; and probability of mutation P_m = 0.01. The PSO algorithm parameters are: population size N= 30, maximum number of iterations L₂ = 200, acceleration factor C₁= C₂= 1.5, weighting factor ω= 0.7. The UWB ranging error is supposed to obey a Gaussian distribution with a zero mean and a variance of σ². To evaluate the localization performance, the localization error is calculated as follows:

$\text{error}=\frac{{\displaystyle \underset{i=1}{\overset{I}{\sum }}\sqrt{{\left({\hat{x}}_i-x_i\right)}^2+{\left({\hat{y}}_i-y_i\right)}^2}}}{I}$ (6)

where, $\left({\hat{x}}_i,{\hat{y}}_i\right)$ represents the estimate location, I is the number of tags.

As shown in Figure 2(a) and Figure 2(b), the blue circle indicates the location of the base station, and the red star indicates the true location of the tag. The tag location estimated by the traditional genetic localization algorithm is represented by the green circle, and the tag location estimated by the improved genetic localization algorithm is represented by the yellow triangle. The difference between the estimated location of the tag and the true location is indicated by the solid blue line. With I= 16, K= 4, D= 12 m, σ²= 1, the localization error of the traditional genetic localization algorithm in the figure is 0.8929 m and the localization error of the improved genetic localization algorithm is 0.6156 m, which indicates that the improved genetic localization algorithm has better localization effect than the traditional genetic localization algorithm.

Figure 3 shows the localization performance with different range error variances. As we can see, the localization error decreases as the variance of the ranging error decreases. However, the proposed algorithm has lower localization error than the traditional genetic algorithm, trilateral localization algorithm and PSO algorithm. This is because the proposed algorithm takes into account the range of information between the tags and uses the Brownian motion search method. Therefore, the localization accuracy is improved.

The effect of the Brownian motion-based search method on the convergence performance of the localization results is plotted in Figure 4, respectively. For the improved genetic localization algorithm, the convergence speed of the localization result using the Brownian motion search method is lower than that without the Brownian motion search method. This indicates that the search method based on Brownian motion can speed up the convergence speed of the

Figure 2. The effect of traditional and improved genetic localization. (a) The effect of traditional genetic localization. (b) The effect of improved genetic localization.

localization result.

5. Conclusion

In this paper, an improved genetic localization algorithm is proposed. By constructing a new fitness function, the distance information between tags is fully

Figure 3. Variation of positioning error with distance measurement error. (a) I = 8, K = 4, D = 12 m. (b) I = 16, K = 4, D = 12 m.

utilized to improve the localization accuracy, and at the same time, the Brownian motion is added to prevent falling into local optimal solutions. The simulation results show that compared with the traditional algorithm, the improved genetic localization algorithm can reduce the influence of ranging error on the localization error, improve the localization accuracy, and meet the needs of precise localization. The next step will continue to study the application of UWB localization,

Figure 4. Effect of Brownian motion-based search method on the convergence performance of localization results. (a) I = 8, K = 4, D = 12 m. (b) I = 16, K = 4, D = 12 m.

and verify the effectiveness of the improved genetic localization algorithm in the actual environment.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Harris, P. and Gikas, V. (2018) Evaluation of Range Error Calibration Models for Indoor UWB Positioning Applications. 2018 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Nantes, 24-27 September 2018, 206-212.
[2]	Wu, Y., Ding, S., Ding, Y., et al. (2021) UWB Base Station Cluster Localization for Unmanned Ground Vehicle Guidance. Mathematical Problems in Engineering, 2021, Article ID: 6639574. https://doi.org/10.1155/2021/6639574
[3]	Paszek, K., Grzechca, D. and Becker, A. (2021) Design of the UWB Positioning System Simulator for LOS/NLOS Environments. Sensors, 21, 4757. https://doi.org/10.3390/s21144757
[4]	Wang, Y. and Ting, J. (2013) A Method of Target Identification with UWB Based on Genetic Algorithm and Fuzzy Pattern Recognition. 2013 IEEE International Conference on Communications Workshops (IEEE ICC), Budapest, June 2013, 936-940.
[5]	Xia, B., Zheng, X., Zhang, L. and Zhao, L. (2021) UWB Positioning System Based on Genetic Algorithm. Journal of Computer and Communications, 9, 110-118. https://doi.org/10.4236/jcc.2021.94008
[6]	Zeng, Z., Liu, S. and Wang, L. (2019) UWB NLOS Identification with Feature Combination Selection Based on Genetic Algorithm. 2019 IEEE International Conference on Consumer Electronics (ICCE), Las Vegas, 11-13 January 2019, 1-5. https://doi.org/10.1109/ICCE.2019.8662065
[7]	Chu, Y.L., et al. (2021) An Improved Multi-Node Newton Iteration Search Method Based on PSO. Optik, 232, 166404. https://doi.org/10.1016/j.ijleo.2021.166404
[8]	Na, H.J. and Yoo, S.-J. (2019) PSO-Based Dynamic UAV Positioning Algorithm for Sensing Information Acquisition in Wireless Sensor Networks. IEEE Access, 7, 77499-77513. https://doi.org/10.1109/ACCESS.2019.2922203
[9]	Laureano, M.A.P. and Tonidandel, F. (2019) Analysis of the PSO Parameters for a Robots Positioning System in SSL. In: Chalup, S., Niemueller, T., Suthakorn, J., Williams, MA., Eds., Robot World Cup, Springer, Cham, 126-139. https://doi.org/10.1007/978-3-030-35699-6_10
[10]	Huang, J., Zhang, K., Shen, C., et al. (2021) Indoor Location of UWB-TDOA Based on Genetic Algorithm. 2021 IEEE 21st International Conference on Communication Technology (ICCT), Tianjin, 13-16 October 2021, 393-396. https://doi.org/10.1109/ICCT52962.2021.9657953
[11]	Guo, H. and Li, M.Q. (2020) Indoor Positioning Optimization Based on Genetic Algorithm and RBF Neural Network. 2020 IEEE International Conference on Power, Intelligent Computing and Systems (ICPICS), Shenyang, 28-30 July 2020, 778-781. https://doi.org/10.1109/ICPICS50287.2020.9202123
[12]	Xia, B., Zheng, X., Zhang, L., et al. (2021) UWB Positioning System Based on Genetic Algorithm. Journal of Computer and Communication, 9, 110-118. https://doi.org/10.4236/jcc.2021.94008
[13]	Gao, M., et al. (2021) 3-D Terrains Deployment of Wireless Sensors Network by Utilizing Parallel Gases Brownian Motion Optimization. Journal of Internet Technology, 22, 13-29.
[14]	Acı, Ç.I. and Gülcan, H. (2019) A Modified Dragonfly Optimization Algorithm for Single- and Multiobjective Problems Using Brownian Motion. Computational Intelligence and Neuroscience, 2019, Article ID: 6871298. https://doi.org/10.1155/2019/6871298
[15]	Kotte, S. and Injeti, S.K. (2021) Investigation of Butterfly Optimization and Gases Brownian Motion Optimization Algorithms for Optimal Multilevel Image Thresholding. Expert Systems with Applications, 182, 115286. https://doi.org/10.1016/j.eswa.2021.115286