Back to Search
Start Over
Minimum Feedback for Collision-Free Scheduling in Massive Random Access.
- Source :
-
IEEE Transactions on Information Theory . Dec2021, Vol. 67 Issue 12, p8094-8108. 15p. - Publication Year :
- 2021
-
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\ge 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 $k\log (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 $\Theta (\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 \le 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SCHEDULING
*MAXIMA & minima
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731609
- Full Text :
- https://doi.org/10.1109/TIT.2021.3114584