PaperlayerView exact revision on arXiv

Source-linked AI summary

Sensor Scheduling in Variance Based Event Triggered Estimation with Packet Drops

Alex S. Leong, Subhrakanti Dey, Daniel E. Quevedo

arXiv:1511.04792v4eess.SYcs.SY

TL;DR

Event-triggered transmission rules often lack theoretical justification, while prior work largely neglects packet drops. This paper derives optimal scheduling structure for a shared packet-dropping channel, including optimal single-sensor threshold policies.

  • Problem

    Event-triggered rules often lack theoretical justification, and prior work mostly neglects packet drops despite their relevance to wireless communication.

    Source: §I · p. 1

  • Method

    The paper optimizes transmission schedules over a shared packet-dropping channel by minimizing a convex combination of expected remote-estimation error covariance and sensor transmission energy.

    Source: §III · p. 5, §VIII · p. 15

  • Results

    For covariance-based schedules, unstable systems schedule a sensor at large error covariance, switching between sensors is threshold-type, and single-sensor threshold policies are optimal.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Optimal single-sensor threshold policies provide theoretical support for covariance-triggered transmission rules that had often been motivated heuristically.

    Source: §I · pp. 1–2

    The shared-channel setting permits at most one sensor to transmit at a time; channels allowing simultaneous transmissions are left as a possible extension.

    Source: §VIII · p. 15

Abstract

from arXiv · show

This paper considers a remote state estimation problem with multiple sensors observing a dynamical process, where sensors transmit local state estimates over an independent and identically distributed (i.i.d.) packet dropping channel to a remote estimator. At every discrete time instant, the remote estimator decides whether each sensor should transmit or not, with each sensor transmission incurring a fixed energy cost. The channel is shared such that collisions will occur if more than one sensor transmits at a time. Performance is quantified via an optimization problem that minimizes a convex combination of the expected estimation error covariance at the remote estimator and expected energy usage across the sensors. For transmission schedules dependent only on the estimation error covariance at the remote estimator, this work establishes structural results on the optimal scheduling which show that 1) for unstable systems, if the error covariance is large then a sensor will always be scheduled to transmit, and 2) there is a threshold-type behaviour in switching from one sensor transmitting to another. Specializing to the single sensor case, these structural results demonstrate that a threshold policy (i.e. transmit if the error covariance exceeds a certain threshold and don't transmit otherwise) is optimal. We also consider the situation where sensors transmit measurements instead of state estimates, and establish structural results including the optimality of threshold policies for the single sensor, scalar case. These results provide a theoretical justification for the use of such threshold policies in variance based event triggered estimation. Numerical studies confirm the qualitative behaviour predicted by our structural results. An extension of the structural results to Markovian packet drops is also outlined.

I. INTRODUCTION

The paper formulates covariance-based event-triggered scheduling for remote estimation over packet-dropping channels, optimizing estimation error against energy use. It derives structural scheduling results for state-estimate and measurement transmissions, including threshold policies in specified single-sensor cases.

I. INTRODUCTION

  • The scheduling objective balances expected remote estimation error covariance against expected sensor energy use, while allowing random packet drops.The paper contrasts this with event-triggered estimation work that neglected packet drops and scheduling work often constructed offline without event triggering.Source: §I · p. 1
  • For unstable systems, sufficiently large remote error covariance guarantees a scheduled transmission, and sensor switching exhibits threshold-type behavior.These results concern schedules based only on the remote estimator's error covariance.Source: §I · pp. 1–2
  • In the single-sensor state-estimate case, transmitting above an error-covariance threshold and remaining silent below it is optimal.The paper also notes that earlier variance-based transmission rules were often motivated heuristically.Source: §I · pp. 1–2
  • For measurement transmissions, threshold policies are optimal in the single-sensor scalar case, but counterexamples show they are not generally optimal for vector systems.The scalar result provides theoretical justification for variance-based threshold policies in that setting.Source: §I · p. 2
  • With Markovian packet drops, the single-sensor extension can require different thresholds depending on whether the previous packet was received or dropped.Source: §I · p. 2

II. SYSTEM MODEL AND REMOTE ESTIMATION SCHEMES

  • Transmission decisions are made at the remote estimator using its error covariance, and the shared channel causes collisions if multiple sensors transmit simultaneously.The sensors' packet receptions are modeled as independent, identically distributed Bernoulli outcomes with sensor-specific reception probabilities.Source: §II · pp. 2–3

A. Optimal Remote Estimator

  • When no sensor transmits, the remote estimator propagates its state estimate and covariance using the process model without a measurement update.The paper defines its information set from transmission decisions, reception outcomes, and received local estimates.Source: A. Optimal Remote Estimator · p. 3

B. Suboptimal Remote Estimator

The paper uses a constant-gain remote estimator because it is simpler to analyze, and compares it with the optimal estimator and measurement transmission. Under stated stability and reception conditions, the gain equations have a unique fixed point.

B. Suboptimal Remote Estimator

  • The constant-gain estimator replaces the scheduled sensor's time-varying gain with a constant gain and is used in Sections III–IV for its analytical simplicity and good performance in many cases.For a single sensor, this estimator corresponds to the optimal estimator.Source: B. Suboptimal Remote Estimator · pp. 3–4
  • Under the stated stable-system or sufficient packet-reception condition, the gain equations have a unique fixed point with the constant gain equal to the identity.The fixed point uses the local steady-state covariance and a remote covariance satisfying the stated recursion.Source: B. Suboptimal Remote Estimator · p. 4
  • Across 20 randomly generated parameter sets, the suboptimal estimator often gives good performance relative to the optimal estimator.The table also reports expected covariance when measurements are transmitted; the passage does not state a general winner for that comparison.Source: B. Suboptimal Remote Estimator · p. 4, Table I · p. 4

C. Imperfect Feedback Links

Imperfect feedback losses can be represented as reduced forward-link reception probabilities. The scheduling formulation minimizes a weighted error-and-energy objective, and dynamic programming provides a route to its finite- and infinite-horizon solutions.

C. Imperfect Feedback Links

  • A lost feedback command is equivalent, from the estimation perspective, to a forward-link dropout, so imperfect feedback is modeled by lower effective reception probabilities.The effective probability is the product of the forward- and feedback-link reception probabilities.Source: C. Imperfect Feedback Links · p. 4

III. OPTIMIZATION OF TRANSMISSION SCHEDULING

  • The finite-horizon scheduling objective minimizes a convex combination of expected remote error covariance and total transmission energy, with at most one sensor scheduled to avoid collisions.Transmission decisions depend on the remote error covariance, and each scheduled sensor incurs a transmission cost.Source: §III · p. 5
  • The finite-horizon problem can be solved by dynamic programming or exact enumeration, after which a lookup table can determine real-time transmission decisions.Because only one sensor may transmit, the action search can be reduced to the no-transmission choice or one of the M sensors.Source: §III · p. 5
  • For the infinite-horizon problem, the Bellman equation has a solution under the stated stability or packet-reception condition for at least one sensor.The paper identifies the covariance as the MDP state and the transmission choice as its action.Source: §III · pp. 5–6
  • The authors derive threshold-type structure rather than assuming a threshold policy in advance, distinguishing their approach from earlier dynamic-programming schemes.They describe truncating the countable covariance state space and using relative value iteration to compute approximations.Source: §III · p. 6

IV. STRUCTURAL PROPERTIES OF OPTIMAL

The finite-horizon analysis derives structure for covariance-based scheduling: unstable systems eventually require transmission at large covariance, and sensor switching follows threshold-type rules. These results are more complete for scalar systems, where covariance matrices are totally ordered.

A. Finite Horizon Costs

  • The finite-horizon cost functions and tr f(X) are increasing in covariance.These monotonicity properties underpin the structural comparisons used to characterize optimal schedules.Source: §IV · p. 6, A. Finite Horizon Costs · pp. 6–7
  • For unstable A, sufficiently large error covariance makes the optimal schedule transmit a sensor.For stable A, transmission may never be scheduled when transmission costs are large, since tr f(P) remains bounded.Source: A. Finite Horizon Costs · p. 7
  • If one sensor is optimal at a covariance and another at a larger covariance, the first will not be optimal at any still larger covariance.The result may not cover every case because covariance matrices are not generally totally ordered.Source: A. Finite Horizon Costs · p. 7
  • For scalar two-sensor systems, the corollary enumerates four possible covariance-dependent patterns for sensor 2’s optimal schedule.The scalar covariance set is totally ordered, allowing a more complete characterization.Source: A. Finite Horizon Costs · p. 7

B. Infinite Horizon Costs

The infinite-horizon structural results retain threshold-type switching behavior, but thresholds that may vary over a finite horizon become constant. They can reduce computation, although incomparable covariance matrices still require the full dynamic-programming or value-iteration algorithm.

B. Infinite Horizon Costs

  • In the infinite-horizon problem, thresholds are constant rather than time-varying as they generally are over a finite horizon.For the scalar two-sensor case, the finite-horizon thresholds are replaced by constant thresholds for each sensor.Source: B. Infinite Horizon Costs · p. 8
  • The structural results can reduce computation: once a sensor is not scheduled at a covariance, it is not scheduled at any larger covariance.When covariance matrices are incomparable in the positive semi-definite ordering, the full dynamic-programming or value-iteration algorithm is still needed.Source: B. Infinite Horizon Costs · p. 8
  • With steady-state local Kalman filters, the truncated state space has cardinality NM and the action space has cardinality M + 1.These cardinalities are linear, not exponential, in the number of sensors M or horizon K.Source: B. Infinite Horizon Costs · p. 8

C. Single Sensor Case

In the single-sensor case, the optimal policy is a covariance threshold policy, with an infinite threshold possible for stable A. The ordered covariance states also permit a Markov-chain analysis yielding expressions for expected energy use and error covariance.

C. Single Sensor Case

  • For the single sensor, the optimal finite- and infinite-horizon policies use covariance thresholds, which may be infinite when A is stable.The steady-state covariance set is totally ordered, and finite-horizon thresholds may vary with time.Source: C. Single Sensor Case · p. 8
  • The threshold policy lets the remote error covariance evolve as a Markov chain whose state i corresponds to f^i(Pbar).The threshold index t depends on β, and the chain has positive recurrent states for λ in (0, 1).Source: C. Single Sensor Case · pp. 8–9
  • The stationary distribution yields analytical expressions for expected energy usage and expected error covariance in the infinite-horizon single-sensor case.Expected error covariance is expressed as a stationary-probability-weighted sum of traces of the covariance states.Source: C. Single Sensor Case · p. 9
  • The expected error covariance is finite under the stated condition that λ > 1 − 1/max_i |σ_i(A)|^2.The paper says this follows by an argument similar to the proof of Theorem III.1.Source: C. Single Sensor Case · p. 9

V. TRANSMITTING MEASUREMENTS

For transmitted measurements, the paper proves threshold optimality for a single sensor in scalar systems, but shows that threshold and sensor-switching properties need not extend to vector or multi-sensor settings. The analysis assumes only overall-system detectability, and finite-horizon scheduling can be solved by dynamic programming.

A. System Model

  • With measurements transmitted, detectability is required for the overall system rather than for each sensor, and local Kalman filtering at individual sensors is unnecessary.The section also notes that sending measurements is more practical when sensors have limited computation capabilities.Source: §V · p. 9, A. System Model · p. 9

B. Optimization of Transmission Scheduling

  • The finite-horizon covariance-dependent scheduling problem is solved by dynamic programming, working backward over the time horizon.The infinite-horizon formulation is mentioned but omitted for brevity.Source: B. Optimization of Transmission… · pp. 9–10

C. Structural Properties of Optimal Transmission Scheduling

  • For a single sensor in a scalar system, the cost difference between not transmitting and transmitting increases with covariance, implying an optimal threshold policy.The result provides theoretical justification for variance-based triggering.Source: C. Structural Properties of Optimal… · pp. 10–12
  • For vector systems, the scalar structural result does not generally hold, and threshold policies are not generally optimal when measurements are transmitted.The paper attributes the difficulty in part to error covariance matrices being only partially ordered.Source: C. Structural Properties of Optimal… · p. 12
  • With two scalar sensors, the optimal schedule switches from sensor 2 to 1 and back to 2 as covariance crosses 0.5485, 0.8642, and 3.9005.This example also shows that the estimate-case sensor-switching property can fail even for scalar systems.Source: C. Structural Properties of Optimal… · p. 12

D. Transmitting State Estimates or Measurements

The optimal estimator using transmitted state estimates outperforms measurement transmission in all reported cases; the suboptimal estimator also outperforms it in many cases. Infinite-horizon optimization is less computationally intensive for state estimates than for measurements.

D. Transmitting State Estimates or Measurements

A. Single Sensor

The examples show threshold behavior for single-sensor scheduling and covariance-dependent switching among multiple sensors. A performance comparison finds that the stronger approach depends on the desired error–energy operating point.

A. Single Sensor

B. Multiple Sensors

C. Performance Comparison

  • The comparison scheme permits transmissions in round-robin turns to avoid collisions.Source: C. Performance Comparison · p. 14
  • The compared sensor-triggered scheme requires the full remote state estimate as feedback in the multi-sensor case, whereas the proposed remote scheduler needs only one-bit decision feedback.Source: C. Performance Comparison · p. 14
  • At smaller expected energies the state-estimate-triggered scheme performs better, while remote scheduling performs better when a smaller expected error covariance is required.The comparison uses the infinite-horizon, two-sensor setting; the state-estimate-triggered scheme requires feedback of the full remote estimate for multi-sensor implementation.Source: Figure 10 · p. 14, C. Performance Comparison · p. 14

VII. MARKOVIAN PACKET DROPS

For Markovian packet drops, the paper extends its single-sensor analysis by conditioning transmission decisions on the previous loss state as well as the remote error covariance. It derives state-dependent threshold policies and concludes that a threshold policy is optimal for the single-sensor case.

VII. MARKOVIAN PACKET DROPS

  • With Markovian packet drops, the single-sensor transmission decision depends on the remote error covariance and the previous packet-loss state.The previous state distinguishes whether the last transmission was received or lost; the loss process is described by failure and recovery rates.Source: §VII · p. 14
  • For finite-horizon scheduling, thresholds exist for each time step and can differ depending on whether the previous packet was received or lost.Source: §VII · p. 15
  • For the infinite-horizon problem, the optimal policy uses separate covariance thresholds for the previous-received and previous-lost states.The policy does not transmit exactly when covariance is below the corresponding threshold.Source: §VII · p. 15

VIII. CONCLUSION

  • The conclusion identifies threshold-policy optimality in the single-sensor case and structural results for scheduling with either state estimates or measurements.Source: §VIII · p. 15

APPENDIX

The appendix derives the remote estimator’s covariance recursions and proves uniqueness results under stated stability conditions. It also explains how the estimator equations change when no sensor transmits.

A. Derivation of Optimal Estimator Equations (3)

  • The remote covariance recursions are extracted from the augmented-system recursion, and the gains are chosen to minimize the updated covariance trace.When no sensors transmit, the corresponding estimator equations follow by setting the transmission indicators to zero.Source: A. Derivation of Optimal Estimator… · p. 16

B. Proof of Theorem II.2

  • For stable A, the Lyapunov equation has a unique solution P.The passage also states a uniqueness condition for unstable A, but its condition is incomplete here.Source: B. Proof of Theorem II.2 · p. 16
  • The proof establishes uniqueness of the local-filter fixed point under the stated spectral-radius conditions.The argument invokes stability of the local Kalman-filter dynamics and an additional condition involving the estimator gain.Source: B. Proof of Theorem II.2 · p. 17

C. Proof of Theorem III.1

The proof verifies conditions for existence of solutions to the infinite-horizon problem, first using an always-transmit policy for one sensor. It extends the existence result to multiple sensors when a sensor meets a packet-reception condition.

C. Proof of Theorem III.1

  • For unstable A, the always-transmit policy has bounded expected error covariance when λ_m > 1 − 1/max_i |σ_i(A)|^2, yielding a standard policy for the single-sensor existence proof.For stable A, the relevant infinite series converges; the induced Markov chain’s positive recurrent class is the full state space.Source: C. Proof of Theorem III.1 · pp. 17–18, Figure 11 · p. 17
  • The single-sensor proof verifies the finite-cost condition because each stage cost combines expected error covariance and transmission energy.Together with the standard-policy condition, this establishes existence of infinite-horizon solutions for the single-sensor case.Source: C. Proof of Theorem III.1 · pp. 17–18
  • For multiple sensors, existence follows if at least one sensor satisfies λ_m′ > 1 − 1/max_i |σ_i(A)|^2.Restricting the policy to that sensor is sufficient for the existence argument.Source: C. Proof of Theorem III.1 · p. 18
Loading 1511.04792v4…