METHOD AND APPARATUS FOR REDUCING SATELLITE POSITION MESSAGE PAYLOAD BY ADAPTIVE DATA COMPRESSION TECHNIQUES

• US 20140253369A1
• Filed: 03/05/2013
• Published: 09/11/2014
• Est. Priority Date: 03/05/2013
• Status: Active Grant

• Current Assignee: SubCarrier Systems Corporation
• Original Assignee: SubCarrier Systems Corporation
• Inventors: Kelley, David Charles, Berchin, Gregory John
• Granted Patent: US 9,250,327 B2
• Time in Patent Office: Days
• US Class Current: 342/175
• CPC Class Codes: G01S 19/071 DGPS corrections
• CPC Class Codes: G01S 19/074 providing integrity data, e.g. WAAS
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

An adaptive method by which Differential GNSS corrections may be compressed. Each measurement datum to be transmitted to a rover for satellite navigation purposes is decomposed into two parts, namely, an anchor value and a delta value, and in some instances an added third part termed a nonce value is used. Encoding parameters such as the number of bits assigned to each part of the measurement datum, the order of the models used to convey positional data, and scaling constants in the models, are adjusted adaptively based on changing data and/or transmission medium characteristics. Adaptive compression also allows for anomalous conditions such as out-of-range data values to be handled gracefully.

Claims

9. Apparatus comprising:

processor;

computer readable storage medium accessible to the processor and bearing instructions which when executed by the processor cause the processor to undertake logic comprising;

receiving plural measurement data for satellite navigation purposes, at least some measurement data being established by at least a respective anchor value and a respective delta value;

decoding at least some of the measurement data using a first decompression;

receiving at least one indication of a second compression being used; and

based at least in part on the indication, dynamically changing from decoding at least some of the measurement data using the first decompression to decoding at least some of the measurement data using a second decompression.

10. The apparatus of claim 9, wherein the act of dynamically changing from the first decompression to a second decompression includes changing a number of bits decoded from each part of a measurement datum.

11. The apparatus of claim 9, wherein the act of dynamically changing from the first decompression to a second decompression includes changing an order of a model used to convey positional data based on measurement data.

12. The apparatus of claim 9, wherein the act of dynamically changing from the first decompression to a second decompression includes changing a scaling constant in a model used to convey positional data based on measurement data.

13. The apparatus of claim 9, wherein at least one measurement datum is further established by a nonce part, and the act of dynamically changing from the first decompression to a second decompression includes changing at least one of:

a number of bits decoded from the nonce part, an order of a model used to convey positional data based on the nonce part, a scaling constant in the model.

14. The apparatus of claim 9, wherein each of at least some of the measurement data defines a respective anchor portion and a respective delta portion, delta portions being received more frequently than, anchor portions.

15. The apparatus of claim 9, wherein each of at least some of the measurement data defines a respective anchor portion, a respective delta portion, and a respective nonce portion, delta portions being received more frequently than, anchor portions, nonce portions being received more frequently than, delta portions.

16. An adaptive method by which Differential global navigation satellite system (GNSS) corrections are compressed, comprising:

establishing for each measurement datum to be transmitted to a rover for satellite navigation purposes at least an anchor value and a delta value; and

adaptively adjusting at least one encoding parameter of the measurement data based on changing data and/or transmission medium characteristics.

17. The method of claim 16, wherein the act of adaptively adjusting includes adaptively adjusting at least one encoding parameter of the measurement data based on changing data.

18. The method of claim 16, wherein the act of adaptively adjusting includes adaptively adjusting at least one encoding parameter of the measurement data based on changing data.

19. The method of claim 16, wherein the encoding parameter is a number of bits assigned to each part of the measurement datum.

20. The method of claim 16, wherein the encoding parameter is an order of a model used to convey positional data.

21. The method of claim 16, wherein the encoding parameter is a scaling constant of a model used to convey positional data.

22. The method of claim 16, comprising gracefully handling out-of-range data values.

23. The method of claim 16, wherein respective nonce values are established for at least some measurement data.

24. A device comprising:

at least one transmit part configured for obtaining and/or determining data elements from one or more sources, the data elements representing measurements or other information associated with one or more entities, and by means of data compression and encoding, representing an ensemble of the data elements as a set of messages that are transmitted via one or more suitable transmission media, and

at least one receive part configured for receiving, decoding, and decompressing messages created by transmitting part so as to reconstitute data elements contained within the messages, such that a composite size of the messages is significantly smaller than a composite size of a set of messages representing same the data elements in an uncompressed form, and the transmit part is configured for controlling an achievable fidelity of reconstitution of the data elements, by the receive part, by means of an alteration of one or more parameters in the data compression and encoding, the transmit part being configured for adaptively changing compression and/or encoding parameters in response to changing requirements, situations, and/or data, the transmit and receive parts being configured for graceful accommodation of and/or recovery from one or more anomalous data elements that cannot be represented by the encoding, by means of signals encoded in the messages.

1. Apparatus comprising:

processor;

computer readable storage medium accessible to the processor and bearing instructions which when executed by the processor cause the processor to undertake logic comprising;

receiving plural measurement data to be transmitted to a rover for satellite navigation purposes, at least some measurement data being established by at least a respective anchor value and a respective delta value;

compressing at least some of the measurement data using a first compression;

receiving at least one indication of changing measurement data and/or changing transmission medium characteristics; and

based at least in part on the indication, dynamically changing from compressing at least some of the measurement data using the first compression to compressing at least some of the measurement data using a second compression.

2. The apparatus of claim 1, wherein the act of dynamically changing from the first compression to a second compression includes changing a number of bits assigned to a part of a measurement datum.

3. The apparatus of claim 1, wherein the act of dynamically changing from the first compression to a second compression includes changing an order of a model used to convey positional data based on measurement data.

4. The apparatus of claim 1, wherein the act of dynamically changing from the first compression to a second compression includes changing a scaling constant in a model used to convey positional data based on measurement data.

5. The apparatus of claim 1, wherein at least one measurement datum is further established by a nonce part, and the act of dynamically changing from the first compression to a second compression includes changing at least one of:

a number of bits assigned to the nonce part, an order of a model used to convey positional data based on the nonce part, a scaling constant in the model.

6. The apparatus of claim 1, wherein each of at least some of the measurement data defines a respective anchor portion and a respective delta portion, delta portions being sent to a rover at least as frequently as anchor portions.

7. The apparatus of claim 1, wherein each of at least some of the measurement data defines a respective anchor portion, a respective delta portion, and a respective nonce portion, delta portions being sent to a rover more frequently than anchor portions, nonce portions being sent to a rover more frequently than delta portions.

8. The apparatus of claim 6, wherein the first compression includes a respective anchor transmission rate and a delta transmission rate, the second compression includes a respective anchor transmission rate and a delta transmission rate, and at least the anchor transmission rate in the second compression is different from the anchor transmission rate in the first compression, and/or at least the delta transmission rate in the second compression is different from the delta transmission rate in the first compression.

25. The device of claim 24, wherein the data elements include range, range-rate, range corrections, and/or quantities related to range, and corresponding times, and/or parameters used in the determination thereof, associated with observations of one or more GNSS satellites by one or more GNSS reference stations at fixed locations on the surface of the Earth, or

the data elements include parametric models or other representations that are functions of time, and from which range, range-rate, range corrections, and/or quantities related to range, and corresponding times, and/or parameters used in the determination thereof, may be derived by evaluation of the parametric models or other representations, and

the messages represent information that is transmitted by one or more GNSS reference stations to one or more mobile or stationary GNSS rovers via one or more transmission media, as a part of an implementation of GNSS differential range correction.

26. The device of claim 25, wherein compression and encoding parameters are known to both transmit part and receive parts because:

a. compression and encoding parameters are predetermined and either fixed, or changed according to a schedule, or

b. compression and encoding parameter values are changed by the transmit part from time to time, then transmitted to receive parts when changed, or more frequently, or

c. compression and encoding parameter values are changed by external entities from time to time, then conveyed to transmit part and receive parts when changed, or more frequently.

27. The device of claim 26, wherein compression and encoding parameters associated with each GNSS satellite signal are unique to that signal.

28. The device of claim 26, wherein some or all of a set of compression and/or encoding parameters are shared among more than one GNSS satellite signals.

29. The device of claim 28, wherein the transmit part transmits one or more sets of compression and/or encoding parameters to receive part by means of an index to a mutually shared table or list of such parameters.

30. The device of claim 26, wherein the transmit part transmits one or more sets of compression and/or encoding parameters to receive part by means or one or more auxiliary communications methods.

31. The device of claim 26, wherein compression and/or encoding parameter values are transmitted more frequently than a rate at which the values actually change, and an amount of time that passes between when a receive part becomes able to receive data messages from a transmit part, and when the receive part possesses sufficient information to decode and decompress the data messages, is thereby reduced.

32. The device of claim 25, wherein data elements are decomposed into:

a. a set of long-term values that change slowly or not at all, and are optionally represented at a reduced numerical precision and/or accuracy;

values or representations of which are transmitted infrequently, and/or

b. a set of short-term values that change quickly, and are optionally represented at a reduced numerical precision and/or accuracy;

values or representations of which are transmitted frequently, and

c. an optional set of residuals;

values or representations of which are transmitted as necessary, that provide instantaneous corrections to data elements reconstituted only from the long-term and short-term values such that reconstituted data elements can match original data elements to within an increased numerical precision and/or accuracy.

33. The device of claim 32, wherein the set of long-term values represents full quantities of corresponding original data elements, to within a desired numerical precision and/or accuracy.

34. The device of claim 32, wherein the set of short-term values represents differences between a set of current data elements and a corresponding set of recent previous data elements, to within a desired numerical precision and/or accuracy.

35. The device of claim 34, wherein the set of short-term values represents differences between a set of current data elements and a most recently transmitted set of long-term values.

36. The device of claim 35, wherein reconstitution of the set of current data elements depends only upon the set of short-term values and the most recently transmitted set of long-term values;

reconstitution of the set of current data elements thus being possible even in cases where one or more recently transmitted sets short-term values has not been received.

37. The device of claim 34, wherein the set of short-term values represents differences between a set of current data elements and a sum of a most recently transmitted set of long-term values and at least one set of recently transmitted short-term values.

38. The device of claim 34, wherein compression is achieved because the differences have smaller magnitudes than corresponding full quantities of the current data elements, and thus encoding of differences results in a smaller message payload than does encoding of full quantities of data elements.

39. The device of claim 32, wherein the set of residuals represents differences between a set of current data elements and:

a. a most recently transmitted set of long-term values, or

b. a sum of a most recently transmitted set of long-term values and at least one recently transmitted set of short-term values.

40. The device of claim 32, wherein:

a. multiple individual long-term, short-term, or residual values are decomposed into a sum of a value common to all the individual values and an excess value unique to each individual value, and

b. the common value and the multiple unique excess values are encoded into one or more messages by transmit part in lieu of the multiple individual values, along with sufficient ancillary information to enable receive part to reconstitute data elements therefrom.

41. The device of claim 40, wherein data compression is achieved because fewer message bits are required to represent the single common value and multiple unique excess values than are required to represent the multiple individual values.

42. The device of claim 32, wherein:

a. long-term values are transmitted at a rate based upon a rate at which the data elements change, a fidelity with which the reconstituted data elements must match the original data elements, some constraints upon transmission bandwidth and/or data payload, and/or an ability of receive parts to tolerate data starvation, and

b. short-term values are transmitted at a rate based upon a rate at which the data elements change, a fidelity with which the reconstituted data elements must match the original data elements, some constraints upon transmission bandwidth and/or data payload, and/or an ability of receive parts to tolerate data starvation, and

c. optional residual values are transmitted at a rate based upon a fidelity with which the reconstituted data elements must match the original data elements, and/or some constraints upon transmission bandwidth and/or data payload.

43. The device of claim 32, wherein:

a. data elements consist of parametric models or other representations that are functions of time, and

b. parameters of the parametric models or other representations are transmitted instead of values that parametric models or other representations represent, and

c. the parametric models or other representations may be evaluated by receive parts with respect to a current or past time, to reconstitute associated values that parametric models or other representations represent, to within a desired numerical precision and/or accuracy, and

d. the parametric models or other representations may be evaluated by receive parts with respect to a future time, to estimate future values that parametric models or other representations represent.

44. The device of claim 42, wherein the parametric models or other representations may be used to estimate future values, allowing receive parts to tolerate periods of data starvation in an event of inability to receive one or more signals from transmit part or purposeful reduction in transmission rates of long-term values, short-term values, and/or residuals.

45. The device of claim 42, wherein each the parametric model or other representation incorporates an independent set of scale factors for each of long-term values, short-term values, and residuals.

46. The device of claim 42, wherein the device can adapt to exploit trending information regarding data elements when available, or to remain operable when the trending information is absent.

47. The device of claim 32, wherein one or more long-term values are expected to remain constant for some periods of time spanning two or more long-term transmission epochs.

48. The device of claim 47, wherein the transmit part transmits, in addition to each the constant long-term value, one or more indications of a number of long-term transmission epochs over which associated long-term value is expected to remain constant.

49. The device of claim 47, wherein the transmit part transmits each of the constant long-term values in an associated initial message, and omits each of the constant long-term values in at least one subsequent message.

50. The device of claim 25, wherein the transmit part adaptively changes compression and/or encoding parameters for one or more sets of data elements.

51. The device of claim 50, wherein a quality metric is considered when determining compression and/or encoding parameters, consisting of the following, individually or in combination:

a. a fidelity with which data elements reconstituted from transmitted messages can match original data elements,

b. an ability of parametric models or other representations of data elements to predict future values,

c. a time that passes between when a receive part becomes able to receive data messages from a transmit part, and when the receive part possesses sufficient information to decode and decompress the data messages.

52. The device of claim 50, wherein the adaptive changes are applied in order to minimize an average or instantaneous size of messages to be transmitted by transmit part while satisfying the quality metric for data elements reconstituted by receive parts;

where the quality metric may change over time.

53. The device of claim 49, wherein compressed message payload contents are selected so as to achieve a balance between message content, message payload size, and message transmission rates, in response to evolving trends in the data elements themselves.

54. The device of claim 25, wherein a data value that falls outside a range that can be represented within an associated current allocation of message payload in a current long-term, short-term, or residual message, or is otherwise anomalous, is accommodated by:

a. an indication, within the message, that the data value is out of range, and

b. if a sufficient message capacity remains, utilization of a sufficient portion of the remaining message capacity to temporarily extend range of the value such that it can be represented,

or

c. an indication, within the message, that the data value is anomalous and thus cannot be represented, is corrupt, or is missing.

55. The device of claim 24, wherein one or more data elements are encrypted prior to encoding into messages.

56. The device of claim 24, wherein one or more messages are encrypted prior to transmission, or are transmitted via encrypted channels or media.

43-1. The device of claim 42, wherein compression is achieved because encoding of the parameters results in smaller message payload than does encoding of values from which models or other representations are derived.

51-2. The device of claim 50, wherein the adaptive changes are applied such that the quality metric for data elements reconstituted by receive parts is maximized within a constraint upon allowable maximum average or instantaneous size of the messages;

where the quality metric and/or the constraint may change over time.