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