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:
GPS (USA) has 32 satellites,
GLONASS (Russia) has around 23 satellites
QZSS (Japan) 3 to 4 primarily over Japan,
Beidou (China) 16 initially but will expand to 40 eventually,
Galileo (EU) final system will have 30 in orbit
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 (x, y & 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
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
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
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