On the Coded Packet Relay Network in the Presence of Neighbors: Benefits of Speaking in a Crowded Room

This paper studies the problem of optimal use of a relay for reducing the transmission time of data packets from a source to a destination using network coding. More importantly, we address an effect that is typically overlooked in previous studies: the presence of active transmitting nodes in the neighborhood of such devices, which is typical in wireless mesh networks. We show that in systems with a fair medium access control mechanism (MAC), the use of a relay in a crowded medium brings forth considerable and unforeseen improvements, including up to 3.5x gains in terms of throughput compared to using only the direct link in some of our examples, and a considerable extension of the operating region where using a relay is beneficial. The problem is formulated as a Markov Decision Process (MDP) and numerical results are provided comparing simple, close-to-optimal heuristics to the optimal scheme.