An Idealistic System

Figure 2: Top and side view of an idealistic lighthouse with a parallel beam of light.

Consider the special lighthouse depicted in Figure 2, which has the property that the emitted beam of light is parallel (i.e., has a constant width) with width $b$ when seen from top. When seen from the side, the angle of beam spread of the parallel beam is large enough so that it can be seen from most points in space.

When this parallel beam passes by an observer, he will see the lighthouse flash for a certain period of time $t_\mathrm{beam}$. Note that $t_\mathrm{beam}$ depends on the observer's distance $d$ from the rotation axis of the lighthouse since the beam is parallel. Assuming the lighthouse takes $t_\mathrm{turn}$ for a complete rotation, we can express the angle $\alpha$, under which the observer sees the beam of light as follows:

$$\alpha = 2 \pi \frac{t_\mathrm{beam}}{t_\mathrm{turn}}$$ (1)

Figure 2 shows two observers (depicted as squares) at distances $d_1$ and $d_2$ and the respective angles $\alpha_1$ and $\alpha_2$. Now we can express $d$ in terms of $\alpha$ and the width $b$ of the beam as follows:

$$d = \frac{b}{2 \sin (\alpha/2)}$$ (2)

By combining Equations 1 and 2 we obtain the following formula for $d$ in terms of $b, t_\mathrm{beam}$, and $t_\mathrm{turn}$:

$$d = \frac{b}{2 \sin (\pi t_\mathrm{beam} / t_\mathrm{turn})}$$ (3)

Note that the distance $d$ obtained this way is the distance of the observer to the lighthouse rotation axis as depicted in the side view in Figure 2. That is, all the points in space with distance $d$ form a cylinder (not a sphere!) with radius $d$ centered at the lighthouse rotation axis.

Based on the above observations, we can build a simple ranging system consisting of a lighthouse and an observer. The observer device contains a photo detector and a clock. When the photo detector first sees the light it records the corresponding point in time $t_1$. When the photo detector no longer sees the light it records $t_2$. When it sees the light again it records $t_3$. With $t_\mathrm{beam} := t_2 - t_1$ and $t_\mathrm{turn} := t_3 - t_1$ the observer can apply Equation 3 in order to calculate its distance $d$ from the lighthouse rotation axis. Note that if $t_\mathrm{turn}$ is constant it has to be measured only once since it does not change with distance. Also note that the necessary hardware resources of the observer device are matched by a Smart Dust node as explained in Section 2.

Figure 3: 3D Localization support device consisting of three mutually perpendicular lighthouses.

This ranging scheme can be used to build a single device, which allows observers to autonomously determine their position relative to it in three dimensional space. This device consist of three lighthouses with mutually perpendicular rotation axes as depicted in Figure 3. Assuming an observer measures the distances $d_x, d_y$, and $d_z$ as indicated above, its location can be determined by computing the intersection point(s) of three cylinders with radius $d_x, d_y, d_z$ centered at the respective lighthouse rotation axes. Note that there are 8 such intersection points in general, one in each of the 8 quadrants of the coordinate system. If we can ensure, however, that all observers are located in a single quadrant (e.g., the main quadrant defined by the points $(h_x,h_y,h_z)$ with $h_x, h_y, h_z \ge 0$), there is a unique intersection point. This intersection point can be obtained by solving the following equation system for $h_x, h_y, h_z$:

$$\begin{array}{rcl} d_x^2 & = & h_y^2 + h_z^2 \\ d_y^2 & = & h_x^2 + h_z^2 \\ d_z^2 & = & h_x^2 + h_y^2 \\ \end{array}$$ (4)

Note that this equation system does not necessarily have a solution, since the values $d_x, d_y, d_z$ are only approximations obtained by measurements. If there is no solution, an approximation for the intersection point can be obtained using minimum mean square error (MMSE) methods. The solution $(h_x,h_y,h_z)$ obtained this way minimizes the sum of the squares of the differences of the left hand and right hand sides of the equations 4. However, if the equation system has a solution, it can be directly solved using the following set of equations, again assuming that the observer is located in the main quadrant of the coordinate system depicted in Figure 3:

$$\begin{array}{rcl} h_x & = & \sqrt{(-d_x^2 + d_y^2 + d_z^2)/... ... \\ h_z & = & \sqrt{(d_x^2 + d_y^2 - d_z^2)/2} \\ \end{array}$$ (5)

The setup of the complete location system can now be described. The base station is equipped with three mutually perpendicular lighthouses as depicted in Figure 3. At startup, the base station broadcasts certain calibration parameters (e.g., the beam width $b$ for each of the lighthouses) to all dust nodes. The latter use a real-time clock to measure the amount of time during which each of the lighthouses beams are visible. Using Equations 3 and 4, nodes can autonomously compute their location in the reference grid defined by the base station's three lighthouses.

The description of the system's principles gives rise to a number of practical questions. First of all, it is not clear at all whether a system fulfilling the above requirements (e.g., parallel beam) can actually be built in practice. Moreover, we did not discuss the problem how a dust node can distinguish the different beams of the lighthouses, or what happens if a dust node ``sees'' the beams of two lighthouses at the same time. We will discuss these issues in the next sections in order to lay the foundation for an implementation of the system.