Single-Shot Position: Cell-Phone Location without Ephemeris

A new method enables the mobile phone to compute its own position using acquisition assistance data with increased resolution in some of the fields. It benefits network operators as they can deliver the best performance with minimum bandwidth requirements, making this especially relevant in emergency-call situations.

By Javier de Salas and Frank van Diggelen

In assisted GPS (A-GPS) and A-GNSS, some information in the form of assistance data is sent to the mobile terminal equipped with a GNSS receiver. This data helps the receiver acquire satellite signals faster and at lower power levels as well as compute its own position. Assistance data is essential in many GNSS use cases but it is especially relevant in emergency calls from mobile terminals (e911, e112) where a fast response and the best sensitivity are required. Mobile subscribers are often in environments where direct satellite visibility is impaired because the user is inside a building or there are other obstructions. Emergency situations also require a very fast response (time-to -first-fix or TTFF), typically within 30 seconds, so the performance requirements imposed on the GNSS receiver are very stringent.

GNSS assistance data is standardized by 3GPP and 3GPP2 in two different types, broadly known as mobile-station (MS) based and MS-assisted. MS-assisted positions are computed by a server. MS-based methods enjoy certain performance benefits in position accuracy and response time when compared with MS-assisted methods. However, the amount of assistance data required for MS-based operation is substantially larger than the assistance data required by MS-assisted methods.

For this reason, some network operators choose the MS-assisted methods for their emergency-call services. Larger bandwidth requirements are of deep concern if many callers demand the services at the same time, because network capacity could be challenged when it is most needed.

This article describes a method that enables the mobile terminal to compute its own position, thus enjoying the benefits outlined above but with the same assistance data as in MS-assisted methods, only with increased resolution in some of the fields. We call this method single-shot MS-based. Network operators benefit because they can deliver the best performance with the minimum bandwidth requirements, especially relevant in emergency call situations.

Some 3GPP specifications will need to be modified slightly to increase the resolution of the relevant assistance data fields, namely, 3GPP TS 44.031, 3GPP TS 25.331, and 3GPP TS 36.355

Bandwidth versus Performance

Assisted GNSS information is exchanged between the location server and the mobile device using standardized protocols. Several bodies create different specifications: 3GPP, 3GPP2, and the Open Mobile Alliance (OMA). Broadly speaking, we can say that 3GPP and 3GPP2 work on protocols that are used over control plane and OMA works on protocols that are used over user plane.

Control plane refers to the use of cellular signaling channels as the transport mechanism for the assistance data and position information. User plane refers to the use of traffic channels (see Figure 1). When you get a phone call, the control plane makes your phone ring. When you browse the web you are using the user plane.

Figure 1. Control plane is used for signaling purposes, user plane for transferring user data.

Signaling channels are not designed to transfer large amount of information, so it is important for 3GPP and 3GPP2 to make the protocols efficient and save bandwidth while maintaining the best performance. Cellular traffic channels are designed to transport much larger amounts of data and thus the bandwidth restrictions are less important than in the control plane case; OMA typically addresses richer GNSS features for Location Based Services (LBS). This is why network operators often support emergency call location using control plane, leaving the user plane for commercial applications. It is also a very good way to separate emergency traffic from LBS traffic so that the former is never compromised by lack of capacity coming from heavy use of commercial location applications.

Two different types of assisted GNSS have been standardized, known as MS-based and MS-assisted in Global System for Mobile Communicatios (GSM) and code-division multiple-access (CDMA) specifications, and as user-equipment (UE) based and UE-assisted in Wideband Code Division Multiple Access (WCDMA) specifications.

MS-assisted refers to the case where the mobile device equipped with a GNSS receiver does not compute its own position but it is instead computed in a location server in the operator’s network. Assistance data is sent to the mobile device to help acquire satellite signals faster. Remember that GNSS signal acquisition involves a three dimensional search (satellite, frequency and delay) that requires intensive signal processing. So assistance data is sent in the form of visible satellites including expected delays and expected Doppler shifts. These values are provided at a reference time and relative to an approximate location for the subscriber. The approximate location typically comes from the location of the serving cell tower. The reference time, but not the approximate location, is normally included as part of the assistance data. After a certain number of satellites are acquired, measurements are sent back to the location server for it to compute the subscriber position. GNSS measurements for each satellite include the measured delay, measured Doppler frequency and an estimation of the signal power to noise ratio. Assistance data in MS-assisted is referred to as “acquisition assistance”. It contains the minimum information so it is very efficient in bandwidth. See Table 1 for an exact bit count of the GNSS acquisition assistance. This table will be used as an example throughout this paper. In this particular example, it is assumed that assistance data is sent for 16 satellites.

MS-based refers to the case where the GNSS-enabled mobile device computes its own position locally. A different set of assistance data parameters are sent to the device to help it acquire the GNSS signals as well as calculate its own geographical location. Measurements are processed by the mobile device internal circuitry until the locally computed position is deemed accurate enough to meet the requirements received in the location request or a timeout is reached. Location information (latitude, longitude, altitude) is then sent back to the network in response to the location request. Assistance data in MS-based consists, at a minimum, of three elements: an approximate location (coming from the serving cell), an approximate time (accurate to a few seconds) and a description of the satellite orbits and clock errors referred to in the specifications as navigation model. See Table 2 for an exact bit count of the GPS assistance data in MS-based. The GNSS receiver uses the approximate location, the approximate time and the navigation model to estimate the expected delays and Doppler shifts of the visible satellite and thus proceed to the acquisition of satellite signals very much like in the MS-assisted case. Satellite measurements (code delays in the simplest implementation) and navigation model are used to calculate the receiver’s own position as explained below.

Advantages of MS-Based over MS-Assisted

We can see from Tables 1 and 2 that the amount of data used in MS-based i
s significantly larger than that of MS-assisted, in fact by a factor of seven! So why do some operators still decide to use MS-based over MS-assisted? The answer is there are noticeable performance advantages when using MS-based. An in-depth description of these advantages is out of the scope of this paper; but we will provide descriptions of what we see as the three more important ones.

Better Estimate of Position Accuracy. The first advantage lies with the fact that in MS-based mode the mobile device has a much better knowledge of the estimated accuracy of the position that it has computed internally. This was implicitly mentioned in the description of the MS-based and MS-assisted method above when we explained that in MS-assisted mode, the mobile terminal sends the measurements after a sufficient number of satellites (with certain range uncertainties) have been acquired. This is precisely the problem, what is a sufficient number of satellites? It is not easy to know for the mobile receiver because it does not know what positioning algorithm or what satellite subset the location server will use in its calculations. As such, it is more difficult to guarantee the quality of service of the position in the MS-assisted method. One could perhaps argue that the mobile receiver has an idea of the satellite geometry based on the Azimuth and Elevation fields (see Table 1) and therefore can perform a more educated estimation than just using the number of satellites and their associated uncertainties. This argument will only be valid if the mobile device knew exactly what the satellite subset is that the location server will employ in its position computation. Different satellite subsets yield different estimated accuracies. In addition to this, azimuth and elevation fields are optional in other positioning protocols such as Radio Resource Location Protocol (RRLP) and Radio Resource Control (RRC) and are also quantized with a value of 11.25 degrees, which deems them practically useless to quantify the satellite geometry in the critical cases where the dilution of precision (DOP) values are large.

Kalman Filter. The second advantage comes from the use of sophisticated navigation filters (for example, Kalman filters) by all GNSS manufacturers. In the MS-based method, the final position estimate that is sent to the network is computed using consecutive sets of measurements that help the position converge using the receiver dynamic model to smooth the resulting positions for greater accuracy. Conversely, in MS-assisted mode, the position computation engine only has access to a single set of measurements and therefore cannot employ sequential navigation filters.

Coarse-Time A-GNSS. The third advantage is perhaps the more difficult to grasp. It has to do with the fact that most (if not all) A-GNSS location servers only provide reference time information that is accurate to within a few seconds. On the other hand, for classical GNSS position computation, knowledge of absolute time accurate to a few milliseconds is required. Typically, it is the task of the GNSS receiver to decode the accurate satellite time information that comes modulated on the GNSS signals as part of the navigation message. However, in environments where satellite visibility is impaired, such as indoors, the satellite signals may be so low that the timing information cannot be decoded from the satellite due to excessive Bit Error Rate. In these situations, the absolute time can be set as an additional state that to be solved as part of the complete navigation solution therefore increasing the position yield in of the GNSS receiver in difficult environments. We refer to this technique as coarse time A-GNSS.

There is no technical reason why this technique could not be implemented in a location server in the operator’s network as opposed to the mobile device itself. However, for this technique to work properly, the mobile device should indicate to the location server whether or not it has successfully decoded the time from the satellites signals (or perhaps other sources). This is normally done by setting an associated time-uncertainty value with the time reported with the GPS measurements. There are some 3GPP specifications (for example RRC prior to R7) that do not support this parameter so they have hindered the adoption of the coarse time A-GNSS technique in MS-assisted mode.

Continuous Navigation. By delivering ephemeris data (good for several hours), MS-based techniques have an advantage over MS-assisted for continuous navigation. This advantage is not addressed further in this article, where we are focused only on first fixes.

Single-Shot MS-Based Method

We present a brief reminder of how GNSS positions are computed in order to determine what assistance data is strictly needed for a mobile terminal to compute its own location. We will use a simple least squares algorithm for simplicity but the conclusions are extensible to the cases of other positioning algorithms such as Kalman filters.

The observation equations are typically linearized around an approximate location. They can be easily presented in matrix form as:

Δ y = A Δ x

where Δ y is a column vector [m x 1] containing the difference between the predicted and measured pseudo-ranges for the m satellites measured by the GNSS receiver. The predicted pseudo-ranges can be obtained using the acquisition assistance data (codePhase and intCodePhase fields.)

Δ x is a column vector [4 x 1] containing the change in the “state” from the approximate position. The state has four unknowns x, y, z and b. x, y, and z are the change in the local East (longitude axis), North (latitude axis) and Up (altitude axis) coordinates from the reference position, b is the common mode error (mostly from the internal receiver clock error) in distance units.

A is an [m x 4] matrix, the first three elements in each row u_x , u_y , u_z are the coordinates of the unit vectors from the receiver to the satellite, the last element is a 1 for the common mode error. A is sometimes referred as the geometry matrix.

Coordinates of unit vectors can be written as a function of the azimuth and elevation of each satellite. Simple trigonometry yields:

u_x = cos (el) * sin (az)

u_y = cos (el) * cos(az)

u_z = sin(el)

In the coarse-time case there will be a fifth column of A containing the range rates, which are provided in the MS assistance data.

The goal is, of course, to determine the change in the state (our unknowns). Using simple least squares

Δ x = (A^T A)^–1 A^T Δ y

we can easily determine Δx. The coordinate changes in Δx (delta position) will be applied to the approximate location to obtain the new position.

Assistance Data Required

To re-cap from the previous section, we have seen that to compute Δx we need:

• Expected pseudo-ranges for satellites in view (from acquisition assistance)
• Measured pseudo-ranges (from the GNSS receiver)
• Azimuths and Elevations for the geometry matrix (from acquisition assistance)

It would seem that if the mobile device receives acquisition assistance and measures the pseudo-ranges for a few satellites, it has everything that is required to compute a position (or at least a delta position) inside the GNSS mobile device. The delta position is relative to the position used to compu
te the acquisition assistance. Have we achieved our goal of computing position inside the mobile device with acquisition assistance? Not quite. Let’s now look at the acquisition assistance data in more detail.

We explained that we obtain the required expected pseudo-ranges from the acquisition assistance fields codePhase and intCodePhase. The codePhase field is defined with a resolution of one GPS chip, equivalent to 300 meters. Recall that we subtract the expected pseudo-range from the measured pseudo-range before we use the measurements in the position solution so this means if our expected pseudo-range was in error by, say, 150 meters because of the low resolution of this field, this is similar to making a measurement error of that amount, which of course will cause an unacceptable position error. This means the resolution of the codePhase field would need to be increased to be able to compute position. For a resolution of 2 meters, 8 more bits would need to be added.

The second topic of interest relates to the azimuth and elevation fields. These are needed to construct the geometry matrix A. As mentioned before, in 3GPP location protocols the azimuth and elevation of the acquisition assistance element are defined with a resolution of 11.25 degrees. Sines and cosines (needed to calculate the coordinates of the unit vectors) with such large angle errors will also yield large position errors. In Long-term Evolution Positioning Protocol (LPP), the situation has improved with the resolution being 0.7 degrees.

In an effort to quantify how the angle quantization affects the position error, we have run simulations that plot the 95 percentile of the HDOP error as a function of the angle error in azimuth and elevation (see Figure 2.) HDOP is proportional to the position error so this seems to be a reasonable choice. N is the number of satellites used in the simulations. As you might expect: the fewer the satellites the greater the effect.

Figure 2. HDOP error vs Az/El error. We use HDOP as a proxy for the expected position error: if the HDOP changes by 10 percent, we expect the position error to change by a similar amount.

We can see from the plot in Figure 2 that for an angle resolution of 0.7 degrees as currently defined in LPP, the 95 percent HDOP error is under 12 percent. If we wanted to make the worst error (N=4) under 2 percent, we can see that the resolution should be increased to 0.1 degrees. In order to meet this goal, 3 more bits would need to be added to both the azimuth and elevation fields in the acquisition assistance.

Another effect that must be noted is the possible change in the azimuth and elevation from the time the assistance data is received to the time the receiver computes its position (or delta position). In an emergency call scenario, typically we assume this time will not be greater than 24 seconds. Note the total allowed response time for an E-911 call is 30 seconds, including call establishment and network latencies. Simulations based on satellite geometry show that the worst-case effect is approximately of the same order of magnitude as the angle resolution discussed above, and therefore its impact in HDOP is just a few percentage points in the case of N=4.

At this point we seem to have everything we need to compute positions (or delta positions) inside the mobile terminal with the same acquisition assistance used in MS-assisted; albeit with slightly higher resolution in some of the fields.

To facilitate the comparison with MS-assisted and MS-based methods, Table 3 summarizes the exact bit count needed for Single Shot MS-based.

Optionally, if an absolute position is required in the mobile device instead of delta position, it would also require the approximate position (reference location) to be sent along with the rest of the assistance data (acquisition assistance, reference time). However, the MS-based performance advantages listed above can all be realized without the reference location, using only delta position. This is why we have not included Reference Location as an element that is needed for Single Shot MS-based.

Conclusions

We have seen that Single Shot MS-based can be used to enable all the MS-based performance advantages with, essentially, the same assistance data that is used in MS-assisted. Minimal additional bandwidth is required due to the increased resolution of some of the fields. Single Shot MS-based is therefore the best option for network operators that deploy A-GNSS based emergency location.

Not only does MS-based require significantly more bandwidth than MS-assisted (~ 7x) or Single Shot MS-based (~ 6x); but the absolute difference will increase with additional GNSS satellites such as GLONASS, SBAS, QZSS, Compass, and Galileo. Imagine all navigation models have to be sent for all satellites in view and for all GNSS constellations! Acquisition assistance can easily be made generic for every GNSS constellation since it is just “range and Doppler” and, in fact, this is the way it has been conceived in LPP where the dynamic ranges for all parameters are no longer restricted to GPS but allow other GNSS constellations.

Javier de Salas is director of GPS product marketing at Broadcom. Previously he worked at Ashtech, Magellan, and Global Locate. He has an MS in electrical engineering from Universidad Politecnica de Madrid.

Frank van Diggelen is chief navigation officer and senior technical director for GNSS at Broadcom. He is also a consulting assistant professor at Stanford University and is the author of A-GPS: Assisted GPS, GNSS and SBAS. He holds more than fifty issued U.S. patents on A-GPS and has a Ph.D. in electrical engineering from Cambridge University.