CHIRRUP: a practical algorithm for unsourced multiple access
Authors:
- Robert CalderbankRCRobert Calderbank
- Andrew ThompsonATAndrew Thompson
Preprint
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 (IoT), including the special case of radio-frequency identification (RFID), as well as neighbor discovery in ad hoc wireless networks. This paper presents a fast algorithm for unsourced multiple access that scales to $2^{100}$ 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. 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 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 $\mathcal{O}[nK(\log_2 n + K)]$, where $n$ is the codeword length and $K$ is the number of active users, and we report computing times for our algorithm. Our performance and computing time results represent a benchmark against which other practical algorithms can be measured.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- A Coupled Compressive Sensing Scheme for Unsourced Multiple Access2018
- On Frame Asynchronous Coded Slotted ALOHA: Asymptotic, Finite Length, and Delay AnalysisIEEE Transactions on Communications, 2016
- Toward Massive, Ultrareliable, and Low-Latency Wireless Communication With Short PacketsProceedings of the IEEE, 2016
- Five disruptive technology directions for 5GIEEE Communications Magazine, 2014
- Asynchronous code-division random access using convex optimizationPhysical Communication, 2012
- Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHAIEEE Transactions on Communications, 2010
- Exploiting Sparse User Activity in Multiuser DetectionIEEE Transactions on Communications, 2010
- Why Gabor frames? Two fundamental measures of coherence and their role in model selectionJournal of Communications and Networks, 2010
- Neighbor discovery in wireless networks: A multiuser-detection approachPhysical Communication, 2010
- Characterization of Zak Space Support of a Discrete ChirpIEEE Transactions on Information Theory, 2007