混合D2D蜂窝网络中基于模拟退火算法的资源调度策略

余翔，张海波，杨路

（重庆邮电大学，重庆 400065）

研究与开发

混合D2D蜂窝网络中基于模拟退火算法的资源调度策略

余翔，张海波，杨路

（重庆邮电大学，重庆 400065）

D2D通信是未来5G网络中一种近距离直通通信方式，在通信过程中，信息直接由发送端传给接收用户，而不需要经过基站的转发。在传统蜂窝网络中引入D2D通信可以极大地提升系统的总吞吐量、增大频谱资源的利用率以及降低发射终端的功耗。主要介绍了一种适用于混合D2D蜂窝网络中的资源分配方法，通过拉格朗日乘子法结合模拟退火算法实现频谱资源的分配，提出一种同时考虑信道容量和能耗的基于模拟退火算法的资源调度策略。本算法在维也纳仿真平台上经仿真验证，相比于传统贪婪优化算法，可以明显增大系统总吞吐量和频谱资源利用率。另外，算法中采用了分布式资源调度方法，D2D用户根据算法步骤自行搜索适合的目标信道并计算其发射功率，可以有效减少基站的信令开销。

D2D通信；资源分配；拉格朗日乘子法；模拟退火算法；功率控制

[3]提出了一种联合资源分配算法，通过综合考虑信道分配对网络中已有的蜂窝用户和 D2D 用户的信号干扰，寻找具有最小干扰值的信道资源分配给D2D用户，以实现有效的干扰控制，达到增大系统吞吐量的目的。参考文献[4]根据蜂窝用户和D2D链路对的最小信干噪比以及终端的门限发射功率求出D2D链路的发射功率取值范围，然后分别给出了对应的集中式和分布式解决方案。参考文献[5]使用一种贪婪算法使系统的速率达到最大，在该算法中，具有较高的信道质量指示（channel quality indicator，CQI）的蜂窝用户与具有较低信道增益的 D2D链路对共享资源，以减轻D2D用户对原蜂窝用户的干扰影响。参考文献[6]提出了一种基于博弈论的 D2D 资源分配算法，该算法通过构建使系统总干扰量最小化的非合作博弈效用函数，同时考虑系统中D2D用户间的相互干扰以及D2D用户对蜂窝用户的干扰，最后设计该博弈的潜在函数并求出潜在博弈模型的纳什均衡态。

本文采用分布式资源管理方法，提出一种基于模拟退火算法的同时考虑信道容量和能耗的资源调度策略。首先为每条D2D链路初始化一条蜂窝信道，使用拉格朗日乘子法计算出最大化信道上的吞吐量的功率解，每隔一个调度周期 T，系统进入下一个瞬态，每条D2D链路对独立的根据约束条件匹配合适的蜂窝信道，每条蜂窝信道只能被一条D2D链路对复用，然后使用拉格朗日乘子法计算出使该蜂窝信道上吞吐量达到最大时蜂窝用户与D2D发送端的发射功率。判断D2D链路上的数据率是否降低，如果是明显降低则拒绝该蜂窝信道，重新选择一条满足约束条件的蜂窝信道，如果比原分配的信道资源所得数据率增益相当，则以一定的概率接受此次匹配，如果相比于调度之前数据率有所提升，则完全接受。同时判断功率和是否有所增大，如果增大得太多或者超出门限功率值就直接拒绝，重新选择蜂窝信道；如果只有稍微增大就仍以一定的概率接受该信道；如果功率和相比于调度之前有所下降则完全接受，每一轮调度结束后，调度周期则减小一个时间值。

2 系统场景

如图1所示，假设在一个小区中存在M个蜂窝用户和N条D2D链路对，D2D链路复用蜂窝上行信道。蜂窝用户集合为D2D链路的集合为D2D对复用蜂窝上行信道进行通信，由于D2D通信条件的苛刻性，一般混合D2D蜂窝网络中D2D链路远少于蜂窝用户，即 M＞＞N。则在蜂窝用户集中至少存在一个最优解与 D2D链路集D构成共用网络，并使其总吞吐量最大化。为了保护蜂窝用户以及D2D用户的通信质量，设定以基站为中心、半径为R的区域为D2D限制区域[7]；同时，为每条D2D链路的接收端设定一个半径为 r的区域为蜂窝限制区域，即可以与该D2D链路共用信道资源的蜂窝用户不得在此区域内。

图1 D2D通信场景

3 算法分析

设定蜂窝用户的最低信干比为 sinrc，D2D链路的最低信干比为 sinrd，蜂窝用户与D2D链路的门限功率为maxP 。D2D接收端的信干噪比和基站的接收端信干噪比计算式分别如下所示：

其中，Pd、 Pc分别表示D2D对发射端的发射功率以及蜂窝用户的发射功率， Gdd表示D2D链路之间的信道增益， Gcb表示蜂窝用户与基站之间的信道增益， Gcd表示蜂窝用户与D2D接收端之间的信道增益， Gdb表示D2D发射端与基站之间的信道增益， σ2表示高斯噪声功率。由此可得出D2D发射功率的限制范围为：

从物理角度出发，距离和信道增益成反比，瑞利信道中两移动终端的信道增益与距离的计算式[8]如下所示：

其中，K、α均是由环境所决定的路径损耗常数和路径损耗指数；d表示两部终端之间的距离，λ表示两者之间服从对数分布的慢衰落增益，γ表示两者之间服从指数分布的快衰落增益。

为了减小资源分配的复杂度和同频干扰强度，先给基站以及每个D2D接收端设定一个同频最短距离 Rmin。假设基站与D2D接收端所能容忍的门限干扰分别为 IMAX和 Imax，根据蜂窝用户与D2D链路的门限干扰要求可以求得同频用户之间的门限距离分别为：

可以求得限制半径R与r分别为：

4 算法内容

4.1 拉格朗日乘子法求最优解

规定小区中每条D2D链路对能且只能匹配一条蜂窝信道，为每条蜂窝信道设置复用参数表示蜂窝信道上没有复用 D2D链路对，表示蜂窝信道上已经被D2D对复用。一条蜂窝信道 Ci可以被 D2 Dj链路复用的必要条件为：

以上是一个非凸优化的条件极值求解过程[10]，由此可以根据拉格朗日乘子法求出被复用信道上吞吐量达到最大时的功率解：

4.2 算法流程

本文在贪心算法的基础上将 D2D资源分配问题看作是马尔可夫状态转移的数学问题[11]。规定系统为稀疏 D2D蜂窝网络，且网络环境比较稳定，在一个调度周期T内，移动终端之间的信道状态信息保持不变或者变动范围很小[12]。在调度周期内，每条D2D链路自由的选取满足自身复用条件的信道资源，然后使用拉格朗日乘子法[13]结合KKT约束条件求出信道传输速率最大化的功率解。

若求解得到的数据率之和有所增长或者功率之和有所下降，则以此次调度所获取的信道资源替换最近一次的信道资源，若是本轮调度相比于最近一次所接受的信道资源更差，则根据Metropolis准则进行取舍，以一定的概率接受该信道资源作为目标信道。最后，判定调度周期是否结束，若没有结束则进行新一轮的调度，否则，进行退火处理，将调度周期减去这一轮所用的时间，并将这一轮搜索中不满足复用条件的蜂窝信道标记为不可复用信道，缩小匹配范围，重新寻找新的可复用信道，直到调度周期结束或者连续多次匹配的结果未被接受时，则退出算法。

算法中的接受概率计算如下：

具体算法步骤如下。

步骤1 初始化，系统随机为每条D2D链路初始化一条蜂窝信道。

步骤2 假令 D2 Dj的初始化信道 RBj为其目标信道RBλ，并使用式（8）计算出最优功率解,计算最大数据率之和以及功率和

步骤3 根据式（8）为 D2 Dj选择新的可复用信道 RBx，根据式（9）、式（10）计算最大化的数据率和以及功率和并按照式（11）求出概率p q、 的值。

步骤4 比较Cλ与Cx的大小，如果则进入步骤5，如果则以概率p接受信道RBx为目标信道。

步骤5 比较Pλ与xP的大小，如果xP Pλ＜ ,则进入步骤 6，如果xP Pλ＞ ，则以概率q接受信道RBx为目标信道，如果中有一个值超过门限功率，则返回步骤3。

步骤6 替换RBλ为 RBx，更新 D2 Dj的目标信道。

步骤7 判断调度周期是否结束，或者连续K次匹配的信道均未被接受，若是，则退出算法；若否，则进行退温处理，缩短周期，令T T= −并标记步骤 3中不附合条件的蜂窝信道为不可复用信道，减小搜索范围，返回步骤3。

步骤8 每条D2D链路均按照上述步骤匹配目标信道，并得到ST和共用体系的最大吞吐量CΣ。

具体流程如图2所示。

图2 具体算法流程

5 仿真结果

本文选定 LTE FDD单蜂窝小区作为仿真场景，采用LTE系统级仿真器进行验证，仿真参数见表1。

表1 仿真参数

如图 3所示，在仿真过程中经可视化处理而得到的一个半径 600 m的蜂窝小区，小区中随机布置30个蜂窝用户以及15个D2D对，D2D对处在蜂窝边缘。图 4表示本文算法与贪婪算所得系统吞吐量的对比，本文频谱资源块均作归一化处理，其中前15个编号表示被D2D复用的资源块，后10个资源块上无D2D链路复用，由图4中结果可知，未被D2D链路复用的资源块没有复用增益，数据率明显低于被复用的信道，而在被复用的信道中，基于模拟退火算法的资源调度策略可以避免陷入局部最优解，相比于贪婪算法[14]进一步提高了信道数据率。图5是频谱效率的对比结果，由图 5可知，在完全蜂窝模式下，系统的所有用户均不采用D2D通信方式，频谱效率较低且基本保持不变，而在采用 D2D通信方式的系统中，频谱效率随着D2D数目逐渐增大，说明在蜂窝网中引入D2D通信可有效提升频谱效率，而贪婪算法的频谱效率明显低于模拟退火机制的调度算法。图 6表示系统总容量的累积分布状况，本文算法虽然比贪婪算法的收敛速度慢，但是从整体上提升了系统的总吞吐量。

图3 仿真场景布置

图4 本文算法与贪婪算法所得吞吐量对比

图5 频谱效率的对比结果

图6 本文算法与贪婪算法的系统总数据率的累积分布对比

模拟退火算法的收敛周期比较慢，需要网络环境十分稳定，这是算法必要的前提条件。而混合D2D蜂窝网通常为稀疏型D2D蜂窝网，如果在此环境下基站分出额外的控制信令为其进行资源与功率分配，系统得到的收益不会太多，基站的工作成本却很大。因此，使用模拟退火算法可以有两种优势：稀疏型D2D混合网的特性保证了D2D链路在搜索最优解时有足够的解空间；该算法有效降低了基站的信令开销，本文的分布式结构，既可以保证D2D技术对蜂窝系统带来的利益，又可以避免额外的系统开销。

6 结束语

在传统蜂窝网中引入 D2D 通信技术可以有效提升系统吞吐量[15]。本文采用分布式资源管理方法，提出一种以提升系统信道容量和降低能耗为转移条件的基于模拟退火算法的资源调度策略，该算法联合考虑资源分配与功率控制，对系统内资源分配过程进行整体的优化。经仿真验证，该算法相比于传统文献中所使用的贪婪算法能进一步增大系统的总吞吐量以及资源利用率，同时，相比于贪婪算法可以增大资源块的数据率，使频谱效率得到一定的提升。

参考文献：

[1] LI Y B, GUO Z H, XU L X. Dynamic joint resource allocation for device-to-device communication based on inference control in cellular networks[J]. Fire Control & Command Control, 2016,41(1).

[2] GU J, BAE S J, CHOI B G, et al. Dynamic power control mechanism for interference coor dination of device-to-device communication in cellular networks[C]//2011 Third International Conference on Ubiquitous and Future Networks(ICUFN), June15−17, 2011, Dalian, China. New Jersey: IEEE Press, 2011:71-75.

[3] JANIS P, KOIVUNEN V, RIBEIRO C, et al. Interference-aware resource allocation for device-to-device radio underlaying cellular network[C]//VTC Spring 2009 - IEEE 69th Vehicular Technology Conference, April 26−19, 2009, Barcelona, Spain. New Jersey: IEEE Press, 2009: 1-5.

[4] RONG T, WU B, MI Z K. A resource sharing algorithm for D2D communicationwithin LTE networks[J]. Journal of Nanjing University of Posts and Telecommunications(Natural Science, 2013: 33(3).

[5] ZULHASNINE M, HUANG C C, SRINIVASAN A. Efficient resource allocation for device-to-device communication underlaying LTE Network[C]//IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications, Octember 11−13, 2010, Niagara Falls, ON, Canada. New Jersey: IEEE Press, 2010: 368-375.

[6] HYUNKEE M, JEMIN L, SUNGSOO P, et al. Capacity enhancement using an interference limited area for device-to-device uplink underlaying cellular networks[J]. IEEE Transactions on Wireless Communications, 2011, 10(12): 3995-4000.

[7] WANG H, CHU X. Distance-constrained resource-sharing criteria for device-to-device communications underlaying cellular networks[J]. Electronics Letters, 2012, 48(9): 528-530.

[8] LAN B, LI B B, LIU J, et al. Potential game resource allocation algorithm for high density D2D users[J]. Journal of South China University of Technology, 2015, 43(1): 41-46, 52.

[9] YU C H, TIRKKONEN O, DOPPLER K, et al. Power optimization of device-to-device communication underlaying cellular communication [C]//IEEE International Conference on Communications, June 14−18, 2009, Dresden, Germany. New Jersey: IEEE Press, 2009: 1-5.

[10] MARCO B, GABOR F, ANDREA A. Performance analysis of a distributed resource allocation scheme for(D2D) communications[C]//IEEE Workshop on Machine-to-Machine Communications, December 5−9, 2011, Huston, Texas, USA. New Jersey: IEEE Press, 2011: 358-362.

[11] PIRO G, GRIECO L A, BOGGIA G, et al. Simulating LTE cellular systems: an open source framework[J]. IEEE Transactions on Vehicular Technology, 2011, 60(2): 498-513.

[12] 3GPP. Selection procedures for the choice of radio transmission technologies of the UMTS: TR30.03U, version3.2.0[R]. 1998.

[13] ODUOLA W O, LI X F, QIAN L J, et al. Power control for device-to-device communications as an underlay to cellular system[C]//IEEE International Conference on Communication(ICC), June 10−14, 2014, Sydney, Australia. New Jersey: IEEE Press, 2014: 5257-5262.

[14] ZHANG B, LI Y, JIN D, et al. Social-aware peer discovery for D2D communications underlaying cellular networks[J]. IEEE Transactions on Wireless Communications, 2015, 14(5): 2426-2439. [15] YIN R, YU G D, ZHANG H Z, et al. Pricing-based interference coordination for D2D communications in cellular networks[J]. IEEE Transactions on Wireless Communications, 2015, 14(3): 1519-1532.

余翔（1969−），男，重庆邮电大学通信与信息工程学院副教授，主要研究方向为通信网及交换技术、计算机网络及信息安全和下一代网络技术。

张海波（1990−），男，重庆邮电大学硕士生，主要研究方向为D2D通信的资源分配与功率控制。

杨路（1969−），女，重庆邮电大学通信与信息工程学院高级工程师，主要研究方向为通信网及交换技术、计算机网络及信息安全、下一代网络技术。

Resource scheduling strategy based on simulated annealing algorithm in hybrid D2D cellular networks

YU Xiang, ZHANG Haibo, YANG Lu
Chongqing University of Posts and Telecommunications, Chongqing 400065, China

D2D communication is a short distance communication mode in the future 5G network. In the process of communication, the information is transmitted from the sender to the receiver directly, without the need to transmit through the base station. The introduction of D2D communication in the traditional cellular network can greatly improve the total throughput of the system, increase the utilization of spectrum resources and reduce the power consumption of the transmitter. A resource allocation method which was used in hybrid D2D cellular network was mainly introduced, spectrum resources was distributed by Lagrange multiplier method combined with simulated annealing algorithm, a consideration of channel capacity and energy consumption of the resource scheduling strategy based on simulated annealing algorithm was put forward. This algorithm was simulated by the simulation platform in Vienna, compared to the traditional greedy optimization algorithm, it can significantly increase the total system throughput and bandwidth utilization and reduce the power consumption. In addition, the distributed algorithm was adopted, that D2D users searched for a suitable target channel and calculated their transmit power according to the algorithm steps, which reduced the signaling overhead of the base station.

D2D communication, resource allocation, Lagrange multiplier method, simulated annealing algorithm, power control

TN929.5

A

10.11959/j.issn.1000−0801.2017093

1 引言

2016−10−28；

2017−03−17

国家科技重大专项基金资助项目（No.2015ZX03004004）

Foundation Item: National Science and Technology Major Project (No.2015ZX03004004)

随着现代化通信发展节奏的加快，人们对于移动通信网络传输速率的要求不断提高，而频谱资源的有限性使得传统蜂窝模式通信无法满足系统将要承载的容量需求。D2D通信是一种短距离终端直通通信方式，两部终端直接复用蜂窝资源建立连接并传输信息，无需经过基站转发，这种通信模式与传统的蜂窝模式相比，可以降低传输时延且增强可靠性[1]，此外，该模式可以有效地降低eNode B的负载压力以及提高频谱资源的利用率。目前，对于如何提高引入D2D通信的混合网络的总吞吐量以及系统的公平性成为该研究领域的一大重点[2]。