Precise Indoor Positioning Based on UWB and Deep Learning

The most common approaches for indoor positioning are Angle of Arrival (AOA), Received Signal Strength Indicator (RSSI) [5, 6], and Time of Arrival (TOA) [7, 8].

The Angle of Arrival approach is based on the angle measurements. According to [9], there are two main coordinate frames for AOA ranging. The first frame is the so-called local frame which is a spheroidal coordinate frame with origin of local anchor node. This type of coordinate frame uses the anchor node to measure and determine the direction of the target and the distance between the target and itself. After measurement, the obtained data in spheroidal coordinate frame is processed and converted to the second type of coordinate frame called global frame. Global frame consists of a standard three-dimensional coordinate frame with $x$, $y$, $z$ axis. Therefore, the current location of the target can be detected. Theoretically, two anchor nodes with known locations are enough for an AOA positioning system.

The RSSI method measures the path loss of the signal transmitted from the target to an anchor node. By measuring the received signal strength and comparing with transmitted signal strength, the value of strength difference can be calculated. Then, this value becomes the input of a theoretical propagation attenuation model which converts measured value to useful distance parameters. These parameters are further used to determine the location of the target [10].

Time of Arrival is another approach which can be used to obtain the distance between the target and anchor node. According to [11], there are two kinds of TOA techniques. The first type is called one-way TOA, which requires prefect synchronization of system clocks at both the target and anchor node. In one-way TOA, the target sends a clock information to the anchor node. Therefore, the anchor node can compare the time difference between transmitting and receiving, which can be used to calculate the propagation distance from the target to anchor node. The second type is called two-way TOA ranging, which does not need a synchronization of system clocks. The anchor node sends a request message to the target and record the sending time locally. The target then transmits an acknowledgement back to the anchor node after receiving the request message. By doing this way, the anchor node can also calculate the time difference and associate distance parameter in the end.

Compared with AOA, RSSI and TOA approaches require at least three anchor nodes deployed at fixed locations [7]. The Trilateration algorithm is a commonly used method for calculating the target node location. For a two dimension environment, three anchor nodes are needed to determine the location of a target node. Each anchor node measures the distance between the target and the anchor node itself. Three ranging circles can be produced based on the received data by sharing measurement data with each other. The target’s putative position is defined by the intersection of these circles. However, positioning accuracy can be degraded due to several practical issues [7]. For example, environmental noises might interfere with the ranging signal, lowering the precision of measurement during the ranging process. Aside from that, range accuracy might be impacted by the Non-Line of Sight (NLOS) problem, which occurs when an impediment blocks the direct sight from the anchor node to the target. Besides the above mentioned methods, emerging radio sensing techniques, such as [12, 13, 14, 15] can also be used for indoor positioning.

In fingerprint positioning, the whole positioning area is divided into several equal parts [7]. There are two major phases in fingerprint methods: offline phase and online phase. In the offline phase, the system records location information of all reference points distributed in a testing zone, which sets up a local database to store the ‘signature’ of the entire testing zone [16]. In the online phase, the ranging techniques such as AOA, RSSI, or TOA can be applied to obtain real-time data of the target node. By matching the signature and estimation, the best location information can be determined [16].

The machine learning algorithm [17, 18] is one of the most popular and common methods utilized nowadays to implement fingerprint theory. There are many distinct strategies used in machine learning algorithms; two well-known techniques are Decision Tree (DT) and Support Vector Machine (SVM). Decision tree can gather fingerprint with different operations in offline and online phases. According to [19], the location parameters should be measured and recorded before setting up a decision tree model. The entire testing zone can be divided into multiple grids. The characteristics of location data in each grid can be analysed to train the decision tree algorithm so that different decision labels can be created. After learning, the characteristic of new location data of target is compared with decision labels to classify the current data into the data cluster with the most similar label. Furthermore, the best pair of coordinates can be determined after input data going through the decision tree and completing iterative classification process [20].

Support Vector Machine is another proven technique which can applied for indoor positioning application combining with the fingerprint concept. Compared to other ML algorithms, SVM is one of the supervised algorithms which maintains a relatively low level of computation complexity [21]. It aims to train the algorithm based on existing data, and classify new input based on calculating difference between the training model and new input. These basic features make SVM suitable for solving regression problem. However, specific training logic of SVM leads to drawbacks such as time consuming and large memory occupation [7].

Deep learning and neural networks, in addition to traditional machine learning methods, can be used for indoor positioning applications. The Non Line-of-Sight (NLOS) issue [22, 23, 24, 25, 26] is one of the most serious shortcomings of indoor positioning. When an obstacle blocks the direct link between a target and an anchor node, signals sent by the target may still be received by the anchor node. However, range parameters such as RSSI and TOA might be less precise, if not erroneous, reducing the overall system’s positioning accuracy [27].

Deep learning and neural networks are essentially extensions of machine learning. This type of algorithms may be treated as a network made up of many nerve cells. When an input is provided to the algorithm, one or more nerve cells will capture it in order to create an associated output depending on internal rules. Upper cells’ outputs will be used as inputs by the cells below. This procedure will continue until the final nerve cell produces an output that is deemed the system’s ultimate results.

Each nerve cell is given a weight to assure the algorithm’s learning capabilities. Before moving on to the next cell, the input data needs to be adjusted depending on the relevant weights. Algorithms can then learn the characteristics of data and modify weights to optimize the result. Such functions can be accomplished in a variety of ways. For instance, according to [27], Radial Basis Function (RBF) is integrated with neural networks. To begin, get the weights from the neural network’s input and hidden layers. Then, using the hidden layer output and weight values determine the final result. There are numerous primary aspects that might impact the positioning system’s learning efficiency and accuracy. As stated in [27], the required training time is a crucial factor. Longer learning time with enough amount of training samples can improve system performance significantly. Additionally, the number of neurons in hidden layer is another crucial factor which can significantly impact the accuracy [28]. However, the larger the number of neurons, the higher the memory capacity required. As a result, there is a trade-off to be addressed between system load and placement precision.

The Back Propagation (BP) Neural Network is one of the most appealing methods employed and developed in terms of neural network implementation in indoor positioning applications. The BP neural network, like a normal feed-forward neural network structure with a supervised learning algorithm, has at least three layers divided into three categories. The input layer and output layer are first two categories of layers included in the BP neural network structure, where the number of nerve cells for both input and output layers can be adjusted depending on the requirements of specific applications. Apart from that, the BP neural network could extend the size of hidden layer with relatively high level of flexibility. The special structure and relatively high flexibility of the BP neural network provide significant advantages. According to [29], the BP neural network has a strong ability on non-linear representation and prediction. Additionally, benefiting from strong self-learning ability, a BP neural network can theoretically learn and simulate all the abstract functional relationship between multiple variables [30].

In this work, we use mathematics tools and real measured distance values to generate a database of the location data at different coordinates of the testing zone.

Based on our observation, there is a linear relationship between the measured distance and the real distance between an anchor node and a mobile target. This relationship can be described by eq. 1, where $d_{real}$ and $d_{test}$ represent the real and test distance between an anchor node and the target, respectively, and $a$ and $b$ are two real values.

To determine the values of $a$ and $b$, at least two reference points with known coordinates are required. The $d_{real}$ is known for two reference points based on coordinates, and the distance $d_{test}$ from each reference point to an anchor node can be measured during the experiment. By applying data into eq. 1, we can calculate the values of $a$ and $b$. In our work, to minimize the error between the measured distance and real distance, we do the experiment several hundreds times to get the values of $a$ and $b$. Based on these values and eq. 1, we can be then generate training database for our developed BP neural network.

In this project, we used a UWB hardware system to determine the location of the target node. The coordinate for each location of the target node is computed via geometric calculation based on collected TOA distance data. The system is illustrated in Fig. 5.

The system consists of four UWB devices, three of which are anchors nodes, i.e., A0, A1, and A2 with known locations. The testing zone is of size 2x1 meters. Another UWB device is used as a mobile target node. Based on the TOA technique, the distances from the target node to all the three anchor nodes,i.e, d0, d1, d2 can be measured.

After data collection, the trilateration method is used to determine the location coordinate of the target node based on the distance measurements. The calculated coordinate is then compared with the known coordinate. The distance between these two coordinates can be calculated and utilized as a measurement of system performance.

A flow chart of the training model in the distance database generation process is described in Fig. 6.

As shown in the flow chart, the coordinates for pre-set points are declared in the beginning of the process. Based on the distance measurements from the target node at each pre-set point to all anchor nodes, the values of $a$ and $b$ of eq. 1 can be determined. These values are then used for generating distance database for the entire testing zone.

Fig. 7 illustrates the flow chart for the entire positioning process.

The overall positioning process can be divided into five steps. In the first step, the coordinates of three anchor points are declared. Apart from that, the data measurements are loaded to program memory before starting to execute following steps. In the second step, the trilateration method is used to calculate the location of the target node. (This is the performance of positioning system without using the neural network). In the third step, the loaded data for both training and testing are assigned to corresponding input and output sets before feeding to the neural network module. In the fourth step, all training and testing data needs to be normalized so that all data can be unified in the same level of magnitude. The last step is to build the BP neural network, training and testing the location of the target node based on the BP neural network.

There are six points selected and tested during the experiments. We observed that when real distance is longer than 1000 mm, the measured distance is always greater than the actual real distance. Therefore, measurement calibration is introduced in order to compensate the errors. We scale down the measured data to $K$ percent of its original value if the original value is greater than 1000 mm, where $K$ is set to 90, 85, and 80 respectively. The calibrated data is then passed to the Trilateration module as well as the BP neural network module for calculating the target node’s coordinate. We then calculate the distance error between each reference point and the calculated target point. The results for the Trilateration method and the BP Neural Network method are shown in Figs. 8 and 9, repectively.

From Fig.8 we can see, measurement calibration can improve the error performance for the system using conventional trilateration methods. With the enhancement of calibration, the mean error distance of most of testing points decrease, which means that the accuracy of the positioning system is improved. However, for the system using the BP Neural Network method, the error performance does not improve as shown in Fig. 9. One probable explanation is that the suggested calibration procedure is so radical that some of the measured data’s properties are over-corrected and the basic learning algorithm with the BP neural network is highly referring on the typical characteristics of data. On the other hand, by comparing the results in both Figs. 8 and 9, it is clear that the positioning system using the BP neural network provides better performance than the system based on conventional trilateration methods.

Although measurement calibration method tested in the project generally improves error performance of the positioning system, this method is not reliable in a general situation due to its limitations. First, this calibration method can lead to over correction issues, which can be verified by the results of testing point (250, 500), (750, 500), and (750, 1500) in Fig. 9. With the enhancement of calibration, the mean error distance increased, which means the BP neural network is misled by over corrected training data. second, in a general situation, measured error can be caused due to various of factors. The effect of self-defect of equipment can only be one of the major factors. The interference of operation environment, the different complexity of testing field can also impact the final accuracy of positioning system. Therefore, this measurement calibration method can be hardly applied to a general case in practice.

As described in Section III, the coalescent training is an approach which integrates the features of both the TDT and TNT methods. By applying this approach to the BP neural network, we obtain the following results shown in Fig. 14

To observe the performance of the system intuitively, there are six plots generated and shown in Fig. 15 based on the obtained results. The precise position coordinate of each individual testing point is represented by the red dot in the Figure. The dark blue region for each testing point represents the mean error range using the BP neural network algorithm for positioning. On the other hand, the bright blue region represents the mean error range using the trilateration method. It can be seen from Figs. 14 and 15 that the CT-based BP neural network brings a significant improvement on positioning accuracy. Compared to the conventional trilateration method, the CT-based BP neural network approach brings about 73 percent improvement on system accuracy in average.