LIU:SURVEY OF WIRELESS INDOOR POSITIONING TECHNIQUES AND SYSTEMS 1069 R-R LS B C R2 Fig.3.Positioning based on RSS,where LS1:LS2,and LS3 denote the P measured path loss. R received signals over a time period T R3-R zi(t)xj(t-T)dt (4) Fig.2.Positioning based on TDOA measurements. The TDOA estimate is the value T that maximizes R(), i.e.,the range differences.This approach requires that the mea- suring units share a precise time reference and reference sig- nals,but does not impose any requirement on the mobile tar- user as the location of the base station or reference point that get.Frequency domain processing techniques are usually used is located closest to that user.The RWGH algorithm can be to calculate T.Except the previous TDOA methods,a delay basically viewed as a form of weighted least-squares algorithm. measurement-based TDOA measuring method was proposed It is suitable for LOS.non-LOS (NLOS)and mixed LOS/NLOS in [23]for 802.11 wireless LANs,which eliminates the require- channel conditions. ment of initial synchronization in the conventional methods. b)TDOA:The idea of TDOA is to determine the relative c)RSS-Based (or Signal Attenuation-Based)Method: position of the mobile transmitter by examining the difference The above two schemes have some drawbacks.For indoor en- in time at which the signal arrives at multiple measuring units, vironments,it is difficult to find a LOS channel between the rather than the absolute arrival time of TOA.For each TDOA transmitter and the receiver.Radio propagation in such environ- measurement,the transmitter must lie on a hyperboloid with a ments would suffer from multipath effect.The time and angle of constant range difference between the two measuring units.The an arrival signal would be affected by the multipath effect:thus. equation of the hyperboloid is given by the accuracy of estimated location could be decreased.An al- ternative approach is to estimate the distance of the mobile unit R,=V(-x)2+(-2+(台-22 from some set of measuring units,using the attenuation of emit- ted signal strength.Signal attenuation-based methods attempt -V(-x)2+(-)2+(a-z)2 (3) to calculate the signal path loss due to propagation.Theoret- ical and empirical models are used to translate the difference between the transmitted signal strength and the received signal where (xi,yi,zi)and (xj,yj,zj)represent the fixed receivers strength into a range estimate,as shown in Fig.3. i and j;and (y,2)represent the coordinate of the target [3]. Due to severe multipath fading and shadowing present in Except the exact solutions to the hyperbolic TDOA equation the indoor environment,path-loss models do not always hold. shown in (3)through nonlinear regression,an easier solution The parameters employed in these models are site-specific.The is to linearize the equations through the use of a Taylor-series accuracy of this method can be improved by utilizing the pre- expansion and create an iterative algorithm [6]. measured RSS contours centered at the receiver [7]or multiple A 2-D target location can be estimated from the two intersec- measurements at several base stations.A fuzzy logic algorithm tions of two or more TDOA measurements,as shown in Fig.2. shown in [8]is able to significantly improve the location accu- Two hyperbolas are formed from TDOA measurements at three racy using RSS measurement. fixed measuring units(A,B,and C)to provide an intersection d)RTOF:This method is to measure the time-of-flight of point,which locates the target P. the signal traveling from the transmitter to the measuring unit The conventional methods for computing TDOA estimates and back,called the RTOF(see Fig.1).For RTOF,a more mod- are to use correlation techniques.TDOA can be estimated from erate relative clock synchronization requirement replaces the the cross correlation between the signals received at a pair of above synchronization requirement in TOA.Its range measure- measuring units.Suppose that for the transmitted signal s(t),the ment mechanism is the same as that of the TOA.The measuring received signal at measuring unit i is xi(t).Assume that xi(t) unit is considered as a common radar.A target transponder is corrupted by the noise n(t)and delayed by di,then i(t)= responds to the interrogating radar signal,and the complete s(t-di)+n(t).Similarly,the signal zj(t)=s(t-dj)+roundtrip propagation time is measured by the measuring units. n(t),which arrives at measuring unit j,is delayed by d and However,it is still difficult for the measuring unit to know the corrupted by the noise n;(t).The cross-correlation function exact delay/processing time caused by the responder in this of these signals is given by integrating the lag product of two case.In long-range or medium-range systems,this delay could Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply.LIU et al.: SURVEY OF WIRELESS INDOOR POSITIONING TECHNIQUES AND SYSTEMS 1069 Fig. 2. Positioning based on TDOA measurements. user as the location of the base station or reference point that is located closest to that user. The RWGH algorithm can be basically viewed as a form of weighted least-squares algorithm. It is suitable for LOS, non-LOS (NLOS) and mixed LOS/NLOS channel conditions. b) TDOA: The idea of TDOA is to determine the relative position of the mobile transmitter by examining the difference in time at which the signal arrives at multiple measuring units, rather than the absolute arrival time of TOA. For each TDOA measurement, the transmitter must lie on a hyperboloid with a constant range difference between the two measuring units. The equation of the hyperboloid is given by Ri,j = (xi − x)2 + (yi − y)2 + (zi − z)2 − (xj − x)2 + (yj − y)2 + (zj − z)2 (3) where (xi, yi, zi) and (xj , yj , zj ) represent the fixed receivers i and j; and (x, y, z) represent the coordinate of the target [3]. Except the exact solutions to the hyperbolic TDOA equation shown in (3) through nonlinear regression, an easier solution is to linearize the equations through the use of a Taylor-series expansion and create an iterative algorithm [6]. A 2-D target location can be estimated from the two intersec￾tions of two or more TDOA measurements, as shown in Fig. 2. Two hyperbolas are formed from TDOA measurements at three fixed measuring units (A, B, and C) to provide an intersection point, which locates the target P. The conventional methods for computing TDOA estimates are to use correlation techniques. TDOA can be estimated from the cross correlation between the signals received at a pair of measuring units. Suppose that for the transmitted signal s(t), the received signal at measuring unit i is xi(t). Assume that xi(t) is corrupted by the noise ni(t) and delayed by di, then xi(t) = s(t − di) + ni(t). Similarly, the signal xj (t) = s(t − dj )+ nj (t), which arrives at measuring unit j, is delayed by dj and corrupted by the noise nj (t). The cross-correlation function of these signals is given by integrating the lag product of two Fig. 3. Positioning based on RSS, where LS1, LS2, and LS3 denote the measured path loss. received signals over a time period T Rˆxi ,xj (τ ) = 1 T  T 0 xi(t)xj (t − τ )dt. (4) The TDOA estimate is the value τ that maximizes Rxi ,xj (τ ), i.e., the range differences. This approach requires that the mea￾suring units share a precise time reference and reference sig￾nals, but does not impose any requirement on the mobile tar￾get. Frequency domain processing techniques are usually used to calculate τ . Except the previous TDOA methods, a delay measurement-based TDOA measuring method was proposed in [23] for 802. 11 wireless LANs, which eliminates the require￾ment of initial synchronization in the conventional methods. c) RSS-Based (or Signal Attenuation-Based) Method: The above two schemes have some drawbacks. For indoor en￾vironments, it is difficult to find a LOS channel between the transmitter and the receiver. Radio propagation in such environ￾ments would suffer from multipath effect. The time and angle of an arrival signal would be affected by the multipath effect; thus, the accuracy of estimated location could be decreased. An al￾ternative approach is to estimate the distance of the mobile unit from some set of measuring units, using the attenuation of emit￾ted signal strength. Signal attenuation-based methods attempt to calculate the signal path loss due to propagation. Theoret￾ical and empirical models are used to translate the difference between the transmitted signal strength and the received signal strength into a range estimate, as shown in Fig. 3. Due to severe multipath fading and shadowing present in the indoor environment, path-loss models do not always hold. The parameters employed in these models are site-specific. The accuracy of this method can be improved by utilizing the pre￾measured RSS contours centered at the receiver [7] or multiple measurements at several base stations. A fuzzy logic algorithm shown in [8] is able to significantly improve the location accu￾racy using RSS measurement. d) RTOF: This method is to measure the time-of-flight of the signal traveling from the transmitter to the measuring unit and back, called the RTOF (see Fig. 1). For RTOF, a more mod￾erate relative clock synchronization requirement replaces the above synchronization requirement in TOA. Its range measure￾ment mechanism is the same as that of the TOA. The measuring unit is considered as a common radar. A target transponder responds to the interrogating radar signal, and the complete roundtrip propagation time is measured by the measuring units. However, it is still difficult for the measuring unit to know the exact delay/processing time caused by the responder in this case. In long-range or medium-range systems, this delay could Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply.