# Interference-Aware and Spectral-Efficient Resource Allocation Using Complete Graphs for the D2D Communication

Authors: Tsang-Ling Sheu; Yan-Jing Wu; Yen-Chieh Chiu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

This paper proposes a heuristic resource block allocation using complete graphs (abbreviated to RACG) mechanism for device-to-device (D2D) communication. RACG not only can reduce the cochannel interference but also can improve the overall system capacity. For RACG, we define two pieces of user equipment in the D2D communication as one D2D pair and use the interference between each D2D pair to establish an interference graph model, which is then used to identify all complete graphs with different numbers of vertices. The innovation of RACG is right that it begins with resource block (RB) allocation for the D2D pairs in the complete graph with the largest number of vertices and considers three additional parameters to determine the allocation sequence for the D2D pairs. The three additional parameters are the frequency at which D2D pairs appear in complete graphs, the interference level of a D2D pair to other D2D pairs, and the number of RBs required. Furthermore, RACG prioritizes the reuse of allocated RB chunks during RB allocation. When a D2D pair and other D2D pairs with allocated RBs do not have mutual interference, the allocated RB chunk that has the closest number of RBs to the number of RBs required is selected and reused. We conduct performance analysis and compare the proposed RACG with a resource allocation of degree-based greedy (RADG) approach. The performance measures include the RB usage rate and occupied rate in a frame.


---

## Body

## 1. Introduction

The development of mobile communication technology brings about massive increases of user equipment (UE) such as smart phones, machine-to-machine modules, and tablets, which in turn cause sudden increases in bandwidth demand in mobile communication networks. UE do not even have sufficient bandwidth for transmission during peak hours or in cities with a high population density, resulting in intolerable packet delay. To provide sufficient bandwidth to an increasing number of UE and maintain low packet delay, the Third-Generation Partnership Project (3GPP) has proposed a new device-to-device (D2D) communication mode for new generation mobile communication networks [1, 2]. We define two pieces of UE in the D2D communication as one D2D pair. The D2D communication can reduce the transmission power and, consequently, the interference produced by the signal. Therefore, the D2D pairs that do not have mutually overlapping transmission ranges can use the same bandwidth resource to transmit simultaneously; through frequency reuse, the overall system capacity can be enhanced.Figure1 illustrates the medium access technology applied in 4G and beyond, namely, Orthogonal Frequency Division Multiple Access (OFDMA) [3]. An OFDMA frame consists of both frequency domain and time domain. The frequency domain is measured in Hertz (Hz) and consists of multiple carriers; each carrier is 180 KHz and can be split into 12 subcarriers. Therefore, each subcarrier is 15 KHz. The time duration of an OFDMA frame is 10 ms, and each frame is divided into ten subframes. Hence, each subframe is 1 ms. A subframe consists of two subslots, where each subslot is 0.5 ms and consists of seven symbols. In the 4G Long-Term Evolution-Advanced (LTE-A) standard, the smallest resource element (RE) and smallest resource block (RB) are defined. One RE consists of one symbol and one subcarrier, whereas one RB consists of seven symbols and one carrier. Therefore, each RB has 84 REs. Since the bandwidth requirement for one piece of UE can be one or more RBs, the scheduler at eNodeB must integrate multiple RBs and allocate them to the UE. This paper defines the bandwidth provided by the integration of multiple RBs as one RB chunk. For example, the RB chunk enclosed by the bold red line in Figure 1 is composed of two RBs.Figure 1
Framework of OFDMA.Figure2 demonstrates that one D2D pair consists of one sender and one receiver. In 3GPP Release13, the direct communication channel between a sender and a receiver is designated as a sidelink [4]. When the sender needs to transmit data, it uses a Sidelink Buffer Status Report (S-BSR) packet to notify the eNodeB about its bandwidth requirement. The eNodeB then allocates an adequate RB chunk to the sidelink according to the received S-BSR packet and informs the sender via a Physical Downlink Control Channel (PDCCH). Before the commencement of the D2D communication, the sender uses a Physical Sidelink Control Channel (PSCCH) to send information to the receiver; this information relates to the RB chunk allocated to the sidelink.Figure 2
Operating procedure of D2D communication.Because the transmission power of the D2D communication is small, it is highly probable that the transmission ranges of D2D pairs do not overlap with one another. The D2D pairs that do not have overlapping transmission ranges can reuse the same bandwidth resource [5, 6] to enhance the overall system capacity. Figure 3 illustrates that each D2D pair comprises one sender and one receiver; the senders are marked in gold (e.g., DUE 1, DUE 3, DUE 5, and DUE n-1), whereas the receivers are marked in gray (e.g., DUE 2, DUE 4, DUE 6, and DUE n). In Figure 3, the D2D pairs covered with different colors stand for communication via different RB chunks. The bottom section of Figure 3 shows two allocated RB chunks in one OFDMA frame, where one is marked in green and the other in blue. These two RB chunks do not reuse the same RBs. The eNodeB cell coverage in Figure 3 contains m D2D pairs. Because the transmission ranges of the D2D pairs may mutually interfere with each other (e.g., D2D pairs 1 and 2), D2D pairs 1 and 2 use the blue and green RB chunks, respectively. However, D2D pairs 2, 3, and m can use the same green RB chunk because their individual transmission ranges do not mutually interfere with each other.Figure 3
Frequency reuse of D2D communication.Without D2D communication, packet exchange between one pair of UE needs the forwarding of eNodeB, resulting in the waste of bandwidth resource and the increase of packet delay. The D2D direct communication reduces the transmission power of UE and cochannel interference. Therefore, RBs can be reused repeatedly, and this repeated usage can enhance the overall system capacity. Aiming to maximize the benefits of frequency reuse and reduce the interference level among adjacent D2D pairs, this paper proposes a heuristic RB allocation mechanism using complete graphs (abbreviated to RACG). At first, RACG establishes an interference graph model and identifies all complete graphs with different numbers of D2D pairs in the model. The main contribution of RACG is that it begins with RB allocation for the D2D pairs in the complete graph with the largest number of D2D pairs and takes into account three additional parameters to determine the allocation sequence for the D2D pairs. The three additional parameters are the frequency at which D2D pairs appear in complete graphs, the interference level of a D2D pair to other D2D pairs, and the number of RBs required. Furthermore, RACG prioritizes the reuse of allocated RB chunks during RB allocation. When a D2D pair and other D2D pairs with allocated RBs do not have mutual interference, the allocated RB chunk that has the closest number of RBs to the number of RBs required is selected and reused. In order to demonstrate the advantages of the proposed RACG, we design two topologies that represent two types of D2D pair distribution, namely, hotspot and random topologies. For the hotspot topology, we select a fixed number of D2D pairs and change the level of interference among the D2D pairs near the hotspot. For the random topology, we gradually increase the total number of D2D pairs. The performance measures include the RB usage rate and occupied rate in an OFDMA frame.The remainder of this paper is organized as follows. Section2 explores the related literature. Section 3 describes the operating procedures of the proposed RACG. Section 4 analyzes and compares the numerical results. Finally, concluding remarks and future works are given in Section 5.


## 2. Related Works

In recent years, studies have proposed RB allocation schemes under the D2D communication. These studies can be classified into four types. The first type of studies [7–12] clustered the D2D pairs based on UE behavior in social networks and applied the game theory to determine optimal RB allocation. The second type of studies [13–18] collected actual geographical locations of D2D pairs to identify the D2D pairs that had no mutual interference and enabled these D2D pairs to reuse the same RB chunk. The third type of studies [19–24] proposed an RB allocation principle with Quality of Services (QoS) provision. The transmission power of each D2D pair was calculated to identify the level of mutual interference, and RB chunks were then allocated to the D2D pairs according to their respective QoS requirements. The fourth type of studies [25–31] created an interference graph model to represent the interference between D2D pairs. As illustrated in Figure 4, each vertex represents a D2D pair. If two D2D pairs mutually interfere with each other, an edge is used to connect two vertices together. Therefore, the degree of each vertex represents the level of interference corresponding to the D2D pair. Each vertex is colored while ensuring that its neighboring vertices do not have the same color. Vertices with the same color are allocated with the same RB chunk to increase the benefits of frequency reuse.Figure 4
Interference graph model.The fourth type of studies is more closely related with the RACG proposed in this paper, and a summary of these studies is provided in this section. Lee et al. [25] proposed an RB allocation with a degree-based greedy (RADG) approach. RADG first calculates the degree of each vertex in an interference graph; next, it selects the D2D pair that has the highest degree (i.e., the D2D pair that causes the largest amount of interference) to perform RB allocation first. If two or more vertices have the same degree, RADG then prioritizes RB allocation for the D2D pair with the larger bandwidth requirement. When the bandwidth requirements are the same, RADG then randomly selects a D2D pair to allocate RBs. RADG is degree-based and does not consider the mutual interference among multiple D2D pairs. Therefore, some D2D pairs cannot reuse the allocated RBs, which reduces the benefits of frequency reuse. In a full duplex environment, T. Yang et al. [26] focused on determining the appropriate transmission powers for uplink, downlink, and D2D communication by establishing the interference graphs of different links according to the bandwidth requirement and interference level for each D2D pair. Li et al. [27] proposed a joint mode selection and resource allocation algorithm by dividing the users into groups via the vertex coloring approach. After solving the power optimization problem for each group and conducting mode selection between the cellular mode and D2D mode for each D2D pair, they assigned channel resources to these groups. On the other hand, the studies in [28–31] considered an environment in which cellular UE and D2D pairs coexist. The authors of [28, 29] considered the level of interference between cellular UE and D2D pairs, and they established an interference graph to determine the optimal RB allocation for achieving the coexistence of cellular UE and D2D pairs. However, cellular UE have higher priority, and an excessive number of cellular UE can cause the starvation of the D2D pairs. Zhao et al. [30] proposed an algorithm that uses an interference graph to decide an RB allocation model. If the interference level of a D2D pair is smaller than a predefined threshold, the D2D pair can reuse the RBs that have allocated to cellular UE. Otherwise, new RBs are allocated to the D2D pair. Without considering the mutual interference between multiple D2D pairs, the proposed RB allocation algorithm is apt to allocate new RBs to some D2D pairs, and this can lead to insufficient system bandwidth. Cai et al. [31] assumed that the number of RBs required by all of cellular UE and D2D pairs is identical, and they used graph coloring to identify the RBs that can be reused. Next, they used the signal-to-interference-plus-noise ratio (SINR) to calculate the transmission rate of these reusable RBs and allocated the RBs with the highest transmission rate to the corresponding D2D pair to meet the bandwidth requirement of each D2D pair. However, this also resulted in some D2D pairs not having reusable RBs, which reduced the benefits of frequency reuse. The application of graph coloring for the above-mentioned RB allocation schemes may result in uneven RB allocation between cellular UE and D2D pairs. In addition, some applications ignore the level of interference between multiple D2D pairs, which leads to fewer reusable RBs because of limited bandwidth resource and therefore affects the overall system capacity.Aiming to maximize the benefits of frequency reuse and reduce the level of interference among adjacent D2D pairs, this paper proposes a heuristic RACG. RACG first maps the interference between D2D pairs to an interference graph model, after which it applies the Bron-Kerbosch algorithm [32] to identify every complete graph within the interference graph. A complete graph (denoted as Kn) is an undirected graph with n vertices, and any two different vertices have exactly one edge connecting them [33]. RACG begins with RB allocation for D2D pairs in the complete graph with the highest number of vertices. The allocation sequence for D2D pairs is determined according to three additional parameters, namely, the number of times D2D pairs appear in different complete graphs, the interference effect of a D2D pair on other D2D pairs, and the number of RBs required by a D2D pair. Besides, RACG prioritizes the reuse of RB chunks during RB allocation. In other words, if a D2D pair and other D2D pairs allocated with RBs do not mutually interfere with each other, we select the allocated RB chunk with the closest number of RBs relative to the number of RBs required. If the RB requirement of this D2D pair exceeds all allocated RB chunks, RACG reuses the largest RB chunk and adds unallocated RBs.


## 3. The Proposed RACG

### 3.1. Interference Graph Model

The RACG mechanism first maps the interference between all D2D pairs to an interference graph model. In the model, each vertex represents one D2D pair, and an edge connecting two vertices indicates the mutual interference between two D2D pairs.Vn and En, respectively, denote a vertex set and edge set in an interference graph. Let Vn=v1,v2,⋯,vn, and the adjacency matrix A is defined to represent the interference graph. A is a symmetric matrix and its size is n×n. The elements of A are ai,j (Equation (1)). When ai,j=1, the transmission ranges of the ith and jth vertices overlap. Conversely, when ai,j=0, the transmission ranges of the two vertices do not overlap. The edge set is En=ei,j∀vi,vj∈Vn,i≠j,ai,j=1. The symbol Gn is used to represent the interference graph whose number of D2D pairs is n, and Gn=Vn,En. For example, Figure 5 shows an interference graph of six D2D pairs, and the adjacency matrix of G6 is demonstrated in Equation (2). In the interference graph of Figure 5, the vertex set V6 is v1,v2,v3,v4,v5,v6, and the edge set E6 is e12,e13,e23,e34,e45,e56.
(1)aij=1,ifviandvjareadjacent0,otherwise∈A,∀1≤i≤n,∀1≤j≤n,(2)3264412.eq-inline.001.Figure 5
Interference graph of six D2D pairs.


### 3.2. RB Allocation Approach

RACG identifies all complete graphs with different number of vertices in the interference graph. Thereafter, it commences RB allocation for the D2D pairs in the complete graph with the largest number of vertices. Different RB chunks are allocated such that the number of RB chunks which can be reused by other D2D pairs increases. These principles allow more D2D pairs to use the same RBs with limited bandwidth resources and increase the benefits of reusing resources. Some D2D pairs may belong to two or more complete graphs with identical sizes. In other words, the vertices of these D2D pairs belong to the intersection of multiple complete graphs with identical sizes. As shown in Figure6, the interference graph has the two largest complete K4 graphs, namely, v1,v2,v3,v4 and v2,v4,v5,v6, and the intersection between these two K4 graphs is v2,v4. v2 and v4 are allocated RB chunks which do not overlap prior to the other vertices for the purpose of reducing the level of interference among adjacent D2D pairs. RB allocation starts with the D2D pairs in the compete graph that has the largest number of vertices, and three parameters are used to determine the allocation sequence of D2D pairs. The three parameters are the number of times D2D pairs appear in different complete graphs, the degree to which a D2D pair interferes with other D2D pairs, and the number of RBs required by a D2D pair. RB allocation to the D2D pairs of K3 will start after RB allocation to the D2D pairs of K4 has finished. RACG prioritizes the allocation of reusable RB chunks. That is, if a D2D pair and other D2D pairs allocated with RBs do not mutually interfere with each other, RACG selects and reuses an allocated RB chunk that has the closest number of RBs to the number of RBs required. Once the RB requirement of a D2D pair exceeds all allocated RB chunks, RACG will reuse the largest RB chunk and adds unallocated RBs.Figure 6
Interference graph with vertices belonging to multiple complete graphs.Table1 lists the parameters used by RACG and their corresponding definitions. n is the number of all vertices in the interference graph. Vm,j is the vertex set of the jth Km complete graph. MKm is the matrix with a size of n×tm, which is made of all Km complete graphs. tm is the total number of Km complete graphs in the interference graph. ci,k denotes the element in the ith row and kth column of MKm; ci,k is either 0 or 1, as demonstrated in Equation (3). If ci,k is equal to 1, then vertex vi belongs to Vm,k; otherwise, ci,k is equal to 0. As expressed by Equation (4), fm,i denotes the sum of all elements in the ith row of MKm, and it indicates the number of Km complete graphs that vertex vi belongs to. rbvi and dvi represent, respectively, the requirement of RBs and degree of vertex vi.
(3)ci,k=1,ifvi∈Vm,k0,otherwise,(4)fm,i=∑k=1tmci,k.Table 1
Parameters and definitions.
ParameterDefinitionnThe number of all verticesVm,jVertex set ofjth Km complete graphMKmMatrix formed by allKm complete graphsci,kElement in theith row and kth column of MKmfm,iSum of all elements inith row of MKmrbviNumber of RBs required by vertexvidviDegree of vertexviThe interference graph of Figure7 is presented as an example. Through applying the Bron-Kerbosch algorithm (mentioned in Section 2), six complete graphs are identified in Figure 7. The vertex sets of these complete graphs are V4,1=v1,v2,v3,v4, V4,2=v3,v4,v5,v6, V4,3=v1,v2,v3,v10, V3,1=v4,v6,v8, V3,2=v6,v7,v8, and V2,1=v8,v9. Therefore, the largest complete graph is K4, and three K4s are identified. The size of MK4 is 10×3, and the value of each element is as shown in Equation (5). Next, the calculation indicates that f4,1=2, f4,2=2, f4,3=3, f4,4=2, f4,5=1, f4,6=1, f4,7=0, f4,8=0, f4,9=0, and f4,10=1. Therefore, v3 has the highest level of interference, and RBs are first allocated to the D2D pair that v3 represents. The vertices v1, v2, and v4 have the same level of interference; hence, RBs are first allocated to the D2D pair that v4 represents because the degree of v4 (denoted as dv4) is greater than dv1 and dv2. Because the degrees of v1 and v2 are both four, the sequence of RB allocation is determined by the RB requirement of the D2D pairs represented by the two vertices (denoted as rbv1 and rbv2).
(5)3264412.eq-inline.002.Figure 7
Interference graph with multiple complete graphs of varying sizes.


### 3.3. Pseudocode of RACG

Pseudocode1 presents the pseudocode of RACG. First, as discussed in Section 3.1, RACG establishes the interference graph model, Gn=Vn,En, of D2D communication. Next, it applies the Bron-Kerbosch algorithm to identify all complete graphs in the interference graph and obtains M vertices in the largest complete graph. Thereafter, MK1, MK2, …, MKM are established, and fm,i, of each vertex i is calculated (1≤m≤M). Per the first principle of RACG, RBs are allocated to the vertex with the largest fM,i (i.e., D2D pair i). When two or more vertices have the same fM,i, the second principle of RACG is applied; that is, these vertices are ranked from largest to smallest according to their degree number for RB allocation. When the degree number of the vertices are the same, the third principle of RACG is applied; that is, RBs are allocated to the vertex that represents the D2D pair requiring the largest number of RBs. When the number of RBs required is identical, a vertex for RB allocation is selected at random.During RB allocation, when D2D pairi is the first to be allocated, then the required RBs (rbvi) are directly allocated to it. By contrast, when this D2D pair and other D2D pairs allocated with RBs mutually interfered with each other, this D2D pair do not reuse the allocated RBs and new RBs will be allocated to it. When this D2D pair and other D2D pairs allocated with RBs do not mutually interfere with each other, the following rules are applied to reuse the allocated RB chunks. (1) The RB chunk that is greater than or equal to rbvi and closest in value to rbvi is reused; and (2) the RB chunk that is smaller than rbvi and closest in value to rbvi is reused, and unallocated RBs are added to meet the RB requirement of vi.Pseudocode 1
RACG.Input :Number of D2D pairs:nInference graph: Gn = (Vn, En)All complete graphs with different set of vertices belonging toGnNumber of the vertices in the maximal complete graph: MThe set ofm vertices for the jth Km: Vm,j for each j, 1 ≤ j ≤ tmThe joint matrix for all of the complete graphs withm vertices: MKm, 1 ≤ m ≤ MNumber of RBs required byvi: rbvi, 1≤ i ≤nDegree ofvi: dvi, 1≤ i ≤nThe set of vertices having been allocated RBs:VR, initially VR={ }Output ://RB allocation to all D2D pairs1.form = M : 1 do2.fm,i = sum of all elements at row i of MKm, 1≤i≤n;3.L= the maximum value among fm,1, fm,2, …, fm,n;4.  for a = L : 1 do5.If only fm,i for vertex vi equals a6.    Do RB allocation for vi;7.   Else8.D = the maximum degree among the vertices with fm,i = a;9.    for d =D : 1 do10.If two or more dvi’s equal to d11.     Do RB allocation forvi’s in the descending order of rbvi;12.Else if two or more vertices requiring the same number of RBs13.      Do RB allocation forvi’s in a random sequence;14.   end for15.  end for16. end for//Do RB allocation for vi17.IfVR ={ }18.  Allocate a new RB chunk ofrbvi RB(s);19.Else ifvi is interfered with every vertex in VR20.   Allocate a new RB chunk ofrbvi RB(s);21.Else if there is at least one allocated RB chunk with size more than rbvi22.   Allocate an allocated RB chunk with size closest torbvi;23. Else24.   Allocate an allocated RB chunk with size closest torbvi plus extra RB(s);25. VR = VR ∪{vi};


## 3.1. Interference Graph Model

The RACG mechanism first maps the interference between all D2D pairs to an interference graph model. In the model, each vertex represents one D2D pair, and an edge connecting two vertices indicates the mutual interference between two D2D pairs.Vn and En, respectively, denote a vertex set and edge set in an interference graph. Let Vn=v1,v2,⋯,vn, and the adjacency matrix A is defined to represent the interference graph. A is a symmetric matrix and its size is n×n. The elements of A are ai,j (Equation (1)). When ai,j=1, the transmission ranges of the ith and jth vertices overlap. Conversely, when ai,j=0, the transmission ranges of the two vertices do not overlap. The edge set is En=ei,j∀vi,vj∈Vn,i≠j,ai,j=1. The symbol Gn is used to represent the interference graph whose number of D2D pairs is n, and Gn=Vn,En. For example, Figure 5 shows an interference graph of six D2D pairs, and the adjacency matrix of G6 is demonstrated in Equation (2). In the interference graph of Figure 5, the vertex set V6 is v1,v2,v3,v4,v5,v6, and the edge set E6 is e12,e13,e23,e34,e45,e56.
(1)aij=1,ifviandvjareadjacent0,otherwise∈A,∀1≤i≤n,∀1≤j≤n,(2)3264412.eq-inline.001.Figure 5
Interference graph of six D2D pairs.


## 3.2. RB Allocation Approach

RACG identifies all complete graphs with different number of vertices in the interference graph. Thereafter, it commences RB allocation for the D2D pairs in the complete graph with the largest number of vertices. Different RB chunks are allocated such that the number of RB chunks which can be reused by other D2D pairs increases. These principles allow more D2D pairs to use the same RBs with limited bandwidth resources and increase the benefits of reusing resources. Some D2D pairs may belong to two or more complete graphs with identical sizes. In other words, the vertices of these D2D pairs belong to the intersection of multiple complete graphs with identical sizes. As shown in Figure6, the interference graph has the two largest complete K4 graphs, namely, v1,v2,v3,v4 and v2,v4,v5,v6, and the intersection between these two K4 graphs is v2,v4. v2 and v4 are allocated RB chunks which do not overlap prior to the other vertices for the purpose of reducing the level of interference among adjacent D2D pairs. RB allocation starts with the D2D pairs in the compete graph that has the largest number of vertices, and three parameters are used to determine the allocation sequence of D2D pairs. The three parameters are the number of times D2D pairs appear in different complete graphs, the degree to which a D2D pair interferes with other D2D pairs, and the number of RBs required by a D2D pair. RB allocation to the D2D pairs of K3 will start after RB allocation to the D2D pairs of K4 has finished. RACG prioritizes the allocation of reusable RB chunks. That is, if a D2D pair and other D2D pairs allocated with RBs do not mutually interfere with each other, RACG selects and reuses an allocated RB chunk that has the closest number of RBs to the number of RBs required. Once the RB requirement of a D2D pair exceeds all allocated RB chunks, RACG will reuse the largest RB chunk and adds unallocated RBs.Figure 6
Interference graph with vertices belonging to multiple complete graphs.Table1 lists the parameters used by RACG and their corresponding definitions. n is the number of all vertices in the interference graph. Vm,j is the vertex set of the jth Km complete graph. MKm is the matrix with a size of n×tm, which is made of all Km complete graphs. tm is the total number of Km complete graphs in the interference graph. ci,k denotes the element in the ith row and kth column of MKm; ci,k is either 0 or 1, as demonstrated in Equation (3). If ci,k is equal to 1, then vertex vi belongs to Vm,k; otherwise, ci,k is equal to 0. As expressed by Equation (4), fm,i denotes the sum of all elements in the ith row of MKm, and it indicates the number of Km complete graphs that vertex vi belongs to. rbvi and dvi represent, respectively, the requirement of RBs and degree of vertex vi.
(3)ci,k=1,ifvi∈Vm,k0,otherwise,(4)fm,i=∑k=1tmci,k.Table 1
Parameters and definitions.
ParameterDefinitionnThe number of all verticesVm,jVertex set ofjth Km complete graphMKmMatrix formed by allKm complete graphsci,kElement in theith row and kth column of MKmfm,iSum of all elements inith row of MKmrbviNumber of RBs required by vertexvidviDegree of vertexviThe interference graph of Figure7 is presented as an example. Through applying the Bron-Kerbosch algorithm (mentioned in Section 2), six complete graphs are identified in Figure 7. The vertex sets of these complete graphs are V4,1=v1,v2,v3,v4, V4,2=v3,v4,v5,v6, V4,3=v1,v2,v3,v10, V3,1=v4,v6,v8, V3,2=v6,v7,v8, and V2,1=v8,v9. Therefore, the largest complete graph is K4, and three K4s are identified. The size of MK4 is 10×3, and the value of each element is as shown in Equation (5). Next, the calculation indicates that f4,1=2, f4,2=2, f4,3=3, f4,4=2, f4,5=1, f4,6=1, f4,7=0, f4,8=0, f4,9=0, and f4,10=1. Therefore, v3 has the highest level of interference, and RBs are first allocated to the D2D pair that v3 represents. The vertices v1, v2, and v4 have the same level of interference; hence, RBs are first allocated to the D2D pair that v4 represents because the degree of v4 (denoted as dv4) is greater than dv1 and dv2. Because the degrees of v1 and v2 are both four, the sequence of RB allocation is determined by the RB requirement of the D2D pairs represented by the two vertices (denoted as rbv1 and rbv2).
(5)3264412.eq-inline.002.Figure 7
Interference graph with multiple complete graphs of varying sizes.


## 3.3. Pseudocode of RACG

Pseudocode1 presents the pseudocode of RACG. First, as discussed in Section 3.1, RACG establishes the interference graph model, Gn=Vn,En, of D2D communication. Next, it applies the Bron-Kerbosch algorithm to identify all complete graphs in the interference graph and obtains M vertices in the largest complete graph. Thereafter, MK1, MK2, …, MKM are established, and fm,i, of each vertex i is calculated (1≤m≤M). Per the first principle of RACG, RBs are allocated to the vertex with the largest fM,i (i.e., D2D pair i). When two or more vertices have the same fM,i, the second principle of RACG is applied; that is, these vertices are ranked from largest to smallest according to their degree number for RB allocation. When the degree number of the vertices are the same, the third principle of RACG is applied; that is, RBs are allocated to the vertex that represents the D2D pair requiring the largest number of RBs. When the number of RBs required is identical, a vertex for RB allocation is selected at random.During RB allocation, when D2D pairi is the first to be allocated, then the required RBs (rbvi) are directly allocated to it. By contrast, when this D2D pair and other D2D pairs allocated with RBs mutually interfered with each other, this D2D pair do not reuse the allocated RBs and new RBs will be allocated to it. When this D2D pair and other D2D pairs allocated with RBs do not mutually interfere with each other, the following rules are applied to reuse the allocated RB chunks. (1) The RB chunk that is greater than or equal to rbvi and closest in value to rbvi is reused; and (2) the RB chunk that is smaller than rbvi and closest in value to rbvi is reused, and unallocated RBs are added to meet the RB requirement of vi.Pseudocode 1
RACG.Input :Number of D2D pairs:nInference graph: Gn = (Vn, En)All complete graphs with different set of vertices belonging toGnNumber of the vertices in the maximal complete graph: MThe set ofm vertices for the jth Km: Vm,j for each j, 1 ≤ j ≤ tmThe joint matrix for all of the complete graphs withm vertices: MKm, 1 ≤ m ≤ MNumber of RBs required byvi: rbvi, 1≤ i ≤nDegree ofvi: dvi, 1≤ i ≤nThe set of vertices having been allocated RBs:VR, initially VR={ }Output ://RB allocation to all D2D pairs1.form = M : 1 do2.fm,i = sum of all elements at row i of MKm, 1≤i≤n;3.L= the maximum value among fm,1, fm,2, …, fm,n;4.  for a = L : 1 do5.If only fm,i for vertex vi equals a6.    Do RB allocation for vi;7.   Else8.D = the maximum degree among the vertices with fm,i = a;9.    for d =D : 1 do10.If two or more dvi’s equal to d11.     Do RB allocation forvi’s in the descending order of rbvi;12.Else if two or more vertices requiring the same number of RBs13.      Do RB allocation forvi’s in a random sequence;14.   end for15.  end for16. end for//Do RB allocation for vi17.IfVR ={ }18.  Allocate a new RB chunk ofrbvi RB(s);19.Else ifvi is interfered with every vertex in VR20.   Allocate a new RB chunk ofrbvi RB(s);21.Else if there is at least one allocated RB chunk with size more than rbvi22.   Allocate an allocated RB chunk with size closest torbvi;23. Else24.   Allocate an allocated RB chunk with size closest torbvi plus extra RB(s);25. VR = VR ∪{vi};


## 4. Performance Evaluation

### 4.1. Simulation Scenarios

We design two network topologies of D2D communication in LTE-A systems as shown in Figure8. The blue circle represents the cell coverage of an eNodeB, and two pieces of UE form a single D2D pair. The distribution of all D2D pairs in Figure 8(a) represents a hotspot topology. Hence, most D2D pairs are concentrated around the eNodeB with only a few D2D pairs being exceptions. Figure 8(b) represents randomly distributed D2D pairs in a random topology.Figure 8
Two network topologies of D2D communication.
(a)
Hotspot topology(b)
Random topologyWe use MATLAB [34] to perform a numerical simulation in which the total number of RBs of an OFDMA frame is set to 400. In the hotspot topology, the number of D2D pairs is fixed at 30, whereas the number of D2D pairs in the random topology changes from 20 to 70. To verify that our proposed RACG effectively alleviates the RB usage rate and occupied rate in an OFDMA frame for D2D communication, we compare RACG and RADG in the hotspot network topology and random network topology. Table 2 summarizes the comparison between RACG and RADG on attributes of design.Table 2
Comparison between RACG and RADG.
Attributes of designThe proposed RACGRADG [25]Interference graph modelvvIdentifying complete graphsvxThe degree of each vertexvvThe frequency at which each vertex appears in complete graphsvxVarious number of RB requirementvvAllocation sequence of the verticesvxReusing an allocated RB chunk with the closest sizevx“v” indicates that the attributes are specified in the scheme. “x” indicates that the attributes are unspecified in the scheme.


### 4.2. Hotspot Network Topology

A hotspot network topology can be classified as high density (HD) and low density (LD). A high-density distribution indicates that the distance between D2D pairs is short, such that D2D pairs are more likely to exhibit mutual interference. By contrast, for a low-density distribution, D2D pairs are further apart and, therefore, less likely to exhibit mutual interference.Figure9 displays the OFDMA Frame Utilization (OFU) of high-density and low-density distributed hotspot network topologies under various bandwidth requirements for D2D pairs. We define OFU as the total number of RBs allocated to D2D pairs divided by the total number of RBs in an OFDMA frame. In Figure 9, the red and blue lines represent the OFU of high-density and low-density distributions, respectively, whereas the solid and dashed lines represent the OFU with RACG and RADG, respectively. We observe from Figure 9 that when the number of RBs required by each D2D pair increases, the OFU of high-density distribution increases at a faster rate, whereas the OFU of low-density distribution increases at a slower rate. This is because the D2D pairs in high-density distribution exhibit more mutual interference. Hence, they have fewer reused RB chunks and the total number of RBs allocated to D2D pairs resulting in a rapid rise in OFU. In high-density distribution, the difference between the OFU with RACG and RADG increases when the number of RBs required by each D2D pair increases, and this trend becomes more obvious in high-density distribution than low-density distribution. This is because RADG only avoids the level of interference but does not consider RB chunks with similar number of RBs; therefore, the OFU of RADG increases rapidly when the number of RBs required increases. Similar to RADG, RACG begins with RB allocation for the D2D pairs in the complete graph with the largest number of vertices, that is, for those with the highest degree. Nevertheless, RACG considers three additional parameters to determine the allocation sequence for the D2D pairs, the frequency at which D2D pairs appear in complete graphs, the interference level of a D2D pair to other D2D pairs, and the number of RBs required, whereas RADG simply generates the allocation sequence at random. Besides, RACG intends allocating the reusable RB chunk that has the closest number of RBs to the number of RBs required to maximize the benefits of frequency reuse. Hence, the OFU of RACG increases at a slower rate relative to RADG.Figure 9
OFDMA frame utilization in the hotspot topology.Randomly setting the number of RBs required by each D2D pair from 31 to 35, we vary the degree of the vertices (i.e., D2D pairs) concentrated near the eNodeB. Figure10 presents the number of RB chunks used in an OFDMA frame when RACG and RADG are applied. The red and blue bars represent the number of RB chunks used by RACG and RADG, respectively. Figure 10 demonstrates that when the interference of D2D pairs concentrated near the center increases or the degree number increases, the number of RB chunks used by RACG or RADG increases. When the degree number of the D2D pairs concentrated near the hotspot increases, the mutual interference between D2D pairs increases, resulting in most D2D pairs being unable to reuse a given RB chunk; therefore, the eNodeB has to allocate a new RB chunk to the D2D pairs. Compared with RADG, RACG achieves superior performance when the mutual interference between D2D pairs increases; this phenomenon is consistent with that observed in Figure 9.Figure 10
Number of allocated RB chunks in the hotspot topology.


### 4.3. Random Network Topology

The number of RBs required by each D2D pair is randomly generated from 1 to 35, and the total number of D2D pairs is varied from 20 to 70. Figure11 presents the OFU versus the total number of D2D pairs in the random network topology. The red and blue lines represent the OFU with RACG and RADG, respectively. Figure 11 indicates that when the number of D2D pairs increases, the OFU with either of RACG and RADG increases. As noted in Section 4.2, the likelihood of D2D pairs mutually interfering with each other increases when the number of D2D pairs increases. Besides, RACG considers more parameters than RADG while doing RB allocation. As a result, the OFU with RACG is lower than that with RADG. However, when the total number of D2D pairs reaches 70, almost all the RBs in an OFDMA frame are used. Hence, the OFU with either of RACG and RADG approaches 100%, and the two schemes do not exhibit a difference.Figure 11
OFDMA frame utilization in the random topology.With the same simulation scenario as Figure11, Figure 12 presents the number of RB chunks used in an OFDMA frame when RACG and RADG are applied. The red and blue bars represent the number of RB chunks used by RACG and RADG, respectively. Figure 12 indicates that the number of RB chunks used by RACG or RADG increases when the number of D2D pairs increases. The number of RB chunks used by RACG is lower than that used by RADG due to the same reason elaborated above. Referring to Figure 11, when the total number of D2D pairs reaches 70, almost all the RBs in an OFDMA frame are used. Therefore, the difference between the number of RB chunks used by RACG and RADG is extremely small.Figure 12
Number of RB chunks used in the random topology.


### 4.4. Complexity Analysis

The time complexity of RACG is divided into five phases. In phase 1,n D2D pairs are mapped to an interference graph model. In phase 2, the number of complete graphs that each vertex belongs to is identified. In phase 3, all elements of a row in the matrix MKm are summed, and each vertex from the largest to smallest is ranked according to its degree. In phase 4, each vertex from the largest to smallest is ranked according to the number of RBs it required. During the final phase, the number of RBs required by each vertex is used for identifying and reusing the RB chunk that corresponds most closely to the number of RBs required by the vertex. In phase 1, the interferences between any two of D2D pairs are inputted into a two-dimensional adjacency matrix; hence, the time complexity for this phase is On2. In phase 2, the Bron-Kerbosch algorithm is applied to identify all the complete graphs in the interference graph. Because the identification of complete graphs is an NP-complete problem, the method proposed by Moon and Moser [35] is applied to group all n vertices into groups of three to form triangles. A total of n/3 triangles are formed, and in each triangle, one or two vertices can form additional triangles with one or two vertices from another triangle. Therefore, the time complexity for identifying the maximum number of complete graphs is O3n/3. In phase 3, we determine the degree of each vertex with the corresponding adjacency matrix A, and we rank them from the largest to smallest according to their degree number; the time complexity for this phase is On2. In phase 4, we rank all the vertices from the largest to smallest according to the number of RBs they required; the time complexity for this phase is also On2. In the final phase, we use the RBs required by each vertex to select and reuse the RB chunk that corresponds most closely to the number of RBs required; the time complexity for this phase is On2. Thus, the time complexity of RACG is O3n/3+4n2.On the other hand, the time complexity of RADG is divided into four phases. In phase 1,n D2D pairs are mapped to an interference graph model; the time complexity for this phase is On2. In phase 2, each row in the adjacency matrix A is summed to obtain the degree of each vertex, and all the vertices from the largest to smallest are ranked according to their degree number; the time complexity for this phase is On2. In phase 3, all the vertices are ranked from the largest to smallest according to the number of RBs they required; the time complexity for this phase is On2. During the final phase, one of RB chunks is randomly selected and reused to meet the RB requirement of each vertex; the time complexity for this phase is On. Thus, the time complexity of RADG is On+3n2. Therefore, the RACG proposed in the paper enables the effective usage of RBs but at the cost of more computational time.


## 4.1. Simulation Scenarios

We design two network topologies of D2D communication in LTE-A systems as shown in Figure8. The blue circle represents the cell coverage of an eNodeB, and two pieces of UE form a single D2D pair. The distribution of all D2D pairs in Figure 8(a) represents a hotspot topology. Hence, most D2D pairs are concentrated around the eNodeB with only a few D2D pairs being exceptions. Figure 8(b) represents randomly distributed D2D pairs in a random topology.Figure 8
Two network topologies of D2D communication.
(a)
Hotspot topology(b)
Random topologyWe use MATLAB [34] to perform a numerical simulation in which the total number of RBs of an OFDMA frame is set to 400. In the hotspot topology, the number of D2D pairs is fixed at 30, whereas the number of D2D pairs in the random topology changes from 20 to 70. To verify that our proposed RACG effectively alleviates the RB usage rate and occupied rate in an OFDMA frame for D2D communication, we compare RACG and RADG in the hotspot network topology and random network topology. Table 2 summarizes the comparison between RACG and RADG on attributes of design.Table 2
Comparison between RACG and RADG.
Attributes of designThe proposed RACGRADG [25]Interference graph modelvvIdentifying complete graphsvxThe degree of each vertexvvThe frequency at which each vertex appears in complete graphsvxVarious number of RB requirementvvAllocation sequence of the verticesvxReusing an allocated RB chunk with the closest sizevx“v” indicates that the attributes are specified in the scheme. “x” indicates that the attributes are unspecified in the scheme.


## 4.2. Hotspot Network Topology

A hotspot network topology can be classified as high density (HD) and low density (LD). A high-density distribution indicates that the distance between D2D pairs is short, such that D2D pairs are more likely to exhibit mutual interference. By contrast, for a low-density distribution, D2D pairs are further apart and, therefore, less likely to exhibit mutual interference.Figure9 displays the OFDMA Frame Utilization (OFU) of high-density and low-density distributed hotspot network topologies under various bandwidth requirements for D2D pairs. We define OFU as the total number of RBs allocated to D2D pairs divided by the total number of RBs in an OFDMA frame. In Figure 9, the red and blue lines represent the OFU of high-density and low-density distributions, respectively, whereas the solid and dashed lines represent the OFU with RACG and RADG, respectively. We observe from Figure 9 that when the number of RBs required by each D2D pair increases, the OFU of high-density distribution increases at a faster rate, whereas the OFU of low-density distribution increases at a slower rate. This is because the D2D pairs in high-density distribution exhibit more mutual interference. Hence, they have fewer reused RB chunks and the total number of RBs allocated to D2D pairs resulting in a rapid rise in OFU. In high-density distribution, the difference between the OFU with RACG and RADG increases when the number of RBs required by each D2D pair increases, and this trend becomes more obvious in high-density distribution than low-density distribution. This is because RADG only avoids the level of interference but does not consider RB chunks with similar number of RBs; therefore, the OFU of RADG increases rapidly when the number of RBs required increases. Similar to RADG, RACG begins with RB allocation for the D2D pairs in the complete graph with the largest number of vertices, that is, for those with the highest degree. Nevertheless, RACG considers three additional parameters to determine the allocation sequence for the D2D pairs, the frequency at which D2D pairs appear in complete graphs, the interference level of a D2D pair to other D2D pairs, and the number of RBs required, whereas RADG simply generates the allocation sequence at random. Besides, RACG intends allocating the reusable RB chunk that has the closest number of RBs to the number of RBs required to maximize the benefits of frequency reuse. Hence, the OFU of RACG increases at a slower rate relative to RADG.Figure 9
OFDMA frame utilization in the hotspot topology.Randomly setting the number of RBs required by each D2D pair from 31 to 35, we vary the degree of the vertices (i.e., D2D pairs) concentrated near the eNodeB. Figure10 presents the number of RB chunks used in an OFDMA frame when RACG and RADG are applied. The red and blue bars represent the number of RB chunks used by RACG and RADG, respectively. Figure 10 demonstrates that when the interference of D2D pairs concentrated near the center increases or the degree number increases, the number of RB chunks used by RACG or RADG increases. When the degree number of the D2D pairs concentrated near the hotspot increases, the mutual interference between D2D pairs increases, resulting in most D2D pairs being unable to reuse a given RB chunk; therefore, the eNodeB has to allocate a new RB chunk to the D2D pairs. Compared with RADG, RACG achieves superior performance when the mutual interference between D2D pairs increases; this phenomenon is consistent with that observed in Figure 9.Figure 10
Number of allocated RB chunks in the hotspot topology.


## 4.3. Random Network Topology

The number of RBs required by each D2D pair is randomly generated from 1 to 35, and the total number of D2D pairs is varied from 20 to 70. Figure11 presents the OFU versus the total number of D2D pairs in the random network topology. The red and blue lines represent the OFU with RACG and RADG, respectively. Figure 11 indicates that when the number of D2D pairs increases, the OFU with either of RACG and RADG increases. As noted in Section 4.2, the likelihood of D2D pairs mutually interfering with each other increases when the number of D2D pairs increases. Besides, RACG considers more parameters than RADG while doing RB allocation. As a result, the OFU with RACG is lower than that with RADG. However, when the total number of D2D pairs reaches 70, almost all the RBs in an OFDMA frame are used. Hence, the OFU with either of RACG and RADG approaches 100%, and the two schemes do not exhibit a difference.Figure 11
OFDMA frame utilization in the random topology.With the same simulation scenario as Figure11, Figure 12 presents the number of RB chunks used in an OFDMA frame when RACG and RADG are applied. The red and blue bars represent the number of RB chunks used by RACG and RADG, respectively. Figure 12 indicates that the number of RB chunks used by RACG or RADG increases when the number of D2D pairs increases. The number of RB chunks used by RACG is lower than that used by RADG due to the same reason elaborated above. Referring to Figure 11, when the total number of D2D pairs reaches 70, almost all the RBs in an OFDMA frame are used. Therefore, the difference between the number of RB chunks used by RACG and RADG is extremely small.Figure 12
Number of RB chunks used in the random topology.


## 4.4. Complexity Analysis

The time complexity of RACG is divided into five phases. In phase 1,n D2D pairs are mapped to an interference graph model. In phase 2, the number of complete graphs that each vertex belongs to is identified. In phase 3, all elements of a row in the matrix MKm are summed, and each vertex from the largest to smallest is ranked according to its degree. In phase 4, each vertex from the largest to smallest is ranked according to the number of RBs it required. During the final phase, the number of RBs required by each vertex is used for identifying and reusing the RB chunk that corresponds most closely to the number of RBs required by the vertex. In phase 1, the interferences between any two of D2D pairs are inputted into a two-dimensional adjacency matrix; hence, the time complexity for this phase is On2. In phase 2, the Bron-Kerbosch algorithm is applied to identify all the complete graphs in the interference graph. Because the identification of complete graphs is an NP-complete problem, the method proposed by Moon and Moser [35] is applied to group all n vertices into groups of three to form triangles. A total of n/3 triangles are formed, and in each triangle, one or two vertices can form additional triangles with one or two vertices from another triangle. Therefore, the time complexity for identifying the maximum number of complete graphs is O3n/3. In phase 3, we determine the degree of each vertex with the corresponding adjacency matrix A, and we rank them from the largest to smallest according to their degree number; the time complexity for this phase is On2. In phase 4, we rank all the vertices from the largest to smallest according to the number of RBs they required; the time complexity for this phase is also On2. In the final phase, we use the RBs required by each vertex to select and reuse the RB chunk that corresponds most closely to the number of RBs required; the time complexity for this phase is On2. Thus, the time complexity of RACG is O3n/3+4n2.On the other hand, the time complexity of RADG is divided into four phases. In phase 1,n D2D pairs are mapped to an interference graph model; the time complexity for this phase is On2. In phase 2, each row in the adjacency matrix A is summed to obtain the degree of each vertex, and all the vertices from the largest to smallest are ranked according to their degree number; the time complexity for this phase is On2. In phase 3, all the vertices are ranked from the largest to smallest according to the number of RBs they required; the time complexity for this phase is On2. During the final phase, one of RB chunks is randomly selected and reused to meet the RB requirement of each vertex; the time complexity for this phase is On. Thus, the time complexity of RADG is On+3n2. Therefore, the RACG proposed in the paper enables the effective usage of RBs but at the cost of more computational time.


## 5. Conclusions

This paper proposes a heuristic RB allocation mechanism using complete graphs (abbreviated to RACG) for D2D communication in LTE-A and beyond mobile communication networks. RACG not only can reduce the cochannel interference but also can enhance the overall system capacity. First, RACG maps the interference between any two of D2D pairs to an interference graph model and identifies all complete graphs in the model. Next, it begins with RB allocation to the D2D pairs in the largest complete graph, and let the D2D pairs with similar RB requirements reuse the same RB chunks if no mutual interference is present. The RB allocation sequence is determined according to three additional parameters, namely, the number of times D2D pairs appear in different complete graphs, the interference effect of a D2D pair on other D2D pairs, and the number of RBs required by a D2D pair. We compare the OFU and number of RB chunks allocated by RACG and RADG via numerical simulations. The results reveal that the difference between RACG and RADG in the OFU increases when the interference among the D2D pairs concentrated at the center increases in the hotspot network topology. The difference between RACG and RADG in the OFU also increases when the total number of D2D pairs increases in the random network topology. On the other hand, the number of RB chunks used by RACG is 15% less than the number of RB chunks used by RADG in the hotspot and random network topologies. Focusing on enhancing the overall system capacity of all communication modes, we are now investigating RB allocation schemes by including cellular UE, which are allowed to directly connect to eNodeB through unused RBs or the RBs used by D2D pairs that do not exhibit mutual interference.



---

*Source: 3264412-2022-02-28.xml*