{'fraction_non_alphanumeric': 0.037658064771871405, 'fraction_numerical': 0.008839735204344551, 'mean_word_length': 4.14437194127243, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Two-level game for relay-based throughput enhancement via D2D communications in LTE networks

In this paper, we facilitate device-to-device (D2D) communications to provide relay assistance to cell-edge user equipments (UEs) with the objective of improving system throughput. We first formulate a joint problem of relay node selection which helps cell-edge UEs find the proper relay nodes, as well as spectrum allocation for D2D links to maximize the system throughput with interference constraints to both D2D and traditional cellular UEs. Furthermore, we propose a distributed algorithm adopting a two-level game model which consists of inner and outer levels to solve the formulated problem. In the inner level, we use the Stackelberg game to select relay nodes for cell-edge UEs, where the relay nodes act as the leaders and the cell-edge UEs act as the followers. In the outer level, the coalition formation game is used to allocate proper spectrum for the D2D links between cell-edge UEs and their relay nodes. The games do not proceed separately, but are dependent on each other, which improves the efficiency of the proposed game model. Simulation results demonstrate that the proposed algorithm outperforms the benchmarks in terms of system throughput.


I. INTRODUCTION
Long-term evolution (LTE) cellular networks need to provide ubiquitous coverage and high throughput with costefficient infrastructure deployment. However, in realistic scenarios, cell-edge user equipments (UEs) are always subjected to unfavorable radio frequency links due to distance-dependent path losses and multi-path propagation to the evolved NodeBs (eNBs).
Device-to-device (D2D) communications, enabling direct communications between devices in close proximity without routing traffic through the eNodeB, have been identified as an appropriate way of enabling cooperative relaying functions to minimize the cell-edge issues arisen due to the wireless variability. Indeed, D2D communications can bring many benefits such as i) extended cellular coverage; ii) offloading of local traffic from cellular networks; or iii) improvement of throughput and spectrum efficiency, among others [1]. Sparking by the potential benefits of D2D communications, many works have been prompted in different scenarios [2][3][4]. Solution approaches that allowed cellular devices and D2D pairs to share spectrum resources were proposed in [2], thereby increased the spectrum efficiency of traditional cellular networks. In [3], D2D spectrum sharing and mode selection using a hybrid network model and a unified analytical approach were jointly studied. In [4], from the perspective of security issue, the performance of secure D2D communication was investigated in energy harvesting large-scale cognitive radio networks.
Recently, [5,6] have introduced D2D communications to the relay assistance for cellular UEs. The work in [5] analytically quantified the cellular network performance during massive infrastructure failure, where some terminals could play the role of relay nodes forming multi-hop communications links via D2D to assist farther terminals. In [5], it was assumed that the D2D and traditional cellular communications occured in different sub-bands. In [6], the authors focused on using opportunistic networks to extend the cellular coverage via joint node and spectrum selection for D2D radio links. However, both in [5,6], the interference between D2D and cellular UEs was not discussed in details.
Due to the intra-cell interference caused by spectrum sharing between D2D and traditional cellular UEs, spectrum allocation is a key issue for network-assisted D2D communications. The spectrum for D2D users can be allocated either in centralized [7,8] or distributed manner [9][10][11]. In [7], a greedy heuristic spectrum allocation algorithm was proposed where any cellular UE with higher channel quality could share RBs with the D2D user that had lower channel quality. In [8], the authors proposed an optimal resource allocation scheme which could significantly improve the network throughput. However, centralized resource allocation may bring high computational complexity to the eNB, therefore, the distributed approach is needed. The authors in [9] proposed a combinational auction game to allocate channels and power to both D2D and cellular UEs to improve energy efficiency. In [10], the authors developed two distributed resource management schemes based on the Lagrangian dual decomposition and the game theory, respectively. In our previous work [11], a joint mode selection and resource allocation algorithm for D2D links based on the coalition formation game was proposed, with the objective of improving the overall system throughput.
In this work, we investigate the joint problem of relay node selection for cell-edge UEs, as well as the spectrum allocation for D2D links between cell-edge UEs and the corresponding relay nodes. A two-level game is adopted to solve the formulated problem. To the best of our knowledge, this formulated joint problem has not been discussed in the aforementioned literature. The main contributions of this paper are summarized as follows. 1) We formulate a joint relay node selection and spectrum allocation problem taking account of the interference constraints for both D2D and cellular UEs; 2) We propose a novel algorithm based on the two-level game model to solve the formulated problem. The two-level games proceed dependently, which improves the efficiency of the proposed algorithm; 3) Simulation results show that the proposed algorithm outperforms both the benchmarks of relay selection algorithm without game and the heuristic spectrum allocation algorithm.
The rest of the paper is organized as follows. Section II presents the single-cell uplink system model and discusses the problem formulation. The proposed joint relay node selection and spectrum allocation algorithm is described in Section III. Section IV discusses the numerical results for the proposed algorithm. Section V concludes the paper.

A. Scenario and Channel Model
We consider a single cell uplink scenario employing single carrier frequency division multiple access (SC-FDMA) where the radio resources are allocated in units of resource block (RB) pairs. The set of cell-edge UEs is denoted by O = {O 1 , ..., O n , ...}, and |O| = N . The set of UEs with favorable uplink channels is denoted by I = {I 1 , ..., I m , ...}, and |I| = M . The UEs with favorable uplink channels can provide relay assistance and spectrum sharing for the celledge UEs. Each UE is equipped with a single omnidirectional antenna. We assume that each I m ∈ I has been granted one RB pair for transmission in advance by the scheduler.
We assume that each cell-edge UE can only select the UE with favorable uplink channels within a maximum distance of 50 meters as the relay nodes, and we denote the set of these potential relay nodes for the cell-edge UE O n by R n = {R 1 , ..., R x , ...}. The system model is as shown in Fig. 1. We characterize our channel model using a time-division notation, where a baseband-equivalent, discrete-time channel model is utilized for the continuous channel.
In our scenario, the D2D links are assumed to reuse the uplink spectrum of cellular UEs. Since spectrum sharing may cause co-channel interference lowering the data rates of UEs, it is important to allocate proper spectrum to D2D links. To control the interference in a reasonable range, we assume that one D2D link can only share one cellular UE's RB pair, while the RB pair of a cellular UE can only be reused by one D2D link.

B. Relay Model
We use the amplify-and-forward (AF) cooperation protocol as the relay model. In phase 1, cell-edge UEs broadcast their information to the relay nodes and the eNB. Assuming the transmission signal with unite signal power at the cell-edge UE O n is x, the received signal at the relay node I r is expressed as y Ir = x P On G On,Ir + n Ir + i Im , where P On denotes the transmission power of O n , which is set as a constant value. G On,Ir is the channel gain between O n and I r , n Ir is the additive white Gaussian noise at I r , and i Im is the interference from the spectrum sharer I m . The signal-to-interference-plus-noise (SINR) of the received signal at I r is given by where |i Im | 2 = P Im G Im,Ir is the power of the received interference from I m . N 0 = 2B RB σ 2 is the power of the Gaussian noise, where B RB is the bandwidth of a RB. Similarly, we can get the SNR at the eNB corresponding to O n , which is expressed as where G On,B is the channel gain between O n and the eNB. In phase 2, the relay node I r amplifies and forwards the received signal y Ir from O n . Therefore, the relayed signal received at the eNB is where y Ir = y Ir /|y Ir |, G Ir,B is the channel gain between I r and the eNB, and n B is the additive white Gaussian noise at the eNB. Substituting (1) into (4), we can get the relayed signal as a function of x, which is expressed by It is assumed that the received noise at each receiver is independent identically distributed (i.i.d) complex Gaussian random variables. Thus the relayed SINR at the eNB corresponding to O n is given by where Based on the derivations in [12], we have the data rate at the eNB with one relay node I r helping as R On,Ir,B = 2B RB log 2 (1 + SINR On,r + SNR On ).
We develop a single-leader-single-follower Stackelberg game model to select the proper relay node from the set of potential relay nodes for each cell-edge UE, where the relay node acts as the leader and the cell-edge UE acts as the follower. For the followers, we define the utility of O n as where α is the unit gain of relayed data rate, and β is the unit price of power consumption of the relay node I r . The optimization problem for O n is The maximum power consumption of UEs is P max . If P Ir > P max , the utility of U On is set to be −∞.
For the leaders, we define the utility of I r as where c is the cost of unit power consumption for relaying data. If β is set to be smaller than c, the utility of I r is a negative value. Then I r will quit gaming since it can not cover the basic cost by selling power to O n . The optimization problem for I r is max

C. Interference Model
If O n selects I r as the relay node, and the D2D link between O n and I r reuses the RB pair allocated to the traditional cellular link of I m (for simplicity, we assume m = r), the received SINR on I r is given by and the received SINR on the eNB for the transmitted signal from I m is where P Im denotes the transmission power of I m , which is a constant value. G Im,Ir denotes the channel gain between I m and I r . The channel gain between I m and the eNB is represented by G Im,B . The corresponding data rates at I r and the eNB are given by and respectively. Through proper spectrum allocation, our objective is to maximize the single-cell throughput, which is given by The two constraints in (17) restrict the interference caused to communication links. The peak interference constraint can be calculated based on the SINR threshold, i.e., I thr = p r /ξ thr − N 0 , where p r is the received power at the receiver.

III. JOINT RELAY NODE SELECTION AND SPECTRUM ALLOCATION
Recall (6), (7) and (12), the relay node selection and spectrum allocation make a difference on each other. Therefore, in this section, we develop a two-level game model implementing a distributed algorithm to jointly consider the relay node selection and spectrum allocation to improve system throughput.

A. Inner Level: Stackelberg Game
For the relay node selection process, we need to find a proper relay node from the set of potential relay nodes for each cell-edge UE, and set the transmission power of the relay node. We develop a Stackelberg game model to set the optimal power to each potential relay node for cell-edge UEs. Recall (6) and (7), the relayed data rate of cell-edge UEs is a function of the interference received from spectrum sharers. Therefore, the relay node selection process is dependent on the spectrum allocation.
In a Stackelberg game, the leader acts first. The followers observe the leader's behavior and decide their own strategies. We develop a single-leader-single-follower game model to select the proper relay nodes for the D2D links, where the relay node acts as the leader, and the cell-edge acts as the follower. The Backward induction can be developed to solve the proposed Stackelberg game.
1) Follower-level game: Supposing that the price β has been given by the leader, we can solve the optimization problem of the follower by taking a derivation of U On with respect to P Ir as Substituting (7) into (18), we can get a quadratic equation of P Ri , which is expressed as Solving the quadratic equation, we can get the solution of P Ir asP where Θ = β( + SNR On + ζ), Φ = 2ν βSNR On + 2ν β + βζν.
To prove the concave property of U On with respect to P Ir , we give the second order derivation as where X = 2 ( + SNR On + ζ)P Ir + 2 νSNR On + 2ν + ζν, and Y = ( + SNR On + ζ)P Ir + ν(2 SNR On + 2 + ζ). We observe that Therefore, U On is a concave function with respect to P Ir . The value ofP Ir expressed in (21) is the maximum point.
2) Leader-level game: From (21), we can find that the optimum value of P Ir is decided by the price β. To guarantee that O n can buy the optimum amount of power from I r , it needs to be satisfied that where P max Ir is the maximum power consumption of I r . Then we can get the maximum and minimum price β as where W = ( + SNR On +ζ), U = (2ν SNR On +2ν +ζν) 2 , and V = (2P max Ir W + 2ν SNR On + 2ν + ζν) 2 . Then, we analyze how the price β affects the leader's utility. When the price β is low, the utility of the leader arises with the price according to (10). However, the follower will buy less power from the leader with higher price, which can be found in (8). Therefore, when the price increases to a certain value, U Ir will decrease because of the smaller P Ir . In conclusion, there is an optimal value for β to achieve the highest U Ir .
Substituting (21) into (10), we get Based on the analysis above, we make the first order derivation of U Ir with respect to β equal to zero, then we can get where P = ( + SNR On +ζ), Q = 2ν SNR On +2ν +ζν,R = B RB αζν/ ln 2, H = 8P R, and T = ζ 2 ν 2 .
We denote the solution of (28) as where f (G On,Ir , G Ir,B , |i Im |) denotes a function of G On,Ir , G Ir,B and |i Im |. The optimal value of β is β ∈ {β min , β * , β max }.

B. Outer Level: Coalition Formation Game
In this step, we allocate proper spectrum to the D2D links between cell-edge UEs and relay nodes based on the coalition formation game [11].
We define a coalition formation game as (S, v, U ) with the player set N = I ∪ O, where S denotes the coalition structure satisfying S = {S 1 , ..., S p , ...S P } with S p being a coalition, and for ∀p = p, S p ∩ S p = ∅, we have ∪ P p=1 S p = N , the characteristic function quantifying the gain of S p is represented by v(S p ) , and U = {u 1 , ..., u x , ...} is the payoff allocation vector of players.
Based on the spectrum sharers selected by the D2D links, we can categorize the coalitions into the following three cases: (1) Case 1: A coalition contains a D2D link O n − I r and a UE I m , i.e., S p = {O n , I m }. In this case, the D2D link reuses the RB pair of I m . For simplicity of notation, we use O n to represent the D2D pair O n − I r .
(2) Case 2: I m forms a singleton coalition, i.e., S p = {I m }. In this case, I m does not share its RB pair with any D2D link.
where R x is either the throughput of a D2D link or a cellular uplink channel. Coalition collection is defined as a set of disjoint coalitions. In this game model, the coalitions which contain D2D links form the D2D collection A D ; while the singleton coalitions which only contain the cellular UEs form the cellular collection A C . The coalition structure changes when a D2D link leaves the current coalition and joins in a coalition of the cellular collection. The initial state of the game is the set of singleton coalitions. In the following steps, D2D links will be chosen randomly to select the proper spectrum. If a D2D link can not find a proper coalition to join in, it will stay idle and transmit in the next time slot.
We assume that a D2D link O n − I r is selected to revise her strategy, then all the other players keep their strategies. Since all the players are myopic, the best-reply rule guarantees that players can select the coalition that promises her the highest payoff. Then the payoff of the D2D pair O n − I r at time t + 1 can be calculated based on the best-reply rule as: where and u t On is the utility of O n at time t. It should be noted that (32) exists only if the constraints in (17) are satisfied.
In our scenario, we assume that there are multiple celledge UEs and multiple UEs with favorable uplinks channels to provide relay assistance and spectrum sharing. Since the relay node selection and spectrum allocation make a difference on each other, we need to design an algorithm to jointly consider these two issues. Since each cell-edge UE tries to select the relay node that provides it with the highest utility, another challenge existing in our scenario is that, two different celledge UEs may ask for the relay assistance from the same relay node. Therefore, we need to design a proper algorithm to solve these problems. The proposed algorithm is shown in Algorithm 1. The complexity of this algorithm is where R n is the set of potential relay nodes for each cell-edge UE, and |R n | is the cardinality of R n .

IV. NUMERICAL RESULTS
In this section, we evaluate the performance of the proposed joint relay node selection and spectrum allocation algorithm. We set c = 0.5, α = 0.01. The bandwidth of each RB is 180 kHz. The noise power N 0 equals to -98dBm.
We consider both the scenarios of single cell-edge UE and multiple cell-edge UEs. In the single cell-edge UE scenario, we analyze how the price β and power consumption of the relay node change with different distances between the cell-edge UE and the eNB, and how they change with different numbers of UEs with favorable uplink channels. For the multiple cell edge UEs scenario, we assume there are 40 cell-edge UEs and we compare the performance of the proposed algorithm with two benchmarks: 1) Relay selection algorithm without game: In this benchmark, the spectrum allocation is based on the coalition formation game, while the relay nodes are selected Algorithm 1 Distributed Joint Relay Node Selection and Spectrum Allocation Algorithm 1: Initialization. a n,r = 0, b n,m = 0, ∀r, m, n. The set of potential relay nodes for each cell-edge UE O n is R n . 2: ---Outer Level: Coalition Formation Game Based Spectrum Allocation 3: For each potential D2D link between O n and its potential relay node I r , where I r ∈ R n , search for the optimal spectrum sharer I m (m = r) based on the best-reply rule ---Inner Level: Stackelberg Game Based Relay Node Selection 5: Based on the selected spectrum for each potential O n − I r pair in the outer level, calculateP Ir andβ as in (21) and (30). Then, calculate the utility of O n as in (8). 6: For each O n , sort the relay nodes in descending order with respect to U On , and select the relay node with the first position in the queue.

7:
If I r is selected, set a n,r = 1 to indicate that I r has been occupied by O n . If the corresponding spectrum sharer with I r for O n is I m , set b n,m = 1 to indicate that I m has been occupied by the D2D link between O n and I r . 8: while n a n,r > 1, ∃r do 9: Randomly select a cell-edge UE for which a n,r = 1 to keep its relay node, while other celledge UEs selecting the same relay node delete the head from the queue, and then select the new head. Renew the values of a n,r , b n,m , ∀r, m, n. Randomly select a O n − I r pair to leave the current coalition and join in a singleton coalition of the cellular collection based on the best-reply rule expressed in (34). 14: end while 15: ---End of Coalition Formation Game without game. For the cell-edge UE with the largest distance from the eNB, it has the highest priority to select the relay node with which it can achieve the highest relayed data rate; 2) Heuristic spectrum allocation algorithm: In this benchmark, the relay node selection is based on the Stackelberg game, while the spectrum allocation is based on the heuristic algorithm proposed in [7]. In the heuristic algorithm, the eNB selects the cellular uplink with the highest channel gain to share resource with the D2D pair with the lowest interference channel gain.
A. Single Cell-edge UE Scenario Fig. 2(a) shows the effect of different numbers of UEs with favorable uplink channels on the price β and the power consumption of the relay node. From this figure, on one hand, we can find that, β decreases with M . This can be easily understood because of the diversity gain achieved by the potential relay nodes. When there are more UEs that can provide relay assistance, the cell-edge UE will have more choices from which it selects the one asking for the lowest price. On the other hand, the power consumption of the relay node increases as M increases. Since the price β gets smaller with the increment of M , the cell-edge UE is encouraged to buy more power from the relay node. Fig. 2(b) depicts the price β and the power consumption of the relay node, respectively, with different distances between the cell-edge UE and the eNB. We observe from the figure that the power decreases with the distance, while β increases as the distance increases. When the distance increases, the number of UEs with favorable uplink channels that are within the transmission range of the celledge UE decreases. In the sequel, the cell-edge UE has less choices from which to select the optimal relay node, and hence the optimal price increases. Further, the cell-edge UE will buy less power because of the higher price. Fig. 2(c) and Fig. 2(d), respectively, demonstrates the utility of the cell-edge UE as expressed in (8) with different numbers of UEs with favorable uplink channels and different distances between the cell-edge UE and the eNB. It can be seen in Fig. 2(c) that the utility of the cell-edge UE increases as the number of UEs with favorable uplink channels increases. This is because of the diversity gain achieved by the potential relay nodes. Fig. 2(c) also shows that the utility decreases with higher values of c. Recall in (10), c is the unit cost of power consumption of the relay node. If β is set to be smaller than c, the utility of the relay node will be a negative value, which means the relay node will quit gaming since it can not cover the basic cost. If c increases, there will be more relay nodes quit gaming, and hence the utility of the cell-edge UE decreases. In Fig. 2(d), we observe that the utility of the cell-edge UE decreases as the distance between the cell-edge UE and the eNB increases, which is because of the smaller number of potential relay nodes.

B. Multiple Cell-edge UEs Scenario
In Fig. 3, we plot the average utility of cell-edge UEs vs. different cellular radii. The average utility of cell-edge UEs of the proposed algorithm improves by about 20% compared to that of the relay selection algorithm without game. In the meanwhile, with larger cellular radius, the average utility of cell-edge UEs gets smaller, which is because of the higher path loss.
The comparison between the proposed algorithm and the heuristic spectrum allocation algorithm is illustrated in Fig.  4(a) and Fig. 4(b). The throughput gain is defined as the system throughput increment percentage compared to the scenario that the cell-edge UEs transmit to the eNB without any relay. We observe that the proposed algorithm improves the system throughput by around 15% compared to the scenario that the cell-edge UEs transmit to the eNB without relay. In addition, we also find that the proposed algorithm outperforms the heuristic spectrum allocation algorithm. Fig. 4(a) shows that the throughput gain increases with the number of UEs with favorable uplink channels, which is caused by the diversity gain caused by the potential relay nodes. Fig. 4(b) demonstrates that the throughput gain increases as the average distance between cell-edge UEs and the eNB increases. This can be easily understood because the throughput enhancement of the cell-edge UEs with relay assistance becomes higher with larger distance to the eNB.
V. CONCLUSIONS In this paper, we leveraged device-to-device (D2D) communications to provide relay assistance for cell-edge user equipments (UEs) to enhance network throughput. We adopted the two-level game model to jointly solve the problem of relay node selection which selected the proper relay nodes for cell-edge UEs and allocated optimal power to the relay nodes, as well as the problem of spectrum allocation for D2D links where the interference between D2D and traditional cellular links was taken into consideration. Simulation results demonstrated that the proposed algorithm outperformed both the relay selection algorithm without game and the heuristic spectrum allocation algorithm.