1. CHIRRUP: a practical algorithm for unsourced multiple access.
- Author
-
Calderbank, Robert and Thompson, Andrew
- Subjects
- *
REED-Muller codes , *ALGORITHMS , *MACHINE-to-machine communications , *AD hoc computer networks , *SCIENCE conferences , *SYSTEMS theory , *INTERNET of things - Abstract
Unsourced multiple access abstracts grantless simultaneous communication of a large number of devices (messages) each of which transmits (is transmitted) infrequently. It provides a model for machine-to-machine communication in the Internet of Things, including the special case of radio-frequency identification, as well as neighbour discovery in ad hoc wireless networks. This paper presents a fast algorithm for unsourced multiple access that scales to |${\mathscr{C}}=2^{100}$| (active or non-active) devices (arbitrary |$100$| bit messages). The primary building block is multiuser detection of binary chirps, which are simply codewords in the second-order Reed–Muller code. The chirp detection algorithm originally presented by Howard et al. (2008, 42nd Annual Conference on Information Sciences and Systems) is enhanced and integrated into a peeling decoder designed for a patching and slotting framework. In terms of both energy per bit and number of active devices (number of transmitted messages), the proposed algorithm is within a factor of |$2$| of state-of-the-art approaches. A significant advantage of our algorithm is its computational efficiency. We prove that the worst-case complexity of the basic chirp reconstruction algorithm is |${\mathscr{O}}[nK(\log _2^2 n + K)]$| , where |$n$| is the codeword length and |$K$| is the number of active users. Crucially, the complexity is sublinear in |${\mathscr{C}}$| , which makes the reconstruction computationally feasible—a claim we support by reporting computing times for our algorithm. Our performance and computing time results represent a benchmark against which other practical algorithms can be measured. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF