Search for: All records

This work generalizes the Age-of-Information (AoI) minimization problem of update-through-queue systems such that in addition to deciding the waiting time, the sender also chooses over which “channel” each update packet will be served. Different channels have different costs, delays, and quality characteristics that reflect the scheduler’s selections of routing, communications, and update modes. Instead of considering only two channels with restricted parameters as in the existing works, this work studies the general K-channel problem with arbitrary parameters. The results show that both the optimal waiting time and the optimal channel-selection policies admit an elegant water-filling structure, and can be efficiently computed by the proposed low-complexity fixed-point-based numerical method. 

Age-Of-Information (AoI) is a metric that focuses directly on the application-layer objectives, and a canonical AoI minimization problem is the update-through-queues models. Existing results in this direction fall into two categories: The open-loop setting for which the sender is oblivious of the packet departure time, versus the closed-loop setting for which the decision is based on instantaneous Acknowledgment (ACK). Neither setting perfectly reflects modern networked systems, which almost always rely on feedback that experiences some delay. Motivated by this observation, this work subjects the ACK traffic to a second queue so that the closed-loop decision is made based on delayed feedback. Near-optimal schedulers have been devised, which smoothly transition from the instantaneous-ACK to the open-loop schemes depending on how long the feedback delay is. The results quantify the benefits of delayed feedback for AoI minimization in the update-through-queues systems. 

We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the n-bit codeword as input and computes an r*n-bit output for some given r in [0,1]. We consider the scenario where the r*n -bit observation is computationally bounded - the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the (adversarial) channel error/corruption. For all r in [0,1−H(p)] where H(.) is the binary entropy function and p is the adversary’s error budget, we characterize the capacity of the above channel and find that the capacity is identical to the completely oblivious setting (r=0). This result can be viewed as a generalization of known results on myopic adversaries and on channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary. 

In this paper, we consider a status update system, where an access point collects measurements from multiple sensors that monitor a common physical process, fuses them, and transmits the aggregated sample to the destination over an erasure channel. Under a typical information fusion scheme, the distortion of the fused sample is inversely proportional to the number of measurements received. Our goal is to minimize the long-term average age while satisfying the average energy and general age-based distortion requirements. Specifically, we focus on the setting in which the distortion requirement is stricter when the age of the update is older. We show that the optimal policy is a mixture of two stationary, deterministic, threshold-based policies, each of which is optimal for a parameterized problem that aims to minimize the weighted sum of the age and energy under the distortion constraint. We then derive analytically the associated optimal average age-cost function and characterize its performance in the large threshold regime, the results of which shed critical insights on the tradeoff among age, energy, and the distortion of the samples. We have also developed a closed-form solution for the special case when the distortion requirement is independent of the age, arguably the most important setting for practical applications. 

This work considers the problem of sending a 1-bit message over an acyclic network, where the “edge” connecting any two nodes is a memoryless binary-input/symmetric-output (BISO) channel. For any arbitrary acyclic network topology and constituent channel models, a min-cut-based converse of the learning rate, denoted by r^*, is derived. It is then shown that for any r < r^*, one can design a scheme with learning rate r. Capable of approaching the optimal r^*, the proposed scheme is thus the asymptotically fastest for sending one bit over any acyclic BISO-channel network. The construction is based on a new concept of Lossless Amplify-&-Forward, a sharp departure from existing multi-hop communication scheme designs. 

Streaming codes eliminate the queueing delay and are an appealing candidate for low latency communications. This work studies the tradeoff between error probability p_e and decoding deadline ∆ of infinite-memory random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels (SECs). The contributions include (i) Proving pe(∆) ∼ ρ∆^{−1.5}e^{−η∆}. The asymptotic power term ∆^{−1.5} of RLSCs is a strict improvement over the ∆^{−0.5} term of random linear block codes; (ii) Deriving a pair of upper and lower bounds on the asymptotic constant ρ, which are tight (i.e., identical) for one specific class of SECs; (iii) For any c > 1 and any decoding deadline ∆, the c-optimal memory length α^*_c (∆) is defined as the minimal memory length α needed for the resulting pe to be within a factor of c of the best possible p^*_e under any α, an important piece of information for practical implementation. This work studies and derives new properties of α^*_c (∆) based on the newly developed asymptotics. 

The ever-increasing needs of supporting real-time applications have spurred new studies on minimizing Age-of-Information (AoI), a novel metric characterizing the data freshness of the system. This work studies the single-queue information update system and strengthens the seminal results of Sun et al. on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a new fixed-point-based method is proposed with quadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art; (ii) When the distributional knowledge is unavailable (which is the norm in practice), two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty; and (iii) the online schemes also admit a modular architecture, which allows the designer to upgrade certain components to handle additional practical challenges. Two such upgrades are proposed for the situations: (iii.1) The AoI penalty function is also unknown and must be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. The performance of our schemes is either provably optimal or within 3% of the omniscient optimal offline solutions in all simulation scenarios.