HK1111767A - Method and apparatus for determining an error estimate in a hybrid position determination system - Google Patents

Description

Method and apparatus for determining error estimates for hybrid positioning systems

The application is a divisional application of the application with the international application date of 24/10/2001, the international application number of PCT/US01/50896, the national application number of 01821346.4 and the title of 'method and device suitable for determining error estimation of hybrid positioning system'.

Background

Technical Field

The present invention relates to positioning. In particular, the present invention relates to a method and apparatus suitable for improving error estimates for positioning measurements made when determining the position of an apparatus.

Description of the Prior Art

A person often wants to know his geographical location. Devices ranging from compasses, maps, sextants, detection devices, etc. have been used to determine the location of a person. Today, we benefit from satellite systems that orbit the earth and provide information to receivers on the earth. Each such receiver may use information provided by the satellites to determine its position. One such system is known as the Global Positioning System (GPS). GPS is a "constellation" of 24 satellites with preferred spacing orbiting around the earth. For most receivers, the position accuracy of a GPS receiver anywhere that the GPS can determine can range from 100 to 10 meters. Each satellite in the GPS satellite constellation transmits a signal encoded with information. This information allows receivers on earth to measure the time of arrival of a received signal at any point in time. Such a measurement of relative arrival time is generally referred to as a "pseudo range" measurement.

GPS is owned and used by the united states department of defense, but is commonly used throughout the world. Briefly, in 10,600 mile orbit above earth, the GPS consists of 21 "regular" satellites and 3 back-up satellites. The satellites are spaced such that at least 4 satellites at any point on the earth are above the horizon. Each satellite includes a computer, an atomic clock, and a radio. Each satellite knows its own orbit and clock, continuously broadcasting its changes in position and time. Once a day, each satellite checks its own detected time and location with the ground station and corrects the information as needed. On the ground, each GPS receiver includes a computer that "triangulates" its own position from the 3 satellite derived bearings to obtain a two-dimensional solution. This result is provided in the form of a geographical location. This location is typically in the form of longitude and latitude. The accuracy of the positioning is typically within 100 meters. If the receiver is also equipped with a display screen displaying a map, the location can be displayed on the map. If a fourth satellite can be received, the receiver/computer can calculate the altitude as well as the geographic location. If the receiver is moving, the receiver may also be able to calculate the speed and direction of the receiver's motion and give an estimated time to reach the specified destination.

Unfortunately, the power level of the received signals from the GPS satellites is extremely low due to the considerable distance between the transmitting satellite and the receiver. Thus, small obstacles in the signal path may block or scatter the signal, making it impossible for the receiver to receive the signal. For example, most GPS receivers have great difficulty receiving signals inside buildings, under dense foliage, in cities where tall buildings block much of the sky, and so on. Thus, other techniques are used instead of or in addition to GPS. Such systems are commonly referred to as "hybrid positioning" systems.

The hybrid positioning system includes a positioning terminal that includes both a GPS receiver and a communication system receiver. In one example of such a hybrid positioning system, the communication system receiver is a cellular telephone receiver. A positioning beacon in a communication system communicates with a hybrid positioning terminal.

When signals from GPS satellites are available, the hybrid positioning terminal receives through a GPS receiver. The hybrid location terminal receives "help information" from the location beacon through the communication system receiver. The aiding information includes information that allows for rapid detection of the frequency and time of the GPS satellite signals. In addition, communication system signals may also be used to determine pseudo ranges to base stations, where one or more of the base stations may be a positioning beacon. The position of the receiver is calculated using the pseudo-ranges to the base stations and the pseudo-ranges to the satellites.

In addition, the positioning receiver in the base station hybrid positioning terminal provides a time reference. In one particular hybrid system, the time reference provided by the communication system to the receiver is GPS time. However, the GPS time provided is offset from the amount of time required for a signal propagating from the positioning beacon to the positioning receiver to communicate the GPS time. The offset may be determined by measuring the propagation delay of a signal from the communication system receiver, to the positioning beacon, and back to the communication system receiver on a "round trip". The offset is equal to half the total Round Trip Delay (RTD). It should be noted, however, that there is an internal delay associated with the reception and retransmission of the signal to locate the beacon that adds to the total Round Trip Delay (RTD). Therefore, in order to get the correct GPS time to pass from the positioning beacon to the positioning terminal, these internal delays must be determined and subtracted from the measured total Round Trip Delay (RTD). This is commonly referred to as "scaling" the positioning beacon. Calibrating a location beacon requires measuring the internal delay of the location beacon. Calibrating a position beacon is a time consuming and difficult task. It would therefore be advantageous to provide a method and apparatus that can determine the location of a hybrid positioning terminal without the need to calibrate a positioning beacon.

That is, the accuracy of the pseudo range measurements made between the positioning terminal and the positioning beacons need not be correct after each positioning beacon in the communication system has been calibrated. This is due to the well-known phenomenon of "multipath". Multipath occurs when a signal takes an indirect path between a transmitter (i.e., a positioning beacon) and a receiver (i.e., a positioning terminal). An indirect path is defined as a path that is longer than the shortest distance between the transmitter and the receiver. The term "multipath" implies that a signal between a transmitter and a receiver will traverse more than one signal path. However, for purposes of this discussion, a signal is considered to be a multipath signal even though the signal takes only one indirect path between the transmitter and the receiver.

Multipath increases the amount of time required for a signal to travel the distance between the positioning beacon and the positioning terminal. This increase is due to the longer distance the signal travels as a result of reflections from obstacles such as buildings. The increase in the amount of time required for the signal to reach the receiver results in an error in the pseudo range measurement. The error in the pseudo range measurements is then converted into an error in the position calculated from the pseudo range measurements.

Multipath can be a problem in GPS signals. However, the effect of multipath in GPS signals is easily accommodated, as the signals may still reach the positioning terminal via a direct path. That is, the signal between the GPS satellite and the positioning terminal may take more than one path. However, one of these paths may be a direct path. Therefore, it is assumed that the direct path is the one that arrives first. Furthermore, the direct path generally has a greater signal strength. Conversely, signals transmitted from a positioning beacon are more likely to take only indirect paths.

Therefore, there is a need to determine the error introduced by multipath. The following description discloses a method and apparatus for determining an estimate of the amount of error that occurs in pseudo range measurements made by a hybrid positioning system.

Summary of The Invention

The disclosed method and apparatus allow the correlation between pseudo range measurement selection parameters and errors to be exploited. A database is established in which the estimated amount of error for a particular pseudo range measurement to the beacon is stored. A cluster (cluster) is defined. Each cluster is associated with a range of values for the selected parameter. The pseudo range measurements are then associated with a particular cluster based on the value of a parameter selected at (or near) the time at which the pseudo range measurements were made. The size of the cluster (i.e., the range of selected parameter values) may be reduced as more estimates of pseudo range measurements are produced. Reducing the size of the clusters reduces the bias of the error estimates due to the correlation between the selected parameters and the error of the pseudo range measurements. The average of the error estimates is used to correct for errors in subsequent pseudo range measurements.

In one embodiment of the disclosed method and apparatus, the position of the terminal that measures the pseudo range to the beacon is a selected parameter. Alternatively, any other relevant parameter such as the power level of the beacon signal may be the selected parameter. Initially, the size of the cluster was quite large, as the database had quite few error estimates in any particular geographic region. However, as the number of error estimates increases, the size of the clusters may decrease, and thus the bias of the error estimates in smaller clusters decreases relative to larger clusters.

According to one embodiment, the error estimate is generated by first calculating what the pseudo range for a particular beacon should be. This calculation is done by determining the current position of the terminal (using it to make pseudo range measurements to the beacon) (first positioning subsystem using accuracy). Assuming that the position of the beacon is known, the pseudo range measurement of the beacon can be conveniently calculated once the position of the terminal is known. A second, less accurate, positioning subsystem is then used to measure the pseudo range from the terminal to the beacon. A difference between the pseudo range calculated by the first, more accurate, positioning subsystem and the pseudo range measurement measured by the second, less accurate, positioning subsystem is determined. It is assumed that this difference is due to an error in the measurements made by the less accurate second positioning subsystem.

Thus, when a first, more accurate positioning subsystem is not available, the database includes information that allows for correction of pseudo range measurements made by a second, less accurate positioning subsystem. The database is self-generated, wherein the information required in the database is retrieved during operation of the terminal according to the availability of the first positioning subsystem with higher accuracy. By using the first positioning subsystem with higher precision, the terminal can detect more points and the clusters in the database are smaller. As a result of the smaller clusters, the bias of the error estimates retained in the database for each cluster will be reduced.

It should be understood that the method and apparatus of the present disclosure may be used with positioning systems other than hybrid positioning systems, as long as there are some other methods to determine the location of the terminal and the method is valid at some time or location, and not at all other times or locations. In this case, the error amount of the pseudo range measurement can be determined using the position of the terminal as a reference by the same method as the positioning of the subsystem with higher accuracy.

According to one embodiment of the disclosed method and apparatus, when the selected parameter is the location of the terminal, an iterative approximation may be used. Assuming that the first, more accurate, positioning subsystem is not efficient and that a sufficient number of initial error estimates have been generated, the iterative approximation uses corrected pseudo range measurements from a relatively large constellation to determine the position of the terminal. Once the terminal position has been so determined, the correlation of the pseudo range can be recalculated from the smaller clusters, assuming a statistically significant number of error estimates have been generated for the smaller clusters.

Brief Description of Drawings

The features, objects, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

FIG. 1 is a schematic diagram of a hybrid positioning system in accordance with the disclosed method and apparatus;

FIG. 2 illustrates the disclosed method with a relationship between the approximate position of the terminal and the expected error in the pseudo range measurements made by the terminal;

FIG. 3 is a schematic diagram of the entire area shown as a single cluster;

FIG. 4 is a schematic illustration of 4 smaller clusters that have been sub-partitioned from one larger cluster;

fig. 5 is a schematic diagram of an example in which some of the clusters in fig. 4 have been combined into new clusters.

Figure 6 shows the process of establishing MSD in the absence of errors with respect to satellite measurements;

FIG. 7 is a simplified block diagram of one embodiment of an iterative process for correcting errors in positioning; and

FIG. 8 is a simplified block diagram of one embodiment of a terminal for implementing the disclosed method.

Detailed description of the preferred embodiments

Fig. 1 is a schematic diagram of a hybrid positioning terminal 100. For the purposes of this disclosure, a hybrid positioning system is defined as a system in which the position of the terminal 105 can be determined by the first positioning subsystem alone or in combination with the second subsystem. Preferably, the first positioning subsystem is capable of determining the position of the terminal 105 "independently" of the second subsystem. In this context, the term "independent of the second subsystem" means that the first subsystem may be used to determine the location of the terminal when some or all of the components of the second subsystem are not available. However, in accordance with one embodiment of the disclosed method and apparatus, components of the second subsystem may be required components of the first subsystem. It should be noted that the second subsystem may or may not be capable of location determination without the need to use components or informational conditions of the first subsystem.

Furthermore, in a hybrid positioning system according to the disclosed method and apparatus, at least one "parameter" is related to an error magnitude of a positioning measurement of one of the positioning subsystems. For the purposes of this disclosure, a parameter is any variable that is related to the magnitude of error in one of the positioning subsystem positioning measurements. For example, the parameters of the positioning terminal 105 may be: (1) the location of the location terminal 105; (2) the amount of power in the positioning signal received by the positioning terminal 105; (3) the number of base stations in the geographic area in which the positioning terminal 105 is currently located; (4) the type of building in the geographic area in which the positioning terminal 105 is currently located; (5) the density of structures in the geographic area in which the positioning terminal 105 is currently located, and so on. Each of these variables affects the accuracy of measurements made by the positioning terminals in the terrestrial positioning system and, therefore, is considered a parameter of the positioning terminal 105. However, the parameter related to the error magnitude of the measurement made by the second subsystem is preferably uncorrelated (or less correlated) with the error magnitude of the measurement made by the first positioning subsystem.

In one example of a hybrid positioning system that includes two subsystems, both subsystems include a set of transmitters. The transmitter of each subsystem transmits a positioning signal. In such a hybrid system, it is not necessary to obtain transmissions from both subsystems simultaneously. In the embodiment shown in fig. 1, 4 satellites 101, 3 positioning beacons 103, and 1 positioning terminal 105 are shown. Satellite 101 is the first of two types of positioning signal transmitters associated with the first subsystem.

The satellite 101 provides signals that the terminal 105 can receive. Given that signals received from a sufficient number of satellite signals can be decoded, the received signals enable the terminal to determine the location of the terminal 105 without receiving positioning signals from any of the beacons 103. However, in some embodiments of the disclosed method and apparatus, the terminal 105 may need to communicate with the beacon 103 as an aid to acquisition and processing. Regardless of whether acquisition assistance is required, once a sufficient number of satellites 101 are acquired, the information provided by the satellites 101 is sufficient to calculate the position of the terminal 105.

The beacon 103 is part of the second of the two positioning systems. Like the satellite 101, the beacon 103 provides a signal that the terminal 105 can receive. According to one embodiment of the disclosed method and apparatus, these signals enable the terminal 105 to determine its own position without receiving positioning signals from any of the satellites 101. However, in another embodiment, the second subsystem requires information provided by the transmitter of at least one of the first subsystems in order to determine the location of the terminal 105. Upon receiving information from each of the required transmitters, the terminal 105 can make a determination of position, either alone or with acquisition and processing assistance from one of the beacons 103. Alternatively, the location of the terminal 105 may be determined by a remote device (not shown) that is remote from the terminal 105. In this case, the terminal 105 transmits any information needed to determine the location of the terminal 105 to the remote device. In one embodiment of the disclosed method and apparatus, the remote apparatus is one of the beacons 103 or a subsystem 104 in one of the beacons 103. The remote device is shown in fig. 1 as "selectable" to emphasize the fact that the remote device may be located inside the beacon 103 or outside the beacon 103.

Those skilled in the art will appreciate that there may be more or fewer satellites 101 or beacons 103 than those shown in fig. 1, and there may be more than one terminal 105. In one embodiment of hybrid positioning system 100, satellites 101 are GPS satellites. However, in another embodiment of the hybrid positioning system 100, the satellites 101 may be any other type of transmitter that is capable of performing relatively independent and relatively accurate positioning. For example, a terrestrial positioning system (such as LORAIN) capable of providing accurate positioning may be used instead of satellites.

In one embodiment of hybrid positioning system 100, beacon 103 is a cellular base station that includes (1) a Base Transceiver Subsystem (BTS); (2) a Base Station Controller (BSC); and (3) a position determining device (PDE). However, it is understood that in other embodiments, the beacon 103 may include a subset of these components. Further, the beacon 103 may be any other transmitter capable of transmitting a positioning signal to enable the terminal 105 to perform positioning. It will also be appreciated by those skilled in the art that in a beacon 103 that includes a position determining device (PDE), the position determining device (PDE) may be the remote device as shown in fig. 1.

According to the disclosed method and apparatus, information received from a first type of transmitter should have substantially higher accuracy of location to be calculated than information received from a second type of transmitter can determine the location. For example, in the case of GPS satellites and cellular base stations, the accuracy of positioning using measurements on satellites is generally greater than the accuracy of positioning using measurements on cellular base stations.

For purposes of clarity, the presently disclosed method and apparatus will be described in the context of a hybrid positioning system in which the satellites are GPS satellites and the beacons are Code Division Multiple Access (CDMA) cellular base stations. However, as mentioned above, the present invention does not rely on the unique features of these systems. Thus, the invention may be implemented using any other system for positioning.

In embodiments where the satellites are GPS satellites and the beacons are CDMA cellular base stations (which may or may not include Base Station Controllers (BSCs) and position determining devices (PDEs)), a "pseudo-range" measurement ρ is made relative to the satellites 101_s1-ρ_s4Similarly, pseudo range measurement ρ with respect to the beacon 103 is also performed_b1-ρ_b3. The pseudo range measurement represents the distance between the receiving terminal 105 and the source of the positioning signal. It should be noted that the particular manner in which positioning is performed is not relevant to the presently disclosed method and apparatus. However, the discussion of pseudo range based positioning techniques provides an example of one embodiment of the disclosed method and apparatus. Other methods of measuring pseudo ranges are well known and may be used to implement the disclosed methods and apparatus. In addition, other methods which are not required are also well known and may be used to implement the disclosed methods and apparatus.

In general, the pseudo range measurement represents the time difference between an arbitrary point in time and the time at which the signal arrives at the positioning terminal 105. However, pseudo ranges are typically expressed in meters. The amount of time can be converted to distance by multiplying the time difference by the speed of light in meters per second.

In one embodiment of the disclosed method and apparatus, the beacon 103 is a CDMA base station and the locating terminal notes when a series of start bits of the spreading code that constitute the CDMA signal have been received at a time relative to any previous point. This series of bits is commonly referred to as a "pseudo-random noise (PN) spreading code.

It should be noted that in a CDMA communication system, the signals transmitted by each base station are encoded using the same PN spreading code. However, there is a discrepancy between the start of a code transmitted from one base station relative to the start of a code transmitted from each other base station. Therefore, these deviations must be taken into account before comparing the timing of the signals received from each of the beacons 103 with each other. It is well known that it is easy to determine these deviations and to subtract them. In fact, these deviations are typically used to identify the particular base station from which the signal originated.

Furthermore, it should be noted that the clock period (assumed to be 1 millisecond in this example) must be such that any ambiguity is discerned. That is, the period of the clock must be such that the clock period associated with the received signals uniquely identifies only one relationship between the received signals. Therefore, the duration of the clock must be greater than twice the difference between the times at which each beacon 103 receives the signal, taking into account the deviation of the timing of the code transmitted by each beacon 103. It should be noted that it is very common in the art to perform pseudo range measurements.

If the position of at least 3 beacons 103 from which the pseudo range measurements are available is known, the pseudo range measurements can be used to determine the position of the terminal 105. The pseudo range measurements and the position of the beacon 103 are subjected to a well-known process commonly referred to as the "least mean square" (LMS) process. Likewise, the reverse process is also possible. That is, if the locations of the terminal 105 and the 3 beacons 103 are known, the distance between the terminal 105 and each of the 3 beacons 103 may be used to determine a pseudo range value from the location of the terminal 105 to the beacon 103.

The method and apparatus of the present disclosure actually have the advantage that hybrid positioning systems often have two independent derivative sets of pseudo range measurements. Typically, one set of measurements will have a higher accuracy than the other. Thus, if the measurements of the higher accuracy set are sufficient to determine the position of the terminal 105, the higher accuracy set of measurements may be used to determine errors in the lower accuracy set of measurements. In addition, it has been determined that there is a predictable relationship between a particular parameter (such as the location of the terminal 105) and the amount of error in a lower accuracy set of measurements. Thus, by knowing the parameter values of both and the amount of error associated with the parameter, an estimation of the amount of error in the lower accuracy measurement can be made. For example, by knowing the approximate location of the terminal 105 and the relationship between the location and the amount of error, the error in the lower accuracy measurement can be estimated.

To take advantage of the relationship between certain parameters and the amount of error in lower precision pseudo range measurements, a "measurement statistics database" (MSD) is generated according to one embodiment of the disclosed method and apparatus. It should be noted that other methods than a database may be used to correlate parameter values to the amount of error in measurements made by the lower accuracy positioning subsystem.

MSD, however, provides an efficient method of correlating a parameter, such as the position of the terminal 105, with a correction factor applied to a lower accuracy pseudo range measurement. Thus, when the parameter values are known, the associated correction factor can be determined from the MSD and applied to the pseudo range measurement.

The following example describes one aspect of the disclosed method and apparatus in which the parameter in question is the position of the terminal 105, as determined from substantially uncorrected pseudo range measurements measured by the terminal 105. In one embodiment of the disclosed method and apparatus, the pseudo range measurements are completely uncorrected. However, it will be apparent to those skilled in the art that some corrections may be made to the pseudo range measurements, all without departing from the scope of the described method and apparatus. For example, the pseudo range measurements may be corrected for time offsets due to differences between the times at which the same code is transmitted from different beacons.

It should also be clear to those skilled in the art that the parameter in question may be any of a number of other parameters. It should be noted that this is advantageous in that the terminal 105 or the beacon 103 can directly measure the parameter value in question. The direct measurement of the parameters by the terminal 105 or the beacon 103 eliminates the need for input from external sources for operation of the disclosed method and apparatus. However, it is possible to input the parameters through an external source, for example, an end operator or a signal received from a remote source.

Possible parameters include, but are not limited to, (1) the amount of power of the positioning signal that the terminal 105 has received; (2) the type of building proximate to the terminal 105; (3) the amount of urban development of the general proximity terminal 105; (4) the distance from the beacon 103 to the terminal 105 receiving the positioning signal; and (5) the shape of a correlation peak determined from the correlation of the received signal with a known PN spreading code. It should be clear that this list provides only a few examples of the many types of parameters that can be used to predict the amount of error that may occur in a pseudo range measurement. The present invention should not be limited to the types of parameters listed herein. Rather, the scope of the present disclosure should be considered to include predicting the amount of error in the first set of measurements using any parameter that is correlated with the first set of pseudo range measurements but uncorrelated (to a lesser degree, on the other hand) with the second set of pseudo range measurements.

Generation of a measured value statistical database (MSD)

A process for generating a Measurement Statistics Database (MSD) is described. In particular, FIG. 2 relates to an example of a relationship between an approximate position of the terminal 105 and an expected error in a pseudo range measurement measured by the terminal 105.

Initially, a determination is made as to whether the positioning subsystem is active with a higher accuracy (step 201). If valid, the position of the terminal 105 is determined by using only measurements from the higher accuracy positioning subsystem (step 203). The process of generating MSD requires higher accuracy positioning capability to be effective. If not, the process of generating a statistical database of Measurements (MSD) is not continued until a higher accuracy positioning capability is available or valid. However, it should be appreciated that in this case, if MSD has been generated sufficiently, the error in the subsystem with lower accuracy may be estimated.

In one embodiment of the disclosed method and apparatus, the terminal 105 is capable of positioning based on pseudo range measurements to the satellites 101 or pseudo range measurements to the beacons 103. Pseudo range measurements to satellite 101 tend to be more accurate. Thus, in such embodiments, the pseudo-ranges of satellites 101 are used, if possible, to determine the location of terminal 105. In another embodiment, the beacon pseudoranges are used to supplement the satellite pseudorange measurements only when there are an insufficient number of valid satellites 101. However, similar to the case where the beacon pseudo-range may be used with a satellite to determine the location of the terminal 105, using satellite pseudo-ranges is preferable to using beacon pseudo-ranges.

The position of the terminal 105 is determined from the pseudo-ranges to the satellites 101 using a method substantially as described above with respect to determining pseudo-ranges from the beacons 103. The pseudo-range measurements to satellite 101 are generally more accurate than the pseudo-range measurements from beacon 103, for several reasons, including the fact that satellite 101 is above ground. The probability of receiving a signal on the direct path from the satellite 101 to the terminal 105 is greater than the probability of a signal from the beacon 103 reaching the terminal 105 directly. The signal cannot travel from the beacon 103 directly to the terminal 105, such that the signal adds a distance along the propagation path from the beacon 103 to the terminal 105. When using pseudo ranges from the beacon 103, the additional range results in an error in calculating the position of the terminal 105.

Once the position of the terminal 105 has been determined using the higher accuracy positioning subsystem, the pseudo range of the beacon 103 can be calculated (step 207). It can be seen that the expected pseudo range to a particular beacon 103 can be readily determined from knowledge of the location of the terminal 105 and knowledge of the location of the beacon 103. In one embodiment of the disclosed method and apparatus, the pseudo range is provided to a beacon 103, which determines the expected pseudo range for a particular terminal 105 to a particular beacon 103. If the terminal makes the determination and calculation, the disclosed method and apparatus assumes that the terminal 105 has access to knowledge of the location of the beacon 103. For example, in a system where the beacon 103 is a CDMA base station, the base stations provide information about their own location to the terminal 105. On the other hand, the terminal 105 maintains a database that provides the location of the beacon 103 to the terminal 105 based on the identification indicators received as part of the transmission from the beacon 103 to the terminal 105. In yet another embodiment of the disclosed method and apparatus, the terminal 105 sends information to one or more beacons 103 for processing. The beacon 103 knows or has visited the location of the beacons in the area.

The terminal 105 then measures the pseudo range to each of the beacons 103 (step 209). Each measured pseudo range is associated with a beacon 103 and compared to the pseudo range associated with that beacon 103 calculated in step 207 (step 211). It is assumed that the difference between the calculated pseudo range and the measured pseudo range is an error in the measured pseudo range. It should be appreciated that the pseudoranges to both the beacon 103 and the satellite 101 may be measured and transmitted to the beacon 103 for processing prior to the beacon pseudorange calculation of step 207.

Once the error in the measured pseudo range to the beacon 103 is determined, the "cluster" in which the terminal 105 is currently located is determined (step 213). Clusters can be defined in many ways. According to a preferred embodiment, a cluster is defined as a set of consecutive values of the parameter. For example, if the parameter is the location of the terminal 105, the cluster will be one contiguous geographic area. The set of consecutive parameter values is preferably large enough to include several error measurements. That is, it is desirable to have generated enough error estimates in the cluster to calculate with reasonable accuracy the average of the pseudo range errors generated by the lower accuracy subsystems at any location in the cluster.

If the number of error estimates is insufficient, the cluster size is increased to include more error estimates. On the other hand, clusters will be considered immature until a sufficient number of error estimates are generated for statistics. The cluster is split in two when enough error estimates have been generated to support both clusters. There should be a sufficient number of error estimates per cluster to allow the calculated mean of the errors associated with that cluster to reflect with reasonable accuracy the mean of the substantially infinite number of error estimate calculations taken from the cluster. If the average of the errors in successive clusters is the same, the clusters can be combined even if there are a sufficient number of error estimates to support more than one cluster. However, according to one embodiment of the disclosed method and apparatus, the clusters may be partitioned differently if such partitioning would result in two clusters, each with a sufficient number of error estimate values and a different error estimate average.

The required result is to associate each cluster with a value, or values, of a parameter. If the value of the parameter detected by the terminal 105 is associated with a cluster, then it is assumed that the terminal 105 is in the associated cluster. For example, if the parameter is the location of the terminal 105, the cluster will be associated with a range of geographic locations. If a terminal 105 is detected to be in a cluster, the terminal 105 may be considered to be in the cluster for purposes of the disclosed method and apparatus. On the other hand, assume that the parameter of interest is the power level of the received signal. A terminal 105 will be considered to be within a particular cluster if the terminal 105 detects that the received signal is within the range of power levels associated with the cluster.

The parameters are selected such that there is a correlation between the parameters and the amount of error in the pseudo range measurements produced by the lower accuracy positioning subsystem. Thus, each value of a parameter is associated with a particular value in the positioning error produced by the lower accuracy positioning subsystem. That is, any time the terminal 105 notices that a parameter has a particular value (or is within a particular range of values), the error in the position fix produced by the lower accuracy positioning subsystem will be a particular value (or is within a particular range of values).

The location of the re-reference terminal 105 is an example of a parameter of interest. Each position of the terminal 105 will be associated with a particular amount of error in the positioning measurements made by the terminal 105 using the lower accuracy positioning subsystem. Thus, in order to select a location as a suitable parameter, each location of the terminal 105 must be associated with a particular amount of error in the positioning measurements produced by the lower accuracy positioning subsystem. Thus, for a terminal at position X, the error amount will be Y. Within the range of allowable unreliability, this error value is substantially constant and can be predicted.

As a more obvious example, reference is made to fig. 3 and 4. In the figure, an area 300 is shown, in which eleven locations 301 can be determined. Pseudo range error measurements are generated at each of these locations 301. The error estimates are based on the difference between the pseudo range measurements taken at these locations 301 and the pseudo ranges calculated from knowledge of the location from the higher accuracy positioning subsystem.

Fig. 3 illustrates a schematic diagram showing the entire area 300 as a single cluster. This is because only a relatively small number (11) of error estimates are initially generated in region 300. It should be noted that the particular number required to construct a sufficient number of estimates depends on the particular application. Thus, depending on the application, the number may be significantly greater or less than 11. It should also be noted that when the beacon 103 shown in fig. 3 is located outside the area 300, the positional relationship of the beacon 103 and the area is not relevant to the present invention, but it should be noted that a signal from the beacon 103 in the area 300 can be received.

Over time, additional error estimates are generated at various locations 302 in the region 300. When these additional error estimates are generated at location 400, a sufficient number of error estimates are available in a portion of the cluster to allow the cluster to be partitioned into smaller sub-clusters. Fig. 4 is a schematic diagram of 4 smaller clusters 401, 403, 405, and 407, which have been sub-partitioned from one larger cluster 300.

An average of the errors in the pseudo range measurements produced in each of the smaller clusters 401, 403, 405, and 407 is then determined. If the average of two or more smaller clusters 303, 305, and 307 are close enough in value, the clusters can be put back together to form a cluster. Fig. 5 is a schematic diagram of an example in which the clusters 401, 403, 405 and 407 of fig. 4 are combined to form a further new cluster 501 comprising a location 500 at which an error estimate has been generated. Thus, clusters having relatively complex shapes may be formed using clusters having relatively simple shapes. Taking more error estimates at different locations in the cluster provides the opportunity to reshape the cluster.

The measurements produced in the clusters typically have different amounts of error. A set of error values may form an array associated with a particular beacon 103 in a particular cluster. The values in the array will vary around an average value within a certain range. From a statistical standpoint, one way to determine the range size characteristics in this variation is to calculate the "variance" of the array. Alternatively, the range size may be characterized by the "bias" of the array.

On the other hand, from the value of the error estimate of the measured pseudo range, the boundary of the cluster can be determined. In this case, variations in the error estimates included in the array are minimized. The area in the cluster is defined such that the variation in the error estimate that has been generated by the positioning terminal 105 is within a predetermined range. If one of the measurements is outside the predetermined range, the shape of the cluster is altered to remove the improper location. Greater accuracy results when it is determined that corrections are to be applied to measurements taken by a lower accuracy positioning subsystem. This is of particular value when it is necessary to rely on at least one measurement from a less accurate subsystem in order to determine the position of the terminal 105.

Once the new variance and mean values are derived from the array calculations associated with the particular cluster in which the terminal 105 is located, the new variance and mean values replace the old ones (step 217). Without calculating the variance and the previous value of the mean, the error itself as the mean and the variance will be equal to 0. Each newer error value associated with that cluster will then replace an older value in the array. In one embodiment of the disclosed method and apparatus, the entire array is stored in a Measurement Statistics Database (MSD). On the other hand, only the new variance, mean and number of cells in the array remain in the matrix. It should be noted that in order to update the variance and mean of the error associated with the array, the entire array must be valid. On the other hand, the mean, variance, and number of cells in the array must be known. MSD is dynamically generated each time the terminal 105 generates a measurement by updating the mean, variance, and number of cells in the array.

On the other hand, the values of all cells in the array are stored in MSD. The values of the mean and variance can be calculated from the stored array elements as needed, rather than after each measurement is generated. It should be noted that according to one embodiment of the disclosed method and apparatus, the mean and variance can be weighted by giving more significant importance to certain elements in the array. According to one such embodiment, the more weighted units are those units that are deemed more reliable for some reason. For example, if the terminal 105 generates a pseudo range measurement from a relatively weak received signal, the weight of such pseudo range measurement may be reduced relative to other measurements generated from a stronger signal.

Further, it should be noted that in accordance with one embodiment of the disclosed method and apparatus, it may be assumed that there is substantially no correlation between errors in satellite pseudo range measurements and errors in beacon pseudo range measurements. Thus, following this assumption, satellite errors (i.e., errors in positioning using satellite pseudo range measurements) will generally not offset the average of the errors in the constellation. However, according to another embodiment of the disclosed method and apparatus, no such assumption is made.

Fig. 6 shows the process of establishing MSD without assumptions about errors in the satellite measurements, as described below.

Pseudo range measurements are generated by the terminal 105 to the satellites 101 (step 601). In addition, the terminal notices the variance in the satellite measurements (step 603). That is, since the measurement will have some amount of error, the measurement will vary around an average value within a certain range. This variation is characterized by calculating the variance in the error in the satellite measurements. In addition, the error can be characterized. The variance (or bias) in the error in the satellite measurements is generally known. As is well known in the art, in general, the provider difference and the average are provided in a covariance matrix associated with each satellite 101.

The satellite measurements and error statistics associated with the satellite measurements (typically in the form of a covariance matrix) are applied to a well-known LMS process (step 604). Furthermore, in one embodiment of the disclosed method, the LMS process also takes into account the geometry of the satellites. The result of applying the satellite measurements, the error statistics associated with these measurements, and the satellite geometry to the LMS process is a positioning solution. The positioning solution gives the position of the terminal 105 of the pseudo range measurement. In addition, the LMS process produces a solution covariance matrix that indicates error statistics regarding the amount of error in the solution. Such solution covariance matrices are well known in the art. The average value is assumed to be 0 due to the fact that no multipath error is assumed in the signal received from the satellite.

The solution is expressed in terms of x, y, z and b, where x, y and z are the cartesian coordinates of the terminal 105 relative to a selected reference, such as the center of the earth, and b is the clock offset in the terminal 105 relative to real GPS time. From the positioning solution, an estimate may be generated for the pseudo range measurements for each beacon 103 for which the terminal 105 is receiving its positioning signals (step 606). The pseudo range estimates may then be compared (step 608) to actual pseudo range measurements taken to the terminals 105 of each beacon 103 to determine the difference therebetween. It is assumed that this difference is an estimate of the error in the measured pseudo range. Further, a beaconizer covariance matrix can be calculated from the solution covariance matrix (step 610). The beaconing covariance matrix characterizes the amount of error in each error estimate calculated from the amount of error in the satellite pseudorange measurements (as determined from the satellite covariance matrix). That is, the error estimate in the beacon pseudo range measurements is based on a completely correct calculated pseudo range assumption. However, the statistics of the error are known for the satellite measurements used to derive the calculated pseudo range. Therefore, there is an error in the estimated value of the amount of error in the beacon pseudo range. Error statistics in the error estimates may be determined from the solution covariance matrix, which is in turn computed from the satellite covariance matrix. And can be implemented by methods well known to those skilled in the art.

According to this embodiment of the presently disclosed method and apparatus, MSD is generated such that each input to the MSD is associated with a cluster, a set of beacons, an average of each array of beacon pseudo range measurement error estimates, and a beacon covariance matrix representing the error in each measurement of the pseudo range due to multipath induced errors (step 612). In another aspect, each input includes an identifier of an associated cluster, an identifier of an associated beacon, an array of pseudo range measurement error estimates associated with the beacon, and a beacon covariance matrix of the associated beacon. It should be noted that it is not possible to determine the covariance between beacons associated with different inputs. Thus, if there is only one beacon associated with an input, it is not possible to determine the covariance matrix for that input. As noted above, according to one embodiment of the presently disclosed method and apparatus, the error estimates for an array are weighted according to the reliability of each such estimate.

It will be appreciated that by selecting clusters that cover a larger amount of area, the variance in each cluster will generally become larger. Since there will be more different conditions in a larger cluster. However, an advantage of having a rather large cluster is that less data (i.e. fewer points per square kilometer) is needed to correctly determine the variance and mean of the errors in the cluster.

These values may be used once the variance and mean of the errors associated with a particular beacon in a cluster are known. In particular, when the terminals 105 in the cluster are producing pseudo range measurements, they are used to estimate the error in the pseudo range to a particular beacon 103. The error estimate in the beacon pseudo range measurement is then used to correct the measured beacon pseudo range. This is particularly useful when the satellite pseudorange measurements are too low. Thus, if there are not enough valid satellites to make a position fix based on satellite measurements alone, a corrected pseudo range to the beacon 103 may be used.

It should be understood that the presently disclosed method and apparatus presumes that MSD will be generated and stored in the terminal 105. However, MSD may also be generated and stored in a beacon or other component remote from the terminal 105. For example, it will be clear to those skilled in the art that the terminal 105 may be responsible only for generating pseudo range measurements. These measurements are then transmitted to the beacon 103. The beacon 103 then processes the pseudo range measurements in the devices 104 in the beacon 103 as described above. On the other hand, device 104 is remote from beacon 103, and beacon 103 communicates the pseudo range measurement to remote device 104. The pseudo range measurements are then processed by the device 104. It will be appreciated that processes may be assigned such that certain processes are performed in one device and other processes are performed in other devices. However, without regard to which device is responsible for performing which process, the disclosed method is performed substantially as determined above.

As contemplated above, the present method and apparatus provide a method by which a location can be corrected from a lower accuracy location subsystem in a single correction step. However, in another embodiment of the above-discussed process, an iterative process as shown in FIG. 7 may be performed, as described below.

Initially, the position of the terminal 105 is determined using a lower precision subsystem (step 701). The determination is then corrected according to a correction factor associated with the first relatively large cluster (step 703). The first cluster is intentionally made quite large because, given the fact that the error in the initial position estimate for the lower accuracy subsystem may be very large, it may be difficult to determine which cluster the terminal 105 is in if the cluster is made too small. Once the position correction is made using the correction factor from the first relatively large cluster, the position of the terminal 105 can be identified with a higher accuracy. A smaller cluster is then used to determine a more accurate correction factor (step 705), and since the first correction provides increased accuracy, it is possible to determine in which smaller cluster the terminal 105 currently resides.

It should be understood that the presently disclosed methods and apparatus may employ a positioning system that is not a hybrid positioning system if there are some other methods by which it can be determined that the position of the terminal is available at some time or location, but not at other times or locations. In this case, the amount of error in the pseudo range measurements may be determined using the position of the terminal as a reference, using the same positioning means as the higher accuracy sub-system described above.

Apparatus for implementing one embodiment of the presently disclosed method

Fig. 8 is a simplified block diagram of one embodiment of a terminal 105 for implementing the presently disclosed method. The terminal 105 comprises a receiver 501, a decoder 503, a correlator 505, a reference code generator 507, a processor 509, a clock 511 and a memory 513. The receiver 501 typically includes a conventional radio frequency front end section including an antenna, down-converter, filters, amplifiers, etc., all of which are well known and not shown for simplicity. Receiver 501 receives signals including positioning signals. The received signal is downconverted, filtered, and amplified as needed (not necessarily in that order) for output to a decoder 503. Those skilled in the art will appreciate that other processing not disclosed herein may occur in receiver 501 but is not essential to the novel aspects of the presently disclosed methods and apparatus.

The output of the receiver 501 is coupled to a decoder 503. The decoder 503 decodes the message portion from the received signal. When a positioning signal is received and decoded, the output of the decoder will be a code sequence. The decoded message is coupled to a correlator 505. The correlator 505 is also coupled to a reference code generator 507. The reference code generator 507 provides a reference code sequence to the correlator 505 so that the correlator 505 can identify a predetermined point in the received code sequence. The correlator 505 outputs a signal to the processor 509 indicating when the reference code sequence and the received code sequence are in synchronization. A reference code generator 507 is also coupled to the processor 509. Once the reference code sequence and the received code sequence are synchronized, the output from the reference code generator 507 to the processor 509 allows the processor 509 to determine the timing of the received code sequence.

A clock 511 is also coupled to the processor 509. Clock 511 may be free running or synchronized to an external clock reference. If the clock is synchronized to an external clock reference, the timing of the received code sequence may be determined relative to the external clock reference. Processor 509 is also coupled to receiver 501. The receiver 501 provides the processor 509 with information on which frequency the receiver 501 is tuned.

According to one type of received signal, the processor 509 receives information from the timing of the received code sequence and on which frequency the signal was received, indicating that the code sequence originated from a particular transmitter 101, 103. It should be noted that multiple correlators 505 may be used to correlate multiple signals simultaneously. The processor 509 takes all of the information provided to it and determines the relative timing (i.e., pseudo range) of all received signals. Further, the processor 509 performs all of the pseudo range processing functions described above.

One application of the presently disclosed method and apparatus allows for the generation of a "sector coverage map". A sector coverage map is a map that indicates which geographic area is being served by a particular sector of the beacon 103. The beacon 103 may be considered sectorized when using separate antennas for pointing to and receiving signals from a particular geographic sector transmitted by the server. In general, the sectors discussed assume a pie-shaped wedge shape that diverges substantially outward from the beacon 103. It is common to construct a cellular base station with 3 such sectors, each forming a non-overlapping pie-shaped wedge with a width of 120 degrees. However, due to several factors, the fact that a sector of the beacon 103 can receive signals from, and transmit signals to, an area within the sector is not generally assumed. Thus, the sector coverage map allows both the terminal 105 and the beacon 103 to determine which sector of the beacon 103 is serving the terminal 105.

According to the presently disclosed method and apparatus, a sector coverage map is generated by correlating: (1) sectors where the beacon 103 receives signals from the terminal 105; (2) the location of the terminal 105 as determined by the higher precision positioning subsystem; and (3) the location of the terminal 105 as determined by the lower accuracy positioning subsystem. Thus, the sector of the beacon 105 that is serving a terminal may be more reliably obtained using the sector coverage map generated as described above, along with the location information of the terminal as determined by the lower accuracy positioning subsystem. This is particularly useful when more than one sector receives signals from a terminal 105. This is more useful when more than one sector reports service to a terminal 105, and the location determined by the lower accuracy positioning subsystem determines that the terminal 105 is not in any sector reporting that they are serving the terminal 105.

The foregoing description of the preferred embodiments of the disclosed method and apparatus provides those skilled in the art with the ability to make and use the invention as described in the claims set forth below. Various modifications may be made to these embodiments without departing from the scope of the invention as hereinafter claimed. It is therefore to be understood that the principles disclosed herein may be applied to other non-disclosed embodiments of the disclosed method and apparatus without departing from the scope of the invention as set forth in the claims provided below. The present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the claims provided below.

Claims (4)

1. A method for correcting errors in pseudorange measurements, said method comprising the steps of:

a) measuring, at a mobile receiver, pseudoranges to beacons;

b) measuring a parameter value;

c) determining a correction amount to be applied to the measured pseudorange to each beacon from a predetermined relationship between the parameter value and the correction factor to be applied; and

d) applying the determined correction amount to the measured pseudo-range.

2. A method for correcting errors in pseudorange measurements, said method comprising the steps of:

a) measuring, at a mobile receiver, a pseudorange to a particular beacon;

b) measuring a parameter value;

c) determining a correction amount applied to the measured pseudorange according to the specific beacon, a predetermined relationship between the parameter value and a correction factor to be applied to the specific beacon; and

d) applying the determined correction to each measured pseudorange.

3. The method of claim 2, wherein the parameter is a position of the terminal determined from uncorrected pseudorange measurements.

4. A method for correcting errors in pseudorange measurements, said method comprising the steps of:

a) measuring, at a mobile receiver, a pseudorange to a particular beacon;

b) measuring a parameter value;

c) determining in which cluster a terminal currently resides according to the measured parameter values;

d) determining a correction amount to be applied to the measured pseudorange to a particular beacon from a cluster in which the terminal resides; and

e) applying the determined correction to each measured pseudorange to the particular beacon.