Figuring out a common time base

Using the locator beacon network from the simulator for an indoor navigation system that follows my own requirements means that a receiver must be able to use the network without sending out signals to each node. The receiver must be able to determine its distance from multiple nodes without actually sending anything to those nodes. This is accomplished in the GPS network by synchronizing all the satellites on a very precise clock. Once the transmitter and the receiver have a clock in common the receiver can easily compute its distance to the transmitter:

  1. Transmitter sends a signal at time X saying “It’s time X!”
  2. Receiver receives that signal at time Y
  3. Distance = ( Y – X ) / speed_of_light

So how do you build a common time base on a ad-hoc network of locator nodes run by a random assortment of people? The short answer is that you don’t. Assuming a few things about all the hardware involved you can get by coming up with an ad-hoc time base that still lets you compute distance without requiring any kind of central authority.

This assumes a few things about beacons and receivers in the network:

  • Each node (beacon or receiver) has a fixed (and known) amount of receiver lag. This is the time between when a signal hits the antenna and when it’s pushed to whatever internal system can tag it with the internal clock of the node. This is Send(N) for node N.
  • Each node has a fixed (and known) amount of transmitter lag. This is the time between when a message is sent and timestamped, and when it actually leaves the transmitter’s antenna. This is Recv(N) for node N.
  • None of the nodes are lying.

With these assumptions, the system is relatively straightforward. Any node can compute the translation from its own time base Time(n, t) to some other node’s time base Time(m, t) by pinging that node:

  1. Node N generates a random number ping_key
  2. Node N broadcasts a message containing ping_key and records ping_time = Time(N, t).
  3. Node M receives that broadcast message and records receipt_time = Time(M, t).
  4. Node M sends out a broadcast of its own with: NodeID(M), ping_key, Send(M), Recv(M), receipt_time, Time(M, reply)
  5. Node N receives the response and notices that ping_key matches its own ping_key.
  6. Node N computes its relative time base with M as follows:
    • Total_time = Time(N, reply_receipt) – Time(N, transmission) – ( receipt_time – Time(M, reply))
    • distance_time = (Total_time – Send(N) – Recv(N) – Send(M) – Recv(M) )/2
    • distance = distance_time/speed_of_light
    • time_base_difference = Time(M, t) – Time(N, t) = Time(M, receipt) – Time(N, transmission) – (distance_time + Send(N) + Recv(M))
    • time_base_difference2 = (Time(M, reply) + distance_time + Send(M) + Recv(N) ) – Time(N, reply_receipt)
  7. Node N stores NodeID(M), time_base_difference, distance in its table of nearby beacons. (time_base_difference and time_base_difference2 should be equal assuming that all the lag numbers are right and the distance hasn’t changed. If they drift apart something is wrong.)

This mechanism enables each beacon to keep a constantly updated time base for every node in range via the same packets it is using to determine distance to those beacons. Beacons can then send out everything they know:

  • Their own location (estimated from GPS and refined via the algorithm in the simulator)
  • Time(beacon, broadcast)
  • For each beacon N in range:
    • Node ID of N
    • Time(N, broadcast)

Here comes the unfortunate part: In order to figure out its own time base relative to a beacon each receiver must ping at least one beacon. Once it has that beacon’s time base it can figure out every other beacon in range of that beacon and work out from there. Because clocks on nodes will drift apart over time this ping will need to be repeated every X minutes. Because the last pinged beacon will eventually be out of range, it should also be repeated whenever the receiver moves more than Y distance. This ping need not contain any identifying information about the receiver, so it shouldn’t have privacy implications, but it will reduce the scalability of the system from receiver_count = infinite to receiver_count = bandwidth / (ping_size * ping_frequency). As long as the pings are relatively small and infrequent that should not be an issue. Multiple receivers attached to the same clock (i.e. multiple receivers carried by the same person) could also share time base information and would not need separate pings.

What do you think? Will it work? Are predictable transmit and receive lag even realistic?

~Joe


No Responses Yet to “Figuring out a common time base”

Leave a Reply