2. 西安交通大学电子与信息工程学院, 陕西 西安 710049;
3. 西安科技大学计算机科学与技术学院, 陕西 西安 710054;
4. 西安电子科技大学电子工程学院, 陕西 西安 710071
2. School of Electronics and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China;
3. School of Computer Science, Xi'an University of Science and Technology, Xi'an 710054, China;
4. School of Electronics Engineering, Xidian University, Xi'an 710071, China
1 引言
随着人们生活方式的改变，高速近距离通信的需求呈现指数性增长[1]，设备直通 (device-to-device，D2D) 通信应运而生，其被看作是下一代无线通信系统 (5G) 中的关键技术之一[2-4].D2D带来了新的通信模式，使得数据链路在设备间直接建立，而无需通过基站中继.这样能够有效利用邻近通信对之间良好的信道环境提高频带利用率，降低基站负载，增加用户传输速率、减小端到端时延.此外，如图 1所示，D2D还能激发新的应用场景，包括移动中继协作传输[5]、D2D多播/广播[6]及可靠的车联网[7].正因为上述优势，D2D通信受到了3GPP (the 3rd Generation Partnership Project) 等标准化组织的关注[8-9]，特别是如何在当前高级长期演进 (long term evolution-advanced，LTE-A/4G) 蜂窝网络中进行部署.
|
| 图 1 D2D通信潜在的应用场景 Figure 1 Potential application scenario of D2D communication |
然而，由于复用传统蜂窝网络的频带资源，蜂窝链路 (cellular link，CL) 与D2D链路 (D2D link，DL) 之间会产生严重的同频干扰[2-7]，图 2展示了D2D通信分别复用蜂窝网络上、下行频带资源时的干扰情形.为了有效降低上述同频干扰，D2D通信中资源分配方案的设计至关重要[10-15].文[10]考虑了单条CL和单条DL的复用场景，在固定发射功率的情况下分析了DL发射端到CL接收端的最小距离，从而满足CL的中断概率约束.文[11]考虑了多用户场景，通过信道分配优化系统的整体吞吐量，文[12]同样考虑了上述问题，但其将信道分配转化为二分图中的最大匹配问题，继而可以借助Kuhn-Munkres算法得到最优解，而文[11]借助贪婪算法在较低的复杂度下同样得到了较好的性能.文[13]在文[11-12]的基础上引入了功率控制，保证了CL的服务质量需求 (quality-of-service，QoS).但是文[10-13]都假设单条DL仅仅能够复用单条CL的信道资源，这大大限制了DL的传输速率，因此文[14-15]去除了上述约束，其中文[14]在LTE-A下行联合信道分配和功率控制最大化DL的整体吞吐量并保证传统CL的QoS需求，但是LTE-A下行使用的正交频分复用多址技术会产生高峰值平均功率比，大幅度地降低了发射端的能效，故不利于在用户终端使用.除此之外，蜂窝网络上行通信量远低于下行，导致上行频带利用率严重不足.因此，LTE-A上行更适于D2D通信的部署，但是单载波频分复用多址技术要求分配给单用户的信道资源必须是连续的[15].在上述约束下，文[15]同样联合功率控制和信道分配最大化系统吞吐量，但是其忽略了单用户发射功率在多个信道上的耦合性，从而影响了优化目标的提升.
|
| 图 2 混合蜂窝网络中的同频干扰情形 Figure 2 Co-channel interference in the hybrid cellular networks |
综上所述，已有文[10-15]存在以下3方面不足：(ⅰ) 单用户仅仅能够复用单条CL的信道资源[10-13]；(ⅱ) 仅仅考虑了信道分配，忽略了CL的QoS需求[11-12]或者没有充分联合发射功率和信道分配这两类优化变量[15]；(ⅲ) 没有考虑在LTE-A上行传输的特殊性[14].针对上述不足，本文旨在LTE-A上行最大化DL的总体吞吐量，于此同时保证CL的最低QoS需求，即在不影响已有蜂窝通信的前提下最大化系统频带利用率.但是，上述问题属于混合整数非线性规划，具有较高的复杂度.利用功率控制变量与信道分配变量间的正交性，本文将其分解为相应的两个子问题，其中功率控制部分可以借助凸优化理论分析，而在上述最优解的基础上，信道分配部分等价于经典的集合划分问题 (set partitioning problem，SPP)，其一般意义下属于NP-hard (non-deterministic polynomial-time hard) 问题.本文继而设计了一种多项式时间复杂度的贪婪信道分配算法来满足实际部署需求.仿真结果表明，本文所提方案优于文[11-13, 15]方案，而且实现了算法性能和复杂度的折中.
2 系统模型和问题制定假设小区间干扰已经得到了控制[16]，本文仅仅分析单小区场景.记上行CL和DL的集合为C={1，2，…，N}和D={1，2，…，M}，其中N和M分别代表各自集合内的元素总数.假定CL的资源分配已经完成，本文考虑满负荷的情况，即信道数目等于CL数目.另外，为了便于表示，假定各个上行信道的标识与其上分配的CL标识相同.在上述混合网络中，单条DL容许复用多个上行信道资源来利用多用户分集 (multiuser diversity)，提升其传输速率.而为了避免强干扰以及繁重的信令开销[17]，单个上行信道仅能够被单条DL复用[10-15].对于第i条DL而言，记其复用的信道集合为Si，在LTE-A蜂窝网络上行，由于单用户所用信道的连续性约束，总共有
|
(1) |
(ZN)N=3={∅，{1}，{2}，{3}，{1，2}，{2，3}，{1，2，3}}.如图 2所示，DL1和DL2复用的CRP为S1={1}和S2={2，3}，分别对应于式 (1) 中的第2列和第6列.本文采用信干噪比 (Signal-to-Interference-plus-Noise Ratio，SINR) 简化用户的QoS感受[11-15]，如式 (2) 和式 (3) 所示，第j个信道上DL和CL的SINR可分别定义为γi，jD和γjC：
|
(2) |
|
(3) |
其中，GiD和GjC分别表示上述两条链路中有用信号的路径增益，类似于文[11-15]，其包括与传输距离相关的路径损耗、阴影 (大尺度) 衰落及多径 (小尺度) 衰落.类似地，Gi，jDC和Gj，iCD分别表示从CL发射端到DL接收端及从DL发射端到CL接收端 (基站) 的路径增益.σiD和σjC分别表示上述两条链路接收端的背景噪声.此外，pi，jD≥0表示第i条DL在第j个信道上的发射功率，DL发射端的总发射功率受到pi，maxD约束，即
|
(4) |
|
(5) |
借助香农公式得到上述两条链路在第j个信道上的归一化传输速率Ri，jD和RjC，因此，第i条DL的总归一化传输速率为
基于以上的假设和表示，本文中所要解决的联合信道分配和功率控制问题可以表示为问题1(P1)，如式 (6) 所示，即通过优化功率控制变量pi，jD≥0和信道分配变量Si，在保证CL最低SINR需求的前提下最大化DL链路的总归一化总传输速率：
|
(6) |
其中，式 (c1) 和式 (c2) 表示信道复用约束，即分配给所有DL的信道组合是整个信道资源的一个划分，式 (c3) 表示DL发射端的发射功率上限约束，而式 (c4) 则是保证CL链路的最低SINR需求.由优化理论可知，P1为混合整数非线性规划，属于NP-hard问题.
3 联合信道分配和功率控制在P1的优化目标
|
(7) |
|
(8) |
对于任意给定的第i条DL及相应的CRPSi∈ZN，优化问题P2的最优解可以归纳为定理1.
定理1 P2是关于功率变量pi，jD，∀j∈Si的凸问题，其最优解可以分为两种情况：(a) 若
证明 如式 (9) 和式 (10) 所示，通过求解P2中优化目标
|
(9) |
|
(10) |
|
(11a) |
|
(11b) |
|
(11c) |
|
(11d) |
|
(11e) |
其中，L(pi，jD，λiD，ui，j，vi，j) 为P2的拉格朗日函数，λiD、ui，j、vi，j分别是与各个约束条件相关联的拉格朗日乘数.如果
对于带有约束条件的凸优化问题，一般可以采用障碍法求取最优解[15]，但是注意到当
为了保证论文的完整性，此处进一步给出第i条DL对集合Si中蜂窝上行链路造成干扰的条件.考虑下列问题：
|
(12) |
即在优化DL性能的同时不考虑其对于集合Si中传统蜂窝链路的影响.很容易验证上述问题仍属于凸优化问题，继而可以借助KKT条件得到最优发射功率，如式 (13) 所示：
|
(13) |
其中，νiD+表示与式 (12) 中约束条件 (c3) 相关联的拉格朗日乘数的最优值.类似于P2，其同样可以借助二分法及
|
(14) |
说明对于第i条DL的优化不会影响到集合Si中传统蜂窝链路的性能，否则就需要借助定理1对P2进行求解，即在不影响已有蜂窝通信的前提下最大化系统频带利用率.
3.2 信道分配部分通过上一节单条DL处功率控制得到了P3中所有Ri，SiD，sum*=Ri，SiD，sum*(pi，jD*)，∀i∈D，Si∈ZN，为求解Si*，∀i∈D，接下来首先对P3的特性进行了分析，结论如定理2所示.
定理2 在给定Ri，SiD，sum*，∀i∈D，Si∈Y的情况下，优化问题P3属于优化理论中的SPP.
证明 首先引入新的二元变量[yi]L×1，∀i∈D代替Si，∀i∈D，其为L×1的列向量，如果Si对应于XN×L中的第t个CRP，则其第t个元素yit=1，否则yit=0.另外，记所有[yi]L×1，∀i∈D按列合并后的二元向量为[y](M×L)×1，即[y](M×L)×1=[y1T，y2T，…，yMT]T，对应于[y](M×L)×1，记Ri，SiD，sum*，∀i∈D，Si∈Y相应的列向量为[r](M×L)×1.因此如式 (15) 所示，P3可以等价地转化为以[y](M×L)×1为优化变量的问题4(P4)：
|
(15) |
其中，式 (c5) 中的A=[X，X，…，X]N×(M×L)是M个XN×L按行合并后的二元矩阵，而eN是全1的N维列向量，因此该约束表示每个信道都唯一的分配给一个CRP.另外，式 (c6) 约束单个DL仅仅能够分配到一个CRP，通过简单的数学变换，可以将其等价的转化为By=eM，其中BM×(M×L)是一个特殊的M×M对角矩阵，其对角元素为全1的L维行向量，即eLT.最终，P4可以简化为
|
其中C=[A；B](N+M)×(M×L)为二元矩阵AN×(M×L)和BM×(M×L)合并为的结果，而eN+M是全1的N+M维列向量，因此P4为优化理论中经典的SPP，由于P4与P3的等价性，P3同样属于SPP.证毕.
在优化理论中，SPP属于整数线性规划，一般意义下为NP-hard难题，可以借助分支界限法 (branch-and-bound，BB)[19]得到最优解，但是上述过程需要较长的计算时间，如果用β表示当找到最优解时在遍历树上途径的节点数目，则BB算法的复杂度为O(MLIbis+β(ML)3)，其中，Ibis表示利用第2.1节二分法计算最优功率变量时所需的最大迭代次数，则MLIbis表示得到P4优化目标中权值向量[r](M×L)×1的复杂度，而 (ML)3表示利用单纯形法 (simplex method)[20]求解遍历树上任意节点处线性规划问题的平均复杂度.随着问题维度ML的增大，β也会一定程度的增加，而且会出现β→∞的情况.然而在LTE-A通信系统的实际部署中，资源分配需要在若干个时隙内 (毫秒级) 完成，因此BB机制并不适用于本文所考虑的问题.如表 1所示，本节展示一种多项式时间复杂度的贪婪信道分配算法，大幅度地降低复杂度，同时保证较好性能.
| 初始化H={1，2，…，N}表示未被分配的信道集合；Si表示分配给第i条DL的信道集合，并初始化Si=∅，∀i∈D；Ti表示在连续性约束下第i条DL当前可接入的信道集合，并初始化Ti=H={1，2，…，N}，∀i∈D. |
步骤1 对于Ti≠∅的DL，即A={k∈D|Tk≠∅}中每条DL，借助2.1节功率控制部分对Ti中每个信道元素计算测度值 .
步骤2 在步骤1所有计算出的测度值中找到最大值，即确定  ，将第k*个信道分配给第i*条DL，并更新Si*=Si*∪{k*}，H=H-{k*}，如果测度值中出现多个相同的最大值，则在其中随机选择一个.
步骤3 如果H=∅，则算法结束；否则更新Ti：(a) 如果Si=∅，Ti=H，(b) 否则Ti=(∪j∈SiW(j))∩H，其中W(j) 表示{1，2，…，N}中与第j个信道相邻的信道，返回步骤1. |
本文所提贪婪信道分配算法逐个分配当前剩余信道，在每次循环中，首先 (步骤1)，借助第2.1节功率控制部分确定结合A={k∈D|Tk≠∅}中不同DL对优化目标的贡献
本文借助Matlab仿真工具，考虑半径为200 m的圆形单小区，基站位于小区中心，所有链路的发射端在圆形区域内随机分布，DL的接收端均匀分布在以其对应发射端为中心且半径为5 m到20 m的环形区域内.后续仿真中主要参数的设定如表 2所示.特别地，与文[11-15]相同，本文中所有的路径增益包括与传输距离相关的路径损耗、阴影 (大尺度) 衰落及瑞利多径 (小尺度) 衰落.本节对比了7种算法：
| 仿真参数 | 设定值 |
| 天线类型和天线增益 | 全向 (基站和终端)，14 dBi (基站)/0 dBi (用户终端) |
| 系统中CL数目 | 20 |
| 资源块带宽 | 180 kHz |
| 背景噪声 | -174 dBm/Hz |
| 接收端噪声系数 | 5 dB (基站)/9 dB (用户终端) |
| CL发射功率 | 开环部分路径补偿算法[12] |
| DL最大功率 | pi，maxD=20 mW，∀i∈D |
| CL距离相关的路损模型[12-16] | 128.1+37.6ln d，其中d表示链路发射端到接收端距离 (单位：km) |
| DL距离相关的路损模型[12-16] | 148+40ln d，其中d表示链路发射端到接收端距离 (单位：km) |
| 衰落模型[12-16] | 标准方差为8 dB的阴影 (大尺度) 衰落及瑞利多径 (小尺度) 衰落 |
(ⅰ) 算法1：文[13]中的联合信道分配和功率控制，其中，单个DL最多只复用一个CL的信道，在功率控制最优解的基础上，信道分配等价于分配问题[21]，可以借助匈牙利算法或者Kuhn-Munkres算法[21]得到最优解，其性能优于文[11-12]中单一的信道分配机制.
(ⅱ) 算法2：随机信道分配结合本文第2.1节所提的功率控制.
(ⅲ) 算法3：采用文[15]中的功率控制，忽略了pi，jD，∀j∈Si在Si上各信道之间的耦合性，即pi，jD=min{(pjCGjC/θjC-σjC)/Gj，iCD，pi，maxD/N}，∀j∈Si，而信道分配采用本文中的贪婪算法.
(ⅳ) 算法4：把算法3中的信道分配部分利用BB机制求解，即得到算法3的性能上限.
(ⅴ) 算法5：本文所提的联合信道分配和功率控制机制.
(ⅵ) 算法6：在本文第2.1节功率控制的基础上，利用BB机制求解最优的信道分配，即得到算法5的性能上限.
(ⅶ) 算法7：文[14]中的联合资源分配机制，即忽略了LTE-A上行信道分配中的连续性约束，上述机制可以在多项式时间内趋近最优解，其算法的时间复杂度为O(I1(I2ML))，其中I2表示内层循环收敛所需的迭代次数 (在固定拉格朗日乘数下求解最优的DL发射功率并借助子梯度法拉格朗日乘数1)，而I1表示外层循环收敛所需的迭代次数 (借助二分法更新拉格朗日乘数2)，具体细节可参考文[14]，此处不再赘述.但需要强调，子梯度法目前还没有很好的收敛判断条件，因此，需设置较大的I2来保证优化性能.
最后，表 3列出了所有对比算法的时间复杂度.在仿真中观察优化目标
| 算法标识 | 时间复杂度 |
| 算法1 | O(MNIbis+max{M，N}3) |
| 算法2 | O(MIbis) |
| 算法3 | O(ML) |
| 算法4 | O(ML+β(ML)3) |
| 算法5 | O(MLIbis) |
| 算法6 | O(MLIbis+β(ML)3) |
| 算法7 | O(I1(I2ML)) |
|
| 图 3 DL归一化的总传输速率随着DL数目的变化 Figure 3 Performance variation of aggregate throughput with change in the number of requesting DLs |
|
| 图 4 DL归一化的总传输速率随着CL最低SINR需求的变化 Figure 4 Performance variation of aggregate throughput with change in minimum SINR requirements of CLs |
首先分析DL吞吐量随着参数变化的整体趋势，如图 3所示，随着M的提升，系统中可利用的多用户分集增加，所有算法的性能都会得到提升.另外，如图 4所示，随着θjC，∀j∈C的增大，由式 (3) 可知单信道上DL可使用的发射功率减小，从而导致所有算法的性能下降.综合图 3和图 4可以看出：(ⅰ) 相比于算法1，其它算法容许单条DL复用多条信道资源，一定程度上更好地利用了多用户分集，从而贡献了更高的性能.但是从图 3中注意到，当M较大时 (M=14)，算法1的性能优于算法3和算法4，原因在于算法1中DL在单信道上的功率上限远远大于算法3和算法4
本文在部署D2D通信的LTE-A通信系统上行，联合信道分配和功率控制最大化DL的整体传输速率同时保证已有蜂窝链路的QoS需求，此外，本文容许单条DL复用多条信道并考虑了LTE-A通信系统上行信道分配中的连续性约束.考虑到功率控制变量与信道分配变量间的正交性，本文将其分解为功率控制和信道分配两个子问题，其中功率控制部分可以通过凸优化理论分析得到最优解，而信道分配部分则等价于经典的SPP，本文继而设计了一种多项式时间复杂度的贪婪算法来满足实际部署的需求.特别地，功率控制部分得到的最优解将反馈给信道分配部分，协助信道分配问题的分析和求解，体现了联合资源优化的思想.仿真结果观察了联合资源分配的优势并验证了所提算法的有效性.
为了更好地适应下一代移动通信系统/5G中的个性化需求，在后续的研究中还会考虑面向用户公平性，比如最大化最差链路性能，能耗及能效的资源分配机制.其次，在场景方面还需要考虑移动中继协助下的D2D通信场景及全双工传输；此外，在实现方式上还应该考虑性能与实现复杂度和信令开销之间的折中关系，设计半分布式机制及完全分布式机制.
| [1] | Cisco, White Paper. Cisco visual networking index:Global mobile data traffic forecast update, 2014-2019[EB/OL]. 2015-02-03/2015-02-03. http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white_paper_c11-520862.pdf. |
| [2] | Osseiran A, Boccardi F, Braun V, et al. Scenarios for 5G mobile and wireless communications:The vision of the METIS project[J]. IEEE Communications Magazine, 2014, 52(5): 26–35. DOI:10.1109/MCOM.2014.6815890 |
| [3] | Wang H C, Chen S Z, Xu H. SoftNet:A software defined decentralized mobile network architecture toward 5G[J]. IEEE Network Magazine, 2015, 29(2): 16–22. DOI:10.1109/MNET.2015.7064898 |
| [4] | Chen S Z, Zhao J. The requirements, challenges and technologies for 5G of terrestrial mobile telecommunication[J]. IEEE Communications Magazine, 2014, 52(5): 36–43. DOI:10.1109/MCOM.2014.6815891 |
| [5] | Tang R, Zhao J H, Qu H. Joint mode selection and resource allocation for mobile relay-aided device-to-device communication[J]. KSⅡ Transactions on Internet and Information Systems, 2016, 10(3): 950–975. |
| [6] | 王元, 赵季红, 唐睿. D2D多播场景下面向节能的资源分配机制[J]. 西安电子科技大学学报, 2016, 43(2): 162–167. Wang Y, Zhao J H, Tang R. Energy-aware resource allocation for underlaid D2D multicast[J]. Journal of Xidian University, 2016, 43(2): 162–167. |
| [7] | 刘伎昭, 王泉. 车载自组网中联盟博弈的虚假数据检测策略[J]. 西安交通大学学报, 2015, 49(2): 69–73. Liu J Z, Wang Q. A false data detecting scheme based on coalition game for vehicular ad hoc networks[J]. Journal of Xi'an Jiaotong University, 2015, 49(2): 69–73. DOI:10.7652/xjtuxb201502012 |
| [8] | Lin X Q, Andrews J G, Ghosh A. An overview of 3GPP device-to-device proximity services[J]. IEEE Communications Magazine, 2014, 52(4): 40–48. DOI:10.1109/MCOM.2014.6807945 |
| [9] | 3GPP. 3GPP, TR36.843:3rd generation partnership project; Technical specification group RAN; Study on LTE device to device proximity services-radio aspects (Release 12)[R]. Valbonne, France:3GPP support office, 2014. |
| [10] | Wang H F, Chu X Y. Distance-constrained resource sharing criteria for device-to-device communications underlaying cellular networks[J]. Electronic Letters, 2012, 48(9): 528–530. DOI:10.1049/el.2012.0451 |
| [11] | Zulhasnine M, Huang C, Srinivasan A. Efficient resource allocation for device-to-device communication underlaying LTE network[C]//Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communication. Piscataway, NJ, USA:IEEE, 2010:368-375. |
| [12] | Han J, Cui Q M, Yang C C. Bipartite matching to optimal resource allocation in device to device underlaying cellular network[J]. Electronic Letters, 2014, 50(3): 212–214. DOI:10.1049/el.2013.2378 |
| [13] | Feng D Q, Lu L, Wu Y Y. Device-to-device communications underlaying cellular networks[J]. IEEE Transactions on Communications, 2013, 61(8): 3541–3551. DOI:10.1109/TCOMM.2013.071013.120787 |
| [14] | Zhu D H, Wang J H, Swindlehurst A L. Downlink resource reuse for device-to-device communications underlaying cellular networks[J]. IEEE Signal Processing Letters, 2014, 21(5): 531–534. DOI:10.1109/LSP.2014.2309143 |
| [15] | Wen S, Zhu X Y, Zhang X. QoS-aware mode selection and resource allocation scheme for device-to-device (D2D) communication in cellular networks[C]//Proceedings of IEEE International Conference on Communications. Piscataway, NJ, USA:IEEE, 2013:101-105. |
| [16] | 杨阳, 廖学文, 高贞贞. 多小区终端直通异构网络中利用图论的资源分配方案[J]. 西安交通大学学报, 2014, 48(10): 22–28. Yang Y, Liao X W, Gao Z Z. A resource allocation scheme using graph theory for D2D communication in multi-cell heterogeneous cellular networks[J]. Journal of Xi'an Jiaotong University, 2014, 48(10): 22–28. DOI:10.7652/xjtuxb201410004 |
| [17] | Tang R, Dong J J, Zhu Z C. Resource allocation for underlaid device-to-device communication by incorporating both channel assignment and power control[C]//Proceedings of International Conference on Communication Systems and Network Technologies. Piscataway, NJ, USA:IEEE, 2015:432-436. |
| [18] | Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge, UK: Cambridge University Press, 2004. |
| [19] | Boyd S, Mattingley J. Branch and bound methods[R]. Stanford, CA, USA:Stanford University, 2007. |
| [20] | Vanderbei R J. Linear programming:Foundations and extensions[M]. NY, USA: Springer, 2008. |
| [21] | Kuhn H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics, 2005, 52(1): 7–21. DOI:10.1002/(ISSN)1520-6750 |