Abstract:
A method of estimating the location of a wireless terminal is disclosed that is ideally suited for use with legacy systems. The illustrative embodiment of the present invention is based on the observation that the signal strength of a signal from a transmitter is different at some locations, and, therefore, the location of a wireless terminal can be estimated by comparing the signal strength it currently observes against a map or database that correlates locations to signal strengths. For example, if a particular radio station is known to be received well at a first location and poorly at a second location, and a given wireless terminal at an unknown location is receiving the radio station poorly, it is more likely that the wireless terminal is at the second location than it is at the first location.

Description:
CROSS-REFERENCE TO RELATED APPLICATION  
       [0001]    The underlying concepts, but not necessarily the nomenclature, of these applications are incorporated by reference:  
         [0002]    (i) U.S. Pat. No. 6,269,246, issued 31 Jul. 2001;  
         [0003]    (ii) U.S. patent application Ser. No. 09/532,418, filed 22 Mar. 2000;  
         [0004]    (iii) U.S. patent application Ser. No. 10/128,128, filed 22 Apr. 2002; and  
         [0005]    (iv) U.S. patent application Ser. No. 10/299,398, filed 18 Nov. 2002. 
     
    
     
       FIELD OF THE INVENTION  
         [0006]    The present invention relates to telecommunications in general, and, more particularly, to a technique for estimating the location of a wireless terminal.  
         BACKGROUND OF THE INVENTION  
         [0007]    [0007]FIG. 1 depicts a map of a geographic region that is serviced by a wireless telecommunications system, which system provides wireless telecommunications service to wireless terminals (e.g., wireless terminal  101 ) within the region. The heart of the telecommunications system is wireless switching center  110 , which might also be known as a mobile switching center (“MSC”) or a mobile telephone switching office (“MTSO”).  
           [0008]    Typically, wireless switching center  111  is connected to a plurality of base stations (e.g., base stations  102 -A through  102 -C), which are dispersed throughout the geographic area serviced by the system. As is well known to those skilled in the art, wireless switching center  111  is responsible for, among other things, establishing and maintaining calls between wireless terminals and between a wireless terminal and a wireline terminal (which is connected to the system via the local and/or long-distance networks and which are not shown in FIG. 1).  
           [0009]    The salient advantage of wireless telecommunications over wireline telecommunications is the mobility that is afforded to the users of the wireless telecommunications system. On the other hand, the salient disadvantage of wireless telecommunications lies in that fact that because the user is mobile, an interested party might not be able to readily ascertain the location of the user.  
           [0010]    Such interested parties might include both the user of the wireless terminal and remote parties. There are a variety of reasons why the user of a wireless terminal might be interested in knowing his or her own location. For example, the user might be interested in telling a remote party where he or she is.  
           [0011]    There are a variety of reasons why a remote party might be interested in knowing the location of the user. For example, the recipient of a 911 emergency call from a wireless terminal might be interested in knowing the location of the wireless terminal so that emergency services vehicles can be dispatched to that location.  
           [0012]    There are many techniques in the prior art for estimating the location of a wireless terminal.  
           [0013]    In accordance with one technique, the location of a wireless terminal is estimated to be at the center of the cell in which the wireless terminal is located. This technique is advantageous in that it does not require that additional hardware be added to the wireless terminal or to the wireless telecommunications system, and this means that the first technique can be inexpensively implemented in legacy systems. The first technique is only accurate, however, to a few kilometers, and, therefore, it is generally not acceptable for applications (e.g., emergency services dispatch, etc.) that require higher accuracy.  
           [0014]    In accordance with a second technique, the location of a wireless terminal is estimated by triangulating the angle of arrival or the time of arrival of the signals transmitted by the wireless terminal to be located at various receivers. This technique is accurate to within a few hundreds of meters and is advantageous in that it can be used with legacy wireless terminals. It is disadvantageous, however, in that it generally requires that hardware be added to the telecommunication system&#39;s base stations, and this is very expensive.  
           [0015]    In accordance with a third technique, the location of a wireless terminal is estimated by a radio navigation unit, such as a Global Positioning System receiver, that is incorporated into the wireless terminal. This technique is accurate to within tens of meters and is advantageous in that it does not require that additional hardware be added to the telecommunication system&#39;s infrastructure. The third technique is disadvantageous, however, in that it cannot be used with legacy wireless terminals that do not comprise a radio navigation unit.  
           [0016]    Therefore, the need exists for a technique for estimating the location of a wireless terminal with higher resolution than the first technique and that can be inexpensively implemented in legacy systems.  
         SUMMARY OF THE INVENTION  
         [0017]    The present invention enables the estimation of the location of a wireless terminal without the addition of hardware to either the wireless terminal or to the telecommunication system&#39;s base stations. Some embodiments of the present invention are, therefore, ideally suited for use with legacy systems.  
           [0018]    The illustrative embodiment of the present invention is based on the observation that the signal strength of a signal from a transmitter is different at some locations, and, therefore, the location of a wireless terminal can be estimated by comparing the signal strength it currently observes against a map or database that correlates locations to signal strengths. For example, if a particular radio station is known to be received well at a first location and poorly at a second location, and a given wireless terminal at an unknown location is receiving the radio station poorly, it is more likely that the wireless terminal is at the second location than it is at the first location.  
           [0019]    When this same principal is applied to multiple transmitters and multiple signals, the location of a wireless terminal can be discriminated among locations where the signal strength of one signal is the same. A simple example illustrates this point. A first radio station, Radio Station A, can be received well at Location 1 and Location 2, but poorly at Location 3 and Location 4, and a second radio station, Radio Station B, can be received well at Location 1 and Location 3, but poorly at Location 2 and Location 4. This information is summarized in the table below and forms the basis for a map or database that correlates location to signal strength.  
                                 TABLE 1                           Illustrative Signal Strength Database (Absolute Reception)                    Radio Station A   Radio Station B                       Location 1   Good Reception   Good Reception           Location 2   Good Reception   Poor Reception           Location 3   Poor Reception   Good Reception           Location 4   Poor Reception   Poor Reception                      
 
           [0020]    If a given wireless terminal at an unknown location can receive Radio Station A poorly and Radio Station B well, it is more likely that the wireless terminal is at Location 3 than it is at either Location 1, 2, or 4.  
           [0021]    Furthermore, the location of a wireless terminal can be estimated with a more-than-acceptable degree of accuracy when the signal strength of each signal at each location is quantified. For example, if a particular radio station is known to be received in one location with a strength of −50 dBm, at a second location with a strength of −53 dBm, and at a third location with a strength of −55 dBm, then the reception of the signal with a strength of −56 dBm suggests that the wireless terminal is more likely at the third location than at either the first or second location.  
           [0022]    These principals largely assume, however, that the equipment used to measure the signal strength of the signals is uniformly calibrated, and this, unfortunately, is not always the case is the real world. Many factors, including the make and model of a wireless terminal, the condition of its antenna, the state of its battery, and whether the terminal is inside a vehicle or not can introduce measurement biases that can cause errors in estimating the location of a wireless terminal.  
           [0023]    The illustrative embodiment ameliorates the effects of these biases by pattern matching not the observed signal strengths to the predicted signal strengths themselves, but by pattern matching the pair-wise differentials of the observed signals strengths to the pair-wise differentials of the predicted signal strengths. A simple example illustrates this nuance. A first radio station, Radio Station A, can be received at −56 dBm at Location 1, −42 dBm at Location 2, −63 dBm at Location 3, and −61 dBm at Location 4, and a second radio station, Radio Station B, can be received at −63 dBm at Location 1, −56 dBm at Location 2, −65 dBm at Location 3, and −52 dBm at Location 4. This information is summarized in the table below and forms the basis for a map or database that correlates location to signal strength.  
                                     TABLE 2                           Illustrative Signal Strength Database (Differential Reception)                    Radio   Radio                   Station A   Station B   Difference                       Location 1   −56 dBm   −63 dBm    −7 dBm           Location 2   −42 dBm   −56 dBm   −14 dBm           Location 3   −63 dBm   −65 dBm    −2 dBm           Location 4   −61 dBm   −52 dBm    9 dBm                      
 
           [0024]    If a given wireless terminal with a broken antenna and at an unknown location receives Radio Station A at −47 dBm and Radio Station B at −61 dBm, then it registers Radio Station A as 14 dBm stronger than Radio Station B. This suggests that the wireless terminal is more likely to be at Location 2 than it is at Location 1, 3, or 4.  
           [0025]    A disadvantage of this approach is that the common bias is eliminated at the expense of (1) doubling the variance of the random measurement noise, and (b) by reducing the number of data points to match by one. Furthermore, the pair-wise subtraction introduces correlation into the relative signal strength measurement errors (i.e., all of the data points to be matched are statistically correlated). This correlation must be accounted for in calculating the likelihood of the measurement report.  
           [0026]    The illustrative embodiment comprises: receiving a first signal-strength measurement for a first signal at the wireless terminal and a second signal-strength measurement for a second signal at the wireless terminal; and estimating the location of the wireless terminal based on the difference of the first signal-strength measurement minus the second signal-strength measurement. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0027]    [0027]FIG. 1 depicts a map of a portion of a wireless telecommunications system in the prior art.  
         [0028]    [0028]FIG. 2 depicts a map of the illustrative embodiment of the present invention.  
         [0029]    [0029]FIG. 3 depicts a block diagram of the salient components of location system  212 .  
         [0030]    [0030]FIG. 4 depicts a broad overview of the salient operations performed by the illustrative embodiment in ascertaining the location of wireless terminal  201  in geographic region  200 .  
         [0031]    [0031]FIG. 5 depicts a flowchart of the salient operations performed in operation  401 .  
         [0032]    [0032]FIG. 6 depicts a map of how geographic region  200  is partitioned into 500 locations in accordance with the illustrative embodiment of the present invention.  
         [0033]    [0033]FIG. 7 a  depicts a graph that shows that the signal-strength of an electromagnetic signal decreases, in general, as a function of the distance from the transmitter and in an environment with no radio frequency obstacles.  
         [0034]    [0034]FIG. 7 b  depicts a graph that shows that the signal-strength of an electromagnetic signal decreases, in general, as a function of the distance from the transmitter and in an environment with two radio frequency obstacles.  
         [0035]    [0035]FIG. 8 depicts a map of the signal-strength measurements of the signal radiated from base station  202 - 1  at each location in geographic region  200 .  
         [0036]    [0036]FIG. 9 depicts a map of the signal-strength measurements of the signal radiated from base station  202 - 2  at each location in geographic region  200 .  
         [0037]    [0037]FIG. 10 depicts a map of the signal-strength measurements of the signal radiated from base station  202 - 3  at each location in geographic region  200 .  
         [0038]    [0038]FIG. 11 depicts a flowchart of the salient operations performed in operation  
         [0039]    [0039]FIG. 12 depicts a flowchart of the salient operations performed in operation  403 . 
     
    
     DETAILED DESCRIPTION  
       [0040]    [0040]FIG. 2 depicts a map of the illustrative embodiment of the present invention, which comprises: wireless switching center  211 , location system  212 , base stations  202 - 1 ,  202 - 2 , and  202 - 3 , and wireless terminal  201 , which are interconnected as shown. The illustrative embodiment provides wireless telecommunications service to most of geographic region  200 , in well-known fashion, and is also capable of estimating the location of wireless terminal  201  within geographic region  200 .  
         [0041]    The illustrative embodiment operates in accordance with the Global System for Mobile Communications (formerly known as the Groupe Speciale Mobile), which is ubiquitously known as “GSM.” After reading this disclosure, however, it will be clear to those skilled in the art how to make and use embodiments of the present invention that operate in accordance with other protocols, such as the Universal Mobile Telephone System (“UMTS”), CDMA-2000, and IS-136 TDMA.  
         [0042]    Wireless switching center  211  is a switching center as is well-known to those skilled in the art in most respects but is different in that it is capable of communicating with location system  212  in the manner described below. After reading this disclosure, it will be clear to those skilled in the art how to make and use wireless switching center  211 .  
         [0043]    Base stations  202 - 1 ,  202 - 2 , and  202 - 3  are well-known to those skilled in the art and communicate with wireless switching center  211  through cables and other equipment (e.g., base station controllers, etc.) that are not shown in FIG. 2. Although the illustrative embodiment comprises three base stations, it will be clear to those skilled in the art how to make and use embodiments of the present invention that comprise any number of base stations.  
         [0044]    Wireless terminal  201  is a standard GSM wireless terminal, as is currently manufactured and used throughout the world. Wireless terminal  201  is equipped, in well-known fashion, with the hardware and software necessary to measure and report to wireless switching center  211  on the signal-strength of the control and traffic channels from base stations  202 - 1 ,  202 - 2 , and  202 - 3 .  
         [0045]    A GSM wireless terminal, such as wireless terminal  201 , is capable of reporting the signal strength of a signal as one of 64 levels between −47 dBm and −110 dBm. Any signal stronger than −47 dBm is reported as −47 dBm, and any signal weaker than −110 dBm is reported as −110 dBm.  
         [0046]    In accordance with the illustrative embodiment of the present invention all of the specific portions of the radio frequency spectrum fall within the same band that wireless terminal  201  uses to communicate with base stations  202 - 1 ,  202 - 2 , and  202 - 3 . In some alternative embodiments of the present invention, however, some or all of the specific portions of the radio frequency spectrum are outside the band that wireless terminal  201  uses to communicate with base stations  202 - 1 ,  202 - 2 , and  202 - 3 . In any case, it will be clear to those skilled in the art how to make and use wireless terminal  201 .  
         [0047]    Location system  212  is a computer system that is capable of estimating the location of wireless terminal  201 , as described in detail below. Although the illustrative embodiment depicts location system  212  as estimating the location of only one wireless terminal, it will be clear to those skilled in the art that location system  212  is capable of estimating the location of any number of wireless terminals serviced by wireless switching center  211 .  
         [0048]    Although location system  212  is depicted in FIG. 2 as a distinct entity from wireless switching center  211 , this is done principally to highlight the distinction between the functions performed by wireless switching center  211  and the functions performed by location system  212 . In other words, it will be clear to those skilled in the art how to make and use embodiments of the present invention in which location system  212  resides within or without wireless switching center  211 .  
         [0049]    Although—again for pedagogical purposes—wireless switching center  211 , location system  212 , and base stations  202 - 1 ,  202 - 2 , and  202 - 3  are depicted in FIG. 2 as being within geographic region  200 , this is not necessarily so, and it will be clear to those skilled in the art how to make and use embodiments of the present invention in which some or all of these pieces of equipment are not within the region of location estimation.  
         [0050]    [0050]FIG. 3 depicts a block diagram of the salient components of location system  212 , which comprises: processor  301  and signal-strength database  302 , which are interconnected as shown.  
         [0051]    Processor  301  is a general-purpose processor as is well-known in the art that is capable of performing the operations described below and with respect to FIG. 4.  
         [0052]    Signal-strength database  302  is a non-volatile memory that stores signal-strength measurements as described below and with respect to FIG. 4.  
         [0053]    Overview—FIG. 4 depicts a broad overview of the salient operations performed by the illustrative embodiment in ascertaining the location of wireless terminal  201  in geographic region  200 . In summary, the tasks performed by the illustrative embodiment can be grouped for ease of understanding into four operations:  
         [0054]    i. the population of signal-strength database  302 ,  
         [0055]    ii. the receipt of signal-strength measurements from wireless terminal  201 ,  
         [0056]    iii. the estimation of the location of wireless terminal  201 , and  
         [0057]    iv. the use of the estimated location of wireless terminal  201 .  
         [0058]    The details of each of these operations are described briefly below and in detail afterwards with respect to FIG. 5 though  12 .  
         [0059]    At operation  401 , signal-strength database  302  is populated with data that associates each location within geographic region  200  with a tuple of signal-strength measurements for that location. Operation  401  is generally complex and potentially expensive, and it is, therefore, preferably performed only occasionally. The details of operation  401  are described in detail below and with respect to FIG. 5.  
         [0060]    At operation  402 , location system  212  receives a tuple of signal-strength measurements from wireless terminal  201 . In accordance with the illustrative embodiment, wireless terminal  201  periodically or sporadically provides a tuple of signal-strength measurements to wireless switching center  211  in well-known fashion, and the measurements are forwarded to location system  212 . The details of operation  402  are described in detail below and with respect to FIG. 11.  
         [0061]    At operation  403 , location system  212  estimates the location of wireless terminal  201  based on:  
         [0062]    (i) the tuple of signal-strength measurements received in operation  402 , and  
         [0063]    (ii) the tuples of signal-strength measurements within signal-strength database  302 . The details of operation  403  are described in detail below and with respect to FIG. 12.  
         [0064]    At operation  404 , location system  212  transmits the location estimated in operation  403  to an entity (not shown) for use in an application. It is well known to those skilled in the art how to use the estimated location of a wireless terminal in an application.  
         [0065]    At this point, each of these four operations is described in detail.  
         [0066]    Population of Signal-Strength Database  302 —FIG. 5 depicts a flowchart of the salient operations performed in operation  401 .  
         [0067]    At task  501 , geographic region  200  is partitioned into a plurality of tessallated locations. Geographic region  200  is rectangular and comprises 5,525 square arc-seconds, which near the equator equals almost 5 square kilometers. After reading this specification, it will be clear to those skilled in the art how to make and use embodiments of the present invention that operate with geographic regions of any size and shape.  
         [0068]    In accordance with the illustrative embodiment of the present invention, geographic region  200  is partitioned into a grid of 221 square locations that are designated location x 1 , y 1  through location x 17 , y 13 . The number of locations into which geographic location  200  is partitioned is arbitrary, subject to the considerations described below. In accordance with the illustrative embodiment, each location is an area of approximately 5 arc-seconds in length by 5 arc-seconds in height. Five arc-seconds near the equator equals approximately 150 meters.  
         [0069]    The size of the locations defines the highest resolution with which the illustrative embodiment can locate a wireless terminal. In other words, the illustrative embodiment can only estimate the location of a wireless terminal to within one location (i.e., 5 by 5 arc-seconds in the illustrative embodiment). If greater resolution is desired, for example 1 arc-second resolution, then geographic region  200  would need to be partitioned into 1 arc-second by 1 arc-second locations. If geographic region  200  were partitioned into 1 arc-second by 1 arc-second locations, there would be 5,525 squares, which is considerably more than the 221 used in the illustrative embodiment. Although the ostensibly higher resolution of 1 arc-second versus 5 arc-seconds is advantageous, there are considerable disadvantages to a large number of locations.  
         [0070]    The number of locations to partition geographic region  200  into is based on three factors. First, as the size of each location goes down, the resolution of the embodiment increases. Second, as the size of each location goes down, the number of locations in a region increases, and, consequently, the computational complexity of operation  403  increases quickly. Third, each location must be large enough so that it has (at least slightly) different signal-strength characteristics than its adjacent areas. This is because the illustrative embodiment might—but won&#39;t necessarily—have difficulty distinguishing between adjacent location that have the same signal-strength characteristics. It will be clear to those skilled in the art how to consider these three factors when deciding how to partition a geographic region.  
         [0071]    At task  502 , the signal-strength measurements for a signal from each base station are determined at each location in geographic region. In accordance with the illustrative embodiment, the signal used from each base station is the control channel because it is broadcast at a constant power and because wireless terminal  201  can distinguish it from every other control channel, if it can decode its BSIC (for GSM networks).  
         [0072]    Because there are three base stations in the illustrative embodiment, each with one control channel, a tuple of three signal-strength measurements at each location must be determined.  
         [0073]    In general, the signal-strength of an electromagnetic signal decreases as a function of the distance from the transmitter, as is depicted in FIG. 7 a , but the topography of the region and the presence of buildings, trees, and other radio-frequency obstacles severely alters this generalization, as is depicted in FIG. 7 b.    
         [0074]    In accordance with the illustrative embodiment, the tuple of three signal-strength measurements for each location are determined through a combination of:  
         [0075]    (i) a theoretical radio-frequency propagation model, and  
         [0076]    (ii) empirical signal-strength measurements.  
         [0077]    It will be clear to those skilled in the art how to accomplish this.  
         [0078]    For example, one well-known modeling for outdoor radio-frequency signal propagation is adapted from the power-law decay model. The power-law decay model assumes that the base station&#39;s antenna is high above the ground and that there is line-of-sight propagation to the wireless terminal. In this case, the mean signal-strength, P, received at the wireless terminal decays in inverse proportion to the square of the distance from the transmitter,  
               P   ∝     1     r   2         ,           (     Eq   .              1     )                               
 
         [0079]    up to some break-point. Beyond that breakpoint, the mean power at the wireless terminal decays in inverse proportion to the fourth power of the distance from the transmitter:  
             P   ∝     1     r   4               (     Eq   .              2     )                               
 
         [0080]    The location of the break-point is determined through empirical signal-strength measurements as the location at which the ground bounce signal interferes with the line-of-sight signal.  
         [0081]    In accordance with another well-known model, the signal-strength measurements at each location are determined by taking empirical measurements at various locations and by interpolating for the locations in between the sampled locations. This method is advantageous in that it does not require many empirical measurements to be made, but it is less accurate than taking measurements at every location.  
         [0082]    It will be clear to those skilled in the art how to determine the signal-strength measurements for each location in the geographic region whether through:  
         [0083]    (i) theoretical radio-frequency propagation models, or  
         [0084]    (ii) empirical signal-strength measurements, or  
         [0085]    (iii) any combination of i and ii.  
         [0086]    In accordance with the illustrative embodiment, FIG. 8 depicts the signal-strength of the signal from base station  202 - 1  (hereinafter referred to as “Signal  1 ”) at each location in geographic region  200 . In general, Signal  1  is stronger near base station  202 - 1  and weaker far away from base station  202 - 1 .  
         [0087]    In accordance with the illustrative embodiment, FIG. 9 depicts the signal-strength of the signal from base station  202 - 2  (hereinafter referred to as “Signal  2 ”) at each location in geographic region  200 . Like Signal  1 , Signal  2  is stronger near base station  202 - 2  and weaker far away from base station  202 - 2 .  
         [0088]    In accordance with the illustrative embodiment, FIG. 10 depicts the signal-strength of the signal from base station  202 - 3  (hereinafter referred to as “Signal  3 ”) at each location in geographic region  200 . Like Signals  1  and  2 , Signal  3  is stronger near base station  202 - 3  and weaker far away from base station  202 - 3 .  
         [0089]    When the signal-strength tuples for each location in geographic region  200  have been determined, they are stored in signal-strength database in a data structure that associates each location with the tuple for that location. The data structure is then stored in signal-strength database  302 .  
                                               TABLE 3                           Signal-Strength Database                Signal-Strength Tuple                    Strength of   Strength of   Strength of           Location   Signal 1   Signal 2   Signal 3                       x 1 , y 1     −115   −115   −115           x 2 , y 1     −115   −115   −111           .   .   .   .           .   .   .   .           .   .   .   .           X 7 , y 7      −45    −51    −49           X 8 , y 7      −46    −52    −55           X 9 , y 7      −50    −49    −62           .   .   .   .           .   .   .   .           .   .   .   .           X 16 , y 13     −115    −96   −115           X 17 , y 13     −115   −105   −115                      
 
         [0090]    Table 3 depicts a portion of an illustrative data structure for associating each location with the signal-strength tuple for that location.  
         [0091]    The three signal-strength measurements in a row of table 1 constitute a “tuple” or non-empty set of ordered elements. For example, the signal-strength tuple at Location x 7 , y 7  are the 3-tuple {−45, −51, −49}. In general, the illustrative embodiment of the present invention estimates the location of a wireless terminal by pattern matching the signal-strength measurements by the wireless terminal at a location against the signal-strength tuples in signal-strength database  302 . This process is described in detail below and with respect to operation  402 .  
         [0092]    From task  502 , control passes to operation  402  in FIG. 4.  
         [0093]    Receipt of Signal-Strength Measurements from Wireless Terminal  201 —FIG. 11 depicts a flowchart of the salient operations performed in operation  402 .  
         [0094]    At task  1101 , wireless switching center  211  determines, in well-known fashion, which signals wireless terminal  201  might or might not be able to receive. In accordance with the illustrative embodiment, wireless switching center  211  determines that wireless terminal  201  might be able to receive Signal  1 , Signal  2 , and Signal  3 .  
         [0095]    At task  1102 , wireless switching center  211  directs wireless terminal  201 , in well-known fashion, to attempt to receive the signals it might be able to receive and to report back a signal-strength value for the strongest (up to) 3 signals that wireless terminal  201  is able to receive and distinguish. In accordance with the illustrative embodiment, wireless switching center  211  directs wireless terminal  211  to monitor Signal  1 , Signal  2 , and Signal  3  and to report on all of these signals.  
         [0096]    At task  1103 , location system  212  receives, via wireless switching center  211 , a report from wireless terminal  201  on the signals that it was directed to monitor in task  602 .  
         [0097]    As described above, wireless terminal  201  is incapable of reporting a signal whose signal-strength is equal to −46 dBm or higher, and, therefore, when wireless terminal  201  attempts to report a signal whose signal-strength is −46 dBm or higher, wireless terminal  201  simply reports a signal-strength value of −47 dBm for that signal. The significance of this insight is that a reported signal-strength value of −47 dBm might not accurately reflect the magnitude of that signal&#39;s strength at that location. To further illustrate the significance of this insight and its effect on the design of the illustrative embodiment, this specification shall describe in detail how two different signal-strength reports are processed by the illustrative embodiment. In accordance with the first report, the signal-strength of all three signals is low enough so that wireless terminal  201  can report the actual strength of the signals. In accordance with the first report, Signal  1 =−98, Signal  2 =−64, and Signal  3 =−51. In accordance with the second report, Signal  1 =−98, Signal  2 =−64, and Signal  3 =−50. How these two types of reports are handled is described below and with respect to FIG. 12.  
         [0098]    It will be clear to those skilled in the art how to make and use embodiments of the present invention that perform operation  402 . From task  603 , control passes to operation  403  in FIG. 4.  
         [0099]    Estimation of the Location of Wireless Terminal  201 —FIG. 12 depicts a flowchart of the salient operations performed in operation  403 . For pedagogical purposes, operation  403  as depicted in FIG. 12 is described three times. First, operation  403  is described in the abstract with a focus on describing its underlying theory. Next, operation  403  is described as it is applied to the first report, and finally, operation  403  is described as it is applied to the second report.  
         [0100]    Estimation in General—Task  1201  begins with 211 (17×13=211) candidate locations that must be considered as the location for wireless terminal  201 , and, therefore, 211 signal-strength tuples (i.e., the 211 tuples in signal-strength database  302 ) that must be processed. Tasks  1202  through  1205  can be computationally intense, and the computational burden increases with the number of candidate locations that must be considered. Therefore, location system  212  attempts, at task  1201 , to reduce the number of candidate locations that must be processed in tasks  1202  through  1205 .  
         [0101]    To reduce the number of candidate locations that must be processed in tasks  1202  through  1205 , location system  212  uses the following observation. When a signal is reported with a maximum signal-strength (i.e., “−47” in the illustrative embodiment), location system  212  can reasonably eliminate from consideration as a candidate location every location where the signal-strength measurement for that signal is below the maximum (minus a factor for measurement errors and systematic bias). In other words, when a signal is reported with a maximum signal-strength, location system  212  can restrict consideration in tasks  1202  through  1205  to those candidate locations where signal-strength database  302  predicts the signal-strength to be greater than or equal to the maximum reportable value (minus a factor for measurement errors and systematic bias). In accordance with the illustrative embodiment, the factor for measurement errors and systematic bias is 3 dBm, and, therefore when a signal is reported with −47, location system  212  can restrict consideration in tasks  1202  through  1205  to those candidate locations where signal-strength database  302  predicts the signal-strength to be greater than or equal to −50 dBm. It will be clear to those skilled in the art how to determine and use other factors for measurement errors and systemic bias.  
         [0102]    At task  1202 , location system  212  computes the signal-strength differentials for those reported values that are not at the maximum signal-strength. In particular, for n reported signals that are not at the maximum signal-strength, n−1 signal-strength differentials are computed where:  
         Δ S   k   =S   k   −S   1   (Eq. 1)  
         [0103]    for k=2, 3, . . . n, wherein ΔS k  is the kth signal-strength differential, S k  is the reported signal-strength of Signal k, and S 1  is the reported signal-strength of Signal  1 . When m of the reported signals is at the maximum signal-strength (i.e., −47 dBm), then  
         n−m−1  (Eq. 2)  
         [0104]    pair-wise differentials for the remaining n−m signals are computed, in well-known fashion. At the end of task  1202 , location system  212  will have computed n−m−1 pair-wise differentials, ΔS 2  through ΔS n−m .  
         [0105]    At task  1203 , location system  212  computes the signal-strength differentials for only those locations that were not eliminated from consideration in task  1201 . Furthermore, location system  212  only computes the signal-strength differentials corresponding to the differentials computed in task  1202 ; the idea, of course, being to ensure that “apples are compared with apples.” In particular, for n reported signals that are not at the maximum signal-strength, n−1 signal-strength differentials are computed where:  
         Δ R   k,x,y   =R   k,x,y   −R   1,x,y   (Eq. 3)  
         [0106]    for k=2, 3, . . . n, wherein ΔR k,x,y  is the kth signal-strength differential for location x,y, R k,x,y  is the signal-strength of Signal k at location x,y in signal-strength database  302 , and R 1,x,y  is the reported signal-strength of Signal  1  at location x,y in signal-strength database  302 .  
         [0107]    At the end of task  1203 , location system  212  will have computed n−m− 1  pair-wise differentials, ΔR 2,x,y  through ΔR n−m,x,y , corresponding to the pair-wise differentials computed in task  1203 , for all the candidate locations.  
         [0108]    At task  1204 , location system  212  compares the signal-strength differentials computed in task  1202 , ΔS 2  through ΔS n−m , to the signal-strength differentials in task  1203 , ΔR 2,x,y  through ΔR n-m,x,y , to generate a probability distribution that indicates the goodness of fit between the signal-strength differentials computed from the values received in operation  402  to the signal-strength differentials computed from the tuples in signal-strength database  302 . To accomplish this, the Euclidean norm at each of the i candidate locations is computed for the signal-strength differentials computed from the values received in operation  402  and each of the signal-strength differentials computed from the tuples in signal-strength database  302 . This is described in Equation 4.  
           v   x,y ={square root}{square root over (Σ 2   n (Δ R   k,x,y   −ΔS   k ) 2 )}  (Eq. 4)  
         [0109]    wherein v x,y  is the Euclidean norm between the signal-strength tuple for location x,y in signal-strength database  302  in comparison to the signal-strength differentials computed from the values received in operation  402 .  
         [0110]    Next, the Euclidean norms computed in Equation 4 are turned into un-normalized probabilities by Equation 5:  
               p     x   ,   y       =               -     v     x   ,   y     2         τ   2                 (     Eq   .              5     )                               
 
         [0111]    where τ 2  represents the amount of uncertainty in both ΔS k  and ΔR k,x,y .  
         [0112]    And finally, the values of P x,y  are normalized to generate the probability distribution for the location of wireless terminal  201  in geographic region  200 .  
         [0113]    At task  1205 , location system  212  estimates the location of wireless terminal  201  based on the probability distribution generated in task  1204 . In accordance with the illustrative embodiment, location system  212  estimates the location of wireless terminal based on the geometric mean of the probability distribution generated in task  1204 . After reading this specification, however, it will be clear to those skilled in the art how to make and use embodiments of the present invention that estimate the location of wireless terminal  201  based on another function of the probability distribution generated in task  1204 , such as the maximum likelihood function.  
         [0114]    From task  1205 , control passes to operation  404  in FIG. 4.  
         [0115]    Estimation as Applied to First Report (Signal  1 =−98, Signal  2 =−64, and Signal  3 =−51)—At task  1201 , location system  212  cannot eliminate any candidate locations from consideration based on the fact that none of the reported signals is at the maximum reportable value minus the factor for measurement errors and systematic bias (i.e., 3 dBm). In other words, location system  212  cannot eliminate any candidate signal from consideration because all of the signals are at −51 dBm or less. Therefore, location system  212  must consider all 221 candidate locations in tasks  1202  through  1205 .  
         [0116]    At task  1202 , location system  212  computes two (2) signal-strength differentials for the first report in which R 1 =Signal  1 =−98, R 2 =Signal  2 =−64, and R 3  Signal  3 =−43. In particular, ΔR 2  and ΔR 3  are computed as depicted in Table 4.  
                             TABLE 4                           Signal-strength Differentials for       Signal 1 = −98, Signal 2 = −64, and Signal 3 = −43            k   ΔR k     R k  − R 1                 2   34   −64 − (−98)       3   47   −51 − (−98)                  
 
         [0117]    At task  1203 , location system  212  computes two (2) signal-strength differentials for each of the 221 locations in signal-strength database  302 , as depicted in Table 5.  
                                 TABLE 5                           Signal-strength Differentials for Each Tuple in Signal-Strength       Database 302                Location   ΔS 2,x,y     ΔS 3,x,y                         x1, y1   −110 − (−110) = 0    −110 − (−110) = 0            x2, y1   −110 − (−110) = 0    −111 − (−110) = −1           x3, y1   −110 − (−110) = 0     −97 − (−110) = 3            .   .   .           .   .   .           .   .   .           x16, y13    −96 − (−110) = 14   −110 − (−110) = 0            x17, y13   −105 − (−110) = 5    −110 − (−110) = 0                       
 
         [0118]    At task  1204 , location system  212  first computes the Euclidean norm between the signal-strength differentials in Table 2 against the signal-strength differentials for each location in Table 3 to produce the norms shown in Table 6.  
                             TABLE 6                           Euclidean Norms for Each Location (First Report)                Location   Vx,y                       x1, y1   64.66           x2, y1   63.81           x3, y1   62.13           .   .           .   .           .   .           x16, y13   58.52           x17, y13   62.18                      
 
         [0119]    Next, the Euclidean norms in Table 6 are converted to unnormalized probabilities, as described above, and then the unnormalized probabilities are normalized, in well-known fashion, to produce the probability distribution of the location of wireless terminal  201  at each of the 211 locations in geographic region  200 .  
         [0120]    Estimation As Applied to Second Report (Signal  1 =−98, Signal  2 =−64, and Signal  3 =−50)—At task  1201 , location system  212  can perfunctorily eliminate most of the candidate locations from consideration because the reported signal-strength of one of the reported signals—Signal  3 =−50 dBm—is greater than the maximum reported value (−47 dBm) minus the factor for measurement errors and systematic bias (3 dBm). In other words, location system  212  can eliminate from consideration any candidate location in which S 3  is not at least −50 dBm. Therefore, location system  212  can restrict consideration in tasks  1202  through  1205  to those locations in signal-strength database  302  in which Signal  3  is predicted to be −50 dBm or greater. As can be seen in FIG. 10, there are only 14 locations (x8, y4; x9, y4; x10, y4; x7, y5; x8, y5; x9, y5; x10, y5; x7, y6; x8, y6; x9, y6; x10, y6; x7, y7; x8, y7; x9, y7) at which Signal  3  is predicted to be −50 dBm or stronger, and, therefore, location system  212  need only perform tasks  1202  through  1205 , in the above-described fashion, on those  14  locations. By reducing the number of candidate locations that need to be processed from 221 to 14, task  1201  has greatly reduced the computational complexity of operation  403 .  
         [0121]    It is to be understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.