{'fraction_non_alphanumeric': 0.0505295572248402, 'fraction_numerical': 0.009984603182009052, 'mean_word_length': 4.258586849852797, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Minimizing AoI in Resource-Constrained Multi-Source Relaying Systems with Stochastic Arrivals

We consider a multi-source relaying system where the sources independently and randomly generate status update packets which are sent to the destination with the aid of a bufferaided relay through unreliable links. We formulate a stochastic optimization problem aiming to minimize the sum average age of information (AAoI) of sources under per-slot transmission capacity constraints and a long-run average resource constraint. To solve the problem, we recast it as a constrained Markov decision process (CMDP) problem and adopt the Lagrangian method. We analyze the structure of an optimal policy for the resulting MDP problem that possesses a switching-type structure. We propose an algorithm that obtains a stationary deterministic near-optimal policy, establishing a benchmark for the system. Simulation results show the effectiveness of our algorithm compared to benchmark algorithms.


I. INTRODUCTION
In many emerging applications such as the Internet-of-Things, cyber-physical systems, and intelligent transportation systems, the freshness of status information is crucial [1]. The age of information (AoI) has been proposed to characterize the information freshness in status update systems [2], [3]. The AoI is defined as the time elapsed since the latest received status update packet was generated. Recently, the AoI has attracted much interest in different areas, e.g., queuing systems [4], [5] and scheduling problems [6]- [9].
In some status update systems, there is no direct communication link between the source of information and the intended destination or direct communication is costly. Deploying an intermediate node, typically called a relay, in such systems is indispensable and has an array of benefits, e.g., saving on power usage of wireless sensors and improving the transmission success probability. Recently, the AoI has been studied in relaying systems in [6], [10]- [14]. The work [6] studied the AoI minimization in a multi-source relaying system with the generate-at-will model (i.e., possibility of generating a new update in any time), under a transmission capacity constraint for each link. They provided an optimal scheduling policy for a setting called the error-prone symmetric IoT network. The authors in [10] analyzed the AoI in a discrete-time Markovian system for two different relay settings and analyzed the impact of the relay on the AoI. In [11], the authors analyzed the average AoI (AAoI) in a two-way relaying system in which two sources exchange status data, considering the generate-atwill model. The AoI performance under different policies (e.g., a last-generated-first-served policy) in a general multi-hop networks with single-source was studied in [12]. In [13], the authors studied the AoI in a single-source energy harvesting relaying system with error-free channels, and they designed offline and online age-optimal policies. In [14], the authors considered a single-source relaying system with stochastic arrivals where the source communicates with the destination either through the direct link or via a relay. They proposed two different relaying protocols and analyzed the AoI performance.
At the same time, resource limitations are a main bottleneck in optimizing AoI in status update systems, especially, in power-limited sensor networks. Only a few works, such as [13] has incorporated a resource constraint in the relaying system in analysis of the AoI. Moreover, most of the discussed works consider single-source relaying systems, e.g., [10], [12]- [14]. Accordingly, the AoI in multi-source resource-constrained relaying systems has not been widely studied yet.
In this paper, we consider a multi-source discrete-time relaying system with stochastic arrivals where the sources independently generate different types of status update packets. The packets are delivered to the destination via a buffer-aided transmitter with help of a buffer-aided relay through unreliable (error-prone) links under transmission capacity constraint for each link. We further consider a long-run average resource constraint on the average number of all transmissions (i.e., transmitter-to-relay and relay-to-destination). The considered setup can be a representative of, e.g., vehicle-to-vehicle (V2V) communications, and vehicle-to-infrastructure (V2I) communications in which the infrastructure could be roadside units (RSUs) or base stations and the communications are established with the help of another vehicle acting as a relay [15]. We focus to design an age-optimal scheduling policy with the sum AAoI metric under the transmission capacity and average resource constraints. Specifically, we formulate a stochastic optimization problem and then recast it as a constrained Markov decision process (CMDP) problem. By adopting the Lagrangian method, we analyze the structure of an optimal policy and propose an algorithm that finds a stationary deterministic near-optimal policy. Simulation results show the effectiveness of our algorithm compared to benchmark algorithms.
Our relaying system as a two-hop network is an extension of the recent work [16], where the authors provided scheduling algorithms for minimizing AoI in a one-hop buffer-free network with stochastic arrivals and an error-free link, with no resource constraint. In contrast, in our two-hop bufferaided network, all communication links are error-prone, and we consider an average resource constraint. The most related work to our paper is [8], where the authors studied the AoI minimization problem in a single-source relaying system with the generate-at-will model under a resource constraint on the average number of forwarding transmissions at the relay. Different to [8], we consider a multi-source setup with stochastic arrivals which is a challenging generalization of the model adopted in [8]. In addition, we consider a global resource constraint on the average number of all transmissions in the system.

A. System Model
We consider a status update system consisting of two independent sources 1 , a buffer-aided transmitter (Tx), a bufferaided 2 relay (R), and a destination (D), as depicted in Fig. 1. We assume that Tx sends status update packets to D via R and there is no direct communication between Tx and D. Further, we assume that the size of the buffer in Tx and R is one packet per source. We assume that each transmission takes one slot duration.
Time is slotted and t = 0, 1, 2, 3, . . . , indicates the slot index. The sources, indexed 3 by i ∈ {1, 2}, generate status update packets independently according to the Bernoulli distribution with parameter µ i , where the packets arrive at Tx at the beginning of slots. We assume that the old packets in the waiting buffers are replaced with the new ones from the same source, which is done at the beginning of each slot. Let Λ i [t] be a binary indicator that shows whether a packet from source i arrives at Tx in slot t, where Λ i [t] = 1 denotes that a packet arrived; otherwise, Λ i [t] = 0. Thus, Pr{Λ i [t] = 1} = µ i . • Wireless Channels: We assume an unreliable channel with transmission success probability p and q for the Tx-R link and R-D link, respectively. Let ρ[t] (resp. ρ [t]) be a binary indicator that represents the success of a packet transmission at the Tx-R link (resp. the R-D link) in slot t. In specific, if ρ[t] = 1 (resp. ρ [t] = 1), the transmitted packet in slot t from Tx (resp. R) is successfully received by R (resp. D); otherwise, ρ[t] = 0 (resp. ρ [t] = 0). Thus, Pr{ρ[t] = 1} = p and Pr{ρ [t] = 1} = q. We assume that the perfect feedback (delay-free and error-free) is available at each link. Fig. 1: A multi-source relaying status update system in which different status updates arrive at random time slots at Tx which then sends the packets to D via R. For example, in a vehicular setting, sources can be considered as different status information (e.g., speed and location), Tx can be one vehicle's transmitter called on-board unit [15], R can be another vehicle, and D can be an RSU or a vehicle.
• Decision Variables: We assume that, in each slot, at most one source can be scheduled per link and the transmissions are over orthogonal channels. Let α[t] ∈ {0, 1, 2} denote the (transmission) decision of Tx in slot t, where α[t] = i means that Tx transmits the packet of source i to R, and α[t] = 0 means Tx stays idle. Similarly, let β[t] ∈ {0, 1, 2} denote the (transmission) decision of R in slot t, where β[t] = i means that R forwards the packet of source i to D, and β[t] = 0 means that R stays idle. We assume that there is a centralized controller that decides what Tx and R does during each slot.
, and ∆ i [t] be the AoI of source i at Tx, R, and D, in slot t, respectively. The evolution of these AoIs are given by

B. Problem Formulation
. . , be a sequence of decision variables. We intend to optimize the decision variables in order to minimize the time average sum of AoIs at D, satisfying: i) the transmission capacity constraint per link at every slot and ii) a long-run average resource constraint. Let∆(D) andc(D) denote the long-run expected (time) average sum of AoIs at D and the average number of transmissions in the system, respectively, for given D, which are defined as where 1 {·} is an indicator function which equals to 1 when the condition in {·} holds, and E{·} is the expectation with respect to the system randomness (i.e., channel reliability and packet arrival processes) and the policy. By these definitions, our aim is to solve the following stochastic optimization problem where the real value Γ max ∈ (0, 2] is the maximum allowable average number of transmissions in the system. Constraint (1b) is an average resource constraint that reflects the resource limitation in the normalized form, i.e., normalized to the power usage per each transmission. Thus the constraint can represent a limitation on the total average consumed power.

III. CMDP FORMULATION AND LAGRANGE RELAXATION
In this section, we attain to solve main problem (1) by transforming it into a CMDP problem which is then solved by using the Lagrangian relaxation method.

A. CMDP Formulation
We introduce the CMDP by the following elements: • State: The state of the CMDP incorporates the knowledge about the AoIs at Tx, R, and D. We define the state in slot t by are the relative AoIs at R and D in slot t, respectively. Using the relative AoIs simplifies the subsequent analysis and derivations. The intuition is that the amount of the change of the sum AoIs at D from slot t to the next slot t + 1 is determined by y i [t], which is shown in the following equation ).
Similarly, the amount of the change of the AoI at R is x i [t]. Moreover, we denote the state space by S which includes all possible states. Note that S is a countable infinite set due to the AoIs being potentially unbounded.
• Action: We define the action taken in slot t by Actions are determined by a policy, denoted by π, which is a rule that generates these actions by observing the current state (i.e., Markovian policies), i.e., a policy is a mapping from states to actions, potentially with a probability distribution. Moreover, let A denote the action space.
• Cost Functions: The (immediate) cost functions include: 1) the AoI cost, and 2) the transmission cost. The AoI cost of each slot t is the sum AoIs at D given by C( • State Transition Probabilities: For any two states s, s ∈ S, P ss (a) is the state transition probability that gives the probability of moving to state s (next state) from state s (current state) under taking an action a = (α, β). Mathematically, P ss (a) is given as P ss (a) = i Pr{s i |s i , a}, where s i = (θ i , x i , y i ), s i = (θ i , x i , y i ) are state vectors associated to source i, and Pr{s i |s i , a} is given by (2) shown on the top of next page. Note that s is arranged as s = (s 1 , s 2 ).
By these definitions, the objective of CMDP, denoted by J(π; s[0]), which is the expected average sum AoIs at D, is given by where s[0] is the initial state. Similarly, the constraint function of CMDP, denoted byD(π; s[0]), which is the expected average transmission cost in the system, is given bȳ (1) is transformed into the following CMDP problem The optimal value of problem (3) for a given s[0] is denoted by J * (s[0]).

B. Lagrange Relaxation Method
We transform problem (3) into an unconstrained average cost MDP (or simply MDP) leveraging the Lagrangian relaxation method. By this method, for a given Lagrange multiplier λ ≥ 0, the Lagrangian, acting as the objective function for the MDP problem, is given by . Note that the term −λΓ max is omitted from the Lagrangian because of being constant with respect to the policy for a given λ. An optimal policy of the MDP, for fixed λ, denoted by π * λ and called MDP-optimal policy, is a solution of the following MDP problem: By checking the growth condition [17,Eq. 11.20], the optimal value of the CMDP problem (3), J * (s[0]), and the optimal value of the MDP problem (4), denoted by L * (λ; s[0]), ensures the following: Therefore, the solution of the CMDP problem (3) can be found by an algorithm that iteratively executes the following two steps: 1) find an optimal policy of the MDP problem (4) with fixed λ, i.e., π * λ , and 2) update λ to a direction that aims to obtain J * (s[0]) according to (5).
In the next section, we focus to find an MDP-optimal policy π * λ and estimating the optimal Lagrange multiplier.

IV. OPTIMAL POLICY OF THE CMDP PROBLEM
In the following, we focus on obtaining an MDP-optimal policy and estimating the optimal Lagrange multiplier, respectively, in Sec. IV-A and Sec. IV-B.

A. Optimal Policy of the MDP Problem
We elaborate on the structure of MDP-optimal policy for the case with error-free links by the following theorem.
Theorem 1. For given λ and error-free links, any MDPoptimal policy of problem (4) has a switching-type structure 4 for β with respect to y = (y 1 , y 2 ).
Proof. The proof will be provided in the extended version.
Value iteration is a classical method to handle MDP problems, but cannot be applied for the infinite state spaces. To circumvent this problem, we use the state truncation method and approximation analysis [17,Ch. 16], [18].
1) State Truncation and Approximated MDP: We truncate S into a finite state space S (N ) which is parameterized by an integer N . To this end, whenever the AoIs exceed N , we set their values to N . The corresponding MDP is called the truncated or approximated MDP. The state transition probabilities of the truncated MDP, P (2), we replace θ i + 1, x i , and y i , respectively, by otherwise, it equals to N . In general, there is no guarantee that the truncated MDP converges to the original one [18, p. 276]. By [16,Theorem 9], for large enough N , the truncated MDP convergences to the original MDP.
2) Finding Optimal Policy of the Truncated MDP: Now, the Relative Value Iteration (RVI) algorithm can be exploited to solve the truncated MDP for a given λ and parameter N .
In specific, RVI is an iterative algorithm with the following value iteration equation with iteration index n: where L(s, a; λ) = C(s) + λD(a) and h Alg. 1 (see , where ε is a RVI termination criterion.
For a given N and λ, the RVI algorithm give an optimal policy for the truncated MDP after a finite number of iterations. This is because the truncated state MDP is unichain and by [19,Theorem 8.6.6] the optimality of RVI is guaranteed.
Importantly, there is no guarantee (roughly, no possibility), even for any arbitrarily small ζ, that π * λ bis obtained by Alg. 1 would ensure thatD(π * λ bis ) = Γ max . This is, π * λ bis (resp. J(π * λ bis )) is not necessarily an optimal policy (resp. the optimal value) for the CMDP problem (3). Following [23], by exploiting a mixing policy 5 which is mixture of π * λ − (infeasible policy) and π * λ + (feasible policy) with mixing factor η, the value of CMDP problem (3), J mix , is given by where We remark that although J mix is less than J(π * λ + ), there is no guarantee that J mix is the optimal value of the CMDP problem (3). This is because there are no guarantees that π * λ − and π * λ + are converged policies 6 , i.e., as λ − increases to λ * , the corresponding π * λ − does not change (similarly for λ + as it decreases to λ * ) [20], [24]. However, J mix serves as a benchmark to evaluate the performance of any policy such as π * λ + . Finally, we note that the mixing policy is not stationary and ergodic. Accordingly, one can select π * λ + as a feasible solution for the CMDP problem (3) which is a stationary deterministic policy and is more desirable in practice. As explained before, policy π * λ + is not guaranteed to be an optimal policy for the CMDP problem (3), while it gives acceptable performance for small enough ζ, as shown in the numerical analysis.  19 Compute π * λ + and π * λ − ; 20 ComputeD(π * λ + ) andD(π * λ − ), and then η * by (8); 21 Compute J(π * λ + ) and J(π * λ − ); In this section, we numerically evaluate the AoI performance of the proposed algorithm (Alg. 1) and the structure of an optimal policy. The system parameters including the values of the arrival rates, µ = (µ 1 , µ 2 ), the reliabilities of the links 5 In a mixing policy, randomization (between two deterministic policies) occurs exactly once before starting to operate the system. 6 Here, convergence is point-wise, see [20,Definition 3.6]. in the system, p and q, and the allowable average number of transmissions, Γ max , are stated in the label or legend of each figure. For Alg. 1, we set N = 7, ζ = 0.01, and ε = 0.001. Fig. 2 shows an example of the structure of the policy for the decision at R, β, with respect to the relative AoIs at D, y i , for state s = (1, 2, 0, 1, y 1 , y 2 ). This figure verifies Theorem 1, and unveils that R schedules the available packet of the source with a higher relative AoI at D. Fig. 3 exemplifies the structure of the policy for the decision at Tx, α, with respect to the relative AoIs at R, x i , for state s = (1, 1, x 1 , x 2 , 4, 4). Having α = 0 at (x 1 = 0, x 2 = 1) implies that transmission does not occur at every state due to the resource budget. We can conclude from this figure that for fixed y 1 and y 2 , Tx will give a higher priority to schedule the source that has a lower status update rate. This is because the waiting time at D for receiving new updates from that source becomes large as a consequence of infrequent packet arrivals, which becomes a bottleneck in reducing the AoI. Fig. 4 depicts the average sum AoI at D (sum AAoI) with respect to the allowable average number of transmissions in the system (resource budget), Γ max , for different arrival rates and reliability of the links, obtained by averaging over 100,000 time slots. In this figure, "Mix." refers to J mix obtained by (7), and "Deter." stands for J(π * λ + ). For benchmarking, we consider a "Lower bound" scheme where we eliminate the average resource constraint by setting Γ max = 2 and realize the generate-at-will model by setting the arrival rates as µ 1 = µ 2 = 1. With these setting, our system becomes equivalent to the one studied in [6], and we use the greedybased optimal policy derived in [6]. As another benchmark, we design a "Greedy" policy, where the transmission is allowed in slot t whenD t ≤ Γ max , whereD t denotes the average number of transmissions until t, and the decision criteria are the relative AoI at R for α and the relative AoI at D for β.
First, Fig. 4 shows that the deterministic policy, π * λ + , achieves a near-optimal performance. Fig. 4 illustrates that the sum AAoI dramatically increases when the resource budget Γ max is decreased, and the sum AAoI values become large when channel reliabilities are reduced. Moreover, Fig. 4 exhibit that the sum AAoI converges to the lower bound when the arrival rates of updates are high and the resource budget is large. For that case, we infer that an optimal policy has a greedy behavior where the maximum of the relative AoIs at R is the greedy criterion for the decision of Tx, and the maximum of the relative AoIs at D is a greedy criterion for the decision of R. We observe that the optimality gap for the Greedy policy is large when the resource budget is small. This clearly emphasizes that it is pivotal to take into account resource limitations in age-optimal policy design. Namely, it may be possible to find some algorithms that minimize the sum AAoI, but they are not necessarily resource-efficient ones.
VI. CONCLUSION We studied the sum AAoI minimization scheduling problem in a multi-source relaying system with stochastic arrivals and unreliable communication channels, under per-slot transmission capacity constraints per link and a long-run average resource constraint. To this end, we formulated a stochastic optimization problem and recast it as a CMDP problem. We analyzed the structure of an optimal policy and proposed an algorithm that obtains a stationary deterministic near-optimal policy which is easy to implement. According to the simulation results, our proposed algorithm significantly reduces the sum AAoI compared with the non-trivial greedy-based benchmark algorithm. We concluded that when the average resource budget is large and the arrival rates of status updates are high, an optimal policy has a greedy behavior.