#The 4th LiChuang Competition# Indoor positioning demonstration system based on UWB

Note: * indicates a required field.
[Please fill in the form during the registration phase↓]
* Briefly introduce the work:
Ultra Wide-Band (UWB) is a new type of wireless communication technology. According to the specifications of the Federal Communications Commission of the United States, the operating frequency band of UWB is 3.1~10.6GHz, and the ratio of the system -10dB bandwidth to the system center frequency is greater than 20% or the system bandwidth is at least 500MHz. The generation of UWB signals can be achieved by modulating narrow pulses (such as secondary Gaussian pulses) with extremely short transmission time (such as 2ns) to the UWB operating frequency band through up-conversion methods such as differentiation or mixing. The main advantages of ultra-wideband are low power consumption, insensitivity to channel fading (such as multipath, non-line-of-sight channels), strong anti-interference ability, no interference to other devices in the same environment, strong penetration (can be positioned in an environment that penetrates a brick wall), and high positioning accuracy and positioning precision.
This demonstration system is developed based on UWB technology. With the help of UWB base stations and TDOA (time difference of arrival) positioning algorithms, UWB tags can achieve high-precision indoor positioning at the decimeter level. ****
[Please fill in ↓ during the competition stage]
***** 1. Project details; ****
**** This indoor positioning demonstration system mainly consists of three parts: the central positioning system (host computer, CLE), positioning base stations (synchronous base stations and slave base stations, Anchors), positioning tags (Tags) and Wi-Fi modules. Since the proprietary terms of these parts will be mentioned many times in the following discussion, they will be uniformly described as CLE, Anchor and Tag. The system structure diagram is shown below:
(1) CLE
CLE is a computing server (an ordinary PC can be used, which can run the IDE used for development normally). It parses the message information sent by each anchor, and then uses the parsed message data to synchronize the clocks of each base station. Then, the time data obtained after synchronization and the TDOA algorithm are used to calculate the tag position, and finally the calculation results are output in the form of (x, y, z) coordinates. The main work of this positioning demonstration system is to do two-dimensional positioning, so the default value of the z coordinate value is set to 0.
(2) Anchor
Anchor is a base station, including a synchronous base station (Sync Anchor) for sending synchronization packets and a slave base station (Salve Anchor) for receiving positioning packets; Sync Anchor sends synchronization packets (Clock sync frame) to each Salve Anchor in the form of a broadcast at a certain frequency (usually 10Hz), and sends the frame sequence number and sending time of each message sent to CLE in the form of a TCP synchronization sending message; Salve Anchor is in a constant receiving state, first it needs to receive the synchronization packet from Sync Anchor, record the frame sequence number and receiving time of each message, and organize it into a complete TCP synchronization receiving message, and at the same time, Salve Anchor also needs to receive the synchronization packet from Tag, and in the same way record the frame sequence number and receiving time of each message, organize it into a complete TCP positioning receiving message, and then continuously send the message to CLE. (Sync Anchor can be set to a compatible mode for sending and receiving through software, depending on the specific situation. If it is changed to this mode, the working mode of Salve Anchor in receiving mode is consistent.)
(3) Tag
Tag is a positioning tag, which is in a constant transmission state and sends positioning packets (Blink frame) to each Salve Anchor at a certain frequency (usually 1Hz). Tag does not need to record any information and is in a passive positioning state. Tag itself does not need to calculate its own position. CLE calculates the position of Tag and outputs the result in the form of coordinates.
(4) Wi-Fi module
In this project, the Wi-Fi module is used to forward TCP messages to CLE. Each Anchor will be connected to a Wi-Fi module, and the Wi-Fi module is set as a Client for forwarding TCP messages, and correspondingly, CLE needs to be set as a Server for receiving TCP messages; after such settings, the message data output to the serial port by each Anchor can be forwarded to CLE through the Wi-Fi module.
* 2. Describe the challenges faced by the work and the problems solved;
1. Challenges faced:
(1) It is not easy to determine the appropriate deployment environment;
(2) The crystal oscillator built into the UWB module is not a TXCO, so the clock drift is large, and this part of the error is difficult to avoid.
2. Problems solved:
(1) In response to the deployment environment problem, I raised the height of the base station as much as possible during the project, and tried to transmit signals between base stations in line of sight, reducing the obstruction when the tag communicates with the base station. (2)
In response to the accuracy problem of the hardware itself, this project consulted many documents in the relevant technical field during the process, and used the wireless clock synchronization algorithm to synchronize the clocks of each base station, and used the TDOA algorithm and EKF (Extended Kalman Filter) to calculate the tag position.
* 3. Describe the key points involved in the hardware and software parts of the work;
1. Key points of the hardware part:
The focus of the entire project is how to use UWB technology to accurately locate the tag at the decimeter level, so in the process of hardware design, we strive to be simple and clear, and do not make too many redundant designs according to project requirements. The hardware part is mainly composed of the following parts:
Main control MCU: STM32F103;
UWB module: DWM1000;
Wireless communication module: Wi-Fi module;
Power module: 3.3V-LDO power module;
Debug and burning port: SWDIO and SWCLK download debug port and TX and RX serial port print port;
The most important point to pay attention to during the hardware design process is the design and selection of the antenna of the DWM1000 module, because UWB signals are high-frequency electromagnetic waves and are more sensitive to occlusion, so in order to minimize the propagation error of the signal, it is necessary to ensure the line-of-sight propagation of the signal.
2. Key points of the software part
Clock Synchronization of the base station:
I believe that everyone who has done UWB indoor positioning knows that the biggest problem encountered when using the TDOA algorithm for indoor positioning is clock synchronization. How to ensure that the clocks between the positioning base stations remain synchronized is the top priority that affects the final positioning result. After all, a time error of 1ns brings a positioning error of 30cm.
Because each base station, whether it is the main base station that transmits the synchronization signal or the slave base station that receives the synchronization signal and the positioning signal, has its own independent clock. Therefore, when we use the TDOA algorithm to calculate the position, we must unify the timestamps of all base stations that receive the positioning signal to a common reference clock. Each base station is subject to its own independent hardware clock system, so the clock of each base station itself also has deviations at different times. The size of this deviation mainly depends on the accuracy of the crystal oscillator (if you don’t care so much about the cost and want higher positioning accuracy, then the active low-frequency deviation crystal oscillator is indispensable).
Before talking about synchronization, I will first explain the clock error. The error of UWB mainly comes from two aspects:
1). The clock deviation (drift) caused by the crystal oscillator of each base station itself;
2). The clock system (offset) of each independent base station.
Therefore, after understanding the source of the deviation, we can perform targeted clock calibration. After analyzing and counting the data of each anchor receiving timestamp, we can find that the independent clock drift of each anchor is increasing in a certain time unit.
(1) Synchronization message and positioning message
Next, I will analyze the clock synchronization of each base station from the simplest to the most complex through this project. First, let's consider a relatively simple situation, which is the demonstration system implemented by our project. In the positioning system, there are 4 base stations (Anchor) and 1 located tag (Tag), where the Tag sends positioning packets (posPacket) at a certain frequency. One of them is used as the master anchor, which is used to send synchronization packets (syncPacket) and receive positioning packets (posPacket), and records the syncPacket sending time and the posPacket receiving time of the synchronization message respectively. The other three are used as slave anchors, which receive synchronization packets and positioning packets at the same time, and record the syncPacket receiving time and the posPacket receiving time of the synchronization message respectively. Let's analyze how the clock is synchronized in this case.
(2) Message sequence number
In the positioning system we introduced above, the main base station sends synchronization packets at a time interval of 150ms, and the tag sends positioning packets at a time interval of 1s. For each message containing a timestamp, there is also a sequence number that increases in sequence. This sequence number starts from 0 and goes to 255, and it repeats in a cycle. This cyclic increasing sequence number is very important for our synchronization, which will be described in detail below.
(3) Message timestamp
The previous section described the sequence number in the message. This section will describe another key information in the message, that is, the timestamp. As a clock system that is not a perpetual calendar, time will not grow indefinitely. This is of course. The clock system of the UWB chip counts in a fixed period. The system uses a 40-bit binary integer to represent the timestamp, where the minimum counting unit of the system time is approximately:
So the fixed period of the clock system is approximately:
So the local clock will overflow every 17.21s, so corresponding boundary processing is required when performing time synchronization.
(4) Boundary processing of sequence numbers and timestamps
When any salve anchor in the system receives a syncPacket from a master anchor or a posPacket frame data from a tag, the sequence number of the frame data and the timestamp of receiving the frame data will be recorded on each frame data. If the sequence number or timestamp recorded on the frame data is less than the value of the previous frame data, it means that the counter of the anchor has overflowed and needs to be corrected accordingly. The correction can be performed according to the respective cycles.
(5)
Detailed explanation of clock synchronization The overall schematic diagram of clock synchronization is as follows:
The figure above shows the current positioning system receiving and sending positioning and synchronization messages on the time axis. T represents the tag sending positioning messages to each anchor, which is the blue line in the figure above. A positioning message is sent every 1 second. A0-A3 are anchors, of which A0 is the master anchor and A1-A3 are salve anchors. The red line is the synchronization message, which is sent every 150ms. In order to describe the synchronization process of the entire system clock in more detail, we take the process of a salve receiving a message and performing synchronization and illustrate it, as shown in the figure below:
In the above figure, T is the tag for sending positioning messages, MA represents master anchor, and SA represents salve anchor. Whenever T sends a positioning message, MA and SA record the time RX of the current reception of the positioning message and the sequence number SeqNum of the current frame after receiving the message; MA records the sending time TS and sequence number SeqNum of the message each time it sends a synchronization message. Similarly, SA records the receiving time RS and sequence number SeqNum after receiving the synchronization packet. For any SA, when it receives a positioning message, it must have received a synchronization message from the MA at the previous moment. According to our previous analysis, the system clock drift caused by the crystal oscillator increases regularly, so we look for the synchronization message of the previous frame based on the current synchronization frame. At this time, we can use the previous two frames of synchronization messages closest to the positioning message to synchronize the SA clock to the MA clock. The same principle can be extended to each SA, and the time when each SA is synchronized with the MA can be obtained. Based on this theory, the clock modeling of each anchor can be performed.
The above description is the clock synchronization solution used in this project.
Tag location calculation:
To calculate the tag location, you first need to give the coordinate information of the base station, and it is relatively accurate location information. Our project uses a two-dimensional positioning solution, so you only need to determine the (x, y) coordinates of each base station when deploying the base station. The current deployment of the project in the laboratory is as follows:
'Sync_Anchor':{'x':68.811,'y':20.981}
'Salve_Anchor1':{'x':62.981,'y':22.321}
'Salve_Anchor2':{'x':62.931,'y':27.056}
'Salve_Anchor3':{'x':68.846,'y':28.352}

(1) TDOA algorithm
In theory, it is very simple to use the TDOA algorithm to calculate the target position. It only uses high school knowledge. The Chinese explanation of TDOA (Time Difference Of Arrival) is the time difference between the positioning packet sent by the tag and the arrival of each base station. Why can we use this difference to calculate the position? At this time, we have to mention the hyperbola. What are the properties of the hyperbola? One of them is that the distance difference between the upward point of the hyperbola and the two foci is a constant. If the foci are regarded as the positions of the base stations, then the position of the tag is the intersection of the hyperbolas. Therefore, the essence of the TDOA algorithm is to find the intersection of multiple hyperbolas in two-dimensional space. Next, I will summarize the TDOA algorithm with a schematic diagram.
Assume that there are three base stations A0, A1 and A2. In this example, it represents two-dimensional positioning (the principle is relatively simple to describe), but this method is also applicable to three-dimensional positioning.
Assume that there is a tag to be located. In this example, CF is located at the coordinate (0.0, -0.5). The red lines in the figure are the straight-line distances between the base stations, which can be regarded as the focal lengths of the hyperbola in mathematics. Base stations A0 and A1 form a branch of a blue hyperbola. Similarly, A0 and A2 form another branch of a yellow hyperbola. A1 and A2 form the last branch of the green hyperbola. The intersection of these three curves is the location of the located tag. When the focal position, focal length and TDOA are known, the location of the tag can be solved using the equation of the hyperbola. Every time the tag moves, the corresponding TDOA will change, so the result of the re-solution will also change. In this way, the location of the tag can be obtained in real time.
(2) EKF (Extended Kalman Filter)
Since the location of the located target can be solved using the TDOA algorithm, why do we still need to use the extended Kalman filter?
This is because the above-mentioned solution process is a geometric solution calculated theoretically, but in actual application scenarios, due to the existence of measurement errors, interference in the signal transmission process, environmental noise, hardware errors and other reasons, the measured TDOA is not accurate, which may result in the theoretical geometric intersection not existing in the located target area, and the location of the tag cannot be obtained. Therefore, we need to use the extended Kalman filter to predict the actual location of the current tag based on the previous position of the located target and the actual calculated position. In addition, when calculating, we no longer calculate the theoretical geometric solution, but use approximate methods to obtain approximate solutions.
I will not elaborate on the specific knowledge of the extended Kalman filter in this document. I will upload the detailed explanation document of the extended Kalman filter referenced in this project in the open source document.
* 4. List of materials for the work;
(1) Schematic diagram of the base station and tag (for the sake of simplicity, the base station and tag of this project use the same hardware design, and the working mode of each hardware is set through the program);
(2) **PCB diagram of the base station and tag**;
(3) **BOM sheet of the base station and tag**;
(4) **Configurable Wi-Fi module**;
(5) **Embedded software code (Testing Only)**;
**Notes: **The above materials can be used to build the hardware part of the entire project and the embedded software part used only for testing.
* 5. Upload pictures of the work;
(The PCB must have the competition logo and take a photo to upload. If not, it will be deemed as giving up the competition)
* 6. Demonstrate your work and record it into a video and upload it;
(The video content must include: introduction of the work; function demonstration; performance test; close-up of the competition logo on the PCB; if not, it will be deemed as giving up the competition)
7. Open source documents.
references
(1) Project board schematic;
(2) Project board PCB diagram;
(3) Project embedded test code;
(4) Complete project introduction information;
(5) Current algorithm reference document;
(6) Project board static image;
(7) Project demonstration video.