设备直通中基于组合拍卖的联合资源分配机制

董姣姣 赵季红, 唐 睿 曲 桦 朱正仓 王璐瑶 曹照鑫

1(西安邮电大学通信与信息工程学院 陕西 西安 710061)2(西安交通大学电信学院 陕西 西安 710049)

设备直通中基于组合拍卖的联合资源分配机制

董姣姣1赵季红1,2唐 睿2曲 桦2朱正仓2王璐瑶2曹照鑫2

1(西安邮电大学通信与信息工程学院 陕西 西安 710061)2(西安交通大学电信学院 陕西 西安 710049)

设备直通D2D(Device-to-Device Communication)通信是5G系统中的关键技术，通过复用传统蜂窝通信的频谱资源，能够大幅度提升系统频谱利用率，但却给传统蜂窝用户带来了同频干扰。针对上述问题，提出一种联合功率控制和信道分配的资源分配机制来最大化D2D链路的总吞吐量，并保证蜂窝链路的服务质量需求。该方案分为两步：底层功率控制考虑给定信道组合下的最大吞吐量，首先证明原问题属于凸优化，继而利用Karush-Kuhn-Tucker条件分析得到最优解；基于功率优化的结果，上层的信道分配等价于整数线性规划问题，一般意义下属于NP-hard难题，因此提出基于组合拍卖的分配机制来实现性能与复杂度之间的折中。最后，通过仿真验证了所提资源分配机制的有效性，并展示了联合无线资源分配的优势。

设备直通通信 系统吞吐量 资源分配 凸优化 组合拍卖

0 引 言

随着智能终端以及高清视频等媒体业务的快速普及，网络通信量爆炸式增长，促使新的无线通信技术的产生来进一步提高有限且日益紧张的无线频谱资源的利用率，此时设备直通D2D(Device-to-Device Communication)通信广受关注。作为5G的关键候选技术[1]，D2D通信是指一种在系统的控制下，允许邻近信道质量良好的终端用户通过复用传统蜂窝通信的频谱资源直接进行通信，而不用经过基站中转的新型通信技术。它能够增加蜂窝网络的系统频谱资源利用率，降低终端用户发射功率，因此在一定程度上可以解决无线频谱资源严重匮乏的问题。

然而，由于频带复用，D2D通信必然会给传统蜂窝通信产生同频干扰。目前，已有较多的研究关注如何协调这种同频干扰的难题。文献[2]在单信道场景下将D2D发射机作为全双工中继复用蜂窝下行链路，保证蜂窝用户最小速率的前提下采用功率控制来优化D2D链路的传输速率，但忽略了信道分配对目标性能的影响。文献[3]使用一种基于最大信干噪比的信道选择策略来观察已用信道和可用信道的总数对D2D通信的总吞吐量的影响。文献[4]在多信道多用户场景下，仅利用信道分配设计了贪婪启发式算法来优化系统吞吐量。文献[5]基于高级长期演进LTE-A(Long Term Evolution-Advanced)蜂窝系统上行链路，联合模式选择和信道分配最大化系统吞吐量。但文献[3-5]均未考虑功率控制对目标性能的影响，即忽略了单用户发射功率在多个信道上的耦合性，也未涉及保证传统蜂窝用户的性能。文献[6]联合功率控制和信道分配进行优化系统吞吐量，但文献[6]仅考虑单用户复用单信道且单信道分配单用户的简单场景，并未考虑单用户复用多信道和单信道分配多用户的场景，频谱利用率不高。然而，在容许单用户复用多信道或者单信道分配给多用户的D2D通信场景中，更能充分利用多用户分集增益以及信道复用增益来进一步降低发射功率[7]，提升系统网络的整体吞吐量[8-10]，进而降低通信时延，达到提升用户体验的目的。文献[7]引入D2D多播场景，联合信道分配和功率控制来最小化移动中继的总能耗，但未考虑频带利用率这个重要性能。文献[8-9]都是在单信道容许被多用户复用的场景下，不同的是，文献[8]联合功率控制和信道分配最大化D2D的吞吐量，文献[9]通过反向迭代组合拍卖的方式利用信道分配来优化下行链路时系统的整体吞吐量，但都没有对容许单用户复用多信道的上行链路场景的研究。文献[10]在单用户复用多信道的场景下，仅利用信道分配优化D2D链路的总效益，但忽略了功率控制对性能的影响。

基于上述分析，本文在单条D2D链路可以复用多条连续信道的LTE-A上行链路场景下，联合功率控制和信道分配来优化系统中D2D通信的总吞吐量，并保证传统蜂窝用户的最低服务质量QoS需求。该联合资源分配方案分为两步实现：第一步，给定信道组合下的功率优化，我们证明了原问题属于凸优化，并利用Karush-Kuhn-Tucker (KKT)条件求得D2D链路复用所给信道组合时的吞吐量和发射功率最优解；第二步，基于上述求到的任意D2D链路复用任意信道组合时对应的最大吞吐量和最优功率，信道分配部分的求解等价于整数线性规划问题，一般意义下仍为NP-hard难题，因此本文借助组合拍卖[11]模型，设计基于组合拍卖的贪婪启发式信道分配算法来求解D2D总吞吐量的最大值。最后，通过几种对比算法的仿真，充分验证了所提联合资源分配机制能有效提高研究场景下系统中D2D链路的总吞吐量。

1 系统模型和问题制定

(1)

(2)

(3)

其中，(a)保证了Ci的最低QoS需求；(b)是对Ci的发射功率限制；(c)和(d)表示对Dj的发射功率限制；(e)表示单条Dj只能获得Sj中的单个集合Sj|k；(f)表示Sj中的任意一个信道i只能分配给单条Dj。

2 联合资源分配机制

2.1 功率控制部分

功率控制部分在确定的信道组合下，通过优化DL和CL的发射功率来最大化DL的吞吐量。由于不同信道之间的正交性，多信道下的功率控制问题被分解成多个单信道下的功率控制问题。不失一般性，我们以Dj复用Sj|k为例，∀i∈Sj|k,j∈D，优化模型P2如式(4)所示：

(4)

(5)

(6)

(7)

(8)

(9)

2.2 信道分配部分

(10)

P4:maximizeYRTYsubjectto: AY≤eN(a) BY≤eM(b)

(11)

(11a)的意义同(3e)，表示单条DL最多可以得到单个信道集合，(11b)的意义同(3f)，表示单个信道最多也只能分配给单条DL。由式(11)可以得出，二元变量Y中的取值只能为整数0或者1，同时模型也是线性的，因此，式(11)为整数线性规划问题。由于P4和P3的等价性，因此优化问题P3也属于整数线性规划问题。

算法1 贪婪启发式信道分配算法

信道分配过程：

(5) 重复以上步骤，直到∀j∈D获得一个Sj|k包或者∀i∈Sj|k被拍卖结束。

对于所提基于组合拍卖的贪婪启发式信道分配算法，我们分析相关性质如下：

(3) 复杂性：假设信道的数量和D2D链路的数目分别为M和N个，对于详尽优化算法，一个信道有N种分配可能，因此，M个信道就有NM个可能的分配结果，算法的复杂度为O(NM)；文中所提信道分配算法需要投标者对所有可能的信道集合进行估价，信道集合的数目为1+2+…+N=N(N+1)/2，如果总的迭代次数为t，则所提算法的复杂度为O(MN(N+1)/2+t)。显然，对于数量足够多的数目M和N，有限的迭代次数t，本文所提算法具有较低复杂性。即O(NM)>Ο(MN(N+1)/2+t)。

3 仿真结果

仿真考虑一个半径为200m圆形单小区，BS在中心，所有CL和DL均匀分布在小区内，D2D用户对之间的距离随机分布在5～20m之间，其他一些参数总结见表1所示[7]。本文通过MATLAB平台进行仿真，本文对比了以下6种算法来优化系统中D2D链路的总吞吐量：1) 文献[6]中在单用户复用单信道和单信道仅分配给单用户的场景下，联合功率控制和信道分配(即参考算法1)；2)-6)均在单用户复用多信道场景下，其中，2) 为本文功率控制机制联合随机信道分配(即为D2D链路随机分配信道) (即参考算法2)；3) 为固定功率算法(即将DL的发射功率值设为固定值)联合本文信道分配机制(即参考算法3)；4) 固定功率算法联合随机信道分配(即参考算法4)；5) 本文优化问题的最优解(即参考算法5)；6) 为本文所提联合功率控制和信道分配方案(即本文算法)。其中，引入参考算法1是为了体现当单条D2D链路同时复用多个信道资源时能够得到更大的多用户分集；参考算法2-4是为了观察对比多维无线资源联合优化的优势；参考算法5是为了观察验证本文所提联合优化机制的有效性。

表1 仿真参数表

图1 D2D用户总吞吐量随蜂窝用户的SINR门限值变化

如图2所示，固定蜂窝用户的SINR门限值为15dB，观察各算法系统中D2D链路的总吞吐量随蜂窝资源数目从3增加到8时的变化曲线。从图中可以看出，随着蜂窝资源数目的增大，所有算法的系统中D2D链路总吞吐量都在增加，这是因为更多蜂窝资源即信道的加入，提供了更多的机会使D2D链路可以选择复用后性能更优的信道资源进行配对，这就使得系统中D2D链路的总吞吐量不断增大。同样可以看出，由于限制了单用户只能复用单信道，参考算法1相比于其他算法，系统中D2D链路的总吞吐量整体较低，如表2所示，在蜂窝资源数目为3和8时本文算法比参考算法1的D2D总吞吐量分别提高了139.67和96.23个百分点，而且在蜂窝资源数目达到D2D链路的数目为5时，明显的其算法的吞吐量增长缓慢，因为只是不同D2D链路的互换换来的吞吐量曲线稍微增大。相比于参考算法2、3、4，本文所提的联合优化算法充分利用单用户复用多信道的优势尽可能的提升D2D链路的整体性能增益，对应所提升的百分比如表2所示，可见本文算法比参考算法2、3、4的吞吐量提高百分比最大值分别为85.55%、47.19%、122.16%。同样，相比于参考算法5所得到的优化问题的最优解而言，本文算法的吞吐量性能有所下降，但换来的是多项式运算复杂度的降低。因此，几种算法的对比验证了本文在单用户复用多信道场景下所提的联合资源分配机制的有效性。

图2 D2D用户总吞吐量随蜂窝资源数目的变化

蜂窝资源数目/个345678本文算法吞吐量提升百分比参考算法285.5567.1856.6359.3455.9853.62参考算法3-2.008.5520.4233.7939.6747.19参考算法4122.1674.2966.7173.6474.29

4 结 语

本文在容许单用户复用多信道的场景下，提出了一种联合功率控制和信道分配的资源分配机制，同时保证传统蜂窝用户的最低QoS需求来优化系统中D2D链路的总吞吐量：功率控制部分首先证明了在任意给定信道组合下的功率控制属于凸优化，然后利用KKT条件进行求解吞吐量和功率最优解；基于上述最优信息的反馈；信道分配部分首先证明了原问题等价于整数线性规划问题，一般仍属于NP-hard难题，因此我们设计了基于组合拍卖的贪婪启发式信道分配算法来实现复杂度与性能的折中。最后，通过仿真观察了D2D链路的整体吞吐量随蜂窝用户的SINR门限值和蜂窝资源数目的变化趋势，验证了所提联合资源优化机制能有效提升系统中D2D链路的整体吞吐量。

[1]IMT-Advanced推进组,3GPP项目组.IMT-AdvancedD2D(Device-to-Device)技术白皮书v1.9.1[R].IMT-2020_3GPP_14061,2014.

[2]ZhangG,YangK,LiuP,etal.Powerallocationforfull-duplexrelaying-basedD2Dcommunicationunderlayingcellularnetworks[J].IEEETransactionsonVehicularTechnology,2015,64(10):4911-4916.

[3]HanS,KwonT,ChoiJW.AnalysisofD2DsystemperformancewithamaximalSINRchannelselectionstrategy[C]//2014InternationalConferenceonInformationandCommunicationTechnologyConvergence(ICTC).Busan,Korea:IEEE,2014:379-380.

[4]ZulhasnineM,HuangC,SrinivasanA.Efficientresourceallocationfordevice-to-devicecommunicationunderlayingLTEnetwork[C]//Proceedingsofthe2010IEEE6thInternationalConferenceonWirelessandMobileComputing,NetworkingandCommunications(WiMob).NiagaraFalls,Canada:IEEE,2010:368-375.

[5]WenS,ZhuX,ZhangX,etal.QoS-awaremodeselectionandresourceallocationschemeforDevice-to-Device(D2D)communicationincellularnetworks[C]//Proceedingsofthe2013IEEEInternationalConferenceonCommunicationsWorkshops(ICC).Budapest,Hungary:IEEE,2013:101-105.

[6] 赵季红,董姣姣,唐睿,等.蜂窝通信与设备直通通信混合网络下的资源优化[J].电信科学,2016,32(3):105-112.

[7] 王元,赵季红,唐睿,等.D2D多播场景下面向节能的资源分配机制[J].西安电子科技大学学报(自然科学版),2016,43(2):162-167.

[8]TangR,ZhuangX,DongJ,etal.ThroughputmaximizationforDevice-to-Devicecommunicationsunderlayingcellularnetworkviajointresourceallocation[C]//Proceedingsofthe2015 2ndInternationalConferenceonCommunicationTechnology(ICCT),2015:191-199.

[9]XuC,SongL,HanZ,etal.EfficiencyresourceallocationforDevice-to-Deviceunderlaycommunicationsystems:areverseiterativecombinatorialauctionbasedapproach[J].IEEEJournalonSelectedAreasinCommunications,2013,31(9):348-358.

[10]ZhangJ,WuG,XiongW,etal.Utility-maximizationresourceallocationfordevice-to-devicecommunicationunderlayingcellularnetworks[C]//Proceedingsofthe2013IEEEGlobecomWorkshops,2013:623-628.

[11]ShohamY,Leyton-BrownK.Multiagentsystems:algorithmic,game-theoretic,andlogicalfoundations[M].NewYork:CambridgeUniversityPress,2009:361-377.

JOINT RESOURCE ALLOCATION SCHEME BASED ON COMBINATORIAL AUCTION MODEL FOR DEVICE-TO-DEVICE COMMUNICATION

Dong Jiaojiao1Zhao Jihong1,2Tang Rui2Qu Hua2Zhu Zhengcang2Wang Luyao2Cao Zhaoxin2

1(SchoolofTelecommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710061,Shaanxi,China)2(SchoolofElectronicsandInformationEngineering,Xi’anJiaotongUniversity,Xi’an710049,Shaanxi,China)

Device-to-Device (D2D) communication is a key technology in 5G system, and it can greatly improve the spectral efficiency by reusing the spectrum resources of traditional cellular communication, but it brings the co-channel interference to the traditional cellular users. Aiming at the above problem, a resource allocation mechanism combining joint power control (PC) and channel assignment (CA) is proposed to maximize the aggregate throughput of D2D links and guarantee the quality of service requirement of cellular links. The mechanism is divided into two steps. Considering the maximum throughput of a given channel assignment, the lower-layer PC first proves that the problem belongs to convex optimization, and then uses Karush-Kuhn-Tucker conditions analysis to get the optimal solution. Based on the results of power optimization, the upper-layer CA belongs to the integer linear programming, which is NP-hard in the general sense. Therefore, the allocation mechanism based on combination auction is proposed to realize the trade-off between performance and complexity. Finally, the effectiveness of the resource allocation mechanism is verified by simulation, and the advantages of joint wireless resource allocation are showed.

D2D communication System throughput Resource allocation Convex optimization Combinatorial auction

2016-03-03。国家自然科学基金项目(61372092)；国家高技术研究发展计划项目(2014AA01A706)。董姣姣，硕士生，主研领域：D2D通信等。赵季红，教授。唐睿，博士生。曲桦，教授。朱正仓，硕士生。王璐瑶，硕士生。曹照鑫，博士生。

TP393

A

10.3969/j.issn.1000-386x.2017.04.021