betaFeedback

WorksComputer Science

Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous Feedback

Abstract

We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability qq, subject to average sampling- and transmission-rate constraints fsf_s and frf_r, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a 44-approximation guarantee. The joint problem reduces to the sampling-constrained problem when fs≤qfrf_s\leq qf_r and the transmission-constrained problem when fs≥frf_s\geq f_r. For qfr<fs<frqf_r<f_s<f_r, we formulate a constrained Markov decision process (CMDP) and introduce the class Πˉ\barΠ of (W,R)(W,R) policies, where WW specifies a waiting threshold for transmission and RR specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in Πˉ\barΠ. We then formulate a linear program (LP) over distributions of (W,R)(W,R) policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three (W,R)(W,R) policies. Since Πˉ\barΠ is countably infinite, for every ε>0ε>0 we construct a finite subset Πˉε⊂Πˉ\barΠ_ε\subset\barΠ and show that the LP restricted to this set yields an εε-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four (W,R)(W,R) policies with a 22-approximation guarantee for qfr<fs<frqf_r<f_s<f_r.

Paper details

vlnc:W_8ttaa3zy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…