WO2011046455A1

WO2011046455A1 - An apparatus and method for determining a position of an object

Info

Publication number: WO2011046455A1
Application number: PCT/NZ2010/000205
Authority: WO
Inventors: Timothy Christopher Anthony Molteno
Original assignee: University of Otago
Current assignee: University of Otago
Priority date: 2009-10-13
Filing date: 2010-10-13
Publication date: 2011-04-21
Anticipated expiration: 2012-04-13

Abstract

A method (300) and system for determining a position of an object is provided. The method (300) comprises receiving GPS data from two or more satellites (301). An actual signal characteristic associated with the GPS data is then determined (302). A set of signal characteristics being of a same type as the actual signal characteristic is computed (303) from a set of receiver parameters (308). The set of receiver parameters (308) has estimated positions for the object. The actual signal characteristic is compared to the set of signal characteristics of the same type (304) to determine at least one similar signal characteristic from the set of signal characteristics which is substantially the same as or close to the actual signal characteristic (305). The receiver parameters used to compute each of the similar signal characteristics is also determined (306). The position of the object is approximate to one of the estimated positions of the receiver parameters used to compute each of the similar signal characteristics.

Description

AN APPARATUS AND METHOD FOR DETERMINING A POSITION

OF AN OBJECT

Field of the invention

The present invention relates to an apparatus and method for determining a position of an object.

This application claims priority from United States provisional application 61 /251147 filed 13 October 2009. Subject matter described in the provisional application is incorporated herein by reference.

Background of the invention In a traditional Global Positioning System (GPS), the position of a GPS receiver can be determined using the received information from a plurality of GPS satellites. Typically, traditional GPS systems would require navigation messages from four different satellites in order to determine the location of the receiver. Each GPS satellite transmits a navigation message that includes the time the message was transmitted and the precise orbital information of the satellite (the ephemens). The GPS satellites transmit the messages to the receiver substantially at the speed of light (~3 x 10⁸ ms^"1). The satellites transmit navigation messages every 30 seconds. From the navigation message, the GPS receiver determines the time the navigation message was transmitted from the satellite. The receiver then compares that information to a local clock. The distance between the receiver and the satellite can be determined from the time difference between when the message was transmitted by the satellite and when the message was received by the receiver.

The GPS receiver also determines the ephemeris information from the navigation message. The ephemeris information provides the location of the satellite when the navigation message was transmitted. Combining the information of the distance between the receiver and the satellites and the location of each satellite, the position of the receiver can be determined. Common techniques for determining the location of the receiver from a plurality of satellites includes a least-squares approach.

Using the LI civilian band (at -1.57 GH%), the time to obtain the first fix on the position of the receiver typically exceeds 30 seconds, which is the repeat time of the satellite navigation messages. It is an object of the present invention to provide a technique for determining the position of the receiver using only a segment of the satellites' navigation message.

Additionally and/ or alternatively, it is an object of the present invention to provide the public with a useful choice.

Summary of the invention

The present invention provides a method for determining a position of an object, wherein the object includes, or is in communication with, a Global Positioning System (GPS) receiver, the method comprising: receiving GPS data from two or more satellites; determining an actual signal characteristic associated with the GPS data; computing a set of signal characteristics, the set of signal characteristics being of a same type as the actual signal characteristic, and the set of signal characteristics computed from a set of receiver parameters, the set of receiver parameters including estimated positions for the object; and comparing the actual signal characteristic to the computed set of signal characteristics of the same type to determine at least one similar signal characteristic from the set of signal characteristics which is substantially the same as or close to the actual signal characteristic, and to determine the receiver parameters used to compute each of the similar signal characteristics; wherein the position of the object is approximate to one of the estimated positions of the receiver parameters used to compute each of the similar signal characteristics.

The present invention further provides an apparatus in communication with an object, wherein the apparatus is used for determining a position of the object and is in communication with a Global Positioning System (GPS) receiver for receiving GPS data from two or more satellites, the apparatus comprising a processor for: determining an actual signal characteristic associated with the GPS data; computing a set of signal charactenstics, the set of signal characteristics being of a same type as the actual signal characteristic, and computing the set of signal characteristics from a set of receiver parameters, the set of receiver parameters including estimated positions for the object; and comparing the actual signal characteristic to the computed set of signal

characteristics of the same type to determine at least one similar signal characteristic from the set of signal characteristics which is substantially the same as or close to the actual signal characteristic, and to determine the estimated position used to compute each of the similar signal characteristics wherein the position of the object is

approximate to one of the estimated positions of the receiver parameters used to compute each of the similar signal characteristics.

An aspect of the present invention broadly consists in a method for determining a position of an object, wherein the object includes, or is in communication with, a Global Positioning System (GPS) receiver, the method comprising:

receiving GPS data from two or more satellites;

determining at least one actual signal characteristic associated with the GPS data; computing at least one set of signal characteristics,

at least one of the at least one set of signal characteristics is of a same . type as at least one of the at least one actual signal characteristics, and the at least one set of signal characteristics is computed from a set of receiver parameters, the set of receiver parameters includes estimated positions for the object; and

comparing each of the at least one of the actual signal characteristic to the set of signal characteristics of the same type to determine at least one signal characteristic from the set of signal characteristics which are substantially the same or close to the actual signal characteristic, and to determine the estimated position used to compute each of the at least one of the signal characteristics; wherein the position of the object is one of the estimated positions used to compute each of the at least one of the signal characteristics. The term "comprising" as used in this specification means "consisting at least in part of; that is to say when interpreting statements in this specification which include "comprising", the features prefaced by this term in each statement all need to be present but other features can also be present. Related terms such as "comprise" and

"comprised" are to be interpreted in a similar manner.

Preferably, the method includes optimizing the estimated positions used to compute each of the at least one of the signal characteristics to determine the position of the object. Preferably the step of optimizing involves a space-time optimization algorithm. Preferably, the step of optimizing involves a Nelder-Meade optimization algorithm.

Additionally and/or alternatively, the step of optimizing involves Monte-Carlo methods, Conjugate-gradient methods, Powell's method and/ or Markov chain Monte-Carlo methods. Preferably, the set of receiver parameters include local time and local clock offset of the - object.

Preferably, at least one of the at least one set of signal characteristics is computed using a set of initial receiver parameters. Preferably, the set of initial receiver parameters are obtained from a database. Preferably, the database is external to the object.

Preferably, the type of at least one GPS data characteristic is Doppler shift information. Preferably, the type of at least one GPS data characteristic is codephase information. Preferably, an actual signal characteristic of one type is compared to the corresponding set of signal characteristics before computing the set of signal characteristics corresponding to an actual signal characteristic of another type. Preferably, the set of signal characteristics corresponding to the signal characteristic of the one type is computed from the set of initial receiver parameters. Preferably, the step of comparing the actual signal characteristic to the corresponding set of signal characteristics of the one type reduces the number of estimated positions for the object in the set of receiver parameters used to compute the corresponding set of signal characteristics of the one type. Preferably, the set of signal characteristics corresponding to the signal

characteristic of the other type is computed from a set of receiver parameters which is a subset of the set of receiver parameters, wherein the subset of the set of receiver parameters are calculated using the reduced number of estimated positions of the object used to compute the corresponding set of signal characteristics of the one type. Preferably, the one type is Doppler shift information and the other type is codephase information. Alternatively, the one type is codephase information and the other type is Doppler shift information.

Alternatively, the sets signal characteristics of the one and the other types are computed from a same set of receiver parameters. Preferably, the same set of receiver parameters is the initial set of receiver parameters.

Preferably, the step of comparing to determine at least one signal characteristic from the set of signal characteristics which are substantially the same or close to the actual signal characteristic involves a least squares algorithm.

An additional and/ or alternative aspect of the present invention broadly consists in an apparatus in communication with an object, wherein the apparatus is used for determining a position of the object and is in communication with a Global Positioning System (GPS) receiver for receiving GPS data from two or more satellites, the apparatus comprising a processor for:

at least one of the at least one set of signal characteristics is of a same type as at least one of the at least one actual signal characteristics, and computing the at least one set of signal characteristics from a set of receiver parameters, the set of receiver parameters includes estimated positions for the object; and

comparing each of the at least one of the actual signal characteristic to the set of signal characteristics of the same type to determine at least one signal characteristic from the set of signal characteristics which are substantially the same or close to the actual signal characteristic, and to determine the estimated position used to compute each of the at least one of the signal characteristics wherein the position of the object is one of the estimated positions used to compute each of the at least one of the signal characteristics.

Preferably, the GPS receiver is internal to the apparatus. Alternatively, the GPS receiver is external to the apparatus.

Preferably, the processor optimizes the estimated positions used to compute each of the at least one of the signal characteristics to determine the position of the object.

Preferably the processor uses a space- time optimization algorithm to optimize the estimated positions. Preferably, the processor uses a Nelder-Meade optimization algorithm to optimize the estimated positions. Additionally and/ or alternatively, the processor uses Monte-Carlo methods, Conjugate-gradient methods, Powell's method and/ or Markov chain Monte-Carlo methods to optimize the estimated positions.

Preferably, the set of receiver parameters include local time and local clock-offset of the , object.

Preferably, the type of at least one GPS data characteristic is Doppler shift information. Preferably, the type of at least one GPS data characteristic is codephase information.

Preferably, the processor compares an actual signal characteristic of one type to the corresponding set of signal characteristics before the processor computes the set of signal characteristics corresponding to an actual signal characteristic of another type. Preferably, the processor computes the set of signal characteristics corresponding to the signal characteristic of the one type from the set of initial receiver parameters. Preferably, the step of comparing the actual signal characteristic to the corresponding set of signal characteristics of the one type reduces the number of estimated positions for the object in the set of receiver parameters used to compute the corresponding set of signal characteristics of the one type. Preferably, the processor computes the set of signal characteristics corresponding to the signal characteristic of the other type from a set of receiver parameters which is a subset of the set of receiver parameters, wherein the subset of the set of receiver parameters are calculated using the reduced number of estimated positions of the object used to compute the corresponding set of signal characteristics of the one type.

Preferably, the one type is Doppler shift information and the other type is codephase information. Alternatively, the one type is codephase information and the other type is Doppler shift information. Alternatively, the sets of signal characteristics of the one and the other types are computed from a same set of receiver parameters. Preferably, the same set of receiver parameters is the initial set of receiver parameters.

Preferably, the processor uses a least squares algorithm in the step of comparing to determine at least one signal characteristic from the set of signal characteristics which are substantially the same or close to the actual signal characteristic.

This invention may also be said broadly to consist in the parts, elements and features referred to or indicated in the specification of the application, individually or collectively, and any or all combinations of any two or more said parts, elements or features, and where specific integers are mentioned herein which have known equivalents in the art to which this invention relates, such known equivalents are deemed to be incorporated herein as if individually set forth. As used herein, the term "and/ or" means "and" or "or", or where the context allows both.

The invention consists in the foregoing and also envisages constructions of which the following gives examples only.

Brief description of the drawings

Preferred embodiments of the invention will now be described, by way of non-limiting example, with reference to the accompanying drawings, in which: Figure 1 is a general overview of a GPS system in which the invention is configured to operate,

Figure 2 shows a block diagram of some of the components of the system and apparatus according to a preferred embodiment,

Figure 3 shows a block diagram of a preferred form method of the invention,

Figure 4 shows a block diagram of another preferred form method of the invention,

Figure 5 shows a Doppler least squares intensity map of the mean Doppler shift for 900 square degrees centred on the receiver location,

Figure 6 shows a codephase least squares intensity map for 100 square degrees centred on the receiver location,

Figure 7 shows a block diagram of another preferred form method of the invention,

Figure 8 shows a block diagram of another preferred form method of the invention.

Detailed description of preferred embodiments

The present invention is directed to a method for determining a position of an object 101 associated with a Global Positioning Satellite (GPS) receiver 102. The object 101 may be a variety of things, which include an equipment, a vehicle, a cellular device, or a person. Referring to figures 1 and 2, the object 101 within a GPS environment 100 includes the GPS receiver 102 and a processor 104. Alternatively, where appropriate, the GPS receiver 102 is external to the object 101 and in communication with the object 101.

The receiver 102 contains a local clock. A segment of the navigation message from a GPS satellite 108A, 108B is digitized by the GPS receiver 02. The start of this sequence of GPS data is measured at the receiver's 102 local clock as The process of signal acquisition in the local receiver 102 involves the measurement of different types of signals characteristics, which include a codephase (δ¹) and Doppler-shift of the spread-spectrum pseudorandom number (PRN) code for each visible satellite signal 108A, 108B. The PRN sequence from each satellite repeats every millisecond and contains 1023 binary numbers in a pseudorandom sequence. The relationship between the local clock at the receiver 102 (/) and the GPS system clock (T) is:

where //is the clock offset at the receiver 102.

Each satellite 08A, 108B transmits a signal at intervals of τ.^' The system time that GPS data from the satellite 108A, 108B is sent is given by:

where T,is an arbitrary start time, chosen so that the

are integers.

The system time that the navigation message reaches the receiver 102 ^is given by:

where is the measured time for the start of the sequence at the receiver 102, and t_u is the clock offset at the receiver 102.

The GPS receiver 02 measures the codephase and the Doppler shift of the signals embedded in a short (typically a few milliseconds) segment of satellite data. This system is similar to the method of exact fractions from interferometry; only the fractional part of the codephase for the signal from each satellite 108A, 108B and Doppler shift information are known.

The codephase is the phase in the local receiver 102 at which the PRN code from a satellite is received. There are several well-known techniques for recovering the codephase. In the preferred embodiment of the system, parallel codephase recovery using Fourier Transforms is used. Other codephase recovery techniques include parallel frequency space search and serial search. The codephase is measured relative to the start of the sequence measured at the receiver's 102 local clock. The codephase is a number between zero and one. Zero indicates that the PRN sequence starts exacdy at

indicates that the PRN sequence for that satellite starts exactly at milliseconds, where τ is the PRN

sequence repeat time.

The system time at the receiver 102 when the navigation message from the

satellite 108A, 108B is received is given by:

The signal transmission time for each satellite 108A, 108B is given by:

Converting to a local clock value, the above expression for the signal transmission time becomes:

From the above expression, the system offset time (tj is no longer important.

Using the signal transmission time, the distance from the

satellite 108A, 108B to the receiver 102 can be determined (from the ephermis information). The distance 110A, 110B between the receiver and the

satellite 108A, 108B is the product of the transmission time of the navigation message from the

satellite 108A, 108B to the receiver 102 and the velocity at which the navigation message was transmitted. The navigation message is transmitted to the receiver 102 substantially at the speed of light, c. Assume that, at time /, the position of the satellite is and the unknown location of the receiver 12 is

At any given time, there are only a small number of positions near the earth's surface that will have the received codephases all at the same time. Finding the location of the receiver 102 from these fractional codephases is an inverse problem. The frequency and the phase information is used to solve the inverse problem of finding the position and local time of the receiver 102 given measurements of the codephase and Doppler shift. The present invention solves the forward problem, which assumes the position, local time and local clock offset of the receiver 102 to be known.

The present invention assumes that the position, local time and local clock offset of the receiver 102 in the above equation are known. These assumed values of the receiver parameters are obtained from a database 106. Using estimated values of the position, local time and local clock offset of the receiver 102, estimated signal characteristics such as the fractional part and the integral part M' of the codephase can be determined.

These estimated signal characteristics are computed by the processor 104.

The relative fractional codephase, is the difference (modulo τ) between the

fractional codephases

for two satellites. The forward problem is the calculation of from the receiver position r₀, and the two estimated satellite positions,

The least squares measure for relative fractional codephase, , is

Figure 3 shows a general block diagram of the method 300 of the present invention. The first step 301 of the method of the present invention is receiving GPS data from two or more satellites 108A, 108B. The GPS data is a portion of the navigation message transmitted from a satellite 108A, 108B.

The second step 302 is determining at least one actual signal characteristic associated with the GPS data. The types of actual signal characteristics include Doppler shift and codephase information. The third step 303 is computing at least one set of signal characteristics. At least one of the at least one set of signal characteristics is of a same type as at least one of the at least one actual signal characteristics. The at least one set of signal characteristics is computed from a set of receiver parameters 308. The set of receiver parameters 308 include estimated positions, local time and local clock offset of the object 101. Those parameters 308 are stored and can be obtained from database 106.

The fourth step 304 is comparing each of the at least one of the actual signal characteristic to the set of signal characteristics of the same type. The fifth step 305 is to determine at least one signal characteristic from the set of signal characteristics which are substantially the same or close to the actual signal characteristic. The sixth step 306 is to determine the estimated position used to compute each of the at least one of the signal characteristics. The position of the object 101 is or is approximate to one of the estimated positions used to compute each of the at least one of the signal characteristics. Preferably, the receiver parameters that are used to compute those estimated signal characteristics are stored in database 106.

Additionally, there could be implemented into the system a seventh step 307 of optimizing the receiver parameters. Step 307 preferably includes a full four-dimensional space-time optimisation using a Nelder-Meade optimisation algorithm. This yields an estimate for the receiver position as well as the local time. Additionally and/ or alternatively, the step of optimizing involves Monte-Carlo methods, Conjugate-gradient methods, Powell's method and/or chain Monte-Carlo methods. Referring to Figure 4, the actual Doppler shift information is compared to the corresponding set of Doppler shift information in step 404 before computing the set of codephase information corresponding to the actual codephase information in step 410. The set of Doppler shift information is computed in step 410 from the set of initial receiver parameters 308. The step 402 of comparing the actual Doppler shift information to the corresponding set of Doppler shift information reduces the number of estimated positions for the object in the set of receiver, parameters 308 used to compute the set of Doppler shift information. The set of signal characteristics corresponding to the codephase information is computed in step 410 from the reduced number of receiver parameters obtained from step 404.

Figure 5 shows the Doppler least squares estimator as plotted over region of 30 degrees in latitude and 30 degrees in longitude. This shows a global and local minimum at the receiver location. This estimate is sufficient to locate the receiver within a small enough region. A more accurate position of the receiver is obtained by minimizing the relative codephase estimator.

Figure 6 shows the relative codephase estimator plotted for six visible satellites over a region ten degrees in width and height centred at the actual receiver location. The search for the global miriimum is a complex nonlinear minimisation problem. However, the Doppler search is sufficiently accurate to place the receiver within the central local minimum region and the relative codephase least squares estimator can be easily minimised once this is known.

The local minimum in the relative codephase least-squares measure can be

approximated by a quadratic function of the position, velocity and local time.

Position, velocity and time solutions can be obtained using a similar time separated measurement scheme, the receiver position and its velocity can be determined by forming the least squares measure from the forward problem.

By way of example, referring to Figure 7, the actual codephase information is compared to the corresponding set of codephase information in step 412 before computing the set of Doppler shift information corresponding to the actual Doppler shift information in step 401. The set of codephase information is computed in step 410 from the set of initial receiver parameters 308. The step 412 of comparing the actual codephase information to the corresponding set of codephase information reduces the number of estimated positions for the object in the set of receiver parameters used to compute the set of codephase information. The set of signal characteristics corresponding to the Doppler shift information is computed in step from the reduced number of receiver parameters from step 416.

By way of further example, referring to Figure 8, the sets signal characteristics of the one and the other types are computed from a same set of receiver parameters.

Preferably, the same set of receiver parameters is the initial set of receiver parameters.

The foregoing describes the invention including preferred forms thereof. Modifications and improvements that would be obvious to those skilled in the art are intended to be incorporated in the scope hereof, as defined by the accompanying claims.

Claims

CLAIMS:

1. A method for determining a position of an object, wherein the object includes, or is in communication with, a Global Positioning System (GPS) receiver, the method comprising:

receiving GPS data from two or more satellites;

determining an actual signal characteristic associated with the GPS data;

computing a set of signal characteristics,

the set of signal characteristics being of a same type as the actual signal characteristic, and

the set of signal characteristics computed from a set of receiver parameters, the set of receiver parameters including estimated positions for the object; and

comparing the actual signal characteristic to the computed set of signal characteristics of the same type

to determine at least one similar signal characteristic from the set of signal characteristics which is substantially the same as or close to the actual signal characteristic, and

to determine the receiver parameters used to compute each of the similar signal characteristics;

wherein the position of the object is approximate to one of the estimated positions of the receiver parameters used to compute each of the similar signal characteristics.

2. The method according to claim 1 , further comprising the step of optimizing the estimated positions used to compute each of the at least one of the signal characteristics . to determine the position of the object.

3. The method according to claim 2, wherein the step of optimizing involves a space-time optimization algorithm.

4. The method according to claim 2 or 3, wherein the step of optimizing involves one or a combination of a Nelder-Meade optimization algorithm, Monte-Carlo methods, Conjugate-gradient methods, Powell's method and/or Markov chain Monte- Carlo methods.

5. The method according to any one of claims 1 to 4, wherein the set of receiver parameters further includes local time and/ or local clock offset of the object.

6. The method according to any one of claims 1 to 5, wherein the set of signal characteristics is computed using a set of initial receiver parameters.

7. The method according to claim 6, wherein the set of initial receiver parameters is obtained from a database.

8. The method according to claim 7, wherein the database is external to the object.

9. The method according to any one of claims 1 to.8, wherein the type of the GPS data characteristic is Doppler shift information.

10. The method according to any one of claims 1 to 8, wherein the type of the GPS data characteristic is codephase information.

11. The method according to any one of claims 1 to 8, wherein two actual signal characteristics of a first and second type respectively are determined from the GPS data, and two corresponding sets of signal characteristics of the first and second type respectively are computed.

12. The method according to claim 11 , wherein the receiver parameters used to compute the two sets signal characteristics of the first and the second types are the same.

13. The method according to claim 1 , wherein the set of signal characteristics of the second type is computed using the receiver parameters that is used to compute the at least one similar signal characteristics of the first type that is substantially the same as or close to the actual signal characteristic of the first type.

14. The method according to any one of claims 11 to 13, wherein the first type is Doppler shift information and the second type is codephase information.

15. The method according to any one of claims 11 to 13, wherein the first type is codephase information and the second type is Doppler shift information.

16. The method according to any one of claims 1 to 15, wherein the step of comparing to determine at least one similar signal characteristic from the set of signal characteristics which are substantially the same as or close to the actual signal characteristic involves a least squares algorithm.

17. An apparatus in communication with an object, wherein the apparatus is used for determining a position of the object and is in communication with a Global

Positioning System (GPS) receiver for receiving GPS data from two or more satellites, the apparatus comprising a processor for:

determining an actual signal characteristic associated with the GPS data;

computing a set of signal characteristics,

computing the set of signal characteristics from a set of receiver parameters, the set of receiver parameters including estimated positions for the object; and

to determine the estimated position used to compute each of the similar signal characteristics

18. The apparatus according to claim 17, wherein the GPS receiver is internal to the apparatus.

19. The apparatus according to claim 17, wherein the GPS receiver is external to the apparatus.

20. The apparatus according to any one of claims 17 to 19, wherein the processor optimizes the estimated positions used to compute the signal characteristics to determine the position of the object.

21. The apparatus according to claim 20, wherein the processor uses a space-time optimization algorithm to optimize the estimated positions.

22. The apparatus according to claim 20 or 21 , wherein the processor uses one or a combination of a Nelder-Meade optimization algorithm, Monte-Carlo methods, Conjugate-gradient methods, Powell's method and/or Markov chain Monte-Carlo methods to optimize the estimated positions.

23. The apparatus according to any one of claims 17 to 22, the set of receiver parameters include local time and local clock offset of the object.

24. The apparatus according to any one of claims 17 to 23, wherein the set of signal characteristics is computed using a set of initial receiver parameters.

25. The apparatus according to 24, wherein the set of initial receiver parameters is obtained from a database.

26. The apparatus according to 25, wherein the database is external to the object.

27. The apparatus according any one of claims 17 to 26, the type of the GPS data characteristic is Doppler shift information.

28. The apparatus according any one of claims 17 to 26, the type of the GPS data characteristic is codephase information.

29. The apparatus according any one of claims 17 to 26, wherein two actual signal characteristics of a first and second type respectively are determined from the GPS data, and two corresponding sets of signal characteristics of the first and second type respectively are computed.

30. The apparatus according to claim 29, wherein the receiver parameters used to compute the two sets signal characteristics of the first and the second types are the same.

31 . The apparatus according to claim 29, wherein the set of signal characteristics of the second type is computed using the receiver parameters that is used^' to compute the at least one similar signal characteristics of the first type that is substantially the same as or close to the actual signal characteristic of the first type.

32. The apparatus according to any one of claims 29 to 31 , wherein the first type is Doppler shift information and the second type is codephase information.

33. The apparatus according to any one of claims 29 to 31, wherein the first type is codephase information and the second type is Doppler shift information.

34. The apparatus according to any one of claims 17 to 33, wherein the step of comparing to determine at least one similar signal characteristic from the set of signal characteristics which are substantially the same as or close to the actual signal characteristic involves a least squares algorithm.