Minimum Feedback for Collision-Free Scheduling in Massive Random Access
share
Consider a massive random access scenario in which a small set of k active users out of a large number of n potential users need to be scheduled in b≥ k slots. What is the minimum common feedback to the users needed to ensure that scheduling is collision-free? Instead of a naive scheme of listing the indices of the k active users in the order in which they should transmit, at a cost of klog(n) bits, this paper shows that for the case of b=k, the minimum fixed-length common feedback code requires only klog(e) bits, plus an additive term that scales as Θ(loglog(n)). If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires k log(e) bits, but the dependence on n can be reduced to O(1). When b>k, the number of feedback bits needed for collision-free scheduling can be significantly further reduced. Moreover, a similar scaling on the minimum feedback rate is derived for the case of scheduling m users per slot, when k ≤ mb. Finally, the problem of constructing a minimum collision-free feedback scheduling code is connected to that of constructing a perfect hashing family, which allows practical feedback scheduling codes to be constructed from perfect hashing algorithms.
READ FULL TEXT