Joint relay selection and subchannel allocation for amplify-and-forward OFDMA cooperative networks

In this paper, a random combinatorial optimization approach, which we shall refer to as random bipartite graph (RBG) based maximum matching, will be proposed to investigate and solve the joint relay selection and subchannel allocation problem in cooperative networks. By studying the properties of the maximum matching on RBG, the outage probability and diversity-multiplexing tradeoff of the proposed RBG matching method will be obtained. It will then be demonstrated that the outage probability and diversity-multiplexing tradeoff of the RBG matching method for cooperative communication systems with multiple source-destination pairs is the same as that of relay systems with only one source and one destination, i.e., d(r) = N (K + 1)(1 - 2r), where N is the number of subchannels, and K is the number of relay nodes. In addition, it will be shown that the proposed algorithm for maximum matching enjoys a sublinear computation complexity O(N^2/3). Simulation results will illustrate the potential of the proposed RBG matching method as well as verify the theoretical derivations.