Optimal selective encoding for timely updates

news story image

An information source generates i.i.d. status updates from a random variable X. Only a portion of the realizations (shown with a square) is encoded into codewords. Update packets that come from the selected portion of the realizations that find the transmitter node idle are sent to the receiver node. Non-selected realizations (shown with a triangle) are always discarded at the transmitter node even if the transmitter node is idle. (Fig. 1 from the paper)

Age of information is a performance metric which quantifies the timeliness of information in networks. It keeps track of the time since the most recent update at the receiver has been generated at the transmitter. Age increases linearly in time; when a new update packet is received, the age drops to a smaller value. Although initial applications of age of information considered queueing networks, scheduling and optimization problems, the concept of age is applicable to a wider range of problems, particularly in autonomous driving, augmented reality, social networks, and online gaming, as information freshness is crucial in all these emerging applications.

In the paper Optimal Selective Encoding for Timely Updates, Professor Sennur Ulukus (ECE/ISR) and her students Melih Bastopcu and Baturalp Buyukates consider a status updating system in which an information source generates independent and identically distributed update packets based on an observed random variable X which takes n values based on a known probability mass function (pmf). The transmitter node implements a selective encoding policy to send the realizations to the receiver node such that only the most probable k update realizations are encoded and the other realizations are discarded. They also consider a case in which the remaining previously discarded n−k realizations are encoded into codewords randomly to further inform the receiver.

The researchers derive the average age for both types of operation and designed age-optimal codeword lengths. Through numerical results they show that the proposed selective policy achieves a lower average age than encoding all the realizations and determine the age-optimal k values for arbitrary pmfs.

Published February 12, 2020