LORAN stands for LOng Range Aid to Navigation

Started as a service by the Coast Guard for ship navigation during WW II. Coverage area in 1973:Loran History notes

Key idea: measure the difference in arrival time between two beacon pulses from known locations. Points of equal difference from a hyperbola:

LORAN typically used three stations: one master and two secondaries. The secondaries retransmit the instant they hear the master beacon (with a precise fixed offset).

For each (master, secondary) pair you get a hyperbola. The receiver lies at the intersection of the two hyperbolas.

Radio beacons have limited range, so there were many remote LORAN stations (considered a bad assignment in the Coast Guard).

First satellite-based navigational system – see Wikipedia.

• This was mostly used to provide (US) ships and submarines with precise locations.
• NAVSAT used 5 pairs of satellites (for redundancy) in low-earth polar orbits.
• Ships could get a reading accurate to about 100m from one satellite, although they may have to wait an hour for a satellite to appear in view.
• It also enabled 50 ms accurate time sync worldwide for the first time.

• These satellites travel at 17000 MPH, which means there is a significant Doppler effect that varies based on the angle between the receiver and the tangent of the orbit.
• Since this angle varies for all locations of the satellite, you can compute the angle given the measured shift (of a known reference signal).
• You also need to compute the precise location of the satellite, for which the Navy provided daily updates.
• Given the angle and the precise orbit of the satellite you can estimate location with several consecutive readings (beacons every two minutes).
• Since readings are sparse, typically complement them with inertial navigation.
• Provides only 2D location: you need to be on the surface of the earth.
• Also limited in practice to slow-moving receivers.
• Opened to civilians in 1967 and retired in 1991 (due to GPS)

RAND History of GPS

GPS testing started mid 70s both on the ground using fake satellites (“pseudollites”) and test satellites. Key innovations include:

• atomic clocks
• 4 satellites in each of 6 orbits
• use of (any) 4 satellites to recover 3D location + time
• can also get 2D location with 3 readings (since altitude = 0)

Currently 31 GPS satellites in use; several competing system proposed or partially deployed.

Basic idea is trilateration: measure the distance from 3 references points.

• Distance is measured by time of flight
  • Beacon carries its transmit time
  • Speed of light varies some with the atmosphere – limits accuracy
• But we don't know local time:
  • Use 4 satellites and solve for local time as well
  • Qualcomm assisted GPS does know local time – can get a fix faster and with fewer satellites
• Extra readings improve accuracy, also enable error corrections for the atmosphere.
  • Good receivers listen to up to 20 channels simultaneously, 6-10 is more typical
• GPS signal is weak, hence need line of sight (outdoors)

To prevent opponents from using GPS the DoD initially added pseudorandom noise to the transmit time.

• If you have the key, you can calculate the noise and remove it.
• Users without the key were thus less accurate (by 10-30 meters)

Problem 1: Differential GPS

• Some receivers KNOW where they are exactly, so they can calculate the noise.
• They can then transmit corrections locally (e.g. using Coast Guard radio signals)
• Differential GPS receivers recieve the local corrections and apply them
• Atmospheric corrections are also included
• Current FAA Wide Area Augmentation System does this with satellites.

Problem 2: Gulf War

• US ran out of military-grade receivers
• Selective Availability was turned off during the war, so DoD could use civilian equipment

SA turned off altogether in 2000.

Idea: enhance accuracy using extra infrastructure and the cellular network

Driven by E911: mandate for precise location information for 911 calls

Assistance Server:

• Good receiver at a known location
• Transmits helpful data to the phones
  • Orbit and atmospheric information
  • May establish precise time (CDMA)
• Could also help with computation, but no longer necessary

Qualcomm phones seem to get good fixes even indoors

Approach 1: build a WiFi signal strength map of your location, then use it compute location from readings

• Ekahau product
• Hard to build the map
• Small physical area in practice (e.g. manufacturing plant)

Approach 2: figure out what beacons you can hear in every location

PlaceLab: use WiFi beacons to estimate location, even indoors

• PlaceLab PDF
• Use a variety of beacons: WiFi, GSM, Bluetooth, ??
• Each beacon must have a unique ID (easy)
• Database maps beacon IDs to a location estimate
• Overlap multiple estimate to get to 20m accuracy in a dense urban area (Seattle)
• Fair amount of work on how to estimate location given a set of beacon IDs and signal propagation data

Beacon sources:

• war driving sites, see Wigle.net
• FCC basestation data
• collect your own

Idea: given a picture of where you are, look it up in a (very large) database to figure out where you are

• Could be very precise
• Would provide orientation as well
• Need many images (but this is here now for major cities, at least for streets)
• Big database search problem