1068 IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS,VOL.37.NO.6.NOVEMBER 2007 data link is provided in a positioning system,it is possible to send the measurement result from a self-positioning measuring unit to the remote side,and this is called indirect remote posi- tioning,which is the third system topology.If the measurement R result is sent from a remote positioning side to a mobile unit via a wireless data link,this case is named indirect self-positioning, which is the fourth system topology. Our paper is different from the previous survey papers [1] and [2]in several ways.Comparing with the previous survey paper [1],our paper focuses on indoor application of wireless Fig.1.Positioning based on TOA/RTOF measurements. location positioning while [1]just generally describes the lo- cation systems for ubiquitous computing,without addressing attenuation of the emitted signal strength or by multiplying the different types of location algorithms,especially for wireless radio signal velocity and the travel time.Roundtrip time of flight location methods.Also,the paper [2]presents a slight out-of- (RTOF)or received signal phase method is also used for range date overview of the technologies for wireless indoor location estimation in some systems.Angulation locates an object by solutions,and does not offer much detail about them and per- computing angles relative to multiple reference points.In this formance benchmarking for indoor wireless positioning system. survey,we focus on the aforementioned measurements in the The publication date of this paper is 2002,and since then,sev- shorter range,low-antenna,and indoor environment. eral wireless indoor positioning systems or solutions have been 1)Lateration Techniques: developed.In this paper,we present the latest developed systems a)TOA:The distance from the mobile target to the mea- or solutions,and their location algorithms.Our main purpose is suring unit is directly proportional to the propagation time.In to provide a qualitative overview for them.When possible,we order to enable 2-D positioning,TOA measurements must be also offer a quantitive comparison of these systems or solutions. made with respect to signals from at least three reference points, This review paper is organized as follows.Section II shows as shown in Fig.1 [4].For TOA-based systems,the one-way the measuring principles for location sensing and the position- propagation time is measured,and the distance between mea- ing algorithms corresponding to different measuring principles. suring unit and signal transmitter is calculated.In general,direct Performance metrics for indoor positioning techniques are ex- TOA results in two problems.First,all transmitters and receivers plained in Section III.Section IV presents current wireless in- in the system have to be precisely synchronized.Second,a times- door positioning systems and solutions,and their performance tamp must be labeled in the transmitting signal in order for the comparison.Finally,Section V concludes the paper and gives measuring unit to discern the distance the signal has traveled. possible future directions for research on wireless positioning TOA can be measured using different signaling techniques such systems for indoor environments. as direct sequence spread-spectrum(DSSS)[22],[23]or ultra- wide band (UWB)measurements [78]. II.MEASURING PRINCIPLES AND POSITIONING ALGORITHMS A straightforward approach uses a geometric method to com- It is not easy to model the radio propagation in the indoor pute the intersection points of the circles of TOA.The position environment because of severe multipath,low probability for of the target can also be computed by minimizing the sum of availability of line-of-sight (LOS)path,and specific site param- squares of a nonlinear cost function,i.e.,least-squares algo- eters such as floor layout,moving objects,and numerous reflect- rithm [4],[5].It assumes that the mobile terminal,located at ing surfaces.There is no good model for indoor radio multipath (o,y0),transmits a signal at time to,the N base stations lo- characteristic so far [2].Except using traditional triangulation, cated at(1,),(2,2),...,(N,yN)receive the signal at time positioning algorithms using scene analysis or proximity are t1,t2,...,tN.As a performance measure,the cost function can developed to mitigate the measurement errors.Targeting differ- be formed by ent applications or services,these three algorithms have unique advantages and disadvantages.Hence,using more than one type F(x) aif2(x) (1) of positioning algorithms at the same time could get better i=1 performance. where oi can be chosen to reflect the reliability of the signal received at the measuring unit i,and fi()is given as follows. A.Triangulation f(x)=c(t:-t)-V(x-x)2+(-)2 (2) Triangulation uses the geometric properties of triangles to estimate the target location.It has two derivations:lateration where cis the speed of light,and=(,y,t)T.This function is and angulation.Lateration estimates the position of an object formed for each measuring unit,i=1,...,N,and fi(x)could by measuring its distances from multiple reference points.So,it be made zero with the proper choice of y,and t.The location is also called range measurement techniques.Instead of measur- estimate is determined by minimizing the function F(x). ing the distance directly using received signal strengths(RSS), There are other algorithms for TOA-based indoor location time of arrival (TOA)or time difference of arrival (TDOA)is system such as closest-neighbor (CN)and residual weighting usually measured,and the distance is derived by computing the (RWGH)[5].The CN algorithm estimates the location of the Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply.1068 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 data link is provided in a positioning system, it is possible to send the measurement result from a self-positioning measuring unit to the remote side, and this is called indirect remote posi￾tioning, which is the third system topology. If the measurement result is sent from a remote positioning side to a mobile unit via a wireless data link, this case is named indirect self-positioning, which is the fourth system topology. Our paper is different from the previous survey papers [1] and [2] in several ways. Comparing with the previous survey paper [1], our paper focuses on indoor application of wireless location positioning while [1] just generally describes the lo￾cation systems for ubiquitous computing, without addressing different types of location algorithms, especially for wireless location methods. Also, the paper [2] presents a slight out-of￾date overview of the technologies for wireless indoor location solutions, and does not offer much detail about them and per￾formance benchmarking for indoor wireless positioning system. The publication date of this paper is 2002, and since then, sev￾eral wireless indoor positioning systems or solutions have been developed. In this paper, we present the latest developed systems or solutions, and their location algorithms. Our main purpose is to provide a qualitative overview for them. When possible, we also offer a quantitive comparison of these systems or solutions. This review paper is organized as follows. Section II shows the measuring principles for location sensing and the position￾ing algorithms corresponding to different measuring principles. Performance metrics for indoor positioning techniques are ex￾plained in Section III. Section IV presents current wireless in￾door positioning systems and solutions, and their performance comparison. Finally, Section V concludes the paper and gives possible future directions for research on wireless positioning systems for indoor environments. II. MEASURING PRINCIPLES AND POSITIONING ALGORITHMS It is not easy to model the radio propagation in the indoor environment because of severe multipath, low probability for availability of line-of-sight (LOS) path, and specific site param￾eters such as floor layout, moving objects, and numerous reflect￾ing surfaces. There is no good model for indoor radio multipath characteristic so far [2]. Except using traditional triangulation, positioning algorithms using scene analysis or proximity are developed to mitigate the measurement errors. Targeting differ￾ent applications or services, these three algorithms have unique advantages and disadvantages. Hence, using more than one type of positioning algorithms at the same time could get better performance. A. Triangulation Triangulation uses the geometric properties of triangles to estimate the target location. It has two derivations: lateration and angulation. Lateration estimates the position of an object by measuring its distances from multiple reference points. So, it is also called range measurement techniques. Instead of measur￾ing the distance directly using received signal strengths (RSS), time of arrival (TOA) or time difference of arrival (TDOA) is usually measured, and the distance is derived by computing the Fig. 1. Positioning based on TOA/RTOF measurements. attenuation of the emitted signal strength or by multiplying the radio signal velocity and the travel time. Roundtrip time of flight (RTOF) or received signal phase method is also used for range estimation in some systems. Angulation locates an object by computing angles relative to multiple reference points. In this survey, we focus on the aforementioned measurements in the shorter range, low-antenna, and indoor environment. 1) Lateration Techniques: a) TOA: The distance from the mobile target to the mea￾suring unit is directly proportional to the propagation time. In order to enable 2-D positioning, TOA measurements must be made with respect to signals from at least three reference points, as shown in Fig. 1 [4]. For TOA-based systems, the one-way propagation time is measured, and the distance between mea￾suring unit and signal transmitter is calculated. In general, direct TOA results in two problems. First, all transmitters and receivers in the system have to be precisely synchronized. Second, a times￾tamp must be labeled in the transmitting signal in order for the measuring unit to discern the distance the signal has traveled. TOA can be measured using different signaling techniques such as direct sequence spread-spectrum (DSSS) [22], [23] or ultra￾wide band (UWB) measurements [78]. A straightforward approach uses a geometric method to com￾pute the intersection points of the circles of TOA. The position of the target can also be computed by minimizing the sum of squares of a nonlinear cost function, i.e., least-squares algo￾rithm [4], [5]. It assumes that the mobile terminal, located at (x0, y0), transmits a signal at time t0, the N base stations lo￾cated at (x1, y1), (x2, y2),...,(xN , yN ) receive the signal at time t1, t2,...,tN . As a performance measure, the cost function can be formed by F(x) =
N i=1 α2 i f 2 i (x) (1) where αi can be chosen to reflect the reliability of the signal received at the measuring unit i, and fi(x) is given as follows. fi(x) = c(ti − t) − (xi − x)2 + (yi − y)2 (2) where c is the speed of light, and x = (x, y, t)T . This function is formed for each measuring unit, i = 1, ..., N, and fi(x) could be made zero with the proper choice of x, y, and t. The location estimate is determined by minimizing the function F(x). There are other algorithms for TOA-based indoor location system such as closest-neighbor (CN) and residual weighting (RWGH) [5]. The CN algorithm estimates the location of the Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply.