2020/07/30 by Justin Kang, Wei Yu, Kang, Justin Singh +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Technologies #Algorithm #Binary logarithm #Collision #Combinatorics #Computer network #Computer science #Computer security #Cooperative Communication and Network Coding #Discrete mathematics #FOS: Computer and information sciences #Hash function #Information Theory (cs.IT) #IoT Networks and Protocols #Mathematical optimization #Mathematics #Random access #Scaling #Scheduling (production processes)
paper · pdf · doi:10.48550/arxiv.2007.15497
openalex publication_date 2020/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 k log(e) bits, plus an additive term that scales in n as Θ(log log(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 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. 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.