Scaling Laws for Age of Information in Wireless Networks

We study age of information in a multiple source-multiple destination setting with a focus on its scaling in large wireless networks. There are n nodes uniformly and independently distributed on a fixed area that are randomly paired with each other to form n source-destination (S-D) pairs. Each source node wants to keep its destination node as up-to-date as possible. To accommodate successful communication between all n S-D pairs, we first propose a three-phase transmission scheme which utilizes local cooperation between the nodes along with what we call mega update packets to serve multiple S-D pairs at once. We show that under the proposed scheme average age of an S-D pair scales as O(n^1/4logn) as the number of users, n, in the network grows. Next, we observe that communications that take place in Phases I and III of the proposed scheme are scaled-down versions of network-level communications. With this along with scale-invariance of the system, we introduce hierarchy to improve this scaling result and show that when hierarchical cooperation between users is utilized, an average age scaling of O(n^α(h)logn) per-user is achievable, where h denotes the number of hierarchy levels and α(h) = 1/3·2^h+1. We note that α(h) tends to 0 as h increases, and asymptotically, the average age scaling of the proposed hierarchical scheme is O(logn). To the best of our knowledge, this is the best average age scaling result in a status update system with multiple S-D pairs.