Dynamic Sleep Scheduling in Rechargeable

Sensor Networks

Neeraj Jaggi, Koushik Kar and Ananth Krishnamurthy

Rensselaer Polytechnic Institute

{jaggin,kark,krisha}@rpi.edu

1.Introduction and Motivation

Wireless sensor networks are deployed for detecting “interesting” phenomena in a wide range of environments, including oceans, forests, urban areasand military-surveillance. Since sensor nodes are often heavily constrained in terms of battery energy, efficient energy management is crucial to the successful operation of such networks. The low-cost and failure-prone nature of these nodes, together with practical difficulties in accurate sensor placement, may often lead to random and redundant deployment of such nodes in the region of interest. Most sensor network applications involve monitoring a geographically vast area over an extended period of time. Since the deployment region is vast, and often inaccessible, periodic replacement of sensor batteries may not be a viable solution. A more feasible and cost-effective solution is to equip the sensors with rechargeable batteries [1], which can significantly enhance the operational lifetime of the sensor by scavenging energy from natural sources like sunlight, wind, water etc. The process of recharging, in general, would be a slow process, possibly dependent on random environmental factors like the intensity of sunlight, wind speed etc. Typically, the rate of recharging would be significantly less than the energy discharge rate during the activation (sensing and transmission) period. As a result, a sensor would need to spend most of its lifetime in theoff state, when it is not sensing, but only recharging. The recharge processes across different sensors in close vicinity can be correlated, sincethe recharging process (like the intensity of sunlight) is expected to exhibit a significant degree of spatial correlations. In addition, the events of interest, which the sensors would like to detect, may be correlated in space as well. That is, events of interest may occur simultaneously in aportion of the deployment area and would be detected by multiple, closely-located activesensors covering that area.

A discussion on the importance of energy management in ad-hoc and sensors networks, along with a description of various performance objectives, is outlined in [2]. For efficient operation of such energy-constrained sensor networks, individual sensor nodes must be “put to sleep” (or deactivated) or “woken up” (or activated) appropriately. The tiny, low-cost nature of the sensor devices and minimal processing capabilities creates the need to develop simple, efficient and distributed algorithms to implement these decisions.

2.Dynamic Sleep Scheduling Problem

The dynamic node activation or dynamic sleep scheduling problem involves determining when each sensor should be involved in data gathering (activation) and when each of them should be put on the “standby” mode (deactivation), so as to maximize the long-term reliability index of the system [4]. Since the sensors are heavily energy-constrained, activating a sensor whenever possible may not be a good strategy. The key to obtaining efficient policies is to activate some sensors currently, while keeping a sufficient number of sensors in store for future use.

Note that the presence of spatial correlations in the discharge and/or recharge processes make the development of an efficient sleep scheduling policy considerably more difficult. These correlations could significantly affect system performance, and therefore,activation strategies developed must be robust to the presence of such correlations.

2.1.Rechargeable Sensor Systems

Sensor systems can be distinguished in terms of activation (and deactivation) constraints on sensors. Two different system models are considered here, namely, the Full Activation(FA) system model[3, 4] and the Partial Activation (PA) system model [5, 6]. In FA system model, sensor nodes involved in sensing get discharged after a certain duration of time, and need to be recharged fully till they can start sensing again. Whereas, in PA system model, a sensor is modeled as a energy bucket of  quanta, and is available for activation as long as it has non-zero energy. In PA system model, a sensor can activate (deactivate) itself even when it is not fully recharged (discharged), unlike in FA model.

The state transition diagram for a rechargeable sensor under FA system model is shown in Figure 1. In a realistic sensing environment, the discharge and recharge times of a sensor could depend on various random factors. Therefore, the discharge time and recharge time of each sensor under the FA model is modeled as exponentially distributed with means and respectively. Let, since the discharge rate typically exceeds the recharge rate. Spatial correlation among the sensors' recharge and discharge times is modeled by considering two different correlation models, namely the Independent Lifetime (IL) and the Correlated Lifetime (CL) correlation models.In the IL model, the discharge and recharge times of all sensors are independent, whereas in the CL model, the discharge times of all sensors entering the active state at the same time are the same. Similarly, the recharge times of all sensors entering the passive state at the same time are the same. The discharge (recharge) times of sensors entering the active (passive) state at different times are independent of each other.

In PA system model, a sensor is modeled as a finite-buffer quantum-queue with a buffer capacity of , as shown in Figure 2. Note that the queue is discharged of quanta only when the sensor is activated. The quanta arrival or recharge process at each sensor is modeled as Poisson with rate λ, and thedischarge time of each quantum is exponentially distributed with mean . Let , since average discharge rate is typically more than the average recharge rate.Spatial correlation across thesensors' recharge and discharge processes leads totwo different correlation models, namely the Independent Discharge Recharge (IDR) and the Correlated Discharge Recharge (CDR) correlation model. In IDR model, the discharge as well as the recharge processes at different sensors are independent, whereas in CDR model, the discharge as well as the recharge processes at different sensors are completely correlated, i.e., recharge quanta arrive at the same time at all the sensors and get consumed, one by one, at the same time from all active sensors.

2.2.Performance Criteria

Consider a system of rechargeable sensors deployed redundantly in the region of interest for monitoring and data gathering purposes. Ifa large number of sensors are deployed, itis likely that more sensors would remain charged (and hence can be used for sensing) at any given time. Thus, the overallsystem performancewould typically improve (possibly with diminishing returns) with a more redundant deployment of sensors. The performance of the rechargeable sensor system can be characterized by a continuous, non-decreasing, strictly concave function Usatisfying U(0) = 0. More specifically, U(n)represents the “utility” derived per unit area, per unit time, from n active sensors covering an area. As an example of a practical utility function, consider the scenario where each sensor can detect an event with probability p. If the utility is defined as the probability that the sensing system is able to detect an event, then , where nis the number of sensors that are active. Figure 3 depicts the shape of this utility function for various values of detection probability p. The long-term system performance is represented by the time-average utility of the system.Let  denote the entire area in the physical space of interest. Let nΠ(t) denote the number of active sensors that cover area element at time t, under activation policy Π. Then the time-average utility under policy Π, is given by. The decision problem is that of finding the sleep schedule orpolicy Π*, such that the time-average utility achieved is maximized.

3.Threshold based Sleep Scheduling

Although under specific cases, the optimal sleep scheduling question can be formulated using the Markov decision process framework, determining optimal policies can becomputationally prohibitive and would require global knowledge and coordination.In practicalscenarios, however, a sensor would be requiredto take activation decisions in a distributed manner,based only on local topologyand state information. This motivates us to study a class of simple threshold policies, which can easily be implemented in a distributed manner with a small amount of local coordination.

A threshold activation policy with parameter m ischaracterized as follows: At a decision instant, a ready (or available) sensor s is activated if the number of active sensors does not exceed m after sis activated. Otherwise, sis kept in ready state till the next decision instant.In other words, athreshold policy with parameter m tries to maintain the number of active sensors in the system as close tomas possible, never exceeding mhowever.The activation decisions need to be taken only when the state of the overall system changes.

3.1.Performance Evaluation for Identical Coverage

To simplify the analysis and obtain fundamental insights, let us first examine the performanceof threshold policies for a system of sensors, where each of the sensors is able to cover theentire area of interest (.In this Identical Coveragescenario, the performance of activation policy Π is given by , where nΠ(t)denotes the number of active sensors at time twhen the system operates under policy Π. In this case, threshold policies achieve near-optimal performance in both FA and PA system models.

Theorem 1: The upper-bound to maximum achievable performance is given by [4, 5] :

(i)under the FA system model;

(ii)under the PA system model.

For FA system model, using Markov chain, the performance of threshold policies can be

expressed in closed-form,as a function of m. For PA system model, the performance of threshold policies can be expressed in terms of steady-state utilizations of equivalent queuing systems. Let UT(m) denote the time-average utility achieved by threshold activation policy employing a threshold of m. Let N be divisible by both (1+ρ) and by γ.

Theorem 2:Threshold policies provide the following performance bounds [4, 5, 6] :

(i)under FA model, for both IL and CL correlation models.

(ii)under PA model, for both IDR and CDRcorrelation models.

Note that the recommended threshold () is the energy balancing threshold given by solution to the equationunder FA system model, andthe equation under PA system model. Also, in the latter case, the threshold policy achieves asymptotically optimal performancewith respect to the sensor energy bucket size

Figures 4 and 5 plot the performance of threshold policies for various values of threshold parameter. For both the FA and PAsystem models, threshold policies achieve the performance bounds as given in Theorem 2, and the bounds can be shown to be fairly tight. The presence of correlation in the discharge and rechargetimes (processes) worsenssystem performance, particularly at higher values of the threshold.The threshold activationpolicies are of interest due to several reasons. Firstly, they achieve provably near-optimal performance under both the system models. Secondly, they are robust to the presence of spatial correlations in the recharge and discharge times(processes) across the sensor nodes. Thirdly, they are computationally efficient, since the sensors do not need to considertheircurrent energy levels or the utility function, while taking activation decisions. Finally, threshold policies can easily be extended to develop a distributed algorithm appropriate for more general network scenario, as described below.

3.2.Distributed Algorithm

In a realistic deployment scenario, sensor nodes would be deployed at random, and will typically cover different areas in the physical space of interest. In other words, the coverage areas of two sensors may overlap only partially, ormay not overlap at all.

Let midenote the targeted threshold for sensor i. In other words, sensor i wants to maintain a utility of U(mi) per unit area per unit time in its coverage areaAi. When the sensor is ready (available), then at any decision instant, it computes the current utility per unit time in its coverage area as follows. For a generic unit area element , let n(A,t) denote the number of active sensors covering it at time t. Then the current utility per unit time at time t in the coverage area of sensor i is calculated as . If the current utility is less than the targeted utility, then the sensor activates itself. Otherwise, the sensor remains in the ready (available) state until the next decision instant.

The targeted threshold may be different fordifferent sensors depending upon the density of deployment of sensor nodes in each sensor's coveragearea. For each unit area element , let N(A) denote the total number ofsensors covering A. Then the sensor i would like to maintain a threshold of in this area element, under the FA network model. The overalltargeted utility per unit time in the sensor's coverage area Ai is given by. Targeted utility can similarly be computed for PA network model.

In order to evaluate the network performance for a range of thresholds, let us introduce a localthreshold parameter. If sensor i employs a local threshold parameter of α, itstargeted utility is given by, under the FA network model and similarly under thePA network model. Note that the value of α = 1, corresponds to the recommended threshold given by Theorem 2.However, some of the invariants from the identical coverage case may not be satisfied in the general network scenario. For instance, even though allsensors employ a local threshold of α, it is possible that more than targeted number ofsensorsare active in some area element A at some point of time.

3.3.Performance Evaluation for General Network

The maximum achievable utility in each generic area element in the network is summed up to obtain the upper bound on the achievable performance for the entire network. The discharge and recharge processes at sensors are triggered by the occurrence of discharge and recharge events respectively. An event drops at an area element in the network and affects sensors which lie in the vicinity of the area element. These events occur randomly at the area elements spanning the entire network. The amount of spatial correlation in the recharge and discharge times (processes) at the sensor nodes is modeled using the different event models, namely,Independent Events (IE) model and Block-Correlated Event(BCE) model. Events occur according to a Poisson process, and are uniformly distributed in the area of interest. In IE model, an active sensor gets discharged by a quantumonly when a discharge eventoccurs within its coverage area. The recharge processis modeled similar to the discharge process. Note here that the recharge and dischargeprocesses at different sensors are not completely independent since the sensors may have overlapping coverage areas.However, the degree of correlation is smaller in comparison to the BCE model. In BCE model, the network is divided intovirtual blocks of equal sizes. A discharge(recharge) event occurring anywhere in the block affects all the sensors located in this block ina similar manner. This introduces spatial correlation across the discharge (recharge) times (processes) ofthe sensors.

The performance of the distributed node activation algorithm is evaluated using simulationsfor a wide range of system parameters, for different sensor system models.Atotal of N = 52 sensors, each having a circular coverage pattern of radius 12units, arethrown uniformly at random in an area of size 50x50. With these parameters, themean coverage of the network, defined as the average number of sensors covering anypoint in the deployment region, is observed to be approximately 9.1. The event detectionprobability for individual sensor node p = 0.1. For FA network model ρ = 3, and for PA network model γ = 2. The sensor energy bucket size K = 100.

Figures 6 and 7 plot the network performance for various values of local threshold parameter α, for FA and PA network models respectively. The performance for all the system models peaks at a value of α close to 1, and the peak performance is very close to upper bound.Note that, as the number of blocks decrease, the size of each block increaseswhich leads to an increase in the degree of spatial correlation.Therefore, the figures demonstratethat the performance of threshold policies degrade as the degree of spatial correlation increases.This performance drop is particularly significant at higher values of the threshold parameter α.Particularly, we observe that the performance bounds achieved for identical coverage case are also satisfied in the general network scenario.

4.Concluding Remarks and Open Questions

We have considered a network of rechargeable sensors, and addressed the question ofhow sensors should be activated dynamically with the objective of maximizing the time-average utility. Westudied the performance of simple threshold activation policies, and showed analyticallythat for the case withidentical coverage, the energy-balancing threshold policyattains performance:

  • At least ¾ of the optimum, under Full Activation sensor system model, and
  • At least of the optimum, under Partial Activation sensor system model.

The optimal threshold policy can be implemented in a distributed manner in the general network scenario and achieves near-optimal performance for various system parameters. Our results also show thatcorrelations in the discharge and recharge times (processes) worsen system performance, andoptimal threshold policy is robust to such correlations.

We have taken into account the effects of spatial correlation in the discharge and recharge times (processes) on the node activation policies. It remains to model and investigate the effects of temporal correlations on the activation policies. Another interesting perspective is to include the connectivity criteria in the network performance, in addition to that of coverage. Exploring the structure of the optimal activation policyin these scenarios using a Markov decision process framework remains to be an open question.

Bibliography

[1] A. Kansal, and M.B. Srivastava, “Energy Harvesting Aware Power Management”, in Wireless Sensor Networks: A Systems Perspective, Artech House, July 2005.