Abstract:
Disclosed is a method and apparatus for determining the new sample points of the location determination system in a wireless environment. In the training phase, after knowing the distribution of the observed radio signal of a location for a target device, the uncertainty of the probability distribution of the received radio signal is analyzed by a location probability distribution model. The radio signal distribution differences are calculated, and the penalties between the location in question and its nearby locations are also calculated, thereby determining whether a location is the candidate of new sample points or the recalibration points. This invention has nothing to do with decision rules and will not undergo the problems of choosing inappropriate decision rules. It also provides a penalty model for generating penalty of error prediction from one location to another location, which can as well easily mitigate the problem on the sample points with the double-role attribute of the border line.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention generally relates to a method for determining the new sample points of a location determination system in a wireless environment. 
       BACKGROUND OF THE INVENTION 
       [0002]    To estimate the location of a target device, a location determination system must estimate a quantity. The quantity must be at least a function of distance. The quantity can be the strength of the signal from the access point (AP). The signal strength will logarithmically decay in accordance with the distance in a free space. The location determination technique is based on the observation of the received radio signal at the target device. In general, the observations at a location form a probabilistic model. The probabilistic model describes the distribution of the received radio signal. 
         [0003]    The distribution of the observation at each sample point (SP) usually approximates the radio signals in the nearby regions. To establish the probabilistic model of each SP, it is necessary to collect radio data at each SP. However, most environments usually use a large amount of sample points; therefore, it is impractical to collect the radio data. In general, physical measurements are taken only at a few SPs, and then a simulation or theoretical calculation is performed to obtain the probabilistic distribution of other SPs. For example, the interpolation or extrapolation is performed on the physical measurements at the SPs to obtain the probabilistic distribution of other SPs. Therefore, the established probabilistic model depends on the “how many” and “where” aspects of the collected radio data. 
         [0004]    The wireless location determining system usually uses two phases for processing. One is a training phase, and the other is a location determining phase. The training phase is an offline phase. During this phase, the system will extract the signatures of the AP at certain cells in the region, collect and analyze the signal pattern, and use a few SPs to estimate the map of the entire space. The map is known as radio map. 
         [0005]    In the location determining phase, the target device compares the received signal strength of the AP with the radio map to determine the optimal match, such as the nearest candidate, to be used as the target device&#39;s estimated location. 
         [0006]    World International Patent Publication WO03/102620 disclosed a method for determining the error estimate of the predicted location of a target device. The method is based on a probabilistic model and collected observations to determine the location of the target device.  FIG. 1  shows the method of determining error estimate. As shown in  FIG. 1 , step  101  is to determine the posterior location probability distribution of the target device at a specific observation. Step  103  is to determine the error distance function between the true location and the target device&#39;s estimated location at the specific observation. Step  105  is to multiply the posterior location probability distribution with the distance function, and add the product to the error estimate. Finally, step  107  is to repeat the above steps in the physical area where the location determining system is operating. 
         [0007]    The error distance estimation is determined by the expectation of the error distance between the sample points and the target device&#39;s estimated location in the physical area where the location determining system is operating. The error distance estimation can be used to determine whether new sample points should be added, or the existing sample points should be recalibrated. The point with the maximum expectation of error distance is the point needed to be sampled or recalibrated. 
         [0008]    The error distance expectation is different for the different observations of the estimated location. Therefore, it is difficult for the error distance estimation to give good, objective, or effective suggestions on the new sample points, unless the optimal decision rule is taken into account. However, if the random mapping decision rule is used, it is not suitable to use the error distance expectation to differentiate the location based on the received signals because the expectation is independent of the selection of sample points based on the observed radio signals. 
         [0009]    Furthermore, when location determining models in different environments are taken into account, the grid size of the sample points of different models used in location estimation can be inconsistent. Therefore, when the error distance estimation is used to recommend the potential locations, the decision rule of the error distance expectation will attempt to choose the sample points with a large grid size. Therefore, the sample points in the region of a small grid size will be ignored. 
         [0010]    If the candidate selection is confined to the same location determining model, the sample points on the border lines will always be neglected in the region of a large grid size, or selected in the region of a small grid size. This is due to the double-role attribute of the sample points on the border lines. 
         [0011]    Reducing the number of actually measured sample points is a key technology difference among the wireless location determining systems. However, if the location determining effect is not good after the training phase, new sample points must be added or calibrated. 
       SUMMARY OF THE INVENTION 
       [0012]    The examples of the present invention may provide a method and an apparatus for determining the new sample points of the location determination system in a wireless environment. In the training phase, when the observation of the radio signals of the target device is known, the observation distribution can be applied to calculate the stability of the radio signals of the location, and the difference from the observation probability distribution of other observation points in order to determine whether a location is the candidate of new sample points. 
         [0013]    After receiving the radio signal of an observation location, the stability of the radio signal can be described by the uncertainty of the probability distribution formed by the signal. The difference between the probability distributions of the radio signals of two locations can be calculated by the average of substituting each observation to a difference function. The difference function can be the absolute value of the subtraction of two values, the logarithmic difference between two values, or other similar functions. When considering the penalty of error prediction at different locations, the weight or penalty function and the difference of signal distribution of two locations can be combined together for consideration. 
         [0014]    In one exemplary embodiment, the method for determining new sample points may comprise the following steps. The first step is to calculate the stability of the received radio signal at a location. The second step is to calculate the radio signal distribution difference and determine the penalties between the said location and its nearby locations. The third step is to calculate the calibration index of the location. The final step is to repeat the above steps for all the locations in the physical area where the system is operating. 
         [0015]    In another exemplary embodiment, the apparatus for determining new sample points may comprise a location probability distribution model indicating a location probability distribution function for the target device in the wireless system, a stability module for measuring the stability of a received radio signal of the target device at a location q, a penalty model for generating a penalty of error prediction between the location q of the received radio signal and its nearby locations, and a calibration module for producing a calibration index I(q) of the location q. 
         [0016]    The present invention does not rely on the decision rules, and does not have problems caused by the wrong choice of decision rules. The present invention also provides the penalty mechanism of the error prediction of moving from one location to another location, and can solve the problem caused by the double-role attribute of the sample points on the border lines. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0017]    The present invention can be understood in more detail by reading the subsequent detailed description in conjunction with the examples and references made to the accompanying drawings, wherein: 
           [0018]      FIG. 1  shows a flowchart of a conventional method for determining the error estimation of a target device; 
           [0019]      FIG. 2  shows four probability distributions corresponding to the radio signals received at four different locations; 
           [0020]      FIG. 3  shows a flowchart of the method for determining new sample points in a wireless location determination system of the present invention; 
           [0021]      FIG. 4  shows an example of using a different λ for a different area on the border line; 
           [0022]      FIG. 5A  shows the probability distributions of four sample points SP 1 -SP 4  during the training phase; 
           [0023]      FIG. 5B  shows the mutual distance between the four sample points SP 1 -SP 4 ; 
           [0024]      FIG. 5C  shows the information entropies of four sample points SP 1 -SP 4 ; 
           [0025]      FIG. 5D  shows the calculated difference of each pair of probability distributions of four sample points SP 1 -SP 4  by using Kullback-Leibler distance; and 
           [0026]      FIG. 5E  shows the calibration indices of four sample points SP 1 -SP 4 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0027]    The present invention is to determine the new sample points of a target device during the training phase of a wireless location determination system. The location determining technique is to use the radio signal observation at a location of the target device as a basis. The observations at a location reported by the target device form a probability distribution, which is a conditional probability. In other words, the conditional probability P(o t =m t |q t =s t ) means the probability that the target device reports the observation m t  at location s t , and q t  and o t  are respectively the location and observation variables of the target device at time t. 
         [0028]    The probability distributions corresponding to the radio signals at different locations are independent with each other. As shown in  FIG. 2 , the four probability distributions PDF 1 -PDF 4 , corresponding to the radio signal received at four different locations, such as four sample points SP 1 -SP 4 , are independent. In general, there are situations in which extensive calibration is needed. For example, unstable regions, say unstable regions with some large obstacles, may be better covered with the sample points having accurate probability distributions. 
         [0029]    In order to locate the potential candidates of new sample points, the technique for determining new sample points of the present invention is based on the intrinsic property of the observation distribution to select new sample points during the training phase. Therefore, the present invention does not rely on the decision rule, and does not have the problems caused by the wrong choice of the decision rule. 
         [0030]    After obtaining the distribution of radio signal o t  at time t at a specific location, the present invention calculates the stability of the radio signal at this location, and the probability distribution difference between the said location and its nearby locations to determine whether this location is a new sample point.  FIG. 3  shows a flowchart of the method for determining new sample points in a wireless location determining system. 
         [0031]    As shown in  FIG. 3 , step  301  is to calculate the stability of the radio signal at a specific location. Step  302  is to calculate the radio signal distribution difference between the said location and its nearby locations, and determine the penalties between the said location and its nearby locations. Step  303  is to calculate the calibration index of this location. Step  304  is to repeat the above steps for all the locations in the physical area where the wireless system is operating. 
         [0032]    After obtaining the calibration index for all the locations, the new calibration points can be recommended based on this calibration index and the environment situation of the physical area where the wireless system is operating. The following describes the detailed operations of steps  301 - 304 . 
         [0033]    In step  301 , the stability of the received radio signal at the location q can be described by the uncertainty of the probability distribution P(O|q) formed by the radio signal at the location q, where O represents the all possible observed outputs of the received radio signal at this location. There are many ways to measure the uncertainty, such as the information entropy by Shannon. The uncertainty is defined as follows: when probability distribution P(O|q) is a discrete probability distribution, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                        
                       
                         ( 
                         
                           O 
                            
                           
                             | 
                           
                            
                           q 
                         
                         ) 
                       
                     
                     = 
                     
                       - 
                       
                         
                           ∑ 
                           
                             
                               o 
                               i 
                             
                             ∈ 
                             O 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             p 
                              
                             
                               ( 
                               
                                 
                                   o 
                                   i 
                                 
                                  
                                 
                                   | 
                                 
                                  
                                 q 
                               
                               ) 
                             
                           
                            
                           
                             log 
                             2 
                           
                            
                           
                             p 
                              
                             
                               ( 
                               
                                 
                                   o 
                                   i 
                                 
                                  
                                 
                                   | 
                                 
                                  
                                 q 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    when probability distribution P(O|q) is a continuos probability distribution, 
         [0000]    
       
         
           
             
               
                 
                   
                     H 
                      
                     
                       ( 
                       
                         O 
                          
                         
                           | 
                         
                          
                         q 
                       
                       ) 
                     
                   
                   = 
                   
                     - 
                     
                       
                         ∫ 
                         o 
                       
                        
                       
                         
                           p 
                            
                           
                             ( 
                             
                               o 
                                
                               
                                 | 
                               
                                
                               q 
                             
                             ) 
                           
                         
                          
                         
                           log 
                           2 
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               o 
                                
                               
                                 | 
                               
                                
                               q 
                             
                             ) 
                           
                         
                          
                         
                           
                              
                             o 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0034]    In step  302 , the difference between the two probability distributions P(O|q) and P(O|{tilde over (q)}) can be obtained by the norms of the two functions. The norm can be the L p -norm, sup norm, or the average of the difference function of each possible observation. The difference function can be the logarithmic difference, or the absolute difference between two probability distributions of each common observation. A preferred difference function is the Kullback-Leibler distance, which is defined as follows: when the probability distribution P(O|q) is a discrete probability distribution, 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                     KL 
                   
                   ( 
                   
                     
                       
                         
                           P 
                            
                           
                             ( 
                             
                               O 
                                
                               
                                 | 
                               
                                
                               q 
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             P 
                              
                             
                               ( 
                               
                                 O 
                                  
                                 
                                   | 
                                 
                                  
                                 
                                   q 
                                   ~ 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             
                               o 
                               i 
                             
                             ∈ 
                             O 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             p 
                              
                             
                               ( 
                               
                                 
                                   o 
                                   i 
                                 
                                 | 
                                 q 
                               
                               ) 
                             
                           
                            
                           
                             
                               log 
                               2 
                             
                             ( 
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       o 
                                       i 
                                     
                                      
                                     
                                       | 
                                     
                                      
                                     q 
                                   
                                   ) 
                                 
                               
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       o 
                                       i 
                                     
                                      
                                     
                                       | 
                                     
                                      
                                     
                                       q 
                                       ~ 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                     ; 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    when the probability distribution P(O|q) is a continuous probability distribution, 
         [0000]    
       
         
           
             
               
                 
                   
                     D 
                     KL 
                   
                   ( 
                   
                     
                       
                         
                           P 
                            
                           
                             ( 
                             
                               O 
                                
                               
                                 | 
                               
                                
                               q 
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             P 
                              
                             
                               ( 
                               
                                 O 
                                  
                                 
                                   | 
                                 
                                  
                                 
                                   q 
                                   ~ 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         
                           ∫ 
                           o 
                         
                          
                         
                           
                             p 
                              
                             
                               ( 
                               
                                 o 
                                  
                                 
                                   | 
                                 
                                  
                                 q 
                               
                               ) 
                             
                           
                            
                           
                             
                               log 
                               2 
                             
                             ( 
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     o 
                                      
                                     
                                       | 
                                     
                                      
                                     q 
                                   
                                   ) 
                                 
                               
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     o 
                                      
                                     
                                       | 
                                     
                                      
                                     
                                       
                                         q 
                                          
                                         
                                             
                                         
                                       
                                       ~ 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                            
                           
                               
                           
                            
                           
                              
                             o 
                           
                         
                       
                     
                     ; 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0035]    The Kullback-Leibler distance is not negative, and is not commutative. In other words, the Kullback-Leibler distance between the two probability distributions P(O|q) and P(O|{tilde over (q)}) is not the same as the Kullback-Leibler distance between the two probability distributions P(O|{tilde over (q)}) and P(O|q). Furthermore, the Kullback-Leibler distance between the two probability distributions P(O|q) and P(O|{tilde over (q)}) is zero if and only if the two probability distributions are identical. It is worth noting that all the possible observations at a specific location have strictly positive probabilities. Therefore, the zero probability will be ruled out in calculating the difference between the two probability distributions P(O|q) and P(O|{tilde over (q)}). 
         [0036]    In step  303 , it is worth noting that the present invention provides a mechanism w(q,{tilde over (q)}) for the penalty of error prediction from one location q to another location {tilde over (q)}. The mechanism for penalty of error prediction can be determined by a key parameter λ and the difference function between two locations q and {tilde over (q)}. The parameter λ can be set by the service provider according to the requirements of the actual environment. An example of the mechanism w(q, {tilde over (q)}) for penalty of error prediction is chosen as follows. w(q, {tilde over (q)})=1−e −λd(q,{tilde over (q)}) , where d(q,{tilde over (q)}) is the distance function between two locations q and {tilde over (q)}, and λcan be selected according to different precision requirements or different regions. 
         [0037]    By using different λs for the different regions on the border line, the problem of the border lines having double-role attribute can be easily solved. 
         [0038]    There are many examples for different error penalties in some areas. For example, some areas are restricted areas for children. Therefore, if the target device is erroneously predicted to be outside the restricted area while the target device is actually within the restricted area, a heavy penalty should be given. By using different λs for different areas near the location q, the requirement for the actual environment can be met.  FIG. 5  shows an example of using different λs for different areas. 
         [0039]    As shown in  FIG. 4 , the location of target device in restricted area  401  is SP, and the neighboring sample points are SP 1 -SP 6 , where SP 1  is outside of the restricted area. If the target device is restricted to the area  401 , and the target device is erroneously predicted to be at location SP 1  while the actual location is at SP, a heavier penalty must be given. In other words, the λ 1  used by the error penalty from SP to SP 1  is heavier than the λ used by the error penalties from SP to SP 2 , SP 3 , SP 4 , SP 5 , or SP 6 . 
         [0040]    In step  303 , calibration index I(q) of a location q is a function of the following three factors: the stability of the received radio signal at a to-be-measured location, the radio signal distribution difference between the to-be-measured location and its nearby locations, and the penalty of error prediction from location q to location {tilde over (q)}. Calibration index I(q) of location q can be calculated as the following equation (5): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       I 
                        
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         
                           
                             H 
                             max 
                           
                           - 
                           
                             H 
                              
                             
                               ( 
                               
                                 O 
                                  
                                 
                                   | 
                                 
                                  
                                 q 
                               
                               ) 
                             
                           
                           + 
                           ɛ 
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             q 
                             ~ 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             w 
                              
                             
                               ( 
                               
                                 q 
                                 , 
                                 
                                   q 
                                   ~ 
                                 
                               
                               ) 
                             
                           
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       D 
                                       KL 
                                     
                                     ( 
                                     
                                       
                                         
                                           P 
                                            
                                           
                                             ( 
                                             
                                               O 
                                                
                                               
                                                 | 
                                               
                                                
                                               q 
                                             
                                             ) 
                                           
                                         
                                          
                                         
                                            
                                           
                                             P 
                                              
                                             
                                               ( 
                                               
                                                 O 
                                                  
                                                 
                                                   | 
                                                 
                                                  
                                                 
                                                   q 
                                                   ~ 
                                                 
                                               
                                               ) 
                                             
                                           
                                           ) 
                                         
                                       
                                       + 
                                     
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       
                                         D 
                                         KL 
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             P 
                                              
                                             
                                               ( 
                                               
                                                 O 
                                                  
                                                 
                                                   | 
                                                 
                                                  
                                                 
                                                   q 
                                                   ~ 
                                                 
                                               
                                               ) 
                                             
                                           
                                            
                                           
                                              
                                             
                                               P 
                                                
                                               
                                                 ( 
                                                 
                                                   O 
                                                    
                                                   
                                                     | 
                                                   
                                                    
                                                   q 
                                                 
                                                 ) 
                                               
                                             
                                             ) 
                                           
                                         
                                         ) 
                                       
                                     
                                     / 
                                     2 
                                   
                                   + 
                                   ɛ 
                                 
                               
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where H max  is the maximum information entropy of the radio signal at location q. The maximum information entropy can be obtained by using uniform distribution, and ε is a very small constant to prevent the denominator from being zero. 
         [0041]    In step  304 , steps  301 - 303  are repeated for all the locations in the physical area where the wireless system is operating to obtain the calibration index for all the locations of the target device. According to the calibration index, one or more candidates for new sample points can be determined. The number of the candidates depends on the actual environment. 
         [0042]    It is worth noting that intrinsic property of the observation distribution is used as a basis in the present invention, therefore, the present invention does not rely on the decision rule, and does not have problems from choosing the wrong decision rule. 
         [0043]    For implementing the method with the operating flow as shown in  FIG. 3 , an apparatus may include a location probability distribution model, a stability module, a penalty model, and a calibration module. The location probability distribution model indicates a location probability distribution function for the target device in the wireless system. The stability module measures the stability of a received radio signal of the target device at a location q. The penalty model for generates a penalty of error prediction between the location q of the received radio signal and its nearby locations. The calibration module for producing a calibration index I(q) of the location q. 
         [0044]    As discussed above, the penalty model may generate the penalty of error prediction through a parameter λ and a difference function between the location q and another location {tilde over (q)} of its nearby locations. The calibration module may produce the calibration index I(q) through the stability of the received radio signal at said location q, a radio signal distribution difference between the location q of the received radio signal and its nearby locations, and the penalty of error prediction from the location q to another location {tilde over (q)} of its nearby locations. The stability module may measure the stability by through an information entropy for said received radio signal at said location q 
         [0045]      FIG. 5A  to  FIG. 5E  show an example of the present invention.  FIG. 5A  shows the four probability distributions of the received radio signal at four sample points SP 1 -SP 4  during the training phase.  FIG. 5B  shows the mutual distance between the four sample points SP 1 -SP 4 , where the unit is 1 meter.  FIG. 5C  shows the entropy at the four sample points SP 1 -SP 4  calculated by equation (1).  FIG. 5D  uses the Kullback-Leibler distance of equation (4) to calculate the difference between each pair of the probability distributions at the four sample points SP 1 -SP 4 . 
         [0046]    As aforementioned, in  FIG. 5D , the difference D KL (P(O|SP 1 ))∥P(O|SP 2 ))=2.2189 is different from the difference D KL (P(O|SP 2 ))∥P(O|SP 1 ))=1.5361. The λ of the mechanism for penalty of error prediction w(q,{tilde over (q)}) is assumed to be  1 .  FIG. 5E  uses equation (5) to calculate the index for the four sample points SP 1 -SP 4 , and the value of ε is set to 10 −5 . 
         [0047]    The result of  FIG. 5E  shows that the calibration index for SP 3  is 7.2237, which is the highest among all the four sample points SP 1 -SP 4 , followed by SP 2  with the index equal to 7.0251. Both are much higher than the sample points SP 1  and SP 4 . In other words, the recommended new sample point is SP 3 , or both SP 3  and SP 2 , depending on the actual environment. 
         [0048]    In summary, during the training phase, the present invention calculates the stability of the received radio signal and the difference between the probability distributions of the radio signal at this location and its nearby locations, to determine whether the location is the new sample point or new calibrated point. The present invention uses the intrinsic property of the observation distribution as a basis, and does not rely on the decision rule. Therefore, the present invention does not have the problem of choosing the wrong decision rule. The present invention also provides a mechanism for penalty of error prediction from a location to another location to solve the problem caused by the sample points on the border lines having double-role attribute. 
         [0049]    Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.