Cost

In this section we want to examine how the presented location system fits the stringent resource restrictions of future Smart Dust Systems. As explained in Section 3.3, these restrictions especially apply to the receiver side, i.e., the Smart Dust nodes.

The Berkeley Smart Dust prototype has already demonstrated that a photo detector similar to the one we are using for our location system is feasible. What remains to be shown is how the receiver software (i.e., the device driver and the user level program) fit onto a Smart Dust node.

Both the processing overhead and the memory footprint of the device driver are very low, which is very important for Smart Dust. The first is true because the driver is interrupt driven, i.e., it does not do any sensor sampling or polling. Moreover, the interrupt can be used to wake up the processor from a power saving mode. Thus, the system has to be woken up only during the short periods when a beam is hitting the photo detector. The memory footprint is very low because the driver does not have to store arrays of peak detections. Instead, for each sequence of peaks it only keeps ``first peak'' and ``last peak'' time stamps which are updated when a new interrupt occurs. The whole data structure for one lighthouse only takes about 25 bytes.

Similarly, the location computation part of the user level program has a very low memory footprint. It just retrieves the $\alpha$ values from the device driver and executes the approximation program described in Section 4.2. Given the relatively infrequent location updates, speed is not a problem. On computationally very limited platforms like future Smart Dust nodes, it might be necessary to revert to fixed point arithmetic and a hardware implementation of the location computation code in case the provided processing capabilities are too limited. Besides the basic arithmetic operations ($+,-,*,/$) we need support for $\sin \alpha$ and $\sqrt{x}$ in order to solve Equation System 10. Note that $\sin \alpha$ is easy to approximate since the values of $\alpha$ obtained from Equation 1 are small due to $t_\mathrm{beam} \ll t_\mathrm{turn}$. The second order approximation $\sin \alpha \approx \alpha - \alpha^3/6$ has a maximum error of 0.1% for $\vert\alpha\vert \le 33^\circ$. There are also fast approximations for $y = \sqrt{x}$. One possible approach is to first approximate $1/\sqrt{x}$ by iterating $y := y (3-xy^2) / 2$ with an appropriate initial value for $y$. Multiplying the result by $x$ gives an approximation for $\sqrt{x}$.

The requirements on the clock are also quite relaxed. Note that we don't need a real-time clock since we are only interested in the quotient $t_\mathrm{turn}/t_\mathrm{beam}$. A simple counter which ticks at a constant rate would also be sufficient. The resolution of the clock (or counter) just has to be high enough to reliably distinguish the $t_\mathrm{mirror}$ values of different lighthouses. Since the $t_\mathrm{mirror}$ values of our prototype system are 4ms and 5ms, respectively, a clock resolution of 0.5ms would be sufficient.

Please note that dust nodes don't have to be calibrated due to the following two reasons. Firstly, the two beam sightings used to measure $t_\mathrm{beam}$ and $t_\mathrm{turn}$ are identical from a measurement point of view. Any constant hardware and software delays will subtract out. Secondly, only the quotient $t_\mathrm{turn}/t_\mathrm{beam}$ is used for node localization, which is independent of the actual clock frequency.