南京大学：《物联网技术导论 Introduction of Internet of Things》课程教学资源（参考文献）Survey of Wireless Indoor Positioning Techniques and Systems

IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS.VOL.37.NO.6.NOVEMBER 2007 106 Survey of Wireless Indoor Positioning Techniques and Systems Hui Liu,Student Member,IEEE,Houshang Darabi,Member,IEEE,Pat Banerjee,and Jing Liu Abstract-Wireless indoor positioning systems have become very An astonishing growth of wireless systems has been wit- popular in recent years.These systems have been successfully used nessed in recent years.Wireless technologies have entered the in many applications such as asset tracking and inventory man- realms of consumer applications,as well as medical,industrial, agement.This paper provides an overview of the existing wireless indoor positioning solutions and attempts to classify different tech- public safety,logistics,and transport system along with many niques and systems.Three typical location estimation schemes of other applications.Self-organizing sensor networks,location triangulation,scene analysis,and proximity are analyzed.We also sensitive billing,ubiquitous computing,context-dependent in- discuss location fingerprinting in detail since it is used in most cur- formation services,tracking,and guiding are some of the nu- rent system or solutions.We then examine a set of properties by which location systems are evaluated,and apply this evaluation merous possible application areas.Since wireless information method to survey a number of existing systems.Comprehensive access is now widely available,there is a high demand for ac- performance comparisons including accuracy,precision,complex- curate positioning in wireless networks,including indoor and ity,scalability,robustness,and cost are presented. outdoor environments [1,[2].The process of determining a lo- Index Termns-Indoor location sensing,location fingerprinting, cation is called location sensing,geolocation,position location, positioning algorithm,radio frequency(RF),wireless localization. or radiolocation,if it uses wireless technologies. Different applications may require different types of loca- I.INTRODUCTION tion information.The main types discussed in this paper are NDOOR location sensing systems have become very pop- physical location,symbolic location,absolute location,and rel- ular in recent years.These systems provide a new layer of ative location [1].Physical location is expressed in the form of automation called automatic object location detection.Real- coordinates,which identify a point on a 2-D/3-D map.The world applications depending on such automation are many.To widely used coordinate systems are degree/minutes/seconds name a few.one can consider the location detection of products (DMS),degree decimal minutes,and universal transverse mer- stored in a warehouse,location detection of medical personnel cator (UTM)system.Symbolic location expresses a location in or equipment in a hospital,location detection of firemen in a a natural-language way,such as in the office,in the third-floor building on fire,detecting the location of police dogs trained to bedroom,etc.Absolute location uses a shared reference grid for find explosives in a building,and finding tagged maintenance all located objects.A relative location depends on its own frame tools and equipment scattered all over a plant. of reference.Relative location information is usually based on The primary progress in indoor location sensing systems has the proximity to known reference points or base stations. been made during the last ten years.Therefore,both the research Various wireless technologies are used for wireless indoor and commercial products in this area are new,and many people location.These may be classified based on:1)the location po- in academia and industry are currently involved in the research sitioning algorithm,i.e.,the method of determining location. and development of these systems.This survey paper aims to making use of various types of measurement of the signal such provide the reader with a comprehensive review of the wireless as Time Of Flight (TOF),angle,and signal strength;2)the location sensing systems for indoor applications.When possi- physical layer or location sensor infrastructure,i.e.,the wireless ble,the paper compares the related techniques and systems.The technology used to communicate with the mobile devices or authors hope that this paper will act as a guide for researchers, static devices.In general,measurement involves the transmis- users,and developers of these systems,and help them iden- sion and reception of signals between hardware components of tify the potential research problems and future products in this the system.An indoor wireless positioning system consists of at least two separate hardware components:a signal transmitter emerging area. and a measuring unit.The latter usually carries the major part Manuscript received September 27,2005;revised March 26,2006.This of the system“intelligence.” work was supported in part by the National Institute of Standards and There are four different system topologies for positioning sys- Technology/Advanced Technology Program Grant and in part by the Illinois Law Enforcement Alarm System under a Department of Homeland Security tems [3].The first one is the remote positioning system,whose grant.This paper was recommended by Associate Editor P.Samz. signal transmitter is mobile and several fixed measuring units H.Liu is with the Department of Electrical and Computer Engineering,Uni- receive the transmitter's signal.The results from all measuring versity of Illinois at Chicago,Chicago,IL 60612 USA (e-mail:hliu13@uic.edu). H.Darabi and P.Banerjee are with the Department of Mechanical and In- units are collected,and the location of the transmitter is com- dustrial Engineering.University of Illinois at Chicago,Chicago,IL 60607 USA puted in a master station.The second is self-positioning in which (e-mail:hdarabi@uic.edu;banerjee@uic.edu). the measuring unit is mobile.This unit receives the signals of J.Liu is with General Motors,Warren,MI 48090 USA (e-mail:jing.liu@ gm.com). several transmitters in known locations,and has the capability to Digital Object Identifier 10.1109/TSMCC.2007.905750 compute its location based on the measured signals.If a wireless 1094-6977/S25.00©2007EEE Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 1067 Survey of Wireless Indoor Positioning Techniques and Systems Hui Liu, Student Member, IEEE, Houshang Darabi, Member, IEEE, Pat Banerjee, and Jing Liu Abstract—Wireless indoor positioning systems have become very popular in recent years. These systems have been successfully used in many applications such as asset tracking and inventory man￾agement. This paper provides an overview of the existing wireless indoor positioning solutions and attempts to classify different tech￾niques and systems. Three typical location estimation schemes of triangulation, scene analysis, and proximity are analyzed. We also discuss location fingerprinting in detail since it is used in most cur￾rent system or solutions. We then examine a set of properties by which location systems are evaluated, and apply this evaluation method to survey a number of existing systems. Comprehensive performance comparisons including accuracy, precision, complex￾ity, scalability, robustness, and cost are presented. Index Terms—Indoor location sensing, location fingerprinting, positioning algorithm, radio frequency (RF), wireless localization. I. INTRODUCTION I NDOOR location sensing systems have become very pop￾ular in recent years. These systems provide a new layer of automation called automatic object location detection. Real￾world applications depending on such automation are many. To name a few, one can consider the location detection of products stored in a warehouse, location detection of medical personnel or equipment in a hospital, location detection of firemen in a building on fire, detecting the location of police dogs trained to find explosives in a building, and finding tagged maintenance tools and equipment scattered all over a plant. The primary progress in indoor location sensing systems has been made during the last ten years. Therefore, both the research and commercial products in this area are new, and many people in academia and industry are currently involved in the research and development of these systems. This survey paper aims to provide the reader with a comprehensive review of the wireless location sensing systems for indoor applications. When possi￾ble, the paper compares the related techniques and systems. The authors hope that this paper will act as a guide for researchers, users, and developers of these systems, and help them iden￾tify the potential research problems and future products in this emerging area. Manuscript received September 27, 2005; revised March 26, 2006. This work was supported in part by the National Institute of Standards and Technology/Advanced Technology Program Grant and in part by the Illinois Law Enforcement Alarm System under a Department of Homeland Security grant. This paper was recommended by Associate Editor P. Samz. H. Liu is with the Department of Electrical and Computer Engineering, Uni￾versity of Illinois at Chicago, Chicago, IL 60612 USA (e-mail: hliu13@uic.edu). H. Darabi and P. Banerjee are with the Department of Mechanical and In￾dustrial Engineering, University of Illinois at Chicago, Chicago, IL 60607 USA (e-mail: hdarabi@uic.edu; banerjee@uic.edu). J. Liu is with General Motors, Warren, MI 48090 USA (e-mail: jing.liu@ gm.com). Digital Object Identifier 10.1109/TSMCC.2007.905750 An astonishing growth of wireless systems has been wit￾nessed in recent years. Wireless technologies have entered the realms of consumer applications, as well as medical, industrial, public safety, logistics, and transport system along with many other applications. Self-organizing sensor networks, location sensitive billing, ubiquitous computing, context-dependent in￾formation services, tracking, and guiding are some of the nu￾merous possible application areas. Since wireless information access is now widely available, there is a high demand for ac￾curate positioning in wireless networks, including indoor and outdoor environments [1], [2]. The process of determining a lo￾cation is called location sensing, geolocation, position location, or radiolocation, if it uses wireless technologies. Different applications may require different types of loca￾tion information. The main types discussed in this paper are physical location, symbolic location, absolute location, and rel￾ative location [1]. Physical location is expressed in the form of coordinates, which identify a point on a 2-D/3-D map. The widely used coordinate systems are degree/minutes/seconds (DMS), degree decimal minutes, and universal transverse mer￾cator (UTM) system. Symbolic location expresses a location in a natural-language way, such as in the office, in the third-floor bedroom, etc. Absolute location uses a shared reference grid for all located objects. A relative location depends on its own frame of reference. Relative location information is usually based on the proximity to known reference points or base stations. Various wireless technologies are used for wireless indoor location. These may be classified based on: 1) the location po￾sitioning algorithm, i.e., the method of determining location, making use of various types of measurement of the signal such as Time Of Flight (TOF), angle, and signal strength; 2) the physical layer or location sensor infrastructure, i.e., the wireless technology used to communicate with the mobile devices or static devices. In general, measurement involves the transmis￾sion and reception of signals between hardware components of the system. An indoor wireless positioning system consists of at least two separate hardware components: a signal transmitter and a measuring unit. The latter usually carries the major part of the system “intelligence.” There are four different system topologies for positioning sys￾tems [3]. The first one is the remote positioning system, whose signal transmitter is mobile and several fixed measuring units receive the transmitter’s signal. The results from all measuring units are collected, and the location of the transmitter is com￾puted in a master station. The second is self-positioning in which the measuring unit is mobile. This unit receives the signals of several transmitters in known locations, and has the capability to compute its location based on the measured signals. If a wireless 1094-6977/$25.00 © 2007 IEEE 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 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.

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.

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.

LIU:SURVEY OF WIRELESS INDOOR POSITIONING TECHNIQUES AND SYSTEMS 1071 Here,P(is)denotes the probability that the mobile node bias if it is chosen.The output of the system is a two-element is in location Li,given that the received signal vector is s.Also vector or a three-elements vector,which means the 2-D or 3-D assume that P(Li)is the probability that the mobile node is of the estimated location. in location Li.The given decision rule is based on posteriori 4)SVM:SVM is a new and promising technique for data probability.Using Bayes'formula,and assuming that P(Li)= classification and regression.It is a tool for statistical analysis P(Lj)for i,j=1,2,3,...,n we have the following decision and machine learning,and it performs very well in many classifi- rule based on the likelihood that(P(sLi)is the probability that cation and regression applications.SVMs have been used exten- the signal vector s is received,given that the mobile node is sively for a wide range of applications in science,medicine,and located in location Li) engineering with excellent empirical performance [15],[16]. Choose Li if P(s Li)>P(s Lj), The theory of SVM is found in [17]and [18].Support vec- tor classification (SVC)of multiple classes and support vector for i,j=1,2,3,...,n,ji.regression (SVR)have been used successfully in location fin- gerprinting [19],[20]. In addition to the histogram approach,kernel approach is 5)SMP:SMP uses the online RSS values to search for can- used in calculating likelihood.Assuming that the likelihood of each location candidate is a Gaussian distribution,the mean and didate locations in signal space with respect to each signal trans- mitter separately.M-vertex polygons are formed by choosing at standard deviation of each location candidate can be calculated. least one candidate from each transmitter(suppose total of M If the measuring units in the environment are independent,we can calculate the overall likelihood of one location candidate transmitters).Averaging the coordinates of vertices of the small- est polygon (which has the shortest perimeter)gives the location by directly multiplying the likelihoods of all measuring units. estimate.SMP has been used in MultiLoc [74]. Therefore,the likelihood of each location candidate can be cal- culated from observed signal strengths during the online stage, and the estimated location is to be decided by the previous deci- C.Proximity sion rule.However,this is applicable only for discrete location Proximity algorithms provide symbolic relative location in- candidates.Mobile units could be located at any position,not formation.Usually,it relies upon a dense grid of antennas,each just at the discrete points.The estimated 2-D location(,)having a well-known position.When a mobile target is de- given by (5)may interpolate the position coordinates and give tected by a single antenna,it is considered to be collocated with more accurate results.It is a weighted average of the coordinates it.When more than one antenna detects the mobile target,it of all sampling locations is considered to be collocated with the one that receives the strongest signal.This method is relatively simple to implement. (,=∑(P(Ls)(xL4,L). (5) It can be implemented over different types of physical media. i=1 In particular,the systems using infrared radiation (IR)and radio Other probabilistic modeling techniques for location-aware frequency identification(RFID)are often based on this method. and location-sensitive applications in wireless networks may Another example is the cell identification (Cell-ID)or cell of involve pragmatically important issues like calibration,ac- origin (COO)method.This method relies on the fact that mo- tive learning,error estimation,and tracking with history.So bile cellular networks can identify the approximate position of Bayesian-network-based and/or tracking-assisted positioning a mobile handset by knowing which cell site the device is using has been proposed [48]. at a given time.The main benefit of Cell-ID is that it is already 2)kNN:The kNN averaging uses the online RSS to search in use today and can be supported by all mobile handsets. for k closest matches of known locations in signal space from the previously-built database according to root mean square III.PERFORMANCE METRICS errors principle.By averaging these k location candidates with It is not enough to measure the performance of a positioning or without adopting the distances in signal space as weights,an technique only by observing its accuracy.Referring to [21]and estimated location is obtained via weighted kNN or unweighted considering the difference between the indoor and outdoor wire- NN.In this approach,k is the parameter adapted for better less geolocation,we provide the following performance bench- performance. marking for indoor wireless location system:accuracy,preci- 3)Neural Networks:During the offline stage,RSS and the sion,complexity,scalability,robustness,and cost.Thereafter, corresponding location coordinates are adopted as the inputs we make a comparison among different systems and solutions and the targets for the training purpose.After training of neural in Section IV. networks,appropriate weights are obtained.Usually,a multi- layer perceptron(MLP)network with one hidden layer is used for neural-networks-based positioning system.The input vector A.Accuracy of signal strengths is multiplied by the trained input weight ma- Accuracy (or location error)is the most important require- trix,and then added with input layer bias if bias is chosen.The ment of positioning systems.Usually,mean distance error result is put into the transfer function of the hidden layer neuron. is adopted as the performance metric,which is the average The output of this transfer function is multiplied by the trained Euclidean distance between the estimated location and the true hidden layer weight matrix,and then added to the hidden layer location.Accuracy can be considered to be a potential bias,or 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 1071 Here, P(Li|s) denotes the probability that the mobile node is in location Li, given that the received signal vector is s. Also assume that P(Li) is the probability that the mobile node is in location Li. The given decision rule is based on posteriori probability. Using Bayes’ formula, and assuming that P(Li) = P(Lj )fori, j = 1, 2, 3,...,n we have the following decision rule based on the likelihood that (P(s|Li) is the probability that the signal vector s is received, given that the mobile node is located in location Li) Choose Li if P(s|Li) > P(s|Lj), for i, j = 1, 2, 3, . . . , n, j = i. In addition to the histogram approach, kernel approach is used in calculating likelihood. Assuming that the likelihood of each location candidate is a Gaussian distribution, the mean and standard deviation of each location candidate can be calculated. If the measuring units in the environment are independent, we can calculate the overall likelihood of one location candidate by directly multiplying the likelihoods of all measuring units. Therefore, the likelihood of each location candidate can be cal￾culated from observed signal strengths during the online stage, and the estimated location is to be decided by the previous deci￾sion rule. However, this is applicable only for discrete location candidates. Mobile units could be located at any position, not just at the discrete points. The estimated 2-D location (ˆx, yˆ) given by (5) may interpolate the position coordinates and give more accurate results. It is a weighted average of the coordinates of all sampling locations (ˆx, y) = ˆ
n i=1 (P(Li|s)(xLi , yLi )). (5) Other probabilistic modeling techniques for location-aware and location-sensitive applications in wireless networks may involve pragmatically important issues like calibration, ac￾tive learning, error estimation, and tracking with history. So Bayesian-network-based and/or tracking-assisted positioning has been proposed [48]. 2) kNN: The kNN averaging uses the online RSS to search for k closest matches of known locations in signal space from the previously-built database according to root mean square errors principle. By averaging these k location candidates with or without adopting the distances in signal space as weights, an estimated location is obtained via weighted kNN or unweighted kNN. In this approach, k is the parameter adapted for better performance. 3) Neural Networks: During the offline stage, RSS and the corresponding location coordinates are adopted as the inputs and the targets for the training purpose. After training of neural networks, appropriate weights are obtained. Usually, a multi￾layer perceptron (MLP) network with one hidden layer is used for neural-networks-based positioning system. The input vector of signal strengths is multiplied by the trained input weight ma￾trix, and then added with input layer bias if bias is chosen. The result is put into the transfer function of the hidden layer neuron. The output of this transfer function is multiplied by the trained hidden layer weight matrix, and then added to the hidden layer bias if it is chosen. The output of the system is a two-element vector or a three-elements vector, which means the 2-D or 3-D of the estimated location. 4) SVM: SVM is a new and promising technique for data classification and regression. It is a tool for statistical analysis and machine learning, and it performs very well in many classifi- cation and regression applications. SVMs have been used exten￾sively for a wide range of applications in science, medicine, and engineering with excellent empirical performance [15], [16]. The theory of SVM is found in [17] and [18]. Support vec￾tor classification (SVC) of multiple classes and support vector regression (SVR) have been used successfully in location fin￾gerprinting [19], [20]. 5) SMP: SMP uses the online RSS values to search for can￾didate locations in signal space with respect to each signal trans￾mitter separately. M-vertex polygons are formed by choosing at least one candidate from each transmitter (suppose total of M transmitters). Averaging the coordinates of vertices of the small￾est polygon (which has the shortest perimeter) gives the location estimate. SMP has been used in MultiLoc [74]. C. Proximity Proximity algorithms provide symbolic relative location in￾formation. Usually, it relies upon a dense grid of antennas, each having a well-known position. When a mobile target is de￾tected by a single antenna, it is considered to be collocated with it. When more than one antenna detects the mobile target, it is considered to be collocated with the one that receives the strongest signal. This method is relatively simple to implement. It can be implemented over different types of physical media. In particular, the systems using infrared radiation (IR) and radio frequency identification (RFID) are often based on this method. Another example is the cell identification (Cell-ID) or cell of origin (COO) method. This method relies on the fact that mo￾bile cellular networks can identify the approximate position of a mobile handset by knowing which cell site the device is using at a given time. The main benefit of Cell-ID is that it is already in use today and can be supported by all mobile handsets. III. PERFORMANCE METRICS It is not enough to measure the performance of a positioning technique only by observing its accuracy. Referring to [21] and considering the difference between the indoor and outdoor wire￾less geolocation, we provide the following performance bench￾marking for indoor wireless location system: accuracy, preci￾sion, complexity, scalability, robustness, and cost. Thereafter, we make a comparison among different systems and solutions in Section IV. A. Accuracy Accuracy (or location error) is the most important require￾ment of positioning systems. Usually, mean distance error is adopted as the performance metric, which is the average Euclidean distance between the estimated location and the true location. Accuracy can be considered to be a potential bias, or Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply.