Abstract:
A method and apparatus are presented for providing a compact extended ephemeris package for GNSS processing. An extended ephemeris service provides orbit trajectories and clock corrections which are predicted into the future for navigation satellites. The extended ephemeris package format used allows the ephemeris information to be sent quickly and efficiently, even when using a low bandwidth communication network. Client GNSS receiver devices obtain the extended ephemeris package and extract the satellite ephemeris information for later use. This allows a client device to operate for many days or weeks without needing to decode or receive new satellite ephemeris information.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to providing long-term predicted satellite ephemeris information for navigation satellites with the objectives of the invention being to reduce the amount of data that is needed to transfer a set of long-term predicted satellite ephemeris information while the loss of accuracy caused by the compression and transmission of said ephemeris information is kept to an acceptable value, and while the computational load required to decompress said ephemeris information is kept to an acceptable level. 
       DESCRIPTION OF RELATED ART 
       [0002]    Global Navigation Satellite System (GNSS) receiver devices can use predicted ephemeris in place of decoded ephemeris data. This invention enables the transfer of the predicted satellite ephemeris information encoded as an extended ephemeris package and distributed to client GNSS receiver devices in a format that minimizes the required communication bandwidth along with storage and processing requirements on the client devices. 
         [0003]    GNSS positioning and timing capabilities have become a requirement in many applications—from consumer devices such as GNSS-enabled smart phones to automated Machine-to-Machine (M2M) systems. GNSS includes the Global Positioning System (GPS) of the United States, the GLObalnaya Navigatsionnaya Sputnikovaya Sistema (GLONASS) or Global Navigation Satellite System of Russia, the Galileo system of the European Union, the BeiDou System (BDS) of China and any other similar satellite systems. 
         [0004]    In order to calculate the global position of a device, GNSS receiver components require what may be called the ephemeris: precise information about the orbit trajectory and clock corrections for each satellite that is used. Note that in some other descriptions of the art, “ephemeris” may refer only to the orbit trajectory, excluding the clock corrections. Traditionally, a GNSS receiver obtains the ephemeris for each satellite by decoding a message broadcast by that satellite. The satellite clock correction for the required time is calculated from polynomial coefficients, such as the af0, af1, and af2 parameters included in the GPS broadcast navigation data and described in ICD-GPS-200 (Interface Control Document 200F, “Navstar GPS Space/Navigation User Segment Interfaces”). 
         [0005]    The orbital trajectory of Earth orbiting satellites are often represented as a set of orbital parameters which are valid for a specific time interval. In the ideal case, an orbiting satellite could be perfectly modelled using 6 Keplerian parameters. However, in reality, all Earth orbiting satellites are subject to external perturbing forces which prevent the satellite from travelling in a pure Keplerian orbit. Additional parameters are needed to account for perturbation forces which act on the satellite, including but not limited to gravitational anomalies from the Earth as well as gravitational forces from the Sun, Moon, and planets. 
         [0006]    In some cases such as GNSS satellites, a total of 15 orbital parameters are used (ICD-GPS-200); of these 15 parameters, 6 are the Keplerian parameters which describe an unperturbed orbits and the other parameters account for orbital anomalies caused by perturbing forces. In circumstances where the amount of data that can be used to represent the orbit trajectory is limited, and the perturbation parameters used to model a perturbed orbit must be reduced in number and/or precision, a trade off must be made between the duration for which these parameters can accurately represent a perturbed orbital trajectory and the overall accuracy of the modelled orbit during this period. 
         [0007]    Alternatively, the orbit trajectory may be represented in a tabular format of position coordinates, and optionally velocity and acceleration vectors, for one or more time points, such as in the GLONASS broadcast ephemeris message. The orbit trajectory may then be calculated by propagating the satellite position from one time point or interpolating between multiple time points. 
         [0008]    Regardless of the format, it may be undesirable for a GNSS receiver to rely on the satellite broadcasts for ephemeris information. The broadcast ephemeris is transmitted at very low data rates (e.g. 50 bps for GPS), which means it can take an unacceptably long time to decode enough data to be able to use a satellite. If the received satellite signal is weak or intermittent, the required data will take even longer to be available, if ever. Even once a satellite is usable, the short validity period (e.g. 4 hours for GPS) means that the satellite may not remain usable for longer operation. 
         [0009]    Assisted GNSS (AGNSS) or, in particular Assisted GPS (AGPS), is a technique that provides a GNSS receiver with ephemeris information from an external source. This allows the receiver to begin using GNSS signals without decoding the full broadcast ephemeris message. A traditional AGNSS receiver requires frequent updates from the service, as the ephemeris information received is only useful for the same short validity period as the satellite broadcast ephemeris. 
         [0010]    Another alternative to decoding the current satellite broadcast ephemeris is for the GNSS receiver to use a previously stored extended ephemeris. Extended ephemeris is a technique where the satellite orbit trajectory and clock corrections are predicted well beyond the short validity interval of the live broadcast. The prediction duration often spans across many days and as long as one month. As a result, the receiver can compute the satellite position without the need of decoding the entire navigation message at the cost of reduced position accuracy over time. This reduces the Time to First Fix (TTFF) and increases the receiver signal acquisition sensitivity. 
         [0011]    The orbit trajectory can be predicted into the future by using a force model based on orbital mechanics. The force model is applied by integrating the various acceleration components acting on the satellite over the prediction duration. By incorporating as many perturbing forces as possible, the highest level of accuracy can be achieved using this approach. 
         [0012]    The satellite clock correction can be extrapolated into the future based on recent historical data at the time the predictions are made. The accuracy of the extrapolation relies on the quality of the satellite clock and the mathematical model used. 
         [0013]    These ephemeris predictions require extensive data and processing resources. Since resources are limited on a mobile GNSS device, the extended ephemeris is ideally generated by an external service. This extended ephemeris service may gather the information necessary to predict the satellite orbit trajectories and clock corrections, package the information for distribution, and provide the package over a wired or wireless communication network. Then, a client device will receive the extended ephemeris package, extract the satellite orbit trajectory and clock corrections for the applicable time, and use the information for GNSS processing. 
         [0014]    The challenge of transmitting extended ephemeris data with a prediction duration spanning several weeks is that the data size of orbit trajectories for multiple satellites may be so large that it is becomes impractical or unfeasible. Both the power consumed while receiving the data package and the local storage used at the client device can be too much for its limited resources. 
         [0015]    WIPO published patent application 2009/065206 (Lamance) assigned to Rx Networks and published 28 May 2009 describes reducing the transmitted data size by sending information about the physical forces acting on the satellites. Then the client device uses a simplified force model to perform some of the prediction computation onboard, placing a heavy processing burden on the client device. Furthermore, attempting to limit the processing load with simpler force models can lead to increased positioning errors. 
         [0016]    U.S. Pat. No. 7,839,324 (Phatak) assigned to SiRF Technology Inc., issued 23 Nov. 2010 describes a method of transmitting extended ephemeris information by delta-encoding a series of the Keplerian orbit models that span the entire prediction period. A drawback to this approach is that external forces acting on the satellites such as the gravity of the moon and sun cause satellites to travel in perturbed orbits. Thus, orbital parameters describing a perturbed orbit will contain harmonic and secular trends. To this end, in order to achieve a high compression ratio using differential compression, the harmonic and secular trends found in the orbital parameters needs to be removed prior to delta-encoding. For U.S. Pat. No. 7,839,324 however, the Keplerian parameters are differentially compressed without the modelling or removal of systematic trends; this reduces the efficiency of the differential compression and results in a poor data compression ratio for the extended ephemeris information. 
         [0017]    WIPO published patent application 2012/064568 (Brown) assigned to SORCE4 published 18 May 2012 describes a method of compressing extended ephemeris information by first modeling the overall trend of a set of orbit models as described by the ICD-GPS-200 using both sinusoidal and polynomial parameters. This model is not an exact fit and cannot be used to accurately determine a satellite&#39;s position. To compensate for this, a set of correction terms are then used to capture the differences between the original orbital parameters and the trend that is described by the sinusoidal and polynomial parameters. This method is not desirable due to the fact that many correction terms need to be transmitted in combination with the sinusoidal and polynomial models; thereby increasing the total amount of data that needs to be transferred to a client device. 
         [0018]    Therefore, a need exists for an extended ephemeris service and client device that uses a data package format which has a small size for distribution, maintains position accuracy requirements, and can be utilized at the client device without a heavy processing burden. 
       SUMMARY OF THE INVENTION 
       [0019]    According to the invention, there is provided a method for encoding an extended satellite orbit trajectory comprising: 
         [0020]    representing the orbit trajectory as a series of orbit segments wherein each orbit segment is described by a set of orbital parameters valid for an orbit segment interval; 
         [0021]    creating for each orbital parameter a series of points representing the values that said parameter takes at all times T at which the parameter is applicable for an orbit segment; 
         [0022]    performing for each orbital parameter a plurality of curve fits over the series of points for said parameter wherein each curve fit is performed on a set of N points where N is no less than 2 and no greater than 8, and where each curve fit results in a set of M coefficients where M is no less than 2 and no greater than 8; 
         [0023]    forming for the said coefficients, M series of curve fit coefficients such that all instances of the same coefficient generated from each of the sets of N points is grouped into the same series; 
         [0024]    and carrying out an encoding step for encoding each series of curve fit coefficients with compression. 
         [0025]    Preferably each of the series of curve fit coefficients is compressed with differential compression. 
         [0026]    Preferably the relative times between the points of any one of the sets of N points is the same as the relative times between the points of all of the other sets of N points. 
         [0027]    Preferably for any two of the sets of N points, the time difference between the first point of each set can be expressed as L*T orb ±(0.25*T orb ), where L is an integer and T orb  is the orbital period of the satellite. 
         [0028]    Preferably for any two of the sets of N points, the time difference between the first point of each set can be expressed as L*T orb ±(0.1*T orb ), where L is an integer and T orb  is the orbital period of the satellite. 
         [0029]    Preferably for any two of the sets of N points, the time difference between the first point of each set can be expressed as L*T orb , where L is an integer and T orb  is the orbital period of the satellite. 
         [0030]    Preferably one of the characteristics of the encoding step includes the ability to recursively compute a set of polynomials or the ability to use predefined polynomials. 
         [0031]    Preferably the encoding step uses Chebyshev, Legendre, Hermite, or Laguerre polynomials. 
         [0032]    Preferably for the curve fits of orbital parameters over time, a number of mathematical models can be used either individually as standalone functions or in combination with multiple functions. 
         [0033]    Preferably the models include polynomial, spline, rational, and trigonometric functions in the time domain. 
         [0034]    Preferably in the frequency domain, wavelets and Fourier series can also be used. 
         [0035]    Preferably the Whittaker-Shannon interpolation method can be used to represent the behaviour of a given orbit parameter in the frequency domain. 
         [0036]    Preferably one or more orbital parameters are modelled as multiple sets of coefficients of orthogonal basis functions. 
         [0037]    Preferably the orthogonal basis functions are Chebyshev functions. 
         [0038]    Preferably the curve fit coefficients and predicted clock corrections are encoded using a variable number of encoding bits to adjust the range of values to the orbit trajectory being modelled. 
         [0039]    Preferably the curve fit coefficients and predicted clock corrections have a variable precision so as to provide different precisions each of which meets a defined service level. 
         [0040]    Preferably the orbital parameters are in the form of parameters as described by the ICD-GPS-200, or a subset thereof. 
         [0041]    Preferably the satellite is one of a plurality of satellites which are arranged for GNSS processing. 
         [0042]    Preferably the method defined above is used in a method for providing a compact extended ephemeris package for a satellite, comprising: 
         [0043]    obtaining for said satellite orbit trajectory and clock corrections predicted into the future; 
         [0044]    and encoding each orbit trajectory using the method of any one of claims  1  to  18  along with the clock corrections into an extended ephemeris package for distribution to client devices. 
         [0045]    Preferably the extended ephemeris package from the extended ephemeris service is provided to a plurality of client devices, including the further steps comprising: 
         [0046]    decoding the curve fit coefficients and predicted clock corrections from the extended ephemeris package; 
         [0047]    computing the orbital parameters from the decoded curve fit coefficients, where the orbital parameters are from orbit segments applicable to a time of interest; 
         [0048]    and converting the orbital parameters and clock corrections for the time of interest into an ephemeris. 
         [0049]    According to a further aspect of the invention there is provided an apparatus comprising a client device which uses a compact extended ephemeris package for a plurality of satellites comprising: 
         [0050]    a component for receiving the extended ephemeris package wherein the package contains extended satellite orbit trajectory encoded by the method as defined above; 
         [0051]    a component for decoding the encoded extended satellite orbit trajectory; 
         [0052]    a component for computing the orbital parameters from the decoded extended satellite orbit trajectory, where the orbital parameters are from orbit segments applicable to a time of interest; 
         [0053]    and a component for converting the orbital parameters and clock corrections for the time of interest into an ephemeris. 
         [0054]    The data compression technique described herein is not confined to orthogonal basis functions but can work with a wide range of polynomial, trigonometric, and spline functions. Moreover, the data compression can be done in both the time domain as well as frequency domain using Fourier series and wavelets. 
         [0055]    The disclosure herein uses as one example orthogonal basis functions but also this can be generalized so that other functions can also be used. The following supporting information sets out the design decisions that went into the selection of the method defined herein. 
         [0056]    The term orbital parameter refers to any parameter that describes the orbital trajectory of a satellite and is not strictly confined to those described by the ICD-GPS-200. To this end, orbital parameters may also include subsets of the ICD-GPS-200 ephemeris parameters, GLONASS ICD ephemeris parameters and any subset thereof, additional parameters that maybe used in combination with said ICD-GPS-200 and GLONASS ICD ephemeris parameters to describe the orbital trajectory of a satellite, and any other parameters used to describe the orbital trajectory of a satellite. 
         [0057]    Also, the invention herein can further be applied to satellites not originally intended for navigation, if orbit trajectory and clock corrections can be calculated for those satellites; these satellites may include the Iridium, Globalstar, and Orbcomm satellite constellations. In such instances, the extended ephemeris information for telecommunication satellites can be used to reduce the time needed to acquire telecommunication signals. These telecommunication signals can be used for conventional telecommunication applications such as data transfer as well as unconventional navigation applications using signals of opportunity. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0058]      FIG. 1  shows the general arrangement of encoding and distribution of an extended satellite orbit trajectory in which the present invention is used. 
           [0059]      FIG. 2  is a graph showing the curve fitting method of the present invention which uses orbital parameter interpolation. 
           [0060]      FIG. 3  shows the process of generating and encoding curve fit coefficients. 
           [0061]      FIG. 4  shows one embodiment of the extended ephemeris service  400  from  FIG. 1  using orthogonal basis functions as one of the more general concepts described in relation to  FIG. 2 . 
           [0062]      FIG. 5  is an example client device of this embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0063]    Methods and apparatus of a preferred embodiment for providing a compact extended ephemeris package for GNSS processing are described hereinafter and explained with reference to the figures. This embodiment is used as an example for the present invention and does not exclude other embodiments. The embodiment comprises an extended ephemeris service to generate a compact extended ephemeris package which is distributed over a wired or wireless communication network, and one or more client devices which obtain the extended ephemeris package to be used for GNSS processing.  FIG. 1  shows one possible embodiment of the present invention. 
         [0064]    One or more input sources may provide predicted ephemeris information for some number of days into the future (for example, 1, 3, 7, 14, or 28 days). Historical satellite data  101  may be in the form of satellite tracking data or estimates of the satellite position and clock corrections. The historical satellite data may be used by an orbit propagator  102  to calculate predicted satellite orbit trajectories  103  over the prediction duration. The historical satellite data  101  may also be used by a clock propagator  104  to calculate predicted satellite clock corrections  105  over the prediction duration. 
         [0065]    One or more data stores, hereinafter collectively referred to as the extended ephemeris data store  106 , may collect the predicted satellite orbit trajectories  103 , predicted satellite clock corrections  105 , and optionally other prediction information  107  such as, but not limited to, satellite velocity, ionospheric model coefficients, satellite health information, and time group delay. 
         [0066]    In this embodiment, the orbit and clock propagation may be performed by the extended ephemeris service provider. In an alternative embodiment, a third-party provider may generate the propagated orbits, clock corrections, or both and supply this information to the extended ephemeris data store  106 . 
         [0067]    An extended ephemeris service  400  may comprise one or a network of servers to encode the information from the extended ephemeris data store  106  into a compact extended ephemeris package  108 , and distribute the package to one or more client devices  500  through a communication medium  109 . A client device  500  may include a GNSS process which calculates position from the decoded extended ephemeris information and the signals from satellites  600 . 
       Compressing Satellite Orbit Trajectories 
       [0068]    The approach, shown in  FIG. 2 , as applied in the present arrangement uses curve fitting and interpolation techniques to compress long-term satellite orbit information. An extended satellite orbit trajectory which spans a duration of multiple orbital periods is represented as a series of orbit segments, wherein each orbit segment is described by a set of orbital parameters that are valid for an orbit segment interval. Each orbital parameter is considered individually as a series of points that change over time. The curve fitting is performed on smaller sets of the points rather than performing one large curve fit over all of the points in the extended satellite orbit trajectory. In this way, a plurality of fitted curves is used to span the entire duration of a given long-term orbit prediction. The coefficients that are the result of the curve fits are compressed in a manner that takes advantage of the underlying physical properties of satellite orbits. 
       Generating Orbital Parameters 
       [0069]    To generate the orbital parameters for a given satellite, an iterative least-squares best-fit algorithm is typically used to minimize the difference between the satellite&#39;s orbital trajectory to be modelled, which may take the form of a time series of position coordinates, and the modelled orbital trajectory represented by the orbital parameters being generated. 
         [0070]    Since said orbital parameters represent a specific portion of a satellite&#39;s trajectory and not necessarily a complete orbit; the portion of the satellite trajectory being represented by said orbital parameters is referred to as an orbit segment. As such, the period of time for which said orbital parameters represent a given satellite&#39;s trajectory is referred to as the orbit segment interval. The orbital parameters that describe the orbit segment are associated with a time T at which the parameters are applicable. 
         [0071]    As mentioned previously, a trade off must be made between the duration of a given orbit segment interval and the level of accuracy to which the orbital parameters can describe an orbit segment during said orbit segment interval. In order to maintain a fitting accuracy on the order of several metres, orbit segment intervals used for modelling Medium-Earth Orbits (MEO) may vary between 1 and 24 hours. More typically for orbits of GNSS satellites, an orbit segment interval of 4-8 hours is used. Because the perturbing forces that act on Low-Earth Orbit (LEO) satellites are much stronger, the typical orbit segment intervals for LEO satellites may vary on the order of several minutes up to several hours. 
         [0072]    Conversely, geosynchronous and High-Earth orbit satellites experience weaker perturbing forces as compared to GNSS satellites; as such, typical orbit segment intervals for said satellites may vary from several hours up to several days. Moreover, for highly elliptical orbits of satellites such as those used in the Japanese Quasi-Zenith Satellite System (QZSS) and the Sirius Satellite Radio constellation, the orbit segment intervals used may vary depending on the distance between the orbit segment and the foci of the orbit (i.e. the Earth&#39;s centre of mass). To this end, an orbit segment nearest to the perigee may have a shorter orbit segment interval as compared to the orbit segment nearest to the apogee. In addition, a given level of fitting accuracy may be maintained for a longer orbit segment interval by making use of additional perturbation parameters not described by the ICD-GPS-200. Conversely, a subset of the ICD-GPS-200 orbital parameters may be used for shorter orbit segment intervals without degrading the overall accuracy of the modelled orbit segment. 
         [0073]    Another factor that can influence the accuracy of a modelled orbit segment is the numerical precision of the orbital parameters used to represent the orbit segment. In the case of GNSS orbits, many of the orbital parameters are extremely sensitive to small deviations caused by numerical errors. As a result, any small deviations in the GNSS orbital parameters, whether they are caused by numerical errors or otherwise, may result in gross positioning errors in the corresponding orbit segment. Because of this, the numerical precision needed for storing and distributing GNSS orbital parameters is very high; the required numerical precision for GPS orbital parameters is specified by the ICD-GPS-200. As noted in the ICD-GPS-200, the numerical precision required for each individual GPS orbital parameters may vary greatly from one another. 
         [0074]    In the arrangement described herein, long-term orbits of satellites generally refer to durations spanning one or more hours to several weeks. More specifically, in the case of MEO satellites such as GNSS satellites, long-term orbits refer to durations that span over more than one orbit segment interval. In the instance where the long-term orbit of a given GNSS satellite span over several weeks, many orbit segments are needed to represent the orbit with an accuracy level better than several metres. For example, if the full set of orbital parameters as specified by the ICD-GPS-200 were to be directly transmitted without compression for 32 satellites at a rate of once every four hours over a period of 28 days, a total of more than 230 kilobytes are needed; therefore, it may be undesirable to distribute long-term orbit information by directly transmitting the orbital parameters due to limitations in the communication bandwidth. To this end, the arrangement described herein provides an alternative arrangement to distribute the long-term orbit information using significantly less bandwidth as compared to directly distributing the orbital parameters for said long-term orbit information. 
         [0000]    Compression with Curve Fitting 
         [0075]    A variety of data compression techniques can be used to compress orbital parameters with varying degrees of effectiveness. These techniques may include data differencing and modelling of the harmonic and secular trends. Although data differencing can be used effectively to compress parameters with stationary processes, many orbital parameters are non-stationary and cannot be efficiently compressed by data differencing techniques. Alternatively, harmonic and secular trends present over many orbit segments may be modelled using curve fitting and interpolation techniques, where interpolation is a special case of curve fitting in which the curve must pass through all data points used for the fit. 
         [0076]    The arrangement described herein uses a plurality of fitted curves to model the change in an orbital parameter over the duration of an extended satellite orbit trajectory. By using this method, the fitted curve can accurately represent a given orbital parameter over a small number of orbit segments; this fitted curve also requires fewer coefficients to describe the orbital parameters being modelled and each coefficient is less sensitive to numerical instabilities that exist with high-order polynomial curve fitting. In practical terms, the number of orbit segments used in each curve fit should be no more than 8. Also, a number of orbit segments fewer than 2 is a trivial case that does not produce a curve fit. 
         [0077]    For the interpolation of orbital parameters over time, a number of mathematical models can be used either individually as standalone functions or in combination with multiple functions; these models include polynomial, spline, rational, and trigonometric functions in the time domain. Since different orbital parameters may exhibit unique behaviour that make them more suited to be modelled by a particular mathematical function, it may be desirable to use different functions for interpolation based on the orbital parameter used. 
         [0078]    One added benefit to the above approach of precise, short-term curve fitting of orbital parameters is that many orbital parameters have harmonic trends that coincide closely with their orbital period. Because of this, if the orbit segment interval is chosen so that the orbital period of a given satellite coincides with an integer number of orbit segment intervals, the coefficients of the fitted curves that describe a given orbital parameter will be very similar from one orbital period to the next. By exploiting this behaviour, the coefficients that describe each fitted curve can then be effectively compressed using differential data compression. 
         [0079]    The arrangement described herein takes advantage of the intrinsic properties of how orbital parameters behave over time in order to compress the orbital parameters for distribution in an efficient manner. In general, the orbital parameters described by the ICD-GPS-200 exhibit deterministic properties with harmonic and secular trends when observed over a plurality of orbit segments; as such, the harmonic and secular trends can be exploited to maximize the data compression ratio of the orbital parameters. Doing so allows the arrangement described herein to minimize the amount of data needed when distributing long-term orbit information. 
         [0080]    Furthermore, data compression can be categorized as being either lossless or lossy. The arrangement described herein makes use of lossy data compression techniques in a manner that allows the long-term orbit information to be transmitted with a minimum amount of data; at the same time, the arrangement described herein also ensures degradation in accuracy of the modelled orbit segments caused by data compression loss is kept at an acceptable level. This is achieved in part by adjusting the numerical precision of both the original uncompressed form of the orbital parameters as well as the compressed form of the orbital parameters. 
         [0081]    The arrangement described herein, shown in  FIG. 3 , thus provides a method for encoding an extended satellite orbit trajectory wherein the full duration of the trajectory is represented as a series of orbit segments. Each orbit segment is described by a set of orbital parameters which are valid for an orbit segment interval. 
         [0082]    Each orbital parameter is considered individually as a series  301  of points that change over time, where the point is the value that the parameter takes at the time T at which the parameter is applicable for an orbit segment.  FIG. 2  shows how an individual orbital parameter has a point for each orbit segment and may change over time. 
         [0083]    A plurality of curve fits is performed over sets of the points  302  representing the orbital parameter. In the example shown in  FIG. 2 , the curve fit is performed on a set of 4 points, and repeated for other sets of 4 points until all of the orbit segments are represented in at least one of the curve fits. In the example, each curve fit results in 4 coefficients to be encoded. In general however, each curve fit may be performed over sets of N points  303 , where N is no less than 2 and no greater than 8, and results in M coefficients  304 , where M is no less than 2 and no greater than 8. 
         [0084]    Each of the curve fit coefficients is then formed into a series of the same coefficient from all of the curve fits  305 . In the example of  FIG. 2 , the 4 coefficients are formed into 4 series, one series containing all values of the first coefficient, then another series of the second coefficient, and then series for the third and fourth coefficients. In general there will be M series of coefficients formed  306 . 
         [0085]    Then for each of the series of coefficients, the members in the series are compressed with differential compression  307  or another means of compression, yielding M series of compressed coefficients  308 . 
         [0086]    In the example of  FIG. 2 , the duration between the time T of each point value of the orbital parameter is constant at one half of a satellite orbital period T orb . Thus, the first point of any two adjacent curve fits will be separated by duration of 2*T orb . In general, the duration between the time T of each point can be variable and the sets of points formed for the curve fits need not be in strict order of increasing time. But the compression of the curve fit coefficients is improved if the relative time between points used for one curve fit is the same as the relative time between points in each of the other curve fits, and also that the time between the first point of any two curve fits is near an integer L number of satellite orbital periods, say L*T orb ±0.25*T orb . 
         [0087]    In the frequency domain, wavelets and Fourier series can also be used. For example, the Whittaker-Shannon interpolation method can be used to represent the behaviour of a given orbit parameter in the frequency domain. 
         [0088]    In addition to selecting a mathematical function that is well suited for the behaviour of a given orbital parameter, there are additional characteristics that make certain functions more suitable for mobile devices. One of these characteristics include the ability to recursively compute a set of polynomials or the ability to use predefined polynomials; examples of this can be found in Chebyshev, Legendre, Hermite, and Laguerre polynomials. 
         [0089]    Other factors that influence the selection of a function candidate for modelling orbital parameters include the computational load required to generate such functions; for example, the use of trigonometric functions for interpolation can greatly increase the computational load on a low-power mobile device. 
         [0090]    Lastly, numerical stability is also a key consideration in the selection of candidate functions for the interpolation of orbital parameters; by using numerically stable functions, fewer bits are needed to accurately distribute the coefficients which represent a given curve. 
       Extended Ephemeris Service 
       [0091]    In the arrangement described herein, an extended ephemeris service generates the extended ephemeris package comprising satellite orbit trajectories and clock corrections over a prediction duration that is longer than the validity interval of typical broadcast ephemeris. Orthogonal basis function coefficients combined with the satellite clock corrections are encoded into an extended ephemeris package. The range of values and resolution of each encoded field may be set to achieve a predefined accuracy requirement for the decoded values. To achieve further compression, variations in the orthogonal basis function coefficients for the satellite orbital parameters may be encoded using differential compression. 
         [0092]    The extended ephemeris service then distributes the extended ephemeris package to one or more client devices that perform GNSS processing. In one embodiment, the package is distributed by way of a communication medium. The communication medium may be a wired or wireless communication link, a physical storage device such as a memory card, or any other means of data transfer. 
         [0093]    A client device obtains the extended ephemeris package and stores the information. The client device first decodes the satellite clock corrections and orthogonal basis function coefficients, and then extracts the orbit segments of interest. The current ephemeris is then provided to a GNSS process as required for processing. 
         [0094]    Further objects and advantages of the present invention will be clear to those with skill in the art through the detailed description of a preferred embodiment below along with the described figures. 
         [0095]    In one embodiment of the present invention, the extended ephemeris service transforms the predictions from the extended ephemeris data store into an extended ephemeris package that is suitable for distribution to GNSS client devices. For each satellite orbit trajectory that is predicted, the service may represent the trajectory as a series of orbital parameters. To minimize and limit the bandwidth demand on the communication link, the extended ephemeris service models the orbital parameters using orthogonal basis functions. The coefficients of the orthogonal basis functions in addition to the clock correction model coefficients are encoded and packed in a manner that expedites transmission along with efficient storage and retrieval at the client device. 
         [0096]      FIG. 4  describes an embodiment of the extended ephemeris service  400  from  FIG. 1 . The extended ephemeris service obtains the predicted satellite orbit trajectories, clock corrections and other prediction information from the extended ephemeris data store  106 . The extended ephemeris service may transform the predicted satellite orbit trajectories into a compact representation using orthogonal basis functions  401  to model orbital parameters. 
         [0097]    In this embodiment, the orbit trajectories from the extended ephemeris data store may be represented by a tabular format of satellite X, Y, and Z position coordinates, and optionally velocity and acceleration vectors. In a tabular format, satellite positions between epochs can be interpolated so that the predicted orbit trajectories can be represented with a high degree of fidelity for the full prediction duration. However, a tabular representation may require an undesirably large data package size and may require too much memory and processor resources at a client device. 
         [0098]    A satellite orbit may be represented in a more compact form by using a set of orbital parameters. One set of orbital parameters which can be encoded in a compact form is the Keplerian broadcast ephemeris model used in the ICD-GPS-200. However, a set of orbital parameters can only represent an orbit accurately over a limited validity interval. Therefore, the extended ephemeris service may represent the satellite orbit trajectory as a series of orbit segments that cover the full prediction duration, where each orbit segment is represented by a set of orbital parameters. In other embodiments, the extended ephemeris data store may represent the orbit trajectories in a format other than the tabular format. Regardless, the extended ephemeris service may still transform satellite orbit trajectories into series of orbit segments represented by orbital parameters. 
         [0099]    Due to the temporal trend of satellite orbits, systematic variations of individual orbital parameters over several orbit segments are well-suited to being modelled by orthogonal basis functions through curve fitting as previously described, further reducing the bandwidth and memory requirement for the extended ephemeris package. Therefore, instead of encoding each orbit segment in the series as an individual set of orbital parameters, orthogonal basis function coefficients may be generated to represent an orbital parameter across multiple sets of orbit segments. One example of orthogonal basis functions that may be used for modelling sets of orbit segments are the Chebyshev functions. 
         [0100]    The extended ephemeris service may then optionally compress the sets of orthogonal basis function coefficients. The harmonic nature of orbits leads to correlation between the orthogonal basis function coefficients which model an orbital parameter over different orbit segments. In  FIG. 4 , if a compression technique is utilized  402 , the service may make use of this correlation to reduce the bandwidth and memory requirement. In block  403 , differential compression may be used on the orthogonal basis function coefficients modelling some or all orbital parameters. For example, the first set of coefficients for a parameter may stay the same, while the remaining sets are differenced with regard to the preceding set. The extended ephemeris service may be configured such that the time between curve fits maximizes the compression ratio of the extended ephemeris package. 
         [0101]    In block  404 , the predicted clock corrections of each satellite may be modelled using conventional methods, for example the af0, af1, and af2 coefficients used in the GPS broadcast ephemeris. 
         [0102]    The orthogonal basis function coefficients and the clock correction coefficients may be encoded in block  405 . The number of bits required to encode each value is a function of the numerical precision and range of values necessary to meet the required accuracy for GNSS processing. To achieve higher accuracy, a higher precision and a greater number of bits must be used. However, this leads to a smaller compression ratio and a bigger extended ephemeris package  108  which increases the bandwidth and memory requirement to transmit the extended ephemeris package  108  and store it on the device. The extended ephemeris service may adjust the numerical precision to achieve a predetermined accuracy requirement. The extended ephemeris service may also use a variable number of encoded bits to fit the range of values necessary for the current set of coefficients that may be smaller for certain orbital conditions. 
         [0103]    In some embodiments, the extended ephemeris package  108  may include other useful prediction information such as—but not limited to—ionospheric model coefficients, satellite health information, and time group delay. Also, in some embodiments, the extended ephemeris package may be encrypted to prevent unauthorized access. 
         [0104]    The resulting extended ephemeris package  108  may then be transmitted to the client device  500  using some method of data transfer, such as a wired or wireless communication link. 
       Client Device 
       [0105]    GNSS positioning computations use measurements taken from multiple GNSS satellite signals and the current ephemeris for each satellite used in the position solution. The current ephemeris refers to the ephemeris—some representation of the satellite trajectory and clock correction—which is applicable for the time of interest (i.e. the time of the measured satellite signal). In the arrangement described herein, the current ephemeris may be created from the extended ephemeris package. 
         [0106]    In an embodiment of the invention, one or more client devices  500  ( FIG. 1 ) may obtain the extended ephemeris package  108  from the extended ephemeris service and provide the current ephemeris to a GNSS process.  FIG. 5  details an example client device of this embodiment. 
         [0107]    In the example embodiment, a storage process  501  may obtain the extended ephemeris package  108  from the extended ephemeris service by way of a communication medium. The communication medium may be a wired or wireless communication link, a physical storage device such as a memory card, or any other means of data transfer. The storage process may then store the extended ephemeris information locally. In this embodiment, the format of the stored extended ephemeris  502  may be unaltered from the extended ephemeris package as obtained. Alternatively, the extended ephemeris package may be partially decoded or processed before storing for more efficient retrieval at the time when current ephemeris is required. If the extended ephemeris package has been encrypted by the extended ephemeris service, the client device may decrypt the package before decoding. 
         [0108]    As the extended ephemeris information is now stored locally, current ephemeris may be created for GNSS processing without further data transfer from the extended ephemeris service while the stored extended ephemeris is still valid. However, a more up-to-date extended ephemeris package may be obtained to replace or update the stored extended ephemeris before its validity has ended. 
         [0109]    The example client device may include a GNSS process  503  which is triggered on demand to calculate the position of the client device. Demand may be initiated by a user, an automated process, or an external event. 
         [0110]    The GNSS process may initiate a retrieval process  504  to create current ephemeris for all navigation satellites available in the stored extended ephemeris, or for a desired subset of satellites. The retrieval process may retrieve  505  the stored extended ephemeris and decode  506  the orthogonal basis function coefficients. If the orthogonal basis function coefficients have been compressed with differential compression  507  by the extended ephemeris service, the retrieval process may un-compress  508  the orthogonal basis function coefficients. The retrieval process may then compute  509  the orbital parameters of the orbit segments which are valid for the time of interest. The retrieval process also may decode  510  the satellite clock corrections from the retrieved stored extended ephemeris. The computed orbital parameters and decoded satellite clock corrections for the time of interest may then be converted  511  to the current ephemeris  512  and provided to the GNSS process  503  in the necessary format. The format of the current ephemeris may be a common industry standard, proprietary to a third-party GNSS processor, or unique to the client device system. 
         [0111]    In an alternative embodiment, one or more stages of the retrieval process  504  may be performed by the storage process  501  to optimize for response time and/or client device resource utilization when the GNSS process  503  requests current ephemeris. 
         [0112]    In another embodiment, the GNSS process  503  may comprise dedicated GNSS receiver components and circuitry on the same hardware platform as the storage process and retrieval process. Alternatively, the GNSS process may be part of a separate device.