Advanced
Slotted ALOHA Based Greedy Relay Selection in Large-scale Wireless Networks
Slotted ALOHA Based Greedy Relay Selection in Large-scale Wireless Networks
KSII Transactions on Internet and Information Systems (TIIS). 2015. Oct, 9(10): 3945-3964
Copyright © 2015, Korean Society For Internet Information
  • Received : March 06, 2015
  • Accepted : August 23, 2015
  • Published : October 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Fengchen Ouyang
Jianhua Ge
Fengkui Gong

Abstract
Since the decentralized structure and the blindness of a large-scale wireless network make it difficult to collect the real-time channel state or other information from random distributed relays, a fundamental question is whether it is feasible to perform the relay selection without this knowledge. In this paper, a Slotted ALOHA based Greedy Relay Selection (SAGRS) scheme is presented. The proposed scheme allows the relays satisfying the user’s minimum transmission request to compete for selection by randomly accessing the channel through the slotted ALOHA protocol without the need for the information collection procedure. Moreover, a greedy selection mechanism is introduced with which a user can wait for an even better relay when a suitable one is successfully stored. The optimal access probability of a relay is determined through the utilization of the available relay region, a geographical region consisting of all the relays that satisfy the minimum transmission demand of the user. The average number of the selection slots and the failure probability of the scheme are analyzed in this paper. By simulations, the validation and the effectiveness of the SAGRS scheme are confirmed. With a balance between the selection slots and the instantaneous rate of the selected relay, the proposed scheme outperforms other random access selection schemes.
Keywords
1. Introduction
C ooperative communication can efficiently improve the transmission capacity of a wireless network and guarantee the quality-of-service (QoS) with cooperative relay technique. In a relay service network, poor channel condition users can achieve diversity gain against fading by utilizing a feasible relay node [1] . Due to the above fact, the relay selection protocol plays an indispensable role in offering a network the most suitable relay from a set of candidates. Many well developed works are proposed to examine the relay selection issue [2 - 10] . A summary work is presented in [2] which reviews several conventional single and multiple best relay selection schemes. Since the channel-state-information (CSI) is sometimes estimated inaccurately, its influence on the relay selection is discussed in [3] and [4] . In order to reduce the overhead of the CSI update, low cost selection algorithms are proposed in [5] and [6] which require only limited feedback from each relay. Other schemes combine the selection with resource allocation. In [7] , the relay selection is embedded in a multi-relay Stacklberg game-theoretical model based on the reduction of the network waiting-time. In [8] , a joint optimization of relay selection and resource allocation in OFDMA networks is formulated to minimize the total transmission power. Similar concepts can also be found in [9] and [10] .
As described in previous works, most of the classical relay selection schemes are based on the complete information assumption or involve some information collecting mechanisms to obtain enough knowledge for comparison. Despite the fact that the increase of the relay number can usually offer a user more choices to find a better relay, it also requires extra spectrum or time overhead to collect these relays’ information, which, in turn, harms the time-averaging performance of the network. In a practical scenario such as a decentralized large-scale relay service network, it becomes unrealistic to identify all the relays and select the optimal one by exhaustive comparison. Considering this, our goal is to design a scheme that can rapidly provide the user a desirable relay without any previous information from them.
Random relay selection, a strategy that randomly picks up a relay that satisfies certain constraints, greatly relieves above troubles. Without specific comparison, the random selection requires much less information than the optimal selection schemes while attaining an acceptable outcome. In [11] , a sequential random selection is proposed to increase the network lifetime, and applied with non-reciprocal links and less energy supply. Since the random feature provides each relay an opportunity, its expected performance is therefore influenced by all the candidates, no matter strong or weak. Consequently, the selection should not always be executed among all the relays (especially when the number of the relay node is large), but only among a few “good” ones. Determining the set of the relay candidates (the relays that can meet certain requirement of the user) therefore becomes a vital task for the random selection schemes. In dealing with random distributed relays with the consideration of their transmission capacity, the favored relays should be geographically limited in a certain region. Then the determination of the above relay set can sometimes turn into a stochastic geometry [12] problem. There are several recent random selection schemes based on the stochastic geometry model [13 - 17] . A random selection framework is developed in [13] with a spatial QoS region to determine the set of relays. The selection can switch between the random and the best according to the density of the nodes. A performance comparison among the geometry based, the random, and the optimal selections is presented in [14] . In [15] , a practical scheme that combines the stochastic geometry and ALOHA based selection is evaluated. An energy-efficient multi-hop relay selection scheme is proposed in [16] where a selection sector is chosen whose region is determined by its radius and angle. The similar fan-shaped selection region can also be discovered in [17] where the network simultaneously transmits the information and harvests the energy.
In this paper, a simple but effective random relay selection scheme in the large-scale wireless network is proposed based on: the slotted ALOHA protocol, the greedy selection mechanism, and the geometry-based available relay region. The main contributions are
  • 1) A Slotted ALOHA based Greedy Relay Selection (SAGRS) scheme is proposed in a dynamic large-scale relay service network. During the selection, the user only broadcasts its own transmission request but requires no previous information from relays. The relays compete to access through slotted ALOHA protocol and the user improves its final transmission rate through a “greedy” comparison strategy. The network cost is greatly reduced since the selection is applied in a blind manner.
  • 2) The request of the user and the number of relays satisfying this request is connected with a geometric region named the “Available Relay Region (ARR)”. Specifically, by computing the area of the ARR, the distribution of the available relay number can be determined with the given network parameters. In addition, the optimal access probability adaptive to the relay density and the number of successfully accessed relays is also derived.
  • 3) The expressions of the average number of the selection slots and the selection failure probability in the SAGRS scheme are given. It is shown that with proper settings, the proposed SAGRS scheme can possess both a short selection phase and low failure probability, thus achieving a better performance compared to other selection schemes.
The remainder of the paper is organized as follows: in Section 2, the network model is described. In Section 3, two slotted ALOHA based relay selection schemes are introduced and based on their properties, the proposed SAGRS scheme is developed and evaluated. The available relay region is also formulated for the optimal access probability. In Section 4, an analysis of the performance of the SRGRS scheme is made. In Section 5, simulation results are given with discussion. Finally, in Section 6, the conclusion is drawn.
2. System model
As shown in Fig. 1 , a large-scale relay service network with random positioned relays and the source-destination pair of a user is considered. The relays are uniformly distributed in a 2-D plane with a density of λ r . The source (transmitter) of the user, denoted by U s , intends to transmit its data to the corresponding destination (receiver), denoted by U d . However, as a basic assumption of the proposed model, the direct channel between U s and U d is assumed to be blocked for reasons (e.g. fading, security), which means the successful transmission can only be achieved with the assistance from relays. Owing to this, U s should select relays that satisfy its demand before the procedure of transmission. For the sake of simplicity, it is assumed that the user can only select and utilize at most one relay during the transmission.
PPT Slide
Lager Image
Network model of the SABRS scheme.
The network is decentralized so that no base station coexists for the information collection or broadcast. Due to the scale of the network, nor do the relays exchange their local information with each other, and therefore each individual relay in the proposed network only possesses the knowledge of its own. In addition, since the spectrum resource is scarce in a large-scale network, we assume that all the activities related to one user are limited in one single channel. Under these conditions, it is impossible for every relay to upload its real-time status through the “feedback” channels to the user for comparison.
From above observations, we model the proposed network as a “blind” network for two reasons: (1) for the user, it is blind to all the relays information since it has no access to the relay numbers, nor to their CSI or positions; (2) for the relays, as is previously mentioned, they are blind to each other.
We adopt the selective decode-and-forward (SDF) [1] protocol in transmission so that the relay only forwards the successfully decoded data to the destination. The channel between any two nodes is assumed to be independent and identically distributed (i.i.d.) with path loss and Rayleigh fading. The channel gain is modeled as | h | 2 = χ / d 2 , whereddenotes the distance between the communicating nodes, the path loss factor is 2, and χ is an exponential distributed random variable with unit variance, respectively. Since most of the real world wireless networks are mobile, we further assume that the source and the relays can dynamically change their locations between fixed-length frames to promote the practicality of the model. The frames are assumed to be time-slotted and each frame contains L slots. We also assume that each node is equipped with a positioning module (e.g. GPS) for its real time positions. Under above conditions, a relay serves in one frame may fail to provide even the basic service in next frame if it moves to a remote location or simply refuses to cooperate. As a consequence of this, the mobility of the network requires that periodical selection should be performed in each frame to guarantee reliable transmission.
3. Slotted ALOHA Based Relay Selections
According to the proposed blind scenario and demand of the user, it is known that each frame consists of a selection phase to obtain a relay and a transmission phase to transmit the data with the selected relay. To attain an acceptable time-averaging transmission rate in each frame, the applied relay selection scheme should consider both the instantaneous rate of the relay and the slots consumed in selection. Before the definition and formulation of the SAGRS scheme, first we introduce two related slotted ALOHA based relay selection schemes, namely, the “best” relay selection and the “first” relay selection.
3.0.1 “best” relay selection
The slotted ALOHA based “best” relay selection is the most conventional and yet simple random access selection scheme. As presented in Fig. 2 (a), the length of the selection phase is fixed in all frames. Its basic concept is: after the broadcast & identification slot (same as the SAGRS scheme, which will be developed later), the available relays randomly access the channel in each slot of the selection phase with slotted ALOHA protocol to compete for the selection. If a relay accesses successfully, it will be stored for comparison. At the end of the selection phase, U s compares the instantaneous rates of all the stored relays and chooses the one with the highest rate, which is regarded as the “best” relay, to assist its transmission. It is clear that the “best” here only refers to the best one among the successful accessed relays, but not necessary to be the best among all the relays.
PPT Slide
Lager Image
Frame structure of the “best” and the “first” relay selection scheme.
The simple frame structure of the “best” relay selection makes it an easy implemented scheme. However, the greatest weakness of the scheme is its fixed length of the selection phase. Since none of the selection slots is allowed to be spared for transmission, the selection slots following the one in which the “best” relay successfully accesses will be wasted. Similarly, if no relay accesses successfully during the selection, the scheme cannot spare more slots from the transmission phase either, and thus results in a failed frame.
3.0.2 “first” relay selection
To remedy the defects introduced by the fixed phase length, the “first” relay selection scheme is proposed (e.g. [15] , [18] ). The most significant difference of this scheme from the “best” relay selection is that the selection phase breaks whenever the first relay accesses successfully ( Fig. 2 (b)). As a result, the length of the selection phase becomes flexible and the slots after the successful one can be saved for transmission to further enhance the performance.
Although the “first” relay selection provides a flexible length for the selection phase, it causes a new problem. Since the selection will always end when the first relay is selected (which is also the only relay that can be selected), it does not contain the comparison between relays. This implies that even if the performance of the first relay is not “good enough”, the source has no chance to change for a better one.
3.0.3 SAGRS
Considering the merits and demerits of the above two schemes, the SAGRS scheme is therefore proposed with a frame structure presented in Fig. 3 . By absorbing the concepts of the relay comparison from the “best” relay selection and the flexible selection phase from the “first” relay selection, the scheme further improves the time-averaging rate of the user.
PPT Slide
Lager Image
Frame structures of the SAGRS scheme under three different termination conditions (T1, T2, T3). The instantaneous rate order of the successful relays in all the sub-figures is: A
The beginning of the SAGRS is similar to the “first” relay selection. The difference is, after the first relay accesses successfully, the greedy nature of the scheme drives the user to wait for a better relay. Only when the source believes that the relay it obtained is already good enough, will it ends the selection and proceeds with the transmission.
Since the selections in each frame are performed in the same way periodically, all the following discussions are restricted in one frame and will not be specifically mentioned again. Moreover, for better distinction among relays, we make several notions in Table 1 . As the flowchart in Fig. 4 shows, the selecting procedure of the SAGRS consists of three main parts: Initialization , Identification , and Selection . The mechanism can be described as follows:
Notion for different relay types in the paper
PPT Slide
Lager Image
Notion for different relay types in the paper
PPT Slide
Lager Image
Selection flowchart of the SAGRS scheme in one frame. The scheme consisits of three main parts, while the selection parts consists of four sub-parts.
Initialization : At the beginning of a frame, the user denotes the transmission rate of the current stored relay as R s with an initial value
PPT Slide
Lager Image
= 0 , and denotes the counter of the successful relays as m with an initial value m 0 = 0 . To avoid meaningless waiting cost, we define W as the maximum bearable number of the successive unsuccessful slots, and define l and w as the counters of the total selection slots and the successive unsuccessful slots with initial values l 0 = 1and w 0 = 0 , respectively. It is clear that we have l L and w W .
Identification : In the first slot, U s broadcasts a message containing its minimum required rate
PPT Slide
Lager Image
and its location information to all the relays (U d is a fixed station whose location is assumed to be known by relays). To improve the quality of the selection, the wake up and timing information are also included in the message if needed ( [19] ). After the broadcasting, each relay calculates its own transmission rate R r based on the received message. A relay whose rate satisfies the condition
PPT Slide
Lager Image
marks itself as an available relay and goes on to the next part, otherwise one marks itself as an unavailable relay and quits the rest selection procedure of the current frame.
Selection: After user’s request broadcasting and relays’ self-identification, the available relays (if exist) compete for selection slot by slot until one of the selection termination criterions is triggered. The discussion of the selection part can be further divided into four sub-parts ( I , II , III , and IV ), which are described as:
  • I)Access method: In each new selection slot, every unassessed relays each broadcasts an access message containing its rateRrin a common access probabilitypacc( 0 ≤pacc≤ 1 ), or else it stays silent and only monitors the channel. A successful access is achieved if and only if the slot is accessed by only one relay. Otherwise a collision (or idleness) occurs, and the relays can only compete in the next slot. The selection decision of a successful relay is then judged by theselection criterioninIII.
  • II)Accumulation of counters: The successful relay countermadds 1 whenever a successful access inIis made. The unsuccessful slot counterwwill only be activated after the first relay is successfully stored (a.k.a.m≥ 1). If the access in one slot is not successful, 1 is added tow. Otherwise w returns to 0. The total slot counterladds 1 in each slot.
  • III)Selection criterion: When an access succeeds, the rate of the successful relayRrwill be compared with that of the currently stored oneRs. There are two comparison results as:
  • S1) If the rate of the successful relay is better than the stored one (Rr>Rs), the user replaces the stored relay with the new successful one, updates the rate toRs=Rr, and “greedily” expects more better relays to be achieved in future slots. The selection procedure continues when this condition occurs.
  • S2) If the rate of the successful relay is no better than the stored one (Rr≤Rs), the user thinks the stored relay is already good enough and the selection phase is terminated.
  • IV)Termination criterion: The selection phase terminates if and only if
  • T1) A new successful relay is no better than the stored relay (ConditionS2inIII).
  • T2) The counterwreaches toW.
  • T3) The counterlreaches toL.
As we can figure out, in Condition T3 ( Fig. 3 (c)), if all the slots are used up but no relay access successfully, the selection is considered as a failure. Otherwise the current stored relay is selected in three conditions, then U s transmits its data to U d with the assistance of the selected relay in a two-hop half-duplex manner in the rest slots of the frame.
- 3.1 Formulation of the SAGRS
From the previous descriptions, since the only duty of U s is to broadcast the transmission request, no additional calculation is needed in the selection, which means the procedure of the SAGRS scheme is carried out in a relay self-selecting way. In view of this, there are two main values that an available relay should calculate before the random access selection: the achievable relay rate R r , and the access probability p acc .
- 3.1.1 Achievable relay rate Rr
The outage probability of the user appling the SDF protocol in the proposed scheme is presented as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
denote the outage probabilities of the U s -to-relay (SR) and relay-to-U d (RD) links, respectively. Considering the channel gain | h | 2 , the outage probability of the SR link can be obtained by
PPT Slide
Lager Image
and likewise
PPT Slide
Lager Image
where Γ s = P s / N 0 and Γ r = P r / N 0 denote the Signal-to-Noise Ratio (SNR) of the SR and RD links, while P s and P r denote the transmit power at U s and the relay, respectively. N 0 denotes the noise power. Given the user’s target outage probability ε and substitute (2) and (3) into (1), we have
PPT Slide
Lager Image
Hence the maximum instantaneous relay rate R r of a relay can be obtained by
PPT Slide
Lager Image
Based on the achievable rate R r in (5), the corresponding one-frame time-averaging transmission rate
PPT Slide
Lager Image
of the user is therefore given by
PPT Slide
Lager Image
where X denotes the slots used in the selection. Formulation (6) can also be utilized to calculte the time-averaging transmission rate of the “best” and the “first” selection given their selection slot number, respectively.
- 3.1.2 Access probability pacc
As previously mentioned, each one of the unaccessed relays randomly accesses the channel under the slotted ALOHA protocol, therefore an access probability is needed to maximize the total success probability in each slot. However, since the network is blind, the relays cannot locally determine the optimal access probability without knowing the exact number of their competitors. Nevertheless, as all the relays share the same hardware setting, a common access probability p acc that is probabilistic optimal can be derived if the distribution of the available relay number is known. This distribution can be obtained through the utilization of the ARR.
ARR is defined as a region comprising all the available relays that satisfies the criterion
PPT Slide
Lager Image
. According to Poisson limit theorem, the number of relays that fall in to an ARR S in a uniformly distributed network obeys the Poisson distribution with the variance
PPT Slide
Lager Image
, where |S| denotes the area of S . Given λ r , we can estimate the number of the available relays if |S| can be derived. Reformulate (4), S is thereby a distance set of all the possible available relay locations that satisfy the minimum transmission rate
PPT Slide
Lager Image
at the outage constraint ε as
PPT Slide
Lager Image
In order to calculte the area|S|, in Fig. 5 , a 2-D rectangular coordinate system is set up to measure the distances on the relay plane based on the geographical locations of the user’s nodes. Specifically, U s is at the origin point of the coordinate, while U d locates at the positive x-axis. The coordinates are measured in meters. From (7), if the distances ( d SR , d RD ) of an available relay satisfies the inquality in (7), the relay always locates in(grey area), which is determined by its border. The transmission rate R r of any relay on the border of S equals
PPT Slide
Lager Image
. By the decomposition of the distances the between a relay and the user nodes, we have
PPT Slide
Lager Image
. Substitute them into (7) and get
PPT Slide
Lager Image
where d SD denotes the direct distance between U s and U d . Then we turn the inequality in (8) into an equation to obtain the border function of S . Since the region is symmetric about the x-axis, the area |S| is therefore integrated as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
. The integral interval is from x min to x max . Let y SR = 0 , x min and x max can be obtained by
PPT Slide
Lager Image
Substituting (10) into (9), |S| is thereby presented as
PPT Slide
Lager Image
With further substiution of α and β into (11), we can get the closed-form formulation of
PPT Slide
Lager Image
PPT Slide
Lager Image
Coordinate system on the relay plane. The area |S| is calculated with the interation of its border.
Remark: From (8) and (11), it can be figure out that the border of S is acturally a cirlce with the center at ( α /2,0), and the radious is
PPT Slide
Lager Image
. It is a special case because the path loss factor of the channel is 2 for analytical convenience, and thus influence the distance expression in (7). With higher facters, the shape of the ARR will no longer be a cirlce.
We denote K (|S||) as the number of the relays falling into the ARR (a.k.a. available relays), and the probability of K (|S|) = k is therefore given as
PPT Slide
Lager Image
To obtain the final optimal access probability p acc , the success probability under each value of K (|S|) should be determined first. Since a successful relay does not need to attend the rest random access competition, the number of the unaccessed relays reduces if a successful access is done, which influences its distribution. Based on this result, an unaccessed relay can adjust its access probability against the running down competitors to improve the access result, and the success probability is consequently a function of m . We further denote K u (|S|) as the number of the unaccessed relays, and the probability of K u (|S|) = k m ( k available relays, m successful relays, and k > m ) , denoted as p u ( k m ) , is therefore obtained as
PPT Slide
Lager Image
On the other side, the success probability in one slot among k m unaccessed relays is
PPT Slide
Lager Image
Combine (13) and (14), and the expected probability of the successful access in one slot with m successful relays when k > 0 is therefore given as
PPT Slide
Lager Image
Consequently, knowing the values of λ and m , the optimal access probability p acc for every unaccessed relay is the probability that maximizes
PPT Slide
Lager Image
, which can be obtained though
PPT Slide
Lager Image
From the formulations (15) and (16), it is clear that all the parameters needed to find the optimal access probabilities are given when the network is established. To avoid unnecessary delay involved by seaching, the preparation of p acc ( λ , m ) can be carried out before any selection and stored in a table in each relay for query instead of real-time search.
4. Performance analysis
In this section, the performance analysis of the SAGRS scheme is provided. Specifically, we give the analytical solutions to the average number of slots for selection and the failure probability, respectively.
- 4.1 Average number of slots for selection
The average slots consumed in one selection consists of two parts. The first part is the fixed one broadcast slot occupied by U s . The second part is the random access slots, which is further divided into two subparts: (1) the slots used to find the first relay, and (2) the slots used to terminate the selection after the first relay is achieved. We thereby split our discussion according to the above structure. However, it is rather complex to obtain a formulation of the average slots with the total slot constraint L . Considering this, the following propositions provide its upper bound when L → ∞. This bound will also be compared to the exact value to show their gap in the simulation section.
As a definition, we denote the expected value of a random variable as E [.] hereinafter.
Proposition 1. Let X 1 be the number of slots used to achieve the first relay. The average value of X 1 ( L → ∞) is given by
PPT Slide
Lager Image
Proof. See Appendix A.
After the first relay is acquired, the user continues the selection by seeking a better relay and stops only when one of Condition T1 or T2 occurs. Therefore the slots used from the first relay to the end of the selection can be modeled as a Markov chain (See Fig. 12 ). As described in Section 2. and shown in sub-part III of Fig. 4 , the transmission rate of a new successful relay will be compared to that of the stored relay, and influences the value of the selection slot number. However, due to the random position of the relays, the comparison result is consequently a probability event. Therefore we should figure out the probability that the transmit rate of the m th successful relay is lower than that of the ( m −1)th successful relay (a.k.a. the stored relay), denoted as
PPT Slide
Lager Image
, before the formulation of the average slot number in the second subpart. The following lemma shows the expression of
PPT Slide
Lager Image
.
Lemma 1. The probability that the transmit rate of the m th successful relay is lower than that of the ( m −1)th successful relay is
PPT Slide
Lager Image
Proof. See Appendix B.
With the above lemma, the average slot number of the second subpart of the selection is shown below.
Proposition 2. Let X 2 be the number of slots used till the selection termination after the first relay is stored. The average value of X 2 ( L → ∞) is given by
PPT Slide
Lager Image
Proof. See Appendix C.
With the above two propositions, the total average slot number of selection E [ X ]( L →∞) is therefore obtained as
PPT Slide
Lager Image
- 4.2 Failure probability
The failure probability P f of the SAGRS scheme is the probability that no relay is successfully selected in one frame. From the prior discussion, since the selection always succeeds when the first relay accesses successfully, its failure probability equals that of the first relay selection scheme, which can be obtained as
PPT Slide
Lager Image
As shown in formula (21), the failure probability of SAGRS contains two parts: the first part is the failure probability in the broadcast slot (the probability that no relay is qualified to the minimum required rate
PPT Slide
Lager Image
); the second part is the failure probability of random access selection, which means no relay accesses successfully in any of the rest L −1 slots though there exists at least one available relay after the broadcast slot.
5. Numerical Results
In this section, the performance evaluation of the SAGRS scheme is presented in a virtual network scenario. As shown in Fig. 6 , a 400 × 300 m 2 2-D relay region is established to simulate the proposed “large-scale” network. User nodes U s and U d are placed at (0,0) and (100,0) , respectively. Simulation parameters are: P s = P r = 10 mW , N 0 = 0.1 mW , ε = 0.1,
PPT Slide
Lager Image
= 10 -3 b/s/Hz , W = 10 , and L = 100 if not specified. The numerical results are averaged over 10 3 relay distribution samples with Monte Carlo simulation method in MATLAB. For comparison, the slot number allocated to the selection phase is fixed at 11 for the “best” relay selection. All the rates presented in the following figures are the one-frame time-averaging transmission rate.
PPT Slide
Lager Image
A network example when λr = 4×10-3 .
In Fig. 7 , the transmission rate of the SAGRS scheme is illustrated compared to the “best”, the “first” ( [18] ), and an ideal selection scheme ( [20] ) against different relay node densities λ r .The ideal scheme can always select the optimal relay in the network. To achieve this goal, it requires the information from all the available relays before making the decision. This collection needs a predetermined information upload sequence that allocates each available relay an independent slot, which is impossible in the proposed network because the relays are blind to each other without a control station. Even if the assumption can be realized somehow, the length of the selection phase is totally determined by the amount of available relays. As λ r raises, the increasing relays occupy more and more slots in selection and heavily damage the time-averaging performance even though the best relay can always be selected. When the relay number exceeds the total slot number L , no time is left for transmission because all slots are consumed in selection. As for the other three schemes, the SAGRS outperforms both the “best” and the “first” selections with given λ r . When λ r is relatively low, the rates of the three schemes increase rapidly along with λ r as it effectively decreases the probability of idleness. As λ r further increases, the SAGRS scheme preserves a stable performance during a feasible interval of λ r (in Fig. 7 the interval is approximately from 2×10 -4 to 4×10 -3 , and similar hereinafter). Since the rate improvement introduced by more relays is neutralized by the increasing chance of collision in access, a balance is generated in this interval and thus the rates no longer increase with λ r . In addition, more available relays enable more chances for comparison, broadening the gaps between the two comparison-based schemes and the “first” selection. When λ r is relatively too high (non-realistic) beyond the feasible interval, the rates of the three schemes fall because the probability of too many available relays increases greatly. Based on (12) and (15), these unfeasible distributions of the available relay number lead to a high probability for multiple relays to simultaneously access in each slot, which causes more collisions and harms the performance of the schemes on the contrary. The result implies a fact that it is not always effective to improve the performance of the proposed schemes only by adding more relays.
PPT Slide
Lager Image
Transmission rate versus λr .
In Fig. 8 , the impact of the minimum required rate
PPT Slide
Lager Image
on user’s transmission rate is illustrated. The relay density is fixed at λ r = 10 -3 . The figure implies that, as
PPT Slide
Lager Image
determines the area of the ARR, its value also affects the distribution of available relay number and needs to be chosen properly. When
PPT Slide
Lager Image
is set low, a large number of available relays resulted by a large ARR cause a high collision probability to harm the rate performance (as for the ideal scheme, it is caused by more uploading slots). As
PPT Slide
Lager Image
rises, the number of available relay falls and the rate also improves. However, when
PPT Slide
Lager Image
reaches to a relatively high value, the area of ARR is too small compared to the relay density, the probability of no available relay rapidly increases so the rate descends abruptly.
PPT Slide
Lager Image
Transmission rate
In Fig. 9 , the influence of the endurance limit W on the rate performance of the SAGRS is given. Regardless of the change of the relay density, the transmission rate is an increasing function of W . However, when W is beyond certain values (in Fig. 9 this bound is approximately W = 10 ), its influence on the rate is eliminated. It is because a more relaxed limit already guarantees a user enough slots to seek for new relays.
PPT Slide
Lager Image
Transmission rate versus W .
Fig. 10 illustrates the average number of slots consumed in the selection of the four schemes. Similar to Fig. 7 , unfeasible relay densities results in ill distributions of the available relay number. Since the “best” selection only occupies fixed 11 slots in selection, its selection slots never change. The selection slots of the ideal scheme reflect the number of available relays thus increase monotonically with λ r and reaches an unacceptable value when λ r is high. For the other two schemes, if no relay is available, all slots will be wasted in idleness, otherwise too many available relays increase the possibility of collision and cost more slots to resolve. Both of the two extremes bring about unacceptable numbers of selection slots. In the feasible interval, the selection slots of both the SAGRS and the “first” selection reach a stable minimum value. Moreover, to seek for a better relay, the SAGRS costs more slots than the “first” selection, but less than the “best” selection. Based on the result in Fig. 7 , with this balance between the extra selection slots and better instantaneous rate, the SAGRS improves the time-averaging performance of the user. In addition, even when L is loosen to ∞ , the gap between analysis and simulation of the SAGRS is very slight, which is due to the negligible probability to consume extremely massive slots ( L > 100 ) for selection.
PPT Slide
Lager Image
Average number of the selection slots versus λr
In Fig. 11 , the failure probability in the selection phase of the SAGRS scheme is presented. Given
PPT Slide
Lager Image
, the failure probability P f decreases with λ r and finally reaches a negligible level. In addition, the comparison of the two curves shows that since a higher
PPT Slide
Lager Image
leads to a smaller ARR, it requires a higher relay density to contain enough available relays for selection.
PPT Slide
Lager Image
Failure probability Pf versus λr
6. Conclusion
In this paper, a slotted ALOHA based greedy relay selection scheme is proposed in the large-scale wireless networks. The most significant characteristic of the scenario is its blindness because no information about any individual relay is available at the user. Due to the random distribution of the relays’ positions, the scheme utilizes the slotted ALOHA protocol for the relays to compete for selection. Furthermore, when encountering a successful relay, the scheme involves a greedy mechanism that allows a user to further seek for a better one. An available relay region is also embedded to guide the relays for an optimum access probability. By utilizing a few more extra slots in selection, the SAGRS scheme can provide a relay with higher instantaneous transmission rate. The tradeoff between them leads to a better time-averaging rate, owing to which the proposed scheme outperforms other random access based selection schemes.
BIO
Fengchen Ouyang was born in 1988. He received his B.S. degree from Xidian University in 2011. He is currently a Ph.D. candidate in the State Key Laboratory of Integrated Service Networks of Xidian University. His research interests include wireless communication, resource allocation and relay selection, and large-scale networks.
Jianhua Ge received his Ph.D. degree in School of Telecommunication Engineering from Xidian University, Xi’an, China, in 1990. He is currently a Professor and Deputy Director of the State Key Laboratory of Integrated Service Networks of Xidian University. He has worked on digital television (DTV) standardization as a DTV technical expert. His research interests include digital communications, digital video broadcasting, and performance enhancement techniques for 4G/B4G cellular communication systems.
Fengkui Gong received his Ph.D. degree in School of Telecommunication Engineering from Xidian University, Xi’an, China, in 2007. He is currently a Professor in State Key Laboratory of Integrated Service Networks of Xidian University. His research interests include next generation broad -band wireless communication, Mobile-to-Mobile communication, satellite communication, and digital video broadcasting.
References
Laneman J. N. , Tse D.N.C. , Wornell G. W. 2004 “Cooperative diversity in wireless networks: Efficient protocols and outage behavior,” IEEE Transactions on Information Theory 50 (12) 3062 - 3080    DOI : 10.1109/TIT.2004.838089
Jing Y. , Jafarkhani H. 2009 “Single and multiple relay selection schemes and their achievable diversity orders,” IEEE Transactions on Wireless Communications 8 (3) 1414 - 1423    DOI : 10.1109/TWC.2008.080109
Vicario J. L. , Bel A. , Lopez-Salcedo J. A. , Seco G. 2009 “Opportunistic relay selection with outdated CSI: outage probability and diversity analysis,” IEEE Transactions on Wireless Communications 8 (6) 2872 - 2876    DOI : 10.1109/TWC.2009.081561
Michalopoulos D. S. , Suraweera H. A. , Karagiannidis G. K. , Schober R. 2012 “Amplify-and-forward relay selection with outdated channel estimates,” IEEE Transactions on Communications 60 (5) 1278 - 1290    DOI : 10.1109/TCOMM.2012.032012.110430
Park S. , Kim D. , Nam S. 2011 “Adaptive threshold based relay selection for minimum feedback and channel usage,” IEEE Transactions on Wireless Communications 10 (11) 3620 - 3625    DOI : 10.1109/TWC.2011.11.102328
Tannious R. , Nosratinia A. 2008 “Spectrally-efficient relay selection with limited feedback,” IEEE Journal on Selected Areas in Communications 26 (8) 1419 - 1428    DOI : 10.1109/JSAC.2008.081008
Ouyang F. , Ge J. , Hou J. 2014 “Cooperative waiting-time reduction for cognitive radio networks using Stackelberg game,” IET Communications 8 (17) 3072 - 3080    DOI : 10.1049/iet-com.2014.0200
Chen Y. , Fang X. , Huang B. 2014 “Energy-efficient relay selection and resource allocation in nonregenerative relay OFDMA systems” IEEE Transactions on Vehicular Technology 63 (8) 3689 - 3699    DOI : 10.1109/TVT.2014.2302021
Alam M. S. , Mark J. W. , Shen X. 2013 “Relay selection and resource allocation for multi-user cooperative OFDMA networks,” IEEE Transactions on Wireless Communications 12 (5) 2193 - 2205    DOI : 10.1109/TWC.2013.032113.120652
Choi B.-G. , Bae S. J. , Cheon K. , Park A.-S. , Chung M.-Y. 2011 “Relay selection and resource allocation schemes for effective utilization of relay zones in relay-based cellular networks,” IEEE Communications Letters 15 (4) 407 - 409    DOI : 10.1109/LCOMM.2011.022411.101831
Mousavifar S. A. , Khattab T. , Hasna M. “Sequential random selection relaying for energy efficient wireless sensor networks,” in Proc. of IEEE Global Telecommunications Conference (GLOBECOM) December 6-10, 2010 1 - 6
Chiu S. N. , Stoyan D. , Kendall W. S. , Mecke J. 2013 Stochastic Geometry and its Applications 3rd Edition Wiley
Cho S. , Choi W. , Huang K. 2011 “QoS provisioning relay selection in random relay networks,” IEEE Transactions on Vehicular Technology 60 (6) 2680 - 2689    DOI : 10.1109/TVT.2011.2153220
Etezadi F. , Zarif K. , Ghrayeb A. , Affes S. 2012 “Decentralized relay selection schemes in uniformly distributed wireless sensor networks,” IEEE Transactions on Wireless Communications 11 (3) 938 - 951    DOI : 10.1109/TWC.2012.010312.101314
Ouyang F. , Ge J. , Gong F. , Hou J. 2015 “Random access based blind relay selection in large-scale relay networks,” IEEE Communications Letters 19 (2) 255 - 258    DOI : 10.1109/LCOMM.2014.2379280
Li B. , Li H. , Wang W. , Hu Z. , Yin Q. 2013 “Energy-effective relay selection by utilizing spacial diversity for random wireless sensor networks,” IEEE Communications Letters 17 (10) 1972 - 1975    DOI : 10.1109/LCOMM.2013.090413.131503
Krikidis I. 2014 “Simultaneous information and energy transfer in large-scale networks with/without relaying,” IEEE Transactions on Communications 62 (3) 900 - 912    DOI : 10.1109/TCOMM.2014.020914.130825
Bettstetter C. , Brandner G. , Vilzmann R. “On colliding first messages in slotted ALOHA,” in Proc. of IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) September 15-18, 2008 1 - 6
Zhang Y. , Dolmans G. “Wake-up radio assisted energy-aware multi-hop relaying for low power communications” in Proc. of IEEE Wireless Communications and Networking Conference April 1-4, 2012 2498 - 2503
Michalopoulos D. S. , Suraweera H. A. , Schober R. “The impact of relay selection on the tradeoff between information transmission and wireless energy transfer,” in Proc. of IEEE Global Telecommunications Conference (GLOBECOM) December 8-12, 2014 4191 - 4196