# TDoA UWB positioning with three receivers using known indoor features_图文

Proceedings of 2010 IEEE International Conference on Ultra-Wideband (ICUWB2010)

TDOA UWB Positioning with Three Receivers Using Known Indoor Features

Jan KIETLINSKI-ZALESKI? , Takaya YAMAZATO? and Masaaki KATAYAMA?

School of Engineering Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464–8603, Japan Email: jkietlin@katayama.nuee.nagoya-u.ac.jp ? EcoTopia Science Institute Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464–8603, Japan

?

Abstract—Ultra-Wideband is an attractive technology for short range positioning, especially indoors. However, for normal 3D Time Difference of Arrival (TDoA) positioning, at least four receivers with unblocked direct path to the transmitter are required. A requirement that is not always met. In this work, a novel method for TDoA positioning using only three receivers is presented and tested using real-world measurements. Positioning with three receivers is possible by exploiting the knowledge of some of the indoor features, namely positions of big ?at re?ective surfaces, re?ectors, for example ceiling and walls. Index Terms—UWB, positioning, TDoA, indoor

I. I NTRODUCTION The main challenge for indoor positioning is the big number of re?ections and diffractions, from walls, furniture, people, that introduce strong fading. The conventional way to combat fading is to increase the bandwidth of the signal, which not only limits fading but also increases time resolution and accuracy of time-based ranging. Ultra-Wideband (UWB) radio is then a natural choice for high precision indoor positioning. Such positioning has many possible applications, for example in-building goods tracking, workers monitoring or access control [1]. For standard Three Dimensional (3D) Time Difference of Arrival (TDoA) Positioning ranges to four or more receivers are needed [2]. This is because, in addition to 3D transmitter position, time sent also has to be estimated. When only three receivers are available, the conventional method is to reduce the problem to 2D by assuming height[3]. Method that, apart from not estimating height, can introduce a height-related 2D bias to the results. In this paper we propose a novel method for three receiver positioning that uses the high time resolution of UWB signals and knowledge of big ?at re?ective surfaces in the environment, which we will call re?ectors, to estimate the 3D position. Because of the high time resolution of UWB signal, multipath components (MPCs) are distinguishable. Some MPCs are caused by re?ections from known re?ectors. We will use MPC delays together with knowledge of re?ector positions for positioning. Such usage of later arriving MPCs was not, to our knowledge, reported in the literature before. The proposed method was tested using signals obtained during a measurement campaign.

This paper builds upon our previous work on ToA positioning methods. In [4] we presented a MPC-based ToA method for two receivers using Least Squares approach, validated by simulation. In [5] we introduced a much improved Maximum Likelihood(ML)-based method, using measurement results for validation. Finally, in this paper we tackle TDoA positioning with three receivers and a new ML-based TDoA method. The rest of the paper is organized as follows: We start with a general description of the problem in section II. Next in section III, we de?ne the system elements. We then introduce our own method in section IV, dividing it into result curve calculation step in IV-A and ML on-curve position estimation step in IV-B. Next, in section V we present results of the proposed method when used with measurement data. Finally, we draw conclusions in section VI. II. P ROBLEM S TATEMENT In TDoA ranging transmitter T is unsynchronized with receivers R = [R1 , · · · , RN ]. Because signal sent time is not known, range from receiver Rn to transmitter T , dn , cannot be directly determined from signal reception time tn . Instead, range differences between different receivers Rn can be computed. Choosing R1 as reference, for each other Rn , ?n,1 , can be calculated as: estimate of range difference, d ?n,1 = C (tn ? t1 ), d n = 1, 2, . . . , N (1)

where C is the speed of light. Next, remembering that dn,1 = dn ? d1 , position of the transmitter T can be estimated by solving: ? ? d2,1 = (xt ? x2 )2 + (yt ? y2 )2 + (zt ? z2 )2 ? ? ? ? ? (xt ? x1 )2 + (yt ? y1 )2 + (zt ? z1 )2 ? ? . . (2) . ? ? ? 2 2 2 ? ? dN,1 = (xt ? xN ) + (yt ? yN ) + (zt ? zN ) ? ? ? (xt ? x1 )2 + (yt ? y1 )2 + (zt ? z1 )2 where T := [xt , yt , zt ] is the position of transmitter and Rn := [xn , yn , zn ] that of receiver n, n = 1 · · · N . For N > 4, a data fusion method, such as Least Squares, can be used. For N = 4, the set can be solved directly. For N = 3, only three receivers, the result is not a point, but a second degree curve (hyperbola, ellipse or parabola).

978-1-4244-5306-1/10/$26.00 ?2010 IEEE

de?ned by vector [xmin , ymin , zmin , xmax , ymax , zmax ]. T ∈ SA ? xmin ≤ xt ≤ xmax ymin ≤ yt ≤ ymax zmin ≤ zt ≤ zmax (4)

No knowledge about transmitter’s position in SA is assumed. Knowledge of a set of M big, ?at re?ectors, for example ceiling and walls, is assumed. The set is represented as FR = [F R1 , · · · , F RM ]. Each re?ector F Rm is described 2 by roughness σF Rm and a 3D surface equation: Am x + Bm y + Cm z + Dm = 0

Fig. 1. Many re?ected paths with similar path length - problem with ?nding MPC matching F Rm re?ection. Example of receiver’s mirror image concept.

2 2 A2 m + Bm + Cm = 1

(5)

More information is needed to ?nd 3D position of the transmitter. The conventional method is to assume the height coordinate and reduce the problem to 2D. This method, if transmitter’s height is not nearly constant, will produce a bias. Since this bias is height-related, it cannot be reduced by ?ltering (in case of a moving tag). To solve this problem, to ?nd the 3D transmitter position, information contained in received MPCs is used. If for each receiver-re?ector pair it was known which MPC in the signal detected by receiver matches the re?ection from the re?ector, using MPC delays for positioning would be trivial. Each re?ector-MPC match found would be an extra range measurement to an imaginary receiver, mirror image of the real receiver. Unfortunately, indoor environment is rich in re?ections and diffractions that cause many MPCs. A simple example is presented in Fig. 1. Correct re?ector-MPC matches are not known a priori. This paper concentrates on the problem of using information contained in MPCs, assuming only that for each re?ector there is a matching MPC among detected MPCs.

where [Am , Bm , Cm , Dm ] are normalized surface coef?cients of re?ector F Rm and [x, y, z ] are coordinates in 3D space. 2 Roughness σF Rm is the assumed added path length variance 2 caused by re?ection from F Rm . σF Rm models both error in assumed re?ector position and irregularities of the re?ector. The knowledge of FR can be either given a priori, or gained using a calibration step. Mirror image of receiver Rn through m . re?ector F Rm will be denoted as Rn

m = Rn ? 2(Rn · [Am Bm Cm ]+ Dm )[Am Bm Cm ] (6) Rn m m m where Rn := [xm n , y n , zn ] . In ranging, each receiver Rn can detect not only ?rst, but all distinct MPCs. Result of ranging is a vector of measured ?J ?j ?1 MPC arrival times [t n , . . . , tn ], where tn is assumed to have j j j2 ? a Gaussian error distribution: tn = tn + ej n ? N (0, σn ). Without knowing t0 , signal sent time, ranges cannot be directly calculated. Range differences to a chosen refer?1 ence are calculated instead. R is reordered so that t 1 = 1 minn∈(1,N ) (tn ), ie. R1 becomes the closest receiver to T . R1 and t1 1 are chosen as reference. N vectors of range difference estimates dn = ?J ] are calculated as: ?1 , · · · , d [d n,1 n,1

?j = (t ?j ?1 d n ? t1 )C n,1 ?j = dj + ej ? N (0, C 2 (σ j 2 + σ j 2 )) d n n,1 n,1 n,1 1

(7) (8)

III. S YSTEM MODEL A mobile UWB transmitter T is sending pulses. Each pulse is received by a set of N stationary receivers R = [R1 , · · · , RN ]. Each receiver is described by its 3D position vector, Rn := [xn , yn , zn ]. Signal at Rn is often represented in the literature as:

Kn

where C is the speed of light. In each received signal, the MPC corresponding to the direct path is assumed to be detected, as well as most MPCs matching re?ections from FR. The ?rst MPC range of dn , ?1 will then correspond to the direct path between T and Rn . d n,1 dn will also contain a subset corresponding to FR-re?ected paths. This subset is not known a priori. IV. P OSITION E STIMATION WITH T HREE R ECEIVERS A. Result Curve(RC) The ?rst step of the proposed method is to use direct path range differences to calculate Result Curve(RC ). RC should contain / be near to real transmitter position. RC is calculated as the solution of (2) for three receivers. In a nondegenrate case it will be a second degree curve, hyperbola, ellipse or parabola. An example RC is shown on Fig. 2. Paper

rn (t) =

kn =1

αkn s(t ? τkn ) + n(t),

(3)

where Kn is the number of MPCs, αk and τk are the fading coef?cient and delay of kth MPC, respectively, n(t) is zero-mean additive white Gaussian noise (AWGN), s(t) is the transmitted pulse shape. Subscript n de?nes to which receiver’s received signal the parameter applies to. The transmitter T := [xt , yt , zt ] is inside Service Area SA,

Fig. 2. Result Curve (RC ) - Second degree curve, solution of eq. (2) for three receivers. Real transmitter position should be near RC . Presented in prime base.

[6] presents a simple way to calculate and represent RC . Following it, RC is de?ned with a [g, h, d, e, f ] parameter vector and a 3D rotation + translation transformation Q(·) from real base to prime base, de?ned by receiver positions: R1 = [0, 0, 0], R2 = [b, 0, 0], R3 = [cx , cy , 0] . yt = gxt + h zt = ± dxt2 + ext + f ,T = Q

?1

Fig. 3.

Flowchart of the proposed algorithm

lowering contributions from early MPCs to offset the tendency of the algorithm to assign high probability near re?ector F Rm . Pj = min exp ? Pfst (1 ?

1 dj n,1 ? dn,1 ) ,1 dmax

(T ) (9)

(11)

where T := [xt , yt , zt ] are possible transmitter positions in prime base, T := [xt , yt , zt ] are possible transmitter positions in real base. Transmitter’s position on the RC can be described with zt as T (zt ). For each zt there are two possible xt . xt corresponding to lower |T | (ie. closer to R1 ) is chosen. This can cause error if RC is an ellipse, both xt being correct solutions. Since T ∈ SA , only zt : T (zt ) ∈ SA are considered. B. Position on RC Calculation Algorithm The second step of the proposed method is ?nding real transmitter position T (zt ) on RC . Re?ector positions and MPC delays are used. Since re?ector-MPC matches are not known, a statistical approach is used. Each detected MPC is assumed to be a possible match for re?ector. For each receiver-re?ector pair (Rn , F Rm ) ∈ R × FR, dj n,1 matching to F Rm -re?ected path to Rn will, with big probability, be among detected MPC range differences, dn . F Rm -re?ected path to Rn can be represented as a direct path m , as discussed in Section III. The error of MPC detection to Rn m2 2 2 2 is assumed to be Gaussian with σn = σn + σF Rm , σn being range measurement variance (assumed constant for all MPCs), 2 σF Rm being re?ector’s roughness. Then, likelihood function for possible T (zt ), L(dn ; zt ) is constructed as follows: L(dn ; zt ) = Nrm Pndet +

Jn

where Pfst , ?rst MPC penalty, and dmax , maximum penalty length, are algorithm parameters. m zt) for If the matching dj n,1 is detected, the value of Ln ( T (zt ) near to the real position of T will be high. Because zt) will also of other, non-matching MPCs the value of Lm n( be high for other zt . However, for each (Rn , F Rm ) pair, zt) near T will be high but high value regions caused Lm n( by non-matching MPCs will be different. If all Lm zt) for n( (Rn , F Rm ) ∈ R × FR are combined, the result likelihood function L(zt) should still be high near T , while semirandom and lower for other zt . The total likelihood function L(zt) is calculated as follows: L(zt) =

n∈[1,N ],m∈[1,M ]

Lm zt) n(

(12)

This calculation assumes the independence between Lm n which is not strictly correct, but the introduced error is small. Finally, zt estimate is found by maximizing likelihood: z ?t = arg max

zt n∈[1,N ],m∈[1,M ]

ln Lm zt) n(

(13)

The result transmitter position is T (? zt ). A ?owchart of the complete algorithm is presented in Fig. 3 V. M EASUREMENT RESULTS

+ Nrm

j =1

Pj exp

j m ?1 d(T (zt ),Rn )?(dn,1 +d(T (zt ),R1 )) 2 m 2 σn

(10)

where Nrm is a normalization constant, Pndet represents the m ) chance that the matching MPC was not detected, d(T (zt ), Rn m , dj is the range differis the range between T (zt ) and Rn n,1 ence for jth MPC in the Rn received signal. Pj is a penalty

In order to verify the proposed method, we performed measurements at Warsaw University of Technology(PW), Department of Electronics and Information Theory(EiTI), in cooperation with Dr. Jerzy Kolakowski. Fig. 4 presents measurement setup. The transmitted signal was designed to roughly correspond to the 3.4-4.8 GHz band.

1.4

Mean Square Error (MSE) [m]

1.2 1 0.8 0.6 0.4 0.2 0

ToA, direct solution TDoA, Assumed Height (1.5 m) TDoA, Proposed Algorithm

Fig. 4.

Measurement Setup, schematic

1

2

3

4

5

Number of reflectors

Fig. 6. Average 3D positioning error for different number of known re?ectors

proposed method is better if 3 or more re?ectors are used. Best result, achieved for 4 re?ectors, lowers the MSE by 12% comparing to Assumed Height method. Results of the proposed method generally improve with the number of re?ectors used. However, this is not the case for the 5th re?ector, the door wall. As can be seen on Fig. 5, door wall is uneven, with sections at different depths, making a ?at re?ector a poor approximation of its shape and introducing error defeating the gain. VI. C ONCLUSIONS In this paper we presented a TDoA positioning method using three receivers and knowledge of indoor re?ective surfaces. Measurement results show that it can determine the transmitter’s position with better accuracy than the conventional Assumed Height method. A more random error distribution, which is useful in conjunction with positiontracking algorithms, is also a bene?t. The proposed method is best to be used as a backup scheme in a bigger localization system, for cases when only three receivers are reliably in the range of the transmitter. R EFERENCES

[1] Z. Sahinoglu, S. Gezici, and I. Guvenc, Ultra-wideband positioning systems: theoretical limits, ranging algorithms, and protocols. Cambridge Univ Press, 2008. [2] S. Gezici, Z. Tian, G. B. Giannakis, H. Kobayashi, A. F. Molisch, H. V. Poor, and Z. Sahinoglu, “Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks,” IEEE Signal Process. Mag., vol. 22, no. 4, pp. 70–84, July 2005. [3] J. Schroeder, S. Galler, K. Kyamakya, and T. Kaiser, “Three-dimensional indoor localization in non line of sight uwb channels,” in Proc. IEEE International Conference on Ultra-Wideband ICUWB 2007, 2007, pp. 89–93. [4] J. Kietlinski-Zaleski, T. Yamazato, and M. Katayama, “Toa uwb position estimation with two receivers and a set of known re?ectors,” in Proc. IEEE International Conference on Ultra-Wideband ICUWB 2009, 2009, pp. 376–380. [5] ——, “Experimental validation of toa uwb positioning with two receivers using known indoor features,” in Proc. IEEE/ION Position, Location and Navigation Symposium PLANS 2010, 2010. [6] B. Fang et al., “Simple solutions for hyperbolic and related position ?xes,” IEEE Transactions on Aerospace and Electronic Systems, vol. 26, no. 5, pp. 748–753, 1990. [7] K. Siwiak, H. Bertoni, and S. M. Yano, “Relation between multipath and wave propagation attenuation,” Electronics Letters, vol. 39, no. 1, pp. 142–143, 9 Jan 2003.

Fig. 5.

Experiment Layout. Lecture Room S36, EiTI, PW

The service area was a classroom, as presented on Fig. 5. Receivers R1, R3 and R4, were used. The considered re?ectors were: ceiling, ?oor, left, right and door walls, in that order. Measurements were performed for transmitters at heights of 0.5, 1.5 and 2.5m placed at points shown in Fig. 5, for a total of 60 positions. Modi?ed CLEAN algorithm was used for MPC detection [7]. Table I presents method parameters used. 3D Mean Square Errors (MSE) for 60 transmitter positions using different 3-receiver methods are presented in Fig. 6. Best results are achieved with Time of Arrival positioning. If available, ToA should be used. The standard three receivers TDoA algorithm, Assumed Height has MSE of 89 cm. The

TABLE I PARAMETERS USED IN THE PROPOSED METHOD Pndet Pfst dmax [m] σn σF R1 σF R2 σF R3 σF R4 σF R5 0.05 1.25 1.5 0.10m 0.12m 0.18m 0.20m 0.20m 0.30m