Abstract
This paper investigates the relay selection (RS) problem in networks with multiple users and multiple common amplify-and-forward (AF) relays. Considering the overall quality-of-service of the network, we first specify our definition of optimal RS for multiple-user relay networks. Then an optimal RS (ORS) algorithm is provided, which is a straightforward extension of an RS scheme in the literature that maximizes the minimum end-to-end receive signal-to-noise ratio (SNR) of all users. The complexity of the ORS is quadratic in both the number of users and the number of relays. Then a suboptimal RS (SRS) scheme is proposed, which has linear complexity in the number of relays and quadratic complexity in the number of users. Furthermore, diversity orders of both the ORS and the proposed SRS are theoretically derived and compared with those of a naive RS scheme and the single-user RS network. It is shown that the ORS achieves full diversity; while the diversity order of the SRS decreases with the number of users. For two-user networks, the outage probabilities and array gains corresponding to the minimum SNR of the RS schemes are derived in closed forms. It is proved that the advantage of the SRS over the naive RS scheme increases as the number of relays in the network increases. Simulation results are provided to corroborate the analytical results.
Introduction
In cooperative wireless communications, relays serve as critical "digital boosters," enhancing signal reach and reliability by mitigating the effects of fading and physical obstacles. While relay selection (RS) for a single user is a well-understood problem, modern networks increasingly involve multiple users competing for a shared pool of relay resources.
This competition introduces a significant challenge: if multiple users attempt to utilize the same "best" relay simultaneously, a simple first-come, first-served approach—often termed Naive RS—can lead to severe performance degradation for users lower in the priority queue. Such bottlenecks can compromise the network's overall quality of service. Furthermore, finding the globally optimal pairing for $N$ users and $N_r$ relays is computationally intensive. This research defines optimality in multi-user settings and proposes algorithms that balance signal quality with computational efficiency.
Relay Selection Methodologies
The study focuses on Amplify-and-Forward (AF) relays and introduces two primary selection schemes designed to manage user competition effectively.
Optimal Relay Selection (ORS)
The ORS algorithm aims to maximize the minimum Signal-to-Noise Ratio (SNR) across all users in the network. By focusing on the "weakest link," the ORS ensures a high level of fairness and overall network reliability. The algorithm utilizes a linear marking mechanism and an iterative deletion process to guarantee a unique, optimal solution. However, this optimality comes at a cost; the computational complexity is quadratic, denoted as $O(N^2 N_r^2)$.
Suboptimal Relay Selection (SRS)
To address the needs of large-scale networks where ORS might be too slow, the authors propose the SRS scheme. This algorithm operates sequentially but employs a "smallest-best" priority logic. Instead of letting users pick their best relay in an arbitrary order, the SRS identifies which user's best available relay is the weakest among all users and allows that user to select first. This prevents the most disadvantaged users from being left with no viable options.
The SRS scheme significantly reduces computational overhead, achieving linear complexity in terms of the number of relays ($O(N^2 N_r)$).
Performance Analysis and Key Insights
The researchers evaluated these schemes using mathematical derivations for outage probability and array gain, alongside Monte Carlo simulations under Rayleigh fading conditions. Several key insights emerged:
- Resilience of Diversity: A major finding is that ORS achieves full diversity order ($N_r$). This indicates that with optimal selection, the network's reliability improves as if each user had exclusive access to all relays, despite the inherent competition.
- The Competition "Power Tax": While diversity order remains high for ORS, the network experiences a hit in array gain (a horizontal shift in the performance curve). Competition effectively acts as a power tax, requiring higher transmit power to achieve the same reliability as a single-user network.
- SRS vs. Naive RS: Both SRS and Naive RS achieve a lower diversity order of $N_r - N + 1$. However, SRS provides significantly better array gain than the Naive approach. The advantage of SRS over Naive RS actually increases as the number of relays in the network grows.
Conclusion and Future Work
This paper demonstrates that while multi-user competition for relays introduces complexity and performance trade-offs, intelligent selection algorithms can maintain high network reliability. The ORS scheme provides a benchmark for full diversity, while the SRS scheme offers a practical, high-performance alternative for larger networks.
Future research directions include adapting these schemes for decentralized networks where global Channel State Information (CSI) is difficult to obtain. Additionally, extending these strategies to non-homogeneous environments (where users are at varying distances from the relay cluster) and different relaying protocols, such as Decode-and-Forward (DF), remains an important area for further study.
Summary updated