# Frequency Resource Sharing and Allocation Scheme Based on Coalition Formation Game in Hybrid D2D-Cellular Network

Authors: Qing Ou; Rongqing Zhang; Xi Luan; Yuxin Cheng; Jun Wu; Jianjun Wu
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

A distributed cooperation scheme on frequency resource sharing is proposed to improve the quality of service (QoS) in device-to-device (D2D) communications underlaying cellular networks. Specifically, we formulate the resource allocation problem as a coalition formation game with transferable utility, in which all users have the incentive to cooperate with some others and form a competitive group to maximize the probability of obtaining their favorite spectrum resources. Taking the cost for coalition formation into account, such as the path loss for data sharing, we prove that the core of the proposed game is empty, which shows the impossibility of grand coalition. Hence, we propose a distributed merge-and-split based coalition formation algorithm based on a new defined Max-Coalition order to effectively solve the coalition game. Compared with the exhaustive search, our algorithm has much lower computer complexity. In addition, we prove that stability and convergence of the proposed algorithm using the concept of a defection function. Finally, the simulation results show that the proposed scheme achieves a suboptimal performance in terms of network sum rate compared with the centralized optimal resource allocation scheme obtained via exhaustive search.


---

## Body

## 1. Introduction

The demand of increasing data rate for local services and growing spectrum congestion have triggered the research for improving spectral efficiency in cellular networks. The device-to-device (D2D) communication link behaving as an underlay to the cellular network has been regarded as an effective technique to provide better wireless services in local areas [1–4]. In the hybrid D2D-cellular system, D2D users may share resources with cellular users in either an orthogonal manner or a nonorthogonal manner [5]. In the orthogonal case, dedicated resources are allocated to D2D users, and it cannot improve spectral efficiency, though it is easy to implement. Therefore, nonorthogonal resource sharing receives more attention [6–9]. While intracell interference in the nonorthogonal case has significant influence on the network throughput, hence, an efficient resource sharing strategy is essential for the feasibility of the hybrid D2D-cellular system.The resource sharing problems in the hybrid D2D-cellular system have been analyzed in many existing researches. In [7], the optimum resource allocation and power control scheme was proposed, which shows that, with proper resource management, the hybrid D2D-cellular communications can greatly increase the network throughput when comparing with traditional cellular-only networks. However, the proposed cooperation algorithm in [7] fully depended on a centralized entity in the network such as a base station (BS), and a large amount of communication overhead was required for information exchange among the users. In [9, 10], a resource sharing algorithm was proposed based on coalition graph game, while in these two papers the cooperation cost on the communication was not discussed, which would limit its benefits or even impair the users’ performance.In this paper, we propose a frequency resource sharing scheme based on the definition of coalition. Both the D2D users and the cellular users form several cooperation coalitions, in which there are some D2D users and a cellular user, and each coalition occupies a dedicated resource. In order to allocate the frequency resource, we defined the coalition sum transmission rate as the coalition that can be achieved through the resource blocks (RBs) allocated to it. Only the user group who can achieve the maximum sum rate on a specific RB can obtain it from the BS for data transmission, so each user (either D2D pair or cellular UE) has the incentive to cooperate with others who can achieve an improved sum rate on its preferred RBs to maximize its own utility and form a strengthened user group. In this strategy, we suppose that every cellular UE and D2D pair has an identical priority to access the RBs.The main contribution of this paper is that the spectrum resource allocation in the hybrid D2D-cellular system is formulated as a coalition formation game with transferable utility [11, 12]. In the proposed game, each user can only join one coalition game at a time, while at the next time slot it can change its identify (i.e., its current preferred RB index) leaving the current subgame and participating in another one. Based on this, we further divide the proposed game into several subgames and those subgames can process the resource allocation at the same time. In addition, we suppose a distributed merge-and-split based coalition formation algorithm on the basis of a new defined Max-Coalition order to solve the proposed game in a distributed manner effectively with low complexity.The rest of this paper is organized as follows. Section2 presents the proposed system model and the corresponding resource allocation optimization problem. In Section 3, we model the resource allocation problem as a coalitional game with transferable utility. In Section 4, a distributed coalition formation algorithm is proposed based on the merge-and-split rules to solve the resource allocation problem. Simulation results are provided in Section 5. Finally, conclusions are drawn in Section 6.


## 2. System Model and Problem Formulation

### 2.1. System Description

In this paper, the D2D pairs reuse the downlink resource in the underlaying D2D communication system that is analyzed as depicted in Figure1. Orthogonal frequency division multiplexing (OFDM) technique is employed to support multiple access for both the traditional cellular UEs and the D2D pairs; therefore, the wideband channel for the cellular data transmission can be divided into several narrow band subcarriers denoted as K RBs, K=RB1,RB2,…,RBK. We assume that there are X traditional cellular UEs and Y D2D pairs in the investigated network, where Ux, x=1,2,…,X, denotes a traditional cellular UE and Dy,t and Dy,r, y=1,2,…,Y, denote a possible D2D pair whose distance is short enough to satisfy the constraint of the direct D2D communication, where Dy,t represents the transmitter of the D2D pair and Dy,r represents the receiver of the D2D pair. We define the set of references {1,2,…,X}, the set of references {1,2,…,Y}, the set of traditional cellular UEs, and the set of D2D communication pairs that are represented by X, Y, U, and D, respectively.Figure 1
System model for D2D communications underlaying cellular network when sharing downlink resource.The channel gains of the traditional cellular communication link from the BS to the cellular UEUx, the D2D communication link from Dy,t to Dy,r, the interference link from the BS to Dy,r, the interference link from Dy,t to Ux, and the interference link from Dy,t to Dy′,r, when they share the RBk for individual data transmission, are represented by gUxk, gDy,t,Dy,rk, gb,Dy,rk, gDy,t,Uxk, and gDy,t,Dy′,rk, respectively, where x∈X, y∈Y, y′∈Y, y≠y′, and k∈K. The channel gains contain the normalized small-scale fading and the distance-dependent path loss. Note that, in our assumption, the small-scale fading on different RBs for a certain communication link is independent, but within one RB it stays the same, that is, a frequency flat fading in each RB. Also quasistatic channel fading is assumed from one slot to another. The thermal noise at the receivers satisfies independent Gaussian distribution with zero mean and the same variance denoted by σ2.Suppose that the BS and the transmitter of the D2D pairs transmit with powersPb and Pd allocated to each RB, respectively. Whenever a coalition (regarded as the cellular UEs and D2D pairs sharing the RB for individual data transmission after cooperation) occupies the RB, part of the transmission power is used as a cost on the information exchange among the members in the coalition [13–18], and the remaining power is used for actual data transmission. The cost is the sum of the power that is used to each member in a coalition S exchanging information to its corresponding farthest member inside S. For instance, the power needed for broadcast transmission between a member i∈S and its corresponding farthest member i^∈S is given by
(1)P¯i,i^=κ0·σ2gi,i^k,
where κ0 is a target SNR for information exchange; gi,i^k=h2·di,i^(-α) is the exchange of information link from member i to member i^ when RBk is allocated to it for data transmission; h is the path loss constant; α is the path loss exponent; and di,i^ is the distance between member i and member i^. As a consequence, the total power cost denoted by P^S for a coalition S is given by
(2)P^S=∑x∈X,Ux∈S‍P¯Ux,U^x+∑y∈Y,Dy∈S‍P¯Dy,D^y.As the defined cost in (2) depends on the location of the members and the size of the coalition, a higher power cost is incurred whenever the distance between the members increases or the size of coalition increases.Thus, the actual power constraint of the cellular UEUx per coalition S is given by
(3)PUx=Pb-P¯Ux,U^x+.Also, the actual power constraint of the D2D pairDy per coalition S is given by
(4)PDy=Pd-P¯Dy,D^y+,
where it defines a+≜max⁡(a,0).Thus the fraction power used for data transmission of coalitionS is
(5)PS=∑x∈X,Ux∈S‍PUx+∑y∈Y,Dy∈S‍PDy.The instantaneous signal-to-interference-plus-noise ratio (SINR) at cellular UEUx, x∈X, when RBk is allocated to it for data transmission, can be given as follows:
(6)SINRUxk=PUx·gUxkσ2+∑Dy∈SPDygDj,t,Uxk,
and the instantaneous SINR at the receiver of the D2D pair Dy, that is, Dy,r, y∈Y, when RBk is allocated to it for data transmission, can be given as follows:
(7)SINRDyk=PDy·gDy,t,Dy,rkσ2+∑Ux∈SPUxgb,Dy,rk/K+∑j≠Y,Dy∈SPDygDj,t,Dy,rk.


### 2.2. Frequency Resource Allocation Problem

In the underlaying D2D communication system, the interference problem is not negligible, which, therefore, calls for optimal RB assignment solution to reduce the interference, and then each communication link can properly perform its individual data transmission. According to the Shannon capacity formula, we define thesum rate of the cellular network as the sum of the channel capacities for all the communication links within the network. Let S(X+Y)×K=UX×KDY×K be an RB assignment solution, where UX×K=αx,k and DY×K=βy,k denote the RB assignment matrix for the traditional cellular communication links and the D2D communication links, respectively. The value of αx,k and βy,k, with x∈X, y∈Y, and k∈K, can be defined as follows:
(8)αx,k=1,whenRBkisallocated  toUx,0,otherwise,(9)βy,k=1,whenRBkallocated  toDy,0,otherwise.Therefore, we can obtain the optimal RB assignment solution, denoted bySopt, solving the optimization problem as follows:
(10)Sopt=argmax⁡S(X+Y)×K∑k=1K‍WK∑x=1X‍log21+SINRUxkαx,kiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+∑y=1Y‍log21+SINRDykβy,k(11)s.t.S=Ux,Dy∣αx,k=1,βy,k=1,x∈X,y∈Y,∑x=1X‍αx,k≤1,∑k=1K‍αx,k≤1,∑k=1K‍βy,k≤1,
where SINRUxk and SINRDyk are given in (6) and (7), respectively. Particularly, the second constraint in (11) guarantees that different traditional cellular UEs can never occupy the same RB for data transmission. The third constraint in (11) guarantees that each user can obtain at most one RB in an OFDM symbol through every RB assignment process.The optimal RB assignment solution in (10) and (11) can be obtained through an exhaustive search for all the possible choices of αx,k and βy,k subjected to the conditions given in (11), where αx,k and βy,k are independent of each other. Then, the computational complexity can be obtained as the multiplication of the complexity with all possible choices of αx,k and βy,k. So the computational complexity of it can be obtained as follows:
(12)Toptimal=O∑k=0K‍HXkY+1K-1K-1!,
where (n)! denotes the factorial computation of a nonnegative integer n and Hmn represents the permutation operation, which is defined as
(13)Hmn=(m)!(m-n)!,whenm≥n,0,otherwise,
where m and n are both nonnegative integers, and we further define (0)!=1.Based on (13), the optimal RB assignment solution is an NP-hard combinatorial optimization problem with nonlinear constraints; particularly, as the number of cellular UEs and D2D pairs grows, the computational complexity increases rapidly. In other words, directly finding an optimal solution of the aforementioned optimization problem is computationally prohibitive, and no polynomial-time algorithm can optimally solve it. Therefore, in the following section, we formulate this resource allocation problem as a coalitional formation game and solve it in a distributed manner with low computational complexity.


## 2.1. System Description

In this paper, the D2D pairs reuse the downlink resource in the underlaying D2D communication system that is analyzed as depicted in Figure1. Orthogonal frequency division multiplexing (OFDM) technique is employed to support multiple access for both the traditional cellular UEs and the D2D pairs; therefore, the wideband channel for the cellular data transmission can be divided into several narrow band subcarriers denoted as K RBs, K=RB1,RB2,…,RBK. We assume that there are X traditional cellular UEs and Y D2D pairs in the investigated network, where Ux, x=1,2,…,X, denotes a traditional cellular UE and Dy,t and Dy,r, y=1,2,…,Y, denote a possible D2D pair whose distance is short enough to satisfy the constraint of the direct D2D communication, where Dy,t represents the transmitter of the D2D pair and Dy,r represents the receiver of the D2D pair. We define the set of references {1,2,…,X}, the set of references {1,2,…,Y}, the set of traditional cellular UEs, and the set of D2D communication pairs that are represented by X, Y, U, and D, respectively.Figure 1
System model for D2D communications underlaying cellular network when sharing downlink resource.The channel gains of the traditional cellular communication link from the BS to the cellular UEUx, the D2D communication link from Dy,t to Dy,r, the interference link from the BS to Dy,r, the interference link from Dy,t to Ux, and the interference link from Dy,t to Dy′,r, when they share the RBk for individual data transmission, are represented by gUxk, gDy,t,Dy,rk, gb,Dy,rk, gDy,t,Uxk, and gDy,t,Dy′,rk, respectively, where x∈X, y∈Y, y′∈Y, y≠y′, and k∈K. The channel gains contain the normalized small-scale fading and the distance-dependent path loss. Note that, in our assumption, the small-scale fading on different RBs for a certain communication link is independent, but within one RB it stays the same, that is, a frequency flat fading in each RB. Also quasistatic channel fading is assumed from one slot to another. The thermal noise at the receivers satisfies independent Gaussian distribution with zero mean and the same variance denoted by σ2.Suppose that the BS and the transmitter of the D2D pairs transmit with powersPb and Pd allocated to each RB, respectively. Whenever a coalition (regarded as the cellular UEs and D2D pairs sharing the RB for individual data transmission after cooperation) occupies the RB, part of the transmission power is used as a cost on the information exchange among the members in the coalition [13–18], and the remaining power is used for actual data transmission. The cost is the sum of the power that is used to each member in a coalition S exchanging information to its corresponding farthest member inside S. For instance, the power needed for broadcast transmission between a member i∈S and its corresponding farthest member i^∈S is given by
(1)P¯i,i^=κ0·σ2gi,i^k,
where κ0 is a target SNR for information exchange; gi,i^k=h2·di,i^(-α) is the exchange of information link from member i to member i^ when RBk is allocated to it for data transmission; h is the path loss constant; α is the path loss exponent; and di,i^ is the distance between member i and member i^. As a consequence, the total power cost denoted by P^S for a coalition S is given by
(2)P^S=∑x∈X,Ux∈S‍P¯Ux,U^x+∑y∈Y,Dy∈S‍P¯Dy,D^y.As the defined cost in (2) depends on the location of the members and the size of the coalition, a higher power cost is incurred whenever the distance between the members increases or the size of coalition increases.Thus, the actual power constraint of the cellular UEUx per coalition S is given by
(3)PUx=Pb-P¯Ux,U^x+.Also, the actual power constraint of the D2D pairDy per coalition S is given by
(4)PDy=Pd-P¯Dy,D^y+,
where it defines a+≜max⁡(a,0).Thus the fraction power used for data transmission of coalitionS is
(5)PS=∑x∈X,Ux∈S‍PUx+∑y∈Y,Dy∈S‍PDy.The instantaneous signal-to-interference-plus-noise ratio (SINR) at cellular UEUx, x∈X, when RBk is allocated to it for data transmission, can be given as follows:
(6)SINRUxk=PUx·gUxkσ2+∑Dy∈SPDygDj,t,Uxk,
and the instantaneous SINR at the receiver of the D2D pair Dy, that is, Dy,r, y∈Y, when RBk is allocated to it for data transmission, can be given as follows:
(7)SINRDyk=PDy·gDy,t,Dy,rkσ2+∑Ux∈SPUxgb,Dy,rk/K+∑j≠Y,Dy∈SPDygDj,t,Dy,rk.


## 2.2. Frequency Resource Allocation Problem

In the underlaying D2D communication system, the interference problem is not negligible, which, therefore, calls for optimal RB assignment solution to reduce the interference, and then each communication link can properly perform its individual data transmission. According to the Shannon capacity formula, we define thesum rate of the cellular network as the sum of the channel capacities for all the communication links within the network. Let S(X+Y)×K=UX×KDY×K be an RB assignment solution, where UX×K=αx,k and DY×K=βy,k denote the RB assignment matrix for the traditional cellular communication links and the D2D communication links, respectively. The value of αx,k and βy,k, with x∈X, y∈Y, and k∈K, can be defined as follows:
(8)αx,k=1,whenRBkisallocated  toUx,0,otherwise,(9)βy,k=1,whenRBkallocated  toDy,0,otherwise.Therefore, we can obtain the optimal RB assignment solution, denoted bySopt, solving the optimization problem as follows:
(10)Sopt=argmax⁡S(X+Y)×K∑k=1K‍WK∑x=1X‍log21+SINRUxkαx,kiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+∑y=1Y‍log21+SINRDykβy,k(11)s.t.S=Ux,Dy∣αx,k=1,βy,k=1,x∈X,y∈Y,∑x=1X‍αx,k≤1,∑k=1K‍αx,k≤1,∑k=1K‍βy,k≤1,
where SINRUxk and SINRDyk are given in (6) and (7), respectively. Particularly, the second constraint in (11) guarantees that different traditional cellular UEs can never occupy the same RB for data transmission. The third constraint in (11) guarantees that each user can obtain at most one RB in an OFDM symbol through every RB assignment process.The optimal RB assignment solution in (10) and (11) can be obtained through an exhaustive search for all the possible choices of αx,k and βy,k subjected to the conditions given in (11), where αx,k and βy,k are independent of each other. Then, the computational complexity can be obtained as the multiplication of the complexity with all possible choices of αx,k and βy,k. So the computational complexity of it can be obtained as follows:
(12)Toptimal=O∑k=0K‍HXkY+1K-1K-1!,
where (n)! denotes the factorial computation of a nonnegative integer n and Hmn represents the permutation operation, which is defined as
(13)Hmn=(m)!(m-n)!,whenm≥n,0,otherwise,
where m and n are both nonnegative integers, and we further define (0)!=1.Based on (13), the optimal RB assignment solution is an NP-hard combinatorial optimization problem with nonlinear constraints; particularly, as the number of cellular UEs and D2D pairs grows, the computational complexity increases rapidly. In other words, directly finding an optimal solution of the aforementioned optimization problem is computationally prohibitive, and no polynomial-time algorithm can optimally solve it. Therefore, in the following section, we formulate this resource allocation problem as a coalitional formation game and solve it in a distributed manner with low computational complexity.


## 3. Frequency Resource Allocation Using Coalitional Game

In this section, we formulate the frequency resource assignment problem among both cellular UEs and D2D pairs as a coalitional game with transferable utility (TU). In the game, each player seeks to obtain an optimal RB for its individual data transmission, while it has to share the RB with some other players within the same resource group.


### 3.1. Utility Function

The utilities of the player in the coalition are defined as the transmission rate which can be achieved through the RBs allocated to it. Therefore, the utility of cellular UEUx, x∈X, denoted by RUx, can be obtained as follows:
(14)RUx=∑k=1K‍αx,kWKlog21+SINRUxk,
and the utility of D2D pair Dy, y∈Y, denoted by UDy, is given as
(15)RDy=∑k=1K‍βy,kWKlog21+SINRDyk,
where SINRUxk, SINRDyk, αx,k, and βy,k are given in (6), (7), (8), and (9), respectively.Note that for a certain communication link every player has different performance on different RBs, and so each of them has two individual attributes, the identity order listL(V) and the current identity δ(V), where V=Ux or Dy, x∈X, y∈Y. The L(V) is a vector of RB indices corresponding to the highest signal-to-noise ratio (SNR) at the receiver of the communication link to the lowest SNR, and δ(V) is the first element of L(V) which indicates the current interested RB index of the player.


### 3.2. Coalitional Game

We use a coalitional TU game(T,v) to analyze the distributed resource assignment process, where T represents the set of players; that is, T=U∪D, and v(S) is the value of a coalition S, S⊆T. Note that, in our assumption, only the players seeking for the same RB can cooperate with each other to form a coalition. Based on the current identity δ(V) of each player, we divided the coalitional TU game (T,v) into K types of subcoalition games, and each coalition, denoted by Sk, k∈K, corresponds to the K RBs. The value v of a coalition Sk can be given as follows:
(16)vSk=0,ifSk=Φ,WK∑i=1Sk‍log21+SINRVik,otherwise,
where |Sk| denotes the number of members in the coalition Sk, Vi=Ux or Dy, x∈X, y∈Y, Vi∈Sk, and Φ represents the empty set.We define the payoff of each player in a coalitionSk, k∈K, as the individual contribution to the coalition value that it offers. Therefore, the payoff of the player Vi, i=1,2,…,|Sk|, in coalition Sk can be given as follows:
(17)ϕik=vSk-vSkVi,
where Sk/{Vi} denotes the coalition transformed from Sk by deleting Vi in it. Note that vΦ=0 in our definition of the coalition value, and thus ϕik=vSk if there is only one player Vi in coalition Sk; that is, Sk={Vi}. We can guarantee that finally at most one cellular UE will stay in a coalition by the payoff allocation policy in which only the cellular UE has the highest payoff (note that this payoff of a cellular UE is calculated by (17) when supposing that all the other cellular UEs are removed from the current coalition) can obtain the payoff while the payoffs of the other cellular UEs in the same coalition are set equal to a high negative value. Then, those cellular UEs with negative payoffs will deviate from the coalition on their own initiative.In this paper, the proposed distributed resource assignment(T,v) coalitional game will seldom form the grand coalition and, instead, disjoint coalitions will form in the network due to the cost.Definition 1.
A coalitional TU game(T,v) is said to be superadditive if for any two disjoint coalitions S1,S2⊂T, v(S1∪S2)≥v(S1)+v(S2).Theorem 2.
The proposed distributed resource assignment(T,v) coalition game with cost is, in general, nonsuperadditive.Proof.
Consider that two disjoint coalitionsS1⊂T and S2⊂T in the network, with the player of S1∪S2 located far enough to yield a very large power cost per (2) cause the data transmission power in (5)  PS=0. Then by (16) the coalition value of S1∪S2 is v(S1∪S2)=0<v(S1)+v(S2), so the proposed distributed resource assignment (T,v) coalition game is not superadditive.Definition 3.
Anϕk is said to be unstable through a coalition S, if v(S)>∑i∈Sϕk; that is, the players have an incentive to form coalition S and reject the proposed ϕk. The set C of stable imputations is called the core; that is,
(18)C={ϕk:∑i∈N‍ϕik=v(N),∑i∈N‍ϕik≥v(S),∀S⊆T}.
A nonempty core means that the players have an incentive to form the grand coalition.Theorem 4.
In general, the core of the proposed(T,v) coalitional game with cost is empty.Based on the previous analysis, the cost on cooperation information exchange for a coalitionS increases with the number of the player and the distance between the players in S. Because this coalition consists of a large number of users who are randomly located at different location, so similar to the proof of Theorem 2, consider two disjoint coalitions S1 and S2 with v(S1∪S2)=0 due to the cooperation costs. In this case, coalitions S1 and S2 have no interest to combine with each other to form a grand coalition, so they form two independent disjoint coalitions. As a consequence, the core of the proposed game does not exist. Because of the nonsuperadditivity of the game and the emptiness of the core, the grand coalition of all players will not form.Considering that there are some different types of coalitions and only the coalitions of the same type can be merged together, we divide the defined coalitional game(T,v) into K coalitional subgames, denoted by (Tk,vk), k∈K, where Tk=Vi∣δ(Vi)=k,Vi∈T, T=T1∪T2∪⋯∪TK, Tk1∩Tk2=Φ, k1, k2∈K, k1≠k2, and vk is defined the same as v in (16). However, the K coalitional subgames cannot proceed independently during the resource assignment, since each player in the game can change its current identity due to the payoff. Every player can obtain its current identity in the current coalitional subgame group, and then it joins another coalitional subgame group to seek for the corresponding RB which may bring it higher potential payoff. Thus, the K coalitional subgames need to dynamically update their own group information once one of the players makes a decision to change its current identity during the resource allocation.


## 3.1. Utility Function

The utilities of the player in the coalition are defined as the transmission rate which can be achieved through the RBs allocated to it. Therefore, the utility of cellular UEUx, x∈X, denoted by RUx, can be obtained as follows:
(14)RUx=∑k=1K‍αx,kWKlog21+SINRUxk,
and the utility of D2D pair Dy, y∈Y, denoted by UDy, is given as
(15)RDy=∑k=1K‍βy,kWKlog21+SINRDyk,
where SINRUxk, SINRDyk, αx,k, and βy,k are given in (6), (7), (8), and (9), respectively.Note that for a certain communication link every player has different performance on different RBs, and so each of them has two individual attributes, the identity order listL(V) and the current identity δ(V), where V=Ux or Dy, x∈X, y∈Y. The L(V) is a vector of RB indices corresponding to the highest signal-to-noise ratio (SNR) at the receiver of the communication link to the lowest SNR, and δ(V) is the first element of L(V) which indicates the current interested RB index of the player.


## 3.2. Coalitional Game

We use a coalitional TU game(T,v) to analyze the distributed resource assignment process, where T represents the set of players; that is, T=U∪D, and v(S) is the value of a coalition S, S⊆T. Note that, in our assumption, only the players seeking for the same RB can cooperate with each other to form a coalition. Based on the current identity δ(V) of each player, we divided the coalitional TU game (T,v) into K types of subcoalition games, and each coalition, denoted by Sk, k∈K, corresponds to the K RBs. The value v of a coalition Sk can be given as follows:
(16)vSk=0,ifSk=Φ,WK∑i=1Sk‍log21+SINRVik,otherwise,
where |Sk| denotes the number of members in the coalition Sk, Vi=Ux or Dy, x∈X, y∈Y, Vi∈Sk, and Φ represents the empty set.We define the payoff of each player in a coalitionSk, k∈K, as the individual contribution to the coalition value that it offers. Therefore, the payoff of the player Vi, i=1,2,…,|Sk|, in coalition Sk can be given as follows:
(17)ϕik=vSk-vSkVi,
where Sk/{Vi} denotes the coalition transformed from Sk by deleting Vi in it. Note that vΦ=0 in our definition of the coalition value, and thus ϕik=vSk if there is only one player Vi in coalition Sk; that is, Sk={Vi}. We can guarantee that finally at most one cellular UE will stay in a coalition by the payoff allocation policy in which only the cellular UE has the highest payoff (note that this payoff of a cellular UE is calculated by (17) when supposing that all the other cellular UEs are removed from the current coalition) can obtain the payoff while the payoffs of the other cellular UEs in the same coalition are set equal to a high negative value. Then, those cellular UEs with negative payoffs will deviate from the coalition on their own initiative.In this paper, the proposed distributed resource assignment(T,v) coalitional game will seldom form the grand coalition and, instead, disjoint coalitions will form in the network due to the cost.Definition 1.
A coalitional TU game(T,v) is said to be superadditive if for any two disjoint coalitions S1,S2⊂T, v(S1∪S2)≥v(S1)+v(S2).Theorem 2.
The proposed distributed resource assignment(T,v) coalition game with cost is, in general, nonsuperadditive.Proof.
Consider that two disjoint coalitionsS1⊂T and S2⊂T in the network, with the player of S1∪S2 located far enough to yield a very large power cost per (2) cause the data transmission power in (5)  PS=0. Then by (16) the coalition value of S1∪S2 is v(S1∪S2)=0<v(S1)+v(S2), so the proposed distributed resource assignment (T,v) coalition game is not superadditive.Definition 3.
Anϕk is said to be unstable through a coalition S, if v(S)>∑i∈Sϕk; that is, the players have an incentive to form coalition S and reject the proposed ϕk. The set C of stable imputations is called the core; that is,
(18)C={ϕk:∑i∈N‍ϕik=v(N),∑i∈N‍ϕik≥v(S),∀S⊆T}.
A nonempty core means that the players have an incentive to form the grand coalition.Theorem 4.
In general, the core of the proposed(T,v) coalitional game with cost is empty.Based on the previous analysis, the cost on cooperation information exchange for a coalitionS increases with the number of the player and the distance between the players in S. Because this coalition consists of a large number of users who are randomly located at different location, so similar to the proof of Theorem 2, consider two disjoint coalitions S1 and S2 with v(S1∪S2)=0 due to the cooperation costs. In this case, coalitions S1 and S2 have no interest to combine with each other to form a grand coalition, so they form two independent disjoint coalitions. As a consequence, the core of the proposed game does not exist. Because of the nonsuperadditivity of the game and the emptiness of the core, the grand coalition of all players will not form.Considering that there are some different types of coalitions and only the coalitions of the same type can be merged together, we divide the defined coalitional game(T,v) into K coalitional subgames, denoted by (Tk,vk), k∈K, where Tk=Vi∣δ(Vi)=k,Vi∈T, T=T1∪T2∪⋯∪TK, Tk1∩Tk2=Φ, k1, k2∈K, k1≠k2, and vk is defined the same as v in (16). However, the K coalitional subgames cannot proceed independently during the resource assignment, since each player in the game can change its current identity due to the payoff. Every player can obtain its current identity in the current coalitional subgame group, and then it joins another coalitional subgame group to seek for the corresponding RB which may bring it higher potential payoff. Thus, the K coalitional subgames need to dynamically update their own group information once one of the players makes a decision to change its current identity during the resource allocation.


## 4. Coalition Formation Algorithm

This section aims to design a distributed merge-and-split based coalition formation algorithm to solve the resource assignment problem in the investigated D2D communications underlaying cellular network.


### 4.1. Coalition Formation Concepts

To construct a coalition formation process suitable to the proposed coalitional game, we need several definitions as follows.Definition 5.
Acollection of coalitions, denoted by P, is defined as a set P=S1,S2,…,Sp of mutually disjoint coalitions Si⊂T. In other words, a collection is any arbitrary group of disjoint coalitions Si of T that is not necessarily spanning all the players of T. If a collection P spans all the players of T, that is, ⋃i=1pSi=T, then the collection is recognized as apartition of T.Definition 6.
Consider two collectionsP=S1,…,Sp and Q=S1*,…,Sq* which are partitions of the same subset T*⊆T (i.e., the same players in P and Q). Then, acomparison relation⊳ is defined as that P⊳Q implies the way P partitioning T* is preferred to the way Q partitioning T*.In the proposed coalition formation game, among all of the same type coalitions only one coalition which has the maximum coalition value can obtain the corresponding RB for data transmission, which means that if a player cannot join the coalition with the maximum coalition value, it cannot obtain its preferred RB, and then its payoff would be zero. Based on this, all of the disjoint coalitions of the same coalition type are preferred to combine with others if they can form a stronger one with a higher coalition value instead, and thus all the players of them will have more chance to obtain their corresponding RB for their individual data transmission. Then, we define a new comparison relation with respect to the investigated resource assignment problem as follows.Definition 7.
Consider two collectionsP=S1,…,Sp and Q=S1*,…,Sq* with the same players in them. Then, theMax-Coalition orderP⊳Q is defined as follows:
(19)max⁡{v(S1),…,v(Sp)}>max⁡{v(S1*),…,v(Sq*)},
where max⁡{⋯} means the maximum value of a vector.


### 4.2. Merge-and-Split Based Coalition Formation Algorithm

Based on the coalition formation concepts defined in the previous subsection, we construct a distributed coalition formation algorithm based on two simple rules denoted by “merge” and “split” which permit modifying a partition ofT [13].(1) Merge Rule. Merge any set of coalitions S1,…,Sl whenever the merge form is preferred, that is, where ⋃j=1l‍Sj⊳S1,…,Sl; then S1,…,Sl→⋃j=1l‍Sj.(2) Split Rule. Split any set of coalitions ⋃j=1l‍Sj whenever the split form is preferred, that is, where S1,…,Sl⊳⋃j=1l‍Sj; then ⋃j=1l‍Sj→S1,…,Sl.According to the above rules, some coalitions can merge into a larger coalition if the coalitional game can yield a preferred partition based on the Max-Coalition order. This implies that if the merged coalition has a higher value than any of the disjoint coalitions, a group of players will form a larger coalition to improve the opportunity for winning the corresponding RB for their individual data transmission. Note that the merge can only occur among disjoint coalitions of the same coalition type due to our assumption that only the players of the same identity, that is, seeking for the same RB currently, can form a coalition. Similarly, an existing coalition can make a decision to split into smaller disjoint coalitions if splitting can yield a preferred partition based on the Max-Coalition order.Based on the defined merge-and-split rules, we construct the distributed coalition formation algorithm as follows.Phase 1: State Initialization
(i)
Each cellular UE and D2D pair acts as a player participating in the proposed coalitional game in order to acquire its interested RB for individual data transmission. Each player, denoted byVi, initializes its attributes based on the CSI of its own communication link.
(a)
V
i calculates its identity order list L(Vi) according to the SNR on different RBs. The identity order list disposes the RB index with a higher SNR in the front and the RB index with a lower SNR followed in order.
(b)
V
i initializes its current identity δ(Vi) as the first element in L(Vi).
(ii)
The proposed coalitional game is divided intoK coalitional subgames. Each player in the proposed coalitional game chooses to join a corresponding coalitional subgame based on its current identity δ(Vi) and is regarded as a disjoint independent coalition.Phase 2: Iterative Coalition FormationRepeat
(i)
Each subgame deals with the merge-and-split based coalition formation concurrently and independently until reaching a temporal stable partition.
(1)
Iteration indext=0.
(2)
Repeat
(a)
P
t
k =Merge(Ttk): coalitions in Ttk decide to merge into a temporal subpartition Ptk based on the merge rules.
(b)
Q
t
k =Split(Ptk): coalitions in Ptk decide to split into a temporal subpartition Qtk based on the split rules.
(c)
Updatet=t+1 and Ttk=Qtk.
(3)
Until merge-and-split operations terminate.
(ii)
Each player checks whether it is in the coalition with the highest value in the current subgame.
(1)
IfVi with the current identity δ(Vi)=k*, k*∈K, is in the coalition with the highest value of type k*, then Vi stays in the current state.
(2)
Else,Vi removes k* from the vector of its identity order list and changes its identity by updating δ(Vi).
(iii)
Each subgame updates its own player group and gets ready to start another round merge-and-split based coalition formation process to reach a new temporal stable partition if the player group of it is changed.Until all the players either stay in the coalition with the highest value of a certain type or have an empty vector of the identity order list left.Phase 3: Resource Assignment
(i)
Each coalition reports its current identity and coalition value to the BS, based on which the BS allocates each RB to the coalition with the highest value of the corresponding identity for the data transmission of its players.


### 4.3. Complexity Analysis

According to the distributed coalition formation algorithm, which is processed in an iterative manner, different initial states of distributed coalition formation constructed based on the current location of the cellular UEs and D2D pairs and the information of the communication links in the cellular network will lead to a different number of iterations to obtain the final RB assignment solution, and thus the proposed algorithm has different computational complexity. Based on the procedure of the proposed distributed coalition formation algorithm, the worst-case complexity denoted byTcoalition can be easily calculated when considering the case that each cellular UE and D2D pair experiences all the virtual clusters and is given as follows:
(20)Tcoalition=O((X+Y+1)·(X+Y)·K),
where we treat the computational complexity of the problem to find a maximum or minimum value from a cluster with N values as O(N). Compared with the complexity of the optimal resource-allocation scheme calculated in (12), the proposed distributed coalition formation algorithm can effectively reduce the computational complexity to obtain the RB allocation solution.


### 4.4. Partition Stability

The result of the proposed distributed coalition formation algorithm is a cellular network partition composed of disjoint independent coalitions. In [19, 20], the authors used the concept of a defection function to investigate the stability of network partition.Definition 8.
A defection functionD associates with any partition T=T1,…,Tl as a group of collections in V. If no players are interested in leaving the current partition T to form another coalition, then the partition of T is D-stable.Here there are two important two defection functions. One is the weak equilibrium-like stability, known asDhp function which associates with each partition T of V, and the group of all partitions of V can be formed through merge or split. The other one is the Dc function which associates with each partition T of V which is the group of all collections in V. This function allows any group of players to leave the partition T of V through any operation and to create an arbitrary collection in V. Two forms of stability steming from these definitions are as follows: Dhp-stability and a stronger Dc-stability. If no player in T is interested in leaving T through merge-and-split to form other partitions in V, then the partition T is Dhp-stable. If no player in T is interested in leaving T through any operation (not necessarily merge or split) to form other collections in V, then a partition T is Dc-stable.Therefore, a partition isDhp-stable if no coalition has an incentive to split or merge. Thus, a partition T=T1,…,Tl is Dhp-stable, if the following two necessary and sufficient conditions are satisfied (⋫ is the nonpreference operator, opposite of ⊳).(i)
For eachi∈1,…,m and each partition R1,…,Rm of Ti∈T, we have
(21)R1,…,Rm⋫Ti.(ii)
For eachS⊆1,…,m, we have
(22)⋃i∈S‍Ti⋫Ti∣i∈S.The above conditions are the generalized forms of theDhp-stability conditions presented in [20]. Using this definition of Dhp-stability, we have the following theorem.Theorem 9.
Every partition resulting from the proposed distributed coalition formation algorithm isDhp-stable.Proof.
Consider a partitionT resulting from the convergence of an iteration of merge-and-split operations such as in the distributed merge-and-split based coalition formation algorithm that we proposed; then no coalition in T can leave this partition through merge or split. Assume that T=T1,…,Tl is the partition resulting from the proposed merge-and-split algorithm; if, for any i∈1,…,l and any partition S1,…,Sm of Ti, we assume that S1,…,Sm⊳Ti, then the partition T can still be modified through the application of the split rule on Ti contradicting with the fact that T resulted from a termination of the merge-and-split iteration; therefore, S1,…,Sm⋫Ti (first Dhp-stability condition verified). A similar reasoning is applicable in order to prove that T verifies the second condition, and otherwise a merge rule would still be applicable.Nevertheless, a stronger form of stability can be sought using strictDc-stability. The appeal of a strictly Dc-stable partition is not always guaranteed for its existence which needs two conditions [20].(1)
TheDc-stable partition is the unique outcome of any arbitrary iteration of merge-and-split operations on any partition of V.(2)
TheDc-stable partition is to maximize the social welfare which is the sum of the utilities of all coalitions in a partition.Thus, in our proposed coalition formation game, because of the cooperation cost, the first condition ofDc-stability depends on the location of cellular UEs and D2D pairs in the network. In fact, an ideal case with no cost for cooperation was analyzed in [12], and as the number of the users increases for a fixed power constraint, the system’s diversity increases. Actually, consider a partition T=T1,…,Tl of V and two disjoint coalitions S1 and S2 such that {S1∪S2}⊂Ti. Assuming that no cost for cooperation exists, the value of the coalition S1∪S2, denoted by v(S1∪S2), is larger than the values v(S1) and v(S2) of the coalitions S1 and S2 acting noncooperatively (due to the larger number of users in S1∪S2), and thus |S1∪S2|·v(S1∪S2)>|S1∪S2|·max⁡(v(S1),v(S2)) with |S1∪S2|=|S1|+|S2|. As a result, v(S1∪S2) satisfies
(23)S1∪S2·vS1∪S2>S1·CS1+S2·CS2.From (23), v(S1∪S2)>v(S1)+v(S2) is the necessary condition to verify the first Dc-stability condition. However, due to the cost given by (2), v(S1∪S2), v(S1), and v(S2) can have different power constraints, that is, users location, and this condition is not always verified. Therefore, in practical networks guaranteeing the first condition for existence of a strictly Dc-stabe partition is random due to the random location of the users. Furthermore, for a partition T=T1,…,Tl, the second condition of Dc-stability is also dependent on the distance between the users in different coalitions Ti∈T.In summary, the existence of theDc-stable partition is tied closely to the users location, which is a random parameter in practical networks.


## 4.1. Coalition Formation Concepts

To construct a coalition formation process suitable to the proposed coalitional game, we need several definitions as follows.Definition 5.
Acollection of coalitions, denoted by P, is defined as a set P=S1,S2,…,Sp of mutually disjoint coalitions Si⊂T. In other words, a collection is any arbitrary group of disjoint coalitions Si of T that is not necessarily spanning all the players of T. If a collection P spans all the players of T, that is, ⋃i=1pSi=T, then the collection is recognized as apartition of T.Definition 6.
Consider two collectionsP=S1,…,Sp and Q=S1*,…,Sq* which are partitions of the same subset T*⊆T (i.e., the same players in P and Q). Then, acomparison relation⊳ is defined as that P⊳Q implies the way P partitioning T* is preferred to the way Q partitioning T*.In the proposed coalition formation game, among all of the same type coalitions only one coalition which has the maximum coalition value can obtain the corresponding RB for data transmission, which means that if a player cannot join the coalition with the maximum coalition value, it cannot obtain its preferred RB, and then its payoff would be zero. Based on this, all of the disjoint coalitions of the same coalition type are preferred to combine with others if they can form a stronger one with a higher coalition value instead, and thus all the players of them will have more chance to obtain their corresponding RB for their individual data transmission. Then, we define a new comparison relation with respect to the investigated resource assignment problem as follows.Definition 7.
Consider two collectionsP=S1,…,Sp and Q=S1*,…,Sq* with the same players in them. Then, theMax-Coalition orderP⊳Q is defined as follows:
(19)max⁡{v(S1),…,v(Sp)}>max⁡{v(S1*),…,v(Sq*)},
where max⁡{⋯} means the maximum value of a vector.


## 4.2. Merge-and-Split Based Coalition Formation Algorithm

Based on the coalition formation concepts defined in the previous subsection, we construct a distributed coalition formation algorithm based on two simple rules denoted by “merge” and “split” which permit modifying a partition ofT [13].(1) Merge Rule. Merge any set of coalitions S1,…,Sl whenever the merge form is preferred, that is, where ⋃j=1l‍Sj⊳S1,…,Sl; then S1,…,Sl→⋃j=1l‍Sj.(2) Split Rule. Split any set of coalitions ⋃j=1l‍Sj whenever the split form is preferred, that is, where S1,…,Sl⊳⋃j=1l‍Sj; then ⋃j=1l‍Sj→S1,…,Sl.According to the above rules, some coalitions can merge into a larger coalition if the coalitional game can yield a preferred partition based on the Max-Coalition order. This implies that if the merged coalition has a higher value than any of the disjoint coalitions, a group of players will form a larger coalition to improve the opportunity for winning the corresponding RB for their individual data transmission. Note that the merge can only occur among disjoint coalitions of the same coalition type due to our assumption that only the players of the same identity, that is, seeking for the same RB currently, can form a coalition. Similarly, an existing coalition can make a decision to split into smaller disjoint coalitions if splitting can yield a preferred partition based on the Max-Coalition order.Based on the defined merge-and-split rules, we construct the distributed coalition formation algorithm as follows.Phase 1: State Initialization
(i)
Each cellular UE and D2D pair acts as a player participating in the proposed coalitional game in order to acquire its interested RB for individual data transmission. Each player, denoted byVi, initializes its attributes based on the CSI of its own communication link.
(a)
V
i calculates its identity order list L(Vi) according to the SNR on different RBs. The identity order list disposes the RB index with a higher SNR in the front and the RB index with a lower SNR followed in order.
(b)
V
i initializes its current identity δ(Vi) as the first element in L(Vi).
(ii)
The proposed coalitional game is divided intoK coalitional subgames. Each player in the proposed coalitional game chooses to join a corresponding coalitional subgame based on its current identity δ(Vi) and is regarded as a disjoint independent coalition.Phase 2: Iterative Coalition FormationRepeat
(i)
Each subgame deals with the merge-and-split based coalition formation concurrently and independently until reaching a temporal stable partition.
(1)
Iteration indext=0.
(2)
Repeat
(a)
P
t
k =Merge(Ttk): coalitions in Ttk decide to merge into a temporal subpartition Ptk based on the merge rules.
(b)
Q
t
k =Split(Ptk): coalitions in Ptk decide to split into a temporal subpartition Qtk based on the split rules.
(c)
Updatet=t+1 and Ttk=Qtk.
(3)
Until merge-and-split operations terminate.
(ii)
Each player checks whether it is in the coalition with the highest value in the current subgame.
(1)
IfVi with the current identity δ(Vi)=k*, k*∈K, is in the coalition with the highest value of type k*, then Vi stays in the current state.
(2)
Else,Vi removes k* from the vector of its identity order list and changes its identity by updating δ(Vi).
(iii)
Each subgame updates its own player group and gets ready to start another round merge-and-split based coalition formation process to reach a new temporal stable partition if the player group of it is changed.Until all the players either stay in the coalition with the highest value of a certain type or have an empty vector of the identity order list left.Phase 3: Resource Assignment
(i)
Each coalition reports its current identity and coalition value to the BS, based on which the BS allocates each RB to the coalition with the highest value of the corresponding identity for the data transmission of its players.


## 4.3. Complexity Analysis

According to the distributed coalition formation algorithm, which is processed in an iterative manner, different initial states of distributed coalition formation constructed based on the current location of the cellular UEs and D2D pairs and the information of the communication links in the cellular network will lead to a different number of iterations to obtain the final RB assignment solution, and thus the proposed algorithm has different computational complexity. Based on the procedure of the proposed distributed coalition formation algorithm, the worst-case complexity denoted byTcoalition can be easily calculated when considering the case that each cellular UE and D2D pair experiences all the virtual clusters and is given as follows:
(20)Tcoalition=O((X+Y+1)·(X+Y)·K),
where we treat the computational complexity of the problem to find a maximum or minimum value from a cluster with N values as O(N). Compared with the complexity of the optimal resource-allocation scheme calculated in (12), the proposed distributed coalition formation algorithm can effectively reduce the computational complexity to obtain the RB allocation solution.


## 4.4. Partition Stability

The result of the proposed distributed coalition formation algorithm is a cellular network partition composed of disjoint independent coalitions. In [19, 20], the authors used the concept of a defection function to investigate the stability of network partition.Definition 8.
A defection functionD associates with any partition T=T1,…,Tl as a group of collections in V. If no players are interested in leaving the current partition T to form another coalition, then the partition of T is D-stable.Here there are two important two defection functions. One is the weak equilibrium-like stability, known asDhp function which associates with each partition T of V, and the group of all partitions of V can be formed through merge or split. The other one is the Dc function which associates with each partition T of V which is the group of all collections in V. This function allows any group of players to leave the partition T of V through any operation and to create an arbitrary collection in V. Two forms of stability steming from these definitions are as follows: Dhp-stability and a stronger Dc-stability. If no player in T is interested in leaving T through merge-and-split to form other partitions in V, then the partition T is Dhp-stable. If no player in T is interested in leaving T through any operation (not necessarily merge or split) to form other collections in V, then a partition T is Dc-stable.Therefore, a partition isDhp-stable if no coalition has an incentive to split or merge. Thus, a partition T=T1,…,Tl is Dhp-stable, if the following two necessary and sufficient conditions are satisfied (⋫ is the nonpreference operator, opposite of ⊳).(i)
For eachi∈1,…,m and each partition R1,…,Rm of Ti∈T, we have
(21)R1,…,Rm⋫Ti.(ii)
For eachS⊆1,…,m, we have
(22)⋃i∈S‍Ti⋫Ti∣i∈S.The above conditions are the generalized forms of theDhp-stability conditions presented in [20]. Using this definition of Dhp-stability, we have the following theorem.Theorem 9.
Every partition resulting from the proposed distributed coalition formation algorithm isDhp-stable.Proof.
Consider a partitionT resulting from the convergence of an iteration of merge-and-split operations such as in the distributed merge-and-split based coalition formation algorithm that we proposed; then no coalition in T can leave this partition through merge or split. Assume that T=T1,…,Tl is the partition resulting from the proposed merge-and-split algorithm; if, for any i∈1,…,l and any partition S1,…,Sm of Ti, we assume that S1,…,Sm⊳Ti, then the partition T can still be modified through the application of the split rule on Ti contradicting with the fact that T resulted from a termination of the merge-and-split iteration; therefore, S1,…,Sm⋫Ti (first Dhp-stability condition verified). A similar reasoning is applicable in order to prove that T verifies the second condition, and otherwise a merge rule would still be applicable.Nevertheless, a stronger form of stability can be sought using strictDc-stability. The appeal of a strictly Dc-stable partition is not always guaranteed for its existence which needs two conditions [20].(1)
TheDc-stable partition is the unique outcome of any arbitrary iteration of merge-and-split operations on any partition of V.(2)
TheDc-stable partition is to maximize the social welfare which is the sum of the utilities of all coalitions in a partition.Thus, in our proposed coalition formation game, because of the cooperation cost, the first condition ofDc-stability depends on the location of cellular UEs and D2D pairs in the network. In fact, an ideal case with no cost for cooperation was analyzed in [12], and as the number of the users increases for a fixed power constraint, the system’s diversity increases. Actually, consider a partition T=T1,…,Tl of V and two disjoint coalitions S1 and S2 such that {S1∪S2}⊂Ti. Assuming that no cost for cooperation exists, the value of the coalition S1∪S2, denoted by v(S1∪S2), is larger than the values v(S1) and v(S2) of the coalitions S1 and S2 acting noncooperatively (due to the larger number of users in S1∪S2), and thus |S1∪S2|·v(S1∪S2)>|S1∪S2|·max⁡(v(S1),v(S2)) with |S1∪S2|=|S1|+|S2|. As a result, v(S1∪S2) satisfies
(23)S1∪S2·vS1∪S2>S1·CS1+S2·CS2.From (23), v(S1∪S2)>v(S1)+v(S2) is the necessary condition to verify the first Dc-stability condition. However, due to the cost given by (2), v(S1∪S2), v(S1), and v(S2) can have different power constraints, that is, users location, and this condition is not always verified. Therefore, in practical networks guaranteeing the first condition for existence of a strictly Dc-stabe partition is random due to the random location of the users. Furthermore, for a partition T=T1,…,Tl, the second condition of Dc-stability is also dependent on the distance between the users in different coalitions Ti∈T.In summary, the existence of theDc-stable partition is tied closely to the users location, which is a random parameter in practical networks.


## 5. Simulation Results and Analysis

To evaluate the efficiency of the proposed merge-and-split based coalition formation algorithm for the frequency resource allocation in the hybrid D2D-cellular network, the following simulations are conducted. Consider an isolated cellular cell, where traditional cellular communications and D2D communications coexist and can share the RB for their individual data transmission. The cellular UEs and D2D pairs are distributed randomly within the network, where each D2D pair has a fixed distance between the transmitter and the receiver. The main simulation parameters are set as in Table1.Table 1
Simulation parameters.
Parameters
Value
Channel bandwidthW
20 MHz
Total RB numberK
10
Cell radius
500 m
D2D pair distance
10 m
BS’s transmit powerPb
46 dBm
Device’s transmit powerPd
24 dBm
Path loss model
UMi model in [21–24]
Small-scale fading
Rayleigh fading coefficient
Noise power spectral density
−174 dBm/Hz
Noise figure
5 dBIn Figure2, we show an example that the cellular UE number is X=3 and D2D pairs number is Y=6 with random distribution in the network, and the total RB number is K=3. The final coalition structure of the network based on the proposed merge-and-split based coalition formation algorithm is showed. Clearly, the proposed algorithm allows the users to structure themselves into disjoint independent coalitions for the purpose of max sum rate of the network. Considering the formed coalition 1 including U1,D5,D6, since the distance between them is small enough, the cooperation cost in this coalition is less than the transmission power by (3) and (4), so the value v of coalition 1 is nonzero, and then by (17) the payoff of each user in this coalition is smaller than they merge from the coalition. Considering the D2D pair 2 in coalition 2, the distance between D2 and the members in coalition 1 is far away, and thus by (1) the power it needs for broadcast transmission is larger than Pd, so the utility function of D2 equals zero and D2 splits from coalition 1 to form coalition 2 with D1 pairs.Figure 2
A final coalition structure resulting from the proposed distributed coalition formation algorithm for a network ofX=3 UEs, Y=6 D2D pairs, and K=3 links.In Figure3, we compare three different resource assignment schemes for the investigated hybrid D2D-cellular network, that is, the greedy orthogonal resource assignment scheme, the proposed merge-and-split based coalition formation scheme, and the optimal resource assignment scheme formulated in (10) and (11), in terms of network sum transmission rate. From Figure 3, it is shown that the proposed coalition formation scheme can achieve a suboptimum performance compared with the optimal resource assignment scheme. While the proposed scheme can solve the K RBs resource assignment problem concurrently and in a distributed manner, compared with the optimal scheme, it has much lower computational complexity in obtaining the resource allocation solution.Figure 3
Comparison in terms of network sum rate between different schemes.As shown in Figure4, we compare the cumulative distribution function (CDF) in different SINR of the three different schemes. Obviously, compared with the greedy orthogonal resource assignment scheme, the performance of the proposed merge-and-split based coalition formation scheme improves almost 3 dB, while it has a little drop compared with the optimal resource assignment scheme.Figure 4
Comparison in terms of the cumulative distribution function of different SINR.


## 6. Conclusions

In this paper, we have investigated the resource allocation problem for the hybrid D2D-cellular system in a distributed manner. Specifically, we have formulated this problem as a coalitional game while accounting for the cost of cooperation in terms of power. Then, we have proposed a distributed merge-and-split based coalition formation algorithm to solve the resource allocation problem effectively based on the Max-Coalition order. Moreover, the stability of the hybrid D2D-cellular communication system partitions resulting from the proposed algorithm has been studied by the defection functionD. Simulation results have demonstrated efficiency of the proposed scheme in terms of network’s sum transmission rate.



---

*Source: 301932-2015-03-03.xml*