While many aspects of deployed sensor networks will be specific to particular applications, we have begun to identify key building blocks that will enable a wide range of applications. This section discusses a ``Frisbee'' model for low-duty-cycle operation and techniques for time synchronization.
One of the most important design goals of sensor network applications is minimizing the power used. Energy is a precious resource in sensor networks because there is a finite amount available; every use of it directly affects the lifetime of the network [Kaiser-Pottie00]. This makes energy-efficiency critical.
![\includegraphics[scale=0.4]{frisbee-diagram.eps}](img1.png)
|
In networks where ``interesting'' events happen infrequently, an effective way of saving power is to turn nodes off when they are not needed. In an ideal but unattainable world, a sensor network is completely asleep during the long lulls in activity. When something does happen, only a limited zone of the network that is close to the event is kept in its fully active state. The active zone should be centered at the current location of a target phenomenon that is being tracked; and, of course, the zone should move through the network along with the target. Nodes that are not within sensing range of the event are outside of the zone, and therefore do not waste energy on data acquisition or housekeeping tasks such as maintaining time synchronization. Optimally, the zone should move such that a phenomenon of interest is always kept inside of the zone. The zone might be circular, with its radius proportional to the speed of the object. We call this model of a constantly moving circular zone the ``Frisbee'' model.
To implement an approximation of the optimal Frisbee, two essential components required: (1) A low-power operating mode with wakeup: some sensors must always be vigilant; others must have a way of saving power such that they can be awakened by an external stimulus; and (2) Definition of the Frisbee boundary: sensors must use localized algorithms so that nodes can autonomously decide whether or not they are part of the Frisbee; i.e., entering or leaving it.
At the core of our idea is the fact that sensor nodes can be designed with a ``power-saving'' mode in which they are asleep. This sleep mode must require less power than a mode in which nodes are maintaining active vigilance. This mode is distinguished from simply being off because it must be possible for an external stimulus to ``wake up'' the nodes, bringing them from their low-power mode into a vigilant mode. The nodes should be able to generate this stimulus so that they can awaken their peers.
Most nodes should be asleep most of the time. Some nodes will remain awake all the time to serve as ``sentries'' - performing tasks such as accepting tasking instructions from users and looking for a potential event of interest. When a sentry senses a nearby event, it wakes up nodes in its vicinity, allowing the group to acquire data with finer granularity or a wider range of modalities than would be possible with a single (sentry) sensor. As the target moves, nodes will send further wakeup signals to other nodes in the target's direction of motion. We envision a ``wakeup wavefront'' that precedes the phenomenon being tracked. As the target moves beyond the useful range of sensor nodes, those nodes go back to sleep.
An interesting observation is that by increasing the density of nodes we may be able to guarantee that enough nodes will be listening soon enough to achieve low latency wakeup, even with relatively low duty cycle wakeup at the level of individual nodes. On detection we might wake up every node that comes on cycle, so that over the course of an entire cycle, gradually all the nodes in the vicinity would be wakened. In a sense we are exploiting parallelism, by using larger numbers of low duty cycle (low power) nodes, instead of smaller numbers of higher power nodes.
A central theme pervading the design of all sensor networks is a fully distributed, decentralized design. This naturally extends to the algorithms that we plan to develop for defining the Frisbee boundary. That is to say, each node will autonomously decide whether or not it is ``in the Frisbee'' - there is no central controller that doles out instructions to nodes.
One example of a simple distributed algorithm for this is as follows. Nodes that have recently detected the target wake up all other nodes within a fixed radius. If possible, neighboring nodes that are already awake should be queried so that the target's speed and direction can be determined, in order to better shape and direct the ``wakeup wavefront.'' After a certain amount of time without any detected activity, the nodes time out and return to their previous sleep state.
The design of this algorithm will also incorporate the idea of adaptive fidelity. In motion tracking, ever-denser distributions of sensors will usually lead to increasingly precise tracking results. However, if a particular application considers network lifetime to be more important than tracking precision, it is possible to adjust this by only waking up, say, one-half or one-quarter of the nodes that fall physically within the Frisbee. Another potential variation is that sensors closer to the center of the Frisbee are awakened with a higher density than nodes near the edges.
With a framework such as the above in place, each application will be able to tune its desired precision and commensurate energy expenditure. Applications can define what percentage of the sensor nodes within a Frisbee should be awakened every time the Frisbee moves into a new region. The decision of which exact nodes should actually be awakened is, again, a decentralized decision, likely to be made through randomization or some other technique.
Time synchronization is a building block critical to many aspects of a distributed sensor system. For example, it is critical to a common sensor network feature: data aggregation. Due to the high energy cost of communication compared to computation [Kaiser-Pottie00], local processing, summarization, and aggregation of data is often employed in order to minimize the size and frequency of transmissions. Suppression of duplicate notifications of the same event from a group of nearby sensors can result in significant energy savings [Intanago00]. To recognize duplicates, events must be timestamped with a precision on the same order as the event frequency. Correct time synchronization can also lead to energy savings in systems that use TDMA or other types of scheduled wake-ups; the size of the guard bands used to ensure rendezvous in the face of clock skew is inversely proportional to the synchronization precision.
For an application such as ours, which involves the detection of the speed and direction of phenomena such as tagged animals, time synchronization is critical -- a set of distributed sensors must share a common time coordinate in order to integrate a series of proximity detections into a determination of speed and direction. Important variables that will vary with the application are the required precision of the time synchronization, and (closely related) the required frequency with which the sensors must be able to determine a ``fix'' on the tracked object. Both of these are informed by the expected nominal speed of tracked objects. Another factor affecting these parameters is the geographic density of sensors relative to both the tracked object's speed and the effective range of the sensors.
Maintaining synchronized time energy-efficiently among a large cluster of nodes that may often be off is a challenge not undertaken by conventional wired networks. The needs of a time coordinate and constraints on a synchronization system in a distributed sensor network vary along numerous axes: precision, scope, lifetime, cost, form factor, and so on. A variety of methods methods for establishing time synchronization are available across these same axes.
The simplest is the distinction between global and local time. A global timebase is one that is shared by every node in the network, or that exists completely independent of the sensor network. By some metrics, these are the best solutions because they eliminate accumulated error that invariably comes from distributing time hop-by-hop within a network. A single time signal broadcast to all nodes can go a long way towards reducing time-sync error. Existing time distribution infrastructures such as the WWVB time signal or GPS-time may be used for this purpose. We are investigating the use of various low-power devices that receive these time signals and can be integrated with our sensor node hardware.
While the idea of using universal time is attractive, it also does have a number of drawbacks. The hardware required to receive special time signals consumes energy and physical space, both of which are quite limited in tags. Adding a new piece of specialized hardware will always be more resource-intensive than a solution that uses existing communication capabilities of a sensor node. Moreover, universal time by definition depends on an existing time distribution infrastructure, which is often unavailable. WWVB works only in the continental US; no infrastructure is available underwater, inside of many structures, or on Mars.
For these reasons, it is also wise to consider a peer-to-peer time distribution strategy. One example is that employed by NTP, the Network Time Protocol [Mills96]. NTP can be used to establish a federation of synchronized nodes, even if the federation has no external time source. An NTP-like algorithm operates over the existing communications infrastructure of nodes; peers repeatedly poll each other for their current time in an effort to establish their relative bias and skew. Of course, if some NTP nodes have access to an external time source, a hybrid distribution algorithm is possible.