# Overlapping Coalition Game for Resource Allocation in Many-to-Many D2D Communication

Authors: Jihua Sheng; Sihan Liu; Tiancong Huang; Yucheng Wu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Device-to-device (D2D) communication is one of the promising technologies for the next-generation cellular network, which uses direct communication between two neighboring devices to obtain a high transmission rate. This paper focuses on wireless resource allocation in a many-to-many D2D communication scenario to maximize the D2D transmission sum rate. Through the model analysis, the objective function is formulated while guaranteeing the minimum transmission rate of both the cellular users (CUs) and the D2D pairs. Based on the candidate sequence, an overlapping coalition game algorithm is proposed to enhance the D2D transmission sum rate. Furthermore, the preference sequence of CUs is adopted in the coalition initialization. According to the interference intensity, a power allocation scheme is designed further to improve the transmission sum rate of the D2D pairs. The simulation results have verified the validity of the proposed algorithm.


---

## Body

## 1. Introduction

With the rapid development of the Internet of Things (IoT) and cellular technology, the demand for mobile internet access is growing at a tremendous rate in the past decade [1–3]. As one of the critical technologies of 5G [4, 5], device-to-device (D2D) communication can improve the transmission rate of communication networks, enhance the system throughput [6, 7], and reduce the communication delay [8]. D2D communication is a short-distance communication technology that data transmission can be directly carried out between two terminals. D2D communication can be operated as an underlay mode by sharing the cellular spectrum, which significantly improves the performance of network and the user experience [9, 10].In the hybrid network formed by the cellular users (CUs) and the D2D pairs, the communication quality will be affected. On the one hand, the D2D pairs reusing the cellular spectrum will disturb the communication of CUs. On the other hand, the D2D devices sharing the spectrum will be interfered by the corresponding CUs [11, 12]. Especially, the interferences will be more serious in many-to-many scenario, where one channel resource can be reused by multiple D2D pairs, and a D2D pair can reuse multiple channel resources. The transmission rate of D2D communication will be very small as the existence of serious interferences in a many-to-many scenario, which will restrict the development of D2D communication. Therefore, the methods of reasonable channel allocation and power control are very important in D2D communication research.This paper mainly focuses on the resource allocation and power control in many-to-many D2D communication, which is different from reported works, such as the random selection [13], cooperative game [14], or matching game with externalities [15] to reuse the channel resources and improve the D2D transmission sum rate. An overlapping coalition game algorithm based on the candidate sequence is proposed to further enhance the D2D transmission sum rate in this work. And the cellular user’s preference sequence is adopted to initialize the coalition. Furthermore, a power control scheme based on interference intensity is designed to improve the utility of the coalition.The main contributions of this paper are summarized as follows:(1)
In a many-to-many scenario, the system model was analyzed, and the sum transmission rate of D2D pairs with guaranteeing the quality of service (QoS) was formulated as the objective function(2)
An overlapping coalition game algorithm based on the candidate sequence was proposed to guide the channel resource allocation, which could enhance the transmission rate of D2D pairs. Furthermore, the preference sequence was used in the processing of the coalition initialization(3)
A power allocation scheme based on the preference sequence was proposed to allocate the powers of D2D pairs. To ensure the performance requirements of D2D pairs and CUs in the coalition, the coalition utility was used to evaluate whether the power allocation is effectiveThe rest of this paper is outlined as follows. The related works are described in Section2. Section 3 provides the system model and the problem formulation. Section 4 provides a detailed description of the resource allocation algorithm and the power control strategy. Simulation results are presented in Section 5. The conclusion is summarized in Section 6. For the sake of convenience, the major symbols used in this paper are listed in Table 1 with their definitions.Table 1
List of major symbols.
SymbolDescriptionNThe number of CUsMThe number of D2D pairsn0Gaussian white noiserm,nDThe transmission rate of themth D2D pair sharingThenth resource blockrnCThe transmission sum rate of thenth CUsξm,nDThe SINR of themth D2D pair sharing the nthResource blockξnCThe SINR of thenth CUpnCThe transmit power ofnth CUspmDThe transmit power of D2D pairsm′D2D pairs in the same coalition with themth pairDnA set of all the D2D pairs sharing the same resourceχm,nThe reusing indicator of CUsRCThe transmission sum rate of the all CUsRDThe transmission sum rate of the all D2D pairsgCn,mThe path gains from the transmitter of thenth CUs to the mth D2D pair receivergDm,mThe path gains from the transmitter of themth D2D pair to D2D pair receivergDm′,mThe path gains from the transmitter of them′th D2D pair to the mth D2D pair receivergDn,m,BThe link gain between themth D2D pair sharing the nth channel resource block and the base stationRthCThe rate thresholds of CUsRthDThe rate thresholds of D2D pairsgCn,BThe path gains of thenth CUs to the base stationgDm,BThe path gains of themth D2D pair to the base stationrnCThe transmission rate of CUspDmaxThe maximum transmit power of D2D pairsLThe players of all users in the system modelCSThe coalition structurevThe utility functionsHm,SlHistorical information tablepuThe power intervalkThe path loss constantβn,mThe multipath fading parameter from thenth CUs to receiver of the mth D2D pairωn,mThe shadow gain from thenth CUs to receiver of the mth D2D pairγn,mThe distance from thenth CUs to the receiver of the mth D2D pairαThe path loss factorSnA set of the corresponding D2D pairs and the CU that share thenth resource blockρn,mThe interference intensity of themth D2D pair that reuse the nth cellular user


## 2. Related Works

Recent studies concerning resource allocation mainly focused on the following aspects: mode selection [16], resource multiplexing, and power allocation [17] for D2D communication. The D2D communication includes the following scenarios: one-to-one, many-to-one, and many-to-many D2D communication.
(1)
One-to-one D2D communicationResource allocation in one-to-one D2D communication was studied in [18, 19]. In [18], a network-assisted distributed processing architecture was proposed to solve the throughput optimization problem, which included receiving mode selection, verification for relay selection, and transmission power adjustment. It could reduce the burden of centralized processing. A power control and channel allocation scheme for the energy efficiency maximization of D2D pairs through reusing uplink-downlink resources was presented in [19].
(2)
Many-to-one D2D communicationFor the scenario of multiple channel resources can be multiplexed by one D2D pair, the coalition game with priority sequences was presented to maximize the D2D throughput while guaranteeing the minimum rate of each user in [20]. In [21], a sealed bid single price auction game was introduced to attain the maximum throughput by balancing the interference between D2D users and CUs. In [22], by jointly considering the mode selection and power control strategy, a coalition formation game was proposed to maximize the energy efficiency of all users in the cellular network. In [23], a two-tier resource allocation scheme was discussed to maximize the spectral efficiency with guaranteeing a minimum throughput and its latency requirement. A spectrum resource allocation algorithm based on game theory was proposed to enhance the system sum rate in [24]. However, in [24], the power control strategy was not discussed to improve the system performance.The resource allocation method which multiple D2D pairs can multiplex a channel resource was investigated in [25–29]. In [25], based on matching theory and coalition game theory, a constrained deferred acceptance algorithm and a coalition formation algorithm were proposed to maximize the system performance with guaranteeing the QoS of all users. In [26], the cooperative D2D communication in an uplink cellular network was investigated, where D2D users acted as relays for cellular users to maximize the total average achievable rate under the outage probability constraint. Channel resource allocation methods based on interference analysis in a multiplexing scenario were studied to improve the system performance in [27, 28]. A distributed resource allocation algorithm based on the interference threshold was introduced to maximize the transmission rate of the D2D pairs in [29]. Only the matching problem between the D2D pairs and the CUs was taken into account in the research works mentioned above, and the performance of the CU was seldom considered during the optimizing process.
(3)
Many-to-many D2D communicationChannel multiplexing in a many-to-many D2D communication was studied in [14, 15, 30, 31]. A cooperative game resource allocation algorithm based on the overlapping coalition was proposed to improve the utility of the system, in which the coalition initialization was formed by choosing the most suitable CU to reuse its resources block according to the cross-tier interference strength in [14]. A many-to-many resource allocation algorithm based on externalities was proposed to reach a stable state and improve the performance of the system in [15]. A resource allocation method based on the graph coloring theory was proposed to optimize the spectral efficiency of the system in [30]. An iterative user-subchannel swap algorithm was proposed to maximize the sum rate of LTE and D2D users in [31].The literature mentioned above showed that the power and the spectrum allocation were considered to optimize the system performance from multiple aspects. The complexity for channel resource allocation of both one-to-one and many-to-one is much lower than that of many-to-many in D2D communication. In this paper, under the condition of guaranteeing the user’s QoS, an overlapping coalition formation game is proposed to solve the problem of resource allocation in many-to-many D2D communication.


## 3. System Model and Problem Formulation

This section provides a detailed description of the system model in many-to-many D2D communication and the optimization problem to maximize the transmission sum rate of D2D pairs is formulated.In a many-to-many D2D communication scenario, one channel resource can be shared by one CU and multiple D2D pairs, and a D2D pair can reuse multiple channel resources. As shown in Figure1, CUs and D2D pairs coexist in the cell network, and the network contains N CU and M D2D pair. The set of channel resource blocks contains in the cell is represented as C=1,⋯,n,⋯,N. The D2D pair set is D=1,⋯,m,⋯,M. The D2D pairs share the uplink of the CUs. For example, the 1st D2D pair (DU1), the 2nd D2D pair (DU2), and the 6th D2D pairs (DU6) in the cell network reuse the spectrum of the 1st CU (CU1). Meanwhile, DU2 can also share the spectrum of CU2.Figure 1
Many-to-many uplink resource reusing system model.It is assumed that the base station has the perception function of all complete channel state information (CSI). How the base station obtains the CSI of users is not involved in this study. Themth D2D pair receives the interferences from the corresponding CU and the D2D pairs which share the same channel resource. The transmission rate of the mth D2D pair sharing the nth resource block can be expressed as
(1)rm,nD=log21+ξm,nD,ξm,nD=pmDgDm,mn0+pnCgCn,m+∑m′∈Dn\mχm′,npm′DgDm′,m.where ξm,nD is the signal to interference noise ratio (SINR) of the mth D2D pair sharing the nth resource block. pnC and pmD are the transmit power of the nth CU and the mth D2D pair, respectively. And n0 is the Gaussian white noise. The symbol of m′ represents the m′th D2D pair which shares the same frequency with the mth D2D pair. Dn is a set of all D2D pairs sharing the same channel resource. gCn,m, gDm,m, and gDm′,m are the path gain from the nth CU, the transmitter of the mth D2D pair and the m′th D2D pair to the mth D2D pair receiver, respectively. The parameter χm,n is the indicator of reusing the nth resource block. If the nth resource block is reused by the mth D2D pair, χm,n=1. Otherwise, χm,n=0.The transmission sum rate of all D2D pairs can be given as(2)RD=∑n∈C∑m∈Drm,nD=∑n∈C∑m∈Dlog21+ξm,nD.The SINR of thenth CU is expressed as follows:
(3)ξnC=pnCgCn,Bn0+∑m∈Dnχm,npmDgDm,B,where gCn,B and gDm,B are the path gains of the nth CU and the mth D2D pair to the base station, respectively.The transmission sum rate of all CUs in the cell can be described as(4)RC=∑n∈CrnC=∑n∈Clog21+ξnC=∑n∈Clog21+pnCgCn,Bn0+∑m∈Dnχm,npmDgDm,B.The objective function is to maximize the transmission rate of all D2D pairs while considering the minimum rate of each user. And it can be described as follows:(5)maxχm,n,pmDRD=∑n∈C∑m∈Drm,nD=∑n∈C∑m∈Dlog21+ξm,nD,(6)s.t.rm,nD≥RthD∀m∈D,∀n∈C,(7)rnC≥RthC∀n∈C,(8)pmD≤pDmax∀m∈D,(9)pnC≤pCmax∀n∈C,(10)χm,n∈0,1∀m∈D,∀n∈C.where RthD and RthC are the D2D pairs and CUs’ transmission rate threshold values, respectively. The pDmax and pCmax are maximum transmit power of the D2D pairs and CUs, respectively. Equation (6) (Equation (7)) represents the transmission rate constraint of the mth D2D pair (the nth CU). Equation (8) (Equation (9)) indicates the transmit power of the mth D2D pair (the nth CU) should be less than or equal to the corresponding maximum value. Equation (10) means whether the mth D2D pair sharing the nth channel resource. Since Equation (5) is a nonlinear equation which involves a binary variables of χm,n, therefore, the objective function is a mixed-integer nonlinear programming (MINLP) problem.


## 4. Resource Allocation Algorithm for Optimizing Transmission Rate

This section introduces a resource allocation algorithm based on the overlapping coalition game and power control strategy of all D2D pairs in a many-to-many D2D communication scenario.


### 4.1. Preference Sequence Coalition Initialization

The definition of the overlapping coalition is given as follows.Definition 1.
In the coalition gameG=L,v,CS, L=1,⋯,m,⋯.,M denotes a set of all D2D pairs that share the channel resources. The parameter v represents the utility function. The coalition structure CS=S1,S2,⋯,Sn,⋯,SN denotes a set of Sn, where Sn represents a set of the corresponding D2D pairs and the CU that share the nth resource block. As the D2D pairs can join multiple coalitions, an overlapping coalition structure is formed. It means that Si∩Sj≠∅, i,j∈N,i≠j, where Si and Sj represent the ith and jth coalition in the same coalition structure, respectively.The utility function ofv can be used to evaluate whether the coalition has been improved. The utility function of the mth D2D pair sharing the nth channel resources is defined as
(11)vm,Sn=rm,nD,rm,nD≥RthD,0,otherwise.The utility function of the coalitionSn with transmission rate constraints is expressed as
(12)vSn,CS=∑m∈Dnrm,nD,rm,nD≥RthD,rnC≥RthC,0,otherwise.The utility function of coalition structureCS is the sum of the utility value of each coalition and it can be expressed as
(13)vCS=∑n∈CvSn,CS.In the process of coalition initialization, the performance of each CU should be firstly guaranteed when the channel resource blocks are shared. The interference intensity of themth D2D pair that shares the nth channel resource block is used as the preference value, and it can be expressed as
(14)ρn,m=pmDgDn,m,B,where gDn,m,B is the communication link gain between the mth D2D pair sharing the nth channel resource block and the base station. If the preference value of the mth D2D pair is lower, the interference to the CU sharing the same channel resource is smaller. Therefore, the D2D pair is more likely to reuse this resource block.The preference sequence of themth D2D pair is a set of preference values for the mth D2D pair that shares different channel resources. In order to optimize the sum transmission rate of all D2D pairs, the preference sequence is adopted in coalition initialization. The coalition initialization process based on the preference sequence includes four steps:
(1)
The first step: calculating the preference value of the1st D2D pair according to Equation (14), arranging the preference values in ascending order to form the preference sequence (denoted as T1)(2)
The second step: calculating the transmission rate of the1st D2D pair and the corresponding CU in the order of the T1, respectively. If the transmission rate is lower than the rate threshold, the calculation is stopped. Otherwise, the preference values that make the transmission rate satisfy the transmission rate threshold will form a new preference sequence (denoted as T1′)(3)
The third step: repeatedly obtaining themth D2D pair preference sequence Tm′ according to the first and second steps, until all Tm′m∈M have been obtained(4)
According toTm′m∈M, all D2D pairs which share the same resource block are determined and the corresponding D2D pairs form an initial coalition


### 4.2. Overlapping Coalition Game

Definition 2.
It is assumed that the coalition structureCSp is described as CSp=S1⋯,Sa,⋯,Sb,⋯,SN and the mth D2D pair belongs to the coalition of Sa. If the mth D2D pair switchs from Sa to Sb, the coalition structure CSq=S1,⋯,Saq,⋯,Sbq,⋯,SN is formed, where Saq=Sa\m and Sbq=Sb∪m.The coalition game guideline is given as(15)CSp⊳CSq⇔vm,Sbq>vm,Sa,vSbq,CSq≥vSb,CSp,vCSq>vCSp,where the first inequation of (15) means that the utility value of the mth D2D pair in the coalition of Sbq is larger than that in Sa. And the second inequation of (15) means that the utility value of Sbq is no less than that of Sb. The third inequation of (15) represents that the utility value of coalition structure CSq will be greater than that of CSp. If the D2D pair who meets the above three conditions, it can switch from one coalition to another. According to (14), the preference values for the mth D2D pair sharing all channel resource is obtained. The mth D2D pair chooses the coalition with a lower preference value to join.If the coalition consists of only one CU, which means that there is no any D2D pair in the coalition. Therefore, the corresponding coalition switch guideline is given as follows:(16)CSp⊳CSq⇔vm,Sbq>vm,Sa,vCSq>vCSp.As the channel resource has not been used by any D2D pair, the D2D pair was randomly selected to join a new coalition if two conditions are satisfied: (i) the individual utility of the D2D pair is increased and (ii) the total utility of the new coalitional structure is increased. Eventually, the total transmission rate of D2D pairs and the utility value of coalition structure will be improved after multiple switching.The channel resource allocation is determined through randomly selection [13] or cooperative game [14] to improve the D2D transmission sum rate. This work shows that the D2D transmission sum rate can be further enhanced by introducing the candidate sequence in the overlapping coalition game. The candidate sequence S0 contains all D2D pairs in the network. This sequence always remains unchanged, and it is represented as S0=1,⋯m,⋯,Mm∈D.Definition 3.
Considering two coalition structuresCSp=S1,⋯,Sa,Sb⋯,SN and CSq=S1,⋯,Saq,Sbq⋯,SN. For the coalition Sa, the m′th D2D pair in the candidate sequence S0 wants to join or replace the mth D2D pair in Sa, so Saq=Sa∪m′,m′∈S0,m′∉Sa, or Saq=Sa\m∪m′. ∃a≠b,Saq∩Sbq≠ϕ.The guideline of D2D pairs in the candidate sequence to join the coalition or replace the D2D pair in the coalition is expressed as(17)CSp⊳CSq⇔vSaq,CSq≥vSa,CSp.Them′th D2D pair in the candidate sequence S0 can join or replace the mth D2D pair in Sa if the utility of Saq is no less than that of Sa.In order to reduce the times of game, the proposed algorithm sets a historical information tableHm,Sl. If the mth D2D pair already exists in the coalition Sl or has been refused to join the coalition Sl, it is set that Hm,Sl=1; otherwise, Hm,Sl=0.
(18)Hm,Sl=1,m∈SlormhasbeenrefusedbySl,0,otherwise.Algorithm1 summarizes the resource allocation algorithm.


### 4.3. Power Allocation

In the many-to-many scenario, it is not easy to perform power control while allocating channel resources. Therefore, the power of each D2D pair is allocated after the coalition structure is formed.Each D2D pair sends its channel status information to the base station, and the base station sets the transmit power of the corresponding D2D pair. It is assumed that the transmit power level isΨ=1,2,⋯,um⋯,Q, where Q is the maximum power level. The maximum transmit power pDmax of each D2D pair on each subchannel is a fixed value. The power interval is pu=pDmax/Q. According to the power level, the transmit power of the mth D2D pair can be expressed as
(19)pmD=umpu.In the process of power allocation, the transmission rate of each CU and each D2D pair must meet the minimum rate requirement. The optimization goal of the power allocation is to improve the coalition utility. The transmit power of all D2D pairs is allocated according to the preference sequence. The power allocation strategy is given as follows:(1)
The first step: for the coalitionSnn∈N, allocating the highest levels of power to the corresponding D2D pair, which the interference to the CU in the coalition of Sn is the smallest(2)
The second step: if the conditions shown in Equations (6), (7), (8), and (9) are met, the corresponding transmit power of the D2D pair will be allocated(3)
The third step: if the conditions shown in Equations (6), (7), (8), and (9) are not met, reducing one of the power levels, calculating the transmission rate, and judging whether the conditions mentioned above are satisfied. If satisfied, the corresponding transmit power will be allocated. Otherwise, further reducing one of the power levels until the conditions mentioned above are satisfied(4)
The fourth step: selecting the next D2D pair (the transmit power has not been allocated) inSn which the interference to the CU in the coalition of Sn is the smallest(5)
The fifth step: selecting the next coalition to allocate the transmit power until the transmit power of all D2D pairs in the cell are allocatedAlgorithm 1: Resource allocation algorithm based on overlapping coalition game
Step 1: Initialize1:Sn=n and CS=S1,⋯,Sn,⋯,SN;Step 2: Overlapping coalition initialization1: According toρn,m=pmDgDn,m,B and form Tm′ (m from 1 to M);2: According toTm′m∈M, all D2D pairs sharing the same resource block are determined while satisfying Equations (6), (7), (8), and (9).3: Corresponding D2D pairs form an initial coalition.Step 3: Overlapping coalition game1:CS=S1,⋯,Sa,⋯,Sn,⋯,SN;2: ForSa, a from 1 to N3: InSa, for the mth D2D pair m∈Sa;4:ifρa,m>ρn,m and Hm,Sn=0then5:if Meet (15) or (16) and Hm,Sa=1then6:   JoinSn, and set Hm,Sn=1,Hm,Sa=0;7:else8:   SetHm,Sn=1;9:end if10:else11:  Themth D2D pair stays in Sa.12:end if13: End for14:if the number of D2D pairs in Sa does not changed then15:if in S0, the m′th D2D pair meets Equation (17) and Hm′,Sa=0then16:   them′th D2D pair join the coalition Sa or replace the m-th D2D pair, Hm′,Sa=1;17:else18:   SetHm′,Sa=1;19:end if20:end if21: End for22: Repeat Step 3 until the coalition structure remains unchanged in this round of game.Step 4: Output1: End the iteration and output the coalition structure.


### 4.4. Complexity and Convergence

It can be seen from Algorithm1 that the computational complexity is related to the number of channel resources N and the D2D pairs M. During the initial process of coalition game, the D2D pair selects the most suitable coalition to join according to the preference sequence of the D2D pair, which can reduce the switch times for the D2D pair to join the corresponding coalitions. Moreover, the history information table Hm,Sl is introduced to prevent the D2D pairs from rejoining the same coalition. In general, the computational complexity of this algorithm is less than ON×M. The worst-case occurs when all D2D pairs find the channel resources to reuse at the last switching; therefore, the computational complexity of the proposed algorithm is ON×M. The computational complexity of the proposed algorithm is similar to that presented in [14], in which the computational complexity is ON×M. The computational complexity of the proposed algorithm is a little better than that of the algorithm proposed in [15], which the computational complexity is OM/2+N×M.The criterion of the coalition game is that each D2D pair carries out handover if its utility and the system utility are increased. If the D2D pair meets the switching conditions of Equations (15), (16), or (17), it means the utility of the D2D pair is not reduced. And the corresponding D2D pair can join the other coalitions. Otherwise, the D2D pair stays in the original coalition. If the number of D2D pairs and CUs are given, it can be seen that the total number of coalitions formed in Algorithm 1 is finite. And the system utility will reach the maximum value through the limited times of switching. Eventually, Algorithm 1 is converged and the stable coalition structure is formed.The relationships between the system utility and the iterations withN=5 and M =100 is shown in Figure 2. It can be seen that the system utility will reach the maximum value through the limited iterations, in which a stable coalition structure will be formed.Figure 2
The relationships between the system utility and the iterations.


## 4.1. Preference Sequence Coalition Initialization

The definition of the overlapping coalition is given as follows.Definition 1.
In the coalition gameG=L,v,CS, L=1,⋯,m,⋯.,M denotes a set of all D2D pairs that share the channel resources. The parameter v represents the utility function. The coalition structure CS=S1,S2,⋯,Sn,⋯,SN denotes a set of Sn, where Sn represents a set of the corresponding D2D pairs and the CU that share the nth resource block. As the D2D pairs can join multiple coalitions, an overlapping coalition structure is formed. It means that Si∩Sj≠∅, i,j∈N,i≠j, where Si and Sj represent the ith and jth coalition in the same coalition structure, respectively.The utility function ofv can be used to evaluate whether the coalition has been improved. The utility function of the mth D2D pair sharing the nth channel resources is defined as
(11)vm,Sn=rm,nD,rm,nD≥RthD,0,otherwise.The utility function of the coalitionSn with transmission rate constraints is expressed as
(12)vSn,CS=∑m∈Dnrm,nD,rm,nD≥RthD,rnC≥RthC,0,otherwise.The utility function of coalition structureCS is the sum of the utility value of each coalition and it can be expressed as
(13)vCS=∑n∈CvSn,CS.In the process of coalition initialization, the performance of each CU should be firstly guaranteed when the channel resource blocks are shared. The interference intensity of themth D2D pair that shares the nth channel resource block is used as the preference value, and it can be expressed as
(14)ρn,m=pmDgDn,m,B,where gDn,m,B is the communication link gain between the mth D2D pair sharing the nth channel resource block and the base station. If the preference value of the mth D2D pair is lower, the interference to the CU sharing the same channel resource is smaller. Therefore, the D2D pair is more likely to reuse this resource block.The preference sequence of themth D2D pair is a set of preference values for the mth D2D pair that shares different channel resources. In order to optimize the sum transmission rate of all D2D pairs, the preference sequence is adopted in coalition initialization. The coalition initialization process based on the preference sequence includes four steps:
(1)
The first step: calculating the preference value of the1st D2D pair according to Equation (14), arranging the preference values in ascending order to form the preference sequence (denoted as T1)(2)
The second step: calculating the transmission rate of the1st D2D pair and the corresponding CU in the order of the T1, respectively. If the transmission rate is lower than the rate threshold, the calculation is stopped. Otherwise, the preference values that make the transmission rate satisfy the transmission rate threshold will form a new preference sequence (denoted as T1′)(3)
The third step: repeatedly obtaining themth D2D pair preference sequence Tm′ according to the first and second steps, until all Tm′m∈M have been obtained(4)
According toTm′m∈M, all D2D pairs which share the same resource block are determined and the corresponding D2D pairs form an initial coalition


## 4.2. Overlapping Coalition Game

Definition 2.
It is assumed that the coalition structureCSp is described as CSp=S1⋯,Sa,⋯,Sb,⋯,SN and the mth D2D pair belongs to the coalition of Sa. If the mth D2D pair switchs from Sa to Sb, the coalition structure CSq=S1,⋯,Saq,⋯,Sbq,⋯,SN is formed, where Saq=Sa\m and Sbq=Sb∪m.The coalition game guideline is given as(15)CSp⊳CSq⇔vm,Sbq>vm,Sa,vSbq,CSq≥vSb,CSp,vCSq>vCSp,where the first inequation of (15) means that the utility value of the mth D2D pair in the coalition of Sbq is larger than that in Sa. And the second inequation of (15) means that the utility value of Sbq is no less than that of Sb. The third inequation of (15) represents that the utility value of coalition structure CSq will be greater than that of CSp. If the D2D pair who meets the above three conditions, it can switch from one coalition to another. According to (14), the preference values for the mth D2D pair sharing all channel resource is obtained. The mth D2D pair chooses the coalition with a lower preference value to join.If the coalition consists of only one CU, which means that there is no any D2D pair in the coalition. Therefore, the corresponding coalition switch guideline is given as follows:(16)CSp⊳CSq⇔vm,Sbq>vm,Sa,vCSq>vCSp.As the channel resource has not been used by any D2D pair, the D2D pair was randomly selected to join a new coalition if two conditions are satisfied: (i) the individual utility of the D2D pair is increased and (ii) the total utility of the new coalitional structure is increased. Eventually, the total transmission rate of D2D pairs and the utility value of coalition structure will be improved after multiple switching.The channel resource allocation is determined through randomly selection [13] or cooperative game [14] to improve the D2D transmission sum rate. This work shows that the D2D transmission sum rate can be further enhanced by introducing the candidate sequence in the overlapping coalition game. The candidate sequence S0 contains all D2D pairs in the network. This sequence always remains unchanged, and it is represented as S0=1,⋯m,⋯,Mm∈D.Definition 3.
Considering two coalition structuresCSp=S1,⋯,Sa,Sb⋯,SN and CSq=S1,⋯,Saq,Sbq⋯,SN. For the coalition Sa, the m′th D2D pair in the candidate sequence S0 wants to join or replace the mth D2D pair in Sa, so Saq=Sa∪m′,m′∈S0,m′∉Sa, or Saq=Sa\m∪m′. ∃a≠b,Saq∩Sbq≠ϕ.The guideline of D2D pairs in the candidate sequence to join the coalition or replace the D2D pair in the coalition is expressed as(17)CSp⊳CSq⇔vSaq,CSq≥vSa,CSp.Them′th D2D pair in the candidate sequence S0 can join or replace the mth D2D pair in Sa if the utility of Saq is no less than that of Sa.In order to reduce the times of game, the proposed algorithm sets a historical information tableHm,Sl. If the mth D2D pair already exists in the coalition Sl or has been refused to join the coalition Sl, it is set that Hm,Sl=1; otherwise, Hm,Sl=0.
(18)Hm,Sl=1,m∈SlormhasbeenrefusedbySl,0,otherwise.Algorithm1 summarizes the resource allocation algorithm.


## 4.3. Power Allocation

In the many-to-many scenario, it is not easy to perform power control while allocating channel resources. Therefore, the power of each D2D pair is allocated after the coalition structure is formed.Each D2D pair sends its channel status information to the base station, and the base station sets the transmit power of the corresponding D2D pair. It is assumed that the transmit power level isΨ=1,2,⋯,um⋯,Q, where Q is the maximum power level. The maximum transmit power pDmax of each D2D pair on each subchannel is a fixed value. The power interval is pu=pDmax/Q. According to the power level, the transmit power of the mth D2D pair can be expressed as
(19)pmD=umpu.In the process of power allocation, the transmission rate of each CU and each D2D pair must meet the minimum rate requirement. The optimization goal of the power allocation is to improve the coalition utility. The transmit power of all D2D pairs is allocated according to the preference sequence. The power allocation strategy is given as follows:(1)
The first step: for the coalitionSnn∈N, allocating the highest levels of power to the corresponding D2D pair, which the interference to the CU in the coalition of Sn is the smallest(2)
The second step: if the conditions shown in Equations (6), (7), (8), and (9) are met, the corresponding transmit power of the D2D pair will be allocated(3)
The third step: if the conditions shown in Equations (6), (7), (8), and (9) are not met, reducing one of the power levels, calculating the transmission rate, and judging whether the conditions mentioned above are satisfied. If satisfied, the corresponding transmit power will be allocated. Otherwise, further reducing one of the power levels until the conditions mentioned above are satisfied(4)
The fourth step: selecting the next D2D pair (the transmit power has not been allocated) inSn which the interference to the CU in the coalition of Sn is the smallest(5)
The fifth step: selecting the next coalition to allocate the transmit power until the transmit power of all D2D pairs in the cell are allocatedAlgorithm 1: Resource allocation algorithm based on overlapping coalition game
Step 1: Initialize1:Sn=n and CS=S1,⋯,Sn,⋯,SN;Step 2: Overlapping coalition initialization1: According toρn,m=pmDgDn,m,B and form Tm′ (m from 1 to M);2: According toTm′m∈M, all D2D pairs sharing the same resource block are determined while satisfying Equations (6), (7), (8), and (9).3: Corresponding D2D pairs form an initial coalition.Step 3: Overlapping coalition game1:CS=S1,⋯,Sa,⋯,Sn,⋯,SN;2: ForSa, a from 1 to N3: InSa, for the mth D2D pair m∈Sa;4:ifρa,m>ρn,m and Hm,Sn=0then5:if Meet (15) or (16) and Hm,Sa=1then6:   JoinSn, and set Hm,Sn=1,Hm,Sa=0;7:else8:   SetHm,Sn=1;9:end if10:else11:  Themth D2D pair stays in Sa.12:end if13: End for14:if the number of D2D pairs in Sa does not changed then15:if in S0, the m′th D2D pair meets Equation (17) and Hm′,Sa=0then16:   them′th D2D pair join the coalition Sa or replace the m-th D2D pair, Hm′,Sa=1;17:else18:   SetHm′,Sa=1;19:end if20:end if21: End for22: Repeat Step 3 until the coalition structure remains unchanged in this round of game.Step 4: Output1: End the iteration and output the coalition structure.


## 4.4. Complexity and Convergence

It can be seen from Algorithm1 that the computational complexity is related to the number of channel resources N and the D2D pairs M. During the initial process of coalition game, the D2D pair selects the most suitable coalition to join according to the preference sequence of the D2D pair, which can reduce the switch times for the D2D pair to join the corresponding coalitions. Moreover, the history information table Hm,Sl is introduced to prevent the D2D pairs from rejoining the same coalition. In general, the computational complexity of this algorithm is less than ON×M. The worst-case occurs when all D2D pairs find the channel resources to reuse at the last switching; therefore, the computational complexity of the proposed algorithm is ON×M. The computational complexity of the proposed algorithm is similar to that presented in [14], in which the computational complexity is ON×M. The computational complexity of the proposed algorithm is a little better than that of the algorithm proposed in [15], which the computational complexity is OM/2+N×M.The criterion of the coalition game is that each D2D pair carries out handover if its utility and the system utility are increased. If the D2D pair meets the switching conditions of Equations (15), (16), or (17), it means the utility of the D2D pair is not reduced. And the corresponding D2D pair can join the other coalitions. Otherwise, the D2D pair stays in the original coalition. If the number of D2D pairs and CUs are given, it can be seen that the total number of coalitions formed in Algorithm 1 is finite. And the system utility will reach the maximum value through the limited times of switching. Eventually, Algorithm 1 is converged and the stable coalition structure is formed.The relationships between the system utility and the iterations withN=5 and M =100 is shown in Figure 2. It can be seen that the system utility will reach the maximum value through the limited iterations, in which a stable coalition structure will be formed.Figure 2
The relationships between the system utility and the iterations.


## 5. Simulation and Analysis

### 5.1. Simulation Design

This section verifies the performance of the proposed algorithm. It is assumed that the base station is located in the center of the cell, the CUs and D2D pairs are randomly scattered in the cell, and the cell shape is a regular hexagon. And assuming that the D2D pairs and CUs are stationary or at a low speed. Each coalition contains one CU. Each D2D pair can join multiple coalitions. The Rayleigh channel model has been adopted in the simulation. The path gain of the link from thenth CU to the receiver of the mth D2D pair can be expressed as
(20)gn,m=kβn,mωn,mγn,m−α,where k represents the path loss constant. βn,m with exponential distribution is the multipath fading parameter from the nth CU to the receiver of the mth D2D pair. And ωn,m with log-normal distribution represents the shadow gain from the nth CU to the receiver of the mth D2D pair. γn,m indicates the distance from the nth CU to the receiver of the mth D2D pair, and α indicates the path loss factor. Other simulation parameters are listed in Table 2, which is the same to that shown in [14].Table 2
Simulation parameters.
ParametersValueCell radius500 mNumber of CUsN4~8Number of D2D pairsM1~5CUs’ maximum transmission powerpCmax23 dBmD2D maximum transmission powerpDmax13 dBmCUs’ rate thresholdRthD2 ~4 bps/HzD2D pairs rate thresholdRD1 bps/HzD2D maximum transmission distanced50 mNoise power spectral density-174 dBm/HzResource block bandwidth15 kHzPath loss factorα3Multipath fadingβn,m (exponential distribution mean)1Shadow fadingλn,m (logarithmic distribution standard deviation)8 dBThe maximum power levelQ13The system transmission sum rate is the sum of the transmission rate of all D2D pairs and CUs. According to Equations (2) and (4), it can be expressed as
(21)Rtotal=∑n∈C∑m∈Drm,nD+∑n∈CrnC.In order to verify the performance of the proposed algorithm, this paper takes the transmission sum rate of all D2D pairs and the system transmission sum rate as indicators and carries out simulation verification on the numbers of the users and the transmission rate thresholds of the CUs.The proposed algorithm is compared with the following four algorithms:(1)
Exhaustive algorithm: the D2D pairs select coalitions to maximize the D2D system transmission rate by the exhaustive search, which means that search all possible coalitions to find the optimal solution. The algorithm is labeled as “Exhaustive”(2)
Cooperative game (CG) algorithm [14]: an overlapping coalitions game algorithm with cooperative optimization is proposed to maximize the system utility in terms of the sum rate of all D2D links. The algorithm is labeled as “CG”(3)
Matching game with externalities (MGWE) algorithm [15]: with signal-to-interference-plus-noise ratio constraints for both D2D devices and the cellular users, a resource allocation algorithm based on the many-to-many two-sided matching game with externalities to maximize the system sum rate. The matching game with externalities algorithm is labeled as “MGWE”(4)
Auction algorithm [32]: it is an iterative combinatorial auction algorithm with flexible power control, where the CUs are considered as bidders, D2D pairs as goods, and the cellular network plays a role as the auctioneer controlling the auction process. The algorithm is labeled as “Auction”1000 times of simulation are carried out and each data point in the simulation results is the average value of 1000 times simulation. WithN=4 and M=5 to obtain the D2D transmission sum rate, the running time of “Proposed,” “CG,” and “MGWN” algorithms is 10.465 ms, 11.857 ms, and 13.297 ms, respectively.


### 5.2. Results and Discussion

Figures3(a) and 3(b) show the effect of CU link number on the transmission sum rate of all D2D pairs and the system transmission sum rate with M=4, respectively. It can be seen that the transmission sum rate of all D2D pairs (the system) increases with the number of CUs becoming larger, which means the more coalitions that the D2D pair can choose to join. The D2D (the system) transmission sum rate in the many-to-many scenario by using the proposed algorithm is close to that by using the “Exhaustive” method, and the D2D (the system) transmission sum rate obtained by using the proposed algorithm is larger than that by using “CG,” “MGWE,” or “Auction” algorithms.Figure 3
Effects of the CUs’ number on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures4(a) and 4(b) show the relationships of D2D link number to the D2D (the system) transmission sum rate with N=4. It can be observed that the D2D and system transmission sum rate by using the proposed method increases with the number of the D2D pairs becomes larger. The performance of the proposed algorithm is close to that of the exhaustive method and is better than that of other three algorithms.Figure 4
Effects of the D2D pairs’ number on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures5(a) and 5(b) show the relationships of the D2D (the system) transmission sum rate varying with CU rate threshold, respectively. It can be seen that the D2D (the system) transmission sum rate becomes smaller as the rate threshold of CU is increased. It is because that the number of D2D pairs accessing the cellular channel becomes smaller with the increment of the CU rate threshold, which leads to the decrement of the D2D transmission sum rate. Compared with the “MGWE” algorithm, the proposed algorithm has a higher transmission sum rate and is close to the “Exhaustive” method. The D2D and system transmission sum rate by using the “CG” algorithm does not decrease rapidly as the rate threshold of the CUs becomes larger. Compared with the “CG” algorithm, the D2D (the system) transmission sum rate obtained by using the proposed algorithm varies more rapidly as the rate threshold of the CUs is increased.Figure 5
Effects of CUs’ rate threshold on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures6(a) and 6(b) show the impact of power allocation and candidate sequence on D2D performance. The “Proposed without PowCtrl” indicates the proposed algorithm includes the optimization procedure of candidate sequence and each D2D pair has a fixed transmit power. The “Proposed without CandSeq” means that the proposed coalition game algorithm with power allocation does not include the optimization procedure of the candidate sequence.Figure 6
Effects of the users’ number on transmission rate.
(a)
Number of CU links(b)
Number of D2D linksIt can be seen that the D2D transmission sum rate increases as the number of the D2D pairs or the CUs becomes larger. The D2D transmission sum rate obtained by using the proposed algorithm is better than that by using the overlapping coalition game algorithm with random initialization. It can be seen that the performance of the “proposed” or the “Proposed without PowCtrl” algorithm is better than that of the “Proposed without CandSeq” algorithm. It means that the optimization procedure of the candidate sequence in the algorithm can further improve the utility of the coalition structure and increase the D2D transmission sum rate. Moreover, the performance of the “proposed” algorithm is better than that of the “Proposed without PowCtrl” algorithm, which indicates that the appropriate power allocation can enhance the D2D transmission sum rate.


## 5.1. Simulation Design

This section verifies the performance of the proposed algorithm. It is assumed that the base station is located in the center of the cell, the CUs and D2D pairs are randomly scattered in the cell, and the cell shape is a regular hexagon. And assuming that the D2D pairs and CUs are stationary or at a low speed. Each coalition contains one CU. Each D2D pair can join multiple coalitions. The Rayleigh channel model has been adopted in the simulation. The path gain of the link from thenth CU to the receiver of the mth D2D pair can be expressed as
(20)gn,m=kβn,mωn,mγn,m−α,where k represents the path loss constant. βn,m with exponential distribution is the multipath fading parameter from the nth CU to the receiver of the mth D2D pair. And ωn,m with log-normal distribution represents the shadow gain from the nth CU to the receiver of the mth D2D pair. γn,m indicates the distance from the nth CU to the receiver of the mth D2D pair, and α indicates the path loss factor. Other simulation parameters are listed in Table 2, which is the same to that shown in [14].Table 2
Simulation parameters.
ParametersValueCell radius500 mNumber of CUsN4~8Number of D2D pairsM1~5CUs’ maximum transmission powerpCmax23 dBmD2D maximum transmission powerpDmax13 dBmCUs’ rate thresholdRthD2 ~4 bps/HzD2D pairs rate thresholdRD1 bps/HzD2D maximum transmission distanced50 mNoise power spectral density-174 dBm/HzResource block bandwidth15 kHzPath loss factorα3Multipath fadingβn,m (exponential distribution mean)1Shadow fadingλn,m (logarithmic distribution standard deviation)8 dBThe maximum power levelQ13The system transmission sum rate is the sum of the transmission rate of all D2D pairs and CUs. According to Equations (2) and (4), it can be expressed as
(21)Rtotal=∑n∈C∑m∈Drm,nD+∑n∈CrnC.In order to verify the performance of the proposed algorithm, this paper takes the transmission sum rate of all D2D pairs and the system transmission sum rate as indicators and carries out simulation verification on the numbers of the users and the transmission rate thresholds of the CUs.The proposed algorithm is compared with the following four algorithms:(1)
Exhaustive algorithm: the D2D pairs select coalitions to maximize the D2D system transmission rate by the exhaustive search, which means that search all possible coalitions to find the optimal solution. The algorithm is labeled as “Exhaustive”(2)
Cooperative game (CG) algorithm [14]: an overlapping coalitions game algorithm with cooperative optimization is proposed to maximize the system utility in terms of the sum rate of all D2D links. The algorithm is labeled as “CG”(3)
Matching game with externalities (MGWE) algorithm [15]: with signal-to-interference-plus-noise ratio constraints for both D2D devices and the cellular users, a resource allocation algorithm based on the many-to-many two-sided matching game with externalities to maximize the system sum rate. The matching game with externalities algorithm is labeled as “MGWE”(4)
Auction algorithm [32]: it is an iterative combinatorial auction algorithm with flexible power control, where the CUs are considered as bidders, D2D pairs as goods, and the cellular network plays a role as the auctioneer controlling the auction process. The algorithm is labeled as “Auction”1000 times of simulation are carried out and each data point in the simulation results is the average value of 1000 times simulation. WithN=4 and M=5 to obtain the D2D transmission sum rate, the running time of “Proposed,” “CG,” and “MGWN” algorithms is 10.465 ms, 11.857 ms, and 13.297 ms, respectively.


## 5.2. Results and Discussion

Figures3(a) and 3(b) show the effect of CU link number on the transmission sum rate of all D2D pairs and the system transmission sum rate with M=4, respectively. It can be seen that the transmission sum rate of all D2D pairs (the system) increases with the number of CUs becoming larger, which means the more coalitions that the D2D pair can choose to join. The D2D (the system) transmission sum rate in the many-to-many scenario by using the proposed algorithm is close to that by using the “Exhaustive” method, and the D2D (the system) transmission sum rate obtained by using the proposed algorithm is larger than that by using “CG,” “MGWE,” or “Auction” algorithms.Figure 3
Effects of the CUs’ number on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures4(a) and 4(b) show the relationships of D2D link number to the D2D (the system) transmission sum rate with N=4. It can be observed that the D2D and system transmission sum rate by using the proposed method increases with the number of the D2D pairs becomes larger. The performance of the proposed algorithm is close to that of the exhaustive method and is better than that of other three algorithms.Figure 4
Effects of the D2D pairs’ number on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures5(a) and 5(b) show the relationships of the D2D (the system) transmission sum rate varying with CU rate threshold, respectively. It can be seen that the D2D (the system) transmission sum rate becomes smaller as the rate threshold of CU is increased. It is because that the number of D2D pairs accessing the cellular channel becomes smaller with the increment of the CU rate threshold, which leads to the decrement of the D2D transmission sum rate. Compared with the “MGWE” algorithm, the proposed algorithm has a higher transmission sum rate and is close to the “Exhaustive” method. The D2D and system transmission sum rate by using the “CG” algorithm does not decrease rapidly as the rate threshold of the CUs becomes larger. Compared with the “CG” algorithm, the D2D (the system) transmission sum rate obtained by using the proposed algorithm varies more rapidly as the rate threshold of the CUs is increased.Figure 5
Effects of CUs’ rate threshold on transmission rate.
(a)
D2D transmission rate(b)
System transmission rateFigures6(a) and 6(b) show the impact of power allocation and candidate sequence on D2D performance. The “Proposed without PowCtrl” indicates the proposed algorithm includes the optimization procedure of candidate sequence and each D2D pair has a fixed transmit power. The “Proposed without CandSeq” means that the proposed coalition game algorithm with power allocation does not include the optimization procedure of the candidate sequence.Figure 6
Effects of the users’ number on transmission rate.
(a)
Number of CU links(b)
Number of D2D linksIt can be seen that the D2D transmission sum rate increases as the number of the D2D pairs or the CUs becomes larger. The D2D transmission sum rate obtained by using the proposed algorithm is better than that by using the overlapping coalition game algorithm with random initialization. It can be seen that the performance of the “proposed” or the “Proposed without PowCtrl” algorithm is better than that of the “Proposed without CandSeq” algorithm. It means that the optimization procedure of the candidate sequence in the algorithm can further improve the utility of the coalition structure and increase the D2D transmission sum rate. Moreover, the performance of the “proposed” algorithm is better than that of the “Proposed without PowCtrl” algorithm, which indicates that the appropriate power allocation can enhance the D2D transmission sum rate.


## 6. Conclusion

According to the analysis of the system model in many-to-many D2D communication, the resource allocation problem is formulated. An overlapping coalition game algorithm based on a candidate sequence is proposed to improve the D2D transmission sum rate. The preference sequence is adopted in the processing of coalition initialization. According to the preference sequence, a power allocation strategy is used to further improve the system utility. Simulation results show that the performance of the proposed algorithm including the optimization procedure of candidate sequence is better than that of the overlapping algorithm with random optimization. Compared to the “CG” and “MGWE” algorithms, when the number of cellular users is 8, and the number of D2D users is 4, the D2D transmission sum rate of the proposed algorithm is improved nearly 24% and 40%, respectively. Moreover, the system transmission rate has been improved nearly 25% and 35%, respectively.



---

*Source: 1738530-2022-02-24.xml*