1070 IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS,VOL.37.NO.6.NOVEMBER 2007 2)Angulation Techniques (AOA Estimation):In AOA,the location of the desired target can be found by the intersection of several pairs of angle direction lines,each formed by the circular radius from a base station or a beacon station to the mobile target. As shown in Fig.5,AOA methods may use at least two known ● transimitter location reference points (A,B),and two measured angles 1 62 to derive target location the 2-D location of the target P.Estimation of AOA,commonly referred to as direction finding (DF),can be accomplished either Fig.4.Positioning based on signal phase. with directional antennae or with an array of antennae. The advantages of AOA are that a position estimate may be determined with as few as three measuring units for 3-D po- sitioning or two measuring units for 2-D positioning,and that no time synchronization between measuring units is required. The disadvantages include relatively large and complex hard- ware requirement(s),and location estimate degradation as the mobile target moves farther from the measuring units.For ac- curate positioning,the angle measurements need to be accurate, but the high accuracy measurements in wireless networks may Fig.5.Positioning based on AOA measurement. be limited by shadowing,by multipath reflections arriving from misleading directions,or by the directivity of the measuring aperture.Some literatures also call AOA as direction of arrival be ignored if it is small,compared with the transmission time. (DOA).For more detailed discussions on AOA estimation algo- However,for short-range systems,it cannot be ignored.An alter- rithms and their properties,see [11]-[13]. native approach is to use the concept of modulated reflection [9]. which is only suited for short-range systems.An algorithm to B.Scene Analysis measure RTOF of wireless LAN packets is presented in [10] with the result of a measurement error of a few meters.The RF-based scene analysis refers to the type of algorithms that positioning algorithms for TOA can be directly applicable for first collect features(fingerprints)of a scene and then estimate RTOF. the location of an object by matching online measurements with e)Received Signal Phase Method:The received signal the closest a priori location fingerprints.RSS-based location phase method uses the carrier phase (or phase difference)to fingerprinting is commonly used in scene analysis. estimate the range.This method is also called phase of arrival Location fingerprinting refers to techniques that match the (POA)[2].Assuming that all transmitting stations emit pure fingerprint of some characteristic of a signal that is location sinusoidal signals that are of the same frequency f,with zero dependent.There are two stages for location fingerprinting: phase offset,in order to determine the phases of signals re- offline stage and online stage (or run-time stage).During the ceived at a target point,the signal transmitted from each trans- offline stage,a site survey is performed in an environment.The mitter to the receiver needs a finite transit delay.In Fig.4,the location coordinates/labels and respective signal strengths from transmitter stations A up to D are placed at particular locations nearby base stations/measuring units are collected.During the within an imaginary cubic building.The delay is expressed as online stage,a location positioning technique uses the currently a fraction of the signal's wavelength,and is denoted with the observed signal strengths and previously collected information symbol oi =(2TfDi)/c in equation Si(t)=sin(2nft+:), to figure out an estimated location.The main challenge to the where iE(A,B.C.D).and c is the speed of light.As long techniques based on location fingerprinting is that the received as the transmitted signal's wavelength is longer than the di- signal strength could be affected by diffraction,reflection,and agonal of the cubic building,i.e.,0<<2m,we can get the scattering in the propagation indoor environments. range estimation Di =(coi)/(2rf).Then,we can use the same There are at least five location fingerprinting-based position- positioning algorithms using TOA measurement.The receiver ing algorithms using pattern recognition technique so far:prob- may measure phase differences between two signals transmit- abilistic methods,k-nearest-neighbor (NN),neural networks, ted by pairs of stations,and positioning systems are able to support vector machine(SVM),and smallest M-vertex polygon adopt the algorithms using TDOA measurement to locate the (SMP). 1)Probabilistic Methods:One method considers position- target. For an indoor positioning system,it is possible to use ing as a classification problem.Assuming that there are n loca- the signal phase method together with TOA/TDOA or RSS tion candidates L1,L2.L3,...,In,and s is the observed signal method to fine-tune the location positioning.However,the re- strength vector during the online stage,the following decision rule can be obtained: ceived signal phase method has one problem of ambiguous car- rier phase measurements to overcome.It needs an LOS sig- nal path,otherwise it will cause more errors for the indoor Choose Li if P(Lils)>P(Ljls), environment. for i,j=1,2,3,...,n,ji. Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply.1070 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 Fig. 4. Positioning based on signal phase. Fig. 5. Positioning based on AOA measurement. be ignored if it is small, compared with the transmission time. However, for short-range systems, it cannot be ignored. An alter￾native approach is to use the concept of modulated reflection [9], which is only suited for short-range systems. An algorithm to measure RTOF of wireless LAN packets is presented in [10] with the result of a measurement error of a few meters. The positioning algorithms for TOA can be directly applicable for RTOF. e) Received Signal Phase Method: The received signal phase method uses the carrier phase (or phase difference) to estimate the range. This method is also called phase of arrival (POA) [2]. Assuming that all transmitting stations emit pure sinusoidal signals that are of the same frequency f, with zero phase offset, in order to determine the phases of signals re￾ceived at a target point, the signal transmitted from each trans￾mitter to the receiver needs a finite transit delay. In Fig. 4, the transmitter stations A up to D are placed at particular locations within an imaginary cubic building. The delay is expressed as a fraction of the signal’s wavelength, and is denoted with the symbol φi = (2πfDi)/c in equation Si(t) = sin(2πft + φi), where i ∈ (A, B, C, D), and c is the speed of light. As long as the transmitted signal’s wavelength is longer than the di￾agonal of the cubic building, i.e., 0 < φi < 2π, we can get the range estimation Di = (cφi)/(2πf). Then, we can use the same positioning algorithms using TOA measurement. The receiver may measure phase differences between two signals transmit￾ted by pairs of stations, and positioning systems are able to adopt the algorithms using TDOA measurement to locate the target. For an indoor positioning system, it is possible to use the signal phase method together with TOA/TDOA or RSS method to fine-tune the location positioning. However, the re￾ceived signal phase method has one problem of ambiguous car￾rier phase measurements to overcome. It needs an LOS sig￾nal path, otherwise it will cause more errors for the indoor environment. 2) Angulation Techniques (AOA Estimation): In AOA, the location of the desired target can be found by the intersection of several pairs of angle direction lines, each formed by the circular radius from a base station or a beacon station to the mobile target. As shown in Fig. 5, AOA methods may use at least two known reference points (A, B), and two measured angles θ1, θ2 to derive the 2-D location of the target P. Estimation of AOA, commonly referred to as direction finding (DF), can be accomplished either with directional antennae or with an array of antennae. The advantages of AOA are that a position estimate may be determined with as few as three measuring units for 3-D po￾sitioning or two measuring units for 2-D positioning, and that no time synchronization between measuring units is required. The disadvantages include relatively large and complex hard￾ware requirement(s), and location estimate degradation as the mobile target moves farther from the measuring units. For ac￾curate positioning, the angle measurements need to be accurate, but the high accuracy measurements in wireless networks may be limited by shadowing, by multipath reflections arriving from misleading directions, or by the directivity of the measuring aperture. Some literatures also call AOA as direction of arrival (DOA). For more detailed discussions on AOA estimation algo￾rithms and their properties, see [11]–[13]. B. Scene Analysis RF-based scene analysis refers to the type of algorithms that first collect features (fingerprints) of a scene and then estimate the location of an object by matching online measurements with the closest a priori location fingerprints. RSS-based location fingerprinting is commonly used in scene analysis. Location fingerprinting refers to techniques that match the fingerprint of some characteristic of a signal that is location dependent. There are two stages for location fingerprinting: offline stage and online stage (or run-time stage). During the offline stage, a site survey is performed in an environment. The location coordinates/labels and respective signal strengths from nearby base stations/measuring units are collected. During the online stage, a location positioning technique uses the currently observed signal strengths and previously collected information to figure out an estimated location. The main challenge to the techniques based on location fingerprinting is that the received signal strength could be affected by diffraction, reflection, and scattering in the propagation indoor environments. There are at least five location fingerprinting-based position￾ing algorithms using pattern recognition technique so far: prob￾abilistic methods, k-nearest-neighbor (kNN), neural networks, support vector machine (SVM), and smallest M-vertex polygon (SMP). 1) Probabilistic Methods: One method considers position￾ing as a classification problem. Assuming that there are n loca￾tion candidates L1, L2, L3 ,..., Ln , and s is the observed signal strength vector during the online stage, the following decision rule can be obtained: Choose Li if P(Li|s) > P(Lj |s), for i, j = 1, 2, 3, . . . , n, j = i. Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply.