混合D2D蜂窩網(wǎng)絡(luò)中基于模擬退火算法的資源調(diào)度策略

余翔，張海波，楊路

（重慶郵電大學(xué)，重慶 400065）

研究與開發(fā)

混合D2D蜂窩網(wǎng)絡(luò)中基于模擬退火算法的資源調(diào)度策略

余翔，張海波，楊路

（重慶郵電大學(xué)，重慶 400065）

D2D通信是未來5G網(wǎng)絡(luò)中一種近距離直通通信方式，在通信過程中，信息直接由發(fā)送端傳給接收用戶，而不需要經(jīng)過基站的轉(zhuǎn)發(fā)。在傳統(tǒng)蜂窩網(wǎng)絡(luò)中引入D2D通信可以極大地提升系統(tǒng)的總吞吐量、增大頻譜資源的利用率以及降低發(fā)射終端的功耗。主要介紹了一種適用于混合D2D蜂窩網(wǎng)絡(luò)中的資源分配方法，通過拉格朗日乘子法結(jié)合模擬退火算法實(shí)現(xiàn)頻譜資源的分配，提出一種同時(shí)考慮信道容量和能耗的基于模擬退火算法的資源調(diào)度策略。本算法在維也納仿真平臺(tái)上經(jīng)仿真驗(yàn)證，相比于傳統(tǒng)貪婪優(yōu)化算法，可以明顯增大系統(tǒng)總吞吐量和頻譜資源利用率。另外，算法中采用了分布式資源調(diào)度方法，D2D用戶根據(jù)算法步驟自行搜索適合的目標(biāo)信道并計(jì)算其發(fā)射功率，可以有效減少基站的信令開銷。

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

[3]提出了一種聯(lián)合資源分配算法，通過綜合考慮信道分配對(duì)網(wǎng)絡(luò)中已有的蜂窩用戶和 D2D 用戶的信號(hào)干擾，尋找具有最小干擾值的信道資源分配給D2D用戶，以實(shí)現(xiàn)有效的干擾控制，達(dá)到增大系統(tǒng)吞吐量的目的。參考文獻(xiàn)[4]根據(jù)蜂窩用戶和D2D鏈路對(duì)的最小信干噪比以及終端的門限發(fā)射功率求出D2D鏈路的發(fā)射功率取值范圍，然后分別給出了對(duì)應(yīng)的集中式和分布式解決方案。參考文獻(xiàn)[5]使用一種貪婪算法使系統(tǒng)的速率達(dá)到最大，在該算法中，具有較高的信道質(zhì)量指示（channel quality indicator，CQI）的蜂窩用戶與具有較低信道增益的 D2D鏈路對(duì)共享資源，以減輕D2D用戶對(duì)原蜂窩用戶的干擾影響。參考文獻(xiàn)[6]提出了一種基于博弈論的 D2D 資源分配算法，該算法通過構(gòu)建使系統(tǒng)總干擾量最小化的非合作博弈效用函數(shù)，同時(shí)考慮系統(tǒng)中D2D用戶間的相互干擾以及D2D用戶對(duì)蜂窩用戶的干擾，最后設(shè)計(jì)該博弈的潛在函數(shù)并求出潛在博弈模型的納什均衡態(tài)。

本文采用分布式資源管理方法，提出一種基于模擬退火算法的同時(shí)考慮信道容量和能耗的資源調(diào)度策略。首先為每條D2D鏈路初始化一條蜂窩信道，使用拉格朗日乘子法計(jì)算出最大化信道上的吞吐量的功率解，每隔一個(gè)調(diào)度周期 T，系統(tǒng)進(jìn)入下一個(gè)瞬態(tài)，每條D2D鏈路對(duì)獨(dú)立的根據(jù)約束條件匹配合適的蜂窩信道，每條蜂窩信道只能被一條D2D鏈路對(duì)復(fù)用，然后使用拉格朗日乘子法計(jì)算出使該蜂窩信道上吞吐量達(dá)到最大時(shí)蜂窩用戶與D2D發(fā)送端的發(fā)射功率。判斷D2D鏈路上的數(shù)據(jù)率是否降低，如果是明顯降低則拒絕該蜂窩信道，重新選擇一條滿足約束條件的蜂窩信道，如果比原分配的信道資源所得數(shù)據(jù)率增益相當(dāng)，則以一定的概率接受此次匹配，如果相比于調(diào)度之前數(shù)據(jù)率有所提升，則完全接受。同時(shí)判斷功率和是否有所增大，如果增大得太多或者超出門限功率值就直接拒絕，重新選擇蜂窩信道；如果只有稍微增大就仍以一定的概率接受該信道；如果功率和相比于調(diào)度之前有所下降則完全接受，每一輪調(diào)度結(jié)束后，調(diào)度周期則減小一個(gè)時(shí)間值。

2 系統(tǒng)場(chǎng)景

如圖1所示，假設(shè)在一個(gè)小區(qū)中存在M個(gè)蜂窩用戶和N條D2D鏈路對(duì)，D2D鏈路復(fù)用蜂窩上行信道。蜂窩用戶集合為D2D鏈路的集合為D2D對(duì)復(fù)用蜂窩上行信道進(jìn)行通信，由于D2D通信條件的苛刻性，一般混合D2D蜂窩網(wǎng)絡(luò)中D2D鏈路遠(yuǎn)少于蜂窩用戶，即 M＞＞N。則在蜂窩用戶集中至少存在一個(gè)最優(yōu)解與 D2D鏈路集D構(gòu)成共用網(wǎng)絡(luò)，并使其總吞吐量最大化。為了保護(hù)蜂窩用戶以及D2D用戶的通信質(zhì)量，設(shè)定以基站為中心、半徑為R的區(qū)域?yàn)镈2D限制區(qū)域[7]；同時(shí)，為每條D2D鏈路的接收端設(shè)定一個(gè)半徑為 r的區(qū)域?yàn)榉涓C限制區(qū)域，即可以與該D2D鏈路共用信道資源的蜂窩用戶不得在此區(qū)域內(nèi)。

圖1 D2D通信場(chǎng)景

3 算法分析

設(shè)定蜂窩用戶的最低信干比為 sinrc，D2D鏈路的最低信干比為 sinrd，蜂窩用戶與D2D鏈路的門限功率為maxP 。D2D接收端的信干噪比和基站的接收端信干噪比計(jì)算式分別如下所示：

其中，Pd、 Pc分別表示D2D對(duì)發(fā)射端的發(fā)射功率以及蜂窩用戶的發(fā)射功率， Gdd表示D2D鏈路之間的信道增益， Gcb表示蜂窩用戶與基站之間的信道增益， Gcd表示蜂窩用戶與D2D接收端之間的信道增益， Gdb表示D2D發(fā)射端與基站之間的信道增益， σ2表示高斯噪聲功率。由此可得出D2D發(fā)射功率的限制范圍為：

從物理角度出發(fā)，距離和信道增益成反比，瑞利信道中兩移動(dòng)終端的信道增益與距離的計(jì)算式[8]如下所示：

其中，K、α均是由環(huán)境所決定的路徑損耗常數(shù)和路徑損耗指數(shù)；d表示兩部終端之間的距離，λ表示兩者之間服從對(duì)數(shù)分布的慢衰落增益，γ表示兩者之間服從指數(shù)分布的快衰落增益。

為了減小資源分配的復(fù)雜度和同頻干擾強(qiáng)度，先給基站以及每個(gè)D2D接收端設(shè)定一個(gè)同頻最短距離 Rmin。假設(shè)基站與D2D接收端所能容忍的門限干擾分別為 IMAX和 Imax，根據(jù)蜂窩用戶與D2D鏈路的門限干擾要求可以求得同頻用戶之間的門限距離分別為：

可以求得限制半徑R與r分別為：

4 算法內(nèi)容

4.1 拉格朗日乘子法求最優(yōu)解

規(guī)定小區(qū)中每條D2D鏈路對(duì)能且只能匹配一條蜂窩信道，為每條蜂窩信道設(shè)置復(fù)用參數(shù)表示蜂窩信道上沒有復(fù)用 D2D鏈路對(duì)，表示蜂窩信道上已經(jīng)被D2D對(duì)復(fù)用。一條蜂窩信道 Ci可以被 D2 Dj鏈路復(fù)用的必要條件為：

以上是一個(gè)非凸優(yōu)化的條件極值求解過程[10]，由此可以根據(jù)拉格朗日乘子法求出被復(fù)用信道上吞吐量達(dá)到最大時(shí)的功率解：

4.2 算法流程

本文在貪心算法的基礎(chǔ)上將 D2D資源分配問題看作是馬爾可夫狀態(tài)轉(zhuǎn)移的數(shù)學(xué)問題[11]。規(guī)定系統(tǒng)為稀疏 D2D蜂窩網(wǎng)絡(luò)，且網(wǎng)絡(luò)環(huán)境比較穩(wěn)定，在一個(gè)調(diào)度周期T內(nèi)，移動(dòng)終端之間的信道狀態(tài)信息保持不變或者變動(dòng)范圍很小[12]。在調(diào)度周期內(nèi)，每條D2D鏈路自由的選取滿足自身復(fù)用條件的信道資源，然后使用拉格朗日乘子法[13]結(jié)合KKT約束條件求出信道傳輸速率最大化的功率解。

若求解得到的數(shù)據(jù)率之和有所增長(zhǎng)或者功率之和有所下降，則以此次調(diào)度所獲取的信道資源替換最近一次的信道資源，若是本輪調(diào)度相比于最近一次所接受的信道資源更差，則根據(jù)Metropolis準(zhǔn)則進(jìn)行取舍，以一定的概率接受該信道資源作為目標(biāo)信道。最后，判定調(diào)度周期是否結(jié)束，若沒有結(jié)束則進(jìn)行新一輪的調(diào)度，否則，進(jìn)行退火處理，將調(diào)度周期減去這一輪所用的時(shí)間，并將這一輪搜索中不滿足復(fù)用條件的蜂窩信道標(biāo)記為不可復(fù)用信道，縮小匹配范圍，重新尋找新的可復(fù)用信道，直到調(diào)度周期結(jié)束或者連續(xù)多次匹配的結(jié)果未被接受時(shí)，則退出算法。

算法中的接受概率計(jì)算如下：

具體算法步驟如下。

步驟1 初始化，系統(tǒng)隨機(jī)為每條D2D鏈路初始化一條蜂窩信道。

步驟2 假令 D2 Dj的初始化信道 RBj為其目標(biāo)信道RBλ，并使用式（8）計(jì)算出最優(yōu)功率解,計(jì)算最大數(shù)據(jù)率之和以及功率和

步驟3 根據(jù)式（8）為 D2 Dj選擇新的可復(fù)用信道 RBx，根據(jù)式（9）、式（10）計(jì)算最大化的數(shù)據(jù)率和以及功率和并按照式（11）求出概率p q、 的值。

步驟4 比較Cλ與Cx的大小，如果則進(jìn)入步驟5，如果則以概率p接受信道RBx為目標(biāo)信道。

步驟5 比較Pλ與xP的大小，如果xP Pλ＜ ,則進(jìn)入步驟 6，如果xP Pλ＞ ，則以概率q接受信道RBx為目標(biāo)信道，如果中有一個(gè)值超過門限功率，則返回步驟3。

步驟6 替換RBλ為 RBx，更新 D2 Dj的目標(biāo)信道。

步驟7 判斷調(diào)度周期是否結(jié)束，或者連續(xù)K次匹配的信道均未被接受，若是，則退出算法；若否，則進(jìn)行退溫處理，縮短周期，令T T= ?并標(biāo)記步驟 3中不附合條件的蜂窩信道為不可復(fù)用信道，減小搜索范圍，返回步驟3。

步驟8 每條D2D鏈路均按照上述步驟匹配目標(biāo)信道，并得到ST和共用體系的最大吞吐量CΣ。

具體流程如圖2所示。

圖2 具體算法流程

5 仿真結(jié)果

本文選定 LTE FDD單蜂窩小區(qū)作為仿真場(chǎng)景，采用LTE系統(tǒng)級(jí)仿真器進(jìn)行驗(yàn)證，仿真參數(shù)見表1。

表1 仿真參數(shù)

如圖 3所示，在仿真過程中經(jīng)可視化處理而得到的一個(gè)半徑 600 m的蜂窩小區(qū)，小區(qū)中隨機(jī)布置30個(gè)蜂窩用戶以及15個(gè)D2D對(duì)，D2D對(duì)處在蜂窩邊緣。圖 4表示本文算法與貪婪算所得系統(tǒng)吞吐量的對(duì)比，本文頻譜資源塊均作歸一化處理，其中前15個(gè)編號(hào)表示被D2D復(fù)用的資源塊，后10個(gè)資源塊上無D2D鏈路復(fù)用，由圖4中結(jié)果可知，未被D2D鏈路復(fù)用的資源塊沒有復(fù)用增益，數(shù)據(jù)率明顯低于被復(fù)用的信道，而在被復(fù)用的信道中，基于模擬退火算法的資源調(diào)度策略可以避免陷入局部最優(yōu)解，相比于貪婪算法[14]進(jìn)一步提高了信道數(shù)據(jù)率。圖5是頻譜效率的對(duì)比結(jié)果，由圖 5可知，在完全蜂窩模式下，系統(tǒng)的所有用戶均不采用D2D通信方式，頻譜效率較低且基本保持不變，而在采用 D2D通信方式的系統(tǒng)中，頻譜效率隨著D2D數(shù)目逐漸增大，說明在蜂窩網(wǎng)中引入D2D通信可有效提升頻譜效率，而貪婪算法的頻譜效率明顯低于模擬退火機(jī)制的調(diào)度算法。圖 6表示系統(tǒng)總?cè)萘康睦鄯e分布狀況，本文算法雖然比貪婪算法的收斂速度慢，但是從整體上提升了系統(tǒng)的總吞吐量。

圖3 仿真場(chǎng)景布置

圖4 本文算法與貪婪算法所得吞吐量對(duì)比

圖5 頻譜效率的對(duì)比結(jié)果

圖6 本文算法與貪婪算法的系統(tǒng)總數(shù)據(jù)率的累積分布對(duì)比

模擬退火算法的收斂周期比較慢，需要網(wǎng)絡(luò)環(huán)境十分穩(wěn)定，這是算法必要的前提條件。而混合D2D蜂窩網(wǎng)通常為稀疏型D2D蜂窩網(wǎng)，如果在此環(huán)境下基站分出額外的控制信令為其進(jìn)行資源與功率分配，系統(tǒng)得到的收益不會(huì)太多，基站的工作成本卻很大。因此，使用模擬退火算法可以有兩種優(yōu)勢(shì)：稀疏型D2D混合網(wǎng)的特性保證了D2D鏈路在搜索最優(yōu)解時(shí)有足夠的解空間；該算法有效降低了基站的信令開銷，本文的分布式結(jié)構(gòu)，既可以保證D2D技術(shù)對(duì)蜂窩系統(tǒng)帶來的利益，又可以避免額外的系統(tǒng)開銷。

6 結(jié)束語

在傳統(tǒng)蜂窩網(wǎng)中引入 D2D 通信技術(shù)可以有效提升系統(tǒng)吞吐量[15]。本文采用分布式資源管理方法，提出一種以提升系統(tǒng)信道容量和降低能耗為轉(zhuǎn)移條件的基于模擬退火算法的資源調(diào)度策略，該算法聯(lián)合考慮資源分配與功率控制，對(duì)系統(tǒng)內(nèi)資源分配過程進(jìn)行整體的優(yōu)化。經(jīng)仿真驗(yàn)證，該算法相比于傳統(tǒng)文獻(xiàn)中所使用的貪婪算法能進(jìn)一步增大系統(tǒng)的總吞吐量以及資源利用率，同時(shí)，相比于貪婪算法可以增大資源塊的數(shù)據(jù)率，使頻譜效率得到一定的提升。

參考文獻(xiàn)：

[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?），男，重慶郵電大學(xué)通信與信息工程學(xué)院副教授，主要研究方向?yàn)橥ㄐ啪W(wǎng)及交換技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)及信息安全和下一代網(wǎng)絡(luò)技術(shù)。

張海波（1990?），男，重慶郵電大學(xué)碩士生，主要研究方向?yàn)镈2D通信的資源分配與功率控制。

楊路（1969?），女，重慶郵電大學(xué)通信與信息工程學(xué)院高級(jí)工程師，主要研究方向?yàn)橥ㄐ啪W(wǎng)及交換技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)及信息安全、下一代網(wǎng)絡(luò)技術(shù)。

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

國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目（No.2015ZX03004004）

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

隨著現(xiàn)代化通信發(fā)展節(jié)奏的加快，人們對(duì)于移動(dòng)通信網(wǎng)絡(luò)傳輸速率的要求不斷提高，而頻譜資源的有限性使得傳統(tǒng)蜂窩模式通信無法滿足系統(tǒng)將要承載的容量需求。D2D通信是一種短距離終端直通通信方式，兩部終端直接復(fù)用蜂窩資源建立連接并傳輸信息，無需經(jīng)過基站轉(zhuǎn)發(fā)，這種通信模式與傳統(tǒng)的蜂窩模式相比，可以降低傳輸時(shí)延且增強(qiáng)可靠性[1]，此外，該模式可以有效地降低eNode B的負(fù)載壓力以及提高頻譜資源的利用率。目前，對(duì)于如何提高引入D2D通信的混合網(wǎng)絡(luò)的總吞吐量以及系統(tǒng)的公平性成為該研究領(lǐng)域的一大重點(diǎn)[2]。