Abstract
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 rate of the minimum fixed-length common feedback code scales only as klog(e) bits, plus an additive term that scales in n as Θ(loglog(n)) for fixed k . If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires klog(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 . 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.