1
Version-Aware Communication in Multi-Hop IoT Networks with Feedback
arXiv:2607.04996v1 [cs.NI] 6 Jul 2026
Erfan Delfani and Nikolaos Pappas, Senior Member, IEEE
Abstract—Timely communication of information in Internet of Things (IoT) networks is critical to enhancing system performance and energy efficiency by minimizing the transmission of outdated or redundant data. Although timeliness metrics such as the Age of Information (AO I) effectively quantify information freshness, they do not account for content evolution. The Version Age of Information (VAO I) addresses this gap by tracking version lag at the receiver, thereby providing a practical content-aware metric. However, prior research has primarily focused on firstmoment analyses in single-hop settings, leaving the distributional properties of VAO I in multi-hop networks, as well as the impact of feedback mechanisms, unexplored. In this study, we provide a comprehensive characterization of VAO I in multi-hop networks with transmission constraints and acknowledgment-based feedback. A bi-level optimization framework is formulated to jointly optimize the update policy of a rate-constrained source and the feedback-aware forwarding policies of the intermediate nodes, aiming to minimize communication overhead while maintaining VAO I performance at the destination. We show that the optimal source policy follows a threshold-based update strategy and derive the optimal threshold in closed form. For both the optimal threshold policy and a randomized baseline, we obtain closedform expressions for the stationary distribution and average VAO I, along with the corresponding update rates across network nodes under feedback-aware forwarding. Numerical results corroborate the analytical findings and illustrate the advantages of utilizing VAO I and feedback to reduce redundant transmissions while preserving data freshness and informativeness in multi-hop systems.
I. I NTRODUCTION Efficient data management is critical for ensuring optimal performance in communication networks across diverse scenarios, ranging from single-hop IoT monitoring systems to multi-hop satellite communication networks. As the volume of data generated by network nodes increases, transmitting all data indiscriminately without considering its semantic significance or task relevance becomes increasingly impractical and unsustainable. Such an approach leads to excessive consumption of critical resources, including energy and bandwidth, ultimately degrading system performance. To address these challenges, there is an urgent need for network management approaches that dynamically optimize data transmission by leveraging semantic metrics to deliver the most timely and informative data within a constrained transmission frequency [2], [3]. This requires a shift from The authors are with the Department of Computer and Information Science at Linköping University, Sweden, email: {erfan.delfani, nikolaos.pappas}@liu.se. This work has been supported in part by the Swedish Research Council (VR), ELLIIT, and the European Union (ELIXIRION, 101120135, 6G-LEADER, 101192080, and SOVEREIGN, 101131481). A shorter version has been published in [1].
traditional passive, semantics-agnostic communication toward active, goal-oriented, semantics-aware approaches. The Age of Information (AO I) [4] is a widely used metric that quantifies the freshness or timeliness of information in status update systems, defined as the time elapsed since the generation of the most recently received data. AoI-aware scheduling minimizes staleness by adapting transmissions to source data arrivals and network service times [5]. However, AO I captures freshness solely through data timestamps, without accounting for actual changes in the source content. As a result, simply refreshing timestamps may fail to deliver new information, and avoiding such redundant updates can reduce transmission and energy consumption. To address this limitation, content-based metrics such as Age of Incorrect Information (AO II) [6] and Version Age of Information (VAO I) [7] have been introduced. AO II adds a distortion-aware dimension by measuring the staleness of incorrect information, specifically when the receiver’s content deviates from the source, unlike AO I, which treats correct and incorrect data uniformly. However, AO II requires precise knowledge of the information state at both the source and destination for comparison, which is practical only when the state space is small, fully modeled, and all state transitions are known. In many real-world applications, such complete knowledge may not be available. In such cases, VAO I provides a more practical content-based metric by focusing solely on content changes at the source, where data evolve through successive, non-reverting versions. This requires only minimal knowledge: at any given time, either a new or a previous version exists, and the receiver must track these versions as timely as possible. Defined as the number of versions by which the receiver lags behind the source, VAO I further improves upon AO I by replacing timestamps with version numbers, thereby eliminating the challenging requirement of clock synchronization between the transmitter and receiver [8]. It is computed simply by comparing the receiver’s stored version with the source’s current version. While these metrics have attracted considerable attention, most existing research has focused primarily on single-hop communication setups and on first-moment analyses, i.e., average values. In contrast, there remains a notable gap regarding multi-hop communication scenarios and the analysis of the full distributions of these metrics, particularly VAO I. Such analyses are essential for a deeper understanding of system behavior and for enabling more effective optimization, especially in resource-constrained IoT systems. Another mechanism for improving the efficiency of
2
data communication networks is the provision of reliable and prompt acknowledgment feedback upon data delivery. Feedback-enabled networks facilitate active, closed-loop decision-making at transmitting nodes, enabling more efficient data transmission and the delivery of the most timely and informative data [9], [10]. This feedback mechanism is particularly important in multi-hop networks. Whereas a lack of feedback in single-hop links affects only one transmitter, in multi-hop networks it causes a cascade of redundant retransmissions across intermediate nodes, wasting network resources without providing any benefit. Investigating the impact of feedback on communication overhead in multi-hop networks while preserving information semantics, specifically VAO I, is another direction that warrants further exploration. In this work, we address these gaps by considering VAO Iaware and feedback-enabled communication approaches, in contrast to VAO I-agnostic and feedback-disabled approaches, in a multi-hop setup to enable efficient data delivery under source transmission rate constraints. VAO I-aware communication improves network efficiency by prioritizing the transmission of fresh and informative data. When network resources are limited, this approach reduces transmissions of stale or redundant information, thereby conserving resources and enabling timely and informative updates. When resource constraints are relaxed, VAO I-aware communication maintains data freshness and informativeness while reducing unnecessary resource consumption by filtering redundant transmissions. We consider these advantages in a multi-hop network consisting of a rate-constrained source node (node 0), a sequence of N intermediate relay nodes (nodes 1, 2, . . . , N ) with no strict rate constraints, and a destination node (node N + 1). The source node determines its transmission or update policy, denoted by ϕ, to optimize the timeliness and informativeness of the data at the destination node, as captured by VAO I. Each intermediate node i ∈ {1, 2, . . . , N } adopts a relaying or forwarding policy θi , whose primary objective is to reliably deliver all received data versions to the destination, thereby optimizing the VAO I at node N +1. As a secondary objective, each forwarding policy also seeks to minimize communication overhead. The resulting problem naturally leads to a bi-level optimization problem: Upper-Level (VAO I Optimization): The network nodes optimize the VAO I at the destination subject to a transmission rate constraint at the source. All intermediate nodes are assumed to employ an ideal always-update forwarding policy, thereby establishing a baseline for the best achievable VAoI at the destination. • Lower-Level (Update Rate Optimization): Given the optimal source policy ϕ∗ obtained from the upper-level problem, the objective is to minimize the transmission rates of the intermediate nodes while preserving the best achievable VAO I at the destination. To reduce communication overhead, intermediate nodes use acknowledgment (ACK) feedback from downstream nodes to suppress redundant retransmissions once the latest data version has been successfully delivered, following a feedback-aware (or VAO I-aware) policy. •
Thus, the upper-level optimization determines the optimal update policy for the rate-constrained source, e.g., an IoT device, while the lower-level optimization determines the minimum update/forwarding rates under a feedback-aware policy at the intermediate nodes, e.g., a network operator. The formal problem formulation is presented in Section II-C. A. Main Contributions The main contributions of this study are as follows: • We analyze the VAO I evolution at the nodes of a multihop network under a general update policy ϕ at a rateconstrained source, assuming an always-update forwarding policy at intermediate nodes. • We formulate a bi-level optimization problem that first characterizes the best achievable VAO I under a sourcerate constraint with always-update forwarding, and then determines the minimum update rates at intermediate nodes under a feedback-aware forwarding policy while preserving this VAO I. ∗ • We show that the optimal source update policy, ϕ , is a threshold policy and derive the optimal threshold in closed form. • We derive closed-form expressions for the stationary distribution and average VAO I at network nodes under two source policies: the optimal (version-aware) threshold policy ϕ∗ and a randomized stationary policy ϕR , serving as a version-agnostic baseline. • We derive closed-form expressions for the update rates at network nodes under a feedback-aware forwarding policy for both threshold and randomized source policies. • We validate the analytical results via simulations and investigate the behavior of VAO I and update rates in the multi-hop network. B. Related Works The literature on information freshness and semantic metrics can be broadly categorized by network topology and depth of analysis. For single-hop setups, existing research has primarily focused on first-moment or average analysis. Several studies have investigated the distributions of AO I and Peak AO I (PAO I) in continuous-time systems using queueing theory [11]–[21], while others have considered discrete-time settings [22]–[26]. Notably, [22] derives general expressions for the stationary distributions and generating functions of AO I and PAO I in discrete-time single-server queues under various disciplines, together with methods for nonlinear age functions. Extending stochastic hybrid system techniques, [23] models AO I and packet age as a two-dimensional Markov process in bufferless queues with Bernoulli arrivals. A matrix-analytic quasi-birth–death framework is proposed in [24] to obtain exact per-source AO I and PAO I distributions in multi-source IoT systems with phase-type service times. The study in [25] investigates age-optimal scheduling with delayed feedback and long-term constraints, providing closed-form benchmarks for random and deterministic policies, while [26] analyzes AO I and PAO I in multi-source Ber/Geo/1/1 systems under preemptive and non-preemptive policies.
3
For content-based metrics, several works have examined the distribution of AO II [6], [27], [28]. Specifically, [6] derives stationary AO II distributions for symmetric multi-state Markov sources under always-update and threshold policies. [27] studies AO II in slotted systems with random delays for two-state Markov sources under threshold policies. Using DTMC analysis, [28] derives stationary AO II and AO IV distributions for two-state Markov sources under given transmission policies. AO CI was introduced in [29], which derives optimal thresholds that minimize a weighted sum of AO CI and update cost. Stationary VAO I distributions for energyharvesting systems are modeled in [30] using DTMCs with stochastic energy arrivals and threshold-based transmissions, while [31] analyzes VAO I in NOMA fading broadcast channels with random version arrivals and power constraints. Although these studies provide valuable insights into the behavior of freshness metrics, they are limited to single-hop configurations. In multi-hop networks, most existing studies on two-hop [32]–[34] and general multi-hop settings [35]–[45] predominantly focus on analyzing or optimizing average freshness metrics, particularly AO I, while largely neglecting contentaware metrics such as VAO I, as well as the characterization of the full distributional behavior. A small subset of prior work goes beyond this focus. [46] derives the distribution of discrete-time AO I in N -hop systems with time-invariant packet loss via recursive methods, while [47] investigates the distributions of AO I and PAO I in continuous-time two-hop networks. However, these studies remain centered on AoIbased metrics and do not extend to content-aware measures such as VAO I. More recently, [48] studies VAO I in multi-hop satellite networks under an always-update forwarding policy. Nevertheless, this work does not account for update rates at intermediate relaying nodes, nor does it investigate the role of feedback mechanisms, which are crucial for efficient closedloop operation and reducing redundant retransmissions and communication overhead in multi-hop topologies. Overall, the current literature reveals a clear gap in the joint analysis of multi-hop communication, feedback-enabled control, and the full distributional behavior of content-based freshness metrics such as VAO I. Addressing this gap is essential for understanding the cascading effects of feedback in multihop systems and for designing resource-efficient policies that preserve information semantics under network constraints. Unlike the aforementioned works, this paper jointly addresses multi-hop VAoI optimization, stationary distribution analysis, and feedback-aware forwarding under source transmission constraints. II. S YSTEM M ODEL AND F ORMULATION We consider a multi-hop line network designed for the communication of status updates from a source node to a destination through a sequence of intermediate relay nodes. The network consists of N + 2 nodes indexed by i ∈ {0, 1, . . . , N + 1}, where node 0 represents the source and node N + 1 denotes the final destination. Nodes 1, . . . , N act as intermediate forwarding nodes that relay updates toward
Δ3
Δ2
Δ1
Δ𝑁−1 Δ𝑁
𝑎1 𝑝1
𝑎2 𝑝2
𝑝0 𝑎0
𝑎𝑁−1
𝑝𝑁−1 𝑎𝑁 𝑝𝑁
Δ𝑁+1
Δ0
Fig. 1: System model of a multi-hop network.
the destination over unreliable communication links. A representative real-world scenario is illustrated in Fig. 1, where a remote energy-limited IoT device (node 0) samples updates from an information source, such as a physical process, and transmits the resulting update packets to a distant ground node (node N + 1). The updates are delivered through N hop communication via a sequence of Low Earth Orbit (LEO) satellites that serve as intermediate relay nodes. In this model, the source node is assumed to be energy-constrained and, therefore, has limited transmission capability. The intermediate nodes are assumed to have no strict resource constraints and aim to deliver data from the source to the destination as reliably as possible while minimizing communication overhead. In all analyses, we consider a slotted (discrete-time) system indexed by t = 0, 1, 2, . . . . The details of the system model are described below. 1) Communication Links Forward links: In this setup, at the beginning of each time slot and in accordance with the update policies outlined in Sec. II-A, each node may attempt to transmit an update to its next-hop node. The completion of each transmission occupies exactly one time slot. Accordingly, updates propagate through the network via hop-by-hop transmissions over unreliable links. The communication link between node i and node i+1 is modeled as a packet erasure channel. Specifically, when node i attempts a transmission during time slot t, the transmission succeeds with probability (w.p.) pi , and consequently, fails (i.e., is dropped) w.p. ϵi = 1 − pi . We define the channel success indicator as: hi (t) ∼ Bernoulli(pi ),
i ∈ {0, 1, 2, . . . , N },
(1)
where hi (t) = 1 indicates that a transmission from node i to node i + 1 at time slot t is successful, and hi (t) = 0 otherwise. Channel outcomes are assumed to be independent across both time slots and different links. Moreover, each node is assumed to maintain a buffer capable of storing a single update. The buffer always retains the most recently received update (version), discarding any older updates upon the arrival of a new one. Backward (feedback) links: For the feedback-aware policy, we consider feedback links to acknowledge the successful delivery of updates within the network. In particular, when enabled, node i+1 sends an ACK to node i upon receiving an update from that node. We assume that ACKs from receivers to transmitters are instantaneous and error-free, as sufficient
4
TABLE I: Update policies and Feedback Requirements Scenarios
Policies (ϕ, θ)
Fig. 2: Order of events at the network nodes.
Fig. 3: Order of events at the source node.
resources can be allocated to ensure the reliable delivery of these small ACK packets. 2) Update and Version Generation The source node 0 continuously monitors the information source and generates a status-update packet in each discrete time slot. However, not every update necessarily contains a new version of the information. We assume that the generation of a new version is modeled as an independent and identically distributed (i.i.d.) Bernoulli process with probability pg . This stochastic model effectively captures the evolution of the information source over the long term. The version generation process at the source is described by: w(t) ∼ Bernoulli(pg ),
(2)
where w(t) = 1 indicates that a new version is generated in time slot t, and w(t) = 0 otherwise. Given this version generation process, the version index at the source node, denoted by V0 (t), evolves according to V0 (t + 1) = V0 (t) + w(t). 3) Temporal Order of Events The system follows a temporal ordering within each time slot. Transmission attempts occur at the beginning of the slot after observing the current state of the system, while channel outcomes and packet receptions are determined during the slot (see Fig. 2). Moreover, the generation of a new version at the source is completed at the end of the slot (see Fig. 3). Under this timing structure, if node i receives a new version during slot t, it can start forwarding that version at the beginning of slot t + 1. A. Update Policies and ACK Feedback 1) Update Policy at the Source The transmission behavior of the source node is characterϕ ized by an update policy ϕ = {aϕ0 (t)}∞ t=0 , where a0 (t) ∈ ϕ {0, 1}. In particular, a0 (t) = 1 indicates that the source transmits its current update at time t, whereas aϕ0 (t) = 0 indicates that the source remains idle. This policy must satisfy an update rate constraint imposed by the resource limitations at the source. We define here (and use throughout the paper) two classes of stationary policies for the source: • Threshold policy: Under a threshold policy ϕT , the source transmits only when the VAO I at node 1, ∆ϕ1 T (t), reaches or exceeds a threshold ∆T : n o aϕ0 T (t) = 1 ∆ϕ1 T (t) ≥ ∆T , where 1{·} is the indicator function. This policy requires ACK feedback from node 1, which enables the source to calculate ∆ϕ1 T (t) and compare it with ∆T . • Randomized policy: Under a randomized policy ϕR , the source transmits independently in each time slot with
1: Version-aware, no feedback 2: Version-aware, feedback enabled 3: Version-agnostic, no feedback 4: Version-agnostic, feedback enabled
(ϕT , θ AU ) (ϕT , θ FA ) (ϕR , θ AU ) (ϕR , θ FA )
Variables ACK from ACK from ¯ ϕ,θ node 1 node i ≥ 2 η̄iϕ,θ , ∆ i ¯ ϕT 1, ∆ ✓ ✗ i ϕT ¯ ϕT η̄i , ∆i ✓ ✓ ϕR ¯ 1, ∆i ✗ ✗ ϕR ¯ ϕR η̄i , ∆i ✗ ✗
probability ψ, i.e., P aϕ0 R (t) = 1 = ψ. This policy is version-agnostic and does not require feedback from node 1. 2) Forwarding Policy at the Intermediate Nodes Intermediate nodes, which are not rate-constrained, adapt their forwarding policies to maximize update delivery based on ACK feedback. If feedback is absent, intermediate nodes transmit continuously in each time slot, as they are unaware of previous successes. We call this policy always-update and AU AU denote it by θ AU = θ1:N = {θ1AU , θ2AU , . . . , θN }. If feedback is available, we define two policies: VAO I-aware and feedbackVA FA aware, denoted by θ VA = θ1:N and θ FA = θ1:N , respectively. According to the VAO I-aware policy, an intermediate node keeps transmitting until its VAO I is lower than that of the subsequent node, i.e., until its latest version has been delivered to the next node: n o VA ϕ,θ VA ϕ,θ VA aϕ,θ (t) = 1 ∆ (t) < ∆ (t) , i i i+1
i ∈ {1, 2, . . . , N }.
Under the feedback-aware policy, a node remains idle only when its stored update has been successfully delivered and no newer update has arrived, ensuring persistent retransmissions until success, irrespective of VAO I. Formally, for node i ∈ {1, 2, . . . , N } at time t + 1: n o n o FA FA ϕ,θ FA aϕ,θ (t + 1) = aϕ,θ (t) 1−hi (t) , i i−1 (t)hi−1 (t) ∨ ai where ∨ denotes the logical OR operator. Remark: The feedback-aware policy is version-agnostic and differs from the VAO I-aware forwarding policy. Specifically, under a feedback-aware policy, the same version may be received multiple times and is forwarded upon each reception. In contrast, a VAO I-aware policy avoids retransmissions by preventing a previously delivered version from being transmitted again. However, when each received update from the source corresponds to a distinct new version, for example, under the threshold policy ϕ = ϕT with ∆T > 0 at the source, as considered in this paper, the two policies become identical. Consequently, the feedback-aware and VAO I-aware forwarding policies coincide when the source operates under a threshold policy, and for notational convenience, we may therefore use θ FA to also represent θ VA in this case. These policies naturally cover four scenarios with respect to version awareness and feedback availability at intermediate nodes, as summarized in Table I.
5
TABLE II: Notation and Variable Descriptions
Fig. 4: Evolution of VAO I within the network over time.
B. Metrics: Update Rate and VAoI Let us define the cumulative number of transmissions by node i ∈ {0, 1, 2, . . . , N } up to time t as ηiϕ,θ (t) ∈ N0 , given by: ηiϕ,θ (t + 1) = ηiϕ,θ (t) + aϕ,θ i (t),
(3)
where ηiϕ,θ (0) = 0, N0 denotes the set of non-negative integers, i.e., N0 = {0, 1, 2, . . . }, and ϕ and θ denote the update and forwarding policies adopted at the source and intermediate nodes, respectively. Then, the average number of transmissions, or update rate, at node i is defined as follows: "T −1 # i X ϕ,θ 1 1 h ϕ,θ ϕ,θ E ηi (T ) = lim E ai (t) . (4) η̄i = lim T →∞ T T →∞ T t=0 The VAO I at node i under policy (ϕ, θ), denoted by ∆ϕ,θ i (t), is defined as the number of versions by which node i lags behind the source node 0: ϕ,θ ∆ϕ,θ (t), i (t) = V0 (t) − Vi
Variable
Description
t i, n N w(t), pg Vi (t) hi (t) pi , ϵ i σi (t)
Discrete time index Network node indices Number of intermediate (relaying) nodes Version generation process and its probability Version index at node i at time t Success indicator of link i → i + 1 Success and erasure probabilities of link i → i + 1 Successful arrival process at node i
ϕ θi ϕT , ∆ T ϕR , ψ
Update policy at source node 0 Update policy at node i Threshold policy and its VAO I threshold Randomized policy and its transmission probability
aϕ i (t), ai ∆ϕ i (t), δi ¯ϕ ∆ i ηiϕ (t), η̄iϕ ϕ π∆ (δi )
Update action process and its value at node i VAO I process and its value at node i Average VAO I at node i under policy ϕ Cumulative updates and update rate at node i Stationary distribution of VAO I at node i
πaϕi (ai )
Stationary distribution of update action at node i
i
C. Problem Formulation Our goal is to minimize VAO I at the destination node while satisfying the rate constraint at the source and minimizing the communication overhead at the intermediate nodes. This problem is formulated as a bi-level optimization problem, where the upper-level problem determines the optimal source policy ϕ∗ , and the lower-level problem determines the optimal update rates at the intermediate nodes under the optimal ∗ ∗ }. The biforwarding policies θ ∗ = θ1:N = {θ1∗ , θ2∗ , . . . , θN level optimization problem is formally defined as follows: P1 : VAO I Optimization AU
(7)
subject to η̄0ϕ ≤ ψ
(8)
ϕ∈Φ
(5)
where V0 (t) denotes the current version at the source node 0, and Viϕ,θ (t) denotes the version stored at node i. The average VAO I at node i under policy (ϕ, θ), is defined as follows: "T −1 # X ϕ,θ 1 ϕ,θ ¯ ∆i = lim E ∆i (t) . (6) T →∞ T t=0
¯ ϕ,θ min ∆ N +1
AU where θ AU = θ1:N is the always-update forwarding policy, and the optimal policy at the source and the optimal VAO I at the ∗ AU ¯ ϕ ,θ , respectively. destination are denoted by ϕ∗ and ∆ N +1
P2 : Update Rate Optimization o n ∗ ∗ ϕ∗,θ min η̄1ϕ ,θ , η̄2ϕ ,θ , . . . , η̄N θ
Fig. 4 illustrates a sample evolution of VAO I in a two-hop network. The source generates new versions at time slots 0, 2, 3, 6, and 8, and its version index V0 (t) increases by one at the beginning of each subsequent time slot. The versions at node 1, denoted by V1ϕ (t), are updated according to the update policy and the transmissions from node 0, i.e., ϕ. If a transmission at time t is successful, then V1ϕ (t + 1) = V0 (t); otherwise, V1ϕ (t + 1) = V1ϕ (t). The corresponding VAO I, ∆ϕ1 (t) = V0 (t) − V1ϕ (t), is listed in parentheses in the second row of the table and plotted in blue. Similarly, node 2 stores the versions V2ϕ,θ (t) received from node 1, which are transmitted in every slot in this example. In this case, V2ϕ,θ (t+1) = V1ϕ (t) if the transmission at time t is successful; otherwise, V2ϕ,θ (t + 1) = V2ϕ,θ (t). The VAO I at node 2, ϕ,θ ∆ϕ,θ (t), is shown in parentheses in the third 2 (t) = V0 (t)−V2 row of the table and plotted in green in Fig. 4.
∗
∗
(9)
AU
¯ ϕ ,θ = ∆ ¯ ϕ ,θ subject to ∆ N +1 N +1
(10)
where θ = θ1:N = {θ1 , θ2 , . . . , θN }. This is a multi-objective optimization problem, for which the optimal solution, in the absence of feedback mechanisms, is the always-update policy. When ACK feedback is available at the intermediate links, the optimal forwarding policy is a VAO I-aware policy, whereby each node i transmits until the successful delivery of its currently stored version, i.e., θ ∗ = θ VA . Notation remark: For the average update rate, we omit the superscript θ in η̄iϕ,θ . This is without loss of generality since, under the always-update policy at intermediate nodes, AU η̄iϕ,θ = 1. Hence, when analyzing update rates at intermediate nodes, we restrict attention to the policy θ FA and drop the superscript for notational simplicity. Similarly, we omit ¯ ϕ,θ since, under all considered policies the superscript θ in ∆ i
6
θ AU , θ VA , and θ FA , intermediate nodes forward all received versions. While the number of forwarded updates may differ across policies, the resulting VAO I is unchanged. The adopted notation conventions are summarized in Table I. For further simplicity, we also omit the superscript ϕ from aϕi (t) and ∆ϕi (t) in sections where the analysis applies to general source update policies, i.e., independently of the specific choice of ϕ. Moreover, we define p̄g = 1 − pg and p̄i = 1 − pi , for i = 0, 1, 2, . . . , N . A comprehensive list of notations is provided in Table II.
We analyze the objective function of P1 and derive an ¯ N +1 , as expression for the VAO I at the destination node, ∆ ¯ 1 . To a function of the VAO I at the first intermediate node, ∆ begin, we show that the VAO I at each node can be expressed in terms of the VAO I at the preceding node. Proposition 1. The VAO I at node i+1 is given by: i = 1, 2, . . . , N,
(11)
where mi is a Geometric Random Variable (RV) with parameter pi , and ξmi | mi is a Binomial RV with parameters mi and pg : P(mi = ℓ) = (1−pi )ℓ−1 pi , ℓ = 1, 2, . . . . (12) k r P(ξmi = r | mi = k) = B(r; k, pg ) = p (1 − pg )k−r , r g r = 0, 1, . . . , k. (13) Proof. The proof is provided in Appendix A. Lemma 1. The VAO I at the destination node is given by: ∆N +1 (t) = ∆1 (t − τN ) + βN , (14) PN PN where τN = i=1 mi and βN = i=1 ξmi are two RVs with PN PN expected values E [τN ] = i=1 p1i and E [βN ] = pg i=1 p1i . Proof. The proof is provided in Appendix B. The variable τN is the relaying delay of each version from node 1 to node N + 1 through N relaying nodes, while βN represents the number of version generations at the source during this delay. Theorem 1. The average VAO I of the destination node which is N + 1 hops away from the source is given by: ¯ N +1 = ∆ ¯ 1 + pg ∆
N X 1 i=1
pi
.
¯ϕ min ∆ 1
(16)
subject to η̄0ϕ ≤ ψ
(17)
ϕ∈Φ
Next, we demonstrate that the optimal on-off policy at the source for optimizing the VAO I at node 1, under an update rate constraint, is a threshold policy. Lemma 2. The optimal on-off scheduling policy for problem P1′ is a threshold policy. Proof. The proof is provided in Appendix D.
III. VAO I O PTIMIZATION
∆i+1 (t) = ∆i (t − mi ) + ξmi ,
P1′ : VAO I Optimization for Node 1
(15)
Proof. The proof is provided in Appendix C. Equation (15) shows that each additional node contributes an additive expected VAO I penalty proportional to its expected relaying delay. According to Theorem 1, the VAO I optimization problem P1 for the destination node is transformed into a VAO I optimization problem at the first intermediate node, as follows:
Therefore, the optimal update policy at the source for solving the VAO I optimization problem P1 is a threshold policy, i.e., ϕ∗ = ϕ∗T . In the next subsection, we derive the closed¯ ϕT and η̄ ϕT , and solve the problem P ′ form expressions for ∆ 1 0 1 to obtain the optimal threshold ∆∗T in closed form. We also derive the complete stationary distribution of the VAO I and the update rates for node 1 and the other network nodes under the version-aware communication policies (ϕT , θ VA ). A. Analysis of ∆ϕ1 T and η̄0ϕT Under a threshold policy ϕT , node 0 controls the transmission actions aϕ0 T (t) ∈ {0, 1} based on the VAO I at node 1 relative to a threshold ∆T : aϕ0 T (t) = 1{∆ϕ1 T (t) ≥ ∆T }. Under this policy, the evolution of ∆ϕ1 T (t) is independent of the actions of other nodes and is fully characterized by aϕ0 T (t) and the system processes, including w(t) and h0 (t). Hence, ∆ϕ1 T (t) can be modeled as a DTMC, and its marginal ϕT stationary distribution, denoted by π∆ (δ1 ), gives the long-run 1 probability of being in state δ1 ∈ N0 . It is obtained from the balance equations: X ϕT ϕT π∆ (δ1 ) = P(δ1 |δ1′ ) π∆ (δ1′ ), (18) 1 1 δ1′ ∈N0 ϕT with δ1 ∈N0 π∆ (δ1 ) = 1, where P(δ1 |δ1′ ) is the transition 1 probability from ∆ϕ1 T (t) = δ1′ to ∆ϕ1 T (t + 1) = δ1 . The average VAO I at node 1 and the update rate at node 0 then follow from this distribution as: h i X ϕT ¯ ϕT = E ∆ϕT (t) = ∆ δ1 π∆ (δ1 ), (19) 1 1 1
P
δ ∈N
η̄0ϕT = E
1 0 h i X ϕ aϕ0 T (t) = P(∆ϕ1 T (t) ≥ ∆T ) = π∆T1 (δ1 ). (20)
δ1≥∆T
The VAO I at node 1, ∆ϕ1 T (t), measures the difference between the version index available at node 1 and the version at the source. Its dynamics are governed by version generation at node 0 and transmissions over the erasure channel. In each slot t, the source generates a new version with probability pg , following the Bernoulli process w(t) ∈ {0, 1}. Node 0 transmits its current version, which is successfully received with probability p0 . The VAO I evolution depends on these two processes. If node 1 successfully receives an update at time t, its buffer is refreshed to the source’s current version and the VAO I resets as ∆ϕ1 T (t+1) = w(t). Otherwise, the VAO I is carried over and
7
may increase due to new version generation, i.e., ∆ϕ1 T (t+1) = ∆ϕ1 T (t) + w(t). Thus, the VAO I remains unchanged if no new version is generated (w(t) = 0), and increases by one if a new version is generated (w(t) = 1), provided that node 1 does not receive a successful update. Proposition 2. The steady-state probability of the VAO I at node 1 under a threshold policy with threshold ∆T is given by the following: • For ∆T ∈ {0, 1}: p̄g p0 , δ1 = 0, αT ϕT π∆1 (δ1 ) = pg p0 h pg p̄0 iδ1 −1 (21) 2 , δ1 ≥ 1. αT α
p
g where f (∆T ) = (∆T −1)p for ∆T ≥ 1, and f (0) = 1. 0 +αT
Proof. The proof is provided in Appendix G. The resulting optimal average VAO I at node 1 under the mixed threshold policy is given by: i i h h ∗ ¯ ϕT ¯ϕ = κ ∆ ¯ ϕT , (29) + (1 − κ) ∆ ∆ 1 1 1 ∗ ∗ ∆T =∆T −1
∆T =∆T
h
¯ ϕT where ∆ 1
i
h
¯ ϕT and ∆ 1
∆T =∆∗ T
to ∆∗T
i
(23) by setting ∆T resulting optimal VAO I at the destination node N + 1 is then given by (15) as follows:
T
•
For ∆T ≥ 2: p̄g p0 , δ1 = 0, 0 +αT (∆T −1)p p 0 ϕT 1 ≤ δ 1 < ∆T , π∆ (δ1 ) = (∆T −1)p0 +αT , 1 δ1−∆T pg π ϕT (∆ −1) pg p̄0 , δ1 ≥ ∆ T , T αT ∆1 αT (22)
where αT = 1 − p̄g p̄0 .
are obtained from
∆T =∆∗ T −1 and ∆∗T − 1, respectively. The
∗
∗
¯ϕ ¯ϕ ∆ N +1 = ∆1 + pg
N X 1 i=1
pi
.
(30)
This is the optimal solution to problem P1 , representing the best achievable VAO I ∗at the destination node, as well as ∗ ¯ϕ ¯ ϕ + pg Pn 1 , for n ∈ at all network nodes: ∆ = ∆ n+1 1 i=1 pi {1, 2, . . . , N }. We now derive the VAO I at the network nodes; specifically, we obtain the distribution of the VAO I for nodes 2, 3, . . . , N + 1.
Proof. The proof is provided in Appendix E. Lemma 3. The average VAO I at node 1 and the update rate at node 0 under a threshold policy with threshold ∆T ≥ 1 are given by: ¯ ϕT = 1 (∆T −1)∆T p0 + pg , ∆ 1 2 (∆T −1)p0 + αT p0 pg ϕT η̄0 = , (∆T − 1)p0 + αT
(23)
ℓ=1
=
It is evident that ∆T = 0 results in an always-update policy ¯ ϕT = pg and η̄ ϕT = 1. Using Lemma 3, at node 0, where ∆ 1 0 p0 the optimization problem P1′ can be reformulated as follows: ′′
P1 : VAO I Optimization for Node 1
subject to
1 (∆T −1)∆T p0 pg + 2 (∆T −1)p0 + αT p0 pg ≤ψ (∆T − 1)p0 + αT
ϕ P(mi = ℓ)P(ξmi = r | mi = ℓ)π∆ (δ − r), i
(26)
Theorem 2. The optimal threshold policy that minimizes the average VAO I at the network under the rate constraint at the source is a randomized mixture of two threshold policies with thresholds ∆∗T and ∆∗T − 1, applied with probabilities κ and 1 − κ, respectively. The optimal threshold is: & ' pg 1 ∗ ∆T = − 1 + p0 , (27) p0 ψ and the corresponding mixing probability κ is: f (∆∗T −1) − ψ , f (∆∗T −1) − f (∆∗T )
for i ∈ {1, 2, . . . , N } and a source update policy ϕ, where ⊛ denotes the convolution operator. Proof. The proof is provided in Appendix H. ϕ Given π∆ (δ1 ) under the adopted policy ϕ at the source, 1 the VAO I distribution at the remaining network nodes can be derived recursively.
(25)
where its solution is obtained in the following theorem.
κ=
ℓ ∞ X X ℓ=1 r=0
Proof. The proof is provided in Appendix F.
min
Theorem 3. The stationary distribution of the VAO I at node i + 1 is given by: ∞ h i X ϕ ϕ π∆ (δ) = P(m = ℓ) B(δ; ℓ, p ) ⊛ π (δ) (31) i g ∆ i+1 i
(24)
where αT = 1 − p̄g p̄0 .
∆T ∈N
B. Distribution of {∆ϕi }N i=2
(28)
IV. VAO I- AWARE U PDATE R ATES U NDER (ϕT , θ VA ) In this section, we derive the update rates at the network nodes for problem P2 , under a threshold policy ϕT with an arbitrary threshold ∆T ≥ 1 at the source (where ϕ∗ is a special case corresponding to the optimal policy) and a VAO I-aware policy θ VA at the intermediate nodes, which results in the best achievable VAO I at the destination. A. Analysis of η̄1ϕT Theorem 4. The update rate at node 1 under (ϕT , θ1VA ) is given by: p0 p0 Θ∆T (32) η̄1ϕT = 1− η̄0ϕT , p1 1 − p̄0 p̄1 p p̄
where Θ = 1−gp̄g1p̄1 .
8
ϕ
ϕ
Fig. 5: Markov Chain of (∆1 T , a1 T ) under (ϕT , θ VA ).
Proof. The update rate η̄1ϕT = E[aϕ1 T ] = P(aϕ1 T = 1) is obtained by deriving the stationary distribution of the joint ϕT variables (∆ϕ1 T , aϕ1 T ), denoted by π(∆ (δ1 , a1 ), which is 1 ,a1 ) obtained from a 2-D DTMC in Fig. 5. The details of the proof are provided in Appendix I.
B. Analysis of forwarding rates {η̄iϕT }N i=2 We propose an iterative algorithm to derive the transition probabilities of the state vector xn = ∆1 , a1 , a2 , . . . , an , n ∈ {1, 2, 3, . . . , N }. The action at each node is independent of the subsequent nodes; therefore, we can factorize the transition probability as: P x′n+1 | xn+1 = P x′n , a′n+1 | xn , an+1
(33)
= P (x′n | xn ) P a′n+1 | x′n , xn , an+1 = P (x′n | xn ) Kxn →x′n a′n+1 | an+1 ,
where we have defined the kernel function Kxn →x′n a′n+1 | an+1 = P a′n+1 | x′n , xn , an+1 as the transition probability of the action at node n + 1 from an+1 to a′n+1 , given that the previous nodes transition from xn to x′n . This kernel can be derived by introducing a variable σn+1 ∈ {0, 1} that captures the successful arrival of an update (n+1) at node n+1. We define a parameter ρxn →x′n as the probability that σn+1 equals 1 when the previous nodes transition from (n+1) xn to x′n , i.e., ρxn →x′n = P(σn+1 = 1 | x′n , xn ). This probability can be expressed recursively as follows: 0 (n+1) ρxn →x′n = 1 p ρ(n) i−1 xn−1 →x′
n−1
an = 0, a′n ∈ {0, 1}, an = 1, a′n = 0, (34) an = 1, a′n = 1.
with the following initialization, where x0 = ∆1 : ( (1) ρx0 →x′ = 0
1 ∆1 ≥ ∆T , ∆′1 ≤ 1, 0 otherwise.
(35)
By conditioning on whether there is an arrival to node n+1, i.e., σn+1 , the kernel function is derived as follows: K xn →x′n a′n+1 | an+1 (36) (n+1) ′ ′ = 1 − ρxn →x′n P an+1 | xn , xn , an+1 , σn+1 = 0 (n+1) + ρxn →x′n P a′n+1 | x′n , xn , an+1 , σn+1 = 1 (n+1) 1 − ρxn →x′n an+1 = 0, a′n+1 = 0, (n+1) ρx →x′ an+1 = 0, a′n+1 = 1, n n = (n+1) pi 1 − ρxn →x′n an+1 = 1, a′n+1 = 0, 1 − pi 1 − ρ(n+1) ′ an+1 = 1, a′n+1 = 1. xn →xn Using this kernel function and starting from x1 = (∆1 , a1 ), whose transition probabilities are known (as depicted in Fig. 5), equation (33) can be computed iteratively to obtain the transition probabilities of the state vector xn , which contains all update actions, as summarized in Algorithm 1. Given the transition probabilities, global P byϕTsolving the ′ balance equations πxϕNT (x′N ) = (x )P(x | xN ) N N x N πx N P subject to the normalization constraint xN πxϕNT (xN ) = 1, the joint stationary distribution πxϕNT (xN ) = ϕT πxN (δ1 , a1 , a2 , . . . , aN ) is obtained. From this, the marginal stationary distribution for any specific node i is derived by summing over all other state variables, P P ϕT specifically πaϕiT (ai ) = δ1 aj̸=i πxN (δ1 , a1 , . . . , aN ). Consequently, rate at node i is calculated as P the update ϕT ϕT ϕT η̄iϕT = a π (a i i ) = πai (1), where πai (ai ) a ai ∈{0,1} i represents the marginal steady-state probability that node i is in state ai ∈ {0, 1}. This procedure is presented in the second part of Algorithm 1 for completeness. V. VAO I AND U PDATE R ATES U NDER (ϕR , θ FA ) In this section, we analyze the VAO I and update rates under version-agnostic policies: the randomized policy ϕR at the source and the feedback-aware policy θ FA at the intermediate nodes. These results serve as a baseline for comparison with the VAO I and update rates obtained under the version-aware policies (ϕT , θ VA ) derived in the previous section.
9
Algorithm 1 Transition Probability Derivation and Stationary Distribution for Multi-hop DTMC under Policies (ϕT , θ VA ) Require: Transition probabilities of (∆1 , a1 ) and system parameters {N, ∆T , pg , p0 , p1 , . . . , pN } 1: Initialize: x1 = (∆1 , a1 ) (1) 2: Initialize: ρx →x′ using equation (35) 0 0 3: for n = 1 to N − 1 do (n+1) 4: Compute ρxn →x′n using equation (34) 5: Compute kernel Kxn →x′n (a′n+1 | an+1 ) using equation (36) 6: Compute the transition probability P(x′n+1 | xn+1 ) using equation (33) where xn+1 = (xn , an+1 ). 7: end for 8: return P(x′n | xn ) for n = 1, 2, . . . , N .
TABLE III: Transition Probabilities for the 2-D DTMC (σ1 , a1 ) y1 = (σ1 , a1 )
y1′ = (σ′1 , a′1 )
Probability P(y1′ |y1 )
(0, 0)
(0, 0) (1, 1)
1 − ψp0 ψp0
(0, 0) (0, 1) (1, 1)
(1 − ψp0 )p1 (1 − ψp0 )(1 − p1 ) ψp0
(0, 1) or (1, 1)
ϕ
Fig. 6: DTMC model of a1 R .
Stationary Distribution and Update Rates C. Analysis of forwarding rates {η̄iϕR }N i=2
1: Solve the global balance equations
P ′ ′ ϕT ϕT (x ) = π x N xN πxN (xN )P(xN | xN ) subject to N P ϕT xN πxN (xN ) = 1 to obtain the joint stationary distribution πxϕNT (xN ). 2: for each node i = 1 to N do 3: ComputePtheP marginal stationary distribution: πaϕiT (ai ) = δ1 aj̸=i πxϕNT (δ1 , a1 , . . . , aN ) 4: Evaluate the node update rate: η̄iϕT = πaϕiT (1) 5: end for ϕ 6: return η̄i T for i = 1, 2, . . . , N . ¯ ϕR and η̄ ϕR A. Analysis of ∆ 1 0 The update rate at the source node under the randomized policy is obtained as follows: h i η̄0ϕR = E aϕ0 R (t) = P aϕ0 R (t) = 1 = ψ. (37) Proposition 3. The stationary distribution and average VAO I at node 1 under a randomized policy with transmission probability ψ are given by: ψp̄g p0 , δ1 = 0, αR ϕR π∆1 (δ1 ) = ψpg p0 h pg (1−ψp0 ) iδ1 −1 (38) 2 , δ1 ≥ 1, αR αR ¯ ϕR = pg , ∆ (39) 1 ψp0 where αR = 1 − p̄g (1 − ψp0 ). Proof. The proof is provided in in Appendix J. ϕR ¯ ϕR , the VAO I distribution and its Given π∆ (δ1 ) and ∆ 1 1 ϕR +1 average at the remaining nodes, namely {π∆ (δi )}N i=2 and i ϕR N +1 ¯ {∆i }i=2 , can be derived using (31) and (15), respectively.
B. Analysis of η̄1ϕR From the DTMC of aϕ1 R depicted in Fig. 6, the distribution and the average update rate at node 1 are obtained as follows: η̄1ϕR = πaϕ1R (1) = 1 − πaϕ1R (0) =
ψp0 . 1 − (1 − ψp0 )p̄1
(40)
We propose an iterative algorithm to derive the transition probabilities of the state vector yn = σ1 , a1 , σ2 , a2 , . . . , σn , an , n ∈ {1, 2, 3, . . . , N }, where σn ∈ {0, 1} indicates whether a successful update arrival occurs at node n. We can factorize the transition probability as follows: ′ ′ P(yn+1 | yn+1 ) = P yn′ , σn+1 , a′n+1 | yn , σn+1 , an+1 ′ = P (yn′ | yn ) P σn+1 , a′n+1 | yn′ , yn , σn+1 , an+1 ′ = P (yn′ | yn ) P σn+1 | yn′ , yn ′ × P a′n+1 | yn′ , yn , σn+1 , σn+1 , an+1 , (41) | {z } σn+1 →σ ′ Ky →y′ n+1 (a′n+1 |an+1 ) n n where the kernels are given as follows: ′ P σn+1 | yn′ , yn (42) ′ 1 σn+1 = 0, an = 0, ′ σn+1 = 1, an = 1, a′n = 0, 1 ′ = 1 σn+1 = 0, an = 1, a′n = 1, σn = 0, ′ 1 − pn σn+1 = 0, an = 1, a′n = 1, σn = 1, p ′ σn+1 = 1, an = 1, a′n = 1, σn = 1. n σn+1 →σ ′ Kyn →yn′ n+1 a′n+1 | an+1 1 1 = pn+1 1 − pn+1
(43) ′ = 1, a′n+1 = 1, σn+1 ′ σn+1 = 0, a′n+1 = 0, an+1 = 0, ′ σn+1 = 0, a′n+1 = 0, an+1 = 1, ′ σn+1 = 0, a′n+1 = 1, an+1 = 1.
Using these kernel functions and starting from y1 = (σ1 , a1 ), whose transition probabilities are given in Table III, equation (41) can be evaluated iteratively to obtain the transition probabilities of the state vector yn , which contains all update actions. The joint stationary distribution πyϕNR (yN ), the marginal distributions πaϕiR (ai ), and the update rates η̄iϕR are then obtained for i = 1, 2, . . . , N , as presented in the second part of Algorithm 2.
10
Algorithm 2 Transition Probability Derivation and Stationary Distribution for Multi-hop DTMC under Policy (ϕR , θ FA )
4.5 4
Require: Transition probabilities of y1 = (σ1 , a1 ) and system parameters {N, ψ, pg , p0 , p1 , . . . , pN } 1: Initialize: y1 = (σ1 , a1 ) 2: Initialize: P(y1′ | y1 ) using Table III 3: for n = 1 to N − 1 do ′ 4: Compute P σn+1 | yn′ , yn using equation (42) σn+1 →σ ′ 5: Compute kernel Kyn →yn′ n+1 a′n+1 | an+1 using using equation (43) ′ 6: Compute the transition probability P(yn+1 | yn+1 ) using equation (41) where yn+1 = (yn , σn+1 , an+1 ). 7: end for ′ 8: return P(yn | yn ) for n = 1, 2, . . . , N . Stationary Distribution and Update Rates P ′ ′ ϕR | yN ) subject to (yN ) = yN πyϕNR (yN )P(yN 1: Solve πy N P ϕR ϕR π (y ) = 1 to obtain π (y ). N N yN yN yN 2: for each node i = 1 to N do P P 3: πaϕiR (ai ) = σ1 ,...,σN aj̸=i πyϕNR (σ1 , a1 , . . . , σN , aN ) 4: Evaluate the node update rate: η̄iϕR = πaϕiR (1) 5: end for ϕ 6: return η̄i R for i = 1, 2, . . . , N .
VI. N UMERICAL R ESULTS We present the numerical results, first to validate the analytical results derived in the previous sections and, second, to analyze and discuss the behavior of the VAO I and the update rate at the network nodes under rate-constrained update policies at the source and at VAO I-aware or feedback-aware intermediate links. Simulations are conducted over 105 time slots, and the results are averaged over 200 Monte Carlo iterations to obtain steady-state values. The default parameters considered are pg = 0.3, N = 4, and (p0 , p1 , p2 , p3 , p4 ) = (0.7, 0.8, 0.55, 0.95, 0.8), unless otherwise stated.
A. VAoI Optimization In Fig. 7, we depict the average VAO I at the network nodes, ¯ n }N , as a function of the update rate at the source, ψ, {∆ n=1 under various source update policies. The average VAO I at ¯ 1 , is shown directly, whereas the first intermediate node, ∆ N ¯ ¯ 1 plus an offset for subsequent nodes, {∆n }n=2 , it equals ∆ corresponding to the expectedPnumber of version generations n−1 during relaying, given by pg i=1 p1i (Theorem 1). We include two additional baselines alongside the optimal threshold policy (VAO I-Optimal) and the randomized policy: AoI-Optimal and uniform policies. The AoI-Optimal policy is obtained by optimizing the AO I at node 1; it is a threshold policy whose threshold is derived from (27) by setting pg = 1. Under the uniform policy, updates at the source occur periodically every D = ψ1 slots, where D is a positive integer. For the VAO I-optimal (optimal mixed-threshold) and randomized policies, both analytical and simulation curves are shown. The
3.5 3 2.5 2
1.5 0.13 0.16
1.5
0.21
0.28
1 0.5 0 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Fig. 7: Average VAO I at network nodes vs. ψ under various source policies.
simulation results match and validate the analytical results in (29) and (39)1 . Fig. 7 shows that the mixed threshold policy (VAO IOptimal) outperforms all baseline policies and achieves the lowest VAO I across network nodes. This gain is more pronounced under stricter update rate constraints at the source. When the constraint is relaxed, all policies converge toward always-update behavior and perform similarly, as seen for larger ψ values (e.g., above 0.5). Among baselines, the AoIOptimal policy outperforms the uniform policy, which in turn outperforms the randomized policy. Notably, to maintain a target VAO I of 1.5 at node 1, the uniform policy reduces the required update rate by 26% (from 0.285 to 0.210), the AoI-optimal policy by 43% (from 0.285 to 0.162), and the VAO I-optimal policy by 54% (to 0.131), compared to the randomized policy. These results highlight that VAO Iaware optimal policies can significantly reduce transmission rates without sacrificing the conveyed information, thereby improving energy efficiency in IoT networks. Optimal VAO I thresholds: Fig. 8 illustrates the contours ∗ ¯ ϕ over of the optimal threshold ∆∗T and the heatmap of ∆ 1 varying success probabilities p0 and version generation probabilities pg for ψ = 0.05. Larger pg and smaller p0 lead ∗ ¯ ϕ and larger optimal thresholds. According to to higher ∆ 1 Theorem 2, under stringent rate constraints (very low ψ), ∆∗T p p can be approximated as ⌈ ψpg0 ⌉. Furthermore, when ψ ≥ αTg , it follows that ∆∗T = 1. In this case, updates occur at all non-zero VAO I states, resulting in the best average VAO I achievable ∗ ¯ ϕ = pg . under an unconstrained network, ∆ 1 p0 B. Stationary Distribution of VAO I For further evaluation, we present the stationary distributions of VAO I at network nodes 1, 3, and 5 under the threshold policy with ∆T = 2 and ∆T = 5, and the corresponding randomized policies with ψ = 0.201 and ψ = 0.084, as shown in Figs. 9 and 10, respectively. In the latter case with stricter rate constraints, the VAO I distribution at node 1 becomes more dispersed, with higher VAO I values occurring with greater probability. The randomized policy yields a smooth stationary distribution with longer tails, whereas the threshold policy 1 Simulation curves are omitted from the remaining figures to reduce redundancy and improve clarity, as they exactly match the analytical results.
11
0.2
0.5
1
50 20 11
0.4
6
24
13
0.8 7
17
8
0.3 30
0.1
9
0.6
20 28
24
0.2 20
1 13 1
33
0.4
0.15
40
15
39 53
28
0.2 0.2
0.05
45
15 7 1
20 24
33
39 45
0.4
62
53
0.6
73
0.1
10
85
0.8
0
0
1
0
¯ϕ Fig. 8: Contour plot of ∆∗T and heatmap of ∆ 1 versus (pg , p0 ).
2
4
6
8
10
0
5
10
15
20
∗
Fig. 9: Stationary distribution of VAO I at network nodes for ∆T = 2 (ψ = 0.201).
Fig. 10: Stationary distribution of VAO I at network nodes for ∆T = 5 (ψ = 0.084).
Fig. 12: Average VAO I vs. pg under threshold and randomized policies.
Fig. 13: Update rates at network nodes vs. pg under threshold and randomized policies.
1
0.8
0.6
0.4
0.2
0 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Fig. 11: Update rates at network nodes vs. ψ under threshold and randomized policies.
C. Update Rate Optimization
policy increases linearly. By contrast, under the optimal threshold policy, it reaches a saturated level corresponding to the threshold ∆∗T = 1. Beyond this point, further transmissions (i.e., ∆∗T = 0) are unnecessary, since sending updates when the VAO I at node 1 is zero provides no benefit; therefore, these redundant transmissions are avoided. As a result, this also yields a lower, fixed arrival rate at the subsequent intermediate nodes. We observe that, although providing feedback at the intermediate nodes under the VAO I-agnostic randomized policy reduces the update rates compared to always-update forwarding, the VAO I-aware source policy achieves a substantially greater reduction. Prioritizing fresh and informative data enables versionaware communication to improve network efficiency across diverse resource conditions compared to version-agnostic communication. Under tight resource constraints, version-aware communication reduces VAoI while utilizing the same amount of resources, while, when resources are abundant, it maintains VAoI while filtering redundant transmissions, thereby minimizing unnecessary resource consumption.
In Fig. 11, the update rates at the source (node 0) and at the first and last intermediate nodes (1 and 4) are shown for both the optimal mixed-threshold and randomized policies. When ψ is low, i.e., when the update-rate constraint is stringent, updates from the source node are rare. This is achieved by using higher thresholds under the threshold policy and a lower transmission probability ψ under the randomized policy. In this regime, both policies yield similar update rates at the source. The update rates at the intermediate nodes are also similar but remain significantly lower than under the always-update policy with feedback-enabled links, since new updates do not always arrive and retransmissions can be stopped once the last received update has been delivered. On the other hand, as the rate constraint is relaxed (i.e., as ψ increases), the source update rate under the randomized
D. VAoI and Update Rate vs. pg We investigate the impact of the version generation probability pg on the VAO I and the update rate of the network nodes under a fixed source update rate constraint, ψ = 0.4. In Fig. 12, the average VAO I of the first intermediate node (1) and the destination node (5) is shown as a function of pg . We observe, first, that the optimal threshold policy outperforms the randomized policy, with the performance gap increasing as pg grows. Second, the average VAO I at the destination under both policies increases more steeply with respect to pg than at node PN −1 1. This additional slope is i=1 p1i , as indicated in (15). The corresponding update rates for these two nodes, as well as for the source, are shown in Fig. 13. For fixed ψ = 0.4, we observe that when pg is low (below 0.32), the optimal
exhibits an almost uniform distribution with considerably shorter tails. As stated in Proposition 2, the VAO I distribution ϕT π∆ (δ) under the threshold policy is uniform for 1 ≤ δ < ∆T , 1 p decreases by a factor of αTg at δ = ∆T , and then decays exponentially at rate pg p̄0 /αT . The VAO I distributions at the subsequent nodes 3 and 5 are obtained by convolving the distribution of the preceding node with a binomial distribution (see (31)), resulting in progressively smoother distributions with longer tails, as we proceed from node 1 to node 5. These distributions explain why the optimal threshold policy outperforms the randomized policy: it effectively prevents the VAO I at node 1 from exceeding the optimal threshold ∆T and keeps the VAO I as uniformly below this threshold as possible, whereas the randomized policy exhibits an exponential decay with a longer tail. Since the average VAO I is a weighted sum of steady-state probabilities, where larger values contribute more, reducing the probability of high VAO I significantly improves performance.
12
threshold policy at the source can transmit all newly generated versions to node 1. However, by skipping transmissions when no new version is available, i.e., by setting the threshold ∆∗T = 1, this policy reduces the source update rate compared to the randomized policy, while still achieving lower VAO I at node 1. This reduction becomes more pronounced as pg decreases. Consequently, the lower arrival rate at node 1 results in fewer transmissions at node 1 and at subsequent nodes up to node 4 compared to the randomized policy. Note that the update rates under the randomized policy are independent of pg , as it is agnostic to VAO I dynamics. On the other hand, when pg increases beyond 0.32 and 0.64, the source resources become insufficient to transmit all newly generated versions. In this regime, the optimal policy increases the threshold values to 2 and 3, respectively (see (27)). Consequently, the source update rate, and thus the arrival rate at node 1, becomes equal under both policies (with the mixing coefficient κ introduced in Theorem 2). For the randomized policy, the update rates at intermediate nodes remain constant as pg increases because it does not account for VAO I evolution. However, the update rates at nodes 1 and 4 in Fig. 13 increase with pg , even though the arrival rate at node 1 remains unchanged. This behavior is explained by the fact that, as pg (and thus ∆∗T ) increases, the optimal threshold policy introduces a silence interval after each successful update delivery, during which no transmissions occur. This allows the VAO I at node 1 to reach the threshold to initiate the next update. During this interval, node 1 attempts one or a few transmissions (depending on p1 ) to deliver the update to the next node, and the update then propagates similarly through subsequent nodes. In this regime, updates are less likely to be replaced by newer versions due to the silence period. In contrast, under the randomized policy, updates are more frequently replaced by newer versions before successful delivery. As a result, some updates are discarded and no longer transmitted, which reduces the average number of transmissions per update. This leads to lower update rates at intermediate nodes than under the threshold policy, albeit with higher VAoI. VII. C ONCLUSION We provided a comprehensive characterization of the VAO I in multi-hop communication networks with transmission constraints and acknowledgment-based feedback. We developed a bi-level optimization framework to jointly address optimal source-side update control and feedback-aware forwarding at intermediate nodes. We showed that the optimal source policy takes a threshold-based form and derived its closedform expression. For both the optimal threshold policy and a randomized baseline, we obtained closed-form expressions for the stationary distribution, the average VAO I, and the update rates across all network nodes. Our results further quantify the role of feedback in reducing redundant transmissions while preserving the best achievable VAO I. Numerical evaluations corroborate the theoretical analysis and underscore the effectiveness of VAO I-aware and feedback-aware design for efficient multi-hop communication systems.
R EFERENCES [1] E. Delfani and N. Pappas, “From timestamps to versions: Version AoI in single- and multi-hop networks,” in Proc. IEEE INFOCOM, 2026. [2] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,” IEEE Commun. Mag., vol. 59, no. 6, 2021. [3] J. Luo, E. Delfani, M. Salimnejad, and N. Pappas, “From information freshness to semantics of information and goal-oriented communications,” arXiv preprint arXiv:2512.12758, 2025. [4] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proc. IEEE INFOCOM, 2012. [5] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, 2021. [6] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” IEEE/ACM Trans. Netw., vol. 28, no. 5, 2020. [7] R. D. Yates, “The age of gossip in networks,” in Proc. IEEE ISIT, 2021. [8] M. Salimnejad, N. Pappas, and M. Kountouris, “So timely, yet so stale: The impact of clock drift in real-time systems,” IEEE Commun. Lett., vol. 29, no. 10, 2025. [9] J. Feng, H. Pan, T.-T. Chan, and J. Liang, “Timely status update: Should arq be used in two-hop networks?” in Proc. IEEE ICC, 2022. [10] A. Munari and L. Badia, “What’s my age of information again? the role of feedback in AoI optimization under limited transmission opportunities,” IEEE Trans. Commun., 2025. [11] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” IEEE Trans. Inf. Theory, vol. 62, no. 4, 2016. [12] J. P. Champati, H. Al-Zubaidy, and J. Gross, “On the distribution of AoI for the GI/GI/1/1 and GI/GI/1/2 systems: Exact expressions and bounds,” in Proc. IEEE INFOCOM, 2019, pp. 37–45. [13] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “A general formula for the stationary distribution of the age of information and its application to single-server queues,” IEEE Trans. Inf. Theory, vol. 65, no. 12, 2019. [14] R. D. Yates, “The age of information in networks: Moments, distributions, and sampling,” IEEE Trans. Inf. Theory, vol. 66, no. 9, 2020. [15] F. Chiariotti, O. Vikhrova, B. Soret, and P. Popovski, “Peak age of information distribution for edge computing with wireless links,” IEEE Trans. Commun., vol. 69, no. 5, 2021. [16] Y. Jiang and N. Miyoshi, “Joint performance analysis of ages of information in a multi-source pushout server,” IEEE Trans. Inf. Theory, vol. 68, no. 2, 2021. [17] M. A. Abd-Elmagid and H. S. Dhillon, “Closed-form characterization of the MGF of AoI in energy harvesting status update systems,” IEEE Trans. Inf. Theory, vol. 68, no. 6, 2022. [18] M. Moltafet, M. Leinonen, and M. Codreanu, “Moment generating function of age of information in multisource M/G/1/1 queueing systems,” IEEE Trans. Commun., vol. 70, no. 10, 2022. [19] D. Fiems, “Age of information analysis with preemptive packet management,” IEEE Commun. Lett., vol. 27, no. 4, 2023. [20] N. Akar and S. Ulukus, “Age of information in a single-source generateat-will dual-server status update system,” IEEE Trans. Commun., vol. 73, no. 9, 2025. [21] Y. Inoue and M. Mandjes, “Characterizing the age of information with multiple coexisting data streams,” IEEE Trans. Inf. Theory, vol. 71, no. 6, 2025. [22] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “The age of information in a discrete time queue: Stationary distribution and nonlinear age mean analysis,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, 2021. [23] J. Zhang and Y. Xu, “On age of information for discrete time status updating system with Ber/G/1/1 queues,” in Proc. IEEE ITW, 2021. [24] N. Akar and O. Dogan, “Discrete-time queueing model of age of information with multiple information sources,” IEEE Internet Things J., vol. 8, no. 19, 2021. [25] Y. Ji, Y. Lu, X. Xu, and X. Huang, “Age-optimal packet scheduling with resource constraint and feedback delay,” IEEE Trans. Commun., vol. 72, no. 7, 2024. [26] T. Zhang, Z. Chen, Z. Tian, M. Wang, L. Zhen, D. O. Wu, Y. Li, and T. Q. S. Quek, “Age of information in internet of vehicles: A discretetime multisource queueing model,” IEEE Trans. Commun., vol. 73, no. 5, 2025. [27] Y. Chen and A. Ephremides, “Minimizing age of incorrect information over a channel with random delay,” IEEE/ACM Trans. Netw., vol. 32, no. 4, 2024.
13
[28] M. Salimnejad, M. Kountouris, A. Ephremides, and N. Pappas, “Age of information versions: A semantic view of markov source monitoring,” IEEE Trans. Commun., vol. 73, no. 12, 2025. [29] X. Wang, W. Lin, C. Xu, X. Sun, and X. Chen, “Age of changed information: Content-aware status updating in the internet of things,” IEEE Trans. Commun., vol. 70, no. 1, 2021. [30] E. Delfani and N. Pappas, “Semantics-aware status updates with energy harvesting devices: Query version age of information,” in Proc. WiOpt, 2024. [31] G. Karevvanavar, H. Pable, O. Patil, R. V. Bhat, and N. Pappas, “Version age of information minimization over fading broadcast channels,” IEEE Trans. Wireless Commun., vol. 24, no. 2, 2025. [32] A. Arafa and S. Ulukus, “Timely updates in energy harvesting two-hop networks: Offline and online policies,” IEEE Trans. Wireless Commun., vol. 18, no. 8, 2019. [33] B. Li, H. Chen, Y. . Zhou, and Y. Li, “Age-oriented opportunistic relaying in cooperative status update systems with stochastic arrivals,” in Proc. IEEE GLOBECOM, 2020. [34] Y. Gu, Q. Wang, H. Chen, Y. Li, and B. Vucetic, “Optimizing information freshness in two-hop status update systems under a resource constraint,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, 2021. [35] R. Talak, S. Karaman, and E. Modiano, “Minimizing age-of-information in multi-hop wireless networks,” in Proc. Allerton Conf., 2017. [36] A. M. Bedewy, Y. Sun, and N. B. Shroff, “The age of information in multihop networks,” IEEE/ACM Trans. Netw., vol. 27, no. 3, 2019. [37] B. Buyukates, A. Soysal, and S. Ulukus, “Age of information in multihop multicast networks,” J. Commun. Netw., vol. 21, no. 3, 2019. [38] J. Lou, X. Yuan, S. Kompella, and N.-F. Tzeng, “Boosting or hindering: AoI and throughput interrelation in routing-aware multi-hop wireless networks,” IEEE/ACM Trans. Netw., vol. 29, no. 3, 2021. [39] Q. Liu, H. Zeng, and M. Chen, “Minimizing AoI with throughput requirements in multi-path network communication,” IEEE/ACM Trans. Netw., vol. 30, no. 3, 2021. [40] Y. Ke, Z. Ni, D. Zhang, X. Miao, C. Y. Leow, S. Wang, G. Pan, and J. An, “Information freshness in multi-hop satellite iot systems,” IEEE Trans. Mobile Comput., 2025. [41] F. Chiariotti, O. Vikhrova, B. Soret, and P. Popovski, “Age of information in multihop connections with tributary traffic and no preemption,” IEEE Trans. Commun., vol. 70, no. 10, 2022. [42] V. Tripathi, R. Talak, and E. Modiano, “Information freshness in multihop wireless networks,” IEEE/ACM Trans. Netw., vol. 31, no. 2, 2023. [43] P. Kaswan and S. Ulukus, “Age of information with non-poisson updates in cache-updating networks,” in Proc. IEEE ISIT, 2023. [44] A. Sinha, S. Singhvi, P. D. Mankar, and H. S. Dhillon, “Peak age of information under tandem of queues,” in Proc. IEEE ISIT, 2024. [45] S. Asvadi and F. Ashtiani, “Age of information in multipath multihop networks,” in Proc. IEEE WCNC, 2024. [46] O. Ayan, H. M. Gürsu, A. Papa, and W. Kellerer, “Probability analysis of age of information in multi-hop networks,” IEEE Networking Lett., vol. 2, no. 2, 2020. [47] O. Vikhrova, F. Chiariotti, B. Soret, G. Araniti, A. Molinaro, and P. Popovski, “Age of information in multi-hop networks with priorities,” in Proc. IEEE GLOBECOM, 2020. [48] E. Delfani and N. Pappas, “Semantics-aware updates from remote energy harvesting devices to interconnected LEO satellites,” IEEE Commun. Lett., vol. 29, no. 8, 2025. [49] J. R. Norris, Markov chains. Cambridge University Press, 1998, no. 2. [50] E. Altman, Constrained Markov Decision Processes. CRC Press, 1999, vol. 7. [51] D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, 3rd ed. Athena Scientific, 2007. [52] F. J. Beutler and K. W. Ross, “Optimal policies for controlled markov chains with a constraint,” J. Math. Anal. Appl., vol. 112, no. 1, 1985.
node i in the previous slot, i.e., Vi+1 (t) = Vi (t−1). The VAO I ∆i+1 (t) = V0 (t) − Vi+1 (t) is then: ∆i+1 (t) = V0 (t) − V0 (t−1) + V0 (t−1) − Vi (t − 1), (44) | {z } | {z } ξ1
where ξ1 = V0 (t) − V0 (t − 1) represents the number of new versions generated by the source in the most recent slot (either 0 or 1). If the latest transmission fails (w.p. 1 − pi ), but the previous one at t−1 succeeds (w.p. pi ), then Vi+1 (t) = Vi (t− 2), and the VAO I becomes: ∆i+1 (t) = V0 (t) − V0 (t−2) + V0 (t−2) − Vi (t−2), | {z } | {z } ξ2
Proof. Node i transmits updates to node i + 1 in every time slot. Upon successful reception, node i + 1 retains only the most recent version, discarding all earlier ones. Thus, the VAO I at node i + 1 depends on the most recent successful transmissions from node i. If the latest transmission at time t succeeds (w.p. pi ), node i + 1 obtains the version held by
(45)
∆i (t−2)
where ξ2 denotes the number of versions generated over the past two slots. Since the source generates a new version in each slot according to a Bernoulli process with parameter pg , ξk ∼ Bin(k, pg ) over k slots. Generally, the VAO I at node i+1 at time t equals the VAO I at node i from mi slots earlier plus the number of generated versions in those mi slots, where mi follows a Geometric distribution representing the number of transmissions required for successful delivery over link i. A PPENDIX B P ROOF OF L EMMA 1 Proof. According to Proposition 1, the VAO I at all nodes can be expressed recursively as follows: ∆2 (t) = ∆1 (t−m1 )+ξm1 , N N .. X X . ⇒ ∆N+1 (t) = ∆1 (t− mi )+ ξmi . ∆N (t) = ∆N−1 (t−mN−1 )+ξmN−1 , i=1 i=1 | {z } | {z } ∆N+1 (t) = ∆N (t−mN )+ξmN , =τN =βN
The expected value of τN and βN is derived: N N X X 1 E [τN ] = E [mi ] = , p i=1 i=1 i N N N X X (a) X Emi E [ξmi |mi ] = pg E [mi ] , E [ξmi ] = E [βN ] = i=1
i=1
i=1
where (a) follows from the tower rule: E [X] = EY EX|Y [X|Y ] . Note that ξmi | mi follows a Binomial distribution, as given in (13), with mean mi pg . A PPENDIX C P ROOF OF T HEOREM 1 Proof. According to Lemma 1, ¯ N +1 (t) = E [∆N +1 (t)] = E [∆1 (t−τN )+βN ] ∆ (a)
A PPENDIX A P ROOF OF P ROPOSITION 1
∆i (t−1)
=
∞ X
P(τN = τ )E [∆1 (t−τ )]+pg
τ =N
(46)
N X
1 , p i=1 i
where the tower rule: E[∆1(t−τN )] = (a) follows from P ∞ EτN E [∆1(t−τN )|τN ] = τ =N P(τN = τ )E[∆1(t−τ )]. The ¯ ¯ N +1 (t) is then: steady-state value ∆N+1 = limt→∞ ∆ ∞ N N X X X 1 1 ¯ ¯ N+1(b) ∆ = lim E[∆1(t)] P(τN = τ )+pg = ∆1+pg . t→∞ p p i=1 i i=1 i τ =N
14
Equality (b) follows directly from the relation limt→∞ E[∆1 (t − τ )] = limt→∞ E[∆1 (t)], which holds for an ergodic and integrable DTMC ∆1 (t), where E |∆1 (t)| < ∞ [49, Sec. 1.10]. A PPENDIX D P ROOF OF L EMMA 2 Consider an on–off update policy ϕ under which, at each time slot t, node 0 decides whether to transmit (aϕ (t) = 1) or remain idle (aϕ (t) = 0), i.e., ϕ = aϕ (0), aϕ (1), . . . . The objective is to minimize the time-average VAO I at node 1 subject to the update rate constraint at node 0. This problem is formulated as a Constrained Markov Decision Process (CMDP): "T −1 # X ϕ 1 E ∆1 (t) s(0) , subject to η̄0ϕ ≤ ψ, (47) min lim ϕ∈Φ T →∞ T t=0 where Φ denotes all feasible policies. The CMDP is characterized by state s(t) ∈ S, action a(t) ∈ A = {0, 1}, transition probability P(s(t + 1) | s(t), a(t)), and transition cost C(s(t), a(t), s(t + 1)), where, for brevity, the superscript ϕ is omitted. The state, s(t) = ∆1 (t), denotes the VAO I at node 1; imposing an upper bound ∆max yields a finite state space S = {0, 1, . . . , ∆max }. The transition probabilities are: pg p̄g 1 p p̄ ′ P(∆1 |∆1 , a) = g 0 p̄g p̄0 p̄0 pg p0 p̄g p0
a = 0, ∆′1 = ∆1 +1, ∆1<∆max , a = 0, ∆′1 = ∆1 , ∆1<∆max , a = 0, ∆′1 = ∆1 = ∆max , a = 1, ∆′1 = ∆1 +1, ∆1<∆max , a = 1, ∆′1 = ∆1 , ∆1<∆max , a = 1, ∆′1 = ∆1 = ∆max , a = 1, ∆′1 = 1, a = 1, ∆′1 = 0.
1)) ≥ 0 is bounded below, the conditions of [50, Corollary 12.2] are satisfied, ensuring the optimal solutions of the dual and primal problems coincide. Thus, the optimal solution to the primal CMDP (47) is found by solving supλ≥0 g(λ), where ϕ∗λ comes from (51). Specifically, the optimal policy is obtained by first solving the unconstrained MDP (51) for fixed λ to get ϕ∗λ , and then optimizing λ as in (49). We proceed to prove that ϕ∗λ is a threshold policy. Proposition 4. The optimal policy of the MDP problem (51) is a threshold policy. Proof. We begin by establishing that the MDP is weakly accessible, thereby ensuring the existence of an optimal policy. An MDP is weakly accessible if its state space can be partitioned into a transient set St and a communicating set Sc , where all states in Sc are mutually reachable under some stationary policy. For any stationary stochastic policy ϕ assigning positive probability to each action a ∈ {0, 1}, any state ∆′1 is reachable from ∆1 . Specifically, if ∆′1 < ∆1 , take a = 1 once, then a = 0 for ∆′1 steps; if ∆′1 ≥ ∆1 , take a = 0 for ∆′1 − ∆1 steps. Hence, the MDP is weakly accessible; thereby by Proposition 4.2.3 in [51], the optimal average cost Jλ∗ is independent of the initial state s(0). Proposition 4.2.6 guarantees the existence of an optimal policy ϕ∗λ , and Proposition 4.2.1 ensures Jλ∗ , the value function V(s), and ϕ∗λ satisfy the Bellman equations: Jλ∗+V(s) = min Qλ (s, a), ϕ∗ (s) ∈ arg min Qλ (s, a), (53) a∈{0,1}
a∈{0,1}
The transition cost at state s(t) under action a(t) is defined as the resulting VAO I, i.e., C(s(t), a(t), s(t+1)) = ∆1 (t+1). The primal CMDP problem (47) can be reformulated as a Lagrangian dual problem by introducing a multiplier λ ≥ 0:
where Qλ (s, a) = Cλ (s, a) + s′ ∈S P s′ s, a V(s′ ). Here, Cλ (s, a) represents the averageP cost per slot, defined by the transition costs as: Cλ (s, a) = s′ ∈S P s′ s, a Cλ (s, a, s′ ), with Cλ (s, a, s′ ) = ∆′1 + λa. The Bellman equation for state s = ∆1 can be written as a∗ (∆1 ) = 1 if Qλ (∆1 , 1) < Qλ (∆1 , 0), and a∗ (∆1 ) = 0 otherwise. Thus, the optimal action a∗ (∆1 ) depends on the sign of the difference ∂V(∆1 ) = Qλ (∆1 , 1) − Qλ (∆1 , 0). We next show that ∂V(∆1 ) is a decreasing function of ∆1 . For ∆−1 ≤ ∆+1 , we prove that ∂V(∆+1 ) ≤ ∂V(∆−1 ), i.e.,
sup min L(λ, ϕ),
∂V(∆+1 ) − ∂V(∆−1 ) ≤ 0.
λ≥0 ϕ∈Φ
P
(48)
(49)
where L(λ, ϕ) denotes the Lagrangian function: "T −1 # X 1 L(λ, ϕ) = lim E {∆1 (t)+λa(t)} s(0) −λψ. (50) T →∞ T t=0 Let g(λ) = L(λ, ϕ∗λ ) denote the dual function, and let ϕ∗λ be the policy minimizing L(λ, ϕ) for fixed λ: "T −1 # X 1 ϕ∗λ = arg min lim E {∆1 (t) + λa(t)} s(0) . (51) ϕ∈Φ T →∞ T t=0 This corresponds to solving an unconstrained MDP with a modified transition cost: Cλ (s(t), a(t), s(t + 1)) = ∆1 (t + 1) + λa(t).
(52)
For a finite state space S, the growth condition in [50, Eq. 11.21] holds. Since the transition cost C(s(t), a(t), s(t +
(54)
This implies a threshold policy: if ∂V(∆T ) < 0 for some ∆T , then ∂V(∆1 ) < 0 for all ∆1 ≥ ∆T , so the optimal action remains 1 for all such states. Using (48), we obtain: ∂V(∆+1 )−∂V(∆−1 ) = −p0 ∆+1 −∆−1 − p̄g p0 V(∆+1 )−V(∆−1 ) − p̄g p0 V(∆+1 +1)−V(∆−1 +1) . The first term is non-positive. Thus, to prove inequality (54), it suffices to prove that V(∆1 ) is increasing in ∆1 , i.e., for ∆−1 ≤ ∆+1 , V(∆−1 ) ≤ V(∆+1 ). We use the Value Iteration Algorithm (VIA) and induction. VIA converges to V (∆1 ) regardless of the initial V0 (∆1 ), i.e., limk→∞ Vk (∆1 ) = V(∆1 ) for all ∆1 ∈ S. The VIA iteration is: X Vk+1 (∆1 ) = min P ∆′1 ∆1 , a ∆′1 +λa+Vk (∆′1 ) . a∈{0,1}
∆′1 ∈S
|
{z
Qλ,k (∆1 ,a)
}
15
A PPENDIX F P ROOF OF L EMMA 3
ϕ
Fig. 14: DTMC model of ∆1 T for ∆T ≥ 2.
We prove by induction that Vk (∆−1 ) ≤ Vk (∆+1 ) for all k ≥ 0. For k = 0, V0 (∆1 ) = 0, so the claim holds. Assume Vk (∆−1 ) ≤ Vk (∆+1 ) and show Vk+1 (∆−1 ) ≤ Vk+1 (∆+1 ). Since Vk+1 (∆1 ) = 0 1 0 min{Vk+1 (∆1 ), Vk+1 (∆1 )} with Vk+1 = Qλ,k (∆1 , 0) and 1 0 Vk+1 = Qλ,k (∆1 , 1), it suffices to prove Vk+1 (∆−1 ) ≤ + − + 0 1 1 Vk+1 (∆1 ) and Vk+1 (∆1 ) ≤ Vk+1 (∆1 ), since then 0 1 0 1 min{Vk+1 (∆−1 ), Vk+1 (∆−1 )} ≤ min{Vk+1 (∆+1 ), Vk+1 (∆+1 )}. By the induction hypothesis, all bracketed terms below are non-positive: 0 0 Vk+1 (∆−1 )−Vk+1 (∆+1 ) = ∆−1 −∆+1 + p̄g Vk (∆−1 )−Vk (∆+1 ) +pg Vk (∆−1+1)−Vk (∆+1+1) . 1 1 Vk+1 (∆−1 )−Vk+1 (∆+1 ) = p̄0 ∆−1−∆+1 + p̄g p̄0 Vk (∆−1 )−Vk (∆+1 ) +pg p̄0 Vk (∆−1+1)−Vk (∆+1+1) . Thus Vk+1 (∆−1 ) ≤ Vk+1 (∆+1 ), completing the proof. A PPENDIX E P ROOF OF P ROPOSITION 2 Proof. For ∆T = 0, when the VAO I at node 1 is zero, transmission decisions do not affect state transitions, since the VAO I depends solely on whether a new version is generated. Hence, the system dynamics and steady-state distribution are identical for ∆T = 0 and ∆T = 1. The case ∆T = 0 represents an always-update policy, which is equivalent to a randomized policy with ψ = 1 (see Proposition 3 and Appendix J). For ∆T ≥ 2, if ∆1 < ∆T , no transmission occurs; the VAO I increments by 1 if a new version is generated, otherwise it remains the same. If ∆1 ≥ ∆T , transmission occurs: on success, VAO I resets to 1 or 0 depending on whether a new version is generated; on failure, it increases by 1 if a new version is generated, or remains unchanged otherwise. The resulting Markov chain is shown in Fig. 14, with balance equations provided for ∆T ≥ 2: P∞ ϕT ϕT ϕT π∆ (0) = p̄g π∆ (0)+ p̄g p0 i=∆T π∆ (i), 1 1 1P ∞ ϕT ϕT ϕT ϕT π∆1 (1) = pg π∆1 (0)+ p̄0 π∆1 (1)+pg p0 i=∆T π∆ (i), 1 ϕT ϕT ϕT π∆1 (δ1 ) = pg π∆1 (δ1 −1)+ p̄g π∆1 (δ1 −1), 2 ≤ δ1 < ∆T , ϕT ϕT ϕT (∆ ), π∆ (∆ ) = p π (∆ − 1)+ p̄ p̄ π T g T g 0 T ∆1 ∆1 1 ϕT ϕT ϕT (δ1 ) = pg p̄0 π∆ (δ1 −1)+ p̄g p̄0 π∆ (δ1 −1), δ1 > ∆T . π∆ 1 1 1 third line is omitted when ∆T = 2. By applying PThe ∞ ϕT π δ1 =0 ∆1 (δ1 ) = 1 and simplifying, Proposition 2 follows.
Proof. For ∆T = 0 and ∆T = 1, the average VAO I is identical, as shown in the proof of Proposition 2, and equals the average VAO I in Proposition 3 with ψ = 1, i.e., ¯ ϕT (∆T =0) = ∆ ¯ ϕT (∆T =0) = pg . For ∆T ≥ 2, using the ∆ 1 1 p0 steady-state probabilities from Proposition 2, the expected P ∞ ϕ ϕ T ¯ T= VAO I, ∆ 1 δ1 =0 δ1 π∆1 (δ1 ), is given by: ( ) h i P∆T −1 pg pg ϕT ϕT r r ¯ δ 1 + ∆T + , ∆1 = π (∆T −1) 2 +∆T ∆1
δ1 =1
αT
αT (1−r)
1−r
p p̄
where r = αgT 0 , and after some algebraic manipulation, the final expression for the average VAO I (23) is obtained. For a threshold policy with parameter ∆T , η̄0ϕT represents the probability of the states that trigger transmission, i.e., η̄0ϕT = P(∆ϕ1 T ≥ ∆T ), given by: ( ∞ X ∆T = 0, (a) 1, ϕT ϕT η̄0 = π∆1 (δ1 ) = (55) pg , ∆T ≥ 1, (∆T −1)p0 +αT δ =∆ 1
T
where step (a) follows directly from the balance equations and the steady-state probabilities presented in Proposition 2, using a geometric series analysis. A PPENDIX G P ROOF OF T HEOREM 2 Proof. Threshold policies that satisfy the update rate constraint are considered feasible. For a threshold policy with parameter ∆T , the update rate at the source node f (∆T ) = η̄0ϕT , given by (55): pg f (∆T ) = P(∆ϕ1 T ≥ ∆T ) = , ∆T ≥ 1. (56) (∆T −1)p0 +αT Therefore, a threshold policy is feasible if it satisfies f (∆T ) ≤ ψ, which can be simplified using (56): pg 1 − 1 + p0 . ∆T ≥ (57) p0 ψ This implies that ∆T must exceed a certain lower bound. Meanwhile, Lemma 3 shows that the average VAO I under the threshold policy (23) is an increasing function of ∆T, since p αT ¯ ϕT = ∆T 1− + pg0 . it can be rewritten as: ∆ 1 2 (∆T −1)p0+αT pg The constant term p0 remains fixed; the first term increases with ∆T due to the linear growth of ∆2T and the rising αT αT value of 1− (∆T −1)p , since (∆T −1)p decreases 0 +αT 0 +αT as ∆T grows. Therefore, minimizing the average VAO I under the update rate constraint entails selecting the smallest integer ∆T that satisfies (57). However, exact equality may not always be attainable, as ∆T must be integer-valued. To achieve f (∆T ) = ψ, a randomized mixture policy can be employed [52] [50, Sec. 6.3], combining two thresholds ∆∗T and ∆∗T −1, where f (∆∗T ) ≤ ψ and f (∆∗T −1) > ψ, resulting in (27). The threshold ∆∗T is applied w.p. κ and ∆∗T −1 with 1−κ, where κf (∆∗T )+(1−κ)f (∆∗T −1) = ψ, leading to (28). This mixed threshold policy constitutes the optimal solution to the CMDP under the average rate constraint (8) [52].
16
A PPENDIX H P ROOF OF T HEOREM 3 Proof. By Proposition 1, the recursive update of the VAO I at node i + 1 is given by ∆ϕi+1 (t) = ∆ϕi (t − mi ) + ξmi . In the stationary regime (t → ∞), ∆ϕi becomes time-invariant ϕ ϕ in distribution. Let π∆ (δ) and π∆ (δ) denote the stationary i i+1 distributions of the VAO I at nodes i and i + 1, respectively. Conditioning on the geometric delay mi = ℓ and applying the law of total probability, we obtain: ∞ X ϕ π∆ (δ) = P(mi = ℓ)P ∆ϕi (t−ℓ)+ξmi = δ | mi = ℓ . i+1 ℓ=1
(58)
Given mi = ℓ, the random variable ξmi | mi = ℓ follows a Binomial distribution and is independent of ∆i (t − ℓ). Hence, since the PMF of the sum of independent random variables is given by convolution, the conditional probability in (58) can be written using the convolution operator ⊛ as: ϕ P ∆ϕi (t−ℓ)+ξmi = δ | mi = ℓ = B(δ; ℓ, pg ) ⊛ π∆ (δ). i Substituting this expression into (58) yields the first equality of the theorem. Expanding the discrete convolution over the support of the Binomial distribution, r ∈ {0, 1, . . . , ℓ}, gives: ℓ X ϕ ϕ P(ξmi = r | mi = ℓ)π∆ (δ−r). B(δ; ℓ, pg ) ⊛ π∆ (δ) = i i r=0
ϕ
Fig. 15: DTMC model of ∆1 R .
p̄g p0 η̄ ϕT , 1 − p̄g p̄1 0 pg pg p0 η̄ ϕT , πvϕT (1, 1) = πvϕT (0, 1) = p̄g (1 − p̄g p̄1 ) (1 − p̄g p̄1 )2 0 δ−1 pg p̄1 πvϕT (δ, 1) = πvϕT (1, 1), 2 ≤ δ < ∆T , 1 − p̄g p̄1 ∆T −2 pg p̄1 pg p̄1 ϕT πv (∆T , 1) = πvϕT (1, 1), 1 − p̄g p̄0 p̄1 1 − p̄g p̄1 pg p̄0 p̄1 π ϕT (δ−1, 1) πvϕT (δ, 1) = 1 − p̄g p̄0 p̄1 v δ−∆T pg p̄0 p̄1 = πvϕT (∆T , 1), δ > ∆T , 1 − p̄g p̄0 p̄1 πvϕT (0, 1) =
which yields: (59)
η̄1ϕT
=
∞ X δ=0
Substituting this back into (58) completes the proof.
p0 πvϕT (δ, 1) = p1
p0 Θ∆T 1− 1 − p̄0 p̄1
η̄0ϕT ,
(61)
p p̄
where Θ = 1−gp̄g1p̄1 . A PPENDIX I P ROOF OF T HEOREM 4 Proof. The transition from ∆ϕ1 T (t) = δ1 to ∆ϕ1 T (t + 1) = δ1′ , i.e., P(δ1′ | δ1 ), is independent of aϕ1 T (t). Therefore, for the transition from (δ1 , a1 ) to (δ1′ , a′1 ), we have the following: P(∆′1 , a′1 | ∆1 , a1 ) = P(∆′1 | ∆1 )P(a′1 | ∆′1 , ∆1 , a1 ). (60) Here, the superscript ϕT is omitted for notational simplicity. From the DTMC of v = (∆1 , a1 ) depicted in Fig. 5: X πvϕT (0, 1) = p̄g p̄1 πvϕT (0, 1)+ p̄g p0 πvϕT (δ, 0)+πvϕT (δ, 1) δ≥∆T
= p̄g p̄1 πvϕT (0, 1)+ p̄g p0 η̄0ϕT , πvϕT (1, 1) = pg p̄1 πvϕT (0, 1)+ p̄g p̄1 πvϕT (1, 1) + pg p0 η̄0ϕT , πvϕT (δ, 1) = pg p̄1 πvϕT (δ−1, 1)+ p̄g p̄1 πvϕT (δ, 1), 2 ≤ δ < ∆T , πvϕT (∆T , 1) = pg p̄1 πvϕT (∆T − 1, 1)+ p̄g p̄0 p̄1 πvϕT (∆T , 1), πvϕT (δ, 1) = pg p̄0 p̄1 πvϕT (δ−1, 1)+ p̄g p̄0 p̄1 πvϕT (δ, 1), δ > ∆T .
A PPENDIX J P ROOF OF P ROPOSITION 3 Proof. At each time slot, a transmission attempt occurs w.p. ψ and succeeds w.p. p0 , giving a success probability of ψp0 . Upon success, the VAO I resets to 0 or 1 depending on whether a new version is generated in that slot. Otherwise, if no transmission occurs or it fails (w.p. 1 − ψp0 ), the VAO I increases by 0 or 1, again depending on version generation. The Markov chain with transition probabilities is shown in Fig. 15, and solving its balance equations as described below yields the stationary distribution in Proposition 3. P∞ ϕ R ϕR ϕR π∆ (0) = p̄g π∆ (0)+ψ p̄g p0 i=1 π∆ (i), 1 1 1 ϕR ϕR ϕR π∆ (1) = p π (0)+ ψp p + p̄ (1−ψp g ∆1 g 0 g 0 ) π∆1 (1) 1 P∞ ϕR (i), +ψpg p0 i=2 π∆ 1 ϕR ϕR ϕR π∆ (δ ) = p (1−ψp )π (δ −1)+ p̄g (1−ψp0 )π∆ (δ1 ), 1 g 0 1 ∆1 1 1 δ1 ≥ 2. ϕR The recurrence relation of π∆ (δ1 ) for δ1 ≥ 1 is geometric: 1 (1−ψp0 )pg ϕ R δ1 −1 = r π∆1 (1), where r = . Thus, its αR
πvϕT (0, 0) = p̄g πvϕT (0, 0)+ p̄g p1 πvϕT (0, 1),
ϕR π∆ (δ1 ) 1
πvϕT (δ, 0) = p̄g πvϕT (δ, 0)+pg πvϕT (δ−1, 0)
¯ ϕR = ∆1 2 . Noting that expected value is given by ∆ 1 (1−r) ψp p ¯ ϕR = pg . π ϕR (1) = 02 g , we obtain ∆
+pg p1 πvϕT (δ−1, 1)+ p̄g p1 πvϕT (δ, 1), 1 ≤ δ < ∆T , πvϕT (∆T , 0) = pg πvϕT (∆T − 1, 0)+ p̄g p̄0 πvϕT (∆T , 0) +pg p1 πvϕT (∆T − 1, 1)+ p̄g p̄0 p1 πvϕT (∆T , 1), πvϕT (δ, 0) = p̄g p̄0 πvϕT (δ, 0)+pg p̄0 πvϕT (δ−1, 0) +pg p̄0 p1 πvϕT (δ−1, 1)+ p̄g p̄0 p1 πvϕT (δ, 1), δ > ∆T .
ϕ
π R (1)
∆1
αR
1
ψp0