Open AccessArticle

Acoustic Sensor Network for Relative Positioning of Nodes

Carlos De Marziani

^1,2,*,

Jesus Ureña

^1,*,

Álvaro Hernandez

¹,

Manuel Mazo

¹,

Juan Jesús García

¹,

Ana Jimenez

¹,

M. Carmen Pérez Rubio

¹,

Fernando Álvarez

³ and

José Manuel Villadangos

Electronics Department, University of Alcalá, Campus Universitario s/n, 28805, Alcalá de Henares, Madrid, Spain

Electronics Department, National University of Patagonia San Juan Bosco, Facultad de Ingeniería, Ciudad Universitaria, Ruta Prov. Nº 1, Km. 4, 9005 Comodoro Rivadavia, Chubut, Argentina

Electrical Eng., Electronics and Automatics Department, University of Extremadura, Extremadura, 06071 Badajoz, Spain

Authors to whom correspondence should be addressed.

Sensors 2009, 9(11), 8490-8507; https://doi.org/10.3390/s91108490

Submission received: 17 August 2009 / Revised: 21 September 2009 / Accepted: 15 October 2009 / Published: 27 October 2009

(This article belongs to the Special Issue State-of-the-Art Sensors Technology in Spain)

Download

Browse Figures

General scheme of the proposed sensor network. ">
Detailed block diagram of node hardware architecture. ">
Principle of measurement using simultaneous Round-Trip-Time-of-Flight. (a) Emission of the request from the Master (starting the positioning process). (b) Acknowledgement from every node in order to compute distances. ">
Positioning Algorithm Scheme. ">
Position estimation for a distribution of nodes with a Gaussian noise in the pTOF measurements. (a) 95% uncertainty ellipses considering an error with standard deviation Σ = 100μs. (b) Total variance in the position estimation. (c) Total bias in the position estimation. ">
Cumulative distribution function in the position estimation of node N4 depending on the total number of nodes (8, 12 and 16), and for a Gaussian error in the pTOF measurements of Σ = 10 μs. ">
Position estimation with errors in tp characterization. (a) Total variance in the coordinate estimation of eight nodes. (b) CDF in the position estimation of node N4. ">
Position estimation when changing the topology of nodes. ">
Errors in the position estimation considering NLOS effect between nodes N1 and N14 (see the node distribution in <a href="#f5-sensors-09-08490" class="html-fig">Figure 5</a>). (a) Total variance in the coordinate estimation. (b) Total bias in the coordinate estimation. ">

Versions Notes

Abstract

In this work, an acoustic sensor network for a relative localization system is analyzed by reporting the accuracy achieved in the position estimation. The proposed system has been designed for those applications where objects are not restricted to a particular environment and thus one cannot depend on any external infrastructure to compute their positions. The objects are capable of computing spatial relations among themselves using only acoustic emissions as a ranging mechanism. The object positions are computed by a multidimensional scaling (MDS) technique and, afterwards, a least-square algorithm, based on the Levenberg-Marquardt algorithm (LMA), is applied to refine results. Regarding the position estimation, all the parameters involved in the computation of the temporary relations with the proposed ranging mechanism have been considered. The obtained results show that a fine-grained localization can be achieved considering a Gaussian distribution error in the proposed ranging mechanism. Furthermore, since acoustic sensors require a line-of-sight to properly work, the system has been tested by modeling the lost of this line-of-sight as a non-Gaussian error. A suitable position estimation has been achieved even if it is considered a bias of up to 25 of the line-of-sight measurements among a set of nodes.

Keywords:

sensor networks; relative localization; remote sensing

1. Introduction

The computation of relative positions among mobile computing devices [1] or members of a robot team [2] can provide enhanced support for multi-user interactions, when systems are not restricted to a particular environment and they cannot depend on any external infrastructure to compute their location, as is common in Local Positioning Systems (LPS) [3]. In these cases, it is necessary to design a sensor network capable of obtaining the distances among sensors in the shortest time and in a cooperative way. These kinds of systems are usually called Relative Localization Systems [4,5]; and the estimation of their coordinates is more difficult than in LPS, since positions are computed by measurements among objects whose locations are not known a priori in the environment.

Several positioning algorithms can be used to determine the relative position of objects, depending on different parameters: the accuracy required for the estimation, the number of observations available at each node and the computational load. In indoor spaces, multilateration techniques are often developed by solving a set of equations that consider all the measurements carried out among nodes. One of the most common algorithms in relative positioning systems is the classic or metric Multidimensional Scaling (MDS) technique [6]. This algorithm allows a geometric configuration of the considered objects with the smallest number of dimensions, by using only the distances measured among them. Nevertheless, data collected by the ranging mechanism are often influenced or corrupted by different parameters (environmental noise, signal delays associated to transducer responses, latency of signal processing algorithms, etc), which lead to errors in the estimation of coordinates. In order to reduce the error in the position estimation with the MDS algorithm, least-square minimization methods can be applied [7-9] using the geometric configuration provided by the MDS technique as starting point, and considering the different parameters associated to the ranging mechanism.

Many relative localization systems use data collected from a ranging mechanism, based on acoustic sensors, by measuring the times-of-flight (TOF) or difference-times-of-flight (DTOF) [8,9] in order to compute the coordinates. This often implies some additional links, e.g., infrared (IR) or radio frequency (RF), or accurate clock signals to measure the propagation time of the emitted signals, but increasing the complexity of the sensor nodes. In order to reduce the complexity of the sensor network, a low-complex ranging method, called Simultaneous Round-Trip-Time-of-Flight (S-RTOF), has been proposed by the authors [10]. This makes possible to determine temporary relations among the emissions carried out from every node using only acoustic signals. Additionally, because of the features of the ranging mechanism, a set of redundant observation data is obtained. This information can be useful to mitigate the non-line-of-sight effect (NLOS) that can appear when acoustic signals are used in indoor spaces. In this way, using high-level algorithms, such as geometry consistency check or statistical analysis [11,12], the estimator performance can be improved by identifying and rejecting those measurements with low accuracy.

In this work, the accuracy achieved in the position estimation by the proposed acoustic sensor network is analyzed. Object positions are computed by MDS algorithm, starting from the distance measurements. Finally, after considering the different possible errors and time delays involved in the computation of temporary relations, refined positions are computed by applying the Levenberg-Marquardt algorithm (LMA) to the non-linear equations which describe the temporary relations among emissions provided by the S-RTOF.

The rest of the paper is organized as follows: Section 2 shows the proposed acoustic sensor network architecture. Also, in Section 2, the used encoding scheme and S-RTOF mechanism are described, considering the different parameters involved in the measurement process. Section 3 explains the used positioning algorithms (MDS and LMA). In Section 4 Monte-Carlo simulations are done to determine the accuracy that can be obtained in the position estimation. Finally, some conclusions are discussed in Section 5.

2. System Architecture

The system architecture is depicted in Figure 1. It consists of an acoustic sensor network, where every object N_q (q ∈ {1, 2,⋯,Q} and Q is the number of nodes in the system) carries a sensor node with a speaker, a microphone and the associated hardware. Acoustic sensing technologies are used since they are suitable for fine-grained location and widely spread due to their low cost, easy implementation and availability in assorted mobile systems.

The computation of the distances d_ql (q,l ∈ {1,2,⋯,Q},q ≠l) between objects is carried out by measuring the propagation time of the acoustic signals emitted by every node, without any additional link to synchronize them. In order to simultaneously detect these acoustic emissions, a Code Division Multiple Access (CDMA) scheme has been used [13] by encoding the emissions with Complementary Sets of Sequences (CSS). A ranging mechanism has been developed based on the simultaneous Round-Trip-Time-of-Flight (RTOF) measurements from acoustic signals emitted by all the nodes. Since data are collected by all the nodes in a cooperative way, it is necessary to share the information obtained by every node in order to generate a map with all the object positions. In this case, data are distributed by means of low-cost RF communication modules [14], which are not synchronized with the acoustic ranging mechanism. It is not necessary any special requirement to collect and distribute the system information, so the proposed architecture can be implemented in general-purpose sensor or mobile computing systems. According to these features, every node can locally compute the object positions, providing a non-centralized architecture.

2.1. Encoding Scheme to Multi-User Detection

A remarkable capability for relative positioning is the measurement in a short time of all the spatial relations among objects, by using a common temporary reference. In order to measure the spatial relations among objects in the shortest time, it is necessary to use multi-user schemes that allow to simultaneously discriminate the emissions from every user or sensor.

In most cases, Direct-Sequence Code-Division Multiple-Access (DS-CDMA) techniques are used to discriminate the node emissions, by encoding every emitter with binary sequences and transmitting it by a simple phase modulation. These encoded signals are detected in a receptor by performing the correlation with every available sequence in the proposed system. Thus, the effectiveness depends on the properties of the used codes [13], requiring ideal properties of auto-correlation (AC) with high main-lobes for null time shifts, and side-lobes in the AC function closer to zero for all non-zero time shifts. Also, it requires that the values of the cross-correlation (CC) function among the different codes be as small as possible.

In the proposed system, an encoding scheme based on Complementary Set of M Sequences (M-CSS) has been used, where the number of sequences M is a power of two [15]. The features of this encoding technique allow to obtain M sets with ideal null cross-correlation, when the addition of the cross-correlation functions (ΣCC) between the corresponding sequences of two different sets is computed. Furthermore, the addition of the auto-correlation functions (ΣAC) from every sequence that composes the set provides null side-lobes. The described properties make attractive their use in sensory systems with simultaneous detection, since several emissions can be discriminated from different independent sources with low signal-to-noise ratios (SNR).

As opposed to the common encoding schemes used in localization, the encoding of emissions by M-CSS assigns more than one sequence to each user. In this way, the required hardware resources are increased, reason why efficient algorithms have been developed in order to minimize these requirements [16]. Furthermore, it is necessary to analyze the most efficient and effective technique to transmit in a short time the sequence of bits used to encode every user. One simple method consists of establishing an emission order of the M-CSS bits and transmitting them by a Binary Phase Shift Keying modulation (BPSK). An exhaustive analysis of this method has been made in [17], as well as some methods to reduce the worsening in the correlation properties provided by the proposed emission mechanism for simultaneous detection in a certain receptor.

According to these signal processing techniques, the emitting stage implemented at the node hardware architecture is shown in Figure 2. This block is divided into the code generation stage for the M-CSS and the arranging bit stage. After that, the obtained encoding is transmitted by BPSK, which allows the emission to be adapted to the transducer bandwidth. Furthermore, a control emission block is implemented to fire the acoustic signal emission, managed by the processing unit. On the receiving module, the demodulation of the signal captured by the microphone is computed after adjusting and digitalizing it. Then, the signal is processed to determine the arrival time of every encoded acoustic emission. For that, a set of correlators has been implemented, according to the algorithms developed in [16] and [17], to detect the emissions carried out by, at most,Q nodes. With the results obtained at the correlator outputs, a peak detector algorithm has been applied in order to determine the arrival instant. Although Q nodes can be simultaneously detected in each common perception area, the Q codes can be replicated in nodes located in other different areas. Practical values of Q can reach, for example, 64 nodes depending on the time required between successive position computations.

Finally, a processing unit has been implemented at each node, which controls the emitting stage according to the results obtained at the correlator outputs. It also computes the temporary relations among the emissions carried out by every node. Moreover, this unit performs the distribution of the data collected by every node by means of a communication block, and it computes the position among the objects.

2.2. Principle of Measurements

Since all nodes are equal in their architecture and functionality, anyone of them can start the ranging process (it is called Master node). In this work, the Master node has been previously assigned (i.e., node q = 1) for a concise explanation of the measurement algorithm. Nevertheless, a multiple access technique as Carrier Sense Multiple Access (CSMA) can be used to automatically assign the master node.

It is assumed that node q = 1 is the Master and has the following coordinates (x_M, y_M, z_M), described by a vector p_M. On the other hand, the positions of two slave nodes q and l are given by vectors p_q and p_l. At a given instant, the Master node emits its encoded acoustic signal (see Figure 3a) starting the RTOF measurement. This emission, called Master Request, is detected by every slave node with their microphones Mic. q and Mic. l at different instants according to their distribution in the environment.

In response to the Master Request, every slave node emits its own code, denoted as Ack. Node, which travels towards the Master node and also to the other slave nodes (see Figure 3b). In this way, in the Master node, the temporary interval from the Master Request emission until the detection of every Ack. Node can be computed. Also, taking advantage of the encoded emissions, it is possible to compute temporary relations in each slave node, from its own Master Request detection until the detection of the Ack. Node emissions from other slaves.

2.3. Pseudo-Time-of-Flight Equations

According to the described principle of measurement, it is possible to determine temporary relations among the emissions carried out from the different nodes, by measuring the differences between the correlation maximum values detected at every node. These values do not exactly describe the propagation time of the acoustic emissions, since there is an offset caused by the rising time of the emitted signal, the latency of signal processing algorithms, and the response time of the transducers [9]. Therefore, it is necessary to consider a delay until the signal is encoded and emitted by the speaker, denoted as t_Spk. Also, in the reception stage, a delay t_Mic appears from the capture of the signal by the microphone until obtaining the correlation maximum values. Assuming that the moving velocities of nodes are much smaller than the propagation speed of acoustic waves, it is possible to obtain (1), which summarizes the temporary relations measured in the Master node for every slave node:

{\hat{t}}_{M - q} = 2 \cdot \frac{‖ p_{M} - p_{q} ‖}{c} + t p_{M} + t p_{q} + T_{CODE}

(1)

where t̂_M₋_q is the time computed between the Master (q = 1) and the slave node q with q ∈ {2,⋯,Q};c represents the propagation speed of sounds;T_CODE is the temporary length of the emitted encoded signal; ‖ ‖ is the Euclidean norm between the considered position vectors (p_M for the Master and p_q for the slave); and tp =t_Spk +t_Mic represents the aforementioned time delays (tp_M and tp_q for the Master and slave node q respectively). According to these features, the measurements have been called pseudo-times-of-flight (pTOF) [18], since they are not a direct time-of-flight measurement of the acoustic emissions.

On the other hand, in the case of the pTOFs measured between slave nodes, e.g., node q and node l, in the slave node q after the detection of the Master Request it is possible to measure the following pTOF after receiving the Ack. Node l:

{\hat{t}}_{q - l} = \frac{‖ p_{M} - p_{l} ‖}{c} + \frac{‖ p_{l} - p_{q} ‖}{c} - \frac{‖ p_{M} - p_{q} ‖}{c} + t p_{l} + T_{CODE}

(2)

where t̂_q₋_l is the pTOF measured in the slave node q regarding the slave node l.

In (1), the computed pTOF depends on the distance between the Master and every slave node involved (‖p_M-p_l‖ and ‖p_M-p_q‖), and on the distance between the slave nodes (‖p_l-p_q‖). In this case, the temporary relation obtained in (2) only depends on the time delays of a slave node (tp_l).

3. Positioning Algorithm

According to (1) and (2), to determine the node positions, it is necessary to solve a non-linear equation system. The parameters to be estimated are described in (3), i.e., the coordinates of every node as well as the time delays associated to the signal processing algorithms in the emission and reception stages:

\begin{array}{l} ρ = [p tp] = [p_{M} p_{2} \dots p_{q} \dots p_{Q} t p_{M} \dots t p_{Q}] \\ ρ = [x_{1} y_{1} z_{1} x_{2} y_{2} z_{2} \dots x_{Q} y_{Q} z_{Q} \dots t p_{M} t p_{2} \dots t p_{Q}] \end{array}

(3)

where ρ is the parameter vector to be estimated; p_q are the coordinate positions (x_q,y_q,z_q) for the node q and the vector tp represents the delay times associated to every node in the system, as described before.

The diagram of the algorithms used to compute the relative positions among nodes is shown in Figure 4. After applying the S-RTOF ranging method and assuming that the nodes have communicated the pTOFs computed by each one of them, the position can be obtained. The MDS algorithm provides a first approximation using the distances calculated with the pTOFs. Then, the results can be improved by using the Levenberg-Marquardt Algorithm (LMA), considering the MDS positions and the characterization of the time delays, performed by auto-calibration [19] or by off-line characterization, as initial point for LMA.

3.1. MDS Position Estimation

The MDS algorithm allows a geometric configuration of the object positions to be achieved in the smallest number of dimensions, by means of the Law of Cosines and linear algebra, when only the inter-node distances are known [6]. Before starting the MDS position estimation, the pTOFs measured in the different nodes are distributed among all of them. In this way, the data collected by every node can be described by (4):

t (ρ) = {\hat{t}}_{M - 2} \dots {\hat{t}}_{M - q} \dots {\hat{t}}_{M - Q} \dots {\hat{t}}_{2 - 3} \dots {\hat{t}}_{q - l} \dots {\hat{t}}_{(Q - 1) - Q}

(4)

where t̂_M₋_q are the pTOFs computed in the Master node for every slave node q; and t̂_q₋_l is the pTOF computed between two slave nodes q and l, with q,l ∈ {2,⋯,Q} and q ≠l. The time delays tp are roughly determined at every node and they are considered time-invariants in the distance computation.

Computation of distances between Master and every slave node

Assuming that the moving velocities of the nodes are much lower than the propagation speed of the acoustic waves, it is possible to compute the distance between the Master and every slave node by the temporary relation described in (5), as follows:

d_{M - q} = ‖ p_{M} - p_{q} ‖ = \frac{[{\hat{t}}_{M - q} - (t p_{M} + t p_{q} + T_{CODE})]}{2} \cdot c

(5)

where tp_M and tp_q are the signal delay times in the emission and reception stage of the Master and the slave nodes respectively (tp_M =t_{Spk M} +t_{Mic M} and tpq =t_{Spk q} +t_{Mic q}).

Computation of distances between every pair of slave nodes

On the other hand, with the data collected by the slave nodes, it is possible to compute their distances by (6) and the reciprocal pTOFs measured. Again, assuming that the node velocity is much lower than the propagation speed of acoustic waves, this distance is:

d_{q - l} = ‖ p_{l} - p_{q} ‖ = \frac{c}{2} \cdot [{\hat{t}}_{q - l} + {\hat{t}}_{l - q} - t p_{l} - t p_{q} - 2 \cdot T_{CODE}]

(6)

where all the parameters have been previously defined.

If an additive Gaussian noise is considered in the measurements of pTOFs, in some particular cases, the slave nodes—see (2)—could detect a negative value of t̂_q₋_l; in such a case the involved pTOF will be set to zero, which is the nearest possible value.

Computation of node positions

With all the computed distances, a matrix D can be arranged, as follows:

D = (\begin{matrix} d_{M M} & \dots & d_{M (Q - 1)} & d_{M Q} \\ d_{2 M} & \dots & d_{2 (Q - 1)} & d_{2 Q} \\ ⋮ & ⋱ & ⋮ & ⋮ \\ d_{Q M} & \dots & d_{Q (Q - 1)} & d_{Q Q} \end{matrix})

(7)

In order to obtain the node positions by MDS [6], it is necessary to build a matrix B called dot-product. This matrix considers the distances among objects from a reference point, being the most suitable the centroid (midpoint) of the figure formed by the objects in a two or three dimensional system (2D or 3D). Every element of B can be obtained as follows:

b_{i j} = - \frac{1}{2} [d_{i j}^{2} - \frac{1}{Q} \sum_{q = 1}^{Q} d_{i q}^{2} - \frac{1}{Q} \sum_{l = 1}^{Q} d_{l j}^{2} + \frac{1}{Q^{2}} \sum_{m = 1}^{Q} \sum_{n = 1}^{Q} d_{m n}^{2}]

(8)

where d_ij,d_iq,d_jl,d_mn describe the distances among nodes with i,j,l,m,n,q ∈ {1,2,⋯,Q}.

Also B can be obtained from the position matrix p, previously defined in (3), but now considering the position matrix referred to the centroid as p*. In this way,B is obtained as follows:

B = p * \cdot {(p *)}^{T}

(9)

It is possible to obtain the estimation of the node positions by the factorization of B using singular value decomposition (SVD), as follows:

\begin{array}{l} B = U \cdot S \cdot U^{T} = U \cdot S^{1 / 2} \cdot S^{1 / 2} \cdot U^{T} = (U \cdot S^{1 / 2}) \cdot {(U \cdot S^{1 / 2})}^{T} \\ p * = (U \cdot S^{1 / 2}) \end{array}

(10)

where U is the eigenvector matrix and S is the eigenvalue matrix. By selecting the first two or three columns of p* (with the largest eigenvalues), according to the dimensions (2D or 3D respectively) of the reference system, it is possible to obtain the estimation of the node positions. Finally, in order to map the estimated positions to the reference system of every node, since the obtained position results are referred to the midpoint of the objects, it is necessary to consider a rotation and a translation with matrixes that can be easily calculated.

3.2. Refining Results

The MDS provides a suitable estimation of the node distribution and positions by converting a whole matrix of distance measurements into a topology with two or three dimensions. Nevertheless, the exact object position cannot be achieved, since there are different error sources in the detection of acoustic signals (environmental effects such as room reverberation, acoustic transducer bandwidth, accuracy in hardware clock signals, etc). These errors corrupt the matrix D and imply inaccuracy in the position estimation. Assuming that the S-RTOF measurements are independently perturbed by a Gaussian noise with zero average and a variance σ², the uncertainty of the observation vector T can be modeled as follows:

T = t (ρ) + η

(11)

where t(ρ) is the vector of the true pTOF (4), which are a function of the parameters to be estimated ρ; and η is a noise vector where every element is associated to an observation from S-RTOF. According to this noise consideration, the density of probability function of vector ρ can be defined as:

f d p_{(T, t (ρ))} = {(2 \cdot π)}^{\overset{- N o}{} / \underset{2}{}} \cdot {| \sum |}^{\overset{- 1}{} / \underset{2}{}} exp - \overset{1}{} / \underset{2}{} \cdot {[T - t (ρ)]}^{T} \sum^{- 1} [T - t (ρ)]

(12)

where Σ is the covariance matrix of noise vector η; and No is the total number of observations. The maximum likelihood (ML) estimator of parameters ρ is the one that maximizes the probability relation (12) [8], and it can be defined as:

\begin{array}{l} \hat{ρ} = {arg}_{ρ} max F (ρ, T) \\ F (ρ, T) = - \overset{1}{} / \underset{2}{} \cdot {[T - t (ρ)]}^{T} \sum^{- 1} [T - t (ρ)] \end{array}

(13)

In (13), the ML estimator depends on the observation vector T, as well as on the features or shape of the covariance matrix with dimensions Nox No. An special case is when the measurement observations are independently perturbed, which means that Σ is diagonal, and the pTOF for the Master and the slave nodes have variances

σ_{M - q}^{2}

and

σ_{q - l}^{2}

, respectively. This special case is usually used as an approximation of Σ; anyway a more detailed study about the nature of pTOF measurements should be performed in order to obtain the exact covariance matrix. According to this, if Σ is diagonal, the maximum likelihood estimator of parameters ρ has been obtained as:

\sum_{q = 2}^{Q} \frac{{\hat{t}}_{M - q}^{Estimated} - {\hat{t}}_{M - q}^{Measured}}{σ_{M - q}^{2}} + \sum_{q = 2}^{Q - 1} \sum_{l = q + 1}^{Q} \frac{{\hat{t}}_{q - l}^{Estimated} - {\hat{t}}_{q - l}^{Measured}}{σ_{q - l}^{2}} = 0

(14)

The first term in (14) represents the difference between the Master observations and its estimation, whereas the second term describes the difference between the pTOF observation and the estimation carried out between two slave nodes. According to this fact, the maximum likelihood estimator minimizes the difference between the measured times and the non-linear equations described in (1) and (2).

A suitable method to solve this kind of problems is the Levenberg-Marquardt Algorithm, which allows to find a local minimum by using a particular starting point. The results obtained with the MDS algorithm are a suitable starting point to estimate the coordinates by means of the LMA.

According to (14), the number of unknown coordinates as well as the time delays associated to every node should be considered. Nevertheless the estimation of all the time delays increases the complexity of the equation system to be solved so the time delays have been considered equal in all the nodes; under this assumption, the number of parameters to be estimated is:

P = D \cdot Q + 1 - \frac{D \cdot (D + 1)}{2}

(15)

where D represents the dimension of the coordinate system; and Q is the maximum number of nodes.

In order to solve the equation system, the number of observations carried out in the system should be higher than P. Since the number of linearly independent observations carried out by the proposed ranging mechanism is Q·(Q − 1) / 2, the minimum number of nodes required to determine the positions is:

\frac{Q \cdot (Q - 1)}{2} \geq D \cdot Q + 1 - \frac{D \cdot (D + 1)}{2}

(16)

According to (16), if the positions are computed in 2D, the minimum number of required nodes is Q = 4; and in 3D it is necessary to have at least Q = 6 nodes in the system.

4. Simulations Results and Performance Analysis

In order to compare the accuracy achieved with the architecture previously described and the used positioning algorithms, some simulations have been carried out. In this analysis, different types of errors have been modeled.

4.1. Node Position Estimation Considering a Gaussian Error in the pTOF Measurements

A first analysis has been performed by considering a node topology in 2D as shown in Figure 5, where the Master node condition is assigned to the object q = 1 with coordinates (0,0), whereas the node q = 2 forms a line with coordinates (0,y₂), providing the coordinate reference system (see Figure 5a). In this case, every node has a pTOF vector T with all the temporary relations collected by the nodes of the system, which are distributed using wireless communication modules. Since disturbances such as ambient and electronic noise have Gaussian nature, it has been considered that every element of T is corrupted with an additive Gaussian noise with zero average and variance σ². Furthermore, the time delays have been considered time-invariant and determined by an off-line characterization, with values t_Mic = 50μs and t_Spk = 50μs. The LMA has been carried out with the lqsnonlin function of the Matlab® optimization toolbox. One thousand tests have been done for every considered variance.

Figure 5a shows the 95% uncertainty ellipses (2σ) obtained around the estimated coordinate when the pTOFs have a Gaussian noise with a standard deviation σ = 100μs. Using LMA for optimization it is possible to achieve a closer solution for the coordinate estimation, as shown with dotted lines in Figure 5a. Also, a characterization of the position algorithms through the total bias and total variance in the coordinate estimation has been carried out. In this case, different standard deviations in the measurement errors have been considered. As shown in Figure 5b, the results obtained by LMA have a smaller variance in the coordinate estimation for all the nodes. On the other hand, both estimators are unbiased, even in those cases where the considered standard deviation is σ = 100μs (see Figure 5c), what implies an error in the distance measurements around 3 cm.

If the positioning algorithms for N₄ are computed changing the number of nodes in the topology described in Figure 6, i.e., considering 8, 12 and 16 nodes in every test, it can be observed that if the number of nodes is increased, the variance in the position estimation decreases. In order to verify this feature, the cumulative distribution function (CDF) of the positioning error has been obtained for the coordinate estimation of common node N₄. The CDF is plotted in Figure 6 for different numbers of nodes, considering an error σ = 10μs in the pTOF measurements. In this case, if more node information is added, a higher increment of the cumulative effect is obtained, which means that a better precision can be achieved.

4.2. Node Position Estimation Considering Errors in the Signal Processing Delay Characterization

In the previous tests the signal processing delays have been considered time-invariant. Nevertheless, the true value of tp may be different from those used for LMA initialisation. Furthermore, they can be different from one node to another. These differences can come from the diverse execution times of signal processing algorithms at every node, since clock signals are not ideal and can have not exactly the same rates. Also, the differences in the response of the transducers may modify tp for every node.

In order to verify the behaviour of the positioning process with these considerations, the algorithms have been tested with the topology described in Figure 5 and a Gaussian error in the signal processing delay characterization with a standard deviation from σ_tp = 1μs to σ_tp = 100μs (see Figure 7a).

In this case, it is observed that the MDS allows a higher precision than the LMA (see Figure 7a). On the other hand, in Figure 7b, the CDF for the position estimation of node N₄ is depicted with a continuous line, only for errors in the determination of tp. Comparing it to the CDF obtained only for errors in the pTOF computation (dotted line in Figure 7b), it is observed that LMA is less sensitive to errors in the pTOF measurements than to errors in the tp characterization. This implies that the used positioning algorithm is less sensitive to errors in the node coordinates than to errors in the time delays.

4.3. Node Position Estimation Varying the Topology of Nodes

In the previous analysis it is assumed that the node topology is fixed. In the topology described in Figure 8 node N₇ moves from point A, to B and C. At every position, the algorithms have been run one thousand times. The pTOFs have a Gaussian noise with a standard deviation σ = 10μs.Figure 8b and Figure 8c show a good accuracy in the position estimation of the node N₇. In this case, the orientation of the 95% uncertainty ellipse varies but the precision in the coordinate estimation does not depend on the node position referred to the reference system.

4.4. Effect of Non-Gaussian Errors in Node Position Estimation

The use of acoustic signals as ranging mechanism requires that the signal propagates along the line-of-sight (LOS) path between nodes. If LOS is blocked by obstacles, becoming a non-line-of-sight (NLOS) link, the signal may reach the receiver due to reflections in the environment. In this case the length of the reflected path is longer than the line-of-sight, reason why the measurements with NLOS errors can considerably bias the real pTOF value and provide inaccurate location estimation. These kinds of errors are non-Gaussian and they are more difficult to solve since they strongly depend on unknown environment conditions.

In order to verify the performance of the proposed algorithms with NLOS effects, the topology of Figure 5 has been tested. In the first test performed, the distance measurements between nodes N₁ and N₁₄ have a large observation error, whereas other nodes have clear LOS path. In practice, this situation can happen when the LOS path between the considered nodes is blocked by walls or other signal-scattering object. The NLOS has been modelled as a positive bias error with an uniformly random distribution, where the maximum value is a percentage of the real pTOF measured in the interval [0%, 50%]. The total bias and total variance in the position estimation have been obtained for the different NLOS error considered as is depicted in Figure 9. In this case, the LMA estimation of node positions allows to obtain a suitable precision and a low bias in the global node position estimation, when the NLOS provides errors up to 35% over the real pTOF between the nodes N₃ and N₆. Nevertheless, when stronger NLOS effects appear between the considered nodes, the global node position estimation has a reduced performance with both algorithms.

The second test considers an NLOS effect by means of a solid object closer to N₃ (see the node distribution in Figure 5), which blocks the path from the nodes N₁,N₂,N₆,N₁₃ to N₃. In this case, the total bias and total variance in the position estimation for different NLOS errors is depicted in Figure 10. It can be observed that the LMA estimation of node positions allows to achieve a suitable precision and a low bias in the global node position estimation, when the NLOS provides errors up to 25% over the real pTOF between the considered nodes.

This example shows that, due to the cooperative nature of the architecture, the NLOS effect in a set of pTOF measurement from different nodes implies errors in all the node positions. Nevertheless, the features of the ranging mechanism provide a set of redundant observation data, which, together with high-level algorithms such as geometry consistency or statistical analysis, can improve the estimation performance by identifying and rejecting those measurements with low accuracy.

5. Conclusions

The performance of a relative positioning algorithm based on the Multi-Dimensional Scaling (MDS) technique and the Levenberg-Marquardt algorithm (LMA) has been analyzed. In this case, the spatial relations among objects are determined by an acoustic sensor network where only acoustic emissions are used, providing a low-complex ranging mechanism. The MDS algorithm allows a geometric configuration of the nodes to be obtained with the minimum number of dimensions. Nevertheless, there are different error sources in the detection of acoustic signals that perturb the distance computation by inserting an error in the position estimation. In order to improve the achieved results, an optimization by LMA has been applied. In this way, the temporary relations among acoustic emissions carried out by the nodes have been used for the minimization. The characterization of the positioning procedure has been performed by Monte-Carlo simulations. The obtained results show that the LMA algorithm allows the precision in the MDS results to be improved, considering different node topologies and errors with Gaussian distribution in the determination of temporary relations. In this case, a fine-grained localization is achieved, even considering different error magnitude in the ranging mechanism (from σ = 1μs to σ = 100μs). The precision in the position estimation varies from 2 cm to 5 cm in the case of the MDS algorithm (when all the nodes are inside a square of 3 × 3 m). Furthermore, a better precision has been obtained by the LMA optimization: from 0.5 cm to 2 cm. On the other hand, the positioning algorithm is sensitive to errors in the signal delays tp, providing a high coordinate estimation error. Therefore it is necessary to accurately determine them by an online characterization and by considering them time-variant. Finally, non-Gaussian errors (i.e., NLOS effects) have been considered since acoustic signals are sensitive to solid objects. The obtained results show that the system is robust to a bias of up to 25% over the pTOF measured with LOS.

Acknowledgments

This work has been supported by the Ministerio de Educación y Ciencia from Spain (RESELAI project, ref. TIN2006-14896-C02-01), by the Ministerio de Fomento from Spain (DETECTREN project, ref. P13/08), by Comunidad de Madrid/Universidad de Alcalá (SUSGAB project, ref. CCG08-UAH/DPI-4072) and by Facultad de Ingeniería, Universidad Nacional de la Patagonia San Juan Bosco, Argentina.

References and Notes

Hazas, M.; Kray, C.; Gellersen, H.; Agbota, H.; Kortuem, G.; Krohn, A. A relative positioning system for co-located mobile devices. Third International Conference on Mobile Systems, Applications, and Services (MobiSys'05), Seattle, WA, USA, June 6-8, 2005; pp. 177–190.
Navarro-Serment, L.; Grabowski, R.; Paredis, C.; Kohsla, P. Millibots. IEEE Robot. Automat. 2002, 9, 31–40.
Higtower, J.; Borriello, G. Location systems for ubiquitous computing. IEEE Comput. 2001, 34, 57–66. [Google Scholar]
Patwari, N.; Hero, A.; Perkins, M.; Correal, N.; O'dea, R. Relative location estimation in wireless sensor networks. IEEE Trans. Signal Process 2005, 51, 2137–2148. [Google Scholar]
Krohn, A.; Zimmer, T.; Beigl, M. Enhancing tabletop games with relative positioning technology. In Advances in Pervasive Computing; Oesterreichische Computer Gesellschaft: Wien, Austria, 2004. [Google Scholar]
Torgerson, W.S. Multidimensional scaling: theory and method. Psychometrika 1952, 17, 401–419. [Google Scholar]
Shang, Y.; Meng, J.; Shi, H. A new algorithm for relative localization in wireless sensor networks. 18th International Parallel and Distributed Processing Symposium (IPDPS'04), Santa Fe, NM, USA, April 26-30, 2004; p. 24.
Moses, R.; Krishnamurthy, D.; Patterson, R. A self-localization method for wireless sensor networks. Eurasip J. appl. Signal Process 2003, 4, 348–358. [Google Scholar]
Raykar, V.; Kozintsev, I.; Lienhart, R. Position calibration of microphones and loudspeakers in distributed computing platforms. IEEE Trans. Speech Audio Proc. 2005, 13, 70–83. [Google Scholar]
De Marziani, C.; Urena, J.; Hernández, Á.; Mazo, M.; Alvarez, F.; García, J.J.; Villadangos, J.M.; Jimenez, A. Simultaneous Measurement of Times-of-Flight and Communications in Acoustic Sensor Networks. Workshop on Intelligent Signal Processing (WISP'05), Faro, Portugal, September 1-3, 2005; pp. 122–127.
Wylie-Green, M.P.; Wang, S.S. Robust range estimation in the presence of the non-line-of-sight error. IEEE Vehicular Technology Conference, Rhodes, Greece, May 6-9, 2001; pp. 101–105.
Chan, Y.; Tsui, W.; So, H.; Ching, P. Time-of-arrival based localization under NLOS conditions. IEEE Trans. Veh. Technol. 2006, 55, 12–24. [Google Scholar]
Fan, P.; Darnell, M. Sequence design for communications applications; Research Studies Press Ltd.: London, UK, 1996. [Google Scholar]
ZigBee Alliance. Available online: http://www.zigbee.org (accessed on December 15th, 2007).
Tseng, C.-C.; Liu, C.L. Complementary set of sequences. IEEE Trans. Inform. Theor. 1972, IT-18, 644–652. [Google Scholar]
De Marziani, C.; Ureña, J.; Hernandez, A.; Mazo, M.; Alvarez, F.J.; Garcia, J.J.; Donato, P. Modular architecture for efficient generation and correlation of complementary set of sequences. IEEE Trans. Sig. Process 2007, 55, 2323–2337. [Google Scholar]
De Marziani, C.; Urena, J.; Hernandez, A.; Mazo, M.; Garcia, J.J.; Jimenez, A.; Villadangos, J.M.; Perez, M.C.; Ochoa, A.; Alvarez, F. Inter-symbol interference reduction on macro-sequences generated from complementary set of sequences. IEEE Industrial Electronics, IECON 2006—32nd Annual Conference 2006, Paris, France, November 7-10, 2006; pp. 3367–3372.
Rydström, M.; Urruela, A.; Ström, E.; Svensson, A. A low complexity algorithm for sensor localization. 11th European Wireless Conference (EW'05), Nicosia, Cyprus, April 10-13, 2005; pp. 714–718.
McCrady, D.; Doyle, L.; Forstrom, H.; Dempsey, T.; Martorana, M. Mobile ranging using low-accuracy clocks. IEEE Trans. Microwave Theory 2000, 48, 951–957. [Google Scholar]

Figure 1. General scheme of the proposed sensor network.

Figure 2. Detailed block diagram of node hardware architecture.

Figure 3. Principle of measurement using simultaneous Round-Trip-Time-of-Flight. (a) Emission of the request from the Master (starting the positioning process). (b) Acknowledgement from every node in order to compute distances.

Figure 4. Positioning Algorithm Scheme.

Figure 5. Position estimation for a distribution of nodes with a Gaussian noise in the pTOF measurements. (a) 95% uncertainty ellipses considering an error with standard deviation Σ = 100μs. (b) Total variance in the position estimation. (c) Total bias in the position estimation.

Figure 6. Cumulative distribution function in the position estimation of node N₄ depending on the total number of nodes (8, 12 and 16), and for a Gaussian error in the pTOF measurements of Σ = 10 μs.

Figure 7. Position estimation with errors in tp characterization. (a) Total variance in the coordinate estimation of eight nodes. (b) CDF in the position estimation of node N₄.

Figure 8. Position estimation when changing the topology of nodes.

Figure 9. Errors in the position estimation considering NLOS effect between nodes N₁ and N₁₄ (see the node distribution in Figure 5). (a) Total variance in the coordinate estimation. (b) Total bias in the coordinate estimation.

Figure 10. Errors in the position estimation considering NLOS effect between nodes N₁,N₂,N₆,N₁₃ and N₃ (according to the distribution shown in Figure 5) (a) Total variance in the coordinate estimation. (b) Total bias in the coordinate estimation.

© 2009 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).

Share and Cite

MDPI and ACS Style

De Marziani, C.; Ureña, J.; Hernandez, Á.; Mazo, M.; García, J.J.; Jimenez, A.; Pérez Rubio, M.C.; Álvarez, F.; Villadangos, J.M. Acoustic Sensor Network for Relative Positioning of Nodes. Sensors 2009, 9, 8490-8507. https://doi.org/10.3390/s91108490

AMA Style

De Marziani C, Ureña J, Hernandez Á, Mazo M, García JJ, Jimenez A, Pérez Rubio MC, Álvarez F, Villadangos JM. Acoustic Sensor Network for Relative Positioning of Nodes. Sensors. 2009; 9(11):8490-8507. https://doi.org/10.3390/s91108490

Chicago/Turabian Style

De Marziani, Carlos, Jesus Ureña, Álvaro Hernandez, Manuel Mazo, Juan Jesús García, Ana Jimenez, M. Carmen Pérez Rubio, Fernando Álvarez, and José Manuel Villadangos. 2009. "Acoustic Sensor Network for Relative Positioning of Nodes" Sensors 9, no. 11: 8490-8507. https://doi.org/10.3390/s91108490

APA Style

De Marziani, C., Ureña, J., Hernandez, Á., Mazo, M., García, J. J., Jimenez, A., Pérez Rubio, M. C., Álvarez, F., & Villadangos, J. M. (2009). Acoustic Sensor Network for Relative Positioning of Nodes. Sensors, 9(11), 8490-8507. https://doi.org/10.3390/s91108490

Article Menu