## 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!”
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)