HK1120308B - Method and apparatus for enhanced autonomous gps - Google Patents

Description

Method and device applied to enhanced autonomous GPS

Technical Field

The present invention relates to positioning systems, and more particularly to the use of long term satellite tracking data in remote receivers.

Background

Global Positioning System (GPS) receivers use measurements from several satellites to calculate position. A GPS receiver typically determines its own position by calculating the time delay between the time a satellite transmits a signal and the time the receiver (located at or near the surface of the earth) receives the signal. Multiplying the time delay by the speed of light yields the distance between the receiver and each satellite visible to the receiver. The GPS satellites transmit satellite positioning data, so-called "ephemeris" data, to the receiver. In addition to ephemeris data, the satellite transmits to the receiver absolute time information associated with the satellite signal, i.e., the absolute time signal is transmitted after the week signal. Such an absolute time signal enables the receiver to unambiguously determine a time tag as to when each received signal was transmitted by each satellite. By obtaining the exact time of transmission of each signal, the receiver can use the ephemeris data to calculate where each satellite was when it transmitted the signal. Finally, the receiver combines the information about the satellite positions with the calculated distances to the satellites to calculate the position of the receiver.

In particular, the GPS receiver receives GPS signals transmitted by orbiting GPS satellites that contain unique pseudo-random noise (PN) codes. By comparing the time shift (shift) between the received PN code signal sequence and the internally generated PN signal sequence, the GPS receiver can determine the time delay between the time of signal transmission and the time of reception.

Each transmitted GPS signal is a direct sequence spread spectrum signal. Standard location services give a version of the application of such signals to commercial applications. These signals apply a direct sequence spread spectrum signal at 1.023MHz spread spectrum to the carrier at 1575.42MHz (L1 frequency). Each satellite transmits a unique PN code (also known as a C/a code) that identifies the particular satellite and allows the receiver to simultaneously receive signals transmitted by several satellites simultaneously with little interference between the signals. The length of the PN code sequence is 1023 chips (chip), corresponding to a time period of 1 millisecond. One cycle of 1023 chips is called a PN frame. Each received GPS signal is constructed from a 1.023MHz repetitive PN type of 1023 chips. Even if the signal is weak, the PN type is observed, and a number of PN frames are processed and averaged to provide a clear time delay measurement. These measured time delays are referred to as "sub-millisecond pseudoranges" because they are modulo the 1 millisecond PN frame boundaries. By solving for the integer value of milliseconds per time delay per satellite, the true unambiguous pseudoranges are obtained. The process of solving unambiguous pseudoranges is known as "integer millisecond ambiguity resolution".

It is sufficient to resolve the position of the GPS receiver after a set of four pseudoranges, the absolute time of transmission of the GPS signals, and the position of the satellites at these absolute times are known. The absolute time of transmission is used to determine the location of the satellite at the time the signal was transmitted, from which the location of the GPS receiver can be determined. The GPS satellites move at speeds approaching 3.9km/s, and therefore, when observed from the earth, the range of these satellites varies at speeds up to +/-800 m/s. The absolute time error results in a position error that can be as high as 0.8m per millisecond of time error. These position errors also cause an approximately large error in the GPS receiver position. Therefore, for a position accuracy of 10m, an absolute time error of 10ms is sufficient. Absolute time errors of more than 10ms result in larger position errors, so the accuracy of a typical GPS receiver requires close to 10ms or better.

The GPS receiver will typically be slow (over 18 seconds) to download ephemeris data from the satellites, often very difficult, and sometimes even impossible (in environments where the signal strength is weak). For these reasons, it has long been known to transmit satellite orbit and clock data to a GPS receiver by other means than waiting for the satellite to transmit the data. This technique of providing satellite orbit and clock data or "aiding data" to a GPS receiver is commonly referred to as "assisted GPS" or a-GPS.

In one type of a-GPS system, a GPS receiver measures pseudoranges and transmits them to a server, which determines the position of the GPS receiver. Such systems are referred to herein as "mobile assisted" systems. In a mobile assisted system, four information exchanges between the GPS receiver and the server are required for each position calculation, including: the receiver requests the server to provide assistance; transmitting the assistance information from the server to the receiver; sending pseudorange measurements from the receiver to a server; finally, the location information is sent from the server to the receiver. In most mobile assistance systems, a new request and new assistance information needs to be sent at each new location, since assistance data is only valid for a short period of time (e.g., a few minutes). Thus, for mobile assisted systems, the total time for determining the position is negatively affected by the number of information interactions between the receiver and the server. Furthermore, if the receiver roams outside the service area of the network transmitting the assistance data, the receiver must autonomously acquire satellite signals and calculate a position, assuming the receiver has the capability of autonomous operation.

In another a-GPS system, the GPS receiver locates itself using assistance data from a server. Such systems are referred to herein as "mobile-based" systems. In a mobile-based system, up to two information interactions between a receiver and a server are performed for each position calculation, including: the receiver requests assistance from the server and the server sends assistance data to the receiver. The position information is calculated internally in the receiver using the assistance information. In conventional mobile-based systems, the assistance information is ephemeris data valid for 2-4 hours. That is, the ephemeris data is the same as the data broadcast by the satellite. Thus, for conventional mobile-based systems, if the receiver had to calculate the position outside of a 2-4 hour period of time (the assistance data was only valid for that period), the total time required to determine the position would be negatively impacted because of the need for additional information interaction between the receiver and the server. Furthermore, if the receiver roams outside the service area of the network transmitting the assistance data for more than 2-4 hours, the receiver must autonomously acquire satellite signals and calculate a position.

Therefore, there is a need in the art for a method and apparatus that can use satellite tracking data in a remote receiver in a manner that minimizes the number of information exchanges between the receiver and a server and that supports extended operations outside the service area of the network.

Disclosure of Invention

A method and apparatus for using long term satellite tracking data in a remote receiver is described. In one embodiment of the invention, the remote receiver receives long term satellite tracking data from a server. For example, the long term satellite tracking data includes satellite orbit, satellite clock, or satellite orbit and clock information that may be valid for at least 6 hours later. The long term satellite tracking data may be generated in the server using satellite tracking information from the reference network, the satellite control site, or both. For example, the long term satellite tracking data may be generated using a satellite orbit model and/or a clock model, such as ephemeris data.

The long term satellite tracking data is used to compute acquisition assistance data in the remote receiver. For example, the acquisition assistance data may include an expected doppler shift of satellite signals transmitted by satellites in view of the remote receiver. The doppler shift may be calculated using the estimated position, the estimated time of day, and the long term satellite tracking data. The remote receiver then acquires satellite signals using the acquisition assistance data. The acquired satellite signals may be used to determine the position of the remote receiver.

In another embodiment, long term satellite tracking data may be acquired at a remote receiver. Satellite Positioning System (SPS) satellites may be detected. Pseudoranges may be determined for the remote receiver to the detected SPS satellites. The position of the remote receiver may be computed using the pseudoranges and the long term satellite tracking data. In one embodiment, SPS satellites may be detected using at least one of acquisition assistance data (calculated using a previously computed position) and a blind search. The use of long term satellite tracking data eliminates the need for the remote receiver to decode ephemeris from the satellites. Further, calculating the position of the remote receiver may eliminate the need to obtain an initial estimated position from a server or network.

Drawings

In order that the features of the invention that are broadly described above will be more clearly understood, reference may be made to the following description of embodiments, some of which are illustrated in the accompanying drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

FIG. 1 is a block diagram of an exemplary embodiment of a positioning system;

FIG. 2 is a block diagram of an exemplary embodiment of satellite tracking data;

FIG. 3 is a block diagram of an exemplary embodiment of a remote receiver;

FIG. 4 is a block diagram of an exemplary embodiment of a server;

FIG. 5 is a flow chart of an exemplary embodiment of a process for autonomously transmitting satellite tracking data to a remote receiver;

6A-6C are flow diagrams of an exemplary embodiment of a process for determining a position of a remote receiver using long term satellite tracking data;

FIG. 7 is a flow chart of an exemplary embodiment of a process of estimating a position of a remote receiver;

FIG. 8 is a flow chart of another exemplary embodiment of a method for determining a position of a remote receiver in accordance with the present invention;

FIG. 9 is a flow chart of an exemplary embodiment of a method of determining a position of a remote receiver using a blind search (blind search) technique in accordance with the present invention;

FIG. 10 is a flow chart of another exemplary embodiment of a method for determining a position of a remote receiver using a blind search technique in accordance with the present invention;

FIG. 11 is a flow chart of yet another exemplary embodiment of a method for determining a position of a remote receiver using a blind search technique in accordance with the present invention;

to facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.

Detailed Description

Fig. 1 is a block diagram of an exemplary embodiment of a positioning system 100. The system 100 includes a server 102 and a plurality of remote receivers 104, i.e., remote receivers 104 as shown₁Remote receiver 104₂And a remote receiver 104₃. The remote receiver 104 measures pseudoranges to a plurality of satellites 106 in a constellation of satellites for position location. For example, the remote receiver 104 may measure pseudoranges to a plurality of Global Positioning System (GPS) satellites in a GPS constellation. The server 102 is used to distribute data representing satellite orbit information, satellite clock information, or both for operation by the remote receiver 104 ("satellite tracking data"). It should be noted that the remote receiver 104 may use the satellite tracking data to assist in acquiring satellite signals and/or calculating position.

The server 102 may distribute the satellite tracking data to the remote receivers 104 using a communication link, such as a wireless communication system 108 or a network 110. For example, the remote receiver 104₁May be within the service area 112 of the wireless communication system 108. In one embodiment of the present invention, satellite tracking data may be transmitted via the remote device 104₁And a base station 116 (located within the service area 112 of the wireless communication system 108) to the remote device 104₁. For example, the wireless communication system 108 may be a cellular telephone network and the service area 112 may be a cell(cell site), the base station 116 may be a cellular tower serving a cell. In another embodiment, satellite tracking data may be provided by the server 102 to the network 110 and then sent to the remote receiver 104₂. For example, the remote receiver 104₂The satellite tracking data may be downloaded from the internet. In some cases, one or more of the remote receivers 104 (e.g., remote receivers 104)₃) May not have the capability to receive satellite tracking data from the server 102. For example, the remote receiver 104₃May be located outside of the service area 112 and may not have the capability to connect to the wireless communication system 108. In addition, remote receiver 104₃May not be able to connect to network 110. As will be described in greater detail below, the satellite tracking data distributed by the server 102 to the remote receivers 114 may be valid for a long period of time (e.g., 2-4 days) as compared to standard broadcast ephemeris. Thus, the remote receiver 104 is not able to connect to the server 102, even though it is not₃Operation may continue for a long period of time.

Satellite tracking data may be generated using multiple types of satellite measurement data ("satellite tracking information"). Specifically, the server 102 receives satellite tracking information from an external source, such as a network of tracking stations ("reference network 118") or a satellite control station 120, or both. The reference network 118 may include several satellite tracking stations that collect satellite tracking information from all satellites in the constellation, or a few tracking stations, or a single station that collects only satellite tracking information in a particular region of the world. The satellite tracking information collected from the reference network 118 may include, for example, at least one of satellite ephemeris, code phase measurement (code phasemeasurement), carrier phase measurement, and doppler measurement. An exemplary system for collecting and distributing ephemeris data using a reference network is described in U.S. patent 6411892 filed on 25/6 2002, which is also incorporated herein in its entirety. The server 102 may receive satellite tracking information (e.g., ephemeris) from a satellite control station 120 (e.g., a master control station in GPS) via a communication link 122. An exemplary system for obtaining ephemeris information directly from satellite control sites is described in U.S. patent application 10/081164 (attorney docket GLBL020) filed on 2/22 2002, which is also incorporated herein in its entirety.

The server 102 generates satellite tracking data for distribution to the remote receivers 104 using satellite tracking information received from the reference network 118 and/or the satellite control site 120. The satellite tracking data generated by the server 102 includes satellite orbit data, satellite clock data, or both satellite orbit and satellite clock data. The satellite tracking data may be valid for a long time compared to ephemeris data broadcast by the satellites 106. In one embodiment of the invention, the satellite trajectory data may be valid for at least six hours. In one embodiment of the invention, the satellite orbit data can be valid for up to four days. Thus, the satellite tracking data transmitted to the remote receiver 104 may be referred to herein as "long term satellite tracking data," as distinguished from broadcast ephemeris, which is typically valid for only 2-4 hours. An exemplary system for generating satellite tracking data is described in U.S. patent 6542080, entitled 4/1/2003, the entire contents of which are also incorporated herein by reference.

Fig. 2 is a block diagram of an exemplary embodiment of satellite tracking data 200. The satellite tracking data 200 includes a plurality of modules (models) 202₁—202_N(collectively referred to as modules 202), where N is an integer greater than or equal to 1. Each of the modules 202 is only active for a certain period of time later (e.g., 6 hours in this embodiment). Each of the modules 202 includes satellite orbit data, satellite clock data, or satellite orbit and clock data. The satellite trajectory data portion of each of the modules 202 may include one or more data representing satellite positions, satellite velocities, and satellite accelerations. The satellite clock data portion of each of the modules 202 may include one or more data representing a satellite clock offset, a satellite clock drift amount, and a satellite clock drift rate. In one embodiment of the invention, each of the modules 202 includes ephemeris data collected from the reference network 118 and/or the satellite control station 120. In another embodiment, each of the modules 202 may use some other format to represent track parameters and/or clock parametersAnd (4) counting. An exemplary module for satellite tracking data is described in us patent 6542820.

The satellite tracking data 200 is defined by N blocks of sequentially arranged satellite orbit and/or clock data (i.e., N modules 202). For ease of description, each of the modules 202 has a validity period of 6 hours, and thus the satellite tracking data has a validity period of 6N hours. However, it should be understood that the validity period of each of the modules 202 may also be other values. For example, satellite tracking data that is valid for 4 days may be generated using 16 modules 202 arranged in sequence.

Referring back to FIG. 1, in one embodiment of the present invention, the satellite tracking data generated by the server 102 is associated with all satellites in the constellation. Thus, wherever the remote receiver 104 calculates its position, the remote receiver 104 will have the correct information for the satellites in view. In another embodiment, the satellite tracking data generated by the server 102 is associated with only satellites visible in a particular area (e.g., the country in which the remote receiver 104 is operating) during the validity period of the orbit and clock data therein. For example, as described above, the satellite tracking data may consist of 16 sequential 6-hour orbit and/or clock modules with a total validity period of four days. In some of these 6 hour periods of validity, where some satellites are not visible anywhere in the country in which the remote receiver 104 is operating, the server 102 may be configured to remove these particular modules from the satellite tracking data before distributing the satellite tracking data to the remote device 104. Since the server 102 can provide satellite tracking data for all possible satellites (e.g., all satellites in a constellation or all satellites visible within a particular area), the data is independent of the location of the remote receiver 104 when the satellite tracking data is transmitted, as long as the remote receiver is somewhere within the particular area.

Fig. 3 is a block diagram of an exemplary embodiment of a remote receiver 300. The remote receiver 300 may be used as any of the remote receivers 104 described in fig. 1. As shown, the remote receiver 300 includes a satellite signal receiver 302, a wireless transceiver 304, a microcontroller 306, a memory 308, a modem 310, and a clock 311. Satellite signal receiver 302 receives satellite signals through antenna 312. The satellite signal receiver 302 processes the satellite signals to generate pseudoranges in a known manner. An exemplary assisted GPS signal receiver is described in us patent 6453237 issued on 9/17 2002, the contents of which are incorporated herein in their entirety. The clock 311 may be used to establish an estimated time of day.

The memory 300 may be random access memory, read only memory, removable memory, hard disk memory, or any combination of these storage devices. The memory 308 may store satellite tracking data 316 that may be used to assist in acquiring satellite signals or calculating position, or both. The satellite tracking data 316 may be received via the antenna 314 using the wireless transceiver 304, or via a computer network (e.g., the internet) using the modem 310. The memory 300 may also store a table of locations ("table 318"). The table 318 may contain recently calculated positions of the remote receiver 400 and/or positions of base stations or cells with which the remote receiver 300 has recently communicated. The table 318 may be used to establish an estimated position of the remote receiver 300. As will be described below, the estimated position of the remote receiver 300 and the estimated time of day may be used to generate data to assist in acquiring satellite signals from the satellite tracking data 316 ("acquisition assistance data" 320).

Fig. 4 is a block diagram of an exemplary embodiment of a server 400. The server 400 may be used as the server 102 described in fig. 1. As shown, the server 400 includes a Central Processing Unit (CPU)402, input/output (I/O) circuits 404, support circuits 406, and a memory 408. The support circuits 406 comprise well-known circuits that facilitate operation of the CPU402, such as clock circuits, cache, power supplies, and the like. The memory 408 may be random access memory, read only memory, removable storage, hard disk storage, or any combination of the above.

Satellite tracking information 410 (e.g., ephemeris, code phase measurements, carrier phase measurements, doppler measurements) is received from an external source of such information (e.g., a reference network and/or a satellite control station) using the I/O circuitry 404 and stored in the memory 408. The server 400 uses the satellite tracking information 410 to calculate long term satellite tracking data for use by the remote device. The I/O circuitry 404 may also be connected to a cellular database 412. The cellular database 412 stores a database containing identifiers ("cell IDs") of various base stations or cells of the wireless communication system, as well as base station or cell locations. As will be described below, the base station or cell site location may be used as an approximate location for the remote receiver. Alternatively, the approximate location of the remote receiver may also be determined using the spacing between cells or base stations, the last known location, or similar information.

The I/O circuitry 404 may also be connected to a device database 414. The device database 414 may be used to record when particular satellite tracking data is distributed to which remote receivers and when such satellite tracking data is expired. Using the device database 414, the server 400 can determine when to update the remote receivers with the most recent satellite tracking data. An exemplary process of transmitting satellite tracking data to a remote receiver will be described below.

Satellite tracking data may be sent to remote receivers upon request from the remote receivers. For example, a user of the remote receiver may manually request satellite tracking data from a server or trigger a position calculation application that requires the use of satellite tracking data. The satellite tracking data may also be automatically transmitted to the remote receiver. Fig. 5 is a flow diagram of an exemplary embodiment of a process 500 for autonomously transmitting satellite tracking data to a remote receiver. The process 500 may be performed by a server or a remote receiver. That is, the remote receiver may determine when it needs satellite tracking data or the server may determine when the remote receiver needs satellite tracking data.

The process 500 begins at step 502 by determining the time elapsed since the last satellite tracking data interaction. At step 504, it is determined whether the elapsed time exceeds a predetermined threshold. The threshold may be a percentage of the satellite tracking data validity period. For example, if the satellite tracking data has a validity period of four days, the threshold may be set to two days. Thus, if two days have elapsed since the last satellite tracking data transaction, the threshold is exceeded. If the threshold is exceeded, the process 500 proceeds to step 506. Otherwise, the process 500 returns to step 502.

At step 506, a determination is made as to whether a connection to the server is available. For example, if the remote receiver is powered off or roams outside the service area of the system, a connection to the server may not be available. If a connection is available, process 500 proceeds to step 508.

At step 508, new satellite tracking data is scheduled to be transmitted to the remote receiver during low traffic periods. Since the threshold in step 504 is set to a percentage of the validity period of the satellite tracking data, the remote receiver does not need to immediately request new satellite tracking data because the currently stored satellite tracking data is still valid. Thus, new satellite tracking data may be transmitted to the remote receiver using a wireless communication system or other network when the network burden is low.

If at step 506 a connection is not available, process 500 proceeds to step 510. At step 510, it is determined whether the elapsed time exceeds the validity period of the satellite tracking data. If not, the process 500 proceeds to step 508 described above. That is, the server will schedule new satellite tracking data to be sent to the remote receiver during low traffic periods. Since the threshold in step 504 is set to a percentage of the validity period of the satellite tracking data, the remote receiver does not need to immediately request new satellite tracking data. The remote receiver may continue to operate using valid satellite tracking data until a connection becomes available, at which time new satellite tracking data may be transmitted during low traffic periods.

If, at step 510, the elapsed time exceeds the validity period of the satellite tracking data, the process 500 continues with step 512. At step 512, new satellite tracking data is scheduled for transmission to the remote receiver when a connection is available. That is, when the remote receiver is again connected to the system, new satellite tracking data will be uploaded to the remote device.

In this way, all remote receivers have valid satellite tracking data at almost all times when they are able to connect to the server. Furthermore, almost all remote receivers can immediately enjoy the benefits of assisted GPS operation when their own position needs to be determined, without requiring a request for satellite tracking data or waiting for satellite tracking data to be transmitted. Thus, the number of server interactions is minimized. When a connection to the server is not possible, the remote receiver that is not able to connect to the server may continue to operate using satellite tracking data for an extended period of time (e.g., four days). In addition, the satellite tracking data is independent of the precise time at which the remote receiver uses the satellite tracking data.

Fig. 6A-6C are flow diagrams of an exemplary embodiment of a process 600 for determining a position of a remote receiver using long term satellite tracking data. The process 600 begins at step 602 by determining the elapsed time since the last satellite tracking data interaction. At step 604, it is determined whether the validity period of the satellite tracking data has been exceeded. For example, the satellite data may be valid for four days. If the satellite tracking data is not valid, the process continues with step 606. Otherwise, process 600 continues with step 610.

At step 606, a determination is made as to whether a connection between the server and the remote receiver is available. If not, the process continues with step 608 to mark the connection as unavailable. Otherwise, the process 600 proceeds to step 607. At step 607, new satellite tracking data is requested and received by the remote receiver from the server. At step 609, the stored satellite tracking data is updated with the new satellite tracking data. The process then proceeds to step 610.

At step 610, the current time of day is determined. In one embodiment, a clock within the remote receiver may be used to determine an estimate of the time of day. At step 612, the position of the remote receiver is estimated. At step 614, acquisition assistance data is computed using the current time of day, the estimated position, and the stored satellite tracking data (or almanac data). The acquisition assistance data may assist the remote receiver in acquiring satellite signals. In one embodiment, the acquisition assistance data includes a predicted doppler shift for each satellite in view of the remote receiver. In GPS, all satellite signals leave the satellite at the same frequency accurate to 1575.42 MHz. However, the frequency of the satellite signal observed at the remote receiver will shift by +/-4.5KHz due to relative satellite motion. The doppler shift of a satellite as it rises from the horizon is up to 4.5KHz or more and as it falls below the horizon is up to 4.5KHz or less, whereas when the satellite is at a zenith (the highest point of the satellite in the air from the perspective of the remote receiver), no doppler shift occurs.

The remote receiver may use the position estimate, the time of day, and stored satellite tracking data (or almanac data) to calculate a doppler shift relative to the estimated position of the remote receiver. As described above, in one embodiment, the satellite tracking data may be provided in the format of ephemeris data. If such satellite tracking data is used, the estimated position and the Doppler shift at the present time of day may be calculated in a conventional manner. The acquisition assistance data provides a window or range of uncertainty in the expected doppler shift. The size of the uncertainty range depends on the accuracy of the initial estimated location and the time of day. The current time of day has little effect on the size of the uncertainty range, with errors that may be several seconds below GPS time. The estimated position has a large impact on the uncertainty range. If the estimated position is within 10km of the true position of the remote receiver, the Doppler range is +/-10 Hz. If the estimated location is within a wide area around the true location (e.g., within a particular country of operation or within 3000 km), the Doppler range is +/-3000 Hz. An exemplary process for processing the remote receiver estimated position will be described below. As is well known in the art, the doppler search range must also contain the uncertainty of the local reference frequency in the remote receiver.

At step 616, the remote receiver acquires satellite signals using the acquisition assistance data. In one embodiment, the remote receiver searches for satellite signals within a frequency range defined by the acquisition assistance data and the local frequency reference. The time it takes to acquire the necessary satellite signals to compute the initial position (the time it takes to first determine the position) depends on the size of the frequency window. The smaller the frequency window, the shorter the time required to first determine the position.

At step 618, a determination is made as to whether the connection is marked as unavailable. If not, the process 600 continues with step 624, where the position of the remote receiver is calculated using the stored satellite tracking data. If the connection is marked as unavailable in step 608, the process continues with step 620. At step 620, ephemeris is decoded from the acquired satellite signals. The acquisition assistance data may be calculated at step 614 using stale or "old" satellite tracking data, or satellite almanac data, and such stale or inaccurate satellite tracking data would not be used to calculate the position of the remote receiver. Thus, if the stored satellite tracking data is out of date and the remote receiver cannot connect to the server to obtain new satellite tracking data, the remote receiver must decode the satellite signals to obtain ephemeris information. At step 622, the position of the remote receiver may be calculated using ephemeris information.

Fig. 7 is a flow diagram of an exemplary embodiment of a process 700 for estimating a position of a remote receiver. The process 700 may be used in step 612 of the process 600 as the primary estimation technique. It will be appreciated by those skilled in the art that other location estimation techniques known in the art may also be used, such as using the migration of the remote receiver between cells or base stations or the last known location of the remote receiver. The process 700 begins at step 702 by determining the cell ID of the cell site in which the remote receiver is currently located ("active cell site"). If no cell ID exists, then no active cell site exists and the process 700 proceeds to step 706. Otherwise, process 700 proceeds to step 704.

At step 704, it is determined whether the cellular location is in a table stored at the remote receiver. That is, the remote receiver may use the cell ID to search a location table to determine the location of the active cell site. If the position associated with the active cell site is in the table, the process 700 proceeds to step 708 where the estimated position of the remote receiver and the uncertainty of the estimated position are output. If the cell location is not in the table, process 700 proceeds to step 706.

At step 706, either there is no cell ID (e.g., the remote receiver is not operating within the service area of the wireless communication system) or there is no location stored in the table associated with the cell ID. Therefore, it is necessary to judge whether or not there is a position that was determined last time. For example, the position determined last time may be a position not exceeding 3 minutes from the time of last determination to the current time. It should be noted that within three minutes, if the remote receiver is operating at a speed of less than 200km/h, the distance traveled by the remote receiver will not exceed 10 km. This distance is within an approximate position uncertainty so that the cell location can be used to obtain the position of the remote receiver. If there is a last determined position, the process 700 proceeds to step 708 and outputs an estimated position and uncertainty using the last determined position as the estimated position. In addition, the location table is updated with the most recent location at step 710.

If at step 706 there is no last determined location, the process 700 proceeds to step 712. At step 712, a determination is made as to whether a connection between the server and the remote receiver is available. If not, the process 700 proceeds to step 718 where the estimated location is set to a wide area (e.g., country or work area). From step 718, process 700 proceeds to step 708 where the estimated position and uncertainty are output.

If at step 712, a connection exists between the server and the remote receiver, process 700 proceeds to step 714. At step 714, the location of the active cell site is requested from the server. If the cell ID has been obtained, the remote receiver may send the cell ID to the server. If, at step 716, a location is returned from the server, the process proceeds to step 708 where the estimated location and uncertainty are output. In addition, the location table is updated with the newly returned location of the particular active cell site at step 710. If at step 716, the location cannot be returned from the server, the process 700 proceeds to step 718, where the estimated location is set to a wider area.

By using the table of positions and the last determined position, the remote receiver may avoid unnecessary interaction with the server. Thus, instead of requesting the location of the active cell site using the cell ID, the remote receiver may first determine whether the information is stored locally.

A method and apparatus for tracking data using long term satellites is described above. In one embodiment of the invention, the long term tracking data includes satellite orbit and/or clock data that is valid for between two and four days. Thus, the remote receiver may continue to operate for up to four days without the need to connect to a server to receive the updated information. If the remote receiver is unable to connect to the server (e.g., the remote receiver roams outside the service area of the network), the remote receiver may continue to use the long term satellite tracking data until the remote receiver is again able to connect to the network. Thus, only one interaction between the server and the remote device occurs between every two to four days, or the interaction occurs only when the remote device requests the location of a cell or base station from the server.

After the long term satellite tracking data is obtained, the remote receiver may obtain satellite signals, determine pseudoranges to corresponding satellites, and calculate position using the pseudoranges and the long term satellite tracking data. The remote receiver may also use the long term satellite tracking data along with the estimated position and estimated time to generate acquisition assistance data (e.g., expected doppler shifts) to assist in the satellite signal acquisition process. This process has been described above with reference to fig. 6. In one embodiment, the estimated location may be obtained from the network (e.g., using a cell ID).

However, in some cases, the remote receiver may not be able to acquire the initial position from the network to compute the acquisition assistance data. For example, the remote receiver may operate autonomously and outside the service area of the network. Thus, in another embodiment of the present invention, rather than receiving an estimated position from the network, the remote receiver attempts to compute acquisition assistance data and determine pseudoranges using the previously computed position as the initial position. The remote receiver then uses the pseudoranges and the long term satellite tracking data to compute position. The position is then checked for validity and if not, the remote receiver performs a blind search procedure to calculate the position.

Specifically, FIG. 8 is a flow chart of another exemplary embodiment of a method 800 for determining a position of a remote receiver in accordance with the present invention. The method 800 may be performed without acquiring an initial position from the network at the remote receiver. The method 800 begins at step 802. At step 804, long term satellite tracking data is acquired. For example, the long term satellite tracking data may be retrieved from memory in the remote receiver. As described above with reference to fig. 5, the remote receiver may acquire long term satellite tracking data from the network. As described above with reference to fig. 6, the remote receiver may periodically refresh the long term satellite tracking data.

At step 806, a determination is made as to whether a previously computed position is available. For example, the remote receiver may install a location cache for storing computed locations and retrieving previously computed locations therefrom. If the previously computed position is not available, the method 800 proceeds to step 820. At step 820, a location is calculated using a blind search process. An exemplary embodiment of a blind search process that may be used in step 820 will be described below in conjunction with fig. 9-11. The method 800 proceeds to step 822 where the location is stored and used as the previous computed location during the next computation.

At step 806, a previously computed position is available, then the method 800 proceeds to step 808. At step 808, acquisition assistance data (e.g., expected Doppler shifts) is computed using the previously computed position as an estimated position, along with long term satellite tracking data. At step 810, satellite signals from Satellite Positioning System (SPS) satellites are obtained at the remote receiver using the acquisition assistance data.

At step 812, a determination is made as to whether the number of satellites from which information is obtained exceeds a predetermined threshold. For example, the threshold may be 2 satellites. Thus, if data has been obtained from more than two satellites at step 810, the method 800 proceeds to step 814. Otherwise, if data is obtained from only two or fewer satellites at step 810, the method 800 proceeds to step 820 where a blind search process is performed to calculate a position.

At step 814, pseudoranges are determined to the detected SPS satellites. The remote receiver may use a conventional correlation process to measure sub-millisecond pseudoranges to the detected SPS satellites. The integer millisecond portion of the sub-millisecond pseudoranges may be determined using a previously computed position used as the estimated position. In one embodiment, the integers may be determined by correlating sub-millisecond pseudoranges to expected pseudoranges between a previously computed position and estimated satellite positions generated from long term satellite tracking data. An exemplary process for calculating pseudorange integers is described in commonly assigned U.S. patent 6734821, entitled 5/11/2004, the entire contents of which are incorporated herein by reference.

At step 816, the position of the remote receiver is computed using the pseudoranges determined at step 814 and the long term satellite tracking data obtained at step 804. The position may be calculated using existing navigation equations. At step 818, a determination is made as to whether the computed position of step 816 is valid. It should be noted that the authenticity of the computed location may be determined using a variety of authenticity verification techniques known in the art. For example, the difference between the calculated position and the previously calculated position (used as the estimated position) may be calculated and compared to a threshold. If the difference exceeds a threshold (e.g., 150Km), the computed position will be marked as invalid. Alternatively, the altitude of the calculated position may be determined to be within a reasonable range (e.g., -1 km-15 km). If the height is outside the range, the computed position is marked as invalid. In another embodiment, a posteriori residuals (a-posteriori residual) associated with the measured pseudoranges may be constructed. The a posteriori residuals may be analyzed to determine if false pseudoranges exist. If all pseudoranges are erroneous, computing the position is not valid. The process of analyzing the posterior margin is described in the above-referenced U.S. patent 6734821.

If, at step 818, the calculated position is not valid, the method 800 proceeds to step 820 where a blind search is performed to calculate the position. Otherwise, the method 800 proceeds to step 822 where the computed position is stored for use as the previous computed position at the next iteration. The method 800 ends at step 824.

Fig. 9 is a flow diagram of an exemplary embodiment of a method 900 for determining a position of a remote receiver using a blind search (blind search) technique in accordance with the present invention. The method 900 may be performed without obtaining an initial estimated position in the remote receiver from the network. The method 900 begins at step 902. At step 904, a blind search is performed to detect SPS satellites. That is, the remote receiver searches for satellite signals in a conventional manner, and the benefit of acquiring assistance data is not obtained. At step 906, pseudoranges are determined to the detected SPS satellites. The remote receiver may measure sub-millisecond pseudoranges to the detected SPS satellites using a conventional correlation process. The integer part of the sub-millisecond pseudorange is computed in a known manner by decoding a converted word (HOW) in the satellite navigation stream broadcast by the satellite to obtain a time-of-week (TOW) count. At step 908, position of the remote receiver is computed using the pseudoranges determined at step 906 and the long term satellite tracking data stored in the remote receiver. The position may be calculated using existing navigation equations. The method 900 ends at step 910.

The use of long term satellite tracking data to calculate position eliminates the need to decode ephemeris at the remote receiver from the satellite navigation stream from each satellite to which a pseudorange is determined. Because ephemeris does not need to be decoded, the cold start speed of the remote receiver is increased, especially in situations where the satellite signal is weak and/or intermittent. Furthermore, the method 900 may be performed without the use of an initial location or precise time from the network, which may allow the method 900 to be performed when the remote receiver is outside the service area of the network. The position calculated using the method 900 may be stored and used as an estimated position to calculate acquisition assistance data in the next position calculation process, as described above with reference to fig. 8.

Fig. 10 is a flow chart of another exemplary embodiment of a method 1000 for determining a position of a remote receiver using a blind search technique in accordance with the present invention. Similar to the method 900 of fig. 9, the method 1000 may be performed without obtaining an initial estimated position from the network at the remote receiver. The method 1000 begins at step 1002. At step 1004, a blind search is performed to detect SPS satellites. At step 1006, sub-millisecond pseudoranges are measured to the detected SPS satellites. At step 1008, pseudorange rates are measured in the remote receiver. In one embodiment, the pseudorange rates may be determined by obtaining Doppler measurements. Alternatively, the pseudorange rates may also be measured by computing the time derivatives of the sub-millisecond pseudoranges.

At step 1010, an estimated position of the remote receiver is computed using the long term satellite tracking data and the pseudorange rates stored in the remote receiver. In one embodiment, this step may be accomplished by iteratively applying the following mathematical model:

where u is a vector of pseudorange rate residuals (i.e. the difference between measured and expected pseudorange rates),represents the partial derivative of the signal as a function of time,is the nth pseudorange rate and c represents the speed of light. The variables x, y and z are updates to the posterior (a-prior) position. In this embodiment, the initial position need not be provided, so the model described above can be applied with the initial position at the center of the surface, iterating until the updates converge. Variable f_cIs an update to the a posteriori reference frequency offset in the remote receiver. In one embodiment, f_cThe unit of (b) is seconds, the unit of c is m/s, and the unit of u is m/s. Expected pseudorange rates and elements of the matrix may be computed using long term satellite tracking data. Derivatives of the above model are described in U.S. patent application 10/617559 (attorney docket number GLBL027), filed on 11/7/2003, of the same assignee, the entire contents of which are incorporated herein by reference. Other terms (term), such as the time of day offset, may be included in the above calculation, but since only an approximate location (e.g., within 10 km) is required, it is sufficient to use the approximate time of day in the above calculation when calculating the values of u and the elements of the matrix.

In another embodiment, the estimated position of the remote receiver may be computed in step 1010 using both the pseudorange rates and the sub-millisecond pseudoranges. It should be noted that if only two satellites are detected at step 1004, the remote receiver will not be able to compute position using only the pseudorange rates or only the pseudoranges without using other assistance data. However, since the pseudorange rates and the pseudoranges provide independent measurements, the pseudorange rates and the pseudoranges may be used in combination to provide sufficient measurements (e.g., four measurements for computing latitude, longitude, altitude, and common mode clock bias) to compute position. Such a calculation is described in U.S. patent application 10/617559, the entire contents of which are incorporated herein by reference.

At step 1012, the integer portions of the sub-millisecond pseudoranges measured at step 1006 are determined using the estimated position computed at step 1010. In one embodiment, the integers may be computed by correlating the sub-millisecond pseudoranges measured at step 1006 with expected pseudoranges (pseudoranges between the estimated position and estimated satellite positions generated from the long term satellite tracking data). An exemplary process for computing pseudorange integers is described in the above-referenced U.S. patent 6734821.

At step 1014, a determination is made as to whether the precise time of day is available in the remote receiver. For example, the remote receiver may acquire the precise satellite time by decoding the HOW to acquire the TOW count message. Alternatively, the remote receiver may initially acquire precise satellite time from the network and then continue to track the precise time. If the exact time of day is known in the remote receiver, the method 1000 proceeds to step 1016. At step 1016, the position of the remote receiver may be computed using the long term satellite tracking data and the full pseudoranges in existing navigation solutions. If the exact time of day is unknown at the remote receiver, the method 1000 proceeds to step 1018.

At step 1018, position of the remote receiver is computed using the long term satellite tracking data and full pseudoranges of the time-independent navigation model. It should be noted that mathematical models are used to model the residual difference (between the actual pseudoranges and the expected pseudoranges) and the relative positions (e.g., x, y, and z positions), time (e.g., local clock bias (t)_c) And the current time of day error (t)_s) ) to establish an association between updates. The expected pseudoranges are based on the estimated position computed at step 1010. In one embodiment, the mathematical model may be defined by the following equation:

where u is a vector of pseudorange residuals (the difference between expected pseudoranges and actual pseudoranges); the H matrix contains the well-known line-of-sight vectors (first three columns) that associate the position updates (x, y, z) with pseudorange residuals; the known constant column (c speed of light) biases the local clock (t)_c) Associated with a pseudorange residual; pseudorange rate column compares the time of day error (t)_s) Associated with the pseudorange residuals. For a detailed understanding of the mathematical model, the reader is referred to the above-cited U.S. patent 6734821. The mathematical model may be iterated several times to converge to a certain position. The method 1000 ends at step 1020.

The use of long term satellite tracking data to calculate position eliminates the need to decode ephemeris at the remote receiver from the satellite navigation stream from each satellite to which a pseudorange is determined. Because ephemeris does not need to be decoded, the cold start speed of the remote receiver is increased, especially in situations where the satellite signal is weak and/or intermittent. Furthermore, the method 1000 may be performed without the use of an initial position or precise time from the network, which allows the method 1000 to be performed when the remote receiver is outside the service area of the network. The position calculated using the method 1000 may be stored and used as an estimated position to calculate acquisition assistance data in the next position calculation process, as described above with reference to fig. 8.

Fig. 11 is a flow chart of yet another exemplary embodiment of a method 1100 for determining a position of a remote receiver using a blind search technique in accordance with the present invention. Again, the method 1100 may be performed without obtaining an initial estimated position from the network at the remote receiver. The method 1100 begins at step 1102. At step 1104, a blind search is performed to detect SPS satellites. At step 1106, sub-millisecond pseudoranges are determined to the detected SPS satellites. At step 1108, the posterior position of the remote receiver is selected from the space of all possible positions. It should be noted that the space of all possible a-priori positions may be segmented, for example, into a grid of 100km x 100km latitude-longitude, with altitude assigned from a terrain altitude look-up table. At step 1110, the integer portions of the sub-millisecond pseudoranges are determined from the a posteriori estimated positions. The integer portion may be performed using steps similar to step 1012 of method 1000 of FIG. 10, described above.

At step 1112, position of the remote receiver is computed using the long term satellite tracking data and the full pseudoranges stored in the remote receiver. As shown in fig. 10, the position may be calculated using existing navigation equations (if accurate time is available) and a time-independent navigation model. At step 1114, a determination is made as to whether the calculated position is valid. The validity of the computed position may be estimated using step 818 of method 800 described above. If not, the method 1100 returns to step 1108 to select another a posteriori location from the space of possible locations. Otherwise, the method 1100 continues to step 1116. At step 1116, the calculated position is output. The method 1100 ends at step 1118. As shown in fig. 8, the location output using method 1100 may be stored and used as an estimated location in the next location calculation to calculate acquisition assistance data.

In the foregoing description, the invention has been described with reference to applications based on the united states Global Positioning System (GPS). It is clear, however, that these methods are equally applicable to other satellite systems, and in particular to the russian glonass system, the european galileo system, and the like, or any combination of the glonass system, the galileo system and the GPS system. The term "GPS" as used herein includes these other satellite positioning systems, namely the russian glonass system and the european galileo system.

Although the method and apparatus of the present invention are described with reference to GPS satellites, it should be understood that the teachings of the present invention are equally applicable to systems using pseudolites or a combination of satellites and pseudolites. Pseudolites are ground-mounted transmitters that broadcast a PN code (similar to a GPS signal) that may be modulated on an L-band carrier signal, typically synchronized with GPS time. The term "satellite" as used herein includes pseudolites or equivalents of pseudolites, and the term "GPS" signals as used herein includes GPS-like signals from pseudolites or equivalents of pseudolites.

While the foregoing is directed to particular embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.

Claims (19)

1. A method for determining a position of a remote receiver, comprising:

obtaining long term satellite tracking data at the remote receiver, the long term satellite tracking data comprising satellite orbit data and/or satellite clock data;

detecting Satellite Positioning System (SPS) satellites;

determining pseudoranges from said remote receiver to said detected SPS satellites; and

computing a position of said remote receiver using said pseudoranges and said long term satellite tracking data;

the detecting step comprises at least one of the following steps: detecting the SPS satellites using acquisition assistance data calculated using a previously calculated position; and, performing a blind search to detect the SPS satellites.

2. The method of claim 1 wherein said remote receiver receives said long term satellite tracking data from a server.

3. The method of claim 2 wherein said long term satellite tracking data is generated by said server.

4. The method of claim 1, wherein said step of determining said pseudorange comprises:

measuring sub-millisecond pseudoranges to the detected SPS satellites;

decoding a current time of week (TOW) value from at least one of said detected SPS satellites; and

solving an integer millisecond portion of the sub-millisecond pseudorange to generate the pseudorange using the TOW value.

5. The method of claim 1, wherein said step of determining said pseudorange comprises:

measuring sub-millisecond pseudoranges to the detected SPS satellites;

measuring a pseudorange rate associated with the detected SPS satellites;

calculating an estimated position of the remote receiver using the pseudorange rates and sub-millisecond pseudoranges; and

solving an integer millisecond portion of the sub-millisecond pseudoranges using the estimated position to generate the pseudoranges.

6. The method of claim 5, wherein the step of calculating the position of the remote receiver comprises:

obtaining an estimated value of the current time of the day;

associating said sub-millisecond pseudoranges with a plurality of position and time variables using said long term satellite tracking data, said time of day estimate and said estimated position;

solving for one or more of the position and time variables to determine a position of the remote receiver.

7. The method of claim 1, wherein said step of determining said pseudorange comprises:

measuring sub-millisecond pseudoranges to the detected SPS satellites;

selecting a priori positions from a position space;

solving an integer millisecond portion of the sub-millisecond pseudoranges using the prior position to generate the pseudoranges.

8. The method of claim 7, wherein the step of calculating the position of the remote receiver comprises:

obtaining an estimated value of the current time of the day;

associating said sub-millisecond pseudoranges with a plurality of position and time variables using said long term satellite tracking data, said time of day estimate and said a priori position; and

solving for one or more of the position and time variables to determine a position of the remote receiver.

9. The method of claim 7, further comprising:

when the position is determined to be invalid, repeating the selecting and solving steps to obtain one other prior position in the position space.

10. A method for determining a position of a remote receiver, comprising:

acquiring long term satellite tracking data in the remote receiver; the long term satellite tracking data comprises satellite orbit data and/or satellite clock data;

measuring sub-millisecond pseudoranges to a plurality of SPS satellites;

measuring pseudorange rates associated with a plurality of SPS satellites;

calculating an estimated position of the remote receiver using the pseudorange rates and sub-millisecond pseudoranges;

solving an integer millisecond portion of the sub-millisecond pseudoranges using the estimated position to generate full pseudoranges;

computing a position of the remote receiver using the full pseudoranges and the long term satellite tracking data.

11. The method of claim 10, wherein the step of calculating the position of the remote receiver comprises:

judging whether the current time of the day is available or not;

if the precise current time of day is not available, the position of the remote receiver is calculated using a time-independent navigation model.

12. The method of claim 11, wherein the step of calculating the position of the remote receiver comprises:

obtaining an estimated value of the current time of the day;

associating said sub-millisecond pseudoranges with a plurality of position and time variables using said long term satellite tracking data, said time of day estimate and said estimated position; and

solving for one or more of the position and time variables to determine a position of the remote receiver.

13. An apparatus for determining a position, comprising:

a memory for storing long term satellite tracking data, said long term satellite tracking data comprising satellite orbit data and/or satellite clock data;

a satellite signal receiver for detecting Satellite Positioning System (SPS) satellites and determining pseudoranges to said detected SPS satellites; and

a processor for computing a position using said pseudoranges and said long term satellite tracking data;

the satellite signal receiver is configured to detect the SPS satellites using at least one of: a) acquiring assistance data calculated using a previously calculated position; b) and (6) blind searching.

14. The apparatus of claim 13, further comprising:

a communications transceiver for receiving the long term satellite tracking data from a server.

15. The apparatus of claim 13, wherein the satellite signal receiver is configured to:

measuring sub-millisecond pseudoranges to the detected SPS satellites;

decoding a current time of week (TOW) value from at least one of said detected SPS satellites; and

solving an integer millisecond portion of the sub-millisecond pseudorange to generate the pseudorange using the TOW value.

16. The apparatus of claim 13, wherein the satellite signal receiver is configured to:

measuring sub-millisecond pseudoranges to at least one of the detected SPS satellites;

measuring a pseudorange rate associated with at least one of said detected SPS satellites;

calculating an estimated position of the remote receiver using the pseudorange rates and sub-millisecond pseudoranges; and

solving an integer millisecond portion of the sub-millisecond pseudoranges using the estimated position to generate the pseudoranges.

17. The apparatus of claim 16, wherein the processor is configured to:

obtaining an estimated value of the current time of the day;

associating said sub-millisecond pseudoranges with a plurality of position and time variables using said long term satellite tracking data, said time of day estimate and said estimated position;

solving for one or more of the position and time variables to determine the position.

18. The apparatus of claim 13, wherein the satellite signal receiver is configured to:

measuring sub-millisecond pseudoranges to the detected SPS satellites;

selecting a priori positions from a position space; and

solving an integer millisecond portion of the sub-millisecond pseudoranges using the prior position to generate the pseudoranges.

19. The apparatus of claim 18, wherein the processor is configured to:

obtaining an estimated value of the current time of the day;

associating said sub-millisecond pseudoranges with a plurality of position and time variables using said long term satellite tracking data, said time of day estimate and said a priori position; and

solving for one or more of the position and time variables to determine the position.