---
abstract: 'Leveraging recent progress in physical-layer network coding we propose a new approach to random access: When packets collide, it is possible to recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. The throughput of the proposed strategy is derived and shown to be significantly superior to the best known strategies, including multipacket reception.'
author:
- '\'
bibliography:
- 'IEEEabrv.bib'
- 'randomaccess\_arxiv.bib'
title: 'Random Access with Physical-layer Network Coding'
---

Introduction
============

Reliable Physical-layer Network Coding {#sec:compfw}
======================================

Model and Problem Formulation {#sec:model}
=============================

\[scale=.6\] =\[draw, rectangle,minimum width=10mm,minimum height=10mm\]; =\[draw, circle,inner sep=1pt\]; =\[-latex\];

(-4.8,6) – (-1.2,6); (1.2,6) – (4.8,6);

at (-3,7) ; at (3,7) ;

\[xshift=-5cm,yshift=5cm\] (0,-.5) rectangle (4,.5); in <span>1, 2, 3</span> <span> (,-.5) – (,.5); </span>

\[xshift=1cm,yshift=5cm\] (0,-.5) rectangle (4,.5); in <span>1, 2, 3</span> <span> (,-.5) – (,.5); </span>

(c11) at (-6.5,3) ; (c21) at (-.5,3) ; (c31) at (5.5,3) ; (c12) at (-5.5,3) ; (c22) at (.5,3) ; (c32) at (6.5,3) ;

(g11) at (-8,2.5) ; (g12) at (-4,2.5) ; (g21) at (-2,2.5) ; (g22) at (2,2.5) ; (g31) at (4,2.5) ; (g32) at (8,2.5) ;

(g11) – (c11); (g12) – (c12); (g21) – (c21); (g22) – (c22); (g31) – (c31); (g32) – (c32);

(-3,4.5) – (c11); (3,4.5) – (c12); (-3,4.5) – (c21); (3,4.5) – (c22); (-3,4.5) – (c31); (3,4.5) – (c32);

(pl11) at (-6,2) ; (pl21) at (0,2) ; (pl31) at (6,2) ;

(c11) – (pl11); (c12) – (pl11); (c21) – (pl21); (c22) – (pl21); (c31) – (pl31); (c32) – (pl31);

(pl11) – (-6,1); (pl21) – (0,1); (pl31) – (6,1);

\[xshift=-8cm,yshift=.5cm\] (0,-.5) rectangle (4,.5); in <span>1, 2, 3</span> <span> (,-.5) – (,.5); </span> at (2,0) ;

\[xshift=-2cm,yshift=.5cm\] (0,-.5) rectangle (4,.5); in <span>1, 2, 3</span> <span> (,-.5) – (,.5); </span> at (2,0) ;

\[xshift=4cm,yshift=.5cm\] (0,-.5) rectangle (4,.5); in <span>1, 2, 3</span> <span> (,-.5) – (,.5); </span> at (2,0) ;

(h1) at (-6,-2) ; (h2) at (0,-2) ; (h3) at (6,-2) ;

(-6,0) to (h1); (0,0) to (h2); (6,0) to (h3);

(m11) at (-6,-4) ; (m21) at (0,-4) ; (m31) at (6,-4) ;

(h1) to (m11); (h2) to (m21); (h3) to (m31);

(m11) to (-6,-5.5); (m21) to (0,-5.5); (m31) to (6,-5.5);

(s1) at (-8,-4) ; (s2) at (-2,-4) ; (s3) at (4,-4) ;

(s1) – (m11); (s2) – (m21); (s3) – (m31);

\[xshift=-9cm,yshift=-6cm\] at (-1,0) ; (0,-.5) rectangle (18,.5); in <span>1, 2, ..., 17</span> <span> (,-.5) – (,.5); </span> (6,-.5) – (6,.5); (12,-.5) – (12,.5);

(-3.2,-7) – (-8.8,-7); (2.8,-7) – (-2.8,-7); (8.8,-7) – (3.2,-7);

at (-6,-8) ; at (0,-8) ; at (6,-8) ;

Proposed Strategy {#sec:strategy}
=================

Comparison to Other Strategies {#sec:comparison}
==============================

Numerical evaluation {#sec:results}
====================

Discussion {#sec:discussion}
==========

We have presented an approach to random access that is based on physical-layer network coding. The gist of this strategy is that whenever packets collide, the receiver decodes a linear combination of these packets. The throughput that is achieved by this approach is significantly better than that of other approaches.

The strategy as it is presented in the current paper does not employ feedback from the receiver. It can, however, easily be adjusted to incorporate feedback from the receiver. Consider, for instance, the case that the receiver provides an acknowledgement as soon as it decodes the system of linear equations  and recovers all message substrings from all users. The users can simply continue to transmit random linear combinations of their message substrings until they receive the acknowledgement. This results in a rateless strategy that is particularly easy to implement.

Observe that in our model we allow for strategies that perform coding over blocks. This potentially leads to very large delays. In fact, the proof of Theorem \[th:main\] is based on using many blocks. We believe that the strategy can be incorporated in a practical implementation, for which the number of blocks that is used is small. In particular, we can, in each block transmit a linear combination of only a small number of message substrings and use a sliding window. This will allow to receiver the decode substrings after a small number of blocks. Similar approaches are proposed for broadcast channels in @kumar08arq and in @sundararajan2009tcp.

Finally, the comparison with the arguments in @minero2012random reveals a further interesting insight. Namely, in @minero2012random, an information-theoretic upper bound is presented that applies to any strategy in which <span>*packets*</span> are decoded after every block. It is clear that if we allow to code over many blocks, the throughput can be enlarged beyond this upper bound, but this requires the receiver to store all the physical-layer channel outputs of all the blocks, which is a high price to pay in terms of implementation complexity.

It is interesting to observe that the new strategy introduced in this paper <span>*also*</span> permits to significantly outperform the upper bound presented in @minero2012random. This is not a contradiction since in our strategy, after every block, we allow to decode linear combinations of packets, rather than only entire packets. In this sense, the proposed strategy is a simple version of coding over many blocks, where the receiver can discard the physical-layer channel outputs after every block. Moreover, it should be expected that a careful implementation of the strategy, will only require coding over a small number of blocks.

Acknowledgement
===============

This work was supported in part by the European ERC Starting Grant 259530-ComCom and by NWO grant $612.001.107$.

{'source': 'arXiv_out/1212'}