Paper Info
Title
Minimizing Age-of-Information with Throughput Constraints in Multi-Path Network Communication.
Abstract
We consider the scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. Our objective is to minimize peak/average Age-of-Information (AoI) subject to throughput requirements. The consideration of batch generation and multi-path communication differentiates us from existing studies. We first show that our AoI minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. Next we prove that minimizing AoI and minimizing maximum delay for a batch of data are roughly equivalent, in the sense that any optimal solution of minimizing maximum delay is an approximate solution of minimizing AoI with bounded optimality loss. We leverage this understanding and design a general approximation framework for our AoI minimization problems. It can adopt any polynomial-time $alpha$-approximation algorithm of the existing maximum delay minimization problem to derive a polynomial-time algorithm for our AoI minimization problems with an approximation ratio of $alpha+mathsf{c}$, where $mathsf{c}$ is a constant determined by throughput requirements. The framework suggests a new avenue for designing approximation algorithms for minimizing AoI in multi-path communications. Extensive simulations over various network topologies validate the effectiveness of our approaches.
Year
Venue
Field
2018
arXiv: Networking and Internet Architecture
Mathematical optimization,Multi path,Computer science,Network communication,Communication source,Network topology,Minification,Throughput,Time complexity,Bounded function,Distributed computing
DocType
Volume
Citations 
Journal
abs/1811.12605
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Qingyu Liu165.14
Haibo Zeng21328.63
Minghua Chen321623.69