Statistical ramblings of a Moonbat

I will try to use this medium to talk about my statistical musings

First world problem of Global Positioning Systems

with one comment

In ancient times, circa AD 2000, getting a GPS device to give you an accurate location was nothing short of a black magic art. After sacrificing three goats, the navigational gods might align at least 3 satellites on your horizon or if they are especially pleased with you for throwing that virgin down the funeral pyre, you might see 4 satellites in your horizon thereby giving you not just the latitude and longitude of your location but an accurate time reference.  Now fast forward 10 years and there are countless countries trying to emulate the highly successful US based GPS with their own navigational satellite constellations. The primary driving force has been the potential for an US based system being used as a bargaining chip on the whim of an US lawmaker (hint ICANN and the internet domain naming controversy). Some of the navigational satellite constellations are:

  1. GPS (USA) has 32 satellites,
  2. GLONASS (Russia) has around 23 satellites
  3. QZSS (Japan) 3 to 4 primarily over Japan,
  4. Beidou (China) 16 initially but will expand to 40 eventually,
  5. Galileo (EU) final system will have 30 in orbit
  6. IRNSS (India) possibly 3, primarily over India .

Add to the above list, numerous ground and satellite based augmentation systems that are useful for correcting any navigational errors. So a GPS receiver in 2013 could potentially be receiving signals from more than 100+ satellites to help find its position. You might assume that all these added information might provide better localization accuracy. However, the reality is quite different. There are two limiting factors. First limitation arises from the reduced memory and processing capabilities within GPS semiconductors which sets an upper limit to the number of satellites that a receiver can search or track at any time. This would be fixed over time due to Moore’s law, but the second issue is much more fundamental and it rests on the algorithms that are used to find your location.

A GPS receiver is essentially measuring the time of flight of a radio wave from a satellite to the receiver. When you multiply this time difference by the speed of light, you get the range, or in GPS parlance, pseudorange between the satellite and your GPS receiver. In addition, the GPS receivers have access to a table of values called ephemeris which helps to accurately compute the position of a satellite at any given time. So using the known position of satellites and the range measurements to them, your receiver has to figure out its own Cartesian coordinate (xy & z). However, there is another hidden parameter that need to be estimated if you care to have a very accurate location. This hidden parameter arises from the cheap clock reference used in your GPS semiconductor. More than likely your GPS semiconductor in you smartphone doesn’t have an atomic clock that is synchronized with the atomic clocks on these navigational satellites. So there would be a clock bias (let’s call it \tau ) between your receiver and GPS satellites that need to be accounted to get an accurate position. Consequently, there are four parameters (3 Cartesian coordinates and 1 clock bias) that need to be estimated from the pseudorange measurements and the known position of the satellites using a technique called Multilateration. The most popular algorithm used in GPS for Multilateration relies on Taylor series approximation to linearize the state equation that relates the pseudorange to the unknown parameters and subsequently apply least-square solution to get x, y, z, \tau . You may read about the details about this computation in this very concise document.

Least-square algorithm is vulnerable to outliers or extremities in measurement. This is because the objective of a least-square algorithm is to find the parameter set (in our case x, y, z, \tau ) that would result in the lowest sum of square difference between the pseudoranges calculated from x, y and z and the measured pseudoranges from each satellite. Consequently, if there are couple of satellites that are producing some extreme pseudorange values due to either intentional degradation by the host government or due to a fundamental wireless propagation issue called multipath fading, then location estimate by GPS would be inaccurate. I have touched upon this fading previously where it was used to aid indoor navigation.  So in 2013, the accuracy of a GPS receiver is not limited by the number of satellite on its horizon but rather an algorithmic limitation arising from the choice of satellites that it decided to include in its Multilateration algorithm.

First World Problem

First World problem

Way back in 2009 while working on indoor navigation, I had observed a similar phenomenon with IEEE 802.15.4 receivers called XBee. For indoor localization, I was tracking the position of a wireless transmitter from signal strength measured by a set of receivers that were positioned at known location within the lab (ERL 114 @ MST). Using the popular Friis transmission equation, I was translating the signal strength values to range measurements which were then subsequently passed on to a Multilateration process as in GPS to find the position of the transmitter. In this setup, I observed that some receivers were skewing the estimated position of the transmitter badly. My initial strategy was to eliminate these offending receivers from the Multilateration algorithm. However, the method that I initially relied on was to only include those receivers that showed high signal strength values. The assumption here was that if the signal strength values measured by a receiver are high then those receivers are close to the transmitter and consequently less affected by noise. However, the noise that I was observing was primarily due to multipath fading which is an altogether different beast than the typical Gaussian noise that most estimation algorithms (least squares in particular) are accustomed to. In the lab multipath fading noise arises when radio signals interfere additively or destructively with a delayed copy of itself. Time delayed copies of the radio signals arises when the signals are reflected by radio obstacles such as walls, doors, people etc. Consequently, you could observe very low signal values when you are close to the transmitter and vice-versa.

My solution to this problem was  was to develop a simple receiver quality metric called R-Factor (Receiver Factor) that accounts for the extent of multipath fading observed by a receiver. One of the characteristics that I observed about the range measurements from a receiver under mulitpath fading was that it typically showed correct range values but extreme jumps in range values were more frequent than a receiver that wasn’t experiencing considerable multipath fading. If a distribution function was plotted for the range measured by the receivers then receivers under severe multipath fading will have fatter tails than those that are under moderate fading. In statistics, Pearson’s measure of Kurtosis is used to measure the fatness of a distribution’s tail. R-Factor for a receiver used for range measurement is the Kurtosis of the distribution of its range measurements. You can read more about R-factor and how it was derived for an IEEE 802.15.4 receiver under multipath fading in my following conference publication*.

* Basheer, M.R.; Jagannathan, S.; , “R-Factor: A New Parameter to Enhance Location Accuracy in RSSI Based Real-time Location Systems,” Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON ’09. 6th Annual IEEE Communications Society Conference on , vol., no., pp.1-9, 22-26 June 2009

Written by ranabasheer

February 17, 2013 at 8:33 pm

One Response

Subscribe to comments with RSS.

  1. […] of signal strength at a location in the lab whereas the third parameter () is related to the R-Factor (latexgamma $) that I developed to indicate the line of sight condition through the kurtosis […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: