引入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)資助課題