# Graph-Based Resource Allocation for D2D Communications Underlying Cellular Networks in Multiuser Scenario

Authors: Bin Guo; Shaohui Sun; Qiubin Gao
Journal: International Journal of Antennas and Propagation
 (2014)

---

## Abstract

With the characteristics of considerable user equipment, massive traffic and numerous local services, but limited frequency resources, the mobile communications in the future require efficient use of frequency resources. Device-to-device (D2D) communications underlying cellular networks have been considered as a promising solution to improve the resources utilization in local scenario. In this paper, we investigated the resources allocation problem in multiuser scenario and proposed a graph-based resources allocation scheme which can achieve suboptimal performance but with low computational complexity and less feedback information.


---

## Body

## 1. Introduction

The development of mobile communications is rapid. ITU forecasted that the amount of global mobile user equipment (UE) will catch up with the world’s total population in 2014 [1]. Informa Telecoms & Media Company estimated that the global mobile data traffic will reach 39.75 trillion MB in 2016, which is 10 times the traffic in 2011 [2]. Furthermore, according to a 3GPP’s report [3], about 80 to 90% of the system throughput will occur in local scenarios in future, such as hotspot scenarios and indoor scenarios. These forecasts show that the future mobile communications are characterized by considerable UE, massive traffic, and numerous local services.In addition, at the World Radio Communication Conference in 2007, the bandwidth allocated to mobile communications is less than 600 MHz [4]. However, ITU predicted that the bandwidth requirement for mobile communications will reach 1280–1720 MHz in 2020 [5]. On one hand there are increasing demands, and on the other hand there is a lack of frequency resources. This conflict puts forward the challenge for efficient use of frequency resources.D2D communications as short-range communication technologies underlying cellular networks can not only improve the transmission rate and save propagation latency and transmission power, but also effectively improve the spectrum efficiency and the system performance [6, 7]. Therefore, they are considered as a promising solution to local services.A key issue of D2D communications underlying cellular networks is the resource allocation and there have been a lot of researches about this issue [8–11]. In [8], the optimum resources allocation and power control are analyzed, and the results show that, by proper resources management, D2D communications can effectively improve the total throughput with limited interference between cellular links and D2D communications. In [9], an interference-aware resource allocation scheme is proposed to minimize the interference and obtain substantial gains in system performance. In [10], a novel resource allocation method by which D2D can reuse the resources of more than one cellular user is proposed and the selection of the optimal resource allocation method is discussed. The resource allocation problem was formulated as a noncooperative resource allocation game in [11], and an efficient auction algorithm was proposed to improve the performance of D2D communication. The simulation results showed that the proposed algorithm has close performance to the centralized scheme, and UE battery lifetime can be greatly extended.However, these studies assumed that the number of D2D pairs is not greater than the number of channel resources, which ignores that the number of D2D pairs will exceed the number of available resources in future. In a multiuser scenario, in order to make users as many as possible to get reliable service, it is inevitable to share channel resources between different D2D pairs. Therefore, the interference situation in system will become more complicated. Except for the interferences between D2D communications and cellular networks, there are additional interferences between different D2D pairs. In addition, the channel state information (CSI) required for interference management at BS will increase, which will increase BS’s burden.In this paper, we propose a graph-based resource allocation scheme for D2D communications in multiuser scenario to solve the above problems. Graph theory is an effective mathematical tool, which is widely used to model and analyze the interaction and relationship of different types of networks. There have been some schemes using graph theory to allocate resources for D2D communications [12, 13]. In [12], an interference-aware graph-based resource sharing algorithm is proposed in downlink scenario of D2D communications underlying cellular networks. The algorithm can effectively obtain the near optimal resource assignment solutions at the BS but with low computational complexity. However, the interference-awareness is defined as a condition that the BS can acquire local awareness on channel gains of each communication link and interference link. With the number of D2D pairs increasing, the graph will become complicated. In [13], a weighted bipartite graph-based scheme is proposed in uplink scenario. This scheme divides pieces of cellular UE and D2D pairs into two parties and converts the resources allocation problem into a matching problem. Matching is processed according to the weight which is defined as the difference between the channel capacity of the D2D pair and the cellular UE and the channel capacity of the cellular UE without D2D pair. The proposed channel sharing scheme increases the system capacity. However, the scheme assumes that the number of D2D pairs is not greater than the number of channel resources. For the opposite case, the paper proposes taking the cellular users as the matching object, which may affect the quality of cellular communications.To our knowledge, there have been no researches for D2D communications based on graph theory in multiuser scenario. In this paper, the proposed scheme can reduce computational complexity and the amount of required feedback information on the premise of keeping guaranteed system performance.The rest of this paper is organized as follows. In Section2, the D2D communications underlying cellular networks in multiuser scenario are described and the resource sharing problem is formulated. In Section 3, the graph-based resources allocation scheme is proposed. In Section 4, we show the simulation results and present analysis on the simulation results. In Section 5, the conclusions are drawn.


## 2. System Model

### 2.1. System Model

As illustrated in Figure1, we consider an uplink transmission scenario in a cellular network, in which pieces of cellular UE transmit signals to BS. It is assumed that there are M traditional pieces of cellular UE (indicated by Um) and N(N≥M) D2D pairs (indicated by Dn) within the coverage of BS. Pieces of cellular UE and D2D pairs are uniformly distributed in the area. D2D transmitters (indicated by DTn) transmit signals to D2D receiver (indicated by DRn) and the maximum distance between them is D.Figure 1
System model for D2D communications underlying cellular network when sharing uplink resource.BS allocates channel resources to cellular communications and D2D communications. It is assumed that channel resources are orthogonal, and the interference only exists in intrachannel when different links share the same channel resource. Given that the number of channel resources equals the number of pieces of cellular UE, that is, being equal toM, one D2D pair is allowed to share one channel resource with other D2D pairs. Therefore, there are two kinds of interferences in this scenario due to channel resources sharing. One is the interference between cellular links and D2D communications. Another is the interference between different D2D pairs.In order to reduce interference and save energy, BS controls the transmit power of pieces of cellular UE and D2D transmitters determine transmit power themselves by setting the maximum transmit powerPTmax⁡ and the maximum received power PRmax⁡. In general, transmitters will transmit signals in PTmax⁡. However, when a received power exceeds the PRmax⁡, the corresponding transmitter should reduce the transmit power.In this paper, the channel model is considered as Rayleigh fading channel, and the channel response follows the independent complex Gaussian distribution. Besides, the path loss model is considered as distance-dependent path loss. Therefore, the channel gains contain the normalized small-scale fading and the path loss. We usegUm,BS, gDTn,DRn, gDTn,BS, and gUm,DRn to, respectively, represent the channel gains of the traditional cellular communication link from Um to BS, the D2D communication link from DTn to DRn, the interference link from DTn to BS, and the interference link from Um to DRn.Consider the following:(1)gUm,BS=PLUm,BShUm,BS,gDTn,DRn=PLDTn,DRnhDTn,DRn,gDTn,BS=PLDTn,BShDTn,BS,gUm,DRn=PLUm,DRnhUm,DRn,
where PLUm,BS, PLDTn,DRn, PLDTn,BS, and PLUm,DRn are the corresponding path losses. hUm,BS, hDTn,DRn, hDTn,BS, and hUm,DRn are the corresponding small-scale fading.


### 2.2. Problem Formulation

We consider that cellular communications have higher priority and BS must guarantee the performance of cellular links first. Therefore, resources allocation for D2D communications is considered under the assumption that all pieces of cellular UE have already equally obtained channel resources.In multiuser scenario, in order to make D2D pairs as many as possible obtaining effective resources, it is inevitable to allocate one channel resource to multiple D2D pairs. On one hand, that leads to a cumulative effect of the interference in one channel resource. On the other hand, that introduces additional interference between these D2D pairs. Therefore, in order to reduce the total interference level in the system as much as possible, it is required to conduct reasonable resources allocation. In this paper, we take the minimum interference level of the system as objective.The resources sharing situation between pieces of cellular UE and D2D pairs are denoted as matrixAM×N=[am,n], where am,n=1 and am,n=0 are, respectively, used to imply whether cellular UE Um and D2D pair Dn share the same resources or not.Thus, the objective can be expressed as(2)min⁡∑m=1MIms.t.∑m=1Mαm,n=1,n=1,…,N.The constraint guarantees that each D2D pair is allowed to obtain one channel resource.I
m is the interference power in channel resource m:
(3)Im=∑m=1M∑n=1N(Im,nc+Im,nd),
where Im,nc and Im,nd, respectively, represent the received interference at BS in channel m from D2D pair Dn and the received interference at D2D pair Dn in channel m from cellular UE Um:
(4)Im,nc=αm,nPDTngDTn,BS,Im,nd=αm,nPUmgUm,DRn+∑i=1i≠nNαm,iPDTigDTi,DRn,
where PDTn is the transmit power of DTn.Thus, the optimization objective can be rewritten as(5)min⁡⁡∑m=1MIm=min⁡⁡∑m=1M∑n=1N(+∑i=1i≠nNαm,iPDTigDTi,DRnαm,n(PDTngDTn,BS+PUmgUm,DRn)+∑i=1i≠nNαm,iPDTigDTi,DRn)s.t.∑m=1Mαm,n=1,n=1,…,N.Moreover, in ideal conditions, BS should know CSIs of all communication links and all interference links to allocate resources. The information is reported by users. In multiuser scenario, BS not only considers the resources sharing between pieces of cellular UE and D2D pairs, but also considers the resources sharing between different D2D pairs. Therefore, a D2D pair needs to report CSIs of the links from all pieces of cellular UE and all the other D2D pairs. With the number of D2D pairs increasing, the amount of feedback information will be considerable. Hence, it is necessary to design an effective method to reduce the amount of feedback information.


## 2.1. System Model

As illustrated in Figure1, we consider an uplink transmission scenario in a cellular network, in which pieces of cellular UE transmit signals to BS. It is assumed that there are M traditional pieces of cellular UE (indicated by Um) and N(N≥M) D2D pairs (indicated by Dn) within the coverage of BS. Pieces of cellular UE and D2D pairs are uniformly distributed in the area. D2D transmitters (indicated by DTn) transmit signals to D2D receiver (indicated by DRn) and the maximum distance between them is D.Figure 1
System model for D2D communications underlying cellular network when sharing uplink resource.BS allocates channel resources to cellular communications and D2D communications. It is assumed that channel resources are orthogonal, and the interference only exists in intrachannel when different links share the same channel resource. Given that the number of channel resources equals the number of pieces of cellular UE, that is, being equal toM, one D2D pair is allowed to share one channel resource with other D2D pairs. Therefore, there are two kinds of interferences in this scenario due to channel resources sharing. One is the interference between cellular links and D2D communications. Another is the interference between different D2D pairs.In order to reduce interference and save energy, BS controls the transmit power of pieces of cellular UE and D2D transmitters determine transmit power themselves by setting the maximum transmit powerPTmax⁡ and the maximum received power PRmax⁡. In general, transmitters will transmit signals in PTmax⁡. However, when a received power exceeds the PRmax⁡, the corresponding transmitter should reduce the transmit power.In this paper, the channel model is considered as Rayleigh fading channel, and the channel response follows the independent complex Gaussian distribution. Besides, the path loss model is considered as distance-dependent path loss. Therefore, the channel gains contain the normalized small-scale fading and the path loss. We usegUm,BS, gDTn,DRn, gDTn,BS, and gUm,DRn to, respectively, represent the channel gains of the traditional cellular communication link from Um to BS, the D2D communication link from DTn to DRn, the interference link from DTn to BS, and the interference link from Um to DRn.Consider the following:(1)gUm,BS=PLUm,BShUm,BS,gDTn,DRn=PLDTn,DRnhDTn,DRn,gDTn,BS=PLDTn,BShDTn,BS,gUm,DRn=PLUm,DRnhUm,DRn,
where PLUm,BS, PLDTn,DRn, PLDTn,BS, and PLUm,DRn are the corresponding path losses. hUm,BS, hDTn,DRn, hDTn,BS, and hUm,DRn are the corresponding small-scale fading.


## 2.2. Problem Formulation

We consider that cellular communications have higher priority and BS must guarantee the performance of cellular links first. Therefore, resources allocation for D2D communications is considered under the assumption that all pieces of cellular UE have already equally obtained channel resources.In multiuser scenario, in order to make D2D pairs as many as possible obtaining effective resources, it is inevitable to allocate one channel resource to multiple D2D pairs. On one hand, that leads to a cumulative effect of the interference in one channel resource. On the other hand, that introduces additional interference between these D2D pairs. Therefore, in order to reduce the total interference level in the system as much as possible, it is required to conduct reasonable resources allocation. In this paper, we take the minimum interference level of the system as objective.The resources sharing situation between pieces of cellular UE and D2D pairs are denoted as matrixAM×N=[am,n], where am,n=1 and am,n=0 are, respectively, used to imply whether cellular UE Um and D2D pair Dn share the same resources or not.Thus, the objective can be expressed as(2)min⁡∑m=1MIms.t.∑m=1Mαm,n=1,n=1,…,N.The constraint guarantees that each D2D pair is allowed to obtain one channel resource.I
m is the interference power in channel resource m:
(3)Im=∑m=1M∑n=1N(Im,nc+Im,nd),
where Im,nc and Im,nd, respectively, represent the received interference at BS in channel m from D2D pair Dn and the received interference at D2D pair Dn in channel m from cellular UE Um:
(4)Im,nc=αm,nPDTngDTn,BS,Im,nd=αm,nPUmgUm,DRn+∑i=1i≠nNαm,iPDTigDTi,DRn,
where PDTn is the transmit power of DTn.Thus, the optimization objective can be rewritten as(5)min⁡⁡∑m=1MIm=min⁡⁡∑m=1M∑n=1N(+∑i=1i≠nNαm,iPDTigDTi,DRnαm,n(PDTngDTn,BS+PUmgUm,DRn)+∑i=1i≠nNαm,iPDTigDTi,DRn)s.t.∑m=1Mαm,n=1,n=1,…,N.Moreover, in ideal conditions, BS should know CSIs of all communication links and all interference links to allocate resources. The information is reported by users. In multiuser scenario, BS not only considers the resources sharing between pieces of cellular UE and D2D pairs, but also considers the resources sharing between different D2D pairs. Therefore, a D2D pair needs to report CSIs of the links from all pieces of cellular UE and all the other D2D pairs. With the number of D2D pairs increasing, the amount of feedback information will be considerable. Hence, it is necessary to design an effective method to reduce the amount of feedback information.


## 3. Graph-Based Resource Allocation Scheme

In this section, the proposed graph-based resource allocation scheme is introduced in detail. In order to decrease the interference level of the system, we propose a resources allocation scheme giving priority to the resources with the minimum interference. In order to avoid the severe interference between D2D pairs and reduce the amount of feedback information, we set up interference matrixes based on a new feedback model. In addition, in order to ensure the performance of cellular links, we design a resource selection scheme to avoid too many D2D pairs reusing one cellular resource.


### 3.1. Feedback Model

Before allocating resources, BS collects CSIs of related channels. Hence, a D2D pair is required to have the ability of measuring channel state including the channels from pieces of cellular UE to the D2D receiver and the channels from all the other D2D transmitters to the D2D receiver and the ability of reporting the information to BS.The channel state from pieces of cellular UE to D2D receivers can be measured and reported by D2D receivers which monitor all communication channels, while, to measure the channel state of interference links between different D2D pairs, we define an exclusive channel for D2D communications, denoted by D2DCH, which consisted ofN orthogonal subchannels. The pattern of the subchannels can be multiple OFDM subcarriers, orthogonal spread spectrum codes, or independent time slots. Each subchannel matches a unique D2D pair. Each D2D transmitter launches its ID signal in corresponding subchannel and each D2D receiver monitors the D2DCH and reports the results to BS.It is seen that the required feedback information of one D2D pair includes CSIs of channels between this D2D pair and all pieces of cellular UE and CSIs of channels between this D2D pair and all the other D2D pairs. With the number of D2D pairs increasing, this feedback model will cause considerable overheads. Therefore, we design a new feedback model to reduce the overheads.First of all, a threshold of interference powerη is set for D2D communications. Then, D2D receivers monitor all cellular resources and report feedback information of those resources in which the received interference power is lower than η. After receiving the feedback information, BS establishes a matrix denoted as X1M×N=[x1m,n], where x1m,n=1 is used to imply that the cellular UE Um does not cause severe interference to D2D pair Dn and cellular resource m is available and x1m,n=0 implies that cellular resource m is not available.At the same time, D2D receivers monitor the subchannels of D2DCH and record those subchannels in which the received interference power is larger thanη. D2D receivers establish matrix denoted as X2N×N′=[x2n,n′], where the x2n,n′=1 and x2n,n′=0 are, respectively, used to imply whether the D2D pair Dn′ will cause severe interference or not to D2D pair Dn when they share the same channel resource. Every D2D receiver just needs to report its corresponding row in X2N×N′ to BS.By this feedback model, D2D pairs just report a part of CSIs and a list, instead of CSIs of all channels. Thus, the amount of feedback information can be reduced considerably. Notice that do not setη too small, or there will be some D2D pairs that cannot acquire resources. The way to set up a reasonable η needs further study. Furthermore, with the matrix X2N×N′, BS can avoid allocating the same resource to D2D pairs which may cause severe interference.


### 3.2. Graph Construction

The first step of the graph-based resource allocation scheme is the graph construction. Here, we consider that a weighted bipartite graph which contains two parties of vertices, respectively, represents the pieces of cellular UE and D2D pairs, and some weighted edges represent the relationships between vertices. According to the scenario in Figure1, the constructed graph is shown in Figure 2.Figure 2
An illustrative example of the graph.There are two pieces of cellular UE and four D2D pairs are in the graph.U1 and U2, which present the pieces of cellular UE, compose the left part, and D1,D2,D3, and D4, which present D2D pairs, compose the right part. The graph is denoted by G=(Vc,Vd,E), where Vc is the vertices set of pieces of cellular UE, Vd is the vertices set of D2D pairs, and E is the edges set. Each vertex vmc∈Vc represents a cellular UE and each vertex vnd∈Vd represents a D2D pair. The edge em,n∈E implies that the D2D pair vnd shares the channel resource with the cellular UE vmc. Moreover, the weights set is denoted by WM×N, which is M-by-N matrix. The element wm,n∈WM×N, representing the weight of the em,n, equals the interference power Im,nc. In addition, the edge en,n′∈E connects vnd∈Vd and vn′d∈Vd, which implies the interference level between D2D pair vnd and D2D pair vn′d. When they will cause strong interference, the edge is denoted by dotted lines. When the interference can be ignored, the edge is denoted by solid lines. The interference level can be obtained according to the matrix X2N×N′.


### 3.3. Graph-Based Resource Allocation Scheme

The algorithm of the proposed scheme is detailed in Algorithm1. Firstly, the graph is established and the parameters of the graph are initialized. The matrix X1M×N and matrix X2M×N are established according to the feedback information of each D2D pair. The WM×N is calculated according to X1M×N and the edge between different D2D pairs is determined by X2M×N. A list LA1×M is established to accumulate interference from allocated D2D pairs on each channel resource and its elements are initialized to 0. A list LR1×N is established to record the allocated resource for D2D pairs and its elements are initialized to 0.Algorithm 1:Graph-based resources allocation algorithm.
Step  1. Graph Construction
Construct the graph and initialize the parameters of the graph.
CalculateX1M×N and X2M×N.
CalculateWM×N according to X1M×N and construct edges between D2D pairs according to X2M×N.
Step  2. Allocation Scheme
Initialize the elements ofLA1×M and LR1×N to 0.
Repeat:
Select the minimum element in the matrix which addsLA1×M to each column of WM×N.
Record the selected resource inLR1×N and accumulate the corresponding weight in LA1×M.
Find D2D pairs whose value in the selected column ofX2N×N′
is 1 and set these D2D pairs’ weights on selected resource to infinite.
UntilLR1×N has no 0 elements.Resources allocation is achieved by an iteration algorithm which is controlled byLR1×N. When LR1×N does not have 0 elements, the calculation will be terminated. In order to reduce the interference level of the system, the resources with the minimum weight are allocated preferentially. However, only considering the weight may lead to a condition that too many D2D pairs reuse one channel resource, which will cause strong accumulative interference on this cellular link. Therefore, we take the sum of weight and accumulated interference as the basis for selecting reuse resource. In each iteration, the edge with the minimum sum value is selected. Then, the selected weight is accumulated to LA1×M. Resource allocation for D2D pair Dn may affect D2D pairs whose value in the nth column of X2N×N′ is 1. The allocated resource will be forbidden to share with those D2D pairs, so their weights associated with the allocated resource will be set to infinite. At this point, the allocation process for one D2D pair is completed. Repeat the above steps until each element of LR1×N is not 0.In addition, the transmit power of D2D communications is determined by D2D transmitters. The initial transmit power of a D2D pair isPTmax⁡. According to the received power reported from D2D receiver, D2D transmitter computes the path loss. If the received power at receiver is lower than PRmax⁡, the transmitter keeps transmit power. If the received power is larger than PRmax⁡, the transmitter computes a new transmit power according to the path loss. By power control, the interference can be further reduced.


### 3.4. Complexity Analysis

At last, we analyze the superiority of the proposed graph-based resource allocation scheme on computational complexity. According to the iteration algorithm in Algorithm1, the computational complexity of the proposed scheme is relative to the initial state of the graph. In the worst case, the computational complexity is
(6)χprop=O((MN)2),
where the computational complexity of finding the minimum value from M-by-N matrix is treated as O(MN).Meanwhile, the computational complexity of the enumeration scheme is calculated as(7)χenum=O(MN).It is obvious that as the number of D2D pairs increases, the computational complexity of the enumeration scheme will increase rapidly. However, the computational complexity of the proposed scheme is polynomial time. Therefore, the proposed scheme is more effective.


## 3.1. Feedback Model

Before allocating resources, BS collects CSIs of related channels. Hence, a D2D pair is required to have the ability of measuring channel state including the channels from pieces of cellular UE to the D2D receiver and the channels from all the other D2D transmitters to the D2D receiver and the ability of reporting the information to BS.The channel state from pieces of cellular UE to D2D receivers can be measured and reported by D2D receivers which monitor all communication channels, while, to measure the channel state of interference links between different D2D pairs, we define an exclusive channel for D2D communications, denoted by D2DCH, which consisted ofN orthogonal subchannels. The pattern of the subchannels can be multiple OFDM subcarriers, orthogonal spread spectrum codes, or independent time slots. Each subchannel matches a unique D2D pair. Each D2D transmitter launches its ID signal in corresponding subchannel and each D2D receiver monitors the D2DCH and reports the results to BS.It is seen that the required feedback information of one D2D pair includes CSIs of channels between this D2D pair and all pieces of cellular UE and CSIs of channels between this D2D pair and all the other D2D pairs. With the number of D2D pairs increasing, this feedback model will cause considerable overheads. Therefore, we design a new feedback model to reduce the overheads.First of all, a threshold of interference powerη is set for D2D communications. Then, D2D receivers monitor all cellular resources and report feedback information of those resources in which the received interference power is lower than η. After receiving the feedback information, BS establishes a matrix denoted as X1M×N=[x1m,n], where x1m,n=1 is used to imply that the cellular UE Um does not cause severe interference to D2D pair Dn and cellular resource m is available and x1m,n=0 implies that cellular resource m is not available.At the same time, D2D receivers monitor the subchannels of D2DCH and record those subchannels in which the received interference power is larger thanη. D2D receivers establish matrix denoted as X2N×N′=[x2n,n′], where the x2n,n′=1 and x2n,n′=0 are, respectively, used to imply whether the D2D pair Dn′ will cause severe interference or not to D2D pair Dn when they share the same channel resource. Every D2D receiver just needs to report its corresponding row in X2N×N′ to BS.By this feedback model, D2D pairs just report a part of CSIs and a list, instead of CSIs of all channels. Thus, the amount of feedback information can be reduced considerably. Notice that do not setη too small, or there will be some D2D pairs that cannot acquire resources. The way to set up a reasonable η needs further study. Furthermore, with the matrix X2N×N′, BS can avoid allocating the same resource to D2D pairs which may cause severe interference.


## 3.2. Graph Construction

The first step of the graph-based resource allocation scheme is the graph construction. Here, we consider that a weighted bipartite graph which contains two parties of vertices, respectively, represents the pieces of cellular UE and D2D pairs, and some weighted edges represent the relationships between vertices. According to the scenario in Figure1, the constructed graph is shown in Figure 2.Figure 2
An illustrative example of the graph.There are two pieces of cellular UE and four D2D pairs are in the graph.U1 and U2, which present the pieces of cellular UE, compose the left part, and D1,D2,D3, and D4, which present D2D pairs, compose the right part. The graph is denoted by G=(Vc,Vd,E), where Vc is the vertices set of pieces of cellular UE, Vd is the vertices set of D2D pairs, and E is the edges set. Each vertex vmc∈Vc represents a cellular UE and each vertex vnd∈Vd represents a D2D pair. The edge em,n∈E implies that the D2D pair vnd shares the channel resource with the cellular UE vmc. Moreover, the weights set is denoted by WM×N, which is M-by-N matrix. The element wm,n∈WM×N, representing the weight of the em,n, equals the interference power Im,nc. In addition, the edge en,n′∈E connects vnd∈Vd and vn′d∈Vd, which implies the interference level between D2D pair vnd and D2D pair vn′d. When they will cause strong interference, the edge is denoted by dotted lines. When the interference can be ignored, the edge is denoted by solid lines. The interference level can be obtained according to the matrix X2N×N′.


## 3.3. Graph-Based Resource Allocation Scheme

The algorithm of the proposed scheme is detailed in Algorithm1. Firstly, the graph is established and the parameters of the graph are initialized. The matrix X1M×N and matrix X2M×N are established according to the feedback information of each D2D pair. The WM×N is calculated according to X1M×N and the edge between different D2D pairs is determined by X2M×N. A list LA1×M is established to accumulate interference from allocated D2D pairs on each channel resource and its elements are initialized to 0. A list LR1×N is established to record the allocated resource for D2D pairs and its elements are initialized to 0.Algorithm 1:Graph-based resources allocation algorithm.
Step  1. Graph Construction
Construct the graph and initialize the parameters of the graph.
CalculateX1M×N and X2M×N.
CalculateWM×N according to X1M×N and construct edges between D2D pairs according to X2M×N.
Step  2. Allocation Scheme
Initialize the elements ofLA1×M and LR1×N to 0.
Repeat:
Select the minimum element in the matrix which addsLA1×M to each column of WM×N.
Record the selected resource inLR1×N and accumulate the corresponding weight in LA1×M.
Find D2D pairs whose value in the selected column ofX2N×N′
is 1 and set these D2D pairs’ weights on selected resource to infinite.
UntilLR1×N has no 0 elements.Resources allocation is achieved by an iteration algorithm which is controlled byLR1×N. When LR1×N does not have 0 elements, the calculation will be terminated. In order to reduce the interference level of the system, the resources with the minimum weight are allocated preferentially. However, only considering the weight may lead to a condition that too many D2D pairs reuse one channel resource, which will cause strong accumulative interference on this cellular link. Therefore, we take the sum of weight and accumulated interference as the basis for selecting reuse resource. In each iteration, the edge with the minimum sum value is selected. Then, the selected weight is accumulated to LA1×M. Resource allocation for D2D pair Dn may affect D2D pairs whose value in the nth column of X2N×N′ is 1. The allocated resource will be forbidden to share with those D2D pairs, so their weights associated with the allocated resource will be set to infinite. At this point, the allocation process for one D2D pair is completed. Repeat the above steps until each element of LR1×N is not 0.In addition, the transmit power of D2D communications is determined by D2D transmitters. The initial transmit power of a D2D pair isPTmax⁡. According to the received power reported from D2D receiver, D2D transmitter computes the path loss. If the received power at receiver is lower than PRmax⁡, the transmitter keeps transmit power. If the received power is larger than PRmax⁡, the transmitter computes a new transmit power according to the path loss. By power control, the interference can be further reduced.


## 3.4. Complexity Analysis

At last, we analyze the superiority of the proposed graph-based resource allocation scheme on computational complexity. According to the iteration algorithm in Algorithm1, the computational complexity of the proposed scheme is relative to the initial state of the graph. In the worst case, the computational complexity is
(6)χprop=O((MN)2),
where the computational complexity of finding the minimum value from M-by-N matrix is treated as O(MN).Meanwhile, the computational complexity of the enumeration scheme is calculated as(7)χenum=O(MN).It is obvious that as the number of D2D pairs increases, the computational complexity of the enumeration scheme will increase rapidly. However, the computational complexity of the proposed scheme is polynomial time. Therefore, the proposed scheme is more effective.


## 4. Simulation Results and Analysis

In this section, we give the simulation results of the proposed resources allocation scheme comparing with enumeration scheme, which achieves the optimal resources allocation through an exhaustive search, and random resources sharing scheme, which allocates the cellular resources to D2D pairs randomly. The parameters are shown in Table1.Table 1
Parameters for simulation.
Parameter
Value
Cell radius
1000 m
The number of channel resources
5
Maximum D2D pair distance
40 m
Maximum transmit power of pieces of cellular UE
23 dBm
Maximum transmit power of D2D transmitters
23 dBm
Maximum received power PRmax
−106 dBm
Noise power
−174 dBm
SINR threshold of cellular links SINRthre
6 dB
Interference threshold of D2D communicationsη
−90 dBmIn terms of system interference, we compare three resource allocation schemes for the considered multiuser scenario of D2D communications underlying cellular network. Figure3 shows that the system interference changed with the number of D2D pairs. It is shown that the interference level changed little with pair number. The enumeration scheme has the lowest interference level, the interference of the proposed scheme is bigger than the optimal scheme by 16 dB, and the interference of the random scheme is the largest.Figure 3
System interference with the number of D2D pairs.Moreover, we investigate the performance of system capacity. Figure4 shows that, with different number of D2D pairs, the enumeration scheme achieves the optimal performance and the proposed scheme achieves suboptimal performance. However, the computational complexity of the proposed scheme is much lower than the enumeration scheme. On the other hand, compared with the random scheme, the proposed scheme has a significant performance promotion in system capacity. In sum, we can conclude that the proposed scheme is an efficiency method for resources allocation.Figure 4
System capacity with the number of D2D pairs.Figure5 shows that the average feedback information of all D2D pairs in system changed with the number of D2D pairs. As it is shown, the feedback amount of the enumeration scheme is much higher than the proposed scheme, and the difference between these two schemes is becoming larger with the number of D2D pairs increasing. It is indicated that the feedback model can not only help construct the edge between D2D pairs, but also effectively reduce the amount of feedback information. Therefore, the proposed scheme will not increase overhead to the system.Figure 5
The average feedback amount with the number of D2D pairs.


## 5. Conclusions

In this paper, we proposed a resources allocation scheme based on graph theory for D2D communication underlying cellular networks in multiuser scenario. Simulation results show that the proposed resources allocation scheme achieves a lower interference level which is close to the optimal scheme but much lower than the random scheme. Furthermore, the proposed scheme can achieve suboptimal system capacity with much lower computational complexity than the enumeration scheme. At the same time, the proposed scheme sharply decreases the amount of feedback information.



---

*Source: 783631-2014-08-12.xml*