Accurate Ultrasound Indoor Localization Using Spring-Relaxation Technique

Abstract

This paper reports on the development of an ultrasonic sensing-based active localization system. The system employs an ultrasonic array to transmit chirp signals and time-of-flight measurement for ranging. The position of the receiver is estimated iteratively using the spring-relaxation technique. A median and 90-percentile error of 12.4 and 21.7 mm, respectively, were obtained for measurements at 625 positions within a 1.2 m × 1.2 m area testbed. The spring-relaxation technique outperforms the widely adopted linear least square-based lateration technique while using the same ranging data. The performance of the system is benchmarked against that of visible light positioning using the same platform setup. The reported results show the ultrasonic system to be more accurate when compared with the visible light positioning system, which achieved median and 90-percentile errors of 33.7 and 58.6 mm, respectively.

1. Introduction

Knowing where you are and your position in relation to the surroundings is called context-aware localization. One of the best-known context-aware localization methods used in the outdoor setting is the Global Positioning System (GPS). This satellite-based positioning has been popularly used for numerous applications. However, GPS cannot be reliably applied in an indoor environment due to the signal attenuation caused by the building of structural material. Consequently, other technologies have been researched for indoor localization systems. Indoor localization research is a growing field, as it has not reached the same level of scalability and adoption rate as that of GPS. The proliferation of modern smart phones, efficient and energy saving wireless sensor nodes, wearable devices and Internet of Things (IoT) technologies have all contributed to the rising popularity of this research area. While Light Detection and Ranging (LiDAR) [1] and computer vision-based [2] techniques have become popular, especially for mobile robotics, researchers are still exploring alternate solutions. They include WiFi [3], Radio Frequency Identification (RFID) [4], ZigBee [5], visible light [6], ultrasound [7] etc. Wireless-based techniques are considered to be less accurate compared to ultrasound and visible light-based methods.

Ultrasound indoor localization (UIL) systems that have been implemented in practice [8,9,10,11,12,13,14,15,16,17,18,19,20,21] show that the 95-percentile position accuracy can vary from about 30mm to 200 mm. The BAT system is an example of one of the more sophisticated solutions [22]. A review of the literature indicates that a trilateration/multilateration algorithm is the most commonly used positioning algorithm for ultrasonic localisation. Spring-relaxation (SR) is another technique that has been used for localization in the Wireless Sensor Network [23,24,25,26,27], similarly to Wifi, Zigbee, Bluetooth, and visible light positioning (VLP) [28]. However, we have not found any previous practical ultrasound localization studies that have used SR.

In this work, we implement an ultrasonic (US) localization system using spring-relaxation technique. The weightings are carefully formulated after observing that the ranging has better accuracy when transmitter (Tx) and receiver (Rx) distance is further apart. Thus, the larger the Tx-Rx separation, the more weight will be contributed to the net force of the springs. These results are benchmarked against that of a lateration algorithm. The performance of the UIL is also benchmarked against a Visible Light Positioning (VLP) system. VLP [29] has garnered the attention of the research community due to its synergy with the upcoming Visible Light Communication (VLC) [30]. VLP is considered to be extremely accurate with reported errors in the order of just a few cm. Spring-relaxation has been investigated for VLP, showing promising results [28]. Therefore, we decided to compare the two systems using the same testbed and algorithm.

The work offers the following contributions:

(1)

This is the first work to apply the spring-relaxation algorithm for ultrasound indoor localization (UIL) in a realistic sub-room scale environment. The weights, analogous to the Young’s modulus, of the springs are adjusted to mitigate the ranging error resulting from multipath interference. To the best of the authors’ knowledge, this novel concept of utilizing springs of varying stiffness to mitigate multipath interference has not been reported in the literature.

(2)

This work is also the first study to benchmark the accuracy of UIL against a Visible Light Positioning (VLP) system using the same platform setup. This is the first reported work that performs an “apple-to-apple” comparison of the two methods.

The rest of the paper is structured as follows. Section 2 gives a brief overview of localization using lateration and spring-relaxation techniques. Section 3 describes hardware and methodology used for ultrasonic localization. Section 4 reports on the performance of ultrasonic localization for spring-relaxation and lateration techniques. In Section 5, the ultrasonic localization results are benchmarked against VLP using identical positioning of anchor and target nodes. Section 6 gives conclusions and suggestions for the future work.

2. Localization Theory

Consider the ultrasonic localization setup shown in Figure 1. Here there are four fixed ultrasonic transmitters (anchor nodes), TX1–TX4, located on the ceiling of a room. Below these is an ultrasonic receiver (target node). To find the position of the receiver, ultrasonic time-of-flight (TOF) measurements can be made. This is the time it takes for the signal to propagate from a transmitter to the receiver. These can be converted into distances $D_i$ using the speed of sound in air. If the target height $h_i$ of the $i^{th}$ transmitter above the receiver is known, these propagation distances can be converted into horizontal ranging distances $r_i$ using Pythagoras theorem $r_i=\sqrt{D_i^2-h_i^2}$. These ranging distances can then be used for localization using algorithms such as lateration.

2.1. Lateration

Localisation can be performed using lateration by finding the intersection point of circles or spheres, which have radii equal to the ranging distances $r_i$, obtained using the ultrasonic time-of-flight (TOF) measurements. The algorithm requires a minimum of three range distances from the reference anchor nodes to the unknown target unit, to form the three equations. The intersection point, which can be derived using the linear least square (LLS) method, is taken to be the position of the target unit. On the other hand, the position accuracy can be affected if the intersection is not in the exact cross point of the three circles, but rather in the overlapping area as depicted in Figure 2. This can be caused by TOF measurement errors.

Linear least square (LLS) is the most common method of solving the lateration problem. With range estimates from $N$ transmitters located at ($x_1$, $y_1$)…($x_N$, $y_N$), the estimated location ($\widehat{x}$,$\widehat{y}$) of the target is given as [31]:

$$\left[\begin{array}{c}\widehat{x}\\ \widehat{y}\end{array}\right]={\left(A^{T}A\right)}^{-1}{A}^{T}b$$

(1)

where $\mathit{A}$ is an ($N$ − 1) × 2 matrix defined as:

$$\mathit{A}=\left[\begin{array}{cc}-2\left(x_2-x_1\right)& -2\left(y_2-y_1\right)\\ -2\left(x_3-x_1\right)& -2\left(y_3-y_1\right)\\ ⋮& ⋮\\ -2\left(x_N-x_1\right)& -2\left(y_N-y_1\right)\end{array}\right]$$

(2)

and $\mathit{b}$ is the ($N$ − 1) × 1 vector:

$$\mathit{b}=\left[\begin{array}{c}{r}_2^2-r_1^2-\left(x_2^2-x_1^2\right)-\left(y_2^2-y_1^2\right)\\ r_3^2-r_1^2-\left(x_3^2-x_1^2\right)-\left(y_3^2-y_1^2\right)\\ ⋮\\ r_N^2-r_1^2-\left(x_N^2-x_1^2\right)-\left(y_N^2-y_1^2\right)\end{array}\right]$$

(3)

and $r_i$ ($i$ = 1, 2 …, $N$) are the range estimates and $T$ represents the transpose operation.

2.2. Spring-Relaxation

The principle behind the SR technique is to estimate the position of a target unit using fictitious springs and Hooke’s law, as indicated in Figure 3. The location of the $i^{\mathrm{th}}$ anchor node can be expressed as a cartesian complex number:

$$X_i=x_i+j y_i,$$

(4)

where $i$ = 1 to 4 (TX1 to TX4 in this case) and the imaginary number, $j=\sqrt{-1}$, is used here to represent the y-axis direction. Each of these anchors is attached by a fictitious spring to a target (e.g., receiver) node, whose position we want to know.

The target is assumed to start at an initial guess position, which is not in an equilibrium state, with each of the springs being either stretched or compressed. The coordinates of the current estimated position of the target is given as:

$$X_{est}=x_{est}+j y_{est}$$

(5)

The current length of the $i^{th}$ spring is then:

$$l_i=|X_{est}-X_i|$$

(6)

The individual force exerted on the target by the i^th spring can be represented in polar format as:

$$F_i=\left| r_i-l_i\right| e^{j{\theta }_{li}}=\left| r_i-l_i\right| angle \left({\theta }_{li} \right),$$

(7)

where $r_i$ is the horizontal projection value from $D_i$, which is the range distance obtained from TOF measurement at that test location, and i = 1 to 4 (no. of springs). ${\theta }_{li}$ is the angular direction of the force F_i acting on the i^th spring with $\left| r_i-l_i\right|$ giving the magnitude of the said force. Equation (7) is essentially Hooke’s law with the spring constant being unity.

The net force exerted on the target will be:

$$\overrightarrow{F_{net}}={\displaystyle \sum }_{i=1}^4{F}_i$$

(8)

At each iteration of the SR algorithm, the target will be moved by a small step size from its current position towards the direction of the net force, $\overrightarrow{F_{net}}$. Hence the target’s new current estimate position is:

$$X_{est}^{m+1}=X_{est}^m+\Delta F_{net}^m,$$

(9)

where m is the iteration number and $\Delta$ is the applied step size. The SR algorithm will then update the $l_i$ (Equation (6)) based on the new current estimate coordinate and re-calculate the individual force and the total net force on the target. The algorithm keeps repeating the whole process and updates the location estimate as it goes along, and it will stop processing when the net force reaches a pre-defined threshold value $\sigma$ (10⁻⁴ in our algorithms) giving:

$$\overrightarrow{F_{net}^m}< \sigma$$

(10)

Now all the fictitious springs have reached their equilibrium state and this position is taken as the estimated location of the target.

3. Localization Hardware and Data Collection

3.1. Ultrasonic Hardware

A block diagram of the ultrasonic system used to measure ultrasonic time-of-flight, TOF, and, hence, distances is shown in Figure 4. An ultrasonic excitation signal was generated on a computer and then converted to an analogue signal utilizing one of the digital-to-analogue converter (DAC) channels of a Data Translation DT9832A https://www.mccdaq.com/Products/Multifunction-DAQ/DT9832 (accessed on 23 February 2021) module using the MATLAB Data Acquisition toolbox. A sampling rate of 500 kHz and a resolution of 16 bit were used. This analogue signal was then used to drive the ultrasonic transmitter.

The ultrasonic transmitter unit used in the localization system was composed of eight tightly packed MA40H1S-R https://www.murata.com/en-us/api/?cate=&partno=MA40H1S-R (accessed on February 23, 2021) air-coupled surface mount transducers. These transducers were wired in parallel on a PCB board (see Figure 5a). This array configuration was used, rather than a single transducer, to increase the transmitted sound intensity, and, hence, increase the maximum range where measurements could be made. The MA40H1S-R ultrasonic transducers were used because the authors had previously found that these transducers had lower ringing response when operated away from their resonant frequency of 40 kHz. Refer to [32] for more details. Ringing is the tendency of a transducer to oscillate at its resonance frequency during and after an excitation signal has been applied to the transducer. A low ringing response is a desirable property for a transducer if TOF distance measurements are made using coded waveforms and cross-correlation. This is because ringing causes the signal being transmitted by the transducer to be distorted, reducing the performance of the cross-correlation technique. (See next section for more details).

The ultrasonic excitation signal applied to the transducers was a linear chirp signal. This was chosen as the transducers were found to be able to reproduce this type of ultrasonic excitation signal with minimal distortion and ringing compared to other coded waveforms, such as barker codes, which have sharp temporal transitions. The chirp excitation signal is widely used in radar applications due to its good autocorrelation or pulse compression characteristics when used with cross-correlation [12,20,33]. It makes it easier to detect the signal and distinguish it from the noise, giving good signal-to-noise ratio (SNR) performance.

A linear chirp signal, which sweeps from a start frequency of frequency $f_0$ to an end frequency of $f_1$ in a time duration of $T$ can be defined as:

$$x\left[n\right]=\sin \left(2\pi \left[f_{0 }t+\frac{\mu t{\left[n\right]}^2}{2}\right] \right),0\le \mathrm{t}\le \mathrm{T},$$

(11)

where the chirp sweep rate $\mu =\frac{ \left(f_1-f_0\right)}{T}$ and $t\left[n\right]$ is the $n^{th}$ time interval. In this work, the chirp swept from 20 to 35 kHz in a duration of 1 ms (see Figure 6).

The transmitted ultrasonic signal was detected using a Panasonic WM-61A https://www.digikey.com/en/products/detail/panasonic-electronic-components/WM-61A/252843 (accessed on 23 February 2021) electronic microphone as a receiver (see Figure 5b). The low-noise microphone can operate at ultrasonic frequencies. A pre-amplifier circuit amplified and filtered the microphone signal, removing frequency components below 10 kHz. The resulting signal was then sampled with one of the analogue-to-digital converter (ADC) channels of the DT9832A module and saved to file. A sampling rate of 500 kHz and resolution of 16 bits were used. One of the digital outputs of the DT9832A board was connected to the hardware trigger of both the DAC and ADC systems, and the same internal clock was used for both. This ensured that both transmission and reception operations were synchronized allowing accurate time-of-flight (TOF) measurements to be made. The measured data were then saved to file for later processing.

3.2. Localization System Setup

The ultrasound indoor localization (UIL) prototype system consists of four of the ultrasound (US) transducers/transmitters described above mounted on the ceiling. The WM61a microphone receiver unit was mounted 1.6 m below to a computer numerical controlled (CNC) machine with a dimension of 1.2 m × 1.2 m. The CNC machine has an accuracy of 0.025 mm; orders of magnitude better than the expected localization accuracy of the UIL system. The receiver board, mounted onto the CNC machine, can be moved to various test locations with very high accuracy. This ensures that the ground truth is accurately recorded. Figure 7 illustrates the UIL system test rig set up that was used.

3.3. Data Collection

The four anchor transmitter stations TX1 to TX4, shown in Figure 7b, each sends out its ultrasound wave to the target object. The transmit and receive hardware is synchronized through the DT board, as described in Section 3.1. In real-world implementation, either an RF or infrared signal can be used to trigger the synchronization between the US emitter and receiver [34]. A time division multiple access (TDMA) [35,36] scheme can be deployed to multiplex the ultrasound emission between these anchor/emitter nodes. At any test point, there will be four different range distance values, e.g., D1, D2, D3 and D4 obtained at one location (see Figure 7a). Figure 8 shows how the CNC machine was used to obtain measurements with the target object (microphone in this case) at a range of positions in a grid pattern starting from coordinate (0 mm,0 mm) to the last coordinate (1200 mm, 1200 mm) with 50 mm step increments between measurement locations.

At each step, the TOF values from the four transmitters on the ceiling are then converted to ranges (D1–D4) to be stored in the database for usage in the localization algorithms later. The ambient temperature impacts the speed of sound in the air, ultimately affecting the range estimation. Therefore, the room temperature was recorded during the experiments. For a real-world system, a temperature sensor of high accuracy and low power consumption (e.g., TMP117, https://www.ti.com/product/TMP117 (accessed on 23 February 2021)) can be collocated with the receiver tag.

3.4. Processing for Estimating Time-Of-Flight, TOF

One method of measuring TOF in ultrasonic data is to use a threshold method. Here the TOF is determined to be the time when the signal first goes above a threshold voltage. However, a problem with this technique is that it can struggle to give accurate results as the signal-to-noise ratio (SNR) reduces.

Cross-correlation is an alternative method that is generally more robust in low SNR conditions. The cross-correlation function of transmit signal $x\left[n\right]$ with the received signal $y\left[n\right]$ can be defined mathematically as [37]:

$$R_{xy} \left[k\right]={{\displaystyle \sum }}_{n=0}^{N-1}x\left[n\right] y\left[n-k\right],$$

(12)

where $n$ is the sample index, $N$ is the total number of samples, and $k$ is the number of samples that the data shifted. This shift can be related to a time shift $\tau$ using $k=\tau F_s$, where $F_s$ is the sampling rate. The time shift when the cross correlation reaches its maximum value is taken as the estimate of the TOF. This technique works best where excitation waveforms are used for transmission that have good autocorrelation properties, such as chirps.

Figure 9 shows an example of a raw signal measured in a room and the cross-correlation of this signal with the transmit signal. Here we can see multiple peaks in the signal. The first peak is the direct path signal which is the one that is used for TOF measurements. The other peaks are due to multipath signals resulting from echoes from walls, the floor etc. A threshold method can be used to select the direct arrival signal for TOF measurement and ignore secondary peaks resulting from multipath echoes.

4. Ultrasonic Localization Results

The accuracy of a localization system is most commonly evaluated through measuring the localization uncertainty which is termed as localization error in the literature [29]. Localization error is defined as the Euclidean distance between the actual position of the target (the ground truth) and the estimated position of the target. The cumulative distribution function (CDF), mean, median and percentile values of the localization error are used in this paper to investigate the localization accuracy following the guidelines of [38,39]. The standard deviation of the localization error is also reported.

4.1. Spring-Relaxation Results

A value of 625 positions (see Figure 8) were tested. For our testbed, the larger ranging errors appear in the regions that are closer to the transmitters, as shown in Figure 10. This was believed to be due to echoes being picked up by the microphone when the receiver was located under one of the transmitters. These multipath components were not resolved, leading to error in TOF measurements.

This range-dependent error led us to modify Equation (7) to use weightings while calculating the forces acting on the springs giving:

$$F\left(i\right)=w\left(i\right) \left| r_i-l_i\right| angle \left({\theta }_{li}\right)$$

(13)

The weights are estimated as:

$$w\left(i\right)=\frac{r_i}{{{\displaystyle \sum }}_{i=1}^4{r}_i}$$

(14)

The weighting w(i) is analogous to the spring constant, with larger springs, representing larger Tx-Rx separation, considered stiffer. Thus, the larger the spring, the more the contribution it has to the net force, since the ranging is more accurate for larger Tx-Rx separations. While the concept of variable stiffness has been utilized to account for the measurement uncertainty in wireless sensor networks [40], it has not been applied for the mitigation of US ranging error.

As a result of applying variable spring stiffness (Equation (13)), the localization performance was seen to improve (see Figure 11). This figure is the cumulative distribution function, CDF. It shows the probability that an error of a particular size will occur. For example, we can see that with identical spring stiffness, 90 percent of the errors are less than 33.8 mm. The mean error reduced from 17.6 to 13.0 mm when using the weighting method.

Table 1. Localization accuracy of the proposed spring-relaxation algorithm.

With Identical Spring Stiffness (no Weighting)	With Variable Spring Stiffness (with Weighting)
Median = 15.2 mm Mean error = 17.6 mm 90-percentile = 33.8 mm Std-deviation = 12 mm	Median = 12.4 mm Mean error = 13.0 mm 90-percentile = 21.8 mm Std-deviation = 6.9 mm

summarizes the results of the SR algorithm for the two cases.

4.2. Benchmarking Spring-Relaxation (SR) with Linear Least Square (LLS)-Based Lateration

The ultrasound indoor localization (UIL) accuracy error obtained from both the methods of LLS lateration and SR are shown in Figure 12 and

Table 2. Localization accuracy error of the spring-relaxation algorithm compared to LLS lateration.

Lateration	Spring-Relaxation
Median = 14.5 mm	Median = 12.4 mm
Mean error = 13.8 mm	Mean error = 13.1 mm
90-percentile = 25.9 mm	90-percentile = 21.8 mm
Std-deviation = 8.0 mm	Std-deviation = 6.9 mm

. As can be observed, the SR algorithm outperforms the lateration in terms of accuracy, with lower error.

5. Benchmarking with Visible Light Positioning (VLP)

VLP systems have been shown to be accurate in the order of several cm [6]. VLP is a positioning technique that makes use of the visible light emitted from sets of LED luminaires to localize a photosensor-equipped target object in an indoor setting environment (see Figure 13). Received signal strength (RSS) at the photosensor is the most common way to find the range of the target from the corresponding luminaire [29].

5.1. VLP System Hardware

The VLP system used the exact platform set up as our UIL system. Four LED luminaires were placed in the same positions that were previously occupied by the US transmitters. Each luminaire, utilizing a bespoke driver, transmits unmodulated sine waves [41]. For the experiments conducted, the luminaires are set to unique frequencies of 2.5, 2.7, 3.2 and 3.5 kHz, respectively, allowing for frequency-division multiplexing (FDM) of the transmitted signals.

The receiver board is equipped with a photodiode (PD) followed by a transimpedance amplifier that feeds an ESP 8266 microcontroller to perform analog-to-digital conversion [41]. Fast Fourier transform (FFT) on the digital data performs the demultiplexing and the magnitude of the FFT at the appropriate frequency (e.g., 2.5 kHz). This provides the RSS for the corresponding luminaire.

5.2. Range Estimation for VLP

If the receiver plane is kept horizontal with the transmitter plain, the simplified Lambertian propagation model gives the received power $P_{r_i}$ at a distance $d_i$ from the $i^{th}$ luminaire as [6]:

$$P_{r_i}=P_{r_{i,0}}{\left(\frac{d_{i,0}}{d_i}\right)}^{m_i},$$

(15)

where m_i is the Lambertian order and $P_{r_{i,0}}$ is the received power at a distance $d_{i,0}$ (refer to Figure 14).

The received signal at the receiver at location ($x,y$) can be expressed as:

$$s\left(t\right)={\displaystyle \sum }_{i=1}^4{G}_i\sin \left(2\pi f_{i}t+{\theta }_i\right),$$

(16)

where $f_i$ and ${\theta }_i$ are, respectively, the frequency and phase of the sinewave of the $i^{\mathrm{th}}$ luminaire at location ($x,y$), and $G_i$ is essentially a function of the distance $d_i$ between the photodiode at location ($x,y$) and the $i^{\mathrm{th}}$ luminaire.

The spectrum $\mathrm{S}\left(\omega \right)$ of the signal at angular frequencies $\omega$ can be computed using the fast Fourier transform (FFT). The power spectrum can then be calculated using:

$${\widehat{\mathrm{P}}}_{ss}\left(\omega \right)=\frac{1}{N}{\left|\mathrm{S}\left(\omega \right)\right|}^2.$$

(17)

The power spectra, ${\widehat{\mathrm{P}}}_{ss}\left(\omega \right)$, at the known modulation frequencies (2.5, 2.7, 3.2 and 3.5 kHz) are used to estimate the received power $P_{r,i}$ for each luminaire. Lambertian orders $m_i$, $P_{r_{i,0}}$ and $d_{i,0}$ are estimated by following the calibration process outlined in [6]. This involves taking offline measurements at 17 points. Refer to Figure 15 for the location of the calibration measurement points.

Once $d_i$ is found from for all four luminaires, the spring-relaxation algorithm outlined in Section 4.2 was used to find the location of the target. Here, the target object, with the photodiode sensor, is taking the place of microphone receiver unit. The localization accuracy of the VLP is shown in

Table 3. Localization accuracy of the UIL compared to VLP.

UIL	VLP (mm)
Median = 12.4 mm	Median = 33.7 mm
Mean error = 13.0 mm	Mean error = 36.5 mm
90-percentile = 21. 8 mm	90-percentile = 58.6 mm
Std-deviation = 6.9 mm	Std-deviation = 17.3 mm

. and in the CDF plot shown in Figure 16. As can be seen, the UIL system is far more accurate than the VLP system.

One advantage of UIL compared with VLP for localizing an object in an indoor environment is its relatively easy and straight-forward hardware set up. Visible light positioning (VLP) requires extra care to make sure that the transmitters placed on the ceiling are parallel to the photoreceiver below. Parameter calibration [6] is also essential in VLP in order to achieve the best fit RSS-distance attenuation model for accurate range distance calculation. Furthermore, the luminaires degrade over time and there may be changes in the room (e.g., moved furniture). Additional calibration will be required to account for these changes.

6. Conclusions

The SR algorithm was successfully implemented for an UIL system to achieve accurate positioning. For the experimental set up utilized, SR outperforms the well-known LLS-based lateration technique. Therefore, the SR algorithm should be further explored. The convergence and the stability of the SR algorithm has been left for future studies. To improve the power output, and, hence, the operational range, an array of eight air-coupled ultrasonic transducers were used. These transducers were specifically chosen due to their low ringing transient response. This means that the high accuracy TOF measurements were able to be obtained using cross-correlation with chirp excitation waveform. More work is needed to develop wireless synchronization for accurate TOF measurements.

Furthermore, the UIL system was found to be more accurate than a VLP system. Unlike the VLP system, the UIL system does not require parameter calibration, as it only needs the ambient temperature, making it easier to deploy in a changing environment. It should be noted that VLP has the advantage of being able to potentially leverage the existing lighting systems if the luminaires are enabled with VLC technology. In such a scenario, the ultrasonic technique can be fused with the VLP system to extend coverage, eliminate blind spot, provide fault tolerance and enhance robustness.

The localization techniques explored here, for both UIL and VLP, are memoryless; they do not take the position estimate of the previous state into account to compute the current position. Future work can explore the utilization of continuous tracking using Kalman [42] or particle filters [43].