CARRIER-PHASE SMOOTHING OF CODE-PHASE MEASUREMENTS

An example of a method of determining a position of a device includes: receiving, with a receiver of the device, a signal from a reference emitter; obtaining a code phase measurement of the signal; obtaining a carrier phase measurement of the signal; calculating an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement; calculating a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity; and determining the position of the device based, at least in part, on the carrier phase smoothed estimate of the code phase.

BACKGROUND

Satellite positioning systems (SPSs) broadcast positioning signals from a constellation of satellites that can be used by a device with an SPS receiver to determine the position and/or velocity of the device. Example SPS include Global Positioning System (GPS), Global Navigation Satellite System (GNSS), Galileo, GLONASS, Beidou (Compass), etc. Each satellite in an SPS broadcasts signals using at least one carrier frequency. For example, GPS uses two carrier frequencies: 1575.4 MHz and 1227.6 MHz. Other SPSs may use more than two carrier frequencies or just one carrier frequency.

Signals broadcast from an SPS satellite are conventionally modulated with a pseudo-random code (PRC). The PRC may also be referred to as a spreading code because it spreads the frequency spectrum of the signal over a particular range of frequencies (e.g., 1 MHz bandwidth). An SPS receiver receives the signal from the SPS satellite and determines the time of arrival (TOA) of the signal by correlating the received signal with a locally generated PRC. In this way, the distance between the SPS receiver and the satellite can be determined by, for example, determining the transit time of the signal (the difference in time between when the signal was received and when the satellite transmitted the signal) and multiplying that transit time by the speed of light. The distance between the satellite and the receiver is referred to as the pseudorange or a code phase measurement. Due to the limited bandwidth of the PRC (e.g., 1 MHz) and noise, the accuracy of the pseudorange measurement is on the order of one meter. However, if a carrier phase measurement is performed and used to determine the location of the receiver, the accuracy of the location of the receiver can be increased.

SUMMARY

An example of a method of determining a position of a device includes: receiving, with a receiver of the device, a signal from a reference emitter; obtaining a code phase measurement of the signal; obtaining a carrier phase measurement of the signal; calculating an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement; calculating a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity; and determining the position of the device based, at least in part, on the carrier phase smoothed estimate of the code phase.

Implementations of such a method may include one or more of the following features. The intermediate quantity may include a difference between the code phase measurement and the carrier phase measurement. The robust aggregation of the intermediate quantity may be a median value of the intermediate quantity. The method may further include determining the median value of the intermediate quantity using a min heap data structure and a max heap data structure. A minimum value of the min heap data structure may be greater than or equal to a maximum value of the max heap data structure, and a number of values of the min heap data structure and a number of values of the max heap data structure differs by no more than one. Determining the median value of the intermediate quantity may include inserting the intermediate quantity into the min heap data structure in response to a determination that the intermediate quantity is greater than the minimum value of the min heap data structure; and inserting the intermediate quantity into the max heap data structure in response to a determination that the intermediate quantity is less than the maximum value of the max heap data structure. The method may further include removing the minimum value from the min heap data structure and inserting the minimum value into the max heap data structure in response to a determination that the number of values of the min heap data structure is greater than the number of values of the max heap data structure by more than one; and removing the maximum value from the max heap data structure and inserting the maximum value into the min heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure by more than one. The method may further include setting the median value of the intermediate quantity equal to the maximum value of the max heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure; setting the median value of the intermediate quantity equal to the minimum value of the min heap data structure in response to a determination that the number of values of min heap data structure is greater than the number of values of the max heap data structure; and setting the median value of the intermediate quantity equal to a mean value of the maximum value of the max heap data structure and the minimum value of the min heap data structure in response to a determination that the number of values of the max heap data structure is equal to the number of values of the min heap data structure. Calculating the carrier phase smoothed estimate of the code phase of the signal may include adding the carrier phase measurement to the robust aggregation of the intermediate quantity.

An example of a device for determining a position of the device includes: a wireless receiver for wirelessly receiving a signal from a reference emitter; and a processor, communicatively coupled to the wireless receiver, configured to: obtain a code phase measurement of the signal; obtain a carrier phase measurement of the signal; calculate an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement; calculate a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity; and determine the position of the device based, at least in part, on the carrier phase smoothed estimate of the code phase.

Implementations of such a device may include one or more of the following features. The intermediate quantity may include a difference between the code phase measurement and the carrier phase measurement. The processor may be configured to determine the robust aggregation of the intermediate quantity by determining a median value of the intermediate quantity. The device may further include a memory configured to store a min heap data structure and a max heap data structure. The processor may be further configured to determine the median value of the intermediate quantity using the min heap data structure and the max heap data structure. A minimum value of the min heap data structure may be greater than or equal to a maximum value of the max heap data structure, and a number of values of the min heap data structure and a number of values of the max heap data structure differs by no more than one. The processor may be further configured to determine the median value of the intermediate quantity by: inserting the intermediate quantity into the min heap data structure in response to a determination that the intermediate quantity is greater than the minimum value of the min heap data structure; and inserting the intermediate quantity into the max heap data structure in response to a determination that the intermediate quantity is less than the maximum value of the max heap data structure. The processor may be further configured to: remove the minimum value from the min heap data structure and insert the minimum value into the max heap data structure in response to a determination that the number of values of the min heap data structure is greater than the number of values of the max heap data structure by more than one; and remove the maximum value from the max heap data structure and insert the maximum value into the min heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure by more than one. The processor may be further configured to: set the median value of the intermediate quantity equal to the maximum value of the max heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure; set the median value of the intermediate quantity equal to the minimum value of the min heap data structure in response to a determination that the number of values of the min heap data structure is greater than the number of values of the max heap data structure; and set the median value of the intermediate quantity equal to a mean value of the maximum value of the max heap data structure and the minimum value of the min heap data structure in response to a determination that the number of values of the max heap data structure is equal to the number of values of the min heap data structure. The processor may be further configured to calculate the carrier phase smoothed estimate of the code phase of the signal by adding the carrier phase measurement to the robust aggregation of the intermediate quantity.

An example of a device for determining a position of the device includes receiving means for wirelessly receiving a signal from a reference emitter; and first obtaining means for obtaining a code phase measurement of the signal; second obtaining means for obtaining a carrier phase measurement of the signal; calculating means for calculating an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement; smoothing means for calculating a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity; and positioning means for determining the position of the device based, at least in part, on the carrier phase smoothed estimate of the code phase.

Implementations of such a device may include one or more of the following features. The intermediate quantity may include a difference between the code phase measurement and the carrier phase measurement. The robust aggregation of the intermediate quantity may be a median value of the intermediate quantity. The device may further include: storing means for storing a min heap data structure and a max heap data structure; and determining means for determining the median value of the intermediate quantity using the min heap data structure and the max heap data structure, wherein a minimum value of the min heap data structure is greater than or equal to a maximum value of the max heap data structure, and wherein a number of values of the min heap data structure and a number of values of the max heap data structure differs by no more than one. The determining means may include: first inserting means for inserting the intermediate quantity into the min heap data structure in response to a determination that the intermediate quantity is greater than the minimum value of the min heap data structure; and second inserting means for inserting the intermediate quantity into the max heap data structure in response to a determination that the intermediate quantity is less than the maximum value of the max heap data structure. The determining means may further be for: removing the minimum value from the min heap data structure and inserting the minimum value into the max heap data structure in response to a determination that the number of values of the min heap data structure is greater than the number of values of the max heap data structure by more than one; and removing the maximum value from the max heap data structure and inserting the maximum value into the min heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure by more than one. The determining means may further be for: setting the median value of the intermediate quantity equal to the maximum value of the max heap data structure in response to a determination that the number of values of the max heap data structure is larger than the number of values of the min heap data structure; setting the median value of the intermediate quantity equal to the minimum value of the min heap data structure in response to a determination that the number of values of min heap data structure is larger than the number of values of the max heap data structure; and setting the median value of the intermediate quantity equal to a mean value of the maximum value of the max heap data structure and the minimum value of the min heap data structure in response to a determination that the number of values of the max heap data structure is equal to the number of values of the min heap data structure. The smoothing means may further be for adding the carrier phase measurement to the robust aggregation of the intermediate quantity.

An example of a non-transitory processor-readable storage medium includes processor-readable instructions configured to cause a processor of a device to: receive a signal from a reference emitter; obtain a code phase measurement of the signal; obtain a carrier phase measurement of the signal; calculate an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement; calculate a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity; and determine the position of the device based, at least in part, on the carrier phase smoothed estimate of the code phase.

Implementations of such a non-transitory processor-readable storage medium may include one or more of the following features. The intermediate quantity may include a difference between the code phase measurement and the carrier phase measurement; and the instructions configured to cause the processor to calculate the carrier phase smoothed estimate of the code phase of the signal may include instructions configured to add the carrier phase measurement to the robust aggregation of the intermediate quantity. The robust aggregation of the intermediate quantity may be a median value of the intermediate quantity. The non-transitory processor-readable storage medium may further include instructions configured to cause the processor to determine the median value of the intermediate quantity using a min heap data structure and a max heap data structure, wherein a minimum value of the min heap data structure is greater than or equal to a maximum value of the max heap data structure, and wherein a number of values of the min heap data structure and a number of values of the max heap data structure differs by no more than one. The instructions configured to cause the processor to determine the median value of the intermediate quantity may include instructions configured to cause the processor to: insert the intermediate quantity into the min heap data structure in response to a determination that the intermediate quantity is greater than the minimum value of the min heap data structure; and insert the intermediate quantity into the max heap data structure in response to a determination that the intermediate quantity is less than the maximum value of the max heap data structure. The instructions configured to cause the processor to determine a median value of the intermediate quantity may further include instructions configured to cause the processor to: remove the minimum value from the min heap data structure and insert the minimum value into the max heap data structure in response to a determination that the number of values of the min heap data structure is greater than the number of values of the max heap data structure by more than one; and remove the maximum value from the max heap data structure and insert the maximum value into the min heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure by more than one. The instructions configured to cause the processor to determine the median value of the intermediate quantity may include instructions configured to cause the processor to: set the median value of the intermediate quantity equal to the maximum value of the max heap data structure in response to a determination that the number of values of the max heap data structure is greater than the number of values of the min heap data structure; set the median value of the intermediate quantity equal to the minimum value of the min heap data structure in response to a determination that the number of values of min heap data structure is greater than the number of values of the max heap data structure; and set the median value of the intermediate quantity equal to the mean value of the maximum value of the max heap data structure and the minimum value of the min heap data structure in response to a determination that the number of values of the max heap data structure is equal to the number of values of the min heap data structure.

Items and/or techniques described herein may provide fast and robust smoothing of a code phase measurement of a signal using the carrier phase measurement of the signal, as well as other capabilities not mentioned. Additionally, techniques described herein may provide faster access to high precision positioning solutions. Other capabilities may be provided and not every implementation according to the disclosure must provide any, let alone all, of the capabilities discussed. Further, it may be possible for an effect noted above to be achieved by means other than that noted, and a noted item/technique may not necessarily yield the noted effect.

DETAILED DESCRIPTION

Techniques are discussed herein for fast and robust carrier-phase smoothing of code-phase measurements in a satellite positioning system (SPS). In general, SPS receivers make two types of measurements for each signal received from a satellite of the SPS: code phase measurements and carrier phase measurements. The code phase measurements typically have a noise standard deviation on the order of 1-2 meters. The carrier phase measurements, however, may be much more precise with a noise standard deviation on the order of 1-2 centimeters. The carrier phase measurements can be used to average noise in the code phase measurements in a process known as “smoothing.” The reduced noise code-phase measurement is referred to as a carrier-phase smoothed code phase measurement.

Carrier-phase smoothing of the code-phase measurements using a simple averaging technique is susceptible to erroneous results due to outlier measurements. For example, a single, large outlier measurement may completely corrupt the carrier-phase smoothed code phase measurement. Outlier measurements become particularly problematic in urban environments where many phase measurements made by the receiver can be outliers.

A robust aggregation approach as described herein allows for fast smoothing of the code-phase measurements of the received signals while being less susceptible to outlier measurements as compared to a simple averaging technique. In an example, a carrier phase measurement and a code phase measurement of a signal may be used to calculate an intermediate quantity. For each epoch of the SPS, the phase measurements are made and the intermediate quantity is calculated. The intermediate quantity may be, for example, the difference between the code phase measurement and the carrier phase measurement. A robust aggregation of the intermediate quantity for a current time and multiple previous times is determined. The robust aggregation may be a median value of the intermediate quantities. The carrier phase measurement is added to the robust aggregation value to yield the carrier-phase smoothed code-phase measurement for the current time. This method can be repeated for every epoch of the SPS.

In an example, the median value of the intermediate quantity can be determined using a min heap data structure and a max heap data structure. The two heap data structures are maintained such that the size of the min heap data structure (i.e., the number of values in the min heap data structure) and the size of the max heap data structure (i.e., the number of values in the max heap data structure) differ by no more than one. Additionally, the two heap data structures are maintained such that the minimum value of the min heap data structure is greater than or equal to the maximum value of the max heap data structure.

Using a median value of the intermediate quantity to produce the carrier-phase smoothed code phase measurement allows for a robust code phase measurement that is less susceptible to outlier phase measurements than other aggregation techniques. Moreover, using a min heap data structure and a max heap data structure to determine the median allows the median to be calculated quickly and efficiently. In particular, finding the minimum and/or maximum value of a heap data structure can be performed in constant time and inserting and/or removing an element into a heap data structure can be performed in a time that is logarithmic in the size of the heap.

Referring toFIG. 1, a simplified diagram of an example of a satellite position system (SPS) is shown. An SPS1includes a device10and a constellation of four satellites15-18. The device10includes an antenna11. Each of the satellites15-18emits a signal that is received by the antenna11and used by the device10to determine the position of the device based on the time of arrivals of the signals. For the sake of clarity,FIG. 1illustrates only a single signal12emitted by satellite15. However, while not shown inFIG. 1, the satellites16-18emit signals similar to the signal12and can be received by the device10. Additionally, the constellation of satellites may include more than the four satellites15-18.

The signal12, for purposes of illustrating the carrier phase and code phase, is illustrated as two separate signals: a carrier signal12aand a code signal12b. The carrier signal12ahas a wavelength λcarrierand the code signal12bhas a wavelength λcode, which is greater than the wavelength λcarrier. While not illustrated in detail inFIG. 1, the code signal12bis a pseudo-random code (PRC) signal that repeats with a frequency that corresponds to the wavelength λcode.

The device10includes an SPS receiver that is operably coupled to the antenna11and includes a carrier phase tracking loop for monitoring the carrier phase of the signal12and a delay tracking loop for monitoring the code phase of the signal. The code phase measurement is a determination of how many periods of the code signal12boccur between the satellite15and the antenna11, and the carrier phase measurement is a determination of how many periods of the carrier phase signal12aoccur between the satellite15and the antenna11. Because the wavelength λcode, is greater than the wavelength λcarrier, the carrier phase measurement can be used to smooth the code phase measurement and provide more reliable measurement results. Techniques described herein allow the device10to quickly and robustly perform carrier-phase smoothing of the code phase measurement.

The device10not only makes phase measurements for multiple satellites, but it makes multiple phase measurements over time, which may be stored in a memory of the device10. For a particular satellite the code phase measurement is represented by ρ(t) and the carrier phase measurement is represented by φ(t). These two phase measurements are associated with a time which corresponds to a particular epoch of the SPS. An estimate for the code phase at time t, can be made using the carrier phase measurement and past measurements of the code phase and the carrier phase. Each code phase measurement is calculated by the formula:

where {circumflex over (ρ)}τ(t) is the code phase estimate at time t based on past measurements made at time t−τ, ρ(t−τ) is the code phase measurement at time t−τ, φ(t−τ) is the carrier phase measurement at time t−τ, and φ(t) is the carrier phase measurement at time t. These estimates can be determined for every from 0 to T−1, where T is the number of past and present phase measurements available in memory.

A carrier-phase smoothed code-phase measurement,ρ(t), is determined by taking the median of the multiple code phase measurements, {circumflex over (ρ)}τ(t), as shown by the formula:

All of the past measurements available in memory may be used in calculating the median, or the device10may use only a certain number of phase measurements that are less than a threshold amount of time away. For example, the device may have T measurements stored in memory but only use the most recent T′ measurements, where T′<T.

While examples described herein utilize a median of the code phase estimates to determine the carrier-phase smoothed code-phase measurement, other robust aggregations may be used. Examples of robust aggregation techniques that may be used include a trimmed (truncated) mean, a winsorized mean, or an M-estimator using a Huber loss function or a Tukey bisquare loss function.

To determine the median of the code phase measurements, the device10may instead determine the median of an intermediate quantity that is a function, ƒ(t), of the code phase measurement and the carrier phase measurement at a particular time t. For example, the difference of the code phase measurement and the carrier phase measurement, ƒ(t−τ)=ρ(t−τ)−φ(t−τ), may be used. The device may determine the median of the past values of this intermediate quantity, represented by the formula:

The carrier phase measurement at time t is added to the median value to determine the quantity that is used as the carrier-phase smoothed code phase estimate, as represented by the formula:

Referring toFIG. 2, a block diagram of an example of a device10that may be part of a satellite position system is shown. The device10is a computer system that includes the antenna11, a processor30, a memory31, an SPS receiver33, and a display34. The device10may be a handheld mobile device, such as a mobile phone or smart phone, or a navigation device used by an individual or a vehicle, such as an automobile, boat, or airplane. In the cases where the device10is a mobile device, the device10includes one or more transceivers (not shown) for communicating with a cellular communication network by transmitting wireless signals to cellular base stations, such as wireless base transceiver stations (BTS), Node Bs, evolved NodeBs (eNB), etc. Similarly, device10may include other wireless transceivers (not shown) for transmitting wireless signals to and receiving wireless signals from local transceivers such as Wi-Fi access points (AP), femtocells, Home Base Stations, small cell base stations, Home Node Bs (HNB) or Home eNodeBs (HeNB) and may provide access to a wireless local area network (WLAN, e.g., IEEE 802.11 network), a wireless personal area network (WPAN, e.g., Bluetooth® network or ZigBee® network) or a cellular network (e.g. an LTE network or other wireless wide area network such as those discussed in the next paragraph).

The antenna11receives the wireless signal12from the satellite15, as well as the signals emitted by the other satellites16-18in the SPS1. The SPS receiver33is a wireless receiver for receiving the signal12from the satellite15via the antenna11. The SPS receiver33includes the necessary systems (not shown) for measuring the code phase and carrier phase of the signal12, such as a delay lock loop and a phase lock loop. The SPS1may be a Global Positioning System (GPS), Global Navigation Satellite System (GNSS), Galileo, GLONASS, Beidou (Compass), etc. While examples of SPSs discussed herein are described as being based on satellite based systems, the satellites15-18are one example of a reference emitter that may emit a positioning signal. Other examples of reference emitters include space vehicles that are not in orbit, various aircraft, or ground based emitters, such as cellular network base stations.

The processor30is an intelligent device, e.g., a central processing unit (CPU) such as those made or designed by Qualcomm®, ARM®, Intel® Corporation, or AMD®, a microcontroller, an application specific integrated circuit (ASIC), etc. The memory31is non-transitory, processor-readable memory that stores instructions that may be executed by processor30and includes random access memory (RAM), read-only memory (ROM) and non-volatile memory such as flash memory or solid state storage. The display34may be a liquid-crystal display (LCD) (e.g., a thin-film transistor (TFT) display), although other forms of displays are acceptable. The display34displays location information to a user of the device by, for example, displaying coordinates and/or a graphical representation of the position of the device10on a map. Software32can be loaded onto the memory31by being downloaded via a network connection, uploaded from a disk, etc. Further, the software32may not be directly executable, e.g., requiring compiling before execution. The software32includes instructions configured to cause the processor30to perform functions described below. The various components of the mobile device10are communicatively coupled to one another via bus20. WhileFIG. 2illustrates the processor30and the memory31being separate from the SPS receiver33, the processor30and memory31may be components of the SPS receiver33such that the processing of the SPS signal is performed by the SPS receiver.

The processor30is communicatively coupled to both the SPS receiver33and the memory31via the bus20. The processor30is configured to obtain the signal12and/or the code and carrier phase measurements from the SPS receiver and determine the location of the device10from the signal12and the other signals received from the other satellites16-18of the SPS constellation.

The processor30is configured to obtain a code phase measurement and a carrier phase measurement of the signal. Obtaining these measurements may include receiving the measurements from the SPS receiver33via the bus20or receiving the measurement from memory31via the bus20.

The processor30is configured to calculate an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement. The function may be the difference of the code phase measurement and the carrier phase measurement. This intermediate quantity may be determined for every epoch of the SPS and stored in memory31. Every past calculation result of the intermediate quantity may be stored in memory or only a set number of past calculation results may be stored.

The processor30is configured to calculate a carrier phase smoothed estimate of a code phase of the signal based, at least in part, on a robust aggregation of the intermediate quantity. As mentioned above, examples of a robust aggregation include a median, a trimmed (truncated) mean, a winsorized mean, or an M-estimator using a Huber loss function or a Tukey bisquare loss function.

The processor30is further configured to determine the position of the device10based, at least in part, on the carrier phase smoothed estimate of the code phase. In particular, the carrier phase smoothed estimate of the code phase may be input into a Kalman filter, along with estimates of code phase measurements from other satellites of the SPS1to determine the location of the device10.

The processor30may be configured to determine the median of the intermediate quantity using a min heap data structure35and a max heap data structure40stored in memory31. Min heap data structures and max heap data structures are tree-based data structures that include multiple elements, or stored values. In a min heap data structure, parent elements are always less than or equal to those of child elements (such as child37and child38, shown inFIG. 2) and the top of the binary tree (the root node) is always the element with the minimum value36. In a max heap data structure, parent elements are always greater than or equal to those of child elements (such as child42and child43, shown inFIG. 2) and the top of the binary tree (the root node) is always the element with the maximum value41. While the min heap data structure35and the max heap data structure40are illustrated as a binary tree inFIG. 2, the actual data structure can be stored as an array in memory31, as is known in the art. Multiple past intermediate quantities are stored in the min heap data structure and the max heap data structure according to the rules set out below. Each satellite of the SPS1stores intermediate quantities associated with past phase measurements in separate min and max heap data structures (not shown).

The processor30is configured to maintain the min heap data structure35and the max heap data structure40according to a set of rules. A first rule is that the minimum value36of the min heap35data structure is kept greater than or equal to a maximum value41of the max heap data structure40. Thus, every time a new intermediate quantity, ƒ(t), is calculates, the intermediate quantity is compared to both the minimum value36and the maximum value41to determine into which heap the new intermediate quantity should be inserted. If the intermediate quantity is greater than the minimum value36of the min heap35, the intermediate quantity is inserted into the min heap35. If the intermediate quantity is less than the maximum value41of the max heap40, the intermediate quantity is inserted into the max heap40. Inserting new elements into a heap data structure requires a reorganization of the elements of the heap data structure. Techniques for reorganizing the elements of a heap are known in the art and may be referred to as heapsort, heapify or sifting.

A second rule that the processor30is configure to use to maintain the min heap data structure35and the max heap data structure40is that the number of values of the min heap data structure35may not differ from the number of values of the max heap data structure40by more than one. The number of values stored in a heap data structure is referred to as the size of the heap data structure. Thus, the min heap data structure35and the max heap data structure40are maintained by the processor30such that the size of the min heap data structure35is one less than the size of the max heap data structure40, the size of the min heap data structure35is equal to the size of the max heap data structure40, or the size of the min heap data structure35is one more than the size of the max heap data structure40. To implement the second rule, the processor is configured to adjust the size of the two heaps after the new intermediate quantity is inserted into the min heap data structure35or the max heap data structure40. The processor30compares the sizes of the two heaps and if the size of one of the heaps is more than one greater than the size of the other heap, then one value is removed from the larger heap and inserted into the other heap. For example, if the min heap data structure35has two more elements than the max heap data structure40, then the minimum value36is removed from the min heap data structure35and inserted into the max heap data structure40. Similarly, if the max heap data structure40has two more elements than the min heap data structure35, then the maximum value41is removed from the max heap data structure40and inserted into the min heap data structure35. As with inserting an element into a heap data structure, removing an element from a heap data structure requires a reorganization of the elements of the heap data structure. The same heapsorting techniques used after inserting a new element into a heap data structure can be used after removing an element from a heap data structure.

With the min heap data structure35and the max heap data structure40storing the past intermediate quantity of the signals from the satellite15, the median value of the intermediate quantity can be determined quickly using only the min value36of the min heap data structure35and the max value41of the max heap data structure40. The processor30is configured to determine the median value of the intermediate quantity in different ways depending on the relative sizes of the min heap data structure35and the max heap data structure40. Thus, determining the median value of the intermediate quantity may include determining and comparing the number of values of each heap data structure. The processor30is configured to set the median value of the intermediate quantity equal to the maximum value of the max heap data structure in response to a determination that the number of values of the max heap data structure is larger than the number of values of the min heap data structure. The processor30is configured to set the median value of the intermediate quantity equal to the minimum value of the min heap data structure in response to a determination that the number of values of min heap data structure is larger than the number of values of the max heap data structure. The processor30is configured to set the median value of the intermediate quantity equal to a mean value of the maximum value of the max heap data structure and the minimum value of the min heap data structure in response to a determination that the number of values of the max heap data structure is equal to the number of values of the min heap data structure.

The processor30is configured to calculate the carrier-phase smoothed code-phase measurement using the median value of the intermediate quantity. For example, the processor30may add the most recent carrier phase measurement, φ(t), to the median value of the intermediate quantity.

Referring toFIG. 3, with further reference toFIGS. 1-2, a method3of determining a position of a device10includes the stages shown. The method3is, however, an example only and not limiting. The method3can be altered, e.g., by having stages added, removed, rearranged, combined, performed concurrently, and/or having single stages split into multiple stages. For example, the method3may be performed iteratively at multiple times. For example, for each epoch of the SPS, the method3may be performed.

At stage50, the method3includes receiving, with a receiver, a signal from a reference emitter. The receiver may be, for example, the SPS receiver33and the reference emitter may be satellite15. The SPS receiver33may receive the signal12from the antenna11. The SPS receiver33may process the signal12to determine a code phase measurement and a carrier phase measurement of the signal12. The signal12and/or the code phase measurement and the carrier phase measurement may be sent to the processor30for additional processing. The measurements may be sent to the processor30directly, or sent to memory31for storage, from where the processor30may retrieve the measurements.

At stage51, the method3includes obtaining a code phase measurement of the signal. The processor30may obtain the code phase measurement by receiving the measurement from the SPS receiver33. Alternatively, the processor30may obtain the code phase measurement from memory31via bus20. It is also possible for the processor30to receive the signal from the SPS receiver33such that the processor30performs the measurement of the code phase. The code phase measurement is a value related to the time required for the signal to propagate from satellite15to the device10.

At stage52, the method3includes obtaining a carrier phase measurement of the signal. The processor30may obtain the carrier phase measurement by receiving the measurement from the SPS receiver33. Alternatively, the processor30may obtain the carrier phase measurement from memory31via bus20. It is also possible for the processor30to receive the signal from the SPS receiver33such that the processor30performs the measurement of the carrier phase. The carrier phase measurement is a value related to the time required for the signal to propagate from satellite15to the device10.

At stage53, the method3includes calculating an intermediate quantity that is a function of the code phase measurement and the carrier phase measurement. For example, the processor30can calculate the intermediate quantity by subtracting the carrier phase measurement from the code phase measurement. The intermediate quantity can be stored in memory31along with past intermediate quantities calculated from previously received signals from the satellite15. The intermediate quantities may be stored in two heap data structures, as described below. All past intermediate quantities may be stored in the memory31. Alternatively, a limited number of previous intermediate quantities may be stored in the memory31. For example, only the previous 10 intermediate quantities from time t, t−1, . . . , t−T′ may be stored in the memory31, where t is the current time and T′ is the threshold number of intermediate quantities to be stored in the memory31.

At stage54, the method3includes calculating a carrier-phase smoothed estimate of a code phase of the signal12based, at least in part, on a robust aggregation of the intermediate quantity. The processor30can perform a robust aggregation technique on the intermediate quantity from the current time and the past intermediate quantities from previous times. Examples of robust aggregation techniques that may be used include a median, a trimmed (truncated) mean, a winsorized mean, or an M-estimator using a Huber loss function or a Tukey bisquare loss function. Details of an example technique for calculating a median value of the intermediate quantities is discussed below in connection withFIG. 4. Once the processor30determines the robust aggregation of the intermediate quantity, the processor30can determine the carrier carrier-phase smoothed estimate of a code phase of the signal12by adding the current carrier phase measurement to the robust aggregation.

At stage55, the method3includes determining the position of the device based, at least in part, on the carrier-phase smoothed estimate of the code phase. The processor30may determine the position of the device using, for example, a Kalman filter and estimates of the code phase measurements from other satellites of the SPS1.

Referring toFIG. 4, with further reference toFIGS. 1-3, a method4of calculating the carrier-phase smoothed estimate of the code phase is shown. The method4is, however, an example only and not limiting. The method4can be altered, e.g., by having stages added, removed, rearranged, combined, performed concurrently, and/or having single stages split into multiple stages. For example, the method4may be performed iteratively at multiple times. For example, for each epoch of the SPS, the method3may be performed. Also, the stage54of the method3may use the method4to calculate the carrier-phase smoothed estimate of the code phase.

At stage60, the method4includes obtaining the min heap data structure35and the max heap data structure40. The heap data structures can be stored in memory31as arrays, as is known in the art, and retrieved by the processor30via bus20. If previous phase measurements have been made by the device, the heap data structures will already exist in memory31. If the current time corresponds to the first phase measurement of a signal the processor may create the min heap data structure35and the max heap data structure40.

At stage61, the method4includes determining whether the current intermediate quantity, determined by the processor at the stage53of the method3, is greater than the minimum value36of the min heap data structure35(i.e., the value stored in the root element of the min heap data structure35) or less than the maximum value41of the max heap data structure40(i.e., the value stored in the root element of the max heap data structure40). This determination may be performed by the processor30. If it is determined that the intermediate quantity is greater than the minimum value36of the min heap data structure35, then the method4continues to stage62where the intermediate quantity is inserted into the min heap data structure35. If it is determined that the intermediate quantity is greater than less than the maximum value41of the max heap data structure40, then the method4continues to stage63where the intermediate quantity is inserted into the max heap data structure40. At stages62and63, the insertion of the intermediate quantity into the heap data structure may include the processor30performing a reorganization of the heap data structure to ensure that every parent element of the max heap data structure40is greater than or equal to the corresponding children elements and ever parent element of the min heap data structure35is less than or equal to the corresponding children elements.

At stage64, the method4includes ensuring, by the processor30, that the size of the min heap data structure35and the size of the max heap data structure40differ by no more than one. The size of each heap data structure is defined as the number of values stored in the heap data structure. The processor30maintains the heaps such that neither one of the two heap data structures has more than one more element than the other heap data structure. To ensure the sizes of the two heap data structures differ by no more than one, the processor30may, after a new element is added to one of the heap data structures, compare the size of the size of the min heap data structure35and the size of the max heap data structure40. If the min heap data structure35has two more elements than the max heap data structure40, then the minimum value36is removed from the min heap data structure35and inserted into the max heap data structure40. If the max heap data structure40has two more elements than the min heap data structure35, then the maximum value41is removed from the max heap data structure40and inserted into the min heap data structure35. After each removal and insertion of an element into the heap data structures, the processor30performs a reorganization of the heap data structures to ensure that every parent element of the max heap data structure40is greater than or equal to the corresponding children elements and ever parent element of the min heap data structure35is less than or equal to the corresponding children elements.

At stage65, the method4includes determining which of the two heap data structures is larger in size, or if the sizes are equal. This determination is made by the processor30because the value for the median of the intermediate quantity is determined differently depending on the sizes of the two heap data structures. If the processor30determines that the size of the min heap data structure35is larger than the size of the max heap data structure40, then the method4continues to stage66where the processor30sets the median value of the intermediate quantity equal to the minimum value36of the min heap data structure35. If the processor30determines that the size of the max heap data structure40is larger than the size of the max heap data structure35, then the method4continues to stage67where the processor sets the median value of the intermediate quantity equal to the maximum value41of the max heap data structure40. If the processor30determines that the size of the max heap data structure40is equal to the size of the max heap data structure35, then the method4continues to stage68where the processor sets the median value of the intermediate quantity equal to the average of the minimum value36of the min heap data structure35and the maximum value41of the max heap data structure40.

At stage69, the method4includes adding the carrier phase measurement to the median value of the intermediate quantity. This addition may be performed by the processor30.

Other examples and implementations are within the scope and spirit of the disclosure and appended claims. For example, due to the nature of software and computers, functions described above can be implemented using software executed by a processor, hardware, firmware, hardwiring, or a combination of any of these. Features implementing functions may also be physically located at various positions, including being distributed such that portions of functions are implemented at different physical locations.

As used herein, “or” as used in a list of items prefaced by “at least one of” or prefaced by “one or more of” indicates a disjunctive list such that, for example, a list of “at least one of A, B, or C,” or a list of “one or more of A, B, or C” means A or B or C or AB or AC or BC or ABC (i.e., A and B and C), or combinations with more than one feature (e.g., AA, AAB, ABBC, etc.).

Further, an indication that information is sent or transmitted, or a statement of sending or transmitting information, “to” an entity does not require completion of the communication. Such indications or statements include situations where the information is conveyed from a sending entity but does not reach an intended recipient of the information. The intended recipient, even if not actually receiving the information, may still be referred to as a receiving entity, e.g., a receiving execution environment. Further, an entity that is configured to send or transmit information “to” an intended recipient is not required to be configured to complete the delivery of the information to the intended recipient. For example, the entity may provide the information, with an indication of the intended recipient, to another entity that is capable of forwarding the information along with an indication of the intended recipient.

Other examples and implementations are within the scope and spirit of the disclosure and appended claims. For example, due to the nature of software, functions described above can be implemented using software executed by a processor, hardware, firmware, hardwiring, or combinations of any of these. Features implementing functions may also be physically located at various positions, including being distributed such that portions of functions are implemented at different physical locations.

Further, more than one invention may be disclosed.

A wireless network is a communication system in which communications are conveyed wirelessly, i.e., by electromagnetic and/or acoustic waves propagating through atmospheric space rather than through a wire or other physical connection. A wireless network may not have all communications transmitted wirelessly, but is configured to have at least some communications transmitted wirelessly.

Components, functional or otherwise, shown in the figures and/or discussed herein as being connected or communicating with each other are communicatively coupled. That is, they may be directly or indirectly connected to enable communication between them.