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