UWB Positioning System Based on Genetic Algorithm

Bin Xia, Xianzhi Zheng, Liye Zhang, Lei Zhao

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

DOI: 10.4236/jcc.2021.94008                

Abstract

In order to enhance the positioning accuracy, a UWB positioning system based on genetic algorithm is proposed. Firstly, it uses the DW1000 module to measure the distance, and preprocesses the measured data to remove noise. Then, a positioning equation is established according to the processed distance information, and the genetic algorithm is used to solve the equation to obtain the coordinates of the unknown node. The experimental results show that the measured positioning accuracy is within 30 cm, which means that the system can obtain a good positioning effect and meet the need for precise positioning.

Keywords

Location, Ultra Wide Band, Genetic Algorithm

1. Introduction

At present, people’s demand for precise positioning technology is becoming more and more urgent. For example, many applications such as smart agriculture [1] [2], smart robot [3] [4], environmental monitoring [5] [6], require accurate location information of the target node. The UWB (Ultra wideband) positioning system [7] [8] [9] transmits data by sending narrow pulses at the nanosecond level, which can provide centimeter-level ranging accuracy. At the same time, the genetic algorithm [10] [11] [12] [13] [14] has become a common method due to its high solution accuracy, fast convergence speed, and strong robustness among the positioning algorithms. In view of this, the combination of the UWB ranging technology and the genetic algorithm positioning can improve the accuracy of positioning. Thus, this paper proposes a UWB positioning system based on the genetic algorithm. The system preprocesses the measurement data of TOA (time of arrival), and uses a genetic positioning algorithm to estimate the target position, which can obtain a good precise positioning effect.

2. UWB Positioning System Description

The positioning system takes STM32F103C8T6 as the main control. The control program is written into the hardware to control the sending and receiving of data through Keil5 software. The hardware uses TTL serial port to connect to the upper computer, and the upper computer displays specific data information through the software written in VS2012. As shown in Figure 1, both the unknown tag and the base station use the same hardware structure [15], whose different functions are defined by the software. The hardware contains the DW1000 UWB chip, which is a positioning chip based on the IEEE802.15.4a standard. The system obtains the measured distance from the unknown tag to different base stations, and estimates the location of the unknown tag through the genetic algorithm.

3. Bilateral Ranging Algorithm

The UWB positioning system uses a bilateral ranging algorithm based on the TOA technology [16] [17] [18] [19], and obtains the distance between the nodes by measuring the propagation time of the UWB signal. The bilateral method [20] adds a communication on the basis of the unilateral ranging method. Thus, the time used for two communications can reduce the impact of the error introduced by the clock offset on the ranging. Device A and device B are two devices with DW1000 modules, as shown in Figure 2. Device A firstly initiates a ranging

Figure 1. Photograph of physical hardware.

Figure 2. Principle diagram of bilateral ranging.

request, and Device B sends back a response after receiving the request. After receiving the response, Device A sends a second ranging request, and Device B receives this request and completes a ranging process.

When the device processes data each time, it records the timestamp of the current processing. In this way, the transmission time difference can be obtained through the relationship of the timestamp:

$T_{\text{prop}}=\frac{T_{\text{round1}}\times T_{\text{round2}}-T_{\text{reply1}}\times T_{\text{reply2}}}{T_{\text{round1}}+T_{\text{round2}}+T_{\text{reply1}}+T_{\text{reply2}}}$ (1)

Thus, the measured distance is equal to the transmission time $T_{\text{prop}}/2$ multiplied by the speed of light c. The error introduced by the bilateral ranging method：

$\text{error}={\hat{T}}_{\text{prop}}\times \left(1-\frac{k_a+k_b}{2}\right)$ (2)

where $k_a$ represents the ratio of the actual frequency and the expected frequency of device A’s clock, and $k_b$ represents the ratio of the actual frequency and the expected frequency of device B’s clock. Assuming that the clock accuracy of device B or device A is 10 parts per million, $k_a=0.99999$, $k_b=1.00001$, the distance between the devices is 100 m. Thus, the error is $10\times 333\times {10}^{-9}$ seconds, and the corresponding ranging error is 1.1 mm, which is completely negligible. Therefore, the bilateral ranging method is widely used. Using the above ranging algorithm, the ranging information can be obtained for positioning.

4. Location Process Based on Genetic Algorithm

This system obtains the distance data of the unknown tag $\left(x,y\right)$ to different base stations through the UWB ranging technology, and uses software to preprocess the distance data. According to the preprocessed distance data, a positioning 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}$ (3)

where $\left(u_k,v_k\right)$ denotes the k-th base station’s position; $d_k$ and $\sqrt{{\left(x-u_k\right)}^2+{\left(y-v_k\right)}^2}$ denote the measured distance and actual distance between the k-th base station and the unknown tag respectively; $e_k$ denotes the ranging error. Finally, the genetic algorithm is used to solve the positioning equation, and the precise position of the unknown label is given. The specific positioning process is as follows:

Step 1. Preprocess the distance data.

As shown in Figure 3 (a) is measured data at 12.35 meters; (b) is measured data at 11.01 meters; (c) is measured data at 6 meters, the measured distance data fluctuates little. Therefore, simple averaging can be used for preprocessing.

Step 2. Initial population.

Suppose the population size is N, and the generation group is $\left\{X_1^g,\cdots ,X_n^g,\cdots ,X_N^g\right\}$, where $X_n^g=\left(x_n^g,y_n^g\right)$ is the n-th individual in the g-th generation population, $n=1,2,\cdots ,N$, $g=1,2,\cdots ,G$.

(a)(b)(c)

Figure 3. Measuring distance data.

Step 3. Calculate fitness value.

The fitness value is used to evaluate the quality of an individual. The smaller the fitness value, the better the individual, and the larger the fitness value, the worse the individual. According to Formula (3), the fitness function value is defined as

$f\left(X_n^g\right)=\frac{1}{K}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{\left(\sqrt{{\left(x_n^g-u_k\right)}^2+{\left(y_n^g-v_k\right)}^2}-d_k\right)}^2}$ (4)

Step 4. Selection.

The selection operator is applied to the group. The selection operation uses a roulette operator, which is realized by accumulating the probability.

Step 5. Crossover.

The crossover operator is applied to the group, and the two selected individuals are generated according to the single-point crossover method.

Step 6. Variation.

The mutation operator is applied to the group, and the selected individual generates a new individual through the basic position mutation method.

Step 7. The next generation group $g=g+1$ is obtained, after the group g undergoes selection, crossover, and mutation operations.

Step 8. Repeat steps 3 to 6 until the maximum evolution number is reached, and the final result is the estimated location of the unknown tag. Figure 4 shows the flow chart of the positioning process.

5. Experimental Results and Analysis

The actual measurement environment of UWB positioning system based on the genetic algorithm is shown in Figure 5. $\left(x,y\right)$ is the position of the unknown tag. The locations of the four base stations are A (0, 0), B (0, 12), C (12, 12), D (12, 0). The main base station A uniformly processes the measurement information from other base stations, and transmits the information to the upper computer PC through the USB data cable. The parameters of the genetic algorithm are shown in Table 1.

The root mean square error (RMS) of positioning is defined as:

$\text{error}=\sqrt{{\left(\hat{x}-x\right)}^2+{\left(\hat{y}-y\right)}^2}$ (5)

Table 1. The parameters of the genetic algorithm.

Figure 4. Positioning flowchart.

Figure 5. Actual measurement environment.

where $\left(x,y\right)$ is the estimated location of the unknown tag. During the test, the unknown tag is placed in different positions. The different estimated positions and the corresponding RMS errors are shown in Table 2. The estimated coordinates of the root mean and different positions square error of positioning are shown in Table 2. It can be seen from this table that the measured positioning accuracy is within 30 cm.

Table 2. Location statistics of some target tags.

6. Conclusion

This paper designs a UWB positioning system that is based on genetic algorithm, which can solve the precise position of the unknown tag. The positioning experiment test shows that the positioning accuracy of the system is within 30 cm, which can well meet the positioning requirements. However, the system only considers the situation under the line-of-sight environment, and the situation under the non-line-of-sight environment needs further study.

Conflicts of Interest

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

References

[1]	Chen, K., Li, Z., Ma, L. and Tang, Y. (2020) Intelligent Agriculture—Agricultural Monitoring and Control Management System. In: Xu, Z., Parizi, R., Hammoudeh, M. and Loyola-González, O., Eds., Cyber Security Intelligence and Analytics, CSIA 2020, Advances in Intelligent Systems and Computing, Vol. 1146, Springer, Cham, 317-325. https://doi.org/10.1007/978-3-030-43306-2_45
[2]	Anitha, D., Shelke, V.D., Anupama, C.G., et al. (2020) Intelligent Wireless Sensor Networks for Precision Agriculture. In: Artificial Intelligence and Evolutionary Computations in Engineering Systems, Springer, Singapore, 167-181. https://doi.org/10.1007/978-981-15-0199-9_15
[3]	Zhang, J., Liu, R., Yin, K., et al. (2018) Intelligent Collaborative Localization among Air-Ground Robots for Industrial Environment Perception. IEEE Transactions on Industrial Electronics, 66, 9673-9681. https://doi.org/10.1109/TIE.2018.2880727
[4]	Zhang, H., Chen, N. and Fan, G. (2019) An Improved Localization Algorithm for Intelligent Robot. 2019 IEEE 12th International Congress on Image and Signal Processing, Bio-Medical Engineering and Informatics (CISP-BMEI), Huaqiao, 19-21 October 2019, 1-5. https://doi.org/10.1109/CISP-BMEI48845.2019.8965664
[5]	Corro, H., Robles, E., Merchan, F., et al. (2019) Design and Implementation of a Lo-Ra-Based IoT Network for Environmental Parameters Monitoring. 2019 IEEE 7th International Engineering, Sciences and Technology Conference (IESTEC), Panama City, 9-11 October 2019, 596-600. https://doi.org/10.1109/IESTEC46403.2019.00112
[6]	Safia, A.A., Al Aghbari, Z. and Kamel, I. (2019) Distributed Environmental Event Monitoring Using Mobile Wireless Sensor Network. Procedia Computer Science, 155, 335-342. https://doi.org/10.1016/j.procs.2019.08.048
[7]	Luo, J. and Gao, H. (2016) Deep Belief Networks for Fingerprinting Indoor Localization Using Ultra Wideband Technology. International Journal of Distributed Sensor Networks, 12, Article ID: 5840916. https://doi.org/10.1155/2016/5840916
[8]	Güler, S., Abdelkader, M. and Shamma, J.S. (2019) Infrastructure-Free Multi-Robot Localization with Ultra-Wideband Sensors. 2019 IEEE American Control Conference (ACC), Philadelphia, 10-12 July 2019, 13-18. https://doi.org/10.23919/ACC.2019.8814678
[9]	Ji, Y., Hejselbæk, J., Fan, W., et al. (2018) A Map-Free Indoor Localization Method Using Ultra Wideband Large-Scale Array Systems. IEEE Antennas and Wireless Propagation Letters, 17, 1682-1686. https://doi.org/10.1109/LAWP.2018.2863291
[10]	Sackey, S.H., Chen, J., Henry, A.J., et al. (2019) A Clustering Approach Based on Genetic Algorithm for Wireless Sensor Network Localization. 2019 IEEE 15th International Conference on Computational Intelligence and Security (CIS), Macao, 13-16 December 2019, 54-58. https://doi.org/10.1109/CIS.2019.00020
[11]	Ren, Q., Zhang, Y., Nikolaidis, I., et al. (2020) RSSI Quantization and Genetic Algorithm Based Localization in Wireless Sensor Networks. Ad Hoc Networks, 107, Article ID: 102255. https://doi.org/10.1016/j.adhoc.2020.102255
[12]	Kanwar, V. and Kumar, A. (2020) DV-Hop Based Localization Methods for Additionally Deployed Nodes in Wireless Sensor Network Using Genetic Algorithm. Journal of Ambient Intelligence and Humanized Computing, 11, 5513-5531. https://doi.org/10.1007/s12652-020-01907-1
[13]	Díez-González, J., Álvarez, R., González-Bárcena, D., et al. (2019) Genetic Algorithm Approach to the 3D Node Localization in TDOA Systems. Sensors, 19, 3880. https://doi.org/10.3390/s19183880
[14]	Sharma, G. and Kumar, A. (2018) Improved Range-Free Localization for Three-Dimensional Wireless Sensor Networks Using Genetic Algorithm. Computers & Electrical Engineering, 72, 808-827. https://doi.org/10.1016/j.compeleceng.2017.12.036
[15]	Li, J., Cui, X., Song, H., et al. (2017) Threshold Selection Method for UWB TOA Estimation Based on Wavelet Decomposition and Kurtosis Analysis. EURASIP Journal on Wireless Communications and Networking, 2017, Article No. 202. https://doi.org/10.1186/s13638-017-0990-4
[16]	Guangzhou LeNet Technology Co., Ltd. About Networking. http://www.gzlwkj.com
[17]	Xie, Y., Janssen, G.J.M., Shakeri, S., et al. (2017) UWB Pulse Detection and TOA Estimation Using GLRT. EURASIP Journal on Advances in Signal Processing, 2017, 1-12. https://doi.org/10.1186/s13634-017-0500-1
[18]	Yang, Z. (2018) TOA Estimation Algorithm Based on Noncoherent Detection in IR-UWB System. Wireless Algorithms, Systems, and Applications: 13th International Conference, WASA 2018, Tianjin, 20-22 June 2018, Vol. 10874, 201.
[19]	Choi, B., La, K. and Lee, S. (2018) UWB TDOA/TOA Measurement System with Wireless Time Synchronization and Simultaneous Tag and Anchor Positioning. 2018 IEEE International Conference on Computational Intelligence and Virtual Environments for Measurement Systems and Applications (CIVEMSA), Ottawa, 12-14 June 2018, 1-6. https://doi.org/10.1109/CIVEMSA.2018.8439949
[20]	Li, X.T., Lang, Y.X., Wei, Z.H., et al. (2019) Ultra-Wideband Positioning Technology and Application Research Based on Improved Two-Way Bilateral Ranging. China Test, 45, 21-27.