南京大学：《物联网技术导论 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.,0P(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 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.

1072 IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS,VOL.37.NO.6.NOVEMBER 2007 systematic effect/offset of a positioning system.The higher the positioning techniques have to use this incomplete information accuracy,the better the system;however,there is often a tradeoff to compute the location. between accuracy and other characteristics.Some compromise between"suitable"accuracy and other characteristics is needed. E.Scalability B.Precision The scalability character of a system ensures the normal po- sitioning function when the positioning scope gets large.Usu- Accuracy only considers the value of mean distance errors. ally,the positioning performance degrades when the distance However,location precision considers how consistently the sys- between the transmitter and receiver increases.A location sys- tem works,i.e.,it is a measure of the robustness of the posi- tem may need to scale on two axes:geography and density. tioning technique as it reveals the variation in its performance Geographic scale means that the area or volume is covered. over many trials.We also notice that some literatures define the Density means the number of units located per unit geographic location precision as the standard deviation in the location error area/space per time period.As more area/space is covered or or the geometric dilution of precision(GDOP),but we prefer units are crowded in an area/space,wireless signal channels it as the distribution of distance error between the estimated may become congested,more calculation may be needed to location and the true location. perform location positioning,or more communication infras- Usually,the cumulative probability functions(CDF)of the tructure may be required.Another measure of scalability is the distance error is used for measuring the precision of a system. dimensional space of the system.The current system can locate When two positioning techniques are compared,if their accu- the objects in 2-D or 3-D space.Some systems can support both racies are the same,we prefer the system with the CDF graph, 2-D and 3-D spaces. which reaches high probability values faster,because its dis- tance error is concentrated in small values.In practice,CDF is F.Cost described by the percentile format.For example,one system has a location precision of 90%within 2.3 m (the CDF of distance The cost of a positioning system may depend on many factors. error of 2.3 m is 0.9),and 95%within 3.5 m;another one has a Important factors include money,time,space,weight,and en- precision of 50%within 2.3 m and 95%within 3.3 m.We could ergy.The time factor is related to installation and maintenance. choose the former system because of its higher precision. Mobile units may have tight space and weight constraints.Mea- suring unit density is considered to be a space cost.Sometimes, we have to consider some sunk costs.For example,a position- C.Complexity ing system layered over a wireless network may be considered Complexity of a positioning system can be attributed to hard- to have no hardware cost if all the necessary units of that net- ware,software,and operation factors.In this paper,we em- work have already been purchased for other purposes.Energy phasize on software complexity,i.e.,computing complexity of is an important cost factor of a system.Some mobile units(e.g., the positioning algorithm.If the computation of the positioning electronic article surveillance (EAS)tags and passive RFID algorithm is performed on a centralized server side,the position- tags,which are addressed later)are completely energy passive. ing could be calculated quickly due to the powerful processing These units only respond to external fields and,thus,could have capability and the sufficient power supply.If it is carried out on an unlimited lifetime.Other mobile units (e.g.,devices with the mobile unit side,the effects of complexity could be evident. rechargeable battery)have a lifetime of several hours without Most of the mobile units lack strong processing power and long recharging battery life;so,we would prefer positioning algorithms with low complexity.Usually,it is difficult to derive the analytic IV.SURVEY OF SYSTEMS AND SOLUTIONS complexity formula of different positioning techniques;thus, the computing time is considered.Location rate is an important Having identified the common measuring principles,the po- indicator for complexity.The dual of location rate is location sitioning algorithms and the important performance metrics of lag,which is the delay between a mobile target moving to a location positioning systems,we are able to discuss specific sys- new location and reporting the new location of that target by the tems.There are two basic approaches to designing a wireless system. geolocation system.The first approach is to develop a signal- ing system and a network infrastructure of location measuring D.Robustness units focused primarily on wireless location application.The second approach is to use an existing wireless network infras- A positioning technique with high robustness could function tructure to locate a target.The advantage of the first approach normally even when some signals are not available,or when is that the designers are able to control physical specification some of the RSS value or angle character are never seen before. and,consequently,the quality of the location sensing results Sometimes,the signal from a transmitter unit is totally blocked, The tag with the target can be designed as a very small wearable so the signal cannot be obtained from some measuring units.tag or sticker,and the density of the sensor can be adjusted to The only information to estimate the location is the signal from the required positioning accuracy.The advantage of the second other measuring units.Sometimes,some measuring units could approach is that it avoids expensive and time-consuming de- be out of function or damaged in a harsh environment.The ployment of infrastructure.These systems,however,may need Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply

1072 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 systematic effect/offset of a positioning system. The higher the accuracy, the better the system; however, there is often a tradeoff between accuracy and other characteristics. Some compromise between “suitable” accuracy and other characteristics is needed. B. Precision Accuracy only considers the value of mean distance errors. However, location precision considers how consistently the sys￾tem works, i.e., it is a measure of the robustness of the posi￾tioning technique as it reveals the variation in its performance over many trials. We also notice that some literatures define the location precision as the standard deviation in the location error or the geometric dilution of precision (GDOP), but we prefer it as the distribution of distance error between the estimated location and the true location. Usually, the cumulative probability functions (CDF) of the distance error is used for measuring the precision of a system. When two positioning techniques are compared, if their accu￾racies are the same, we prefer the system with the CDF graph, which reaches high probability values faster, because its dis￾tance error is concentrated in small values. In practice, CDF is described by the percentile format. For example, one system has a location precision of 90% within 2.3 m (the CDF of distance error of 2.3 m is 0.9), and 95% within 3.5 m; another one has a precision of 50% within 2.3 m and 95% within 3.3 m. We could choose the former system because of its higher precision. C. Complexity Complexity of a positioning system can be attributed to hard￾ware, software, and operation factors. In this paper, we em￾phasize on software complexity, i.e., computing complexity of the positioning algorithm. If the computation of the positioning algorithm is performed on a centralized server side, the position￾ing could be calculated quickly due to the powerful processing capability and the sufficient power supply. If it is carried out on the mobile unit side, the effects of complexity could be evident. Most of the mobile units lack strong processing power and long battery life; so, we would prefer positioning algorithms with low complexity. Usually, it is difficult to derive the analytic complexity formula of different positioning techniques; thus, the computing time is considered. Location rate is an important indicator for complexity. The dual of location rate is location lag, which is the delay between a mobile target moving to a new location and reporting the new location of that target by the system. D. Robustness A positioning technique with high robustness could function normally even when some signals are not available, or when some of the RSS value or angle character are never seen before. Sometimes, the signal from a transmitter unit is totally blocked, so the signal cannot be obtained from some measuring units. The only information to estimate the location is the signal from other measuring units. Sometimes, some measuring units could be out of function or damaged in a harsh environment. The positioning techniques have to use this incomplete information to compute the location. E. Scalability The scalability character of a system ensures the normal po￾sitioning function when the positioning scope gets large. Usu￾ally, the positioning performance degrades when the distance between the transmitter and receiver increases. A location sys￾tem may need to scale on two axes: geography and density. Geographic scale means that the area or volume is covered. Density means the number of units located per unit geographic area/space per time period. As more area/space is covered or units are crowded in an area/space, wireless signal channels may become congested, more calculation may be needed to perform location positioning, or more communication infras￾tructure may be required. Another measure of scalability is the dimensional space of the system. The current system can locate the objects in 2-D or 3-D space. Some systems can support both 2-D and 3-D spaces. F. Cost The cost of a positioning system may depend on many factors. Important factors include money, time, space, weight, and en￾ergy. The time factor is related to installation and maintenance. Mobile units may have tight space and weight constraints. Mea￾suring unit density is considered to be a space cost. Sometimes, we have to consider some sunk costs. For example, a position￾ing system layered over a wireless network may be considered to have no hardware cost if all the necessary units of that net￾work have already been purchased for other purposes. Energy is an important cost factor of a system. Some mobile units (e.g., electronic article surveillance (EAS) tags and passive RFID tags, which are addressed later) are completely energy passive. These units only respond to external fields and, thus, could have an unlimited lifetime. Other mobile units (e.g., devices with rechargeable battery) have a lifetime of several hours without recharging. IV. SURVEY OF SYSTEMS AND SOLUTIONS Having identified the common measuring principles, the po￾sitioning algorithms and the important performance metrics of location positioning systems, we are able to discuss specific sys￾tems. There are two basic approaches to designing a wireless geolocation system. The first approach is to develop a signal￾ing system and a network infrastructure of location measuring units focused primarily on wireless location application. The second approach is to use an existing wireless network infras￾tructure to locate a target. The advantage of the first approach is that the designers are able to control physical specification and, consequently, the quality of the location sensing results. The tag with the target can be designed as a very small wearable tag or sticker, and the density of the sensor can be adjusted to the required positioning accuracy. The advantage of the second approach is that it avoids expensive and time-consuming de￾ployment of infrastructure. These systems, however, may need 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 1073 tracking sensitivity beyond-158 dBm+.Its performance is not automation/ guiding.tracking. control etc. routing,etc. reported so far. Locata Corporation has invented a new positioning tech- GPS nology called Locata [26],for precision positioning both in- DGPS doors and outside.Part of the"Locata technology"consists of a time-synchronized pseudolite transceiver called a LocataLite.A UWB. Cell-ID GPS TOA network of LocataLites forms a LocataNet,which transmits solutions GPS-like signals that allow single-point positioning using RSS WLAN Bluetooth carrier-phase measurements for a mobile device (a Locata).The AOA TDOA DECT,ZigBee al-strength Home RFpositioning Satellite Navigation And Positioning(SNAP)Group at the Uni- RTOF RF&IR versity of New South Wales has assisted in the development of a TOA Locata and testing of the new technology.The test experiments Resolution demonstrate proof-of-concept for the"Locata technology,"and show that carrier-phase point positioning(without radio modem 0.1meter 10meters data links)is possible with subcentimeter precision [26]. Fig.6.Outline of current wireless-based positioning systems B.RFID to use more intelligent algorithms to compensate for the low RFID is a means of storing and retrieving data through elec- accuracy of the measured metrics.Several types of wireless tromagnetic transmission to an RF compatible integrated circuit technologies are used for indoor location.Fig.6 depicts a rough and is now being seen as a means of enhancing data handling outline of the current wireless-based positioning systems,which processes [27].An RFID system has several basic components, is a modified version of [24,Fig.2].It is beyond the scope of this including a number of RFID readers,RFID tags,and the com- paper to provide a complete overview of systems available till munication between them.The RFID reader is able to read the now.We focus on the wireless positioning systems primarily for data emitted from RFID tags.RFID readers and tags use a de- indoor situations.There are some classification approaches to fined RF and protocol to transmit and receive data.RFID tags surveying the indoor positioning system,such as application en- are categorized as either passive or active. vironments(such as 2-D/3-D positioning in office,warehouse, Passive RFID tags operate without a battery.They are mainly etc.),positioning algorithms,and wireless technologies.In this used to replace the traditional barcode technology and are much paper,we adopt the wireless technologies scheme,also address- lighter,smaller in volume,and less expensive than active tags ing their positioning algorithms and their application situation. They reflect the RF signal transmitted to them from a reader and add information by modulating the reflected signal.However, A.GPS-Based their ranges are very limited.The typical reading range is 1-2 m, and the cost of the readers is relatively high.Passive RFID sys- Global positioning system(GPS),or its differential comple- ment DGPS [25],is one of the most successful positioning tems usually make use of four frequency bands:LF(125 kHz), HF(13.56 MHz).UHF (433,868-915 MHz).and microwave systems in outdoor environments.However,poor coverage of frequency(2.45 GHz,5.8 GHz).20 Bewator5 is a known passive satellite signal for indoor environments decreases its accuracy RFID manufacturer. and makes it unsuitable for indoor location estimation. SnapTrack,a Qualcomm Company,pioneered wireless as- Active RFID tags are small transceivers,which can actively transmit their ID(or other additional data)in reply to an interro- sisted GPS (A-GPS)to overcome the limitations of conventional gation.Frequency ranges used are similar to the passive RFID GPS,and provide GPS indoors technique with an average of case except the low-frequency and high-frequency ranges.The 5-50 m accuracy in most indoor environments.A-GPS technol- advantages of active RFID are with the smaller antennae and in ogy uses a location server with a reference GPS receiver that can the much longer range(can be tens of meters).Active tags are simultaneously detect the same satellites as the wireless handset ideally suited for the identification of high-unit-value products (or mobile station)with a partial GPS receiver,to help the par- moving through a harsh assembly process.WaveTrend Tech- tial GPS receiver find weak GPS signals.The wireless handset nologies5 is one of the famous Active RFID manufacturers.A collects measurements from both the GPS constellation and the well-known location sensing system using the RFID technol- wireless mobile network.These measurements are combined by the location server to produce a position estimation. ogy is SpotON [28].SpotON uses an aggregation algorithm for 3-D location sensing based on radio signal strength analysis Recently,Atmel and U-blox'announced the availability of a SpotON researchers designed and built hardware that serves new GPS weak signal tracking technology,called SuperSense. as object location tags.In the SpotON approach,objects are With this new GPS software,GPS navigation becomes possible located by homogenous sensor nodes without central control in building interiors and deep urban canyons because of its i.e.,Ad Hoc manner.SpotON tags use received RSS value as SnapTrack.http://www.snaptrack.com/ 4Atmel/U-blox.http://www.automotivedesignline.com/products/164901239 2Atmel Corporation.http://www.atmel.com/ 5Bewator Ltd.http://www.bewator.com/uk/ 3U-blox AG.http://www.u-blox.com 6WaveTrend Technologies Ltd.http://www.wavetrend.co.za/ 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 1073 Fig. 6. Outline of current wireless-based positioning systems. to use more intelligent algorithms to compensate for the low accuracy of the measured metrics. Several types of wireless technologies are used for indoor location. Fig. 6 depicts a rough outline of the current wireless-based positioning systems, which is a modified version of [24, Fig. 2]. It is beyond the scope of this paper to provide a complete overview of systems available till now. We focus on the wireless positioning systems primarily for indoor situations. There are some classification approaches to surveying the indoor positioning system, such as application en￾vironments (such as 2-D/3-D positioning in office, warehouse, etc.), positioning algorithms, and wireless technologies. In this paper, we adopt the wireless technologies scheme, also address￾ing their positioning algorithms and their application situation. A. GPS-Based Global positioning system (GPS), or its differential comple￾ment DGPS [25], is one of the most successful positioning systems in outdoor environments. However, poor coverage of satellite signal for indoor environments decreases its accuracy and makes it unsuitable for indoor location estimation. SnapTrack,1 a Qualcomm Company, pioneered wireless as￾sisted GPS (A-GPS) to overcome the limitations of conventional GPS, and provide GPS indoors technique with an average of 5–50 m accuracy in most indoor environments. A-GPS technol￾ogy uses a location server with a reference GPS receiver that can simultaneously detect the same satellites as the wireless handset (or mobile station) with a partial GPS receiver, to help the par￾tial GPS receiver find weak GPS signals. The wireless handset collects measurements from both the GPS constellation and the wireless mobile network. These measurements are combined by the location server to produce a position estimation. Recently, Atmel2 and U-blox3 announced the availability of a new GPS weak signal tracking technology, called SuperSense. With this new GPS software, GPS navigation becomes possible in building interiors and deep urban canyons because of its 1SnapTrack. http://www.snaptrack. com/ 2Atmel Corporation. http://www.atmel. com/ 3U-blox AG. http://www.u-blox. com tracking sensitivity beyond −158 dBm4 . Its performance is not reported so far. Locata Corporation has invented a new positioning tech￾nology called Locata [26], for precision positioning both in￾doors and outside. Part of the “Locata technology” consists of a time-synchronized pseudolite transceiver called a LocataLite. A network of LocataLites forms a LocataNet, which transmits GPS-like signals that allow single-point positioning using carrier-phase measurements for a mobile device (a Locata). The Satellite Navigation And Positioning (SNAP) Group at the Uni￾versity of New South Wales has assisted in the development of a Locata and testing of the new technology. The test experiments demonstrate proof-of-concept for the “Locata technology,” and show that carrier-phase point positioning (without radio modem data links) is possible with subcentimeter precision [26]. B. RFID RFID is a means of storing and retrieving data through elec￾tromagnetic transmission to an RF compatible integrated circuit and is now being seen as a means of enhancing data handling processes [27]. An RFID system has several basic components, including a number of RFID readers, RFID tags, and the com￾munication between them. The RFID reader is able to read the data emitted from RFID tags. RFID readers and tags use a de- fined RF and protocol to transmit and receive data. RFID tags are categorized as either passive or active. Passive RFID tags operate without a battery. They are mainly used to replace the traditional barcode technology and are much lighter, smaller in volume, and less expensive than active tags. They reflect the RF signal transmitted to them from a reader and add information by modulating the reflected signal. However, their ranges are very limited. The typical reading range is 1–2 m, and the cost of the readers is relatively high. Passive RFID sys￾tems usually make use of four frequency bands: LF (125 kHz), HF (13.56 MHz), UHF (433, 868–915 MHz), and microwave frequency (2.45 GHz, 5.8 GHz).20 Bewator5 is a known passive RFID manufacturer. Active RFID tags are small transceivers, which can actively transmit their ID (or other additional data) in reply to an interro￾gation. Frequency ranges used are similar to the passive RFID case except the low-frequency and high-frequency ranges. The advantages of active RFID are with the smaller antennae and in the much longer range (can be tens of meters). Active tags are ideally suited for the identification of high-unit-value products moving through a harsh assembly process. WaveTrend Tech￾nologies6 is one of the famous Active RFID manufacturers. A well-known location sensing system using the RFID technol￾ogy is SpotON [28]. SpotON uses an aggregation algorithm for 3-D location sensing based on radio signal strength analysis. SpotON researchers designed and built hardware that serves as object location tags. In the SpotON approach, objects are located by homogenous sensor nodes without central control, i.e., Ad Hoc manner. SpotON tags use received RSS value as 4Atmel/U-blox. http://www.automotivedesignline.com/products/164901239 5Bewator Ltd. http://www.bewator.com/uk/ 6WaveTrend Technologies Ltd. http://www.wavetrend. co.za/ Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply

1074 IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS,VOL.37.NO.6.NOVEMBER 2007 a sensor measurement for estimating inter-tag distance.They interference because of the differences in signal types and radio exploit the density of tags and correlation of multiple measure- spectrum used.UWB short duration pulses are easy to filter in ments to improve both accuracy and precision.Another system order to determine which signals are correct and which are gen- is called LANDMARC (indoor location sensing using active erated from multipath.At the same time,the signal passes easily RFID)[29].Its prototype uses the RFID reader's operating fre- through walls,equipment and clothing.However metallic and quency with 308 MHz.In order to increase accuracy without liquid materials cause UWB signal interference.Use of more placing more readers,the system employs the idea of having UWB readers and strategic placement of UWB readers could extra fixed location reference tags to help location calibration. overcome this disadvantage.Short-pulse waveforms permit an These reference tags serve as reference points in the system. accurate determination of the precise TOA and,namely,the pre- The LANDMARC approach requires signal strength informa- cise TOF of a burst transmission from a short-pulse transmitter tion from each tag to readers.The kNN method is adopted to to a corresponding receiver [33],[32].UWB location exploits calculate the location of the RFID tags.It is reported that the 50 the characteristics of time synchronization of UWB communi- percentile has an error distance of around 1 m while the maxi-cation to achieve very high indoor location accuracy (20 cm). mum error distances are less than 2 m for LANDMARC system. So it is suitable for high-precision real-time 2-D and 3-D loca- tion.3-D location positioning can be performed by using two C.Cellular-Based different measuring means:TDOA,which is measuring the time difference between a UWB pulse arriving at multiple sensors, A number of systems have used global system of mobile/code division multiple access(GSM/CDMA)mobile cellular network and AOA.The advantage of using both means in conjunction to estimate the location of outdoor mobile clients.However,the is that a location can be determined from just two sensors de- accuracy of the method using cell-ID or enhanced observed time creasing the required sensor density over systems that just use difference(E-OTD)is generally low (in the range of 50-200 m), TDOA.More UWB knowledge and products are given in'and their related references. depending on the cell size.Generally speaking,the accuracy is To date,several UWB precision localization systems have higher in densely covered areas (e.g,urban places)and much been fielded [34].8.9,10 The Ubisense systems is a unidirectional lower in rural environments [30]. Indoor positioning based on mobile cellular network is pos- UWB location platform with a conventional bidirectional time sible if the building is covered by several base stations or one division multiple access (TDMA)control channel.The tags base station with strong RSS received by indoor mobile clients. transmit UWB signals to networked receivers and are located Otsasen et al.presented a GSM-based indoor localization sys- using AOA and TDOA.Ubisense works by creating sensor cells. Each cell requires at least four sensors or readers.Throughout tem in [31].Their key idea that makes accurate GSM-based in- buildings or collections of buildings,an unlimited number of door localization possible is the use of wide signal-strength fin- readers can be networked together in a manner similar to cellular gerprints.The wide fingerprint includes the six strongest GSM phone networks.The readers receive data from the tags,from cells and readings of up to 29 additional GSM channels,most of as far as 150 ft,and send it through the Ubisense Smart Space which are strong enough to be detected but too weak to be used software platform. for efficient communication.The higher dimensionality intro- duced by the additional channel dramatically increases localiza- Microwave frequency,covered by the UWB frequency band, tion accuracy.They present results for experiments conducted is used in Siemens local position radar(LPR)[24].Siemens LPR on signal-strength fingerprints collected from three multifloor is an RTOF system,in which the RTOF between a transponder unit and measuring units/base stations is measured via the fre- buildings using weighted kNN technique.The results show that their indoor localization system can differentiate between floors quency modulated continuous wave (FMCW)radar principle.It was launched for industrial applications like crane and forklift and achieve median within-floor accuracy as low as 2.5 m.The same method could be applied in IS-95 CDMA and 3G mobile positioning.It is applicable only for LOS environment. network. E.WLAN (IEEE 802.11) D.UWB This midrange wireless local area network (WLAN)stan- dard,operating in the 2.4-GHz Industrial,Scientific and Med- UWB is based on sending ultrashort pulses (typically 500 MHz wide).UWB location has the following advantages [32].Un- gross bit rate of 11,54,or 108 Mbps and a range of 50-100 m, like conventional RFID systems,which operate on single bands IEEE 802.11 is currently the dominant local wireless network- of the radio spectrum,UWB transmits a signal over multiple ing standard.It is,therefore,appealing to use an existing WLAN infrastructure for indoor location as well,by adding a location bands of frequencies simultaneously,from 3.1 to 10.6 GHz. UWB signals are also transmitted for a much shorter duration than those used in conventional RFID.UWB tags consume less 7Intel Corporation.http://www.intel.com/technology/comms/uwb/.And power than conventional RF tags and can operate across a broad Ultrawideband planet:http://www.ultrawidebandplanet.com UbiSense Company.http://www.ubisense.net area of the radio spectrum.UWB can be used in close prox- 9Aether Wire Location,Inc.http://www.aetherwire.com imity to other RF signals without causing or suffering from 10Time Domain Company.http://www.timedomain.com Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply

1074 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 a sensor measurement for estimating inter-tag distance. They exploit the density of tags and correlation of multiple measure￾ments to improve both accuracy and precision. Another system is called LANDMARC (indoor location sensing using active RFID) [29]. Its prototype uses the RFID reader’s operating fre￾quency with 308 MHz. In order to increase accuracy without placing more readers, the system employs the idea of having extra fixed location reference tags to help location calibration. These reference tags serve as reference points in the system. The LANDMARC approach requires signal strength informa￾tion from each tag to readers. The kNN method is adopted to calculate the location of the RFID tags. It is reported that the 50 percentile has an error distance of around 1 m while the maxi￾mum error distances are less than 2 m for LANDMARC system. C. Cellular-Based A number of systems have used global system of mobile/code division multiple access (GSM/CDMA) mobile cellular network to estimate the location of outdoor mobile clients. However, the accuracy of the method using cell-ID or enhanced observed time difference (E-OTD) is generally low (in the range of 50–200 m), depending on the cell size. Generally speaking, the accuracy is higher in densely covered areas (e.g, urban places) and much lower in rural environments [30]. Indoor positioning based on mobile cellular network is pos￾sible if the building is covered by several base stations or one base station with strong RSS received by indoor mobile clients. Otsasen et al. presented a GSM-based indoor localization sys￾tem in [31]. Their key idea that makes accurate GSM-based in￾door localization possible is the use of wide signal-strength fin￾gerprints. The wide fingerprint includes the six strongest GSM cells and readings of up to 29 additional GSM channels, most of which are strong enough to be detected but too weak to be used for efficient communication. The higher dimensionality intro￾duced by the additional channel dramatically increases localiza￾tion accuracy. They present results for experiments conducted on signal-strength fingerprints collected from three multifloor buildings using weighted kNN technique. The results show that their indoor localization system can differentiate between floors and achieve median within-floor accuracy as low as 2.5 m. The same method could be applied in IS-95 CDMA and 3G mobile network. D. UWB UWB is based on sending ultrashort pulses (typically 500 MHz wide). UWB location has the following advantages [32]. Un￾like conventional RFID systems, which operate on single bands of the radio spectrum, UWB transmits a signal over multiple bands of frequencies simultaneously, from 3.1 to 10.6 GHz. UWB signals are also transmitted for a much shorter duration than those used in conventional RFID. UWB tags consume less power than conventional RF tags and can operate across a broad area of the radio spectrum. UWB can be used in close prox￾imity to other RF signals without causing or suffering from interference because of the differences in signal types and radio spectrum used. UWB short duration pulses are easy to filter in order to determine which signals are correct and which are gen￾erated from multipath. At the same time, the signal passes easily through walls, equipment and clothing. However metallic and liquid materials cause UWB signal interference. Use of more UWB readers and strategic placement of UWB readers could overcome this disadvantage. Short-pulse waveforms permit an accurate determination of the precise TOA and, namely, the pre￾cise TOF of a burst transmission from a short-pulse transmitter to a corresponding receiver [33], [32]. UWB location exploits the characteristics of time synchronization of UWB communi￾cation to achieve very high indoor location accuracy (20 cm). So it is suitable for high-precision real-time 2-D and 3-D loca￾tion. 3-D location positioning can be performed by using two different measuring means: TDOA, which is measuring the time difference between a UWB pulse arriving at multiple sensors, and AOA. The advantage of using both means in conjunction is that a location can be determined from just two sensors de￾creasing the required sensor density over systems that just use TDOA. More UWB knowledge and products are given in7 and their related references. To date, several UWB precision localization systems have been fielded [34].8,9,10 The Ubisense system8 is a unidirectional UWB location platform with a conventional bidirectional time division multiple access (TDMA) control channel. The tags transmit UWB signals to networked receivers and are located using AOA and TDOA. Ubisense works by creating sensor cells. Each cell requires at least four sensors or readers. Throughout buildings or collections of buildings, an unlimited number of readers can be networked together in a manner similar to cellular phone networks. The readers receive data from the tags, from as far as 150 ft, and send it through the Ubisense Smart Space software platform. Microwave frequency, covered by the UWB frequency band, is used in Siemens local position radar (LPR) [24]. Siemens LPR is an RTOF system, in which the RTOF between a transponder unit and measuring units/base stations is measured via the fre￾quency modulated continuous wave (FMCW) radar principle. It was launched for industrial applications like crane and forklift positioning. It is applicable only for LOS environment. E. WLAN (IEEE 802.11) This midrange wireless local area network (WLAN) stan￾dard, operating in the 2.4-GHz Industrial, Scientific and Med￾ical (ISM) band, has become very popular in public hotspots and enterprise locations during the last few years. With a typical gross bit rate of 11, 54, or 108 Mbps and a range of 50–100 m, IEEE 802.11 is currently the dominant local wireless network￾ing standard. It is, therefore, appealing to use an existing WLAN infrastructure for indoor location as well, by adding a location 7Intel Corporation. http://www.intel.com/technology/comms/uwb/. And Ultrawideband planet: http://www.ultrawidebandplanet.com 8UbiSense Company. http://www.ubisense.net 9Aether Wire & Location, Inc. http://www.aetherwire.com 10Time Domain Company. http://www.timedomain.com 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 1075 server.The accuracy of typical WLAN positioning systems us- sonar,vision,and ultrasound sensors).Robot-based or tracking- ing RSS is approximatly 3 to 30 m,with an update rate in the assisting wireless localization has been studied by many re- range of few seconds. searchers [43].Ladd et al.[44],[45]propose a grid-based Bahl et al.[35]proposed an in-building user location and Bayesian robot localization algorithm that uses the lEEE 802.11 tracking system-RADAR,which adopts the nearest neigh- infrastructure.In the first step of the algorithm,a host uses a bor(s)in signal-space technique,which is the same as the kNN.probabilistic model to compute the likelihood of its location for The authors proposed two kinds of approaches to determine a number of different locations,based on the RSS from nine the user location.The first one depends on the empirical mea- APs.The second step exploits the limited maximum speed of surement of access point signal strength in offline phase.By mobile users to refine the results (of the first step)and reject these experiments,it is reported that user orientations,number solutions with significant change in the location of the mo- of nearest neighbors used,number of data points,and num- bile host.Depending on whether the second step is used or ber of samples in real-time phase would affect the accuracy of not,83%and 77%of the time,hosts can predict their loca- location determination.The second one is signal propagation tion within 1.5 m.Haeberlen et al.[46]presented a practical modeling.Wall attenuation factor(WAF)and floor attenuation robust Bayesian method for topological localization over the factor(FAF)propagation model is used,instead of Rayleigh entirety of an 802.11 network deployed within a multistorey fading model and Rician distribution model,which are used in office building.They have shown that the use of a topologi- outdoor situation.WAF takes into consideration the number of cal model can dramatically reduce the time required to train walls (obstructions).The accuracy of RADAR system is about the localizer,while the resulting accuracy is still sufficient for 2-3 m.In their following work [36],RADAR was enhanced by many location-aware applications.Siddiqi et al.[47]used Monte a Viterbi-like algorithm.Its result is that the 50 percentile of the Carlo localization technique,and obtained similar result to that RADAR system is around 2.37-2.65 m and its 90 percentile is of [44].Kontkanen et al.also introduced a tracking-assistant around 5.93-5.97 m. positioning system [48].This system was used to develop the Horus system [37],[38]offered a joint clustering technique Ekahau system,a commercial wireless location-sensing sys- for location estimation.which uses the probabilistic method tem that combines Bayesian networks,stochastic complexity described previously.Each candidate location coordinate is re- and online competitive learning,to provide positioning infor- garded as a class or category.In order to minimize the distance mation through a central location server.In [49].Xiang et al. error,location Li is chosen while its likelihood is the highest.proposed a model-based signal propagation distribution training The experiment results show that this technique can acquire scheme and a tracking-assistant positioning algorithm in which an accuracy of more than 90%to within 2.1 m.Increasing the a state machine is used to adaptively transfer between tracking number of samples at each sampling location could improve and nontracking status to achieve more accuracy.This system its accuracy because increasing the number of samples would is reported to achieve 2 m accuracy with 90%probability for improve the estimation for means and standard deviations of static position determination.For a walking mobile device,5 m Gaussian distribution.Roos et al.[39]developed a grid-based accuracy with 90%probability is achieved. Bayesian location-sensing system over a small region of their While most systems based on WLAN are using signal office building,achieving localization and tracking to within strength,AeroScout(formerly BlueSoft)[50]uses 802.11-based 1.5 m over 50%of the time.Nibble [40],one of the first sys- TDOA location solution.It requires the same radio signal to be tems of this generation,used a probabilistic approach(based on received at three or more separate points,timed very accurately Bayesian network)to estimate a device's location. (to a few nanoseconds)and processed using the TDOA algo- In [41],Battiti et al.proposed a location determination rithm to determine the location method by using neural-network-based classifier.They adopted There are several other location systems using WLAN [7], multilayer perceptron(MLP)architecture and one-step secant [51-54.For space limitations,we do not discuss their details (OSS)training method.They chose the three-layer architecture here. with three input units,eight hidden layer units,and two out- puts,since this architecture could acquire the lowest training F.Bluetooth (IEEE 802.15) and testing error,and it is less sensitive to the "overfitting"ef- Bluetooth operates in the 2.4-GHz ISM band.Compared fect.They reported that only five samples of signal strengths to WLAN,the gross bit rate is lower(1 Mbps),and the range in different locations are sufficient to get an average distance is shorter (typically 10-15 m).On the other hand,Bluetooth error of 3 m.Increasing the number of training examples helps is a"lighter"standard,highly ubiquitous (embedded in most decrease the average distance error to 1.5 m.The authors in [42] phones,personal digital assistants (PDAs),etc.)and supports compared the neural-networks-based classifier with the near- several other networking services in addition to IP.Bluetooth est neighbor classifier and probabilistic method.It is reported tags are small size transceivers.As any other Bluetooth device, in [42]that neural networks give an error of 1 m with 72% each tag has a unique ID.This ID can be used for locating the probability. Wireless location-sensing is actually a specialized case of Bluetooth tag.[74].The BlueTags tag is a typical Bluetooth a well-studied problem in mobile robotics,that of robot tag.12 localization-determining the position of a mobile robot given 1Ekahau,Inc.Ekahau Positioning Engine 2.0.http://www.ekahau.com/ inputs from the robot's various sensors(possibly including GPS, 12Bluelon Company.www.bluetags.com 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 1075 server. The accuracy of typical WLAN positioning systems us￾ing RSS is approximatly 3 to 30 m, with an update rate in the range of few seconds. Bahl et al. [35] proposed an in-building user location and tracking system—RADAR, which adopts the nearest neigh￾bor(s) in signal-space technique, which is the same as the kNN. The authors proposed two kinds of approaches to determine the user location. The first one depends on the empirical mea￾surement of access point signal strength in offline phase. By these experiments, it is reported that user orientations, number of nearest neighbors used, number of data points, and num￾ber of samples in real-time phase would affect the accuracy of location determination. The second one is signal propagation modeling. Wall attenuation factor (WAF) and floor attenuation factor (FAF) propagation model is used, instead of Rayleigh fading model and Rician distribution model, which are used in outdoor situation. WAF takes into consideration the number of walls (obstructions). The accuracy of RADAR system is about 2–3 m. In their following work [36], RADAR was enhanced by a Viterbi-like algorithm. Its result is that the 50 percentile of the RADAR system is around 2.37–2.65 m and its 90 percentile is around 5.93–5.97 m. Horus system [37], [38] offered a joint clustering technique for location estimation, which uses the probabilistic method described previously. Each candidate location coordinate is re￾garded as a class or category. In order to minimize the distance error, location Li is chosen while its likelihood is the highest. The experiment results show that this technique can acquire an accuracy of more than 90% to within 2.1 m. Increasing the number of samples at each sampling location could improve its accuracy because increasing the number of samples would improve the estimation for means and standard deviations of Gaussian distribution. Roos et al. [39] developed a grid-based Bayesian location-sensing system over a small region of their office building, achieving localization and tracking to within 1.5 m over 50% of the time. Nibble [40], one of the first sys￾tems of this generation, used a probabilistic approach (based on Bayesian network) to estimate a device’s location. In [41], Battiti et al. proposed a location determination method by using neural-network-based classifier. They adopted multilayer perceptron (MLP) architecture and one-step secant (OSS) training method. They chose the three-layer architecture with three input units, eight hidden layer units, and two out￾puts, since this architecture could acquire the lowest training and testing error, and it is less sensitive to the “overfitting” ef￾fect. They reported that only five samples of signal strengths in different locations are sufficient to get an average distance error of 3 m. Increasing the number of training examples helps decrease the average distance error to 1.5 m. The authors in [42] compared the neural-networks-based classifier with the near￾est neighbor classifier and probabilistic method. It is reported in [42] that neural networks give an error of 1 m with 72% probability. Wireless location-sensing is actually a specialized case of a well-studied problem in mobile robotics, that of robot localization—determining the position of a mobile robot given inputs from the robot’s various sensors (possibly including GPS, sonar, vision, and ultrasound sensors). Robot-based or tracking￾assisting wireless localization has been studied by many re￾searchers [43]. Ladd et al. [44], [45] propose a grid-based Bayesian robot localization algorithm that uses the IEEE 802.11 infrastructure. In the first step of the algorithm, a host uses a probabilistic model to compute the likelihood of its location for a number of different locations, based on the RSS from nine APs. The second step exploits the limited maximum speed of mobile users to refine the results (of the first step) and reject solutions with significant change in the location of the mo￾bile host. Depending on whether the second step is used or not, 83% and 77% of the time, hosts can predict their loca￾tion within 1.5 m. Haeberlen et al. [46] presented a practical robust Bayesian method for topological localization over the entirety of an 802.11 network deployed within a multistorey office building. They have shown that the use of a topologi￾cal model can dramatically reduce the time required to train the localizer, while the resulting accuracy is still sufficient for many location-aware applications. Siddiqi et al.[47] used Monte Carlo localization technique, and obtained similar result to that of [44]. Kontkanen et al. also introduced a tracking-assistant positioning system [48]. This system was used to develop the Ekahau system,11 a commercial wireless location-sensing sys￾tem that combines Bayesian networks, stochastic complexity and online competitive learning, to provide positioning infor￾mation through a central location server. In [49], Xiang et al. proposed a model-based signal propagation distribution training scheme and a tracking-assistant positioning algorithm in which a state machine is used to adaptively transfer between tracking and nontracking status to achieve more accuracy. This system is reported to achieve 2 m accuracy with 90% probability for static position determination. For a walking mobile device, 5 m accuracy with 90% probability is achieved. While most systems based on WLAN are using signal strength, AeroScout (formerly BlueSoft) [50] uses 802.11-based TDOA location solution. It requires the same radio signal to be received at three or more separate points, timed very accurately (to a few nanoseconds) and processed using the TDOA algo￾rithm to determine the location. There are several other location systems using WLAN [7], [51]–[54]. For space limitations, we do not discuss their details here. F. Bluetooth (IEEE 802.15) Bluetooth operates in the 2.4-GHz ISM band. Compared to WLAN, the gross bit rate is lower (1 Mbps), and the range is shorter (typically 10–15 m). On the other hand, Bluetooth is a “lighter” standard, highly ubiquitous (embedded in most phones, personal digital assistants (PDAs), etc.) and supports several other networking services in addition to IP. Bluetooth tags are small size transceivers. As any other Bluetooth device, each tag has a unique ID. This ID can be used for locating the Bluetooth tag. [74]. The BlueTags tag is a typical Bluetooth tag.12 11Ekahau, Inc. Ekahau Positioning Engine 2.0. http://www.ekahau.com/ 12Bluelon Company. www.bluetags. com Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply

1076 IEEE TRANSACTIONS ON SYSTEMS.MAN.AND CYBERNETICS-PART C:APPLICATIONS AND REVIEWS,VOL.37.NO.6.NOVEMBER 2007 The Topaz local positioning solution 3is based on Tadlys' that MPS position location information,accurate to within 10 m. Bluetooth infrastructure and accessory products.This modu- is generated in less than I s at mobility speeds of up to 200 mi/h lar positioning solution is made up of three types of elements: 2)Positioning Using Multiple Media:Designing a location positioning server(s),wireless access points,and wireless tags. system for a single environment presents difficulties when the The system's performance makes it suitable for tracking hu- system is applied to other environments.To successfully bridge mans and assets.This system provides roomwise accuracy (or, the differences among different types of sensors and overcome alternatively,2-m spatial accuracy),with 95%reliability.The the limitations of a single type of positioning sensor,hybrid positioning delay is 15-30 s.The performance is further en- systems attempt to compensate for the shortcomings of a single hanced in their new generation Topaz system that integrates technology by using multiple sensor types.HP Labs Smart- infrared and other transducers,with the Bluetooth positioning LOCUS [58]uses synchronized RF and ultrasound differential and communication capabilities. time-of-flight measurements to determine the internodal range Antti et al.present the design and implementation of a Blue- between any two nodes.HP Labs researchers developed sev- tooth Local Positioning Application (BLPA)[55].First,they eral techniques to create relative coordinate geometries with convert the received signal power levels to distance estimates little user intervention.To create an absolute frame of reference according to a simple propagation model,and then,they use the and tie internodal topology to building geometry,a minimum extended kalman filter(EKF)to compute 3-D position estimate of three or four nodes (for 2-D or 3-D localizations)must be on the basis of distance estimates.The accuracy of BLPA is re- preassigned to suitable fixed locations.All the remaining nodes ported to be 3.76 m.A similar work has been done by Hallberg are free to move,and locations are continuously updated and et al.[56]. known to the rest of the system.The well-known cricket indoor location system also uses RF and ultrasound media [59]. G.Others Infrared Radiation (IR)wireless is the use of wireless tech- 1)Proprietary Solutions Using Ultra High Frequency nology in devices or systems that convey data through infrared (UHF):The UHF location systems operate,typically either at radiation.IR is used in wireless personal area network (WPAN) the 433-MHz band (medical telemetry)or at the 868-MHz and since it is a short-range narrow-transmission-angle beam suit- 2.4-GHz ISM band.At such frequency ranges,walls have a able for aiming and selective reception of signals.Most of the moderate attenuation. Infrared Data Association (IrDA)wireless system is based on Some proprietary solutions such as the 3-D-ID system from the LOS mode.Considering the high room accuracy of the IR PinPoint [57]or the TDOA system from WhereNet14 have sim- location [60],and the high availability of the UHF location,it ilar performance as the WLAN systems mentioned later.How- makes sense to combine the two methods into a hybrid location ever,the specially designed hardware and a protocol with longer system.Several other companies like Radiansel6 and Versus17 power down periods allows for minimal power consumption in use a combination of RF and IR signals to perform location po- the mobile.For example,WhereNet,a real-time locating sys- sitioning.Their tags emit IR and RF signals containing a unique tem (RTLS),uses the same 2.4 GHz band as the IEEE 802.11 identifier for each person or asset being tracked.The use of RF and Bluetooth systems,but it uses a dedicated standard pro- allows coarse-grain positioning (e.g.,floor)while the IR signals tocol (ANSI 371.1)optimized for low-power spread-spectrum provide additional resolution(e.g.,room).The EIRIS local posi- location.It works by timing the signals transmitted from tags tioning system uses an IRFID triple technology that combines to a network of receivers.3D-ID is a commercial location sys- IR,RF(UHF),and LF(RF low-frequency transponder)signals. tem produced by PinPoint.Pinpoint uses RTOF to do ranging.It It combines the advantages of each technology,i.e.,the room uses an installed array of antennas at known positions to perform location of IR,the wide range of RF,and the tailored range sen- multilateration.When a mobile tag receives a broadcast,the tag sitivity of LF.However,comparing to RF and IR hybrid system, immediately rebroadcasts it on a different frequency,modulated it could be more costly. with the tag's identifier.A cell controller cycles through the an- 3)Positioning Using Cordless Phone System:Cordless tennas,collecting a set of ranges to the tag.Using a 40 MHz phone system is a modern wireless communication infrastruc- signal,this system achieves a 30-m range,1-m precision,and ture.Schwaighofer et al.[61]used digital enhanced cordless 5-s location update rate. telecommunications (DECT)cellular network to solve the in- Commercial indoor positioning systems using mesh network door positioning problem.They used Gaussian process (GP) techniques such as MeshNetwork positioning system(MPS)15 algorithm to calculate the phone location based on the RSS of are also worth to mention.The MPS technology leverages the phones in the DECT network.They showed that their Gaussian patented position location and determination methods built into process positioning system(GPPS)can provide sufficient ac- MeshNetwork Quadrature Division Multiple Access (QDMA) curacy of 7.5 m when used within a DECT network.They radio technology,which uses direct sequence spread spectrum also used kNN to compare with the GP method,and showed (DSSS)and operates in the ISM 2.4-GHz bands.It is reported that kNN can reach an accuracy of 7 m for DECT cellular network. 13 Topaz local positioning solution.http://www.tadlys.com 16Radianse.Inc.Radianse Indoor Positioning.http://www.radianse.com 14WhereNet Company.http://www.wherenet.com/ 17Versus Technology.http://www.versustech.com 15MPS.http://mesh.nowwireless.com/index.htm 18EIRIS System.http://www.elcomel.com.ar/english/eiris.htm Authorized licensed use limited to:University of Pittsburgh.Downloaded on January 27.2009 at 17:04 from IEEE Xplore.Restrictions apply

1076 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 37, NO. 6, NOVEMBER 2007 The Topaz local positioning solution13is based on Tadlys’ Bluetooth infrastructure and accessory products. This modu￾lar positioning solution is made up of three types of elements: positioning server(s), wireless access points, and wireless tags. The system’s performance makes it suitable for tracking hu￾mans and assets. This system provides roomwise accuracy (or, alternatively, 2-m spatial accuracy), with 95% reliability. The positioning delay is 15–30 s. The performance is further en￾hanced in their new generation Topaz system that integrates infrared and other transducers, with the Bluetooth positioning and communication capabilities. Antti et al. present the design and implementation of a Blue￾tooth Local Positioning Application (BLPA) [55]. First, they convert the received signal power levels to distance estimates according to a simple propagation model, and then, they use the extended kalman filter (EKF) to compute 3-D position estimate on the basis of distance estimates. The accuracy of BLPA is re￾ported to be 3.76 m. A similar work has been done by Hallberg et al. [56]. G. Others 1) Proprietary Solutions Using Ultra High Frequency (UHF): The UHF location systems operate, typically either at the 433-MHz band (medical telemetry) or at the 868-MHz and 2.4-GHz ISM band. At such frequency ranges, walls have a moderate attenuation. Some proprietary solutions such as the 3-D-ID system from PinPoint [57] or the TDOA system from WhereNet14 have sim￾ilar performance as the WLAN systems mentioned later. How￾ever, the specially designed hardware and a protocol with longer power down periods allows for minimal power consumption in the mobile. For example, WhereNet, a real-time locating sys￾tem (RTLS), uses the same 2.4 GHz band as the IEEE 802.11 and Bluetooth systems, but it uses a dedicated standard pro￾tocol (ANSI 371.1) optimized for low-power spread-spectrum location. It works by timing the signals transmitted from tags to a network of receivers. 3D-ID is a commercial location sys￾tem produced by PinPoint. Pinpoint uses RTOF to do ranging. It uses an installed array of antennas at known positions to perform multilateration. When a mobile tag receives a broadcast, the tag immediately rebroadcasts it on a different frequency, modulated with the tag’s identifier. A cell controller cycles through the an￾tennas, collecting a set of ranges to the tag. Using a 40 MHz signal, this system achieves a 30-m range, 1-m precision, and 5-s location update rate. Commercial indoor positioning systems using mesh network techniques such as MeshNetwork positioning system (MPS)15 are also worth to mention. The MPS technology leverages the patented position location and determination methods built into MeshNetwork Quadrature Division Multiple Access (QDMA) radio technology, which uses direct sequence spread spectrum (DSSS) and operates in the ISM 2.4-GHz bands. It is reported 13Topaz local positioning solution. http://www.tadlys.com 14WhereNet Company. http://www.wherenet.com/ 15MPS. http://mesh.nowwireless.com/index.htm that MPS position location information, accurate to within 10 m, is generated in less than 1 s at mobility speeds of up to 200 mi/h. 2) Positioning Using Multiple Media: Designing a location system for a single environment presents difficulties when the system is applied to other environments. To successfully bridge the differences among different types of sensors and overcome the limitations of a single type of positioning sensor, hybrid systems attempt to compensate for the shortcomings of a single technology by using multiple sensor types. HP Labs Smart￾LOCUS [58] uses synchronized RF and ultrasound differential time-of-flight measurements to determine the internodal range between any two nodes. HP Labs researchers developed sev￾eral techniques to create relative coordinate geometries with little user intervention. To create an absolute frame of reference and tie internodal topology to building geometry, a minimum of three or four nodes (for 2-D or 3-D localizations) must be preassigned to suitable fixed locations. All the remaining nodes are free to move, and locations are continuously updated and known to the rest of the system. The well-known cricket indoor location system also uses RF and ultrasound media [59]. Infrared Radiation (IR) wireless is the use of wireless tech￾nology in devices or systems that convey data through infrared radiation. IR is used in wireless personal area network (WPAN) since it is a short-range narrow-transmission-angle beam suit￾able for aiming and selective reception of signals. Most of the Infrared Data Association (IrDA) wireless system is based on the LOS mode. Considering the high room accuracy of the IR location [60], and the high availability of the UHF location, it makes sense to combine the two methods into a hybrid location system. Several other companies like Radianse16 and Versus17 use a combination of RF and IR signals to perform location po￾sitioning. Their tags emit IR and RF signals containing a unique identifier for each person or asset being tracked. The use of RF allows coarse-grain positioning (e.g., floor) while the IR signals provide additional resolution (e.g., room). The EIRIS local posi￾tioning system18 uses an IRFID triple technology that combines IR, RF (UHF), and LF (RF low-frequency transponder) signals. It combines the advantages of each technology, i.e., the room location of IR, the wide range of RF, and the tailored range sen￾sitivity of LF. However, comparing to RF and IR hybrid system, it could be more costly. 3) Positioning Using Cordless Phone System: Cordless phone system is a modern wireless communication infrastruc￾ture. Schwaighofer et al. [61] used digital enhanced cordless telecommunications (DECT) cellular network to solve the in￾door positioning problem. They used Gaussian process (GP) algorithm to calculate the phone location based on the RSS of phones in the DECT network. They showed that their Gaussian process positioning system (GPPS) can provide sufficient ac￾curacy of 7.5 m when used within a DECT network. They also used kNN to compare with the GP method, and showed that kNN can reach an accuracy of 7 m for DECT cellular network. 16Radianse, Inc. Radianse Indoor Positioning. http://www.radianse.com 17Versus Technology. http://www.versustech.com 18EIRIS System. http://www.elcomel.com.ar/english/eiris.htm Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 27, 2009 at 17:04 from IEEE Xplore. Restrictions apply