A slotted ALOHA scheme based on bipartite graph optimization

Bipartite graphs have been often used to describe the structure of iteratively-decodable error correcting codes, and to analyze their iterative decoding performance. This paper deals with the application of bipartite graphs to a different problem. More specifically, the bipartite graph description is applied to the iterative interference cancelation process of a recently introduced random access scheme named contention resolution diversity slotted ALOHA. Contention resolution diversity slotted ALOHA relies on MAC bursts repetition and on interference cancelation to increase the throughput of a classic slotted ALOHA access scheme. The graph representation permits to establish a bridge between the iterative interference cancelation process and the iterative erasure recovery process of graph-based codes. Assuming ideal interference cancelation, it is shown how the use of irregular bipartite graphs allows achieving a throughput close to 0.97 packets/slot with a maximum burst repetition rate equal to 16. The iterative interference cancelation analysis is further extended to the case of non-ideal interference cancelation. A discussion on the normalized efficiency is provided as well, considering the average power used by the different approaches.