Optimum Location-Based Relay Selection in Wireless Networks

In wireless networks with large geographical coverage, direct communication links suffer from high propagation losses with distance [3]. To overcome this performance impediment as well as to ensure connectivity in classical and emerging wireless systems, dual-hop communication or cooperative relaying is considered to be an effective transmission and network deployment strategy from a system design point-of-view [4, 5, 6, 7]. At the link level, the classical one-way relay channel supports information flow in one specified direction over potentially shorter transmission distances when compared with direct transmissions. This classical relay channel was originally proposed and studied by van der Meulen in [8]. Cover and El Gamal derived the capacity theorems for Gaussian and certain discrete memoryless relay channels in [9]. They also obtained an achievable lower bound to the capacity of the general relay channel. Subsequently, these results are extended to networks with many relays, multiple antennas (in the form of approximations with bounded capacity gap) and cooperation architectures [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28].

The notable benefits of relays in wireless communications are increase in network capacity and transmission diversity [16, 17, 18, 19], improved energy efficiency (measured in bits per unit energy) [24, 25, 26] and decrease in network deployment costs [4, 29]. These benefits have already been recognized by the wireless industry, and the possibility of deploying relays for multi-hop communications in emerging wireless systems was included in the latest proposals for LTE-A standards [30, 31]. Two apparent major design problems encountered in industry-grade wireless relay network deployments are, besides link-level capacity optimization, relay selection (due to implementation constraints limiting the number of simultaneous relay connections) and relay placement. Some recent studies showed that significant system-wide performance gains due to optimization over these design degrees-of-freedom can be achieved [32, 33, 34, 35]. However, these aspects are usually eclipsed by the mainstream fixed-relay capacity optimization at the link level, e.g., see the recent surveys [7, 36] and the references therein.

In this paper, we focus on the optimum relay selection problem for randomly deployed single-antenna decode-and-forward (DF) relays connecting source and destination nodes located at arbitrary positions in $\mathbb{R}^{2}$. An example network configuration is illustrated in Fig. 1. In wireless communications, the fading and location processes driving the network capacity and outage events usually vary at different time-scales. For example, the phase of the received electromagnetic waves can change significantly over millisecond intervals, while the magnitude changes are substantial over time intervals in the order of seconds or minutes [3, 37]. By carefully separating the time-scale of changes in fading and location processes, we characterize the key distance balancing and minimum norm (with respect to the mid-point between source and destination nodes) properties for the optimum relay location. We derive the distribution of the channel quality indicator (CQI) at the optimum relay node, which leads to the characterization of the best achievable average rates and the minimum outage probability for the resulting class of two-hop wireless communications paths with optimization over the relay selection dimension. These results hold for general fading distributions and non-increasing path-loss models decaying to zero.

The time-scale separation approach we adopt for fading and location processes in this paper is motivated by the practical constraints to rule out the prohibitive relay switching rates due to changes in the fading process. In essence, it is similar to the meta-distribution calculations recently introduced for wireless network performance analysis [38, 39, 40]. In most parts of the paper, we focus on a homogeneous Poisson point process (HPPP), which we denote by $\Phi$, with intensity $\lambda>0$ for relay locations. This assumption leads to an insightful analytical structure exposing fundamental dynamics for relay selection. In addition, the uniform relay distribution was also proven to be the optimum configuration for relay placement under some operating regimes such as high signal attenuation as observed in millimeter wave (mmWave) frequency bands [35].¹¹1It is well-known that an HPPP can be obtained as the limiting process of a sequence of collection of uniformly distributed points over growing subsets of Euclidean spaces [41]. The generalization of the key results to non-homogeneous PPPs is provided in Section IX, alongside other important extensions such as full-duplex operation (FD) and heterogeneity among the network nodes.

An important aspect of the optimum relay selection problem studied in this paper is the feedback load required to find the solution. As such, the source node (or, a central entity in this regard) requires the knowledge of all relay locations to make the optimum relay selection decision, which presents a major design hurdle for practical network deployments with large numbers of relays. To circumvent this feedback bottleneck, we also develop a low-complexity selective distributed-feedback relay selection policy that requires feedback only from a small number of relays on average.

The proposed feedback mechanism is fully distributed since the relay nodes utilize only their local information to decide whether they feed back or not. The relay selection is still performed centrally but with significantly reduced feedback. We show that the number of relays feeding their CQIs back to the source node for relay selection obeys to a Poisson distribution with a certain mean whose analytical form is completely characterized. We obtain the average rate and outage probability attained by the proposed selective distributed-feedback relay selection policy, and show that it is enough to multiplex only five relays over the feedback channel to achieve almost the same performance as the all-feedback scenario. From an implementation and system-design point of view, this finding presents a massive reduction in feedback load with a negligible loss in communications performance.

The key parameter to obtain the best achievable rates and minimum outage probability with optimized relay selection is the CQI at the optimum relay node, which we denote by $\Gamma_{\rm opt}$. $\Gamma_{\rm opt}$ is determined by minimization of an appropriately defined relay selection function over all relay locations in $\Phi$. An important result of this paper is the derivation of the distribution of $\Gamma_{\rm opt}$. In particular, its cumulative distribution function (cdf) is shown to be

with $d$ being the half-distance between source and destination nodes. The network performance limits are simply the appropriate integrals of the $\Phi$-measurable conditional data rates, for which we obtain a single-parameter characterization in the proof of Lemma 1, with respect to $F_{\Gamma_{\rm opt}}\left(\gamma\right)$ on $\mathbb{R}_{+}$. As explained in Section VI in detail, the tail distribution of $\Gamma_{\rm opt}$ decays to zero exponentially and all the moments of $\Gamma_{\rm opt}$ are finite. Further, it is also shown that $\Gamma_{\rm opt}$ converges in distribution to $d$ as $\lambda\rightarrow\infty$.

The previous work on relay selection in random spatial networks is very limited, e.g., see [42, 43, 44, 45, 46, 47, 48, 49, 50, 51]. These papers mostly focus on sub-optimum heuristic strategies for selecting relay nodes such as random and closest-to-source relay selection. The relay nodes selected by the sub-optimum strategies in previous work, as expected, do not possess the fundamental properties of the optimum one that governs the functional form of the distribution of $\Gamma_{\rm opt}$ given above. These are the distance balancing and minimum norm properties of the optimum relay location. It is currently unknown how close a sub-optimum strategy that does not have these properties to the optimum one. To address this gap in the literature, we obtain a sufficient condition and associated optimality probabilities for a relay selection policy satisfying only one of these fundamental properties to be the optimum selection in Theorems 1, 2 and 3. These results reveal the analytical dependence of relay selection optimality on the network parameters such as relay node intensity, and provide design guidelines for when a sub-optimum policy can be used with small performance loss. To the best of our knowledge, our work in this paper is the first study that rigorously and thoroughly investigates the optimum relay selection problem with randomly deployed relay nodes, and derives the fundamental performance limits for multi-hop relay channels with optimized relay selection.

The selective distributed-feedback relay selection policies with autonomous feedback decision computation at relay nodes are studied in Section VII of the paper. An important result in this part is to show that the total feedback load with threshold-based selection obeys a Poisson distribution with mean $\mu\left(T\right)$ given by

where $T$ is the threshold value with which each relay compares its local CQI to decide to feed back or not. It is seen that $\mu(T)$ is a continuous monotone increasing function of $T$ with $\mu(d)=0$ and $\lim_{T\rightarrow\infty}\mu(T)=\infty$. Hence, any given average feedback load can be met by a threshold value by the intermediate value theorem. Further, based on this statistical characterization of the feedback load, we see that the probability of having at least one relay node feeding its CQI back to the source node is equal to $1-{\rm e}^{-\mu(T)}$. Hence, we achieve the same rate and outage performance achieved by the all-feedback strategy with probability at least $0.99$ if we use a selective distributed-feedback relay selection policy with $\mu(T)=5$. The exact characterization of rate and outage with selective feedback is provided in Theorems 6 and 7.

Two significant, as well as surprising, operating regimes for outage probability with selective feedback emerging in Theorem 7 are feedback-limited and rate-limited regimes. To the best of our knowledge, this is the first paper that formally characterizes these operating regimes for the relay selection problem. In particular, the feedback constraints in the feedback-limited operating regime are so tight that we have the same outage probability with or without fading. On the other hand, in the rate-limited operating regime, the target data rate is set so high that we achieve the same outage probability for the all-feedback and selective feedback cases. These operating regimes are discussed in detail in Section VII, with illustrative numerical examples provided in Section VIII.

Paper Organization: The rest of the paper is organized as follows. In Section II, we compare and contrast our findings in this paper with relevant previous work in the literature. In Section III, we formally present our system model, the notion of relay selection policy and associated performance metrics to evaluate the relay-aided wireless network performance with optimized relay selection. The optimum relay selection problem is introduced in Section IV. In this section, we also obtain a single-parameter characterization for $\Phi$-measurable conditional data rates, which underpins most of our analysis by exposing the dependence between the CQI at the selected relay node and the resulting network performance. We discuss the fundamental properties that have to be possessed by the optimum relay node in Section V as well as obtaining a sufficient condition and optimality probabilities for when a relay selection policy possesses only one of these properties.

The best achievable data rates and the minimum outage probability attained by the optimum relay selection policy are derived in Section VI. In this section, we mostly focus on the Rayleigh faded wireless medium for obtaining analytical expressions for network performance, but the same analysis continues to hold for any fading distribution without loss of generality. in Section VII, we put forward the optimum relay selection problem with selective distributed-feedback, obtain a statistical characterization for the total feedback load in the network and derive the resulting network performance with limitations on the average total feedback load. An extensive numerical study is presented in Section VIII to illustrate the main findings of the paper. We provide the extensions of our analysis to full-duplex relays, non-homogeneous PPPs and more heterogeneous communications scenarios with different signal-to-noise ratio (${\sf SNR}$) values at relays and the destination node in Section IX. Finally, Section X concludes the paper. Most of our proofs are relegated to Appendices A-I for the sake of exposition.

Notation: The main notation being used throughout the paper is as follows, with some remaining notation introduced later in the paper when needed. We use boldface, upper-case and calligraphic letters to represent vector quantities, random variables and sets, respectively. We use $\mathbb{R}$, $\mathbb{N}$, $\mathbb{C}$ and $\mathbb{R}^{2}$ to denote the real, natural and complex numbers, and the two-dimensional Euclidean space, respectively. $|x|$ denotes the absolute value of a scalar quantity $x$ (real or complex), whereas $\|\boldsymbol{x}\|$ is used to measure the canonical Euclidean norm of a vector quantity $\boldsymbol{x}$. The expected value of a random variable $X$ is denoted by $\mathsf{E}\left[X\right]$. The probability of an event $\mathcal{E}$ is denoted by $\mathsf{Pr}\left(\mathcal{E}\right)$. We use $\mathsf{1}_{\left\{\cdot\right\}}$ to indicate the indicator function of relevant events and mathematical conditions.

The capacity bounds and outage performance of relay networks without explicit modeling of relay locations are well investigated in the literature [29, 52, 53, 54, 55, 56, 57]. In this body of work, the channel states are either fixed and known values, or randomly generated without any modeling of variations in the link signal-to-noise-ratio (${\sf SNR}$) as a function of relay locations. The papers such as [29, 52, 53] adopted a communication-theoretic perspective to design single and multiple relay selection strategies, maintaining the full cooperative diversity. The analysis is based on the outage probability and error rate over fading channels. In particular, it was shown in [52], for the case without a direct link over Rayleigh fading channels, that the best-relay selection strategy achieves full diversity with an outage probability asymptotically decaying to zero according to $\mathsf{SNR}^{-n}$, where $n$ is the number of relays in the network.

Shannon capacity approximations for the Gaussian $n$-relay diamond networks were obtained in [54, 55, 56]. The authors in [54] developed a noisy network coding scheme achieving a sum rate within $1.5$ bits/s/Hz of the cut-set upper bound for the single relay case. In [55], Avestimehr et al. used a deterministic approach to approximate the network capacity of single-relay and two-relay Gaussian diamond networks within $1$ bits/s/Hz. The cut-set upper bound was shown to be within $1.96(n+2)$ bits of network capacity by using noisy network coding arguments for the $n$-relay case in [56]. The papers [34, 57] developed a network simplification approach by characterising what fraction of total network capacity can be maintained by using only a subset of $k$ relays, out of $n$ available relays in the network. It was shown in [34] that every subset of $k$ relays can at most provide approximately a fraction $k/(k+1)$ of the total capacity with full-duplex relays. The similar results were extended to the half-duplex case in [57].

Our approach and results differ from this body of work in that we explicitly model the relay locations in the current paper. By doing so, we obtain the best achievable average rates and the minimum outage probability for the resulting class of two-hop wireless communications paths by optimizing over the relay selection dimension. Our results hold for general non-increasing path-loss models decaying to zero, and for general fading distributions in some cases.

The outage and rate performance of relay networks with explicit modeling of relay locations are also investigated in the literature [42, 44, 45, 46, 47, 49, 48, 51], usually utilizing sub-optimum techniques for relay selection to have analytical tractability. In this body of work, the relay locations are modeled as points of a spatial point process. The papers such as [45, 49, 48] investigated the relay network performance under the heuristic closest-to-source and mid-point relay selection policies. The authors in [42] considered the relay selection problem from a pre-defined quality-of-service region to minimize the outage probability but they ignored the dependence between source-relay and relay-destination links while calculating the end-to-end network outage performance. In [44], they obtained integral expressions for the outage probability in amplify-and-forward relay networks. The papers [46, 47, 51] considered the relay selection problem to maximize the relay-destination ${\sf SNR}$ values. This approach is effectively equivalent to the sub-optimum closest-to-destination relay selection policy.

The papers such as [49, 47, 45] considered interference in their relay network model. However, the relay selection policies in these papers do not depend on the network interference level. This is because the network interference introduces a coupling between local relay selection processes at the interfering source-destination links, which makes the optimum multi-user multi-relay selection problem intractable. It also becomes prohibitively hard, even for sub-optimum heuristics taking interference into account for relay selection, to present an accurate statistical characterization of the CQI at the selected relays due to the inter-dependence between local relay selection processes, which does not lead to insightful fundamental expressions for the network performance metrics of interest.

In this paper, different from the previous work on randomly deployed relay networks, we take a more fundamental approach and investigate the performance of the optimum relay selection policy for general path-loss models when there is no direct link between source and destination nodes. We derive structural properties being possessed by the optimum relay selection policy. Moreover, we consider distributed selective feedback relay selection policies, non-homogeneous PPPs and different ${\sf SNR}$s at source and relay nodes, which were not considered in the previous work described above. We also consider the time-scale separation between fading and relay location processes cautiously, and identify the effect of such separation on the network performance.

Feedback is an important mechanism in relay networks to facilitate effective relay selection. However, there is only a limited body of work investigating the role of feedback in relay communications [58, 59, 60, 61]. The authors in [58, 59] proposed a compressed sensing approach for joint identity and ${\sf SNR}$ estimation to select relays with strong channel conditions. Despite significant feedback load reduction, the rates achieved by the developed algorithms in these papers are always bounded away from the full feedback scenario. In [60], the author took a different approach to coordinate asynchronous symbol transmissions from multiple relays by using decision feedback equalizers, shown to achieve full diversity. In [61], the authors developed numerical techniques to solve the optimum power allocation problem, maximizing data rates for single-relay channels, under quantized feedback.

In this paper, we focus on solving the feedback problem for relays with random locations by proposing a threshold-based distributed selective feedback relay selection policy to reduce the network feedback load. To the best of our knowledge, there is no prior work addressing this problem when relays are randomly distributed, where availability of relay location and/or channel state information at a central entity or the source node is a common assumption to perform relay selection. This operating assumption requires an excessive feedback load, which does not scale well for large networks. We show that it is enough to multiplex only five relays over the feedback channel to achieve almost the same rate performance as the all-feedback scenario. This is an important reduction in the feedback load from a system-design point of view.

There is a large and growing body of work on routing in random spatial networks [62, 63, 64, 65, 66, 67, 68, 69, 70], to which our results in this paper are also related. This body of work focuses on the evaluation of network layer performance metrics such as end-to-end delay and throughput to assess the efficiency of a given routing protocol. The analysis is usually carried out for fixed rate transmissions with threshold-based detection and ALOHA- or TDMA-type MAC layer. Some models are very specific, focusing on line networks such as [64, 68, 69, 70]. In contrast, we take a more fundamental approach in the current paper by considering the information capacity of cooperative relay channels as the performance metric of interest. This change in the approach also triggers a change in the mathematical analysis, different than the above previous work.

The second fundamental difference between our paper and the previous routing work is that we maximize the “routing” performance of two-hop relay networks by optimizing over the relay selection dimension. The previous routing work fixes the routing protocol such as the $k$-nearest neighbor routing or nearest neighbor routing with minimum bounded progress (i.e., called quasi-equal distance (QED) routing in [70]). To the best of our knowledge, there is no prior paper in the routing literature optimizing the selection of intermediate nodes (from a random spatial field) to maximize the network performance, as we analyzed thoroughly in the current paper.

We consider a relay-aided spatial wireless network in $\mathbb{R}^{2}$, as illustrated by Fig. 1. The network contains a source-destination pair having arbitrary locations $\boldsymbol{x}_{\rm s}\in\mathbb{R}^{2}$ (source node) and $\boldsymbol{x}_{\rm d}\in\mathbb{R}^{2}$ (destination node). The locations of potential DF relay nodes in the network are given by $\varphi=\left\{\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots\right\}$, where $\boldsymbol{x}_{i}\in\mathbb{R}^{2}$ represents the $i$th DF relay location for $i\in\mathbb{N}$. We will always assume that $\varphi$ is a locally finite set, i.e., there are only finitely many relays in every bounded subset of $\mathbb{R}^{2}$. For performance analysis, we will consider the communication scenario in which relay locations are random and determined according to a spatial homogeneous Poisson point process (HPPP) $\Phi=\left\{\boldsymbol{X}_{1},\boldsymbol{X}_{2},\ldots\right\}$. Hence, $\varphi$ should be interpreted as a particular realization of $\Phi$ below, which will usually be clear from the context unless otherwise stated. Relay-based cellular networks are an important example of this model [71, 72, 4], although our analysis is not restricted to infrastructure-based wireless communications. We assume that the primary aim of the relays is to assist data communication between source and destination nodes without generating any additional traffic, as in the latest proposals for LTE-A standards [30, 31].

For the sake of exposition, we will focus our attention only on the easy-to-implement half-duplex (HD) relaying operation in the remainder of the paper. As explained in Section IX, this assumption will not limit our results in the full-duplex (FD) case [19]. The HD operation in our setup follows the classical resource orthogonalization approach [16], and we consider that half of the degrees-of-freedom available in the wireless channel is used by the source node, while the other half is allocated for the relay-destination link. This is usually done through time division multiplexing (TDM) in existing wireless systems when relay and source nodes share the same frequency band [72]. In a relay-aided wireless network setting, the location of the selected relay node is of critical importance to determine the achievable data rates between source and destination. To this end, we examine the network performance under a given relay selection policy, which is formally defined as follows.

Some examples of $\mathcal{P}$ include the ones choosing the relay closest to the source, the relay closest to the destination and the relay closest to the mid-point between source and destination. Our focus below is predominantly on the statistical characterization of the performance of a given relay selection policy $\mathcal{P}$ over a random ensemble of relay locations. For the sake of notational simplicity, we parametrize the relay location selected by $\mathcal{P}$ as $\boldsymbol{x}_{\mathcal{P}}$ in the remainder of the paper, with the understanding that $\boldsymbol{x}_{\mathcal{P}}=\mathcal{P}\left(\varphi\right)$ for any given $\varphi\in\Sigma$. The same meaning is attributed to other variables throughout the paper when we use this parametrization for them as well. The instantaneous rate of information flow from source to destination (in bits/s/Hz) as a function of the relay selection policy $\mathcal{P}$ is given as

where $G$ is a non-negative non-increasing path-loss function decaying to zero, $H_{a,b}\in\mathbb{C}$ is the random fading coefficient between the source, selected relay and destination nodes for $a\in\left\{{\rm s,r}\right\}$ and $b\in\left\{{\rm r,d}\right\}$, and ${\sf SNR}\triangleq\frac{P}{WN_{0}}$ is the signal-to-noise ratio with $P$, $W$ and $N_{0}$ being transmission power, communication bandwidth and noise energy per complex dimension, respectively, [37]. The rate ${\sf r}_{\varphi}\left(\mathcal{P}\right)$ in (5) is achievable for each fading state $\boldsymbol{H}=\left(H_{\rm s,r},H_{\rm r,d},H_{\rm s,d}\right)^{\top}$ by using independent Gaussian codebooks at the source and relay nodes and channel state information (CSI) at the receivers [16].²²2Implicit in this formulation is the assumption of a perfect multiple-access and interference cancellation scheme so that the background noise is the only additive channel distortion at the receivers.

One simplifying assumption that we will make for the rate function ${\sf r}_{\varphi}\left(\mathcal{P}\right)$ in order to pose the optimum relay selection problem for general path-loss models is as follows. We will assume that the signal power received over the longer source-destination link is much smaller than the one received over the shorter relay-destination link. This assumption corresponds to the physical circumstances in which either the direct link between source and destination nodes is severely shadowed by an object in the environment (i.e., $\left|H_{\rm s,d}\right|\approx 0$), or the decay of $G$ with distance is very sharp as in the mmWave communications [72, 71, 4]. It models the multi-hop mode of operation for relay channels [19] as well as the common LTE-A relay deployment scenarios such as dead spot elimination, coverage extension to rural areas and emergency coverage [72, 71, 4].

We will also assume that random fading coefficients $H_{\rm s,r}$ and $H_{\rm r,d}$ change at a much faster time-scale than the network node locations, which is usually the case in typical wireless communication scenarios [3, 73]. In such cases, it is an onerous task, if not practical due to the triggered excessive relay switching rate, for the source node to obtain CSI for all source-to-relay and relay-to-destination channels, and establish a connection to another relay node for handing over the data traffic each time fading coefficients change. Hence, our selection criterion will be based only on relay locations for selecting the relay node, which is also embodied in Definition 1. This approach is reminiscent of the base station selection strategy in cellular networks. This is also the optimum approach when only location information but not the full CSI is available at the source node.³³3We continue to assume the availability of full CSI at the receiver side of each link so that the data rates in (5) are achievable.

For determining the performance of a relay selection policy $\mathcal{P}$, we will use the outage probability and average data rate as our performance metrics [3]. The former one is the common metric to measure the system performance for delay-sensitive data traffic requiring a minimum data rate for successful communications, whereas the latter is more appropriate for when the delay requirement is not stringent and transmitters are allowed to adjust their transmission rates based on the observed path-loss values [74]. We assume for both cases that the permissible decoding delay is large enough to average over the fading process. Then, given $\mathcal{P}$ and the random relay locations $\Phi=\left\{\boldsymbol{X}_{1},\boldsymbol{X}_{2},\ldots\right\}$, the achievable rate over the wireless link connecting the source and selected relay is $\mathsf{E}\left[\log_{2}\left(1+{\sf SNR}\left|H_{\rm s,r}\right|^{2}G\left(\left\|\boldsymbol{x}_{\rm s}-\boldsymbol{X}_{\mathcal{P}}\right\|\right)\right)\big{|}\Phi\right]$, where the expectation is taken only over the randomness due to fading. Similarly, the achievable rate between the selected relay and destination is $\mathsf{E}\left[\log_{2}\left(1+{\sf SNR}\left|H_{\rm r,d}\right|^{2}G\left(\left\|\boldsymbol{X}_{\mathcal{P}}-\boldsymbol{x}_{\rm d}\right\|\right)\right)\big{|}\Phi\right]$.⁴⁴4For the rate between the selected relay and destination, we ignore the term containing $\left|H_{\rm s,d}\right|$ since we assumed $\left|H_{\rm s,d}\right|\approx 0$. If this is not an appropriate modeling assumption, then the relay-destination rate should be interpreted as the rate obtained through a type of selection combining in which the destination takes only the signals from the relay into account for data decoding. If maximum ratio combining is employed at the destination, similar performance analysis continues to hold as discussed in Section VIII. However, we cannot claim the optimality of the proposed relay selection policy for general path-loss models in this case. Hence, we can express the data rate, averaged over the fading process, from source to destination as

which is a function of $\mathcal{P}$ and $\Phi$. Using ${\sf R}_{\Phi}\left(\mathcal{P}\right)$ in (6), the outage probability for delay-sensitive data traffic and the average rate for elastic data traffic for which the variable rate transmission is permissible (e.g., dynamic adaptive video streaming over HTTP [75]) as metrics indicative of the relay-assisted network performance are defined as below.

It is important to note that ${\sf R}_{\rm ave}\left(\mathcal{P}\right)$ defined in (8) should be interpreted as the average of the rate in (6), which is averaged over the random relay locations. It is not the ergodic rate achieved over the long time-horizon for the same source, relay and destination nodes. Rather, the rate in (6) is attained with a different relay node selected by $\mathcal{P}$ for each realization of $\Phi$. In addition, we observe that we can change the order of minimum and expectation operators while going from (5) to (6). This is because the decoding delays permit averaging over the fading process before switching to another relay node. It is more advantageous to minimize expected rates than averaging the minimum of instantaneous rates. This is the waiting-gain we have in (6).

We will start with a set of arbitrary relay locations $\varphi\in\Sigma$ without imposing any statistical structure, and then analyze the case in which relay nodes are randomly distributed over the plane according to an HPPP with intensity $\lambda>0$. Below, $\boldsymbol{w}$ will denote the mid-point between source and destination nodes, i.e., $\boldsymbol{w}=\frac{\boldsymbol{x}_{\rm s}+\boldsymbol{x}_{\rm d}}{2}$, and $d$ will denote the distance from $\boldsymbol{w}$ to $\boldsymbol{x}_{\rm s}$ or to $\boldsymbol{x}_{\rm d}$, i.e., $d=\left\|\boldsymbol{x}_{\rm s}-\boldsymbol{w}\right\|=\left\|\boldsymbol{x}_{\rm d}-\boldsymbol{w}\right\|$. The following simple result formally states the minimum norm property for optimum relay locations. This result also provides a motivation for the mid-point relay selection rule.

Lemma 2 suggests that $\mathcal{P}_{\rm mid}$ possesses one of the key properties for being a solution for (12) since it always chooses the relay node closest to $\boldsymbol{w}$, which is globally the best location to place a relay node without direct link signal reception. However, $\mathcal{P}_{\rm mid}$ does not result in the optimum relay selection for all relay configurations $\varphi\in\Sigma$ since, in addition to its distance from the mid-point between $\boldsymbol{x}_{\rm s}$ and $\boldsymbol{x}_{\rm d}$, the relay’s orientation is also crucial in determining the value of $\widehat{s}\left(\boldsymbol{x}\right)$. That is, the closer the relay location $\boldsymbol{x}$ to the equidistant hyperplane $\mathcal{H}$ between $\boldsymbol{x}_{\rm s}$ and $\boldsymbol{x}_{\rm d}$ is, it better balances the distances between source and destination and leads to a smaller value that $\widehat{s}\left(\boldsymbol{x}\right)$ takes. We will utilize the distance balancing property for optimum relay locations to obtain a sufficient condition under which $\mathcal{P}_{\rm mid}$ is optimum. We formally state this property in the following lemma.

Using Lemma 3, we obtain a sufficient condition for the optimality of $\mathcal{P}_{\rm mid}$ in the next theorem.

For any realization of relay locations, this condition is easy to check since we only need to know the location information of the closest and second closest relay nodes to the mid-point. Now, by considering random relay locations given according to $\Phi$, which is an HPPP having intensity $\lambda>0$ (i.e., $\lambda$ is the average number of relays per unit area), we obtain the probability with which the sufficient condition in Theorem 1 is satisfied.

In the next theorem, we extend the result in Theorem 2 and provide an expression for the probability that $\mathcal{P}_{\rm mid}$ is optimum for Poisson distributed relay locations. Even though it will be more complicated than the expression for $\mathsf{Pr}\left(\mathcal{E}_{\rm suff}\right)$ given in (17), it is the exact expression for the probability $\mathsf{Pr}\left\{\boldsymbol{X}_{\rm mid}=\boldsymbol{X}_{\rm opt}\right\}$, where $\boldsymbol{X}_{\rm mid}\in\Phi$ represents the random location of the relay chosen by $\mathcal{P}_{\rm mid}$.

We note that it is numerically easy to calculate the expectation in (18) by using the probability density function (pdf) of $\boldsymbol{X}_{\rm mid}$. In particular, $\Theta_{\rm mid}$ is uniformly distributed over $\left.\left[0,2\pi\right)\right.$, $\Psi_{\rm mid}=\left\|\boldsymbol{X}_{\rm mid}\right\|$ has the nearest-neighbor pdf $f_{\rm NN}\left(\psi\right)=2\lambda\pi\psi{\rm e}^{-\lambda\pi\psi^{2}}\mathsf{1}_{\left\{\psi\geq 0\right\}}$, and $\Theta_{\rm mid}$ and $\Psi_{\rm mid}$ are independent random variables.

Fig. 2 demonstrates the analytical expressions derived for $\mathsf{Pr}\left(\mathcal{E}_{\rm suff}\right)$ and $\mathsf{Pr}\left\{\boldsymbol{X}_{\rm mid}=\boldsymbol{X}_{\rm opt}\right\}$ in Theorem 2 and Theorem 3 as well as the simulated probability values. Our results in these theorems are correct for all source and destination locations, however we will assume $\boldsymbol{x}_{\rm s}=\left(-d,0\right)$ and $\boldsymbol{x}_{\rm d}=\left(d,0\right)$ to explain our main observations in Fig. 2 without loss of generality. As can be observed in this figure, $\mathsf{Pr}\left\{\boldsymbol{X}_{\rm mid}=\boldsymbol{X}_{\rm opt}\right\}$ decreases as the relay intensity or the separation between source and destination nodes increases. The diminishing behaviour of $\mathsf{Pr}\left\{\boldsymbol{X}_{\rm mid}=\boldsymbol{X}_{\rm opt}\right\}$ as a function of relay intensity arises from the fact that it becomes more likely to find a relay node $\boldsymbol{X}\in\Phi$ with a better distance balancing property, i.e., having angle $\Theta$ close to $\frac{\pi}{2}$ or $\frac{3\pi}{2}$, which is not far away from the mid-point between source and destination, i.e., $\left\|\boldsymbol{X}\right\|\approx\left\|\boldsymbol{X}_{\rm mid}\right\|$, as the relay intensity increases.

For $\boldsymbol{X}\in\Phi$ having the norm $\Psi$ and angle $\Theta$, we can express the relay selection function $\widehat{s}\left(\boldsymbol{X}\right)$ as $\widehat{s}\left(\boldsymbol{X}\right)=\sqrt{\Psi^{2}+2d\Psi\left|\cos\left(\Theta\right)\right|+d^{2}}$. Hence, as the separation between source and destination nodes increases, the relay locations having angles close to $0$ or $\pi$ are penalized more strongly. Since $\mathcal{P}_{\rm mid}$ chooses the relay node based only on the distance to mid-point criterion without considering the distance balancing dimension, it becomes less probable for a relay node selected by $\mathcal{P}_{\rm mid}$ to be optimum when $d$ is large. Correspondingly, the sufficient condition for the optimality of the mid-point relay selection policy is most useful when both the relay intensity and separation between source and destination nodes are small. Overall, despite its analytical convenience for performance evaluation, we observe that $\mathcal{P}_{\rm mid}$ suffers from its “distance balancing ignorant operation” notably, which provides a motivation for an in-depth search for the statistical properties of $\mathcal{P}_{\rm opt}$ in the remainder of the paper.

Remark 1: The performance gap between $\mathcal{P}_{\rm opt}$ and $\mathcal{P}_{\rm mid}$ can be significant in terms of average rate and outage probability depending on the network configuration and signal propagation characteristics. This point will be illustrated numerically in Section VIII.

Remark 2: Using the results in this section and ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm mid}\right)$, we can readily obtain an upper bound on ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$. This upper bound is given by

where $\Delta_{\rm ave}$ is equal to

for the no-fading scenario, and it is equal to

for the Rayleigh fading scenario with the function $P\left(\boldsymbol{x}\right)$ given as in Theorem 3 and the function $f(x)$ defined as $f(x)\triangleq{\rm e}^{x}\text{E}_{1}(x)$, where $\text{E}_{1}(x)$ is the exponential integral given by the identity $\text{E}_{1}(x)=\int_{1}^{\infty}\frac{{\rm e}^{-tx}}{t}{\rm d}t$ for $x>0$. For the Rayleigh fading case, we take $H$ as a circularly symmetric complex Gaussian random variable with unit power, i.e., $H\sim\mathcal{CN}(0,1)$. Hence, $\left|H\right|^{2}$ is an exponential random variable with unit mean, i.e., $f_{\left|H\right|^{2}}(x)={\rm e}^{-x}$. The derivations for the upper bounds above are given in Appendix D. We note that we can calculate ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm mid}\right)$ by averaging (16) with respect to the joint magnitude and angle distribution of $\boldsymbol{X}_{\rm mid}$. Similarly, we can calculate $\Delta_{\rm ave}$ by taking above expectations with respect to the joint magnitude and angle distribution of $\boldsymbol{X}_{\rm mid}$. In the next section, we will characterize the probability distribution of $\widehat{s}\left(\boldsymbol{X}_{\rm opt}\right)$ and obtain an exact expression for ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$.

As explained after the proof of Lemma 1, the conditional data rate, given the relay locations, is equal to

for any relay selection policy. Hence, the key step to obtain analytical expressions for ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$ and ${\sf P}_{\rm out}\left(\mathcal{P}_{\rm opt}\right)$ is to derive the distribution function for $\widehat{s}\left(\boldsymbol{X}_{{\rm opt}}\right)$. For notational simplicity, we define $\Gamma_{\rm opt}\triangleq\widehat{s}\left(\boldsymbol{X}_{{\rm opt}}\right)$. Then, we have

by definition of $\mathcal{P}_{\rm opt}$. That is, $\Gamma_{\rm opt}$ is the minimum value achieved by the relay selection function over $\Phi$. In the next theorem, we provide the cumulative distribution function (cdf) and the pdf of $\Gamma_{\rm opt}$.

There are several important remarks worth to mention about the functional forms of $F_{\Gamma_{\rm opt}}$ and $f_{\Gamma_{\rm opt}}$ given in Theorem 4. Let $g(x)$ be the function defined as $g(x)=x^{2}\operatorname{arcsec}(x)-\sqrt{x^{2}-1}$ for $x\geq 1$. It is easy to see that $g(1)=0$ and $g^{\prime}(x)=2x\operatorname{arcsec}(x)$, which is the first derivative of $g(x)$ with respect to $x$. Since $g^{\prime}(x)>0$ for all $x>1$, we conclude that $g(x)$ is a strictly increasing and positive function of $x$ over $\left(1,\infty\right)$. Further, it can also be seen that $\lim_{x\rightarrow\infty}\frac{g(x)}{x^{2}}=\frac{\pi}{2}$. This shows that the exponents in (22) and (23) are non-positive for all values of $\gamma\geq d$ with the tail of $f_{\Gamma_{\rm opt}}$ decaying according to $\lim_{\gamma\rightarrow\infty}-\frac{\ln\left(f_{\Gamma_{\rm opt}}\left(\gamma\right)\right)}{\gamma^{2}}=\pi\lambda$. Hence, all the moments of $\Gamma_{\rm opt}$ exist although they may not be calculated in closed form. For example, $\mathsf{E}\left[\Gamma_{\rm opt}\right]$ can be obtained numerically by using (22) as below

which cannot be reduced to a closed form.

Secondly, since $g(x)>0$ for all $x>1$, it also holds that $\lim_{\lambda\rightarrow\infty}F_{\Gamma_{\rm opt}}\left(\gamma\right)=1$ for $\gamma>d$ and $\lim_{\lambda\rightarrow\infty}F_{\Gamma_{\rm opt}}\left(\gamma\right)=0$ for $\gamma\leq d$. Therefore, $\Gamma_{\rm opt}$ converges in distribution to a deterministic variable having value $d$. This behaviour coincides with our intuition that there is always a relay in any disc with positive radius centered around the origin when the relay intensity becomes large. Indeed, it can be shown that $\Gamma_{\rm opt}$ converges to $d$ almost surely as $\lambda$ grows without a bound by using Borel-Cantelli lemma [77].

Finally, the proof given in Appendix E for Theorem 4 also reveals the pre-limit distribution for the minimum of relay selection function in the finite network case. Let $\Gamma_{{\rm opt},\tau}=\min_{\boldsymbol{X}\in\Phi\cap\mathcal{B}\left(\boldsymbol{0},\tau\right)}\widehat{s}\left(\boldsymbol{X}\right)$, where $\mathcal{B}\left(\boldsymbol{0},\tau\right)$ is the closed disc centered around the origin $\boldsymbol{0}$ and having radius $\tau$. Then, the cdf $F_{\Gamma_{{\rm opt},\tau}}\left(\gamma\right)$ can be expressed as

where $F_{\Gamma}(\gamma)$ is given by (110) in Appendix D. The convergence of $F_{\Gamma_{{\rm opt},\tau}}\left(\gamma\right)$ to $F_{\Gamma_{\rm opt}}\left(\gamma\right)$ as $\tau$ increases is shown in Fig. 3, which is quite quick.

The optimum multi-user multi-relay selection problem for random spatial networks with interference is not tractable due to coupling between local relay selection processes at the active interfering links. However, the distribution convergence results shown above hints at an efficient sub-optimum heuristic for multi-user multi-relay selection in the presence of interference. If the layer 2 MAC protocol can achieve a certain minimum separation, sufficiently larger than the typical inter-relay distances, between interfering active transmitter-receiver pairs, then the effect of interference can be mitigated to a large extent in the relay selection process and the local relay selection processes can be decoupled from each other. That is, the differential interference at the optimum relay node (chosen by ignoring interference) and at other relays stays below a certain threshold with high probability to overcome the distance advantage provided by the interference-free optimum relay position when the MAC protocol can sufficiently mitigate interference in the vicinity of active communication links. With the suggested decoupling, the results in our paper can be directly applied to approximate the rate and outage performance of the optimum multi-user multi-relay selection policy by running locally optimum relay selection policies, restricted to a small region around each active link as in the interference-free case. This is specifically a co-design issue of MAC and relay selection algorithms, whose complete analysis is not within the scope of this paper.

As seen in (20), an important determinant of the system performance is the random variable $S_{\rm opt}={\sf SNR}\cdot G\left(\Gamma_{\rm opt}\right)$. For a non-negative non-increasing path-loss function, the cdf of $S_{\rm opt}$ can be written as

where $G^{-1}(s)$ is defined as $G^{-1}(s)=\inf\left\{x\geq 0:G(x)\leq s\right\}$. We note that $F_{S_{\rm opt}}(s)=1$ for $s\geq{\sf SNR}\cdot G(d)$ since $G$ is non-increasing and $\Gamma_{\rm opt}\geq d$. We will make use of $F_{S_{\rm opt}}(s)$ to calculate ${\sf P}_{\rm out}\left(\mathcal{P}_{\rm opt}\right)$ below. Further, if $G$ is monotone decreasing and continuous, the pdf of $S_{\rm opt}$ can be written as

which can used to calculate ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$ for the power-law decaying path-loss models such as $G(x)=\frac{1}{x^{\alpha}}$ or $G(x)=\frac{1}{1+x^{\alpha}}$ [78, 79, 80, 81, 82, 83].

Now, we provide expressions for the average rate achieved by the optimum relay selection policy $\mathcal{P}_{\rm opt}$. We will consider both no-fading and Rayleigh fading cases. We recall that we consider a deterministic normalized fading gain with unit power for the no-fading case, and we take $H\sim\mathcal{CN}(0,1)$ for the the Rayleigh fading case.

For ${\sf R}_{\Phi}\left(\mathcal{P}_{\rm opt}\right)$, we can write

where $\text{E}_{1}(x)=\int_{1}^{\infty}\frac{{\rm e}^{-tx}}{t}{\rm d}t$, $x>0$, is the exponential integral as defined in Section V. The expression for ${\sf R}_{\Phi}\left(\mathcal{P}\right)$ for any relay selection policy $\mathcal{P}$ in the Rayleigh fading case was obtained in Appendix D while deriving an upper bound on ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$, which follows from integration-by-parts and change of variables. From Definition 3, the average rate, averaged over relay locations, can be calculated as

where $f_{\Gamma_{\rm opt}}$ is as given in (23). On the other hand, for a monotone decreasing and continuous path-loss function, ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$ can be expressed according to

by using $f_{S_{\rm opt}}(s)$ given in (25). To the best of our knowledge, it is not possible to reduce the integral expressions in (29) and (30) for ${\sf R}_{\rm ave}\left(\mathcal{P}_{\rm opt}\right)$ to a closed-form. However, these single integrals can be evaluated very quickly and efficiently by using standard numerical integration techniques.

Recall that the outage probability ${\sf P}_{\rm out}\left(\mathcal{P}\right)$ for a relay selection policy $\mathcal{P}$ is defined to be the probability that the rate falls below a certain predetermined threshold $\rho$. From Definition 2, we write ${\sf P}_{\rm out}\left(\mathcal{P}_{\rm opt}\right)=\mathsf{Pr}\left\{{\sf R}_{\Phi}\left(\mathcal{P}_{\rm opt}\right)\leq\rho\right\}$ for the optimum relay selection policy $\mathcal{P}_{\rm opt}$. For the no-fading case, by using (28), we have