Time Synchronisation and Localisation

Worked example: how fast a clock goes wrong. A clock that is off by 40 ppm gains or loses 40 microseconds every second. In one minute that is 40 × 60 = 2,400 microseconds, 2.4 ms. To stay within 20 microseconds of a correct clock without estimating the drift, it would need resynchronising every 20 / 40 = 0.5 seconds. Hence TPSN's conclusion that "even if we synchronize the whole network once, nodes will go out of sync in a few minutes", and hence RBS's use of a least-squares line through repeated observations, which recovers the drift (the slope) as well as the offset (the intercept), so a node can correct its clock between synchronisations.

Where the error comes from: four parts of a message's delay

Synchronisation means sending a time in a message, and the message takes an uncertain time to arrive. RBS's authors, after Kopetz and Schwabl, split that delay into four parts:

1. Send time: building the message at the sender, including operating system delays, context switches and handing it to the network interface.
2. Access time: waiting for the channel, which depends on the MAC protocol: waiting for a clear channel, retransmitting after a collision, or waiting for a TDMA slot.
3. Propagation time: travelling from sender to receiver. Between neighbours this is tiny, "simply the physical propagation time of the message through the media".
4. Receive time: the receiver's network interface receiving the message and telling the host.

Send time and access time vary the most, and they are the ones the two families of protocols treat differently. TPSN time-stamps packets "at the moment when they are sent i.e., at MAC layer", which cuts the send time out; RBS removes both, as below.

Sender-receiver synchronisation: the two-way exchange

Figure 34.1 The two-way exchange: T1 and T4 on A's clock, T2 and T3 on B's

Node A sends a message at time T1, by its own clock. Node B receives it at T2 and replies at T3, both by B's clock, putting T1, T2 and T3 in the reply. A receives the reply at T4, by its own clock. From these four timestamps, RFC 5905, the Network Time Protocol's specification, computes the offset of B relative to A:

and the round-trip delay:

TPSN uses the same exchange and the same arithmetic in its equation 1, writing the offset as ((T2 - T1) - (T4 - T3)) / 2 and calling it the clock drift, and the one-way propagation delay as half the round trip. The one assumption is that the delay is the same in both directions.

Worked example. B's clock is actually 6.2 ms ahead of A's, and a message takes 1.1 ms each way. A sends at T1 = 1,000.0 ms. B receives it at T2 = 1,000.0 + 1.1 + 6.2 = 1,007.3 ms on its clock, and replies 2 ms later at T3 = 1,009.3 ms. A receives the reply at T4 = 1,009.3 - 6.2 + 1.1 = 1,004.2 ms on its clock. Then:

• offset = ((1,007.3 - 1,000.0) + (1,009.3 - 1,004.2)) / 2 = (7.3 + 5.1) / 2 = 6.2 ms, exactly the true offset;
• round-trip delay = (1,004.2 - 1,000.0) - (1,009.3 - 1,007.3) = 4.2 - 2.0 = 2.2 ms, the two 1.1 ms trips.

When the delays are not equal. Suppose the message takes 1.5 ms going and 0.7 ms returning, the same 2.2 ms round trip. Then T2 = 1,000.0 + 1.5 + 6.2 = 1,007.7 and T4 = 1,009.3 - 6.2 + 0.7 = 1,003.8, and the formula gives (7.7 + 5.5) / 2 = 6.6 ms: wrong by 0.4 ms, which is half the difference between the two delays, (1.5 - 0.7) / 2 = 0.4. The exchange cannot see asymmetry; the variable send and access times are exactly what make the two directions differ.

TPSN: levels first, then pairs

TPSN synchronises a whole network to one root node in two phases.

1. Level discovery. "The root node is assigned a level 0 and it initiates this phase by broadcasting a level_discovery packet." Each neighbour assigns itself level 1 and broadcasts in turn; each node takes a level one greater than the first it hears and ignores later ones, so every node ends with a level. It is the hop-count beacon of [The Characteristics and Challenges of Ad Hoc Networks in a WSN], used to build a tree.
2. Synchronisation. "Pair wise synchronization is performed along the edges of the hierarchical structure": each level 1 node runs the two-way exchange with the root and corrects its clock; level 2 nodes then synchronise with level 1 nodes, and so on down. The nodes wait a random time before starting, to avoid contention.

On Berkeley motes TPSN synchronised a pair of neighbours "to an average accuracy of less than 20µs", and its authors argue it "roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS)", which they implemented on the same motes for comparison.

RBS: synchronising the receivers with each other

RBS takes a different route. A node broadcasts a reference beacon, which "does not contain an explicit timestamp; instead, receivers use its arrival time as a point of reference for comparing their clocks". Receivers then exchange the times at which they heard it, and each learns its offset from the others.

Why this helps. "Although the Send Time and Access Time may be unknown, and highly variable from message to message, the nature of a broadcast dictates that for a particular message, these quantities are the same for all receivers." A broadcast is only used "to synchronize a set of receivers with one another", never sender with receiver, so the sender's two most variable delays drop out of the error altogether. What remains is the difference in propagation time between the receivers, which is negligible over tens of metres, and the difference in their receive times.

How well it did. On off-the-shelf 802.11 hardware, RBS achieved "1.85 ± 1.28µsec", and across four hops "3.68 ± 2.57µsec", a significant improvement over NTP under similar conditions. The authors also note that the broadcast "does not even need to be a dedicated timesync packet": any broadcast the network already sends, such as a route discovery packet, can serve.

Worked example: synchronisation for localisation

Ultrasonic ranging measures how long sound takes to cross from one node to another. TPSN's authors turn a timing error into a distance error with sound at 345 m/s: at their average accuracy of 20 microseconds, 345 × 0.00002 = 0.0069 m, that is 0.69 cm. At a millisecond of error, 345 × 0.001 = 0.345 m, about 35 cm. That is how closely localisation and synchronisation are tied.

Part 2: Localisation

Why nodes must find their own positions

A reading is only useful with a place attached, geographic routing needs positions ([Geographic Routing: Greedy Forwarding and GPSR]), and coverage cannot be judged without them. GPS solves the problem outdoors for larger devices, but Dargie and Poellabauer note that the "need for small form factor and low energy consumption also prohibits the integration of many desirable components, such as GPS receivers". So a few nodes, called anchors (also beacons, reference points or landmarks), know their positions, from GPS or because they were placed by hand, and every other node works out its own from them.

The methods fall into two families. Bulusu and colleagues call them fine-grained, inferring "the distance to a reference point based on signal strength or timing measurements", and coarse-grained, inferring only "proximity to a given reference point". The survey by Mesmoudi and colleagues uses the names common today: range-based and range-free.

Range-based: four ways to measure

1. RSSI (received signal strength). The stronger the signal, the nearer the sender: a propagation model converts strength into distance. It is "the most common techniques, cheapest and simplest", since it needs no extra hardware, but it is "very susceptible to noise and obstacles".
2. Time of arrival (TOA), or time of flight: distance is travel time multiplied by the signal's speed. It needs the sender and receiver synchronised, which "adds cost and complexity".
3. Time difference of arrival (TDOA). In one form, a node sends a radio signal and an ultrasound signal together; the radio arrives almost at once, the sound much later, and the difference gives the distance: speed of sound times (sound's travel time minus radio's travel time). It needs extra hardware, and "the ultrasound signal can be stopped by obstacles". In another form, differences in arrival time at pairs of anchors place the node on hyperbolas whose intersection is its position.
4. Angle of arrival (AOA): the direction a signal comes from, measured with an antenna array or several receivers. Accurate, but needs extra hardware and suffers from multipath.

Worked example: why RSSI ranging is rough. In the log-normal shadowing model, the received signal at a given distance varies around its average by a random amount with standard deviation σ dB, and it falls by 10n dB for every tenfold increase in distance. So a reading σ dB too strong makes the distance look shorter by a factor of 10 raised to σ / (10n). With the values Zuniga and Krishnamachari used, σ = 4 dB and n = 4, that factor is 10 to the power 0.1, about 1.26: one typical shadowing error puts a node about 26 per cent too far or about 21 per cent too near. An error of that size in every range is what the trilateration below has to absorb.

Trilateration

Figure 34.2 Trilateration: the node lies where the circles of its distances from the anchors meet

A node that knows its distance d1 from an anchor at (x1, y1) lies on a circle around it. Two circles meet in two points; a third anchor picks one. With more anchors, and with measured distances that are never exact, the circles do not meet in one point, and the position is found by least squares: the point that fits all the circles best. The standard trick is algebraic. Each circle's equation is

and subtracting the last anchor's equation from each of the others cancels the x² and y² terms, leaving equations that are linear in x and y. Those are solved by ordinary least squares. The program below does exactly that. Using more than three anchors is multilateration; the arithmetic is the same.

Range-free: centroid and DV-Hop

Centroid. Bulusu and colleagues place reference points on a grid, each broadcasting beacons periodically. A node listens for a while and computes, for each reference point, a connectivity metric: the percentage of its beacons it received. It treats the reference points whose metric exceeds a threshold ("say 90%") as nearby, and places itself at their centroid, the average of their coordinates. Their measurements found "the accuracy for 90% of our data points is within one-third of the separation distance" between reference points.

Worked example. Four reference points stand at (0, 0), (10, 0), (0, 10) and (10, 10), 10 m apart, with a reliable range of 12 m.

• A node at (3, 4) is 5 m, about 8.1 m, about 6.7 m and about 9.2 m from them, so it hears all four and places itself at their centroid, (5, 5). Its error is the distance from (3, 4) to (5, 5), 2 m across and 1 m up, the square root of 5, about 2.24 m.
• A node at (1, 1) is about 12.7 m from (10, 10), out of range, so it hears three. Their centroid is ((0 + 10 + 0) / 3, (0 + 0 + 10) / 3), about (3.33, 3.33), and its error is about 3.30 m, a third of the separation.

The centroid method needs no measurement at all, only counting beacons, and its accuracy is set by how closely the reference points are spaced.

DV-Hop. Niculescu and Nath's DV-Hop works over many hops, where most nodes hear no anchor directly. The survey describes it in three steps:

1. Hop counts. By a distance-vector exchange, "all nodes in the network get minimal hop-count to every anchor nodes".
2. Hop size. Each anchor, knowing the true distances to the other anchors and the hop counts to them, computes an average distance per hop: the sum of those distances divided by the sum of those hop counts. It sends this hop size to the nodes around it.
3. Position. An unknown node multiplies its hop count to each anchor by the hop size, giving an estimated distance to each, and with three or more of these it uses trilateration.

It is simple and "does not depend on range measurement error", but a hop is only an average distance: a straight chain of nodes and a crooked one with the same hop count get the same estimate.

Localisation, computed

The program first trilaterates one node from four corner anchors, with exact and then with slightly wrong distances. It then scatters 100 nodes over a 100 m square with a radio range of 18 m, makes the first 10 of them anchors, and runs DV-Hop's three steps for the other 90.

# Locating nodes from anchors: trilateration from measured distances, and
# DV-Hop (Niculescu and Nath) when a node can only count hops.
import math
import random
from collections import deque

def trilaterate(anchors, dists):
    """Least squares. Subtracting the last circle's equation from each of
    the others leaves equations that are linear in x and y."""
    (xn, yn), dn = anchors[-1], dists[-1]
    rows = [(2 * (xn - xi), 2 * (yn - yi),
             di**2 - dn**2 - xi**2 + xn**2 - yi**2 + yn**2)
            for (xi, yi), di in zip(anchors[:-1], dists[:-1])]
    saa = sum(a * a for a, b, c in rows)
    sab = sum(a * b for a, b, c in rows)
    sbb = sum(b * b for a, b, c in rows)
    sac = sum(a * c for a, b, c in rows)
    sbc = sum(b * c for a, b, c in rows)
    det = saa * sbb - sab * sab
    return (sac * sbb - sbc * sab) / det, (saa * sbc - sab * sac) / det

# 1. Trilateration: a node at (30, 40) and four anchors at the corners.
corners = [(0, 0), (100, 0), (0, 100), (100, 100)]
true = (30, 40)
exact = [math.dist(true, a) for a in corners]
print("exact distances   -> (%.2f, %.2f)" % trilaterate(corners, exact))
errors = [1.05, 0.92, 1.10, 0.97]          # measured 5% long, 8% short, ...
noisy = [d * e for d, e in zip(exact, errors)]
x, y = trilaterate(corners, noisy)
print("distances 3-10%% off -> (%.2f, %.2f), %.2f m from the truth"
      % (x, y, math.dist((x, y), true)))

# 2. DV-Hop: 100 nodes scattered over 100 m x 100 m, radio range 18 m;
#    the first 10 know their positions (the anchors).
rnd = random.Random(5)
pos = [(rnd.uniform(0, 100), rnd.uniform(0, 100)) for _ in range(100)]
RANGE, ANCHORS = 18.0, range(10)
nbrs = [[j for j in range(100) if j != i and math.dist(pos[i], pos[j]) <= RANGE]
        for i in range(100)]

def hops_from(src):                        # step 1: flood hop counts
    h, todo = {src: 0}, deque([src])
    while todo:
        n = todo.popleft()
        for m in nbrs[n]:
            if m not in h:
                h[m] = h[n] + 1
                todo.append(m)
    return h

hops = {a: hops_from(a) for a in ANCHORS}
hop_size = {}                              # step 2: metres per hop, per anchor
for a in ANCHORS:
    others = [b for b in ANCHORS if b != a and b in hops[a]]
    hop_size[a] = (sum(math.dist(pos[a], pos[b]) for b in others)
                   / sum(hops[a][b] for b in others))
errs = []
for n in range(10, 100):                   # step 3: estimate, then trilaterate
    known = [a for a in ANCHORS if n in hops[a]]
    if len(known) < 3:
        continue
    nearest = min(known, key=lambda a: hops[a][n])
    est = [hop_size[nearest] * hops[a][n] for a in known]
    guess = trilaterate([pos[a] for a in known], est)
    errs.append(math.dist(guess, pos[n]))
print("DV-Hop: hop sizes %.1f to %.1f m; %d of 90 nodes located"
      % (min(hop_size.values()), max(hop_size.values()), len(errs)))
print("        mean error %.1f m, that is %.2f of the radio range; worst %.1f m"
      % (sum(errs) / len(errs), sum(errs) / len(errs) / RANGE, max(errs)))

exact distances   -> (30.00, 40.00)
distances 3-10% off -> (36.92, 37.20), 7.46 m from the truth
DV-Hop: hop sizes 9.3 to 12.5 m; 90 of 90 nodes located
        mean error 14.2 m, that is 0.79 of the radio range; worst 47.2 m

Reading it. With exact distances, least squares returns the node's true position. With distances only 3 to 10 per cent wrong, the position moves by 7.46 m: ranging errors grow into position errors, which is why RSSI's rough ranges limit it. DV-Hop needs no ranging hardware at all and still places every one of the 90 nodes, but with a mean error of 14.2 m, 0.79 of the radio range, and a worst case of 47.2 m. The hop sizes, 9.3 to 12.5 m, are only about a half to two thirds of the 18 m range, because a hop in a random network rarely covers the full range, and a node whose shortest paths bend around a gap gets hop counts that overstate its distances. Better anchor placement, more anchors, or ranging where it is affordable all reduce the error; that trade between accuracy and cost is the whole subject of localisation.

Distinctions

What it does not mean

Synchronised does not mean correct. A network synchronised to its root agrees with itself; it need not agree with the real time unless the root does.

One synchronisation is not enough. Clocks drift apart again at up to tens of microseconds per second, so synchronisation is repeated, or the drift is estimated and corrected.

RBS does not need a special packet. Any broadcast that several receivers hear can be used as the reference.

Range-free is not error-free. It avoids measurement error by not measuring, and pays in resolution: a hop or a beacon's range is a coarse unit of distance.

More anchors are not free. Each anchor needs GPS or a manual survey; localisation methods are judged by how few anchors they need for a given accuracy.

Quick revision

• Synchronisation is needed for data fusion, coordinated actuation, duty cycling (RBS), time-stamped cooperation (TPSN), and ranging.
• Offset and skew; crystals accurate to 1 part in 10 thousand to 1 part in a million, 1 to 100 microseconds per second; motes up to 40 ppm.
• Delay components (Kopetz and Schwabl, via RBS): send, access, propagation, receive.
• Two-way exchange (RFC 5905): offset = ((T2 - T1) + (T3 - T4)) / 2, delay = (T4 - T1) - (T3 - T2); assumes symmetric delay; asymmetry errs by half the difference.
• TPSN: level discovery from a root, then pairwise synchronisation down the levels; MAC-layer time-stamps; under 20 microseconds; about 2x better than RBS.
• RBS: a reference broadcast with no timestamp; receivers compare arrival times; removes send and access time; 1.85 ± 1.28 microseconds on 802.11; regression estimates skew.
• Ranging error = speed of sound × timing error: 345 m/s × 20 microseconds = 0.69 cm.
• Localisation: anchors; range-based (RSSI, TOA, TDOA, AOA) and range-free (centroid, DV-Hop).
• Trilateration: circles of measured distance; least squares after subtracting one equation; multilateration with more anchors.
• Centroid: connectivity metric above 90 per cent; average of heard reference points; 90 per cent of estimates within one third of the spacing.
• DV-Hop: hop counts to anchors; hop size = sum of anchor distances / sum of hops; distance = hop size × hops; trilaterate.

Test yourself

1. Why is time synchronisation needed in sensor networks? Explain the sources of error. Readings from different nodes must be combined in time order, duty-cycled and TDMA schedules need neighbours to agree when to wake, actions must be coordinated, and ranging by time of flight needs microsecond agreement. Clocks start with different offsets and run at slightly different rates. A synchronisation message's delay has four parts: send time at the sender, access time waiting for the channel, propagation time, and receive time at the receiver; the variation in these, especially send and access time, becomes synchronisation error.

2. Explain the two-way message exchange and derive the offset. A sends at T1 by its clock; B receives at T2 and replies at T3 by its clock; A receives at T4. If the offset of B is theta and the one-way delay d is the same both ways, T2 = T1 + d + theta and T4 = T3 + d - theta. Subtracting, (T2 - T1) - (T4 - T3) = 2 theta, so theta = ((T2 - T1) + (T3 - T4)) / 2, and the round-trip delay is (T4 - T1) - (T3 - T2).

3. Explain TPSN. The Timing-sync Protocol for Sensor Networks works in two phases. In level discovery, the root takes level 0 and broadcasts; each node takes a level one greater than the first level it hears and rebroadcasts, building a hierarchy. In the synchronisation phase, each node performs a two-way exchange with a node one level above and corrects its clock, level by level from the root down. It time-stamps messages at the MAC layer, and achieved under 20 microseconds between neighbouring motes.

4. Compare RBS with sender-receiver synchronisation. In RBS a node broadcasts a beacon with no timestamp, and the receivers compare the times at which they received it, synchronising with each other. Because the broadcast leaves the sender once, its send time and access time are the same for all receivers and drop out of the error, leaving only differences in propagation and receive time. Sender-receiver protocols synchronise a receiver to a sender with a two-way exchange and must live with the sender's variable delays, unless, like TPSN, they time-stamp at the MAC layer.

5. Explain range-based and range-free localisation with one example of each. Range-based methods measure the distance or angle to anchors, using received signal strength, time of arrival, time difference of arrival or angle of arrival, and compute the position by trilateration. Range-free methods use only connectivity: in the centroid method a node places itself at the average position of the anchors it hears reliably; in DV-Hop a node counts hops to each anchor, converts hops to distances with an average hop size computed by the anchors, and trilaterates.

6. A node hears reference points at (0, 0), (10, 0) and (0, 10) but not the one at (10, 10). Where does the centroid method place it? At the average of the three: ((0 + 10 + 0) / 3, (0 + 0 + 10) / 3), about (3.33, 3.33).