Age of Information in Random Access Channels: Distributed Algorithms for Stochastic Arrivals
Shirin Saeedi Bidokhti
Assistant Professor, Department of Electrical and Systems Engineering, University of Pennsylvania
Time: November 11, 2019 @ 11:15 AM to 12:05 PM
Location: 204 Evans Hall
In applications of remote sensing, estimation, and control, timely communication is not always ensured by high-rate communication. Oftentimes, it is observed that as rate approaches the capacity of a system, delay increases significantly and so does age of information – a metric recently proposed to capture freshness and timeliness of information. This work proposes distributed age-efficient transmission policies for random access channels with M transmitters. In the first part of this work, we analyze the age performance of stationary randomized policies by relating the problem of finding age to the absorption time of a related Markov chain. In the second part of this work, we propose the notion of age-gain of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a distributed manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large M, we prove that
when the total arrival rate is small (below 1/e), slotted ALOHA-type algorithms are asymptotically optimal. As the arrival rate increases beyond 1/e, while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. In the limit of large arrival rates (corresponding to the case in which transmitters are active and always have fresh packets), we prove that the proposed algorithms outperform state of the art techniques with a multiplicative factor of at least two. We conclude that, as opposed to the common practice, it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain.