引入D2D通信的蜂窩網(wǎng)上行資源分配算法

程永生 朱 江 林孝康

?

引入D2D通信的蜂窩網(wǎng)上行資源分配算法

程永生*朱 江 林孝康

(清華大學(xué)電子工程系 北京 100084)

該文研究了引入Device-to-Device (D2D)通信的蜂窩網(wǎng)系統(tǒng)中的上行資源分配問題。首先將該問題建模為一個簡潔的二值整數(shù)規(guī)劃問題。然而整數(shù)規(guī)劃仍是NP難問題。該文利用Canonical對偶理論，得到其對偶形式。該對偶問題是一個連續(xù)域內(nèi)的凸問題。證明了在特定的條件下，可以通過求解對偶問題得到原問題的最優(yōu)解，且對偶間隙為零。提出了一個基于Barrier方法的算法來求解對偶問題。仿真結(jié)果表明，該文的算法優(yōu)于現(xiàn)有算法，且性能接近最優(yōu)。

D2D通信；資源分配；整數(shù)規(guī)劃；Canonical 對偶

1 引言

文獻(xiàn)[11-13]討論了引入D2D通信后的信道分配問題。為了減小信道復(fù)用帶來的干擾，文獻(xiàn)[11,12]假設(shè)每個信道最多被兩個用戶復(fù)用，并分別提出了貪婪算法進(jìn)行信道分配。在文獻(xiàn)[13]中，作者假設(shè)已先將信道分配給蜂窩網(wǎng)用戶，然后將D2D用戶信道復(fù)用建模為一個混合整數(shù)優(yōu)化問題，利用列生成算法給出一個次優(yōu)求解方法。文獻(xiàn)[14]研究了單載波(Single-Carrier, SC) FDMA系統(tǒng)中的上行信道分配。作者假設(shè)每個信道上的發(fā)射功率相等，然后將信道分配問題轉(zhuǎn)化為一個等式約束的二值整數(shù)規(guī)劃(Binary Integer Programming, BIP)問題。然而，BIP仍然是NP難問題，最差情況下的求解復(fù)雜度與問題的規(guī)模成指數(shù)關(guān)系。利用近來提出的Canonical對偶理論[15]，文獻(xiàn)[14]的作者沿用文獻(xiàn)[16,17]中的方法，將等式約束松弛為不等式，進(jìn)一步得到其對偶問題進(jìn)行求解。

本文首先將D2D系統(tǒng)中的信道分配問題建模為一個BIP問題。基于Canonical對偶理論[15]，本文將該BIP問題轉(zhuǎn)化為一個連續(xù)域內(nèi)的凹函數(shù)最大化問題。因此可以利用內(nèi)點(diǎn)法等凸優(yōu)化方法在多項(xiàng)式時間內(nèi)求解[18]。同時，本文給出了最優(yōu)解的條件。在該條件下，可以通過求解Canonical對偶問題得到原問題的全局最優(yōu)解。與文獻(xiàn)[14,16,17]不同，本文方法不需要將等式約束松弛為不等式約束，因此可以得到更寬松的最優(yōu)解條件。另外，本文提出了一個基于Barrier方法[18]的算法，用于求解對偶問題。仿真結(jié)果表明，本文方法的性能明顯優(yōu)于文獻(xiàn)[14]的算法。

2 系統(tǒng)模型

圖1 D2D系統(tǒng)信道分配示例圖

其中，式(1)表明每個用戶在同一時刻只使用一個信道。不等式(2)表示用戶實(shí)現(xiàn)通信所需的最小SINR約束。式(3)的第1部分保證同小區(qū)的蜂窩網(wǎng)用戶間不共用信道；第2部分表示允許D2D用戶復(fù)用信道，但每個信道最多被兩個用戶復(fù)用。

其中，的每一列代表一個可行的分配方案，每一行對應(yīng)一個用戶。列數(shù)為

3 Canonical 對偶方法求解資源分配問題

本節(jié)使用Canonical對偶方法求解上述資源分配問題。將證明當(dāng)滿足一定條件時，可以通過求解對偶問題得到原問題的最優(yōu)解。然后給出一個基于Barrier方法[18]的算法來求解對偶問題。

3.1 Canonical對偶函數(shù)及最優(yōu)解條件

定義指示函數(shù)為

引入全互補(bǔ)函數(shù)(total complementary function)：

將式(6)代入式(5)，可以得到對偶問題：

將

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

證明過程與文獻(xiàn)[17]中Theorem 3.(a)的證明類似(略)。

3.2基于Barrier方法的求解算法

4 仿真結(jié)果

考慮系統(tǒng)帶寬為10 MHz，中心頻率為2 GHz。上行頻譜資源被均分為=10個信道。有c=8個上行蜂窩網(wǎng)用戶和d=7個上行D2D用戶在系統(tǒng)中隨機(jī)均勻分布。同時，D2D接收用戶均勻分布于相應(yīng)的上行D2D用戶周圍100 m的距離內(nèi)。用戶之間以及用戶與基站之間的鏈路相互獨(dú)立，且服從瑞利平衰落。具體的參數(shù)如表2所示。

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

表2仿真參數(shù)

圖3給出了在不同的上行D2D用戶數(shù)目d情況下，系統(tǒng)的平均和速率。其他參數(shù)與圖2相同。從圖3中可以看到，一方面，隨著D2D用戶數(shù)的增加，系統(tǒng)和速率有增長的趨勢。這是由于當(dāng)系統(tǒng)中存在更多的短距離D2D鏈路時，可以獲得更好的頻率復(fù)用效果。該結(jié)果說明了允許短距離D2D鏈路復(fù)用蜂窩網(wǎng)資源的好處。另一方面，可以看到，本文算法的結(jié)果優(yōu)于文獻(xiàn)[14]中的方案以及貪婪算法得到的結(jié)果。并且，在不同的D2D用戶數(shù)的情況下，本文算法的結(jié)果與最優(yōu)解的性能都非常接近。

5 結(jié)論

基于Canonical對偶理論，本文將引入D2D通信的蜂窩系統(tǒng)中的上行資源分配問題轉(zhuǎn)化為一個連續(xù)域內(nèi)的凸優(yōu)化問題。因此可以利用凸優(yōu)化算法在多項(xiàng)式時間內(nèi)求解。文中給出了通過對偶問題得到原問題最優(yōu)解的條件。并提出了一個基于Barrier方法的算法來求解對偶問題。通過仿真發(fā)現(xiàn)，本文算法的結(jié)果優(yōu)于對比算法，且在大部分情況下可以得到原問題的全局最優(yōu)解。

圖2 系統(tǒng)和速率累積分布函數(shù)曲線

[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年生，博士生，研究方向?yàn)闊o線通信與移動社交網(wǎng)絡(luò).

朱 江： 男，1989年生，博士生，研究方向?yàn)樾盘柼幚砼c最優(yōu)化理論.

林孝康： 男，1947年生，教授，研究方向?yàn)楦咚俳粨Q技術(shù)、寬帶通信與IC設(shè)計(jì).

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無線通信研究計(jì)劃(20073000463)資助課題