Optimizing Age of Information in Status Update Systems using Network Coding: A Graph Search Approach

Providing reliable and performant information exchange is essential for the success of emerging Networked Control Systems (NCSs) such as vehicular platooning, distributed automation in smart grids or general industry automation. Since control agents have to exchange local measurement data to collectively control the physical system, the timely and frequent dissemination of updates is the main objective for the underlying communication network. However, periodically delivering information from each node to all other nodes in a timely manner is a challenging task, especially in multi-hop networks. In this work we investigate the potential gains of using network coding in terms of Age of Information (AoI). In network coding, intermediate nodes may combine data packets bit-wise and thus achieve higher network capacity. However, to keep decoding delays low, schedules using coded transmissions have to be carefully designed. AoI-optimal transmission schedules are calculated using a novel graph search formulation which allows for efficient solving of the generally NP-hard scheduling problem. Furthermore, a heuristic for calculating network coding schedules for large networks is proposed. Extensive evaluations demonstrate the fitness of the graph search and heuristic formulation and showcase potential AoI gains of up to 38.9%.