1 Optimal Policies for Age and Distortion in a Discrete-Time Model

2025-04-30 0 0 511.88KB 34 页 10玖币

Optimal Policies for Age and Distortion in a

Discrete-Time Model

Yunus ˙

Inan, Student Member, IEEE, Reka Inovan, Student Member, IEEE, Emre Telatar, Fellow, IEEE

Abstract

We study a discrete-time model where each packet has a cost of not being sent — this cost might depend on the packet content.

We study the tradeoff between the age and the cost where the sender is conﬁned to packet-based strategies. The optimal tradeoff

is found by an appropriate formulation of the problem as a Markov Decision Process (MDP). We show that the optimal tradeoff

can be attained with ﬁnite-memory policies and we devise an efﬁcient policy iteration algorithm to ﬁnd these optimal policies.

We further study a related problem where the transmitted packets are subject to erasures. We show that the optimal policies for

our problem are also optimal for this new setup. Allowing coding across packets signiﬁcantly extends the packet-based strategies.

We show that when the packet payloads are small, the performance can be improved by coding.

Index Terms

Age of Information, Distortion, Markov Decision Process, Policy Iteration

I. INTRODUCTION

Timeliness of information is a crucial aspect of communications. Stale data may have highly undesirable effects; think, for

example, of sensor output for self-driving vehicles, position of an airplane, coolant temperature in a power plant, etc. This

aspect of data is nicely captured by the recently studied notion of Age-of-Information (AoI), by shifting the focus from delay to

freshness. At the same time, not all data is equally important. If, in an attempt to reduce staleness our system drops important

pieces of data, the remedy may be worse than the disease. In this work, we study a simple setup where the freshness and

importance aspects may be treated together.

The loss, or misrepresentation of data and assigning higher cost to more important data is well-captured by the tools of

rate-distortion theory. As said above, the question of freshness has been an object of study in the AoI literature initiated by

Kaul et al. [2]. Since the introduction of AoI, there has been various uses of this metric in many applications. In this work, we

quantify the notion of importance by using a distortion metric. We analyze a discrete-time model which allows us to analyze

the tradeoff between timeliness as measured by AoI and the distortion of the data. The tradeoff can be studied by casting it as

a problem of ﬁnding the optimal policy of a Markov Decision Process (MDP) which identiﬁes the packets to be dropped. We

show that the optimal policy for this MDP can be achieved by a system with ﬁnite memory and we also provide an explicit

The authors are with ´

Ecole Polytechnique F´

ed´

erale de Lausanne (EPFL), 1015 Lausanne, Switzerland. Emails: {yunus.inan, reka.inovan,

emre.telatar}@epﬂ.ch.

A short version of this work is presented at IEEE ITW 2021 [1].

arXiv:2210.12086v1 [cs.IT] 21 Oct 2022

algorithm to compute this policy, which also turns out to be an optimal policy of a problem where the sender transmits packets

over an erasure channel with feedback. Lastly, for packets with small payload, we show that one can improve the performance

with variable-to-ﬁxed length coding techniques, such as Tunstall coding.

II. RELATED WORK

Freshness of data is recently recognized as a semantic aspect of communication. Initial work by Kaul et al. introduced

the AoI as a metric to quantify this aspect [2]–[4]. Following Kaul et al., there have been many studies adopting AoI as a

freshness metric. The ﬁrst strand involved calculation of AoI in simple schemes, e.g. M/M/1 queues [2]. Subsequent extensions

involve more general queues [5]–[8], multiple source streams [9]–[12], various queue management techniques such as the

Last-Come-First-Served (LCFS) protocol [13], and models that allow packet discards [14]–[17] and deadlines [18]. A partial

list of studies that seek to compute or to minimize the age under energy or link constraints is [19]–[34]. For a comprehensive

survey over the AoI literature, see [35]; and for a tutorial, see [36].

Although the works cited above mostly assume error-free transmissions, some others take into account that packets get lost

or erased while passing through the network. In [37], the AoI is studied in a model where transmissions are error-prone. One

may notice that a simple method to combat erasures is to send the packet repeatedly. A more complicated method could send

coded packets, which are then to be conveyed through the erasure channel. A list of works concerning coded transmissions

with feedback is [38]–[45]. An example of a study assuming no feedback is [46], where the authors ﬁnd the optimal coding

strategy. In Section VI, we will discuss that the optimal strategy for our discrete-time model is also optimal for a model where

communications take place over an erasure channel with feedback.

AoI has also found place in stochastic control literature. For instance, in [47], a tradeoff between the information staleness and

performance of a Linear Quadratic Regulator (LQR) is illustrated. In [48], freshness is taken as basis for an algorithm devised

for distributed tracking of a linear system. These works are aligned in the sense that using the fresh data to track and control a

system might improve the performance. This is because of the Markovian nature of the processes that are tracked — the next

state depends only on the freshest data. However, this may not always be the case as the freshest may not be the most important.

This observation is in line with some further studies. For instance in [49], a problem of generating timely updates in a remote

estimation setting has been proposed. The authors have investigated the Mean-square-optimal and AoI-optimal strategies for the

estimation of a Wiener process through a queue and concluded that they are different; consequently demonstrating a tradeoff

between freshness and importance. In [50], the authors generalized the settings to include an Ornstein–Uhlenbeck process. In

[31], a tradeoff between timeliness and distortion is shown for the case of estimation through a Gaussian channel in a power

constrained setting. There also has been several works on integrating the notion of different data importance and timeliness,

e.g., by introducing non-linear cost to stale data [51], [52], by considering separate data streams of different priorities [53],

[54], or by modeling the distortion as a decreasing function of the service time [55].

Our setup contains ﬂavors from the above approaches, yet it features novel aspects. For instance, the resource constraint

is imposed by an external scheduler, giving the sender turns to speak. Hence, as opposed to the works [49], [50], the sender

cannot decide when to send; but it rather decides what to send. Furthermore, we adopt the view that data is formed into

packets of different importance levels, e.g., packets containing abnormal levels of coolant temperature in a nuclear plant could

be classiﬁed as important. Consequently, the distortion metric we propose depends on whether the packets are received or not,

and the accumulated importance levels of the missed data constitutes our distortion metric.

III. NOTATION

Random variables are denoted with uppercase letters (e.g., X); and vectors are denoted with boldface letters (e.g., b). Sets

are denoted with script-style letters (e.g., V). l(b)is the length of a vector b, and biis its ith element. For vectors band b0,

bkb0:= [b1, b2, . . . , b0

1, b0

2, . . .]is the concatenation of the two vectors. b≥i:= [bi, . . . , bl]is segment of bfrom its ith element

until the end; and bj

i:= [bi, . . . , bj]is the segment between its ith and jth elements, bi:=bi

1.b0is a sufﬁx of bif there

exists an i > 1such that b0=b≥i. If b0=b≥iis sufﬁx of b, then b\b0=bi−1. For a, b ∈R,a∧b:= min{a, b}, and

a∨b:= max{a, b}.

IV. PROBLEM DEFINITION

In this section, we describe our discrete-time model in terms of the data to be conveyed, the sender-receiver pair with their

respective communication protocol, and the channel in between.

We assume that the data is formed into packets, and at each time instant t, a new packet arrives to the sender. The packet

payloads originate from a set of ﬁnite elements X, and the probability of a payload taking a particular value is time-invariant

and independent of the past. Consequently, the data is an independent and identically distributed (i.i.d.) process {Xt}t∈N. The

sender observes Xtat time tand keeps Xtin its buffer.

The communication protocol is as follows: The sender is allowed to speak at times T1, T2, . . .. The process {Ti}i∈Nis

independent of the process {Xt}t∈N, and has the property that the interspeaking times Zi:=Ti−Ti−1are i.i.d.. Moreover,

we assume that Zi’s are strictly positive and square integrable, i.e., Pr(Zi>0) = 1 and E[Z2

i]≤ ∞. An example of such a

random variable could be a geometric random variable with Pr(Zi=t) = p(1−p)t−1for t≥1. The speaking process {Ti}i∈N

is inspired by MAC layer protocols where each sender is assigned time slots to speak. When the sender is given a turn to

speak, i.e., at each Ti, it selects a packet from its buffer with timestamp Si≤Tiand forwards XSi. Once XSiis forwarded, we

restrict the sender to not send a packet with timestamp less than Siat the subsequent speaking times Ti+1, Ti+2, . . .. Note that

such restriction results in Si< Si+1. The increasing sequence {Si}i≥0=:Sis henceforth referred as the ‘selection process’.

Transmissions between the sender and the receiver are noiseless and zero-delay. Hence, by time t, the receiver has observed

XSifor every isuch that Ti< t. We also suppose that the packets are formed to contain timestamps, i.e., the packet containing

XSialso contains the information that it was generated at time Si. Consequently, at time t, the receiver is able to reconstruct

the data as Yj(t) = Xjif Xjis among its observation up to time t; otherwise it sets Yj(t)=?.

At this point, we have described our model. Now, we introduce the appropriate distortion and timeliness metrics to study

their tradeoff. Speciﬁcally, given d:X × X ∪ {?} → R≥0, with

d(x, x)=0and d(x, ?) =:v(x),(1)

and given a selection procedure S, deﬁne

D(S)

t:=1

i=1

d(Xi, Yi(t)) and D(S):=Elim sup

t→∞

D(S)

t.(2)

With an analogy to rate-distortion theory, observe that D(S)

tquantiﬁes average distortion between the source and its recon-

struction. D(S)is the expected long-term average distortion.

Timeliness of information is quantiﬁed with the well-studied AoI metric. Namely, with i(t):= sup{i≥0:Ti< t},

T0=S0= 0; deﬁne for all t > 0,

∆(S)

t:=t−Si(t),and ∆(S):=Elim sup

t→∞

τ=1

∆(S)

τ. (3)

∆(S)

tis usually referred as the instantaneous age; and similar to D(S),∆(S)is the expectation of the long-term average age.

Note that Yi(t)can be either equal to Xior to ‘?’. Therefore, specifying only d(x, x)and d(x, ?) — which is readily

determined by v(x)— is sufﬁcient to evaluate D(S). As a consequence, the sender may base its selection Sion VTi, where

Vt:=v(Xt). Therefore, the selection Siis a map Si:VTi→ {Si−1+ 1, . . . , Ti}with V:={v(x):x∈ X }. Intuitively, Vi

represents an importance score for the packet i; high Viis interpreted as the content having high importance and not sending

it incurs a high penalty — this interpretation is also consistent with a model where some arrivals are prioritized. Observe

that the structure of the problem stays the same if all elements of Vare multiplied by a positive constant. If Vdoes not

contain 0, then without loss of generality one can assume that the minimum element in Vis 1and it is an ordered set as

1 = v1< v2< . . . < v|V| :=vmax <∞.

Now that we have the full description of the setting, we aim to characterize the achievable region of (∆(S), D(S))pairs.

We attempt to characterize this region in the sequel and conclude this section with a few remarks.

(i) The model we propose is reminiscent of a remote estimation problem of a discrete-time stochastic process through a

discrete-time queue. However, we require that the sender sends a packet exactly at speaking times, which is equivalent

to force the sender to send as soon as the queue is idle in a discrete-time queueing setting. In [56] and [49], it is shown

that the optimal policies need not be of this type. This makes our problem different and allows us to make the relaxation

that Sineed not be stopping times.

(ii) If 0∈ V, there are multiple interpretations. Vt= 0 can be interpreted as either the data is totally trivial (need not be

reconstructed), or interpreted as the source having not generated data at time t. The second interpretation allows us to

model a source which generates data sporadically. Now there is the question of allowing Xtto be sent or not. Our model

allows sending of Xt, i.e., in the second interpretation, informs the receiver that there has not been any data generated

by the source, and ∆tdecreases accordingly. The reduction of ∆tcan be avoided by appropriate reformulation — to be

discussed in Remark 1.

V. THE AGE-DISTORTION TRADEOFF

A. Markov Decision Problem Formulation as a Lower Bound

To study the age-distortion tradeoff, we study the family of weighted costs η∆(S)+D(S)for η > 0. It is known that the

boundary of the achievable (∆(S), D(S))region can be characterized by studying this family. We seek to obtain a tractable

lower bound for η∆(S)+D(S), and then we further optimize this lower bound over S. First, we derive a simpler expression

for ∆(S). Observe that

lim sup

t→∞

τ=1

∆(S)

τ= lim sup

i→∞ Pi

j=1 Q(S)

j=1 Zj

(4)

where

Q(S)

j:= (Tj−Sj)Zj+1 +Zj+1(Zj+1 + 1)

2.(5)

Since lim

i→∞

iPi

j=1

Zj+1(Zj+1 +1)

2=1

2E[Z1(Z1+ 1)] =:νand limi→∞ 1

iPi

j=1 Zj=E[Z1] =:µwith probability 1 by the

law of large numbers, we obtain

∆(S)=E1

µlim sup

i→∞

j=1

(Tj−Sj)Zj+1 +ν

µ.(6)

Note that ∆(S)cannot be smaller than ν/µ. We subtract ν/µ to obtain the excess age, given by

∆(S)

e:=E1

µlim sup

i→∞

j=1

(Tj−Sj)Zj+1(7)

and determine the feasible (∆(S)

e, D(S))pairs. With the same reasoning as above, we study the family η∆(S)

e+D(S). When

the selection process Ssatisﬁes a certain square-integrability condition, we can ﬁnd alternative expressions for ∆(S)

eand D(S).

Theorem 1. Let S2be the set of selection processes Swith supiE[(Ti−Si)2]<∞. Then for any S∈ S2,

∆(S)

e=Elim sup

i→∞

j=1

(Tj−Sj),(8)

D(S)=1

µElim sup

i→∞

j=1

D(VTj, Sj−1, Sj),(9)

where

D(VTj, Sj−1, Sj):=

Sj−1

j0=Sj−1+1

Vj0(10)

is the penalty incurred by skipping the portion [VSj−1+1, . . . , VSj−1]of VTj.

Proof. See Appendix A.

At this point, we would like to eliminate some of the non-optimal selection processes. More speciﬁcally, we show that if a

packet with importance value vmin and with timestamp less than Tiis selected at time Ti, then one can ﬁnd another selection

process which performs at least as well.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1OptimalPoliciesforAgeandDistortioninaDiscrete-TimeModelYunusInan,StudentMember,IEEE,RekaInovan,StudentMember,IEEE,EmreTelatar,Fellow,IEEEAbstractWestudyadiscrete-timemodelwhereeachpackethasacostofnotbeingsentthiscostmightdependonthepacketcontent.Westudythetradeoffbetweentheageandthecostwherethese...

展开>> 收起<<

1 Optimal Policies for Age and Distortion in a Discrete-Time Model.pdf

共34页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Optimal Policies for Age and Distortion in a Discrete-Time Model

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: