2008 · 173 citations · 10 references
EngineeringComputer ScienceElectrical EngineeringAlgorithmsOptimizationWireless CommunicationsAssignment ProblemsCommunication ComplexityCooperative CommunicationDiversity TechniquesNetwork Information TheoryNetwork OptimizationComplexityCooperative RelayingLinear ComplexityPolynomial Time ComplexityPolynomial-time AlgorithmsRelay NetworksRelay-assisted CommunicationSpatial Diversity
Cooperative communications that exploit a relay node’s antenna provide spatial diversity, and the choice of relay node critically influences overall system performance. The study investigates relay node assignment in networks where multiple source–destination pairs compete for a shared pool of relays. A polynomial‑time algorithm employing a linear‑marking scheme is proposed, delivering linear complexity per iteration for efficient assignment. The algorithm is formally proven optimal and exhibits several attractive properties.
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 diversity. 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 network environment, where multiple source-destination pairs compete 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 complexity for each iteration. We give a formal proof of optimality for this algorithm. We also show several attractive properties associated with this algorithm.
10
Capacity theorems for the relay channel
Thomas M. Cover, Abbas El Gamal · IEEE Transactions on Information Theory · 1979 · 4.2K citations