Information Technology Reference
d 1 and d 2 to two nodes which have positioning information.
Draw circles with diameters
d 1 and d 2 around these two nodes.
These circles will intersect in two points,
n and n ¢.
Check mutual visibility between the new node and the third already positioned
node, in order to discount either of these two points.
Position the new node in the remaining of these points.
For the 3-D case, a similar algorithm is used: Spheres are drawn around three
already positioned nodes; these three spheres can intersect in up to two points.
However, if all sensor nodes are physically on the earth's surface, then one of these
points can usually be discounted on the basis that it is either above or beneath the
surface, so the final step can be omitted.
If no nodes have information on their absolute position, the positioning approach
is impossible; however, if physical distances between any two nodes are known
(one way to measure physical distance is through measurement of radio attenuation)
then localization is possible. Localization means establishing an internal coordinate
system, with origin in one of the nodes (which would then have coordinates 0, 0, 0)
and assigning coordinates to all other nodes, using the same system. For an example
localization algorithm, an interested reader is directed to [ 7 ].
In addition to position information, a sensor measurement usually needs to be accom-
panied by exact time in which the measurement had been made. At first glance, this
does not seem to be much of an issue. However, in applications where precision is para-
mount, it is very important to keep clocks on all sensor nodes synchronized, as a devia-
tion of even a few milliseconds could compromise the validity of the measurement.
In traditional local area networks, the solution is to use the clock on the server
and to keep clocks on workstations synchronized to that clock, all the time. This is
made possible through reliable, wired communication with predictable delays (a
workstation measures round-trip time, asks for the time from the central server, and
uses measured RTT to compensate for the delay). However, in sensor networks, this
approach is not suitable, because synchronizing clocks regularly means spending a
lot of energy to relay clock synchronization messages. Furthermore, communication
delays are not so predictable.
To this day, a “perfect” solution for the time synchronization issue in sensor
networks has not been found. Some of the ideas that are used for time synchronization
Explicit synchronization - Clocks are not kept synchronized all the time;
instead, in order to save on the communication overhead, each sensor node
keeps its own timescale, and conversion between different time scales is done
“on demand” (for example, at each hop of data routing).