A 3D Source Fingerprinting-Based Localization System

Show more

1. Introduction

Early, localization was restricted to military applications and aimed particularly to estimate the enemy position. The Global Positioning System (GPS) was only used by the US Army. Nowadays, localization services are accessible to civilian users and the GPS becomes the most popular localization systems thanks to its coverage and its performance. However, it fails indoors due to the lack of the line of sight and the presence of multipaths that characterize the indoor environments.

Several indoor localization systems have been proposed. Most of them are based on trilateration and fingerprinting technique. The first is based on distance measurements and requires visibility between emitter and receiver. The second is more adapted to indoor environments. It comprises two phases: offline and online phases. In the offline phase, a set of positions are selected in the area of interest and a position-dependent signal parameter is extracted at each position to define the fingerprint. The positions and the relative fingerprints are stored in a database. In the online phase, the target fingerprint is first determined then compared to the built database to estimate the position.

In [1], authors have proposed a mobile phone based system that defines the fingerprint as a combination of ambient sound, color, light and acceleration. Experimental results from 51 stores show that the system reaches an average accuracy of 87%. In [2], a system that is based on ambient sound, called the acoustic background spectrum, is described. It estimates the mobile device position with room level using the nearest-neighbor classification. The system achieves an accuracy of 30%. Combined with a wifi-based localization method, the accuracy can attain 69%. An active sound fingerprint-based system was proposed in [3]. It defines the impulse response as a fingerprint and employs a support vector machine classifier to estimate room locations and within-room positions. Results show that a room-level accuracy of 85.1% and a within-room-position accuracy of 51.3% can be achieved.

In this paper, we enrich the system presented in [4]. The latter is a source localization system that uses the time of arrival of the path of maximum amplitude as a fingerprint and employs a probabilistic method to estimate a within-room position. The system is tested under different conditions. Turbulence is considered in order to model an air conditioning or an open window in an indoor area, a scenario that may happen indoors and that has not been taken into account in almost all the existing localization systems.

The rest of paper is organized as follows: Section 2 describes the proposed system. Section 3 reports the experimental results. Conclusions are presented in Section 4.

2. Localization System

We propose a 3D source localization system that is based on the fingerprinting technique and that employs four receivers placed at known positions.

Several parameters can be extracted from the signal in order to estimate the target position. Among them, the time of arrival (TOA) of the received signal gives information on the unknown position of the emitter or the receiver. However, in reverberant environment, multipaths and noise affect the estimation of the TOA. Hence, deducing the distance directly from the TOA induces errors in the position computation [4]. Some works [5] were based on empirical studies in order to select the best estimation of the TOA. However, the determination of the best parameters requires time. In addition, the chosen values depend on the test bed and on the environment. In our paper, we resort to adapting the TOA as a fingerprint as the fingerprinting technique takes into account the multipath.

The localization scenario can be presented as follows: In the off-line phase, the target environment is meshed regularly in x, y and z. At each position, we correlate the received signals with the source code to determine the instant of the maximum correlation peak. The latter gives an estimation of the TOA. The TOA values relative to each receiver define the source fingerprint. The set of positions c_{l}_{ (1≤l≤L)} and corresponding fingerprints s_{l}_{(}_{1≤l≤L)} are stored in a database. In the online phase, the fingerprint s of a source placed at unknown position c is first computed. Then, its position is estimated when comparing its fingerprint with the previously built database.

An estimate of the position is given as:

$\stackrel{^}{c}=E\left(c|s\right)={\displaystyle {\sum}_{i=1}^{L}{c}_{i}\times P({c}_{i}|s)}$ (1)

where P(c_{i}|s) is the conditional probability of c_{i} given the target signature s. Equation (1) can be rewritten, using Bayes’ formula, as:

$\begin{array}{l}=E\left(c|s\right)=\underset{i=1}{\overset{L}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{c}_{i}\times P\left({c}_{i},s\right)/\underset{i=1}{\overset{L}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}P\left({c}_{i},s\right)\\ =\underset{i=1}{\overset{L}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{c}_{i}\times P\left(s|{c}_{i}\right)\times P\left({c}_{i}\right)/(\underset{i=1}{\overset{L}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}P\left(s|{c}_{i}\right)\times P\left({c}_{i}\right))\end{array}$ (2)

P(s|c_{i}), P(c_{i}) denote the position conditional probability of s and a priori probability of the position c_{i}, respectively. P(c_{i}, s) is the joint probability.

Consequently, to estimate the position c, we need to estimate these probabilities.

Since the form of the joint probability density function are unknown and hardly parametrized, we opt to nonparametric approaches, particularly to the local polynomial regression. Using Taylor’s expansion, the expectation E(c|s) denoted with m(s) is given as:

$m\left({s}_{0}\right)=m\left(s\right)+{m}^{1}\left(s\right)\times \left({s}_{0}-s\right)+\cdots +{m}^{p}\left(s\right){\left({s}_{0}-s\right)}^{p}\times (1/p!)$ (3)

s_{0} denotes the signature of a neighborhood of the target position with signature s.

Considering the position and the corresponding fingerprints stored in the database, the target position can be computed through the weighted least squares when solving the following minimization problem, for p = 1:

${\mathrm{min}}_{\beta}{{\displaystyle \sum}}_{i=1}^{L}\text{\hspace{0.05em}}{({c}_{i}-{{\displaystyle \sum}}_{j=1}^{P}\text{\hspace{0.05em}}{\beta}_{j}\times {(s-{s}_{i})}^{j})}^{2}\times {K}_{H}(s-{s}_{i})$ (4)

H and K are the bandwidth matrix that controls the size of the target neighborhood and the multivariate kernel function, respectively. K_{H}(.) controls the weights and it is given as:

${K}_{H}(.)=K({H}^{-1}(.))/\mathrm{det}(\; H\; )$

The weighted least squares solution to this problem is expressed as [6]:

$\stackrel{\u02dc}{\beta}={({S}^{t}WS)}^{-1}({S}^{t}WC)$ (5)

where

$S=\begin{array}{ccc}1& {({s}_{1}-s)}^{1}& \cdots \\ \vdots & \vdots & \vdots \\ 1& {({s}_{L}-s)}^{1}& \cdots \end{array}\begin{array}{c}{({s}_{1}-s)}^{p}\\ \vdots \\ {({s}_{L}-s)}^{p}\end{array}$ (6)

$C=\begin{array}{c}{c}_{1}\\ \vdots \\ {c}_{L}\end{array}$ (7)

The target position estimator $\stackrel{^}{c}$ is the first component of the vector $\stackrel{\u02dc}{\beta}$ .

As regards the estimator parameters, we have adopted the one of the most popular kernel function that is the Gaussian function defined as:

$K\left(y\right)=\frac{1}{{\left(2\pi \right)}^{\frac{d}{2}}}\times \mathrm{exp}\left(-\frac{1}{2}\times {u}^{T}\times u\right)$ (8)

For the bandwidth selection, we opt to the generalization of Scott’s rule [7] given by:

$H={L}^{-1/(d+4)}\times {\sigma}^{1/2}$ (9)

where L is number of the stored fingerprint vectors, d is the dimension of each fingerprint vector and
$\sigma $ is the covariance matrix of the fingerprint vectors s_{1}, s_{2}, ∙∙∙, s_{L}.

3. Evaluation of System Performance

System performance was evaluated by experiments in ambient and turbulent environments. Performance is given in terms of accuracy and precision. Accuracy is the Euclidean distance between the true position and the estimated position. Precision is the percentage of measurements having errors equal to or less than the accuracy.

3.1. Measurements

Experiments were performed in 1.5 m × 1.5 m × 2 m area within a Hall of laboratory work at the national school of Engineers of Le Mans, containing desk, chair, ∙∙∙ and different materials.

To build the database, the area was meshed in x, y, and z with interposition distance equal to 0.3 m. In particular, three values in z direction from 0.8 m to 1.4 m were considered, assuming that the target height is in this range.

To assess the system performance, 29 test positions were selected and more than seven measurements were performed at each position.

As regards the signal parameters, they were set to:

・ 3000 Hz for the chip and the carrier frequencies

・ 127 chip for the Gold code length

These values were empirically selected so that we obtain a good compromise between precision and computational time.

The sampling frequency was set to 51,200 Hz, the maximum value allowed by the signal acquisition module, in order to obtain a good resolution in TOA.

3.2. Material

The hardware system is composed of a signal acquisition module, one speaker, four microphones, one amplifier and a personal computer (PC).

The signal acquisition module includes two modules: the NI9234 and NI9263. The NI9234 module has four analog input channels, where each input is equipped by a delta-sigma analog-to-digital converter with resolution of 24 bits. The maximum data rate range is 51.2 Kech/s. The NI9263 module has four analog output channels, each having a string digital-to-analog converter with resolution of 16 bits. For our experiments, we have used one uniform output channel and four uniform input channels.

The microphone deployed in these experiments has a dynamic range of up to 122 dB. Its sensitivity is almost 10 mV/Pa. The bandwidth of amplifiers is between 20 Hz and 20 kHz.

Lab VIEW is used to assure the data acquisition between the personal computer and the signal acquisition module. MATLAB is employed for the signal processing.

3.3. Performance

Four microphones, fixed to known positions, are used to estimate the speaker position. Each of the four received signals is correlated with the source code to determine the speaker signature. Then, based on the built database, the position is computed using the local linear estimator.

Performance assessed in ambient environment show that the system provides the location with an accuracy of 5 cm within 75.86% precision (Figure 1).

In order to give a complete evaluation of the system, we have tested its performance under turbulent environment assured via the use of an artificial fan. Such scenario, ignored in almost previously proposed systems, can describe the effect of an open door or window in an indoor environment. Moreover, the noise generated by the fan can also describe a source of noise that may be present in an indoor area.

Figure 1. The performance of the source location system.

Results reported in Figure 1 and compared to that obtained in ambient environment show that the system provides the location with accuracy of less than 5 cm and in 35.9% of cases. An accuracy of 8.5 cm is achieved with 96.5 % and 89.6% precision in ambient and turbulent environments, respectively. The air disturbance has then degraded the measurement of the TOA, which varies when the propagation medium, that is air, moves. Although this degradation, the system still present good performance.

4. Conclusions

In this paper, we presented a 3D acoustic localization system that aims to locate a source. The system is based on fingerprinting technique and uses the nonparametric regression. The effect of noise and turbulence that are currently present in indoor environment has been investigated. Experimental results show degradation in precision by 7% for an accuracy of 8.5 cm.

In future work, we aim to extend our system to the case of several sources. We will identify each source with a Gold code then, we will study the system performance when varying the number of the localized sources.

References

[1] Azizyan, M., Constandache, I. and Choudhury, R.R. (2009) Surround Sense: Mobile phone Localization via Ambience Fingerprinting. Proc. 15th Annu. Int. Conf. MobiCom, Beijing, 261-272. https://doi.org/10.1145/1614320.1614350

[2] Tarzia, S.P., Dinda, P.A., Dick, R.P. and Memik, G. (2011) Indoor Localization without Infrastructure using the Acoustic Background Spectrum. Proceedings of the 9th International Conference on Mobile Systems Applications and Services, 28 June-1 July 2011, Bethesda, ACM, New York.
https://doi.org/10.1145/1999995.2000011

[3] Rossi, M., Seiter, J. and Amft, O. (2013) RoomSense: An Indoor Positioning System for Smartphones Using Active Sound Probing. 4th Augmented Human International Conference (AH’13), 7-8 March 2013.
https://doi.org/10.1145/2459236.2459252

[4] Aloui, N., Raoof, K., Bouallegue, A., Letourneur, S. and Zaibi, S. (2014) Performance Evaluation of an Acoustic Indoor Localization System Based on a Fingerprinting Technique. EURASIP J. Adv. Signal Process, 2014, 13.
https://doi.org/10.1186/1687-6180-2014-13

[5] Choi, J., Kim, J. and Kim, N.S. (2016) Robust Time Delay Estimation for Acoustic Indoor Localization in Reverberant Environments. IEEE Signal Processing Letters, 24.

[6] Fan, J. and Gijbels, I. (1996) Local Polynomial Modelling and Its Applications. Chapman & Hall.

[7] Hardle, W., Muller, M., Sperlich, S. and Werwatz, A. (2004) Nonparametric and Semiparametric Models. In: Springer Series in Statistics, Springer, Heidelberg.
https://doi.org/10.1007/978-3-642-17146-8