measuring
information freshness. AoI measures the time that elapsed since
the last received update was generated. We consider the problem
of minimizing average and peak AoI in wireless networks under
general interference constraints. When fresh information is always
available for transmission, we show that a stationary scheduling
policy is peak age optimal. We also prove that this policy achieves
average age that is within a factor of two of the optimal average age.
In the case where fresh information is not always available, and
packet/information generation rate has to be controlled along with
scheduling links for transmission, we prove an important separation
principle: the optimal scheduling policy can be designed assuming
fresh information, and independently, the packet generation rate
control can be done by ignoring interference. Peak and average
AoI for discrete time G/Ber/1 queue is analyzed for the first time,
which may be of independent interest.
more »
« less
Age Optimal Information Gathering and Dissemination on Graphs
We consider the problem of timely exchange of
updates between a central station and a set of ground terminals
V , via a mobile agent that traverses across the ground terminals
along a mobility graph G = (V;E). We design the trajectory
of the mobile agent to minimize peak and average age of
information (AoI), two newly proposed metrics for measuring
timeliness of information. We consider randomized trajectories,
in which the mobile agent travels from terminal i to terminal
j with probability Pi;j . For the information gathering problem,
we show that a randomized trajectory is peak age optimal and
factor8H average age optimal, where H is the mixing time of
the randomized trajectory on the mobility graph G. We also
show that the average age minimization problem is NPhard.
For the information dissemination problem, we prove that the
same randomized trajectory is factorO(H) peak and average age
optimal. Moreover, we propose an agebased trajectory, which
utilizes information about current age at terminals, and show
that it is factor2 average age optimal in a symmetric setting.
more »
« less
 NSFPAR ID:
 10110599
 Date Published:
 Journal Name:
 IEEE Infocom 2019
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Age of information (AoI) is a recently proposed metric for measuring information freshness. AoI measures the time that elapsed since the last received update was generated. We consider the problem of minimizing average and peak AoI in wireless networks under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: the optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time, which may be of independent interest.more » « less

null (Ed.)We introduce and study the doubly balanced connected graph partitioning problem: Let G =( V , E ) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p ( V )=∑ j &isin V p ( j ) = 0. The objective is to partition G into ( V 1 , V 2 ) such that G [ V 1 ] and G [ V 2 ] are connected, ∣ p ( V 1 )∣,∣ p ( V 2 )∣≤ c p , and max{ ∣ V 1 / V 2 ∣,∣ V 2 / V 1 ∣} ≤ c s , for some constants c p and c s . When G is 2connected, we show that a solution with c p =1 and c s =2 always exists and can be found in randomized polynomial time. Moreover, when G is 3connected, we show that there is always a “perfect” solution (a partition with p ( V 1 )= p ( V 2 )=0 and ∣ V 1 ∣=∣ V 2 ∣, if ∣ V ∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p ( V )≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.more » « less

Given a graph G = (V, E) and a subset T ⊆ V of terminals, a Steiner tree of G is a tree that spans T. In the vertexweighted Steiner tree (VST) problem, each vertex is assigned a nonnegative weight, and the goal is to compute a minimum weight Steiner tree of G. Vertexweighted problems have applications in network design and routing, where there are different costs for installing or maintaining facilities at different vertices. We study a natural generalization of the VST problem motivated by multilevel graph construction, the vertexweighted gradeofservice Steiner tree problem (VGSST), which can be stated as follows: given a graph G and terminals T, where each terminal v ∈ T requires a facility of a minimum grade of service R(v) ∈ {1, 2, . . . `}, compute a Steiner tree G0 by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in G 0 with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multilevel variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edgeweighted case, they have not been studied as well in the more general vertexweighted case. We first describe a simple heuristic for the VGSST problem whose approximation ratio depends on `, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the VGSST problem admits a (2 ln T)approximation, where T is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multigrade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. Finally, we show that this problem is a special case of the directed Steiner tree problem and provide an integer linear programming (ILP) formulation for the VGSST problem.more » « less

Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely biarc digraphs (digraphs with a conservative semilattice polymorphism or minordering), and karc digraphs (digraphs with an extended minordering). Specifically, we show that:  Dichotomy for Graphs: MinHOM(H) has a 2V(H)approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a biarc graph), otherwise, it is inapproximable;  MinHOM(H) has a V(H)^2approximation algorithm if H is a biarc digraph;  MinHOM(H) has a V(H)^2approximation algorithm if H is a karc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of V(H).more » « less