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:
(1)
Thus, the measured distance is equal to the transmission time
multiplied by the speed of light c. The error introduced by the bilateral ranging method:
(2)
where
represents the ratio of the actual frequency and the expected frequency of device A’s clock, and
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,
,
, the distance between the devices is 100 m. Thus, the error is
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
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:
(3)
where
denotes the k-th base station’s position;
and
denote the measured distance and actual distance between the k-th base station and the unknown tag respectively;
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
, where
is the n-th individual in the g-th generation population,
,
.
(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
(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
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.
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:
(5)
Table 1. The parameters of the genetic algorithm.
Figure 5. Actual measurement environment.
where
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.