{'fraction_non_alphanumeric': 0.029863398566169347, 'fraction_numerical': 0.004408060453400504, 'mean_word_length': 4.649062799288548, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sensor Scheduling for Energy-Efficient Target Tracking in Sensor Networks

In this paper we study the problem of tracking an object moving randomly through a network of wireless sensors. Our objective is to devise strategies for scheduling the sensors to optimize the tradeoff between tracking performance and energy consumption. We cast the scheduling problem as a Partially Observable Markov Decision Process (POMDP), where the control actions correspond to the set of sensors to activate at each time step. Using a bottom-up approach, we consider different sensing, motion and cost models with increasing levels of difficulty. At the first level, the sensing regions of the different sensors do not overlap and the target is only observed within the sensing range of an active sensor. Then, we consider sensors with overlapping sensing range such that the tracking error, and hence the actions of the different sensors, are tightly coupled. Finally, we consider scenarios wherein the target locations and sensors' observations assume values on continuous spaces. Exact solutions are generally intractable even for the simplest models due to the dimensionality of the information and action spaces. Hence, we devise approximate solution techniques, and in some cases derive lower bounds on the optimal tradeoff curves. The generated scheduling policies, albeit suboptimal, often provide close-to-optimal energy-tracking tradeoffs.


I. INTRODUCTION
In large networks of inexpensive sensors with small batteries, the sensor nodes are required to operate on limited energy budgets. Sensor management can prolong the lifetime of a sensor network and conserve In this paper, we consider a network of n sensors tracking a single object. The sensors can be turned on or off at consecutive time steps and the goal is to select the subset of sensors to activate at each time step. This problem is challenging due to the inherent tradeoff between the value of information in the sensor measurements and the energy cost, combined with the combinatorial complexity of the decision space.
In previous work [1], two of the authors considered approximate strategies for sensor sleeping, where the sensors are put to sleep to save energy and decisions are made concerning their sleep duration (in time slots). Once in a sleep mode, a sensor would only wake up after its own sleep timer expires. Here, we consider a scheduling variant of the problem which can be thought of as a sleeping problem with an external wake-up mechanism, i.e., sensors can be woken up by external means (e.g. a low-power wake-up radio). At time k, the permissible control actions for an n-sensor scheduling problem are n-dimensional binary vectors, i.e., vectors in {0, 1} n (corresponding to set sensor nodes to activate at each time step), in contrast to vectors in N na(k) 0 for the sleeping problem (corresponding to the sleep durations of awake sensors), where N 0 is the set of non-negative integers and n a (k) the number of awake sensors at time k. While this does not address the combinatorial nature of the control space, the simpler structure of the control space for the scheduling problem enables efficient approximate solution methodologies for the more realistic models that we study in this paper.
A significant body of related research work considers sensor management for tasking sensors in dynamically evolving environments. Castanon [2] has developed an approximate dynamic programming approach for dynamic scheduling of multi-mode sensor resources for the classification of a large number of unknown objects. The goal is to achieve an accurate classification of each object at the end of a fixed finite horizon by assigning different sensor modes to different objects subject to periodic or total resource usage constraints. Mode allocation strategies are computed based on Lagrangian relaxation for an approximate optimization problem wherein sample-path resource constraints are replaced by expected value constraints.
In the context of sensor scheduling for target tracking, information-based approaches [3], [4] have been developed for optimizing tracking performance subject to an explicit constraint on communication costs in a decentralized setting. Williams et al. [3] also adopt a Lagrangian relaxation approach to solve a constrained dynamic program over a rolling horizon. There, the combinatorial complexity of the decision space is avoided by first selecting one leader node, followed by greedy sensor subset selection. Other related work on sensor scheduling include leader-based distributed tracking schemes [5], [6], where at any time instant there is only one sensor active, namely, the leader sensor which changes dynamically as a function of the object state, while the rest of the network is idle.
While previous work focused on developing distributed implementations of efficient sensor scheduling strategies, our goal here is to study the fundamental theory of sensor scheduling for tracking and surveillance applications. Specifically, to explicitly study the fundamental tradeoff between tracking performance and energy expenditure, we define a unified objective function combining tracking and energy costs trading-off the complexity of per-stage costs to better capture the inherent energy-tracking tradeoff. We adopt a bottom-up approach where we consider a range of sensing, motion and cost models with increasing levels of difficulty and devise suboptimal scheduling policies to balance the tradeoff between energy expenditure and tracking performance. In some cases we are also able to derive lower bounds on the optimal energy-tracking tradeoff.
Due to noise and model uncertainties, natural limitations of the measurement devices, or incomplete data about the surroundings, we need to design scheduling policies when the system's state is only partially observable to the controller. Partially-Observable Markov Decision Processes (POMDPs) provide a natural framework for addressing sequential decision problems where the goal is to find a policy (strategy) for selecting actions based on the information available to the controller while addressing both short-term and long-term benefits and costs. Solving POMDPs optimally is generally intractable. For example, the value function for a POMDP with a finite state space depends on information states consisting of conditional probability vectors of dimension equal to the number of states. This has led to a number of POMDP approximations and we refer the reader to Monahan [7] and Hauskrecht [8] for excellent surveys on approximate methods for stochastic dynamic programming. Usually, no single approximation can be prescribed for all POMDPs, rather approximations can be judiciously used to exploit specific problem structures. In this paper, we use a subset of these approximate solution techniques, including reduceduncertainty and point-based approximations [9]- [12]. The former assumes that more information would be available to the controller at future time steps, and the latter solves a reduced optimization problem based on a relatively small subset of sampled beliefs about the object's state. We devise different approaches to deal with the aforementioned computational complexity of the decision space. In one approach, instead of solving one large combinatorial problem, we solve a set of simpler subproblems based on the intuition gained from a simplistic sensing model. In another approach, we iteratively sample control actions from a reduced control space based on the sparsity of a reachable belief set combined with point-based value updates.
The remainder of this paper is organized as follows. In Section II, we describe the tracking problem and define the sensing, transition and cost models, as well as the optimization problem, for each of the considered models. In Section III we describe approximate strategies to generate suboptimal scheduling policies. In Section IV, we present some experimental results, and finally, in Section V, we provide some concluding remarks.

II. SCHEDULING PROBLEM
In the following we consider different models with increasing level of difficulty. Depending on the structure of the model, we devise approximate methods to address the associated difficulties and generate efficient scheduling policies. For notation, vectors are denoted by bold lower-case letters. Superscript T denotes transposition and the indicator function is written as 1I{.}.

A. Simple sensing, observation and cost models
In this model, the network is divided into n distinct cells, one for each sensor. In other words, each cell corresponds to the sensing range of one particular sensor and sensors' ranges do not overlap. A Markov chain with an (n + 1) × (n + 1) probability transition matrix P describes the motion of the target through the field of interest. The extra state is for an absorbing termination state of the Markov chain which is reached when the object leaves the network. It is further assumed that all information about the object trajectory is stored at some central unit and is used to determine the scheduling actions for the different sensors.
We let u k,ℓ denote the action for sensor ℓ at time k; u k,ℓ = 1 if sensor ℓ is activated at time k + 1 and 0 if the decision is to turn it off. The action vector at time k, denoted u k , is a binary vector of size n × 1, one decision per sensor. In this simplistic model, we assume that the target is perfectly observable within the cell of an awake sensor or if it reaches the terminal state τ , otherwise it is unobservable. Thus, the observation s k at time k is defined according to: where ε stands for erasure. The observation model in (1) induces a well-defined probabilistic observation model p(s k |b k , u k−1 ) such that the current observation depends on that actual target location and the scheduling action for the n sensors.
At each time step, the incurred cost is the sum of the energy and the tracking costs. An energy cost of c ∈ (0, 1] per unit time is incurred for every active sensor and a tracking cost of 1 for each time unit that the object is not observed. Once state τ is reached the problem terminates and no further cost is incurred. In other words, τ is an absorbing cost-free state; all n states are transient so that τ is the only recurrence class of the Markov chain. Hence, The parameter c is thus used to tradeoff energy consumption and tracking errors.

B. Overlapping sensors with discrete observations models
In this model, we continue to use a discrete model for the target transition but we redefine a new sensing model and cost structure to account for the fact that sensors could have overlapping visibility regions. Within that model we further consider simple and probabilistic sensing.

1)
Overlapping sensors with simple sensing: In this case, the target is perfectly observed within the visibility region of any active sensor. Denote by R ℓ the set of locations in the visibility region of sensor ℓ and by B i the set of sensors that observe location i. The observation at time k is as follows: Therefore, a tracking error is incurred if none of the sensors observing the current target location is active. Redefining the cost structure for this model: 2) Overlapping sesnors with probabilistic sensing: By probabilistic sensing we account for observation uncertainty even if the target is within the visibility region of one or more active sensors. We assume, That is, the observation is uniformly distributed over the remaining locations (other than the true target location) that belong to the visibility regions of the set of awake sensors monitoring the true location b k . If the true target location does not belong to the visibility region of an awake sensor, we naturally exclude the visibility region of that sensor since no measurement is received from such a sensor. When R is a singleton {b k }, we set q = 1. A tracking error is incurred if the target is not directly observed and the uncertainty in the target location cannot be resolved.

C. Continuous observation, continuous state and arbitrary cost models
In this class of models, the object sensing model allows for an arbitrary distribution for the observations given the current object location. Tracking cost is modeled as an arbitrary distance measure between the actual and the estimated object location. If we denote the set of possible object locations B, we have B = m + 1. Note that, in contrast to the simplistic model in II-A, m is different from n since object locations are arbitrary and we no longer assume one location corresponds to the sensing range of one particular sensor. The (m + 1)-th state again corresponds to a termination state. Furthermore, the target can be moving on a continuous state space in which case m is ∞.
If the state space is discrete, then conditioned on the object state b k at time k, b k+1 has a probability mass function that is given by the b k -th row of the transition matrix P . If the state space is continuous, P is a kernel such that P (x, Y) is the probability that the next object location is in the set Y ⊂ B given the current object location is x. For simplicity of exposition, we focus on discrete state spaces. Also, we omit indexing time whenever the time evolution is well-understood to avoid cumbersome notation. We consider the following observation model for illustration; however, our approach is fairly general: where s is an n × 1 continuous observation vector with the i-th entry, s i , representing the observation of sensor i, p i , i = 1, . . . , n, is the position of the i-th sensor, b is the target state, and ε stands for erasure. δ(.) is the Dirac Delta function. In (6), the observation of an active sensor is Gaussian with a mean received signal strength inversely proportional to the square of the distance between the sensor and the actual target location. The observation of an inactive sensor is just an erasure.
The estimated target location (given the entire history) is denoted byb. We define the tracking error through an arbitrary bounded distance function d(b,b) between the actual and the estimated object locations, which can be the Hamming distance d(b,b) = 1I{b =b} or the Euclidean distance for discrete and continuous state spaces, respectively. The control at each time step is the tuple (b k , u k ). Sinceb does not affect the state evolution, the optimal value forb k is the value that minimizes the tracking cost over a single time step given history up to time k, i.e., where, I k denotes the information state, i.e., the total information available to the central controller at time k which is given by In the case of Hamming cost, it follows thatb is simply the MAP decision, i.e.,b = arg max b p k (b).

D. Optimal scheduling policy
The design of an optimal scheduling policy depends on the history up to time k, i.e., the information state I k . However, the posterior probability distribution, p k = Pr[b k |I k ], of the target's state given I k is a sufficient statistic for this class of partially observable processes. The distribution p k , also known as belief, summarizes all the information needed for optimal control. The sufficient statistic itself forms a Markov process whose evolution can be obtained through Bayes' rule updates 1 . For example, the belief update equation for the simplistic model in Section II-A can be written as: where e i is a row vector with a 1 at the i-th entry and 0 elsewhere. The vector [p k P ] S is the probability vector formed by setting the i-th entry [p k P ] i of the vector p k P to zero, ∀i / ∈ S, and then normalizing the vector into a probability distribution. The set {j : u k,j = 0} signifies the set of deactivated sensors.
In other words, the updated belief for the model in II-A, is a point mass distribution concentrated at τ if the object exits the network, and concentrated at b k+1 if the object is observed. When the object is unobservable, we eliminate the probability mass at all sensors that are awake, since the object cannot be at these locations, and normalize. The multi-valued function in (8), and equivalent Bayes' updates for the other models, define a transformation p k+1 = φ(p k , s k+1 , u k ), mapping the current belief p k , the current control vector u k , and the future observation s k+1 , to a future belief.
The policy u k = µ k (I k ) is defined as a mapping from information states I k to control actions u k . The goal is to design a policy that minimizes the expected sum of costs J, where, J is well-defined since g is upper bounded by cn + 1 (regardless of the model) and the expected time till the object exits the network is finite. Note that the termination is inevitable, thus the objective is to reach the termination state with minimal expected cost. Hence, the scheduling policy is the solution of the minimization problem, This POMDP problem falls within the class of infinite horizon stochastic shortest path problems.
Noting that the termination state is observable, cost-free and absorbing, and that every policy is proper 2 , a stationary policy µ * (.), i.e., one which does not depend on k, is optimal in the class of all historydependent policies and p k is a sufficient statistic for control [13], i.e., u * k = µ * (p k ), is defined through a time-invariant mapping from the belief space to the action space. J can be written in terms of the sufficient statistic and the optimal policy can be obtained from the solution of the Bellman equation: such that J(e τ ) = 0, where J(.) is the value function for the POMDP, and the expectation is taken over the future state b ′ which is distributed according to pP . Note that we removed the time dependence due to the aforementioned time invariance property. For continuous observations, summation over s is replaced by an integration.

III. APPROXIMATE SOLUTIONS AND LOWER BOUNDS
There are a number of algorithms for solving POMDPs exactly [14]- [16]. These algorithms rely on the powerful result of Sondik that the optimal value function for any POMDP can be approximated arbitrarily closely using a set of hyper-planes (α-vectors) defined over the belief simplex [14]. This fact is the basis for exact value iteration based algorithms, such as the Witness algorithm [17] for computing the value function. The result is a value function parameterized by a number of hyper-planes (or vectors) whereby the belief space is partitioned into a finite number of regions. Each vector minimizes the value function over a certain region of the belief space and has a control action associated with it, which is the optimal control for beliefs in its region.
To clarify, in value iteration we generally start with some initial estimate for J * and repeatedly apply the transformation defined by the right hand side of Bellman equation (11) until the sequence of cost denote the set of vectors parameterizing the value function J (k) after k iterations, where |J (k) | is the total number of hyper-planes, and α (k) i (b), which is a hyperplane in the belief space, represents the value of executing the k-step policy associated with the i-th vector starting from a state b. Hence, the value of executing the i-th hyperplane policy starting from a belief state p is simply the dot product of α i and p: Therefore, the value of the optimal k-step policy starting at p is simply the minimum dot product over all hyperplanes, i.e., Hence, J * (k) (p) is piecewise linear and concave. Some of the vectors (also known as policy trees) may be dominated by others in the sense that they are not optimal at any region in the belief simplex.
Thus, many exact algorithms devise pruning mechanisms whereby a parsimonious representation with a minimal set of non-dominated hyper-planes is maintained [7].
Even though the aforementioned linearity/concavity property makes the policy search a great deal simpler, the exact computation is generally intractable except for relatively small problems. The two major difficulties for exact computation arise from the exponential growth of the vectors with the planning horizon and with the number of observations, and the inefficiencies related to identification of such vectors and subsequently pruning them. Namely, the number of hyper-planes grows double exponentially such that after k steps the number of hyperplanes is O |U | |S| k , where |U | and |S| denote the cardinality of the control and observation spaces, respectively. Equivalently, the number of hyperplanes per iteration grows as: This has led to a number of approximations and suboptimal solutions techniques trading off solution quality for speed.
Remark III.1. The intractability of the optimal solution for our problem is primarily due to the following reasons: (i) The cost function is minimized over the simplex of probability distributions, i.e., the (m − 1)dimensional belief simplex for m-state discrete state-space models, and the space of probability density functions for continuous state-space models.
(ii) The exponential explosion of the action space with the number of sensors (2 n actions).
(iii) The exponential growth of the α-vectors with the planning horizon and with the number of observations, especially for continuous observation models.

A. Approximate solutions
In this section, we outline our approximate solution methodologies for the different models introduced in Section II. First, we consider approximations where it is assumed that more information becomes available to the controller at future time steps. Policies based on the assumption that uncertainty in the current belief state will be gone after the next action were first introduced within the artificial intelligence community and known as Q MDP policies [10], [17]. We show that under an observable-after-control assumption, our sensor scheduling problem decomposes into n simpler subproblems, one subproblem per sensor, for the simplistic model of II-A. These subproblems can then be solved exactly using policy iteration [13]. Furthermore, in this case, the Q MDP solution gives us a lower bound on the optimal tracking-energy tradeoff. Unfortunately, this natural decomposition does not extend to the other class of models due to the inherent coupling of their tracking errors. However, based on intuition gained from the simplistic model, we artificially decouple the scheduling problem for those models and individually learn the tracking costs corresponding to each subproblem under the aforementioned Q MDP assumption.
This approach combines Q MDP with reinforcement learning [18].
Second, we develop sensor scheduling strategies based on point-based approximations. Despite the fact that the generated Q MDP based policies perform reasonably well, generally the resulting policies would not take actions to gain information (an effect of the observable-after-control assumption), leading to situations wherein the belief state does not get updated appropriately. Furthermore, while decoupling the scheduling problem provides close-to optimal performance for uncoupled or lightly-coupled sensing and tracking models (see Section IV), it might come at the expense of reduction in solution quality for more realistic or heavily-coupled models. To that end, we develop point-based approximate scheduling policies. While our previous approach reduced complexity via decoupling and learning, the key idea here is to optimize the value function only for a small set of reachable beliefs P and not over the entire belief simplex. Point-based methods have shown great potential for solving large scale POMDPs mostly for robotic applications [8], [9], [11], [19]. Pineau et al. [9] proposed point-based value iteration (PBVI) which performs point-based backups only at a discrete set of reachable belief points, that can be actually Regarding the dimensionality of the action space, we devise a strategy to sample actions based on the support of the beliefs and the sparse structure of the transition models. Intuitively speaking, an object can only move from one side of the network to the other side within time constraints rendering exponentially many scheduling actions irrational at certain times. Hence, instead of performing full updates including 2 n actions, we perform the minimization over a reduced control space U (p) for every p ∈ P (see Section III-C1). When dealing with continuous or large observations, we combine that with a methodology that aggregates observations and uses aggregate observations for value iteration updates (Section III-C2). At the core of the algorithm we use Perseus [11], a variant of PBVI [9], whereby value iteration updates are not carried out for every sampled belief. Instead, the values for many belief points are improved simultaneously in one update. Fig. 1 depicts the structure of our point-based approximation, combining control space reduction and observation aggregation with point-based updates.

B. Q MDP based scheduling policies
Next, we consider our first class of policies based on the Q MDP reduced future uncertainty assumption.
First, we consider the simplistic model in Section II-A, then we use the intuition we developed from this model to devise similar policies for the other models. Since the POMDP is a stochastic shortest path problem with an absorbing cost-free termination state, and the expected termination time is finite, the cost-to-go function for a given belief can be written as the minimum of the dot product of the belief vector and a set of hyper-planes (α vectors): where {α i } is the set of hyperplanes constituting the value function J. In essence, the complexity of the Bellman equation (12) stems from the evolution of the belief p k in (8). We can see why (12) is hard to analyze if we further divide the second term in the summation into two terms depending on whether there is observability or there is an erasure, To further clarify we observe that: and the minimization problem is coupled across the sensors as the second term in (14), which is due to non-observability, depends on the action vector u. The action of one sensor affects belief evolution therefore coupling the problem across sensors. Now, if we make the assumption that perfect observations would be available to the controller after taking a scheduling action, we obtain an approximate surrogate function which can be used to generate a suboptimal scheduling policy. Namely, we replace p(s|u, b ′ ) = δ(s − b ′ ) in (12). We get The terms in the summation in (15) only depend on the control action for each sensor. Furthermore, the belief evolution is independent of the scheduling action, wherefore the approximate recursion in (15) decomposes into separable terms, one per sensor. Hence, the value function and the scheduling policy for sensor ℓ, under the observable-after-control assumption, can be obtained from the solution of per-sensor Bellman equation: The POMDP problem is now decomposed into n separate simpler subproblems such that the total cost function is the sum of the per-sensor cost function while the overall scheduling policy is the per-sensor policies applied in parallel. Each subproblem can be easily solved using standard policy iteration [13] with a simple minimization over a binary control action.
Fundamentally, for the simplistic model, we were able to decompose the problem into n simpler subproblems due to the separability of the tracking cost into per-sensor costs. Note that the problem is still coupled due to the belief evolution in (8)  In this case, we define a surrogate value function for the ℓ-th subproblem as follows: [pP ] i J ℓ (e i ) ℓ = 1, . . . , n (17) where T (i, ℓ) captures the contribution of the ℓ-th sensor to the total tracking error when the target's previous state is i and is obtained via Monte Carlo simulations. Namely, the expected tracking cost can be evaluated by repeatedly simulating our system from time k − 1 to time k while changing the state of the ℓ-th sensor. Similarly, (17) can be generalized for continuous state spaces.
Even though the Q MDP assumption leads to a separable problem and provides a lower bound on the optimal energy-tracking tradeoff for the simplistic model as we elaborate in Section III-D, the resulting scheduling policies are myopic, unlike the sleeping policies in [1]. This follows from the fact that under an observable-after-control assumption, the future cost term is independent of the control vector u. Therefore, we consider more efficient, albeit more difficult, point-based approximations in the next section.

C. Point-based approximate policies
In the previous section, we described Q MDP based policies, whereby issues (i) and ( For completeness we first briefly outline the steps of Perseus and refer the reader to [11], [12] for further details. Later, we discuss specific variations to the algorithm to address the dimensionality of the action and the observation spaces.

One iteration of Perseus
1) Sample a set of belief points P. We obtain these beliefs by simulating the target motion through the field taking random actions and generating observation according to the observation models in  (6) 2) Sample a belief point p ∈ P at random and compute the backup using (18a) and (18b), Perseus updates in POMDPs are the counterpart of asynchronous dynamic programming for MDPs [13] since the order of backup of the belief points is arbitrary and does not require full sweeps over the entire sampled belief set.

1) Sampling actions based on the support of the belief:
Note that the update equation (18) involves a minimization over all control actions in |U |. Even though one iteration of the algorithm is linear in the cardinality |U | of the control space, |U | itself is exponential in the number of sensors rendering the minimization infeasible for a relatively large sensor network.
The idea here is to exploit the structure of the scheduling/tracking problem. Since the target transition model is naturally sparse, we predict relatively small uncertainty regions for the target state at future time steps. More specifically, for every belief point in P, we use prior information about the target transition model to project the future state of the target. This is particularly useful when the current belief vector is sparse leading to more restricted uncertainty regions. Subsequently, we restrict our attention to a significant subset of sensors, that is, sensors of relevance to the particulars of the uncertainty region.
Hence, we only consider scheduling actions involving scheduling different combinations of a reduced number of sensors which considerably reduces the control space for every belief in P. If the number of significant sensors is still large, we randomly sample actions from the reduced control space. Note that the same intuition extends to more complex motion models wherein information about target speed, maneuver, and acceleration can be factored in to define the future uncertainty regions. Hence, instead of performing full updates including 2 n actions, we perform the minimization over a reduced control space for every p ∈ P. Specifically, we redefine the point update equation as: where U (p) designates the reduced control space for the belief vector p.
Note that, future iterations of the algorithm involving a particular belief point, ensure sufficient sampling to relevant control actions in the reduced control space. This approach is well suited to Perseus wherein the value for every belief point is guaranteed to improve over consecutive stages of the algorithm. It is worth mentioning that the observation and the cost models need to be computed on the fly for each sampled control action during the algorithm implementation. to the same minimizing hyperplane, then they can be aggregated [20]. Hence, if we can partition the observation space into regions that map to the same hyperplane (possibly non contiguous), the continuous model is reduced to a corresponding discrete model. Integration is replaced by a summation over these partitions and the weighing probabilities are obtained by integrating the conditional density over these partitions. This is clarified in the following: To find the regions of aggregate observations, we need to solve for the boundaries, i.e., for each pair (i, j) of α vectors we need to solve for s: where φ(p, u, s) Hence, we need to solve: After solving for the boundaries, we can readily define the regions: Now the update step is simply: where

D. Lower bounds
We are able to derive lower bounds on the energy-tracking tradeoff for the simple as well as the continuous Gaussian observation models. For the simple model, the Q MDP value function is itself a lower bound on the expected total cost since more information is available to the controller at future time steps given the reduced uncertainty assumption. To further clarify, observe that if we interchange the order of minimization and summation in the last term of (13), we obtain a lower bound on the optimal cost to go function. Hence, a lower bound can be obtained from the solution of the following equation: Interchanging the order of the summation and minimization corresponds to a fully observable state after the next scheduling action, i.e., that the future belief is e b ′ . Hence, the Q MDP value function is a lower bound on the cost function of the original problem.
Unfortunately, this is only true for the simplistic model and does not extend to the coupled models since the factored tracking cost in (17) need not be a lower bound on the true tracking cost.
To obtain a lower bound on the optimal energy-tracking tradeoff for such models, we combine the observable-after-control assumption with a decomposable lower bound on the tracking cost which we derive next. Consider the continuous observation model with discrete state space. Given the current belief p k and a control vector u k the expected tracking cost can be written as: Defining which is a conditional error probability for a multiple hypothesis testing problem with m hypotheses, each corresponding to a different mean vector contaminated with white Gaussian noise. Conditioned on H j the observation model is: where s(ℓ) is the ℓ-th entry of an n×1 vector s denoting the received signal strength at the n sensors, m j is the mean received signal strength when the target is at state j (j-th hypothesis), and w is a zero mean white Gaussian Noise, i.e. w ∼ N (0, σ 2 I). According to (27), sensor ℓ gets a Gaussian observation, which depends on the future target location, if activated at the next time step, and an erasure, otherwise.
Since the current belief is p k , the prior for the j-th hypothesis is π j = [p k P ] j . The error event E can be written as the union of pairwise error regions as where is the region of observations for which the k-th hypothesis H k is more likely than the j-th hypothesis denotes the likelihood ratio for H k and H j . Using standard analysis for likelihood ratio tests [21], [22], it is not difficult to show that: where, d 2 kj = ∆m T kj ∆mkj σ 2 , ∆m kj = m k − m j , and Q(.) is the normal distribution Q-function. The quantity d kj plays the role of distance between the two hypothesis and hence depends on the difference of their corresponding mean vectors and the noise variance σ 2 . Note that, for different values of k and j, ζ kj are not generally disjoint but allow us to lower bound the error probability in terms of pairwise error probabilities, namely, a lower bound can be written as: And we can readily lower bound the expected tracking error: Next we separate out the effect of each sensor on the tracking error: where 1 is the vector of all ones designating that all sensors will be active at the next time slot. The inequality in (32) follows from the fact that if we separate out the effect of the ℓ-th sensor we get a better tracking performance when all the remaining sensors are awake. Since this holds for every ℓ, a lower bound on the expected tracking error can be written as a convex combination of all sensors contributions: where, ℓ λ ℓ (p k ) = 1.
Let 1 −ℓ denote a vector of length n with all entries equal to one except for the ℓ-th entry being zero.
Then replacing from (31), To simplify notation, we define the following 2 quantities: Intuitively, T 1 (p; i, ℓ) represents the contribution of sensor ℓ to the total expected tracking cost when the underlying state is i, the belief is p, and when all sensors are awake. On the other hand T (p; i, ℓ) is the ℓ-th sensor contribution when it is inactive and all the other sensors are awake.
Now if we assume that the target will be perfectly observable after taking the scheduling action, a lower bound on the total cost can be readily obtained from the solution of the following Bellman equation: where Note that if we can solve the equation above for p = e i for all i ∈ {1, . . . , m}, then it is straightforward to find the solution for all other values of p. We therefore focus on specifying the value function at those points. Since this is the case, we further simplify our notation and use T (i, ℓ) and λ(i, ℓ) as shorthand for T (e i ; i, ℓ) and λ ℓ (e i ), respectively. We can see that a lower bound on the value function of sensor ℓ can be obtained as a solution to the following minimization problem over u: subject to Λ1 n = 1 m where 1 m is a column vector of all ones of length m.
The inner recursion can be solved to obtain a closed form solution for J (ℓ) (e b ) as: Since the problem is only constrained across the different sensors, we obtain a lower bound from the solution of the following optimization problem, subject to n ℓ=1 λ(i, ℓ) = 1 ∀i = 1, . . . , m.
We observe that for every i we are maximizing a concave piecewise linear function in λ(i, ℓ). We pose an equivalent convex optimization problem by realizing that the minimum of a set of concave functions is also concave. Since affine functions are concave, we can apply the technique here. Since the problem is unconstrained across the i dimension we focus on solving the max-min problem for a fixed i. The final solution can then be obtained by summing the objective function for m subproblems.
For each ℓ = 1, . . . , n add a variable t ℓ to the optimization problem. Also for every ℓ append 2 constraints to the optimization problem. The constraints state the minimization over u ℓ implicitly, by The modified problem is therefore: which can be readily solved using standard convex optimization techniques [23].

IV. RESULTS AND SIMULATIONS
In this section, we show experimental results illustrating the performance of the proposed scheduling policies for the different models considered in this paper. In each simulation run, the object was initially the optimal performance (see Section III-D). It is clear that both policies lead to tradeoffs that closely approach the lower bound. The Q MDP policy gets even closer to the lower bound at small tracking errors since the observable-after-control assumption is more meaningful in this regime. In Fig. 3  Next, we consider a network of 10 sensors where object locations are located on integers from 1 to 21. The observation for each sensor is continuous as in (6). For every object state and every scheduling action in the reduced control space, we sample 50 observations to construct estimates of the weight probabilities and compute the aggregate observation boundaries. Up to 32 actions are sampled from the reduced control space. In this setup, the belief set consists of 500 sampled belief vectors and we assume a Hamming error cost. Fig. 6 shows the performance of the different policies for the continuous observation model. It is shown that the point-based scheduling policy outperforms the Q MDP policy. We further show a lower bound on the optimal performance tradeoff. The lower bound is loose especially in the high tracking error regime since the derived bound on per-sensor tracking errors assumes all other sensors are awake. However, we can exactly compute the saturation point for the optimal scheduling policy since every policy has to eventually meet the all-asleep performance curve, shown in Fig. 6a, when the energy cost per sensor is high. At that point, all sensors are inactive and hence the target estimate can only be based on prior information.

V. CONCLUSIONS
In this paper we studied the problem of tracking an object moving randomly through a dense network of wireless sensors. We devised approximate strategies for scheduling the sensors to optimize the tradeoff within the belief simplex. Based on the belief support and the sparsity of the transition models, we developed a methodology to sample actions from reduced control spaces. This was combined with observation aggregation to address the complexity of the observation space for continuous observations models. In some cases we derived lower bounds on the optimal tradeoff curves. While being suboptimal, the generated scheduling policies often provide close-to-optimal energy-tracking tradeoffs. Developing distributed scheduling strategies when no central controller is available is an area for future research.
Another interesting challenge is when the statistics for object movement are unknown or partially known.