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.