Overview and Protocol
Overview
One of the primary challenges for wireless sensor network (WSN) applications is energy management. An accepted solution that dramatically increases sensor lifetime is duty-cycling, i.e., periodically switching on and off communication and/or sensing capabilities. The major factors that affect lifetime are the length of the period (the epoch period) and the duration of the on-time (the awake interval). However, another variable critically affects the performance of the network, namely when in each period each node activates. We refer to this as the wake-up time of the sensor node. In most systems, the wake-up time is randomly established, relating only to when the sensor is initially activated.
This work illustrates an approach to modify, in a decentralized fashion, the wake-up time Wi of the nodes in a WSN so that they are scattered as much as possible. We maintain that such wake-up scattering improves application performance in many situations.
Application Scenarios
1 - Responsiveness to Local Queries
In our first scenario, a set of sensor nodes is distributed throughout a region and a mobile base station is querying for sensor data close to it. The goals in this environment are two-fold. First, we wish to minimize the time that a base station needs to wait to receive data. In other words, the goal is to have at least one node near the base station awake or about to wake up, ready to respond to queries. Second, we wish to minimize the maximum number of nodes that are awake at the same time, therefore reducing the possibility of collisions among query responses issued simultaneously by awake nodes.Rather than trying to adapt to the possibly rapidly moving base station, our approach yields a wake-up scattering solution that suffices for any location of the base station. We accomplish this by considering the wake up times among nearby nodes, motivated by the fact that such nodes are likely to be in contact with the base station at the same time, while those farther away will not. Therefore, in this case the problem can be defined as the search for a confiuration of wake-up times for all sensors that maximizes the minimum difference in wake-up times for any pair of nearby nodes. Put another way, our goal is that any pair of nearby motes should have their wake-up times as far away from each other as possible.
2 - Event Coverage
Another popular use for sensor networks is detection of an event occurring somewhere in the field covered by the sensors. In this scenario, the critical parameters are the sensing range of the devices and the amount of time that the sensors are active. To detect an event, it must occur both spatially inside the sensing range of a node and temporally during the awake time of the node.
Our goal in this scenario is to maximize the percentage of events detected. By treating sensing similarly to communication, we can reuse the previous wake-up scattering technique to exchange among connected neighbors the wake-up times of their sensing devices, thus guaranteeing that the intervals of data acquisition are spread as evenly as possible throughout the epoch, and therefore improving event detection.
3 - Data Latency in Tree-Based Networks
The third scenario we consider is the construction of a tree to funnel data from the edges of the network to a centralized base station, a common approach for applications such as TinyDB. When considering nodes that duty-cycle their communication capabilities, we want to guarantee that when a child has data to send, either its parent in the tree is immediately active or it will be soon, thus minimizing the latency of a data packet on the path to the sink.
If we ignore message propagation delays, the trivial solution is to force all nodes to turn on their communication at the same time. Note that this solution also introduces a high probability of collision as data is forwarded. However, if sensors are active only at the same time as communication, sensing will also be synchronized and the potential benefits of scattering for event detection described previously will not be achieved.
Therefore, our goal is to maintain good event coverage while simultaneously reducing data latency. To achieve this, we require that all nodes keep track of which of their neighbors can serve as parents towards the sink. We assume this is accomplished by broadcasting a message from the sink, that allows nodes to know their distance from the sink, and to infer that all neighbors with distance less than their own are potential parents.
When a node has a message to propagate to the sink (i.e., data collected from one of its own sensors or a message from one of its children), it must forward this to one of its (potential) parents, determined as above. We assume that the node tracks the wake-up time of its parents, and thus knows which parent will be awake next. If one is currently awake, the packet can be immediately sent; if not, the node must wait until a parent is awake, then forward the message. For energy-saving, it may be reasonable for a node to put itself to sleep before sending the packet, then wake up when the parent is awake.
Intuitively, to minimize latency, the next node to wake-up in the epoch after itself should be a parent node. If, instead, the next node is a sibling or child, then data cannot make quick progress. Therefore, our goal is to introduce into the scattering algorithm the constraint that the next node should be a parent. Clearly this cannot be a strict requirement, because if a single node must serve as the parent for multiple children, only one of them can have it as the "next" in the wake-up order. However, we can enforce the constraint that every node has either a parent or a sibling as the next in the wake-up order.
Algorithm
The algorithm itself is designed to generate low communication overhead and is easily implementable in a real WSN system.
Wake-up scattering proceeds in rounds. When nodes are synchronized, a single calibration round lasts one epoch, after which each node selects its new wake-up time offset inside the epoch.
It is worth noting the calibration rounds need not occur in successive epochs, but can be spread out over time, further limiting the already minimal impact of wake-up scattering on the normal operation of the WSN. Furthermore, after calibration stabilizes, it is meaningful to periodically repeat a calibration round in the event that some sensors are added or removed, implying a topology change.
The processing by each node inside a calibration phase is as follows:
Each node must learn the wake-up times of some of its neighbors. The nodes exchange their wakeup time values at the beginning of the calibration epoch. Each node is only interested in the wake-up times of the neighbor that wakes up immediately before it, prev, and immediately after it, next.
The computation of prev and next must take into account the fact that the scheduling of wake-up times is repeated across epochs.
Based on the collected information, each node selects a new wake-up time near the center of the time interval between prev and next. The motivations for not moving to the precise center are discussed in the paper.
