CHIRRUP: a practical algorithm for unsourced multiple access
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 id...
| Glavni autori: | , |
|---|---|
| Format: | Journal article |
| Jezik: | English |
| Izdano: |
Oxford University Press
2019
|
| _version_ | 1826303786320134144 |
|---|---|
| author | Calderbank, R Thompson, A |
| author_facet | Calderbank, R Thompson, A |
| author_sort | Calderbank, R |
| collection | OXFORD |
| description | 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 C=2100 (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 O[nK(log22n+K)], where n is the codeword length and K is the number of active users. Crucially, the complexity is sublinear in 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. |
| first_indexed | 2024-03-07T06:07:59Z |
| format | Journal article |
| id | oxford-uuid:ee7f12d1-21ab-4fa4-bdfc-c09f36e77cc4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:07:59Z |
| publishDate | 2019 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:ee7f12d1-21ab-4fa4-bdfc-c09f36e77cc42022-03-27T11:33:23ZCHIRRUP: a practical algorithm for unsourced multiple accessJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ee7f12d1-21ab-4fa4-bdfc-c09f36e77cc4EnglishSymplectic Elements at OxfordOxford University Press2019Calderbank, RThompson, AUnsourced 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 C=2100 (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 O[nK(log22n+K)], where n is the codeword length and K is the number of active users. Crucially, the complexity is sublinear in 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. |
| spellingShingle | Calderbank, R Thompson, A CHIRRUP: a practical algorithm for unsourced multiple access |
| title | CHIRRUP: a practical algorithm for unsourced multiple access |
| title_full | CHIRRUP: a practical algorithm for unsourced multiple access |
| title_fullStr | CHIRRUP: a practical algorithm for unsourced multiple access |
| title_full_unstemmed | CHIRRUP: a practical algorithm for unsourced multiple access |
| title_short | CHIRRUP: a practical algorithm for unsourced multiple access |
| title_sort | chirrup a practical algorithm for unsourced multiple access |
| work_keys_str_mv | AT calderbankr chirrupapracticalalgorithmforunsourcedmultipleaccess AT thompsona chirrupapracticalalgorithmforunsourcedmultipleaccess |