Optimal relay assignment for cooperative communications

Recently, cooperative communications, in the form of keeping each node with a single antenna and having a node exploit a relay node’s antenna, is shown to be a promising approach to achieve spatial di-versity. Under this communication paradigm, the choice of relay node plays a significant role in the overall system performance. In this paper, we study the relay node assignment problem in a net-work environment, where multiple source-destination pairs com-pete for the same pool of relay nodes in the network. The main contribution of this paper is the development of a polynomial time algorithm to solve this problem. A key idea in this algorithm is a “linear marking ” mechanism, which is able to offer a linear com-plexity for each iteration. We give a formal proof of optimality for this algorithm. We also show several attractive properties associ-ated with this algorithm