|Home | About | Journals | Submit | Contact Us | Français|
This paper describes the development and implementation of a robust high-accuracy ultrasonic indoor positioning system (UIPS). The UIPS consists of several wireless ultrasonic beacons in the indoor environment. Each of them has a fixed and known position coordinate and can collect all the transmissions from the target node or emit ultrasonic signals. Every wireless sensor network (WSN) node has two communication modules: one is WiFi, that transmits the data to the server, and the other is the radio frequency (RF) module, which is only used for time synchronization between different nodes, with accuracy up to 1 s. The distance between the beacon and the target node is calculated by measuring the time-of-flight (TOF) for the ultrasonic signal, and then the position of the target is computed by some distances and the coordinate of the beacons. TOF estimation is the most important technique in the UIPS. A new time domain method to extract the envelope of the ultrasonic signals is presented in order to estimate the TOF. This method, with the envelope detection filter, estimates the value with the sampled values on both sides based on the least squares method (LSM). The simulation results show that the method can achieve envelope detection with a good filtering effect by means of the LSM. The highest precision and variance can reach mm and mm, respectively, in pseudo-range measurements with UIPS. A maximum location error of mm is achieved in the positioning experiments for a moving robot, when UIPS works on the line-of-sight (LOS) signal.
Satellite signaling systems are universally well known. One example is the global positioning system (GPS), which has a high positioning accuracy at 0.15 m . It is very convenient to use satellites to obtain locations. Unfortunately, satellite positioning signals normally cannot be received indoors due to obstructions from buildings, and people have to do most of their work (an estimated 87 percent overall) indoors .
Because of the reasons outlined above, indoor positioning systems (IPSs) have gained increasing attention from researchers across the globe in the last few decades, as IPSs are widely used in health-care as well as in home and building automation [3,4,5,6]. There are already many local positioning systems based on different technologies, and they each have their own advantages and weaknesses. Systems based on infrared beams make use of the scanning sweep method and are very inexpensive for users, but only have accuracy up to 57 cm . Xiaohan Liu et al.  developed an IPS using a visible light communication platform, which has an accuracy of 10 cm, but it requires expensive infrastructure. The ultra-wide-band (UWB) is a great option for IPS and has a strong anti-interference capability, but it needs more infrastructure and is expensive for users . IPS based on computer vision  has the highest precision of the all technology proposals, but it is too expensive and lacks wide applications. The other local positioning solutions consist of radio frequency identification (RFID) , WiFi , and ZigBee , and they have a low positioning accuracy.
Compared to these above technical solutions, a positioning system based on the ultrasonic signal and a wireless sensor network (WSN) has many advantages, including slow propagation speed (about 340 m/s), so that the hardware for the received ultrasonic signals can be simple, obtaining cost savings. The time-of-flight (TOF) of the signal from a transmitter device to a receiver is used to calculate the distance in the UWB and ultrasonic solutions, but a lower time synchronization accuracy between different nodes can be tolerated for the ultrasound’s speed, compared to the speed of electromagnetic wave propagation in the UWB system. The ultrasound signal is weakly influenced by the surroundings and has a negligible penetration of walls, and this can enhance its practical value in the proposed ultrasonic indoor positioning system. Besides, ultrasonic transducers can be integrated easily into the mobile phone system . This is almost equivalent to adding a new human organ, and the location of the person is conveniently completed by it.
There are already many methods of ultrasonic signal processing for distance measurement, including non-destructive testing [15,16]. The envelope signal extracted by these methods has some harmonics that cannot be ignored, and this will affect the measurement accuracy if they are used in ultrasonic indoor positioning systems (UIPSs). The Cricket location system  detects the arrival of the ultrasound with a threshold value. It is simple, but has low precision due to noise interference. The random signal processing method is used to estimate ultrasonic TOF in some works in the literature [18,19], considering environmental noise, but these algorithms are too complex for UIPSs based on WSNs. The ultrasonic signals are encoded into various digital codes, such as binary frequency shift-keyed and code division multiple access codes [20,21,22,23]. These methods can indeed improve the stability of system, but are difficult to decode because of ultrasonic vibration inertia. The acoustical signals are modulated into four sets of orthogonal chirps with multiple access to solve signal interference in , but the chirp signals in conjunction with cross correlation are very complex, and the time resolution of the system for position will be reduced. The frequency-hopping spread spectrum (FHSS) has been introduced into the field of IPS to solve the multiple-access problem [25,26], but the ultrasonic transducer has a narrow frequency bandwidth, which will increase the difficulty and cost of realizing FHSS. Quadrature sampling is used to detect the ultrasonic envelope with a low frequency , which is appropriate for the WSN system and can save power, but it has low robustness. Power is not a problem. Considering that the positioning system works indoors, a new envelope detection method (EDM) is proposed in this paper. The EDM can obtain a high accuracy and robustness in UIPSs.
The paper is organized as follows. In Section 2, the UIPS architecture is described. A detailed account of the principle of the EDM is given in this section. Section 3 describes the algorithm to measure the TOF of the ultrasonic signal and the location of the target. The implementation of the UIPS is shown in Section 4, including the hardware and software. Section 5 gives the experiment results for the EDM in the simulation and practical applications. Finally, the main conclusions of the whole work are summarized in Section 6.
The UIPS has many WSN anchor nodes that are placed at known positions of the indoor space, as shown in Figure 1. The anchor nodes are on the interior ceiling, and there is a WSN node on the mobile robot system, which is the positioning target. The distance values from the target node to every anchor node and their address and time information will be transmitted to the server via wireless WiFi, when all distance measurements are finished. The coordinates for the mobile robot can be calculated by the server when the distance values to all anchors in the same moment are received. The server can forward these coordinates on to users (robots here).
We assume that the number of the anchors is (), and the number of robots is () in a coverage area. Every anchor will send the ultrasonic signal separately at a different time, presented as , , in Figure 2a. Thus, the signal interference between different anchor nodes is avoided when the time synchronization signal (TSS) arrives in the first work mode. There is some time drift between different anchors, for which there must be a compensation algorithm, but it is very complex, and the accuracy is not high. The advantage with this mode is that it needs only one TSS for positions of all robots, and saves power. If just one anchor transmits the signal in a TSS in order to void the compensation for time drift, there needs to be TSSs for all robots, but the position will have large errors in both methods above when robots are moving. Because the measurements for the distances to all anchors are finished at different times, the position coordinates can only be calculated roughly through these distance values.
In the second work mode, the target nodes transmit the ultrasonic signal to the anchors, selected by the UIPS in this paper. Only one robot sends the signal that will be received by all anchors at the same time when the TSS for it arrives, and then the distances to all anchors are measured. The ultrasonic signal pulse is just 1 ms, which will be described later in this article. There is a reasonable assumption that the position for the moving robot will not change in so short a time, so this mode can be appropriate for mobile robot localization, although it needs more TSSs () for all robots. The information from the time synchronization node contains a robot address. The robot with this address will send the ultrasonic signal, and the remaining ones will not. The anchors distinguish the ultrasonic signals from each other with the address. The time synchronization node will cyclically transmit TSS to every robot in turn, so the resolution for UIPS will reduce when grows larger.
Ultrasound is a vibration wave, for which the amplitude will increase when it arrives at the peak. There will be a reducing process while the signal drops to the minimum amplitude value from the peak value. If the driving signal for the ultrasound is cut off immediately when the peak arrives, the signal will have a unique wave peak. The signal for this means can be described by Equation (1) .
where the parameters , , and are the signal amplitude, frequency, and phase, respectively. is also the envelope signal and is given by:
where is the amplitude parameter, and is the bandwidth factor. We can see that will obtain its maximum value when from the equation.
The original ultrasonic signal from the received transducer is shown in Figure 3a, and the envelope is presented in Figure 3b. The ultrasonic envelope detection aims to extract from . We consider that the time when the ultrasonic envelope arrives at its peak is the arrival time of the ultrasonic signal. That means the TOF for the ultrasonic envelope is in Equation (2), if is the start time for transmission of the signal. A rectangular window function with a length of N is defined as Equation (3). It will become , , and , , when the function is moving with a step of T, as shown in Figure 3c. T is the sampling period for the ultrasound signal. of the length of is selected in every window, when multiplies the window function.
The digitalized values are provided by the analog to digital converter (ADC) from with a sampling rate of (), given by:
where and stand for the amplitude sampling value of the envelope and the phase angle at time, respectively, and .
If the window function is discretized into with the same frequency , and we can get Equation (5) in the window i,
where and . Because the value of is small, at just ms in this paper (where and μs), ultrasonic signal is a mechanical vibration, with the characteristic of inertia. Its amplitude and phase have little change in such a short period of time. We can assume that the envelope value and the phase are constant for all j values in every window i, presented as and , respectively, and then we can obtain Equation (6) from Equations (4) and (5), where , , can be obtained from ADC sampling.
Equation (6) is written in the form of a matrix:
where the transposes of , and are given by:
Now, the problem is transformed into a method to estimate of Equation (7). The estimation of is (assumed ), and it can be determined using the least squares method for minimizing the following error function between and ():
The received nodes must know the time at which the transmitter node starts to generate the ultrasonic signal. Hence, there must be a time synchronization in these nodes, which is presented in the first part of this section, followed by TOF estimation and positioning.
The whole space is divided into several subspaces, and there is a reference node in every subspace. All anchor nodes of the subspace have a common ultrasonic signal coverage region, and the RBS node will be asked to broadcast the synchronization signal periodically to the anchor nodes and the target nodes by the server, when there are some positioning nodes that walk into the region. The transmitters will start to work, and the received nodes will begin sampling the signal as the synchronization broadcast is arriving.
The process of the transmission for TSS is shown in Figure 5. The central processing unit (CPU) of the reference node will start a timer count when it receives instructions from the server. The timer will generate an interrupt signal and count from zero again while the counter arrives at the TSS period, and then the CPU program will access the interrupt handing, where the synchronization frames are transmitted to the RF module. The frames will be encoded in the RF module and then transmitted to the receivers by the antenna. Receiving and decoding will be completed by the receivers with a reversed order of the sender when the TSS arrives at the receiving systems. Furthermore, the alignment for the received frames is finished and then an interrupt signal is generated for the CPU.
The velocity of the electromagnetic wave is the approximate speed of light in a vacuum, so the propagation time differences from different nodes are quite minor and can be ignored in a subspace. The synchronization protocol based on RBS suffers from the uncertainties of the transmission and reception times, as well as the yield synchronization error, which is about 13 s , and cannot meet the requirements of the UIPS. Several modifications are performed to reduce the error. First of all, the synchronization and other data transmissions have the same communication module as in the other system, but there are two different modules in the UIPS, and the modules will not be occupied by the data transmission process. The interrupt for transmitting and receiving have the highest priority, and will not be terminated by the other interrupt.
As described above, the rest factors for synchronization accuracy are in the RF module. CC2500 is selected as a synchronization module in UIPS, which can provide extensive hardware support for packet handling, data buffering, and burst transmissions . Encoding/decoding, transmitting/receiving, and alignment are affected by the traffic rate of the synchronization module. A testing experiment is designed in order to verify this and calculate accuracy. The reference node transmits eight bytes of synchronization data to the other node. The structure for the data frame is shown in Figure 6.
The length of the address is two bytes in the figure, and a command is used to distinguish data frames into time synchronization or data transmission. This takes up one byte. The next three bytes are data bits. Because data transmission is completed by WiFi module, the data bits are reserved for future research. The last two bytes are cyclic redundancy check (CRC) bits, which indicates whether the received data has some errors. There are two nodes in the experiment, the data frames are sent once every 200 ms, the receiver will return the data to the reference immediately when the receiving is finished. The time from the beginning of transmission to the end of receiving for the reference node is recorded as in the sender. The statistics of 500 measurements for every rate are shown in Table 1.
The difference between the maximum and minimum value of can indicate the precision of the time synchronization. This brings us to the conclusion that the higher the data communication rate is, the lower the differences are. The difference will be 1 s when the rate is above 100 kb/s, so the precision of the time synchronization should be less than 1 s because of one-sided communications in UIPS. The ranging measurement error, resulting from this, is less than mm, assuming the ultrasonic velocity is 340 m/s.
The analog-to-digital converter (ADC) of the received nodes starts to sample the ultrasound signal using a sampling frequency () when the synchronization data are arriving. The range of ultrasonic propagation is limited to 5 m in UIPS, so the time it takes to sample the signal is less than 15 ms, assuming the velocity is 340 m/s. The uncertain drift of the crystal oscillator of the received nodes can be ignored in this period. Therefore, the time instant at which the envelope reaches its maximum values () can be calculated with .
The parabolic interpolation method in which the adjacent samples around can reduce the TOF estimation () error , is given by:
where is the fractional correction term obtained from parabolic interpolation with three samples , given by:
The speed of ultrasound v in air depends on many factors. The influence of temperature is only considered in the special indoor condition, and it can be estimated with Equation (19) , where is the temperature in degrees Celsius,
Then, the distance between the target node and the anchor node i can be estimated with and v as:
The coordinate of the anchor node i is , and it is assumed that the number of the anchor nodes is k. The coordinate of the target node is . Then, these equations are obtained as:
where the left and right equations are subtracted from the first and second equations, respectively, and the equation is expressed in matrix form as:
where , and are referred to as:
The implementation of UIPS is based on embedded system design. A 32-bit ARM Cortex™-M7 microprocessor is selected as the hardware, which features a single floating point unit (SFPU) and supports single precision data processing instructions and data types. The software is programmed in a bare metal machine in which the registers of hardware can be read or written directly. The real-time performance of the system is strengthened significantly.
The node hardware of UIPS is designed for the core board with a size of 90 mm × 58 mm, shown in Figure 7. The core board is powered by a lithium battery (LB), which can be charged for reuse. It can be configured as a receiver anchor node and arranged in the interior ceiling. The specified extended board for the core board that is configured as the transmitter node can be used to control the mobile robot.
The microcontroller unit (MCU), the transmitter and receiver for ultrasound, the CC3200 and CC2500 modules, and the power system comprise the hardware system of UIPS, which is shown in Figure 8. UIPS has two STM32F722RCT6 32-bit MCUs, which have a running frequency up to 216 MHz and come from STMicroelectronics (http://www.st.com); one is the master, and the other is the slave with alternate sampling and calculation. This MCU integrates 512 Kbytes Flash memory with protection mechanisms and 256 Kbytes of static random access memory (SRAM) on chip. It has an abundance of peripheral resources and interfaces, such as a 12-bit ADC, a digital to analog converter (DAC), a timer that can produce the pulse width modulation (PWM) signal, universal synchronous or asynchronous receiver transmitters (USARTs) and a direct memory access (DMA) channel .
The signal strength of the ultrasonic transmitted transducer with a frequency of 40 kHz is too low to be sampled by the ADC directly, so it must be amplified firstly, and then processed by a band-pass filter to reduce the out-of-band noise. The ultrasonic received sensor can be driven by the PWM orsinusoidal signal, which can be generated by DAC. The former is adopted in UIPS. It can be obtained from the timer with high precision.
The CC3200  module communicates with the master MCU by USART, which can realize the transparent data transmission between the master and the server via the WiFi wireless network. The CC2500 module is used for time synchronization and communicates with the master MCU through the SPI interface. Besides, the module is linked to the master MCU via an input/output (IO) port in hardware.
The implementation of the algorithm for envelope detection in Section 2.2 requires a large number of matrix calculations using Equation (13), but some regularity can be found if Equation (10) is plugged into Equation (13). The elements of will be periodic and constant if the length N and sampling period T are constant, so all will also form a series of periodic coefficients. The coefficients in only one period are enough for the implementation of the algorithm, and are computed in advance using MATLAB and are written into the read-only memory (ROM) of the MCU in a table form. The computational complexity of the algorithm can be reduced significantly.
There are rich DMA channels and interrupt vectors on the MCU chip, with which the real-time and reliability performance of the software system can be enhanced. There is a joined IO port between the CC2500 module and the master MCU as described above. The module will produce a rising edge pulse signal when the time synchronization data come, which makes the software of the master go into an external interrupt vector with the highest priority of all. The system will have an alternating sampling and detection between the master MCU itself and the slave MCU, shown in Figure 6. The master will turn on the DMA channel and enable the timer to trigger the ADC for ultrasound signal acquisition with rate if it is time for the master itself. The software will run into the DMA interrupt service program when all M pieces of data are collected.
The envelope detection method presented in Section 2.2 is implemented in the DMA interrupt service program and then calculates the distance value from the target node to the anchor node; in the figure. The value will be transferred to the server through the WiFi network. The slave MCU will obtain the distance value like the master in the external interrupt program if it is its time, shown in the red dashed rectangle of the figure, and then transfer the value to the master through USART; finally, the master transfers it to the server. The whole software flow diagram is shown in Figure 9.
A simulation experiment using MATLAB is described to prove the validity of the envelope detection method in this section, meanwhile, the point-to-point ranging and the position for the mobile robot are presented to validate the UIPS’s performance.
The analog ultrasonic signal and its envelope are generated from Equations (1) and (2) in Section 2.2, which only has a peak, as mentioned earlier. Noise is inevitable in any practicable system, so the white Gaussian series are added to the signals with a different signal-to-noise ratio (SNR) in order to test the filtering effect of the algorithm in Section 2.2. The Hilbert transform (HT) is widely used for envelope detection in engineering , by which the ultrasonic envelope is also extracted for comparison with the method in this paper. The results are shown in Figure 10.
The envelope detection method based on LSM can detect the envelope of ultrasound with a high precision, comparing (a2) and (a4) in the figure, and there is no time delay for the peak between them. Filter effect analysis proves that the proposed algorithm can obtain a good filtering result, even if the SNR is very low (as shown from (b) to (d) of Figure 10). The method based on HT can detect the envelope too, but it has no filter effect from the third column on. This can only be achieved by means of some special digit filter. Besides, the HT is more complex.
The distance measurement experiment is completed to evaluate the accuracy of UIPS. A pair of nodes are at the same level as each other, which can guarantee that the nodes work on the LOS condition, avoiding interference for ultrasonic multi-path propagation. One is configured as the transmitter, and the other node as a receiver. The transmitter sent a PWM of 1 ms under the control of the time synchronization signal with a period of 200 ms. The ultrasonic signal completely disappears in such time, so that the influence of the last cycle will be avoided.
A commercial vision-based localization system (vicon) from Oxford Metrics Limited (www.vicon.com) is used to measure the separation between nodes, which has a precision of 1 mm. Firstly, some optics markers are planted around the ultrasound transducer symmetrically, shown in Figure 11, so that the position coordinates of two nodes can be obtained from the vicon system. They are and , and the distance is:
Eight group distances are measured, which have some random bits. The quadrature sampling (QS)  is achieved by UIPS to compare the method based on LSM in this paper. The statistics are shown in Table 2, where is an average of 500 times of measurement for each distance, is their variance, and is defined as:
where and represent respectively the maximum and minimum in all 500 measurements. can reflect a certain accuracy of UIPS.
We can see that error is less than mm with the reference distance for two methods. The highest and can obtain values of and 0.23, but they will increase with distance. This is because of the influence of noise when the ultrasonic signal becomes weakened, and the SNR is smaller. and in LSM are smaller than those in QS in all groups, so the method based on LSM has a higher accuracy and robustness.
The localization experiment for the mobile robot is performed in order to test the system function. Four anchor nodes are placed at a fixed position, which are configured as the receiving end, shown in Figure 12. Here, the coordinates of the anchor node are obtained from vicon as above. They are, respectively: , , , and . Each transducer of the anchor node has common coverage areas where the signal from the robot can be received by all. and can be calculated with Equations (23) and (25), given by
The motion with open-loop trajectory for the robot is a standard circle, which starts from different positions with various radii. There are also some optics markers around the ultrasound transducer of the node on the robot, so the trajectory can be obtained from vicon. The mobile robot will transmit the ultrasonic signal in each 200 ms cycle as with the distance measurement. The signal is transmitted with LOS in order to overcome the multi-path case, additionally, a short ultrasonic signal pulse, just 1 ms in this paper, can reduce interference for ultrasonic multi-path effect , so it is ignored here. The robot moves with a very low speed in the common coverage areas, so the Doppler effect of ultrasound is ignored in this experiment.
Four experiments are conducted with different radii in total, and the trajectory tracking results are shown in Figure 13.
We can see that the UIPS can follow the tracks of the robot with a maximum error of mm. The error is 12 mm when the same experiments are completed though quadrature demodulation  with the same sampling frequency . is used to represent the maximum error in this paper, and is defined as:
where is a position from UIPS, which deviates furthest from the vicon reference. is from vicon, because vicon is not in time synchronization with UIPS and has a much higher sampling frequency for positioning data than that of UIPS. is the nearest point to in all cases.
In this work, we present a new envelope detection method for the ultrasonic signal and develop an indoor position system based on this method, which can be also applied to other fields. Filter effect analysis from simulation proves that the method is effective. The system can fix a continuous position on the mobile robot with high and robust stability. We also present an improved time synchronization method based on RBS in the UIPS, which has an accuracy up to 1 s. Network nodes have individual communication modules using the WiFi protocol, which is used widely in day-to-day life. Therefore, we will integrate the ultrasonic transducer with a mobile phone in the future and realize the precise positioning for personnel using the phone and the UIPS.
This work is supported by the National Natural Science Foundation of China (Grant Nos. 61333003, 61690212).
Jun Qi and Guo-Ping Liu conceived and designed the experiments; Jun Qi performed the experiments and analyzed the data; Guo-Ping Liu provided experimental platform and funds; Jun Qi wrote the paper; Guo-Ping Liu provided guidance and polishing for the paper.
The authors declare no conflict of interest.