Time Synchronization in Wireless Sensor Networks - Specifics

Algorithms must scale to large, multihop networks of unreliable, energy-constrained nodes.
Precision requirements vary widely (microseconds to seconds).
Extra hardware for synchronization is generally avoided due to cost and energy penalties.
No fixed upper bounds for packet delivery delay (due to MAC protocols, errors, retransmissions).
Manual configuration of single nodes is not an option.

Protocols Based On Sender/Receiver Synchronization

Lightweight Time Synchronization Protocol (LTS)

Synchronizes sensor network clocks to reference nodes.
Balances energy expenditure and achievable accuracy.
Subdivides synchronization into two blocks:
- Pair-wise synchronization between neighboring nodes.
- Synchronizing all nodes to a common reference.

Pair-wise Synchronization

Node $i$ wants to synchronize with node $j$.
Node $i$ formats a synchronization request packet, timestamped at $t_1$ with $L_i(t_1)$.
Packet is handed to OS/protocol stack, incurring medium access delay.
Node $i$ sends the first bit at $t_2$. Node $j$ receives the last bit at $t_3 = t_2 + \tau + t_p$, where $\tau$ is propagation delay and $t_p$ is packet transmission time.
At $t_4$, packet arrival is signaled to node $j$, timestamped at $t_5$ with $L_j(t_5)$.
Node $j$ formats an answer packet at $t_6$, timestamped with $L_j(t_6)$, and hands it to OS/networking stack.
This packet includes $L_j(t_5)$ and $L_i(t_1)$.

How node $i$ infers its clock correction

Node $i$ wants to estimate the offset $O = \Delta(t_1) := L_j(t_1) - L_i(t_1)$.

Assuming no drift between clocks from $t_1$ to $t_8$, node $i$ estimates $O$ by estimating $\Delta(t_5)$.

$L_j(t_5)$ is generated at some unknown time between $t_1$ and $t_8$.
There is one propagation delay $\tau$ plus packet transmission time $t_p$ between $t_1$ and $t_5$.
There is another time $\tau + t_p$ between $t_5$ and $t_8$ for the response packet. For stationary nodes, propagation delays are assumed equal in both directions.
The time between $t_5$ and $t_6$ is known from $L_i(t_6) - L_j(t_5)$.

The uncertainty about $t_5$ can be reduced to the interval:

$$I = [L_i(t_1) + \tau + t_p, \quad L_i(t_8) - \tau - t_p - (L_j(t_6) - L_j(t_5))]$$

If we assume that times spent in OS/networking stack, interrupt latencies, and medium access delay are the same in both directions, then node $i$ concludes that $j$ generated its timestamp $L_j(t_5)$ at time (from $i$'s point of view):

$$L_j(t_5) = \frac{L_i(t_1) + \tau + t_p + L_i(t_8) - \tau - t_p - (L_j(t_6) - L_j(t_5))}{2}$$

The offset $O$ is then:

$$O = \Delta(t_5) = L_j(t_5) - L_i(t_5) = \frac{L_i(t_8) + L_i(t_1) - L_j(t_6) - L_j(t_5)}{2}$$

Node $i$ can adjust its local clock by adding $O$. This synchronizes node $i$ to $j$'s local time, at the cost of two packets.

Localization and Positioning

Possible Approaches of Finding Position

Three main approaches for determining a node's position:

Using information about a node's neighborhood (Proximity).
Exploiting geometric properties (Triangulation and Trilateration).
Analyzing characteristic properties by comparing with premeasured properties (Scene Analysis).

Anchors

Necessary to provide absolute coordinates.
Nodes that know their own position in the absolute coordinate system.
Can rotate, translate, and scale a re