PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Strategies for Communication and Remote Estimation with an Energy Harvesting Sensor

Ashutosh Nayyar, Tamer Basar, Demosthenis Teneketzis, Venugopal V. Veeravalli

arXiv:1205.6018v1eess.SYmath.OC

TL;DR

The paper studies real-time remote estimation with an energy-harvesting sensor and jointly optimizes communication scheduling and estimation. It characterizes the decentralized problem dynamically and establishes optimal threshold-based communication with simple estimation.

  • Problem

    The paper addresses how a sensor and remote estimator can jointly support real-time estimation when sensor communication is energy-dependent.

  • Method

    It formulates a POMDP-based dynamic program for decentralized scheduling and estimation under communication and distortion costs.

  • Results

    The paper establishes globally optimal energy-dependent threshold communication and simple estimation strategies for finite-valued and multi-dimensional Gaussian sources.

  • Takeaways & Limitations

    The resulting threshold and estimation strategies simplify offline computation and online implementation of optimal remote-estimation policies.

Abstract

from arXiv · show

We consider a remote estimation problem with an energy harvesting sensor and a remote estimator. The sensor observes the state of a discrete-time source which may be a finite state Markov chain or a multi-dimensional linear Gaussian system. It harvests energy from its environment (say, for example, through a solar cell) and uses this energy for the purpose of communicating with the estimator. Due to the randomness of energy available for communication, the sensor may not be able to communicate all the time. The sensor may also want to save its energy for future communications. The estimator relies on messages communicated by the sensor to produce real-time estimates of the source state. We consider the problem of finding a communication scheduling strategy for the sensor and an estimation strategy for the estimator that jointly minimize an expected sum of communication and distortion costs over a finite time horizon. Our goal of joint optimization leads to a decentralized decision-making problem. By viewing the problem from the estimator's perspective, we obtain a dynamic programming characterization for the decentralized decision-making problem that involves optimization over functions. Under some symmetry assumptions on the source statistics and the distortion metric, we show that an optimal communication strategy is described by easily computable thresholds and that the optimal estimate is a simple function of the most recently received sensor observation.

I. INTRODUCTION · A. Notation

The paper studies decentralized joint optimization of energy-constrained sensor communication and remote estimation, where random harvested energy affects scheduling and the estimator must operate with intermittent messages. It also establishes notation for random variables, vectors, probabilities, indicator functions, and conditional distributions.

  • I. INTRODUCTION: The study examines how random energy supply affects the form of optimal communication scheduling and estimation strategies.This goal is presented as a decentralized decision-making problem under energy constraints.
  • I. INTRODUCTION: The setup couples a sensor observing an environmental process with a remote estimator that must produce real-time state estimates.Communication from sensor to estimator consumes energy.
  • I. INTRODUCTION: Random harvested energy makes communication availability stochastic, forcing the sensor to decide when to transmit and the estimator how to estimate between messages.The sensor may harvest energy from the environment, for example through a solar cell.
  • I. INTRODUCTION: The objective is to jointly optimize communication scheduling and estimation strategies to minimize accumulated communication and estimation cost.This differs from energy-harvesting communication work focused on transmission rate, power, throughput, or transmission time.
  • I. INTRODUCTION: Because the sensor decides whether to communicate using information unavailable to the estimator, the joint problem is decentralized.The sensor’s communication decision can signal source information through both transmissions and successive nontransmissions.
  • I. INTRODUCTION: A no-communication decision can reveal that the source lies within an interval when the sensor communicates outside that interval.Consequently, repeated noncommunication can make the estimator’s state estimate depend on more than the most recently received source state.
  • A. Notation: Random variables use uppercase letters, realizations use lowercase letters, and bold letters denote random vectors or their realizations.The sequence notation Xa:b denotes (Xa, Xa+1, . . . , Xb).
  • A. Notation: The notation defines probability and expectation, indicator functions, integer and Euclidean spaces, the identity matrix, and conditional PMFs or densities.P(X = x|Y ) denotes conditional event probability, while P(X|Y ) denotes the conditional PMF or density.

B. Organization … C. The Optimization Problem

The paper formulates finite-horizon remote estimation with an energy-harvesting sensor and jointly optimizes sensor communication and estimator strategies. It develops a function-space dynamic program and uses symmetry and majorization arguments to characterize optimal strategies for discrete and multi-dimensional Gaussian sources.

  • B. Organization: The paper organizes its development around discrete-source formulation, dynamic programming, symmetry-based strategies, multi-dimensional Gaussian sources, special cases, conclusions, and appendices.The organization identifies Sections II–VII and Appendices A–E as covering these components.
  • A. The System Model: The system model pairs a sensor observing a finite-state discrete-time Markov process with a remote estimator that reconstructs the process from transmitted messages.The source state space is a finite interval of the integers.
  • A. The System Model: Energy harvesting is random, storage is discrete and bounded by B, and each successful transmission consumes one energy unit.Harvested energy amounts form an i.i.d. process independent of the source, while observing without transmitting consumes no energy.
  • B. Decision Strategies: The sensor chooses whether to transmit using observation, energy, and past-message histories, while the estimator maps received messages to real-time estimates.The transmission decision satisfies U_t ≤ E_t, so no transmission is possible when E_t = 0; both sensor and estimator strategies may be represented by collections of decision-rule functions.
  • C. The Optimization Problem: Problem 1 seeks sensor and estimator strategies minimizing expected finite-horizon cost given source, energy-arrival, initial-energy, storage-limit, and horizon statistics.The objective combines communication cost c ≥ 0 with distortion function ρ : X × X 7→ R.
  • C. The Optimization Problem: The optimization is reformulated from the estimator’s perspective as a dynamic program involving minimization over a function space.Majorization arguments are used under symmetry conditions to characterize value functions and thereby obtain optimal strategies.
  • C. The Optimization Problem: The approach extends from the discrete case to multi-dimensional Gaussian sources and supplies optimal strategies under a suitable symmetry condition.It also treats special cases with a fixed transmission limit or with communication cost but no transmission-count constraint.

III. PRELIMINARY RESULTS · A. An Equivalent Problem

The preliminary results restrict the sensor’s strategy without performance loss and recast the decentralized problem from the estimator’s perspective. The equivalent formulation is a POMDP whose belief-state dynamic program characterizes optimal estimates and prescriptions, while function-space minimization motivates symmetry-based analysis.

  • III. PRELIMINARY RESULTS: With the estimator’s strategy fixed, the sensor’s optimization is a Markov decision problem with state (X_t, E_t, Y_1:t−1), so an optimal restricted strategy exists.The next state and expected cost depend only on this state and the transmission probability p_t.
  • III. PRELIMINARY RESULTS: The restriction remains valid for the globally optimal estimator strategy, allowing subsequent analysis to consider only sensor strategies of the Lemma 1 form.At time t, the sensor needs (X_t, E_t, Y_1:t−1), while the estimator knows Y_1:t−1.
  • A. An Equivalent Problem: The equivalent formulation makes the estimator the only decision maker, selecting an estimate and a prescription strategy ℓ whose functions determine the sensor’s transmission probabilities.Each prescription Γ_t maps (X_t, E_t) to [0, 1] and satisfies γ(x, 0) = 0.
  • A. An Equivalent Problem: Problems 1 and 2 are equivalent: corresponding sensor and prescription strategies achieve the same total expected cost in both formulations.This equivalence permits solving the estimator’s problem first and using its solution to obtain optimal strategies for the original problem.
  • A. An Equivalent Problem: The estimator’s reformulation is a POMDP with pre- and post-transmission states, prescription and estimate actions, controlled state evolution, observations, and communication and distortion costs.Transmission changes the energy state probabilistically, after which the source and harvested energy evolve according to known statistics.
  • A. An Equivalent Problem: The estimator’s information states are the pre-transmission belief Π_t = P(X_t, E_t|Y_1:t−1) and post-transmission belief Θ_t = P(X_t, E′_t|Y_1:t).Lemma 2 gives fixed transformations governing the evolution of these beliefs.
  • A. An Equivalent Problem: Theorem 1 characterizes optimal estimates and prescriptions as minimizers in a backward dynamic program over post- and pre-transmission beliefs.The estimate minimizer exists for each post-transmission belief, and the prescription minimizer exists for each pre-transmission belief.
  • A. An Equivalent Problem: The prescription minimization is difficult because it ranges over functions in G; the next section therefore uses symmetry assumptions to characterize optimal sensor and estimator strategies.The dynamic program is not solved directly, but instead provides an alternative characterization of optimal strategies.

IV. CHARACTERIZING OPTIMAL STRATEGIES · A. Definitions · B. Analysis

The paper defines neat sources and structural relations on information states, then shows that under neat-source and distortion assumptions, optimal estimation uses the latest received value while sensor transmission follows thresholds.

  • A. Definitions: A neat source has an almost symmetric and unimodal, even initial distribution and i.i.d. finite-support innovations with the same structural property.These assumptions ensure the source state remains in a finite integer interval over the finite horizon.
  • A. Definitions: Because the initial state and innovations have finite support and the horizon is finite, a neat source has a finite state space X.The state space is the finite interval containing all possible source states.
  • A. Definitions: The analysis introduces a binary relation R on information-state distributions and Property R for real-valued functions defined on those distributions.The relation compares distributions whose conditional state laws share almost symmetric unimodality about a common point.
  • B. Analysis: Under A1, the source is neat, while A2 restricts distortion to mismatch loss or |x −a|^k for some k.The subsequent analysis assumes both A1 and A2 throughout.
  • B. Analysis: When conditional state distributions are almost symmetric and unimodal about a common point x′, the minimum expected distortion is achieved at x′.This follows for the distortion functions specified in A2.
  • B. Analysis: The value functions satisfy Property R, and minimizing prescriptions therefore have a threshold form with energy- and belief-dependent parameters.Lemma 4 specifies lower and upper thresholds α(e, π) and β(e, π), with α(e, π) ≤β(e, π).
  • B. Analysis: Theorem 2 gives an optimal strategy whose estimate tracks the latest estimate, whose pre-transmission beliefs remain almost symmetric and unimodal about it, and whose prescription remains threshold-based.The initialization is ˆX0 := 0.
  • B. Analysis: For Problem 1, the optimal estimator uses the most recently received source value, while the sensor transmits when the current deviation exceeds a threshold depending on energy and belief.If no source value has been received, the optimal estimate is 0; transmission is omitted when the deviation is strictly below the threshold.

C. Optimal Thresholds

With the estimator fixed to g∗, a dynamic program computes a globally optimal sensor strategy. This strategy has deterministic thresholds depending only on the current energy level, and therefore realizes the threshold structure.

  • Optimality: The dynamic program’s strategy f∗ minimizes J(f, g∗) over all sensor strategies, including those outside F, and is globally optimal.It also belongs to F, so the dynamic program computes the optimal thresholds.
  • Threshold structure: For every positive energy level, the optimal action is zero below a distortion threshold and one above it.This follows because the relevant dynamic-program term is non-decreasing in d.
  • Threshold structure: The thresholds in f∗ depend only on the sensor’s current energy level, not on the pre-transmission belief π_t.Theorem 3 allowed thresholds to depend on both energy and π_t, whereas f∗ removes the belief dependence.
  • Threshold structure: The strategy f∗ is purely deterministic, unlike the possible randomizations at two points allowed by Theorem 3.For e > 0, the action is selected by comparing J_t(d, e) with the first term in the dynamic-program expression.

V. MULTI-DIMENSIONAL GAUSSIAN SOURCE

For the multi-dimensional Gaussian source, the decentralized estimation problem is characterized by an estimator-perspective dynamic program over sensor prescriptions and estimates. Under the stated symmetry conditions, optimality can be restricted to symmetric threshold transmissions and estimates centered at the beliefs’ symmetry points.

  • Model and formulation: The source is multi-dimensional Gaussian, and the sensor transmits its current observation vector and energy level or sends an empty message over a finite horizon.The estimator produces estimates from received messages, while sensor and estimator use deterministic strategies.
  • Model and formulation: Randomization is not needed for the Gaussian-source problem, and restricting sensor decisions to current source and energy states plus past transmissions causes no loss of optimality.The sensor’s deterministic decision restriction is explicitly stated to preserve optimality.
  • Dynamic programming: The estimator-perspective formulation selects binary-valued sensor prescriptions before transmission and estimates afterward, with beliefs evolving through fixed transformations.The dynamic program operates on pre-transmission and post-transmission conditional densities over source and energy states.
  • Dynamic programming: Theorem 4 gives a dynamic-programming lower bound, achieved by prescriptions and estimates attaining the stagewise infima; arbitrarily close performance remains possible when infima are unattained.The lower bound is V1(π1).
  • Optimal policy structure: Under symmetric-unimodal belief conditions, it is without loss of optimality to use symmetric threshold-based transmission prescriptions and estimates equal to the beliefs’ symmetry points.The argument propagates symmetry through time because the source dynamics preserve the relevant structure.
  • Optimal policy structure: The optimal threshold values are obtained from a dynamic program, while the resulting estimator strategy remains centered at the symmetry point of the relevant belief.Theorem 5 restricts the optimal strategies to this threshold-and-center form, with performance arbitrarily close to the lower bound.

VI. SPECIAL CASES

Under suitable assumptions on the source, the sensor’s energy storage limit B, initial energy statistics, and harvested energy, the paper derives special cases of Problems 1 and 3.

  • Special cases: Suitable assumptions on the source and energy dynamics enable derivation of special cases for Problem 1 in Section II and Problem 3 in Section V.The assumptions concern the source, storage limit B, initial energy level statistics, and energy harvested at each time.

1) Fixed number of Transmissions: … VII. CONCLUSION

The paper characterizes globally optimal communication and estimation for energy-harvesting sensors, including fixed-transmission, unconstrained-energy, and i.i.d.-source cases. Its main solution combines a POMDP-based dynamic program with energy-dependent threshold communication and simple estimation strategies.

  • 1) Fixed number of Transmissions:: At most K transmissions with no energy harvesting models the fixed-number-of-transmissions case.This follows when energy harvested at any time is Nt = 0 with probability 1.
  • 2) No Energy Constraint:: With storage limit B = 1 and one unit harvested at every time, the sensor is always guaranteed energy to communicate.This case still includes communication energy costs through cUt in the objective.
  • 3) I.I.D. Source:: For i.i.d. sources, the optimal estimate without transmission is the source mean value.The analysis can also be extended to finite-valued i.i.d. sources by replacing Dt with Xt in the dynamic program.
  • VII. CONCLUSION: The paper finds globally optimal communication scheduling and estimation strategies for finite-valued and multi-dimensional Gaussian sources.The conclusion covers the remote estimation problem with an energy-harvesting sensor.
  • VII. CONCLUSION: The optimal policies use energy-dependent threshold-based communication and simple estimation strategies.These strategies considerably simplify both off-line computation and on-line implementation.
  • VII. CONCLUSION: The analysis begins with a POMDP-based dynamic program for the decentralized decision-making problem.Because decentralized value functions involve minimization over functions, usual concavity or quadratic properties may not apply or help.
  • VII. CONCLUSION: The work identifies majorization-based properties related to Schur concavity as a potentially appropriate way to characterize optimal solutions.The conclusion emphasizes the need to find the right value-function property for decentralized dynamic programs.

APPENDIX A … APPENDIX C PROOF OF CLAIM 1

The appendices establish convolution and rearrangement lemmas for discrete and multidimensional Gaussian sources, then use them to prove Claim 1 by backward induction on Property R. The proof shows both dynamic-programming terms preserve Property R and constructs a no-worse prescription for ordered distributions.

  • A. For the discrete source: Convolution with an even, almost symmetric unimodal function preserves almost symmetric unimodality and maintains the ordering ξ ≺ ˜ξ.These properties are stated in Lemmas 8 and 9 for the discrete source.
  • B. For the multi-dimensional Gaussian source: For the multidimensional Gaussian source, convolution preserves the ordering ξ ∗µ ≺ ˜ξ ∗µ when µ is symmetric unimodal about zero.The result is given by Lemmas 12 and its continuation.
  • OTHER PRELIMINARY LEMMAS: A symmetric unimodal function convolved with a density symmetric unimodal about zero remains symmetric unimodal about the original center.The proof establishes symmetry through orthogonal transformations and unimodality through decreasing sphere integrals.
  • APPENDIX C PROOF OF CLAIM 1: Backward induction begins with WT+1(π) := 0 and proves that Property R propagates from Wt+1 to Vt.The proof separates the two terms in the dynamic-programming expression and applies the preliminary convolution lemmas.
  • APPENDIX C PROOF OF CLAIM 1: The immediate distortion term L(θ) satisfies Property R because distortion is non-decreasing in |x−a| and rearrangement bounds its inner products.The argument uses mXθ ≺ mX ˜θ and the fact that mX ˜θ is almost symmetric unimodal.
  • APPENDIX C PROOF OF CLAIM 1: For ordered distributions πR˜π, the proof constructs ˜γ from an optimal γ so that θγR˜θ˜γ and Wt(˜π) ≤ Wt(π).Since Vt preserves Property R, the transformed prescription has no greater continuation cost, completing Step 2.
  • APPENDIX C PROOF OF CLAIM 1: If Vt satisfies Property R, then Vt(δ(x,e−1)) is independent of x and equals K(e−1).The proof derives equality by applying Property R in both ordering directions to δ(x,e−1) and δ(x′,e−1).

APPENDIX D

Appendix D assumes a minimizing prescription γ and constructs a prescription ˜γ of the form in (15) that also achieves the minimum. The construction follows Step 2 of Claim 1, and the assumptions imply ˜γ satisfies the lemma’s required form.

  • Appendix D: The minimum defining W_t(π) is assumed to be achieved by a prescription γ.This is the starting assumption for the construction.
  • Appendix D: Using γ, the proof constructs another prescription ˜γ of the form in (15) that also achieves the minimum.The constructed prescription preserves optimality while taking the required form.
  • Appendix D: The construction of ˜γ is identical to Step 2 of Claim 1, with π used instead of ˜π to define n∗(e) and α(e).The proof explicitly reuses that construction with the stated substitution.
  • Appendix D: The almost-sure-unbiased assumption on π and the construction of ˜γ imply that ˜γ has the form required by the lemma.These conditions establish the lemma’s structural requirement.

APPENDIX E PROOF OF CLAIM 2

The proof uses backward induction to show that Properties R_n and R propagate from W_{t+1} to V_t and from V_t to W_t. It establishes these properties through symmetry, unimodality, convolution, and a prescription transformation that does not increase cost.

  • Step 1: Backward induction proves that W_{t+1} satisfying Property R_n implies V_t satisfies Property R_n.The argument considers the two terms in the dynamic-programming expression separately and concludes both satisfy Property R_n.
  • Step 1: Orthogonality of A and convolution with μ preserve the required ordering and symmetric unimodality, yielding π(·, e) ≺ π̃(·, e).The proof first transfers these properties through η and then uses Lemmas 12 and 13 for convolution.
  • Step 1: Lemma 17 shows that L(θ) := inf_a∈R^n E[∥X_t − a∥²|Θ_t = θ] satisfies Property R_n.The proof derives the result by applying the ordering relation and Lemma 10, then taking the infimum over a.
  • Step 2: If V_t satisfies Property R, a transformed prescription γ̃ can be constructed with W(π̃, γ̃) ≤ W(π, γ), implying W_t(π̃) ≤ W_t(π).The construction uses a ball centered at the symmetry point b and establishes θ_γ R θ̃_γ̃.
Loading 1205.6018v1…