Search TheCodeArtist

nGPS : Location fix without GPS

NOTE: Skip this post if you do NOT live on planet earth.

This is one of the ideas that i hit upon when preparing for a talk Sensors on Android @DroidCon2011. It is an unusual application of the on-board sensors present most Android devices. Due to lack of time i was unable to present it in much detail during my talk. So here goes...

nGPS (NO GPS) is a way of obtaining a location fix without using any GPS, AGPS, Wi-Fi Positioning and cell-site triangulation technologies.

Why would anyone want to use nGPS
- Pure GPS based systems take upto 10mins for 1st fix.
- AGPS, Wi-Fi positioning require an active data-connection.
- Cell-site triangulation requires network coverage.

So without any of these technologies at our disposal, how do we obtain a "location-fix" i.e. a latitude-longitude pair representing our current position. The answer lies in the magnetic-field sensor.

The Earth's magnetic field, as measured by a magnetic sensor on the Earth's surface, is combination of of several magnetic fields generated by various sources. These fields interact with each other and the net resultant what the magnetic sensor measures. 
World Magnetic Model (WMM)
Major contributors to a magnetic-field: 
+ Conducting, fluid outer core.
+ Earth's crust and upper mantle.
+ Electrical currents in the atmosphere. 
+ Local magnetic interference.
By filtering the local magnetic interference due to other electronic/electrical devices, we have a unique magnetic-field signature present at each place on earth. The WMM aims to provide an accurate estimate of this field. A device (having a magnetic sensor) can measure the components of this field. Then comparing it with the WMM values of the earth's field, one can identify the latitude/longitude of the present location.
Android contains built-in support for the WMM using the GeomagneticField class. The GeomagneticField class utilises the WMM internally to provide an estimated magnetic field at any given point on Earth at a given time. The important thing to note is that this class accepts the location (alongwith altitude and time) and provides the expected magnetic-field at that position (at that particular altitude and instant of time).

To determine the location using the GeomagneticField class, requires some reverse-lookup trickery on our part. More on it in another post.

UPDATE : A recent talk on Sensors and Location based services on Android at blr-droid meetp#12 featuring nGPS among other things.

18 comments :

  1. how to convert results from magnetic-field sensor from an android device to coordinates using World Magnetic Model? Is there a webservice which does that or how?

    ReplyDelete
  2. The World Magnetic Model provide a straightforward equation to generate the magnetic field for any given location. To generate a position from the magnetic readings, one needs to perform a iterative reverse-search as follows:

    1. Start with a default location for the first iteration.

    2. Calculate the magnetic field expected at that point using the WMM.

    3. Find the difference between the calculated magnetic-field and the readings from the sensor.

    4. Based on the difference, pick a new location and repeat steps 2 & 3. Keep doing this until the difference is within acceptable limits.

    5. The location you have is the best estimate of your present location according to the magnetic-field readings.

    A look-up table with pre-calculated field values for sevral locations across the globe would speed-up the search by helping in choosing a nearby location for the first iteration.

    This can be entirely done on the Android device without an external connectivity using GeomagneticField class goo.gl/xFyXS

    ReplyDelete
  3. How do you compare the magnetic field results of the WMM calculator with the magnetic sensor's readings?
    From inputing my lat and long in the WMM calculator I get a Total Field of 44671.4 nT, but the readings from my phone's magnetic sensors gives me a Total Field of 4-6 E-5, depending on its orientation...

    ReplyDelete
    Replies
    1. While the magnitude may be the same for 2 or more points, the individual components tend to differ. Thus comparing the individual components to the expected values and then modifying the co-ordinates (repeat until the difference is significantly small) will help us zero-in on our location. On Android, android.hardware.GeomagneticField is an helpful class for the same.

      Delete
    2. Also note that one needs to properly align the device flat with respect the earth's surface so that each of the magnetic-field components are along the actual corresponding direction. If this is NOT possible then, one needs to use the accelerometer to determine the actual orientation and remap the axes and calculate the corresponding magnetic-field components accordingly.

      Delete
    3. Ah, so to get the correct magnetic field components' value despite the device orientation I would need to change its coordinate system from the device coordinate system to the world coordinate system. By doing this, the values of the magnetic field components at a particular location obtained by the sensor should roughly be the same as that specified in the World Magnetic Model. Is this correct?

      Delete
    4. Sorry, could you possibly explain how to remap the axes? I tried multiplying the values of the magnetic field components with the rotation matrix to get the correct values like this:
      x' = R11*x + R12*y + R13*z
      y' = R21*x + R22*y + R23*z
      z' = R31*x + R32*y + R33*z
      But it didn't seem to work. The values were still affected by the device orientation. Is the method I'm using wrong?

      Thanks before.

      Delete
    5. Right you are. And the best part is that android.hardware.GeomagneticField is built upon the World Magnetic model.

      Its just a pity that it provides the 3 components of a magnetic field for a given geographical co-ordinate(at a specific time). So one essentially needs to implement a "reverse-lookup" to obtain the necessary location co-ordinates after reading a set of magnetic-field components from the sensor.

      Delete
    6. I will look into that. Thank you for your help.

      Delete
  4. I have heard that the GPS/GLONASS systems are getting accurate to within 1 meter. To what extent is the magnetic model accurate and what accuracy within meters does it provide?

    ReplyDelete
    Replies
    1. Earth's magnetic-field vector variation is not constant and varies at different rates at different places. Hence the accuracy of the location will depend on the location in question. At locations where the field-variation is high, the accuracy will be high too as there will be a significant variation in the geomagnetic in the two nearby locations.

      Also the degree of precision of magnetometer(digital-compass) used to measure the fields will determine how small a variation can be measured; which in turn will determine the smallest distance that can be identified.

      Delete
  5. How precise would it locate location of an device, and would you be able to map a route with it..

    And how do you get rid of the magnetic field due to magnetic fields from wires and other electronic devices..

    ReplyDelete
    Replies
    1. As the magnetic-field varies at different rates at different places, the positional accuracy differs accordingly(from few metres to few 100metres). In places with a high field gradient, even a small change in position leads to a significant measurable change in the magnetic-field.

      The static interference due to electrical systems can be countered by measuring the field in a prior pass through the region and updating the field-map accordingly. This is practical in case of preparing indoor maps of buildings.

      Delete
  6. Brilliant idea Chinmay! I tried this but often I get reading from sensors that are twice that of one predicted by magnetic model, also it fluctuates a lot (any vehicle passing around the house). This can completely throw off the iterative reverse search you proposed. How do you think this can be countered? Many Thanks

    ReplyDelete
    Replies
    1. As you have found out, there are indeed 2 types of magnetic(electro-magnetic) interference involved.

      1. Static (nearly constant).
      Fixed objects like power-lines and electrical appliances tend to project their own magnetic-field. However small they may be, they often tend to introduces major errors in the nGPS calculations. To counter such fields one needs to calculate the theoretical magnetic field at the present location(i.e. requires lat-long of current location). Then the difference between the theoretical and observed values magnetic-field needs to be saved for future reference. The static difference can be subtracted from the observed values each time before nGPS calculations.

      2. Dynamic (quickly changing magnetic-fields)
      The effect of these fields can be overcome by capturing multiple samples over a short period of time and then picking the median value amongst the multiple samples of each component. For more accurate calculations, the set of values can be "winsorised" and the resultant mean can be used as the magnetic-field for nGPS calculations.

      In summary:

      [a] nGPS works best in wilderness where external interference is at a minimum. Imagine a dense tropical forest in a mountain valley where you are unable to obtain a GPS lock.

      [b] To improve nGPS accuracy in areas with plenty of electro-magnetic interference, a prior knowledge of the static fields is critical. This can be be arranged by a one-time enabling of the existing location providers(GPS, Cell-triangulation, WiFi etc.) and capturing the magnetic-field.

      Delete
    2. I dont know if i believe in this approach.
      old tech navigation relies on time and stars
      magnetic mines are dipneedle based
      a dip needle is a compass with gimbel bearings
      surveyors used those to find iron pins
      you merely wait for it to steady down then walk around until you see a radical change this will be the location of a 1/2" x1' iron pin

      at any rate the 1000 mile lines on your world map are basically iron concentrations on a broad scale

      on a fine scale you can see a lot of beer cans and scrap metal


      i have a garmin etrex 30 it has GPS/GLONASS 24recievers so at any given time it has 30 satellites above the horizon it also has a barometer/altimeter and a "3d" compass
      garmin uses the compass to supplement the backtracking compass which seems to jump around a lot on any other model gps

      you have no access to the compass readings other than calibration
      the altimeter keeps a log i think it assumes if the long lat stays steady that the weather is changing the calibration involves using the gps elevation to determine the altimeter elevation

      google has a nexus7 ive been looking into it has 3d accelerometer 3d gyroscope and gps but you can dig into the code and maybe come up with position

      perhaps a gunsite added to the nexus would let you do a stellar sighting

      then with the accelerometer and a mass con map and Hatcher's formula and gps and a compass you could know where you're at
      and whether the stuff beneath your feet is granite, iron or gold


      Pete

      petertyj at yahoo dot com

      Delete
  7. pesky solar inconstancy

    it's what led the hippies and fascists to abandon their 'cycles' of global-cooling-FUD/global-warming-FUD to hide inside global-change


    this nGPS would need constantly updated model and position at least which require

    * location source (GPS, tower masts, wifi voyeurism)
    * internet


    magical pot calling the kettle high



    ReplyDelete