CHIRRUP: a practical algorithm for unsourced multiple access
Authors:
Top Cited Papers
- 5 December 2019
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 9 (4) , 875-897
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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- SPARCs and AMP for Unsourced Random Access2019
- Low complexity schemes for the random access Gaussian channel2017
- 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
- Coded Slotted ALOHA: A Graph-Based Method for Uncoordinated Multiple AccessIEEE Transactions on Information Theory, 2015
- Five disruptive technology directions for 5GIEEE Communications Magazine, 2014
- Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHAIEEE Transactions on Communications, 2010
- A fast reconstruction algorithm for deterministic compressive sensing using second order reed-muller codes2008
- Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Schemefor Satellite Access Packet NetworksIEEE Transactions on Wireless Communications, 2007
- ALOHA packet system with and without slots and captureACM SIGCOMM Computer Communication Review, 1975