引入D2D通信的蜂窝网上行资源分配算法

程永生 朱 江 林孝康



引入D2D通信的蜂窝网上行资源分配算法

程永生*朱 江 林孝康

(清华大学电子工程系 北京 100084)

该文研究了引入Device-to-Device (D2D)通信的蜂窝网系统中的上行资源分配问题。首先将该问题建模为一个简洁的二值整数规划问题。然而整数规划仍是NP难问题。该文利用Canonical对偶理论，得到其对偶形式。该对偶问题是一个连续域内的凸问题。证明了在特定的条件下，可以通过求解对偶问题得到原问题的最优解，且对偶间隙为零。提出了一个基于Barrier方法的算法来求解对偶问题。仿真结果表明，该文的算法优于现有算法，且性能接近最优。

D2D通信；资源分配；整数规划；Canonical 对偶

1 引言

文献[11-13]讨论了引入D2D通信后的信道分配问题。为了减小信道复用带来的干扰，文献[11,12]假设每个信道最多被两个用户复用，并分别提出了贪婪算法进行信道分配。在文献[13]中，作者假设已先将信道分配给蜂窝网用户，然后将D2D用户信道复用建模为一个混合整数优化问题，利用列生成算法给出一个次优求解方法。文献[14]研究了单载波(Single-Carrier, SC) FDMA系统中的上行信道分配。作者假设每个信道上的发射功率相等，然后将信道分配问题转化为一个等式约束的二值整数规划(Binary Integer Programming, BIP)问题。然而，BIP仍然是NP难问题，最差情况下的求解复杂度与问题的规模成指数关系。利用近来提出的Canonical对偶理论[15]，文献[14]的作者沿用文献[16,17]中的方法，将等式约束松弛为不等式，进一步得到其对偶问题进行求解。

本文首先将D2D系统中的信道分配问题建模为一个BIP问题。基于Canonical对偶理论[15]，本文将该BIP问题转化为一个连续域内的凹函数最大化问题。因此可以利用内点法等凸优化方法在多项式时间内求解[18]。同时，本文给出了最优解的条件。在该条件下，可以通过求解Canonical对偶问题得到原问题的全局最优解。与文献[14,16,17]不同，本文方法不需要将等式约束松弛为不等式约束，因此可以得到更宽松的最优解条件。另外，本文提出了一个基于Barrier方法[18]的算法，用于求解对偶问题。仿真结果表明，本文方法的性能明显优于文献[14]的算法。

2 系统模型

图1 D2D系统信道分配示例图

其中，式(1)表明每个用户在同一时刻只使用一个信道。不等式(2)表示用户实现通信所需的最小SINR约束。式(3)的第1部分保证同小区的蜂窝网用户间不共用信道；第2部分表示允许D2D用户复用信道，但每个信道最多被两个用户复用。

其中，的每一列代表一个可行的分配方案，每一行对应一个用户。列数为

3 Canonical 对偶方法求解资源分配问题

本节使用Canonical对偶方法求解上述资源分配问题。将证明当满足一定条件时，可以通过求解对偶问题得到原问题的最优解。然后给出一个基于Barrier方法[18]的算法来求解对偶问题。

3.1 Canonical对偶函数及最优解条件

定义指示函数为

引入全互补函数(total complementary function)：

将式(6)代入式(5)，可以得到对偶问题：

将

代入式(7)和式(8)，可以得到

证明过程与文献[17]中Theorem 3.(a)的证明类似(略)。

3.2基于Barrier方法的求解算法

4 仿真结果

考虑系统带宽为10 MHz，中心频率为2 GHz。上行频谱资源被均分为=10个信道。有c=8个上行蜂窝网用户和d=7个上行D2D用户在系统中随机均匀分布。同时，D2D接收用户均匀分布于相应的上行D2D用户周围100 m的距离内。用户之间以及用户与基站之间的链路相互独立，且服从瑞利平衰落。具体的参数如表2所示。

表1 基于Barrier方法的求解算法

表2仿真参数

图3给出了在不同的上行D2D用户数目d情况下，系统的平均和速率。其他参数与图2相同。从图3中可以看到，一方面，随着D2D用户数的增加，系统和速率有增长的趋势。这是由于当系统中存在更多的短距离D2D链路时，可以获得更好的频率复用效果。该结果说明了允许短距离D2D链路复用蜂窝网资源的好处。另一方面，可以看到，本文算法的结果优于文献[14]中的方案以及贪婪算法得到的结果。并且，在不同的D2D用户数的情况下，本文算法的结果与最优解的性能都非常接近。

5 结论

基于Canonical对偶理论，本文将引入D2D通信的蜂窝系统中的上行资源分配问题转化为一个连续域内的凸优化问题。因此可以利用凸优化算法在多项式时间内求解。文中给出了通过对偶问题得到原问题最优解的条件。并提出了一个基于Barrier方法的算法来求解对偶问题。通过仿真发现，本文算法的结果优于对比算法，且在大部分情况下可以得到原问题的全局最优解。

图2 系统和速率累积分布函数曲线

[1] Doppler K, Rinne M, Wijting C,.. Device-to-device communication as an underlay to LTE-advanced networks[J]., 2009, 47(12): 42-49.

[2] Fodor G, Dahlman E, Mildh G,.. Design aspects of network assisted device-to-device communications[J]., 2012, 50(3): 170-177.

[3] Lei L, Zhong Z D, Lin C,.. Operator controlled device-to- device communications in LTE-advanced networks[J]., 2012, 19(3): 96-104.

[4] Lin X Q, Andrews J G, Ghosh A,.. An overview on 3GPP Device-to-Device proximity services[OL]. http://arxiv. org/abs/1310.0116. 2013.

[5] Osseiran A, Monserrat J F, and Mohr W. Mobile and Wireless Communications for IMT-advanced and Beyond[M]. United Kingdom: Wiley, 2011: Chapter 9.

[6] Yu C, Doppler K, Ribeiro C B,.. Resource sharing optimization for Device-to-Device communication underlaying cellular networks[J]., 2011, 10(8): 2752-2763.

[7] Dong H L, Kae W C, Wha S J,.. Resource allocation scheme for device-to-device communication for maximizing spatial reuse[C]. IEEE Wireless Communications and Networking Conference, Shanghai, 2013: 112-117.

[8] Cheng Y S, Han H, and Lin X K. Device-to-Device communication in CDMA-based cellular systems–uplink capacity analysis[C]. IEEE 3rd International Conference on Communication Software and Networks, Xi’an, 2011: 430-434.

[9] Chiang M, Tan C W, Palomar D P,.. Power control by geometric programming[J]., 2007, 6(7): 2640-2651.

[10] Kha H H, Tuan H D, and Nguyen H H. Fast global optimal power allocation in wireless networks by local D.C. programming[J]., 2012, 11(2): 510-515.

[11] Cheng Y S, Gu Y T, and Lin X K. Power and channel allocation for Device-to-Device enabled cellular networks[J]., 2014, 10(2): 1-10.

[12] Zulhasnine M, Changcheng H, and 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, Niagara Falls, 2010: 368-375.

[13] Phunchongharn P, Hossain E, and Kim D I. Resource allocation for device-to-device communications underlaying LTE-advanced networks[J]., 2013, 20(4): 91-100.

[14] Ahmad A and Assaad M. Polynomial-complexity optimal resource allocation framework for uplink SC-FDMA systems[C]. Proceedings of IEEE Globecom, Houston, 2011: 1-5.

[15] Gao D Y. Duality Principles in Nonconvex Systems: Theory, Methods, and Applications[M]. Boston: Kluwer Academic Publishers, 2000: Chapter 5.

[16] Gao D Y and Ruan N. Solutions to quadratic minimization problems with box and integer constraints[J]., 2010, 47(3): 463-484.

[17] Fang S C, Gao D Y, Sheu R L,.. Canonical dual approach to solving 0-1 quadratic programming problems[J]., 2008, 4(1): 125-142.

[18] Boyd S and Vandenberghe L. Convex Optimization[M]. New York: Cambridge University Press, 2004: Chapter 11.

[19] 3GPP. Selection procedures for the choice of radio transmission technologies of the UMTS[S]. 1998: version 3.2.0.

程永生： 男，1987年生，博士生，研究方向为无线通信与移动社交网络.

朱 江： 男，1989年生，博士生，研究方向为信号处理与最优化理论.

林孝康： 男，1947年生，教授，研究方向为高速交换技术、宽带通信与IC设计.

Uplink Resource Allocation in Device-to-DeviceEnabled Cellular Networks

Cheng Yong-sheng Zhu Jiang Lin Xiao-kang

(,,100084,)

Uplink resource allocation in Device-to-Device (D2D) enabled cellular systems is studied. The sum-rate maximization problem is transformed into a concise Binary Integer Programming (BIP) problem, which is NP-hard. Then based on the Canonical duality theory, a dual problem is obtained. The dual problem is a convex problem in a continuous domain. Under appropriate conditions, the dual method attains the global optimal solution of the primal problem with zero duality gap. An algorithm based on the Barrier method is proposed to solve the dual problem. Simulation results show that the proposed algorithm performs close to optimal and outperforms the existing algorithm.

Device-to-Device (D2D) communication; Resource allocation; Integer programming; Canonical duality

TN929.5

A

1009-5896(2014)12-2822-06

10.3724/SP.J.1146.2014.00056

程永生 chyongsheng@gmail.com

2014-01-09收到，2014-06-20改回

清华-高通CDMA无线通信研究计划(20073000463)资助课题