Timely delivery of information updates is gaining increasing relevance with the advent of technologies such as autonomous flying vehicles, internet of things, and other cyber physical systems. In autonomous flying vehicles, for example, timely exchange of position, velocity, and other control information can improve network safety [1], [2].
Packet delay, the traditionally used measure, accounts for the average time taken for a packet to reach the destination node, but does not measure the 'information lag' at the destination node, especially when the information update generation can be controlled [3]- [5]. For example, if two packets carry the same information, and one arrives early at the destination, then there is no need in accounting for the delay in reception of the second packet.
Age of information (AoI), a newly proposed metric [3], [6], is defined to be the time elapsed since the last received information update was generated at the source node. AoI, upon reception of a new update packet drops to the time elapsed since generation of the packet, and grows linearly otherwise. AoI, therefore, more accurately captures the 'information lag' at the destination node.
AoI has been analyzed for various queueing models [3], [7]- [11], but very little attention has been paid to AoI minimization in wireless networks. A problem of scheduling finitely many update packets under physical interference constraints was shown to be NP-hard in [12]. Age for a broadcast network, where only a single link can be activated at any time, was studied in [13]- [15]. Some preliminary analysis of age for a slotted ALOHA like random access was done in [16],
The authors are with the Laboratory for Information and Decision Systems (LIDS) at the Massachusetts Institute of Technology (MIT), Cambridge, MA. {talak, sertac, modiano}@mit.edu This work was supported by NSF Grants AST-1547331, CNS-1713725, and CNS-1701964, and by Army Research Office (ARO) grant number W911NF-17-1-0508. while multi-hop networks have been considered in [5], [17]. More recent work includes [4], [18], [19], which propose centralized scheduling policies for AoI minimization, under general interference constraints and time varying channels.
In a wireless network, it is not always possible to implement centralized schemes. In this paper, we consider a simple, yet broad, class of distributed scheduling policies for wireless networks, in which each link attempts transmission with a certain probability. We consider time varying channel and a pairwise interference model, in which each link interferes with a specified set of links in the network.
We first derive an interesting relation between the optimal attempt probability, and the optimal age of the given link and the interfering links. We then characterize the optimal distributed policy π D , as a solution to a convex optimization problem. We further show that this convex problem can be solved distributively.
We model a wireless communication network as a graph G = (V, E), where V is the set of nodes and E is the set of directed communication links between the nodes. Each link e ∈ E is associated with a source-destination pair. Time is slotted, with the duration of each slot set equal to the time it takes to transmit a single update packet. For simplicity, we normalize the slot duration to unity.
Transmission of update packets cannot occur simultaneously over all links due to wireless interference constraints [20]. For each link e ∈ E, there is a subset of links N e ⊂ E, that interfere with link e, i.e., if link e and a link l ∈ N e attempt simultaneous transmission, then the transmission over link e fails due to interference. We call this the pairwise interference model. Popular models such as 1-hop and 2-hop interference models [20] are special cases of this model.
Channel uncertainty can also lead to failure in reception of update packets. We consider a two state channel process S e (t) ∈ {0, 1} for all time t and links e. Channel state S e (t) = 1 implies that link e's channel is ON at time t, and a noninterfering transmission over e is successfully received. When S e (t) = 0, even a non-interfering transmission over link e fails due to bad channel conditions. We assume the channel process {S e (t)} t,e to be independent and identically distributed (i.i.d.) across time t, and only independent across links e. We let γ e = Pr (S e (t) = 1) denote the channel success probability for link e. We consider the case when the channel statistics, namely γ e for all e ∈ E, are known but the current channel state S e (t) cannot be observed.
We use U e (t) to denote scheduling decisions at time t, for each link e. U e (t) = 1 when link e attempts transmissions in slot t, and U e (t) = 0 otherwise. Thus, a successful transmission occurs over link e if and only if a transmission is attempted on link e, the link e's channel is ON, and no transmission is attempted over links e ∈ N e . This is equivalent to Ûe (t) S e (t)U e (t) e ∈Ne
(1 -U e (t)) = 1.
(1)
AoI of a network is a function of AoI of each sourcedestination pair. Thus, we define age A e (t) for each link, to be the time since the last received update was generated. We assume source nodes to be active sources, i.e., it can generates a fresh update packet before every transmission.
When all sources are active, the age A e (t), is equal to the time elapsed since the last successful transmission over e. Thus, the evolution of age A e (t) can be written as
for all e ∈ E. We define average age for link e to be
A ave e = lim sup
whenever the limit exists. We define the peak age to be the average of all the age peaks:
A p e = lim sup
where T e (i) denote the ith instance of successful transmission over link e, i.e., the ith instance when Ûe (t) = 1, and N e (T ) is the number of successful transmissions over link e until time T . We define average and peak AoI of the network to be a weighted sum of link AoI:
Our objective is to design distributed scheduling policies that minimize the network average and peak age.
We focus our attention on policies in which scheduling decisions are made by the source of each link e, and not by a centralized scheduler. In particular, we consider policies in which each link e attempts transmission with probability p e > 0, independent across links and slots. We refer to these policies as the distributed stationary policies.
The probability that a non-interfering transmission is attempted over link e is given by f e = p e e ∈Ne (1 -p e ). We will refer to f e as the link activation frequency of link e, and use f = (f e ) e∈E to denote the link activation frequency vector.
The space of all link activation frequencies f , attainable using distributed stationary policies, is given by
Figure 1 shows the set of feasible link activation frequencies for distributed policies for the two interfering link example. Also, shown is the set of all link activation frequencies F attainable using a centralized scheduler. It can be seen that the set F D is non-convex, and strictly smaller than F. The gap between these two sets indicates the price one has to pay in resorting to distributed scheduling.
In this section, we characterize an age optimal policy, and propose an implementation that requires only local information. We first show that for any distributed stationary policy, the peak and average age are equal, and can be written as a simple convex function in link activation frequencies f e .
Lemma 1: For any distributed stationary policy, the average and peak age is given by
where f e = p e e ∈Ne (1 -p e ) is the link activation frequency of link e.
Proof: A similar result was proved in [4] which considered a class of centralized policies, that are not necessarily stationary. Here, we provide a proof for distributed stationary policies.
Consider a link e. Then, under any distributed stationary policy, the event that link e is successfully activated in slot t is independent and identically distributed across slots, with success probability of γ e f e . Thus, the time since last activation We use U e (t) to denote scheduling decisions at time t, for each link e. U e (t) = 1 when link e attempts transmissions in slot t, and U e (t) = 0 otherwise. Thus, a successful transmission occurs over link e if and only if a transmission is attempted on link e, the link e's channel is ON, and no transmission is attempted over links e ∈ N e . This is equivalent to
(1)
AoI of a network is a function of AoI of each sourcedestination pair. Thus, we define age A e (t) for each link, to be the time since the last received update was generated. We assume source nodes to be active sources, i.e., it can generates a fresh update packet before every transmission.
When all sources are active, the age A e (t), is equal to the time elapsed since the last successful transmission over e. Thus, the evolution of age A e (t) can be written as
for all e ∈ E. We define average age for link e to be
A ave e = lim sup
whenever the limit exists. We define the peak age to be the average of all the age peaks:
A p e = lim sup
where T e (i) denote the ith instance of successful transmission over link e, i.e., the ith instance when Ûe (t) = 1, and N e (T ) is the number of successful transmissions over link e until time T . We define average and peak AoI of the network to be a weighted sum of link AoI:
Our objective is to design distributed scheduling policies that minimize the network average and peak age.
We focus our attention on policies in which scheduling decisions are made by the source of each link e, and not by a centralized scheduler. In particular, we consider policies in which each link e attempts transmission with probability p e > 0, independent across links and slots. We refer to these policies as the distributed stationary policies.
The probability that a non-interfering transmission is attempted over link e is given by f e = p e e ∈Ne (1 -p e ). We will refer to f e as the link activation frequency of link e, and use f = (f e ) e∈E to denote the link activation frequency vector.
The space of all link activation frequencies f , attainable using distributed stationary policies, is given by
and 0 ≤ p e ≤ 1 ∀ e ∈ E . (6) Figure 1 shows the set of feasible link activation frequencies for distributed policies for the two interfering link example. Also, shown is the set of all link activation frequencies F attainable using a centralized scheduler. It can be seen that the set F D is non-convex, and strictly smaller than F. The gap between these two sets indicates the price one has to pay in resorting to distributed scheduling.
In this section, we characterize an age optimal policy, and propose an implementation that requires only local information. We first show that for any distributed stationary policy, the peak and average age are equal, and can be written as a simple convex function in link activation frequencies f e .
Lemma 1: For any distributed stationary policy, the average and peak age is given by
where f e = p e e ∈Ne (1 -p e ) is the link activation frequency of link e.
Proof: A similar result was proved in [4] which considered a class of centralized policies, that are not necessarily stationary. Here, we provide a proof for distributed stationary policies.
Consider a link e. Then, under any distributed stationary policy, the event that link e is successfully activated in slot t is independent and identically distributed across slots, with success probability of γ e f e . Thus, the time since last activation is geometrically distributed with mean
Notice that, although the objective function is convex, the constraint set F D is non-convex, see Figure 1. Furthermore, obtaining optimal link activation frequencies f * does not suffice as the distributed policy is characterized by the attempt probabilities p e . The optimal link attempt probabilities p * , that solve (10), yield a distributed stationary policy, that is both peak and average age optimal. We call this policy π D .
The following result characterizes the optimal link attempt probabilities p * in terms of the optimal link age A * e .
Theorem
Now, substituting q e = 1 -p e , the optimization problem (10) reduces to Minimize p≥0,q≥0 e∈E w e γ e p e e ∈Ne q e subject to p e + q e ≤ 1 ∀e ∈ E (11) This is a convex program in standard form, and can be solved using KKT conditions to obtain Theorem 1. The details are given in Appendix B.
Preliminary results on age optimization for a ALOHA type network model were presented in [16] for a network in which only one link can be activated at any given time. As a heuristic, it was argued in [16] that the attempt rates should be
However, Theorem 1 shows that the attempt probability
is both peak and average age optimal. This gives us a more precise answer to the question posed in [16]. Our result, however, holds under the more general pairwise interference constraints, and non-equal weights w e > 0.
A. Distributed Computation of π D Although, Theorem 1 gives a characterization of the optimal attempt probabilities, in terms of the optimal link age A * e , it does not provide for a simple method to computation.
We now provide for an alternate characterization of the network age minimization problem (8). In particular, we show that p * can be obtained by a simpler convex optimization problem, than the one in (11). We will also see that this simpler problem is akin to distributed computation of the policy π D .
for all e ∈ E.
Proof: See Appendix C. We first note that the variable λ e is a proxy for the weighted age w e A e of link e, and the solution λ * e corresponds to optimal weighted age w e A * e . This can also be intuited from (15), which is same as (9).
The objective function G(λ) in ( 14) is a concave function; since the problem is convex. Therefore, a simple projected gradient ascent is guaranteed to converge to the optimal λ * [21]. The gradient of the function G (λ) is given by for all e ∈ E, where θ e = e :e∈N e λ e . Note that the gradient ∂G(λ) ∂λe depends only on λ e and λ e , for e that are 'extended neighbors' of e. This space dependence of ∂G(λ) ∂λe on λ makes the projected gradient descent algorithm akin to distributed implementation.
We give the projected gradient descent algorithm for distributively computing policy π D in Algorithm 1. In it, we divide time into frames, each frame of F ≥ 1 slots. For simplicity, we assume symmetric interference, i.e., e interferes with e if and only if e interferes with e which is same as the condition N e = {e ∈ E | e ∈ N e } for all links e. Link e, sets its attempt probability to p e (m), in frame m ≥ 1. The source of link e tracks and updates two variables, namely, λ e (m) and θ e (m). We use Π to denote the projection on the set [ , +∞), for a > 0. As seen in Steps 5 and 7 in Algorithm 1, variables λ e (m) and θ e (m) need to be exchanged only between the neighboring links. m ← m + 1 11: end for IV. CONCLUSION We considered age minimization in a wireless network, with pairwise interference constraints, time varying channels, and single-hop flows. We considered a simple class of distributed scheduling policies, in which each link attempts transmission with probability p e . We showed an interesting relationship between the optimal attempt probability for a link, and the optimal age of the link and it's neighboring links. We then showed that the optimal link attempt probabilities can be obtained by solving a convex optimization problem, which can be done distributively using the projected gradient ascent algorithm.
Consider a distributed stationary policy with link activation frequencies f e > 0 for each e ∈ E. For a link e, let T e (i) be the ith instance when link e was successfully activated, i.e., the ith instance when Ûe (t) = 1. Let X e (i) = T e (i) -T e (i-1) to be the ith inter-(successful) activation time for link e. Since all the processes involved, namely S e (t) and U e (t), are i.i.d. across time t, X e (i) is geometrically distributed with rate equal to P Ûe (t) = 1 = γ e f e , i.e., P [X e (i) = k] = γ e f e (1 -γ e f e ) k-1 , for all k ∈ {1, 2, . . .}.
We now compute the average age A ave e for link e. Note that the age A e (t) over slots t ∈ {T e (i)+1, . . . T e (i+1)} increases from 1 to X e (i) in steps of 1. Therefore,
m=1 m for all i. Then, using renewal theory [22], we can derive the average age to be
Computing the moments of X e (i) we get A ave e = 1 γefe a.s.. For peak age, note that the ith peak is equal to the ith inter-(successful) activation time X e (i), i.e., A e (T e (i)) = X e (i). Therefore, we have
which is equal to E [X e (1)] = 1 γefe a.s.. This proves the result.
Consider the Lagrangian dual L(p, q, λ) = e∈E w e γ e p e e ∈Ne q e + e∈E λ e (p e + q e -1) .
(17) The problem (11) satisfies Slater's conditions, and thus, the KKT conditions are both necessary and sufficient. Setting partial derivatives of L with respect to p e and q e to zero, we obtain p e λ e = w e A e , and q e λ e = e :e∈N e w e A e ,
for all e ∈ E, where A e = 1 γepe e ∈Ne q e is the age of link e. Equations (18) imply that λ e cannot be zero. By complementary slackness criteria we must have p e + q e = 1. This, with (18)
The age minimization problem, given in (10), can be written as by substituting q e = 1 -p e : Minimize
This follows by first making the the substitution p e = e Pe , q e = e Qe , and f e = e he , and then taking log in each of the constraints. This is a standard technique in geometric programming [21]. However, unlike geometric programming, we don't need to apply log function to the objective as it is already convex, and also separable in variables h e . The problem (20) is convex [21], and satisfies slater's conditions. As a consequence, the duality gap is zero, and the problem ( 20) is equivalent to its Lagrangian dual problem.
Define the Lagrangian function of the optimization problem (20)
where g (λ, ν) is the dual objective function defines as g (λ, ν) =Minimize h,P,Q L (h, P, Q, λ, ν) .
We will now show that the the optimization problem in Theorem 2 is in fact the dual problem (22). First note that the Lagrangian function L (h, P, Q, λ, ν) is strictly convex in h, P, and Q [21]. Thus, first order conditions ∇ h,P,Q L = 0 yield the optimal h, P, and Q. Setting these partial derivatives to 0, we get
, for all e. Substituting (24) and (25) in L, in (21), we recover g(λ, µ) = G(λ), the objective function in (14), and therefore, the dual problem ( 22) is same as the optimization problem in Theorem 2. This proves the first part.
We now show that if λ * is the solution to this problem, then the optimal attempt probability is given by (15). Let f * , p * , q * be the solution to (19), h * , P * , Q * be the solution to (20), and λ * be the solution to the problem in Theorem 2.
Note that, for each link e ∈ E, we must have f * e = p * e e ∈Ne q * e and p * e + q * e = 1; as otherwise the objective function can be reduced by increasing f * e and/or p * e . Since p * e = e P * e and q * e = e Q * e , we have e P * e + e Q * e = 1. Substituting this in (24), and using (25), we obtain
which proves the result.