Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale, highly distributed systems of small, wireless, low-power, unattended sensors and actuators [ADL$^+$98,KKP99,EGHK99]. The vision of many researchers is to create sensor-rich ``smart environments'' through planned or ad-hoc deployment of thousands of sensors, each with a short-range wireless communications channel, and capable of detecting ambient conditions such as temperature, movement, sound, light, or the presence of certain objects.
While this new class of distributed systems has the potential to enable a wide range of applications, it also poses serious design challenges, described more fully by KKP [KKP99] and EGHK [EGHK99]. The sheer number of these devices makes global broadcasting undesirable; wireless nodes' limited communication range relative to the geographic area spanned by the system often makes global broadcasting so inefficient that it is infeasible. As a consequence, many argue that nodes must depend on localized algorithms--making control decisions based solely on interactions with neighbors, without global system knowledge [EGHK99,IGE00].
Another important feature that distinguishes sensor networks from traditional distributed systems is their need for energy efficiency. Many nodes in the emerging sensor systems will be untethered, having only finite energy reserves from a battery. Unlike laptops or other handheld devices that enjoy constant attention and maintenance by humans, the scale of a sensor net's deployment will make replenishment of these reserves impossible. This requirement pervades all aspects of the system's design. For example, nodes must remain off or in a low-power state as often as possible; when on, they must maximize the usefulness of every bit transmitted or received [PK00].
Time synchronization is a critical piece of infrastructure for any distributed system. Distributed, wireless sensor networks make particularly extensive use of synchronized time: for example, to integrate a time-series of proximity detections into a velocity estimate [CEE$^+$01]; to measure the time-of-flight of sound for localizing its source [Gir00]; to distribute a beamforming array [YHR$^+$98]; or to suppress redundant messages by recognizing that they describe duplicate detections of the same event by different sensors [IGE00]. Sensor networks also have many of the same requirements as traditional distributed systems: accurate timestamps are often needed in cryptographic schemes, to coordinate events scheduled in the future, for ordering logged events during system debugging, and so forth.
The broad nature of sensor network applications leads to timing requirements whose scope, lifetime, and maximum error differ from traditional systems. In addition, many nodes in the emerging sensor systems will be untethered and therefore have small energy reserves. All communication--even passive listening--will have a significant effect on those reserves. Time synchronization methods for sensor networks must therefore also be mindful of the time and energy that they consume.
In this paper, we argue that the heterogeneity of requirements across sensor network applications, the need for energy-efficiency and other constraints not found in conventional distributed systems, and even the variety of hardware on which sensor networks will be deployed, make current synchronization schemes inadequate to the task. In sensor networks, existing time synchronization methods will need to be extended and combined in new ways in order to provide service that meets the needs of applications with the minimum possible energy expenditures. The development of these new methods is the core of our proposal.
We will also present our idea for post-facto synchronization, an
extremely low-power method of synchronizing clocks in a local area
when accurate timestamps are needed for specific events. We also
present an experiment that suggests this multi-modal scheme is capable
of achieving a maximum error on the order of 
sec--an order of
magnitude better than either of the two modes of which it is composed.
These results are encouraging, although still preliminary and
performed under idealized laboratory conditions. We believe that our
pilot study lends weight to our methods and that further investigation
is warranted.
We begin our discussion in Section 2, describing a number of metrics that can be used to classify both the types of service provided by synchronization methods and the requirements of applications that use those methods. In Section 3, we justify in more detail the need for synchronized time in sensor networks. Related work is reviewed in Section 4. Section 5 argues why the existing work in the field is insufficient for use in the new sensor network regime, and outlines our proposed contributions. Section 6 describes our post-facto synchronization technique and presents an experiment that characterizes its performance. Our proposed thesis work plan is described in detail in Section 7, and conclusions are drawn in Section 8.