PinPoint Technology - Technical Description
Derived Parametric Synchronization
The goal of PinPoint is to be able to determine the positions of nodes (devices), which can be fixed or moving, in 3D. This section describes how two PinPoint devices, A and B , in a set of PinPoint protocol enabled devices obtain the distance between them without the requirement for synchronized clocks.
Device A sends a signal to device B. Device A's signal contains a timestamp which is the clock count from Device A's environment. Device B runs its own clock asynchronously from Device A. Device B captures the timestamp received fromDevice A and records the value of the pair.
The process is then reversed, B sends to A, A records. These exchanges are repeated twice. Finally, the units swap information about all sent and received time stamps witheach other so that both sides know the eight timestamp values. After this exchange each unit has enough information, as explained in the rest of the section, to apply the Derived Parametric Synchronization(DPS) algorithm, establish the clock rate (drift) differences and the offset (difference in the start times) of the respective clocks.
After the DPS computation iscompleted , the physical distance between the two units is then known, because of the constant nature of the speed of light (and radio waves). In addition, each node also determines the clock characteristics (drift and offset relative to itself) of the nodes in its neighborhood. In the rest of this section, we give the mathematical formulation of PinPoint.
Mathematical Formulation
What follows is a detailed description ofthe DPS technology
Figure 1. DPS Timestamp Exchange
Notation
As a notational convention, we will always use τ to denote local clock times, and t to denote global clock times. Also, when discussing local clock times, the letter contained in the subscript on the τ will always indicate the clock which records the time, so for example τ a 1 is a time recorded by the local clock at node A . We refer to the clock offset and drift rate of a node as α and β respectively. Throughout, we use time as equivalent of distance , i.e., we represent a distance d by the time it will take light to travel that distance.
The speed of light is approximately 300 million meters per second, so one nanosecond of time is approximately one foot. Keep this number in mind when considering the practical implementations of PinPoint vs the clock rates used in the measurements.
Mathematical Formulation
Without loss of generality, we fix on any two nodes, A and B , in the network, and assume that they are neighbors. We describe the messages that they expect to receive from each other and the processing involved in estimating the location. The same discussion holds for the case of n nodes.Both nodes A and B have local clocks, which may have some drift and offset, and for global time t , their clock readings are respectively
Xa = Xa ( Xa + t ) (1)
Xb = Xb ( Xb + t )
Figure 1 shows the messages exchanged and the timing in a measurement cycle. Now, at time t 1 node A b broadcasts tuple giving its identity and a timestamp, the latter denoted by τ a 1 . That is,
τ a 1 ≡ τ a ( t 1 ) = β a ( α a + t 1 ) (2)
and the tuple broadcast is ( A, τ a 1 ). Node B receives it and records the time of receipt as τ b 1 . If we denote the time distance between A and B as d , then the (global) time at which B should receive the broadcast from A is t 1 + d , so that
τ b 1 = β b ( α b + t 1 + d ) (3)
Since each node is running the same decentralized protocol, B also sends a two-tuple, say at global time t2 . In steps similar to above, B broadcasts the tuple ( B, τ b 2 ), where
τ b 2 ≡ τ b ( t 2 ) = β b ( α b + t 2 ) (4)
and A receives this broadcast at global time t 2 + d , which A believes is time
τ a 2 = β a ( α a + t 2 + d ) (5)
Once this first round of messages has completed, they both send a second round, say with A sending its second message at time t3 , and B sending its message at time t4 . Using notation similar to before, we thus have τ a 3 = β a ( α a + t 3 ) , τ b 3 = β b ( α b + t 3 + d ) , τ b 4 = β b ( α b + t 4 ) , and τ a 4 = β a ( α a + t 4 + d ).
Collecting all eight of these together in one place for reference (we refer to these as “the reference equations”), we have:
| τ a 1 = β a ( α a + t 1 ) | | τ b 1 = β b ( α b + t 1 + d ) | |
| τ a 2 = β a ( α a + t 2 + d ) | | τ b 2 = β b ( α b + t 2 ) | (6) |
| τ a 3 = β a ( α a + t 3 ) | | τ b 3 = β b ( α b + t 3 + d ) | |
| τ a 4 = β a ( α a + t 4 + d ) | | τ b 4 = β b ( α b + t 4 ) |
Now that both rounds of messages are complete, the nodes enter the information exchange portion of the algorithm, with A sending the values τ a 2 and τ a 4 to B , and B sending the values τ b 1 and τ b 3 to A . At this point, both of the nodes know all eight values τ a 1 , τ a 2 , τ a 3 , τ a 4 , τ b 1 , τ b 2 , τ b 3 , and τ b 4 . The nodes use these values to independently compute the ratio β a /β b . To see how this is done, note that
The next series of steps is designed to allow for the calculation of the values β a d and β b d . The reasons for this are twofold. First, both β a and β b are typically close to one, so the quantities β a d and β b d are both good estimates of d . Second, both quantities are valuable for helping synchronize the clocks in the network.
We show here how to determine β b d . The development for β a d is similar. First, consider the quantities Δ 1 and Δ 2 given by
Δ 1 ≡ τ b 1 − τ a 1 = β b ( α b + t 1 + d ) − β a ( α a + t 1 ) (8)
and
Δ 2 ≡ τa2 − τ b 2 = β a ( αa + t 2 + d ) − β b ( αb + t2 ) (9)
Averaging these two quantities gives
Now, from the first and second lines of the reference equations (6), we have
τ a 2 − τ a 1 = βa ( t 2 − t 1 ) + β a d (11)
or equivalently that
Substituting Equation 12 into Equation 10 gives
or equivalently
Note that every quantity on the right side of Equation 14 is computable by every node, as long as they have the eight quantities on the left sides of the reference equations. further that determining βbd gives us βad , since βad = ( βa/ βb ) X ( βbd ), and the nodes know both right hand side quantities.