This paper investigates Automatic Repeat request (ARQ) designs for Physical-layer Network Coding (PNC) systems. Most prior work related to PNC explores its use in Two-Way Relay Channel (TWRC). We have previously found that, besides TWRC, there are many other PNC building blocks-building blocks are simple small network structures that can be used to construct a large network. In some of these PNC building blocks, the receivers can obtain side information through overhearing. Although such overheard information is not the target information that the receivers desire, the receivers can exploit the overheard information together with a network-coded packet received to obtain a desired native packet. This can yield substantial throughput gain. Our previous study, however, assumed what is sent always gets received. In practice, that is not the case. Error control is needed to ensure reliable communication. This paper focuses on ARQ designs for ensuring reliable PNC communication. The availability of overheard Information and its potential exploitation make the ARQ design of a network-coded system different from that of a non-network-coded system. In this paper, we lay out the fundamental considerations for such ARQ designs: 1) we put forth a framework to track the stored coded packets and overheard packets to increase the chance of packet extraction, and derive the throughput gain achieved therefore; 2) we investigate two variations of PNC ARQ, coupled and non-coupled ARQs, and prove that non-coupled ARQ is more efficient; 3) we show how to optimize parameters in PNC ARQ - specifically the window size and the ACK frequency - to minimize the throughput degradation caused by ACK feedback overhead and wasteful retransmissions due to lost ACK.

This paper investigates the fundamental building blocks of physical-layer network coding (PNC). Most prior work on PNC focused on its application in a simple two-way-relay channel (TWRC) consisting of three nodes only. Studies of the application of PNC in general networks are relatively few. This paper is an attempt to fill this gap. We put forth two ideas: a general network can be decomposed into small building blocks of PNC, referred to as the PNC atoms, for scheduling of PNC transmissions; and we identify nine PNC atoms, with TWRC being one of them. Three major results are as follows. First, using the decomposition framework, the throughput performance of PNC is shown to be significantly better than those of the traditional multi-hop scheme and the conventional network coding scheme. For example, under heavy traffic volume, PNC can achieve 100% throughput gain relative to the traditional multi-hop scheme. Second, PNC decomposition based on a variety of different PNC atoms can yield much better performance than PNC decomposition based on the TWRC atom alone. Third, three out of the nine atoms are most important to good performance. Specifically, the decomposition based on these three atoms is good enough most of the time, and it is not necessary to use the other six atoms.

This paper investigates the fundamental building blocks of physical-layer network coding (PNC). Since its conception, PNC has developed into a subfield of network coding investigated by many. Most of the prior work, however, focused on the simplest communication setup in which PNC could be applied, namely the two-way-relay channel (TWRC). Studies of the application of PNC in general networks are relatively few. This paper is an attempt to fill this gap. To do so, we put forth two ideas: 1) For the purpose of scheduling transmissions, a general network can be decomposed into small building blocks of PNC, referred to as the PNC atoms. 2) TWRC is only one of many possible PNC atoms - besides TWRC, we identify eight other PNC atoms. We present formal definitions for the nine PNC atoms. We then formulate the PNC scheduling problem as a linear program based on the decomposition principle stated in 1) above. Two major results of our simulation experiments are as follows. First, under the decomposition framework, the throughput performance of PNC is significantly better than those of the traditional multi-hop scheme and the non-physical-layer network coding scheme - e.g., under heavy traffic volume, PNC can achieve 100% throughput gain relative to the traditional multi-hop scheme. Second, PNC decomposition based on a variety of different PNC atoms yield much better performance than PNC decomposition based on the TWRC atom alone.