A Joint Algorithm for Resource Allocation in D2D 5G Wireless Networks

Fahd N.Al-Wesabi,Imran Khan,Mohammad Alamgeer,Ali M.Al-Sharafi,Bong Jun Choi,Abdallah Aldosary and Ehab Mahmoud Mohamed

1Department of Computer Science,King Khalid University,Muhayel Aseer,KSA

2Faculty of Computer and IT,Sana’a University,Yemen

3Department of Electrical Engineering,University of Engineering and Technology,Peshawar,P.O.B 814,Pakistan

4Department of Information Systems,King Khalid University,Mayahel Aseer,KSA

5Department of Computer Science,College of Computers and Information Technology,University of Bisha,KSA

6School of Computer Science and Engineering,Soongsil University,South Korea

7Department of Computer Science,Prince Sattam bin Abdulaziz University,As Sulayyil,11991,Saudi Arabia

8Electrical Engineering Department,College of Engineering,Prince Sattam Bin Abdulaziz University,Wadi Addwasir,11991,Saudi Arabia

9Electrical Engineering Department,Faculty of Engineering,Aswan University,Aswan,81542,Egypt

Abstract:With the rapid development of Internet technology,users have an increasing demand for data.The continuous popularizationof traffic-intensive applications such as high-definition video,3D visualization,and cloud computing has promoted the rapid evolution of the communications industry.In order to cope with the huge traffic demand of today’s users,5G networks must be fast,flexible,reliable and sustainable.Based on these research backgrounds,the academic community has proposed D2D communication.The main feature of D2D communication is that it enables direct communication between devices,thereby effectively improve resource utilization and reduce the dependence on base stations,so it can effectively improve the throughput of multimedia data.One of the most considerable factor which affects the performance of D2D communication is the co-channel interference which results due to the multiplexing of multiple D2D user using the same channel resource of the cellular user.To solve this problem,this paper proposes a joint algorithm time scheduling and power control.The main idea is to effectively maximize the number of allocated resources in each scheduling period with satisfied quality of service requirements.The constraint problem is decomposed into time scheduling and power control subproblems.The power control subproblem has the characteristics of mixed-integer linear programming of NP-hard.Therefore,we proposed a gradual power control method.The time scheduling subproblem belongs to the NP-hard problem having convex-cordinality,therefore,we proposed a heuristic scheme to optimize resource allocation.Simulation results show that the proposed algorithm effectively improved the resource allocation and overcome the co-channel interference as compared with existing algorithms.

Keywords:6G;wireless networks;mobile communication;linear programming

1 Introduction

Device-to-device(D2D)communication has been integrated into the cellular network as an innovation of next-generation communication[1–10].This new type of wireless communication directly transmits data without being forwarded by the base station,so the spectrum utilization rate and data transmission rate are both Improved and reduced the burden of the load[11–21].This communication method has become a research hotspot in the industry,and is committed to the solution of D2D communication solutions[22–25].

According to Cisco’s latest statistical results[26],multimedia streaming has become the mainstream business in wireless networks,and with the changes in people’s lifestyles,more and more multimedia streams are generated in neighboring areas.Communication between traditional base stations and equipment transmission efficiency of the mode in the above scenario is low.As a short-distance communication method,terminal direct communication enables data transmission links to be established directly between devices without forwarding through the base station.It can greatly improve the user’s quality-of-service(QoS)experience,improve the system frequency band utilization,and effectively reduce the load of the base station.Therefore,D2D communication has received extensive attention from academics and industry[27–29],and is regarded as one of the key technologies in 5G[30].

However,when multiple D2D links reuse the same resource,co-channel interference problems will occur.How to solve this problem becomes the key to D2D communication.The resource allocation can coordinate user interference and effectively alleviate the above problems[31,32].In the existing literature,the authors[33]puts forward a channel selection strategy that maximizes the signal-to-interference-noise ratio in the single-link multiplexed single-channel scenario,with the system throughput as the goal,and observes that the system throughput is affected by the number of channels.In order to maximize the total transmission rate of the system,the authors in[34]proposed a reverse iterative combined auction mechanism for multi-link multiplexing single-channel scenarios,which reduced the algorithm complexity.The authors in[35]proposed a method for optimizing the power of D2D users from the perspective of power control in the single-link multiplexing single-channel scenario,and optimized the transmission rate.The authors in[36]optimizes the overall throughput of the system through channel allocation and greedy algorithm for the multi-user multiplexing single channel scenario.In[37],in order to optimize the spectrum utilization,in the single link multiplexing single channel scenario,power control and mode selection are combined to maximize spectrum utilization.In[38],in order to ensure the QoS of D2D users while minimizing the total energy consumption of the system,for the singlelink multiplexing single-channel scenario,the joint mode selection,power control and channel allocation are optimized.The authors in[39]combined power control and resource allocation in the single-link multiplexing single-channel scenario,and proposed a resource allocation mechanism based on graph theory to ensure the quality of service for cellular users and D2D users.Minimize system energy consumption under the premise.Reference[40]aims at multi-user multiplexing single-channel resource scenarios,joint access control,power control and channel allocation to maximize the system throughput,and ensure the existing cellular link users and D2D users QoS.Reference[41]considers the best power allocation in the multi-link multiplexing single channel scenario and proposes a mechanism to maximize the system throughput under the premise of ensuring the QoS of D2D users.Reference[42]aims at the single-link multiplexing single-channel scenario,combined power control and mode selection,and uses an exhaustive search method to ensure the user transmission rate.

However,the literature[33–42]has the following defects:1)The user’s QoS is not guaranteed with the user as the center,and the user’s communication quality cannot be guaranteed[33–41];2)Guaranteed D2D user’s QoS,but the scene a single D2D users can only reuse a single resource[37–39],and the scenario where a single D2D user reuses multiple channel resources has not been studied;3)Without considering the joint optimization of multi-dimensional wireless resources,the optimization of system performance cannot be achieved[36,37];4)The algorithm is complex and difficult to implement[42].

Based on addressing the above problem,this paper proposes a user-centric resource allocation method.The original problem can be broken down into the following two parts:The power control part of the access control maximizes the number of D2D user’s resources that can reuse the same spectrum resource in a single time slot while ensuring the minimum bit error rate requirement.It belongs to a mixed integer linear programming problem,which is an NP-hard problem in a general sense.Therefore,a stepwise power control algorithm is proposed to achieve a compromise between algorithm performance and complexity.Based on the above results,the time scheduling part of the time domain is ensuring the transmission of user data.Based on the transmission rate,we determine the user’s scheduling times so as to maximize the number of D2D links.It is equivalent to the convex-cardinality problem,which also belongs to the NP-hard problem,and then proposes a low-complexity heuristic algorithm.The simulation results show that the method proposed in this paper is necessary for resource optimization,and verifies the effectiveness of the proposed algorithm.

2 System Model

2.1 Network Structure

This article considers the uplink of a single-cell cellular network and assumes that the interference between cells is effectively controlled.In addition,assuming that the system has set dedicated access resources for the D2D link,there is no problem of cellular user interference to D2D users,but the same resources can be reused between D2D users,and co-channel interference will occur at this time.The set of D2D users isD={1,2,...,M},where theMrepresents the total number of D2D users.This article considers a system based on time division multiple access.The time slot structure is shown in Fig.1a.The frame is the smallest scheduling period,and each frame contains several time slots.In each time slot,multiple links simultaneously reuse the same resources for communication,as shown in Fig.1b.

For any time slot,the signal-to-interference and noise ratio SINR(Signal to Interference plus Noise Ratio)value is:

Figure 1:The proposed system model

2.2 User Demand Model

As shown in Fig.1a,assume that the time domain width of each scheduling period istf,and the frequency domain width isSf.In addition,each scheduling period can be divided into time slots,and we denote the time slots asT1,T2,...,TNf.For thei-th D2D user,it is necessary to ensure that its transmission rate is greater than the transmission threshold during the entire scheduling period,so as to ensure the user’s QoS requirements.In a single time slot,the admission control part guarantees the lowest bit error rate,that is,the lowest SINR requirement,such asi-th D2D user.If the SINR threshold value is set toΓDi,the number of times that thei-th D2D user access must meet the Eq.(2)in the scheduling period:

Among them,the vectorω=[ωi]M×1means that each D2D user needs to reuse the resources in the scheduling period to meet its transmission rate the minimum number of times;ceil(·)means the smallest positive integer not less thana.Fig.2 shows a possible scheduling result,among them,DT1and DR1,and DT2and DR1link access time slot T1,can guarantee the minimum of the above two links Bit error rate requirement(equivalent to minimum SINR threshold requirement).In the entire scheduling period,time-domain scheduling is performed according to the scheduling results to meet the user’s QoS.

2.3 Problem Description

Figure 2:D2D user access scheduling in the time domain

Define the vectorα=[αk]|F|×1Represents the number of times that the multiplexing pattern is scheduled in the entire scheduling,thenGαrepresents the total number of multiplexing resources for each D2D users in the scheduling period.Ifω−Gα≤0,it means that the rate requirement of thei-th D2D user is met in the entire scheduling period.Thenω−Gα>0 means thei-th D2D user rate requirement is not met.Therefore,the auxiliary variableq=[qi]M×1is introduced,andω−Gα≤qis introduced into the restriction condition.Among them,q=0 means the D2D user meets the speed requirement,andqi>0 means the D2D user does not meet the rate requirement.Therefore,maximizing the number of D2D users in any time slot is equivalent to minimizing the number of non-zeros in the variableq,and we can minimize the cardinality function card(q)as the optimization target value of this problem.In summary,the proposed algorithm can be described as Problem 1:

Problem 1:

Subject to:

where 11×|F|represents the row vector with all elements l;Eq.(5)indicates that the rate requirement of thei-th D2D user is met within the scheduling period;Eq.(5)indicates that the total number of time slots cannot exceedNf.

3 Joint Access Control and Time Domain Scheduling

In order to maximize the number of D2D users and minimize the number of multiplexed resources while ensuring user QoS,a joint resource allocation scheme is proposed.First,the admission control part determines the D2D user set that meets the minimum bit error rate condition in a single time slot,thereby determining the access matrixG;according to the result of admission.The time-scheduling part adjusts the resources of different time slots.In order to minimize the number of resources reused,the time-scheduling is the optimized result based on admission control.

3.1 Access Control

The purpose of the access control is to generate the multiplexing matrixG.According to the definition of the multiplexing pattern in Section 1.3,we can see that with as the number of D2D users increases,the dimension ofGwill grow exponentially.In addition,as shown in Eq.(3),compared to {1},{2},{3},the multiplexing patterns {1,2},{1,3} can make full use of the resources of each time slot.Using it as the maximum multiplexing pattern is more conducive to maximizing the number of links meeting QoS requirements in the entire scheduling period.In order to better explain the nature of the specific reuse pattern in G,we first introduce the following definitions.

Definition:Maximum reuse patternAn,wherenis the maximum number of multiplexing patterns,which meets the following two conditions:

Condition 1:iis the D2D user,i∈An;

Condition 2:For any D2D link setis satisfied.where |·|represents the collection size.

Satisfying condition 1 means that the D2D linkihas the opportunity to access the system,and satisfying condition 2 means that each time slot resource is multiplexed by the maximum number of D-L,thereby creating the most multiplexing opportunities and ensuring the maximum number of D2D link can access the system.In order to solveAn,We assume that the vectorx=[xi]M×1represents the D2D users that can be accessed in a certain time slot.Ifi-th D2D user is accessed in this time slot,xi=1;otherwise,xi=0.In order to optimize Problem 1,it is necessary to maximize the access of D2D users in any time slot.That is,maximize the sum of the elements ofx.After obtainingx,it can be integrated into matrixG,so that Problem 1 can be further optimized.According to the single time slot,in order to guarantee D2D users,the QoS of D2D users and the maximum number of access resources can be described as Problem 2:

Problem 2:

Subject to:

Eq.(7)represents thei-th D2D user upper limit of the transmitting power;represents the maximum transmitting power of thei-th D2D transmitting end.Eq.(8)represents the D2D user access resources QoS constraints;Eq.(9)indicates that thej-th D2D link has been connected to channel resources.

3.1.1 Traditional Algorithms and Drawbacks

It is easy to know that Problem 2 is a mixed integer linear programming problem,which belongs to the NP-hard problem.In the optimization theory,the branch and bound method(BB)can be used to obtain the optimal solution,but the above process requires a long calculation time[43].If the number of nodes in the traversal tree when the optimal solution is found,the complexity of the BB algorithm isThe(2M)3represents the average complexity of using the simplex method to solve the linear programming problem at any node on the traversal tree.With the increase of the problem dimensionM,βwill also increase to a certain extent,and there will be a situation ofβ→∞.However,in LTE-A,the actual deployment of the communication system,resource allocation needs to be completed in several time slots(millisecond level).Therefore,the traditional BB algorithm is not suitable for the problem considered in this article.

For the convenience of calculation,the optimization target variable of Problem 2 is transformed into thel0-norm function form that can be described as Problem 3:

Problem 3:

Subject to:

wherey=[yi]M×1,yi=1−xi.The above objective function isl0-norm that represents the number of non-zero elements in a vector.Problem 3 is a mixed integer linear programming problem,which can further transform thel0-norm function form the target variable into thel1-norm function form,which is described as Problem 4:

Problem 4:

Subject to:

Problem 4 is a linear programming problem,which can be solved by the simplex method,but the solution result is quite different from the theoretical value.

3.1.2 Progressive Access Control Algorithm

Based on the shortcomings of traditional algorithms,this paper proposes a progressive access control algorithm to reduce complexity while ensuring system efficiency and solving Problem 2.The algorithm is divided into two parts:priority access and feasibility detection.The priority access goal is to maximize the number of access links on the premise of satisfying Eq.(8),and introduce the measured value of D2D link.The goal of feasibility detection is to satisfy the Eq.(7)in Problem 2,so as to solve Problem 2 with low complexity.

a)The first part is to give priority to receiving users.jrepresents the D2D received resource,Ujrepresents the D2D user collection of the received resource,Vjrepresents the remaining D2D sets,thenUj∪Vj=D.The main idea of this part is to calculate the measured value of the D2D link one by one,and select the D2D link with the smallest measured value.The measured value of thei-th D2D link is:

b)The second part is feasibility testing.First,find the optimal transmit power of D2D link that gives priority to access resources in the first part,and determine whether its optimal transmit power satisfies Eq.(6).Secondly,if it is satisfied,it is judged whether the minimum bit error rate is satisfied.For the constraint conditions of Eq.(8),it can be expressed as:

whereprepresents the transmit power vector of D2D link;Erepresents the unit matrix modulo;

Γrepresents the diagonal matrix of the SINR threshold corresponding to the minimum QoS requirement of D2D link;Zrepresents the normalized path gain matrix between D2D users;nrepresent the normalized noise power vector.The specific definition is as follows:

From Eq.(20)to Eq.(23),it is positive and irreducible,Eq.(19)can meet the lowest QoS condition as(E−ΓZ)p≥Γn,namely:

If Eq.(24)makes sense,thenp∗=(E−ΓZ)k Γnis meaningful,that is,when the matrixΓZmaximum eigenvalueλ<1,there is a power vectorp∗,when thei-th D2D istransmit power during transmission,the lowest QoS is met,so it is deleted from one and added toUj.Whenλ≥1,thei-th D2D link does not meet the access resource conditions and is deleted fromVj.Return to the first part untilVj=Ø.

After each update ofUj,it is converted into matrixx(the process is similar toFtoG),andxis stored in matrixG.Ifx⊂G,it is not stored.After traversing allj∈D,the final access matrixGis obtained.

In summary the main steps of the proposed algorithm are shown in Algorithm 1.

Algorithm 1:A Initialization:rate requireme ccess control D2D users;maximum transmit power;minimum QoS requirements;transmission nt of each D2D and sets Uj and Vj.1:Priority to pick up 2:if Vj=Ø,3:end 4:else

images/BZ_312_2074_347_2105_393.png5:Calculate all D2D users measured values in Vj by θDi = ΓDiimages/BZ_312_1653_347_1685_393.pngimages/BZ_312_1685_391_1732_437.pngzDD i,l pD∗l +NDi +images/BZ_312_205_488_252_534.pngl∈Uj l/=i ΓDi zDD j,i pD∗i ,and select the smallest measured value.6:Feasibility test 7:Calculate the optimal transmit power for preferential access to D2D users using P∗=(E −ΓZ)−1 ΓN According to the priority access link obtained in steps 2∼5 8:if P∗< maximum transmit power 9:Calculate the maximum characteristic value λ of ΓZ 10:if λ<1,determine the D2D access link,delete it from Vj and add it to Uj to obtain the matrix representation of the set Uj,similar to the process of transforming F to G 11:Otherwise,delete it from Vj and return to Steps 2∼5 j∈Uj j/=i

3.2 Time-Domain Scheduling

The above part is coordinated by power control and interference to solve D2D access problem in a single time slot access matrixG.According to this,how to solve Problem 1 under the condition of knownGbecomes the key.But Problem 1 is a mixed-integer linear programming problem,see Theorem 1,which is an NP-hard problem in the general sense.

Theorem 1:Given the matrixG,the optimization Problem 1 is a mixed integer linear programming problem.

Proof:Problem 1 can be rewritten as Problem 5:

Problem 5:

Subject to:

Algorithm 2:Time-domain scheduling Initialization: ω matrix,delete D-L link i in ω(i)−Nf,set ω(i)=0,matrix α=[α(j)]|F|×1=0,j ∈∅1:Determine all time slots are allocated to the maximum reuse pattern 2:if all D2D user’s QoS requirements are met

3:end 4:else 5:go to step 6 6:Traverse j,select j∗=argminjμ(j),let α(j∗)=α(j∗)+1,return to steps 1∼5.

4 Simulation Results

The simulation considers a single cell with a radius of 300 m.The base station is located in the center.All cellular users and DT are evenly distributed in the cell.DR is centered on DT to form a circular area with a radius of 10–50 m.The simulation part uses The main parameter description and settings are shown in Tab.1.The entire time length is 1,000 time slots,and the MATLAB platform is used for simulation.

Table 1:Simulation parameters

4.1 Progressive Access Control

The algorithms involved in this part of the simulation include:

(1)Thel1-norm algorithm:the algorithm has low complexity but insufficient performance.

(2)Traditional BB algorithm:The theoretical optimal solution can be obtained,but exponential complexity may appear,which is difficult to apply in actual situations.

(3)Proposed access control algorithm:Aiming at the access control problem of Problem l,using the step-by-step process,determine the maximum access resources in a single time slot while ensuring the user’s lowest bit error rate.The complexity of the algorithms involved in the simulation is shown in Tab.2.

Fig.3 shows the comparison of access resources when the number of D2D users in the cell changes from 20 to 30 under the condition of 1,000 iterations.The change in the ratio of the D2D link to the total link.As the number of D2D users increases,the ratio range decreases.Because the resources required for access remain unchanged,the increase of D2D users increases the interference between systems.It can be seen from the Fig.3 that the proposed access control algorithm shows significantly better performance thanl1-norm algorithm.The proposed algorithm increases the performance by 31.2l%,which is only 4.09% lower than the BB algorithm.

Table 2:Analysis of algorithm complexity involved in simulation

?

Figure 3:Performance comparison of access control algorithms

4.2 Joint Access Control and Time Domain Scheduling

The algorithms involved in this part of the simulation include:

(1)Random algorithm:based on the access control part mentioned in this article,it is solved by random method,with low complexity but insufficient performance;

(2)Traditional BB algorithm:The theoretical optimal solution can be obtained on the basis of the access control part mentioned in this article,but exponential complexity may appear;

(3)Proposed joint access control and time-scheduling algorithm:On the basis of the access control part proposed in this paper,the heuristic algorithm proposed in the time-scheduling stage is combined to solve Problem 1.

The algorithm complexity involved in the simulation is shown in Tab.3.

Table 3:Analysis of algorithm complexity involved in simulation for Joint allocation

Fig.4 shows the system performance when number of D2D users changes from 20 to 30.The change in the ratio of the D2D link to the total number of links.As the number of D2D users increases,the ratio range decreases.Because the interference between D2D user continues to increase,the number of D2D users that can be accessed continues to decrease,resulting in missed D2D link.The number of D2D users keeps increasing,and the system performance decreases.It can be seen from the Fig.4 that the proposed joint resource allocation method is a heuristic algorithm that is close to the optimal,which is only 1.72% less than the optimal algorithm,but it is 13.03% better than the random algorithm,which reflects its effectiveness.

Figure 4:Performance comparison of the proposed joint resource allocation algorithm and existing algorithms with increasing number of D2D users

5 Conclusions and Future Recommendations

This paper analyzes the dense distribution of D2D links and proposes a user-centric joint access control and time-domain scheduling method,which solves the problem of maximizing the number of access links while ensuring the quality of D2D link service.The simulation shows that the algorithm in this paper is an approximate optimal algorithm,which achieves a compromise between algorithm performance and complexity.Further extension to this study is to consider the energy efficiency and integrate it with mmWave communication and evaluate the performance.

Acknowledgement:The author extends his appreciation to the Deanship of Scientific Research at King Khalid University for funding this work under grant number(RGP.2/25/42),Received by Fahd N.Al-Wesabi.www.kku.edu.sa.

Funding Statement:The corresponding authors Bong Jun Choi and Ehab Mahmood Mohammad would like to thank their institutes(Soongsil University,South Korea &Aswan University,Egypt)for supporting this article.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.