User Pairing for Capacity Maximization in Cooperative Wireless Network Coding

In this paper, we consider a network-coded cooperative wireless network, where users mutually pair among themselves to realize network coding. We consider a multi-user environment, where users transmit to a common destination in the absence of dedicated relays. Two nodes constituting a pair periodically swap the roles of the source and relay to mutually achieve spatial diversity. As such, conditioned on the successful detection of the source´´s packet, a networkcoded packet is formed at the relay by a linear combination of its own packet and the source´´s packet. A single transmission of this network-coded packet therefore helps both nodes to achieve diversity gain. In this work, we address the important problem of the mutual pairing of users, which directly governs the overall network performance. We first propose an optimal user pairing algorithm in order to maximize the total network capacity. To simplify the pairing process, we subsequently propose computationally simpler, heuristic user pairing schemes. In particular, we propose max-max pairing to maximize the network capacity, and max-min pairing to minimize the outage probability. Performance analysis of the proposed optimal and heuristic user pairing schemes is performed in terms of the average capacity, average outage probability, and user-fairness.