Introduction

The small size of the sensor nodes in an embedded sensor network restricts the amount of energy resources (typically in the form of batteries) that can be provided and hence the useful lifetime of the system. Therefore, several schemes have been proposed to regulate the rate at which energy is consumed by a sensor node in order to extend the lifetime. We describe one such technique which is based on the theory of Markov Decision Processes (MDP) and Kalman filtering.

The basic idea is to adapt the sampling rate of the sensors to the energy reserves of the system and the criticality of the data being sensed. Since the physical characteristics of the sensors are known, it is possible to build a mathematical model of their energy consumption rate and the relative accuracy of their measurements. This model can then be used to build offline a control policy for the nodes in the network. We have chosen MDPs as the formalism to generate the policy as the resulting controller can be easily implemented as a simple table lookup on the embedded node. We show how the Kalman filter framework can be integrated into the stochastic model and reward structure that are used by the MDP. Kalman filter theory is used to characterize the value of fusing the measurements from multiple sensors and is used while generating the control policy.

Problem statement

We consider the problem of adapting the control of a node in a sensor network to the local energy reserves while still maximizing the amount of information extracted from the network. We are given a distributed set of sensors, each sensor of which is capable of measuring some feature of the environment. The measuring process introduces random errors into the sensor readings. The error can be reduced by taking multiple readings at every sampling instant and averaging the readings. This corresponds to increasing the sampling rate of a sensor. In addition, integrating the readings from multiple sensors will reduce the amount of error in the joint estimate. In a real-world wireless sensor network performing either of these operations (increasing the sampling rate and transferring distributed sensor data to a central location for fusion) consumes energy which is a scarce resource. Hence, the goal is to develop a control framework for this scenario that minimizes the error in the system’s estimate of the measured phenomenon while expenditure of energy is also optimized.

Increasing the amount of information from the network can be accomplished by increasing the sampling rate (or duty cycle) of the individual sensor nodes. However, energy and communication bandwidth are unlimited resources in embedded sensor nodes. Thus, this will deplete their limited energy reserves quickly. A centralized controller is not feasible for the distributed sensor network scenario because the cost of transmitting the local state information (sensor readings and energy reserves) to a central location is large. Moreover, any practical control mechanism also has to take into account the limited computational ability of the embedded sensor nodes.

Solution

Our solution is based on the integrated optimization of both system resources (energy) and measurement accuracy in a distributed sensor network. We use the principles of Kalman filtering and Markov Decision Processes (MDPs) as the mathematical basis for the integrated optimization. In the first step, we assume full observability of the internal state of all sensors (that is its uncertainty in sensor readings, a function of its sampling rate, and energy reserves is known at a central location) and Kalman filtering is used to determine the total uncertainty of the system. This step is performed for all possible global states of the system. This step is illustrated in ??. In the second step, we assume that we are also given a stochastic model of the energy consumption rate of the sensors. The energy consumption model together with the optimal uncertainty at every possible state gives a stochastic model of the expected behavior of the sensors. This model is then used to obtain the optimal action (i.e., sampling rates) for each sensor using the value iteration algorithm for solving an MDP. This action policy is then encoded within each sensor. Note that the determination of this action policy is an offline process.

After deployment, to execute this action policy, each sensor estimates the internal state of the other sensors. As full communication of the internal state is prohibitively expensive considering the high energy cost of wireless transmission, we developed two methods for limiting communication of internal state. The first is based on monitoring the change in measurement uncertainty – a global communication step takes place only if the uncertainty exceeds a threshold. The second method is based on using Partially Observable Markov Decision Processes (POMDPs) – here, the uncertainty of not knowing the internal state of another sensor is explicitly modeled using a POMDP.

This work is supported by the National Science Foundation. The award is titled "CSR--EHS: DEFT (Distributed Embedded Fault-Tolerant Control of Resource Constrained Sensor Networks)".

Global policy construction: Solid dashed lines indicate flow of data from sensors to the Kalman filter to create the global state. Solid lines represent sensors internal state (energy). The state is used in the value iteration algorithm to generate the MDP Policy table.

Execution of control policy at node k: The internal states of remote sensors are approximated with stochastic models (SM) to form state s and access the policy table. The policy table output controls k’s sampling rate.