Code Design Principles for Ultra-Reliable Random Access with Preassigned Patterns
Pages 2604 - 2608
Abstract
We study medium access control layer random access under the assumption that the receiver can perform successive interference cancellation, without feedback. During recent years, a number of protocols with impressive error performance have been suggested for this channel model. However, the random nature of these protocols causes an error floor which limits their usability when targeting ultra-reliable communications. In very recent works by Paolini et al. and Boyd et. al., it was shown that if each user employs predetermined combinatorial access patterns, this error floor disappears. In this paper, we develop code design criteria for deterministic random access protocols in the ultra-reliability region, and build codes based on these principles. The suggested design methods are supported by simulations.
References
[1]
E. Casini, R. D. Gaudenzi, and O. del Rio Herrero, “Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Scheme for Satellite Access Packet Networks,” IEEE Trans. Wireless Comm., vol. 6, no. 4, pp. 1408–1419, Apr. 2007.
[2]
G. Liva, “Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHA,” IEEE Trans. Comm., vol. 59, no. 2, pp. 477–487, Feb. 2011.
[3]
L. G. Roberts, “ALOHA Packet System With and Without Slots and Capture,” SIGCOMM Comput. Comm. Rev., vol. 5, no. 2, pp. 28–42, Apr. 1975.
[4]
G. Choudhury and S. Rappaport, “Diversity ALOHA - A Random Access Scheme for Satellite Communications,” IEEE Trans. Comm., vol. 31, no. 3, pp. 450–457, Mar. 1983.
[5]
E. Paolini, G. Liva, and A. G. i Amat, “A Structured Irregular Repetition Slotted ALOHA Scheme with Low Error Floors,” in Proc. Int. Conf. on Comm., May 2017, pp. 1–6.
[6]
C. Boyd, R. Vehkalahti and O. Tirkkonen, “Interference Cancelling Codes for Ultra-Reliable Random Access,” Int. J. Wireless Inf. Networks, vol. 25, pp. 422–433, Dec. 2018.
[7]
W. H. Kautz and R. C. Singleton, “Nonrandom Binary Superimposed Codes,” IEEE Trans. Inf. Theory, vol. 10, no. 4, pp. 363–377, Oct. 1964.
[8]
A. Graell i Amat and G. Liva, “Finite-Length Analysis of Irregular Repetition Slotted ALOHA in the Waterfall Region,” IEEE Comm. Lett., vol. 22, no. 5, pp. 886–889, May 2018.
[9]
M. Csu˝rös and M. Ruszinkó, “Single-User Tracing and Disjointly Superimposed Codes,” IEEE Trans. Inf. Theory, vol. 51, no. 4, pp. 1606–1611, Apr. 2005.
[10]
J. Komlos and A. Greenberg, “An Asymptotically Fast Nonadaptive Algorithm for Conflict Resolution in Multiple-Access Channels,” IEEE Trans. Inf. Theory, vol. 31, no. 2, pp. 302–306, Mar. 1985.
[11]
C. Di, D. Proietti, I. E. Telatar, T. Richardson, and R. Urbanke, “Finite-Length Analysis of Low-Density Parity-Check Codes on the Binary Erasure Channel,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1570–1579, June 2002.
[12]
S. Neuwirth, “The Size of Bipartite Graphs with Girth Eight,” ArXiv Mathematics e-prints, Feb. 2001.
[13]
R. G. Gallager, “Low Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. IT-8, p. 21–28, Jan. 1962.
[14]
P. Erdos, P. Frankl, and Z. Furedi, “Families of Finite Sets in which No Set Is Covered by the Union of r Others,” Israel Journal of Math, vol. 51, no. 1-2, pp. 75–89, Dec. 1985.
[15]
C. J. Colbourn and J. H. Dinitz, The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
[16]
B. Vasic and O. Milenkovic, “Combinatorial construction of low density parity check codes for iterative decoding,” IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1156–1176, Jun. 2004.
[17]
A. G. Dyachkov and V. V. Rykov, “Bounds on the Length of Disjunctive Codess,” Problemy Peredachi Informatsii, vol. 18, no. 3, pp. 7–13, 1983.
[18]
C. Boyd, R. Vehkalahti and O. Tirkkonen, “Grant-Free Access in URLLC with Combinatorial Codes and Interference Cancellation”, in Proc. IEEE Global Comm. Conf., Dec. 2018.
[19]
P. Busschbach, “Constructive methods to solve problems of s-surjectivity, conflict resolution, coding in defective memories”, Rapport Interne ENST 84 D005, Dec. 1984.
[20]
G. D. Cohen, “Applications of coding theory to communication combinatorial problems”, Discr. Math., vol. 83, pp. 237–248, Aug. 1990.
Index Terms
- Code Design Principles for Ultra-Reliable Random Access with Preassigned Patterns
Index terms have been assigned to the content through auto-classification.
Recommendations
Coded random access: applying codes on graphs to design random access protocols
The rise of machine-to-machine communications has rekindled interest in random access protocols as a support for a massive number of uncoordinatedly transmitting devices. The legacy ALOHA approach is developed under a collision model, where slots ...
Random access game and medium access control design
Motivated partially by a control-theoretic viewpoint, we propose a game-theoretic model, called random access game, for contention control. We characterize Nash equilibria of random access games, study their dynamics, and propose distributed algorithms (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jul 2019
5716 pages
Copyright © 2019.
Publisher
IEEE Press
Publication History
Published: 07 July 2019
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Jan 2025