有效解決網(wǎng)絡(luò)擁塞基于圖論的多小區(qū)D2D通信資源分配算法

中國電子科技集團(tuán)公司電子科學(xué)研究院 |袁蘇文

重慶郵電大學(xué) |梁云錦 吳廣富

移動通信技術(shù)重慶市重點實驗室 |吳建

隨著移動通信技術(shù)的不斷發(fā)展，我國移動通信系統(tǒng)已進(jìn)入了高速發(fā)展的階段。移動通信系統(tǒng)對通信技術(shù)的要求在不斷提高，人們對數(shù)據(jù)傳輸速率和通信覆蓋范圍的要求也越來越高。加之網(wǎng)絡(luò)擁塞現(xiàn)象日趨嚴(yán)重，現(xiàn)有的頻譜資源得不到有效的利用。為解決這一系列問題，D2D通信技術(shù)應(yīng)運而生。

D2D通信技術(shù)是距離相近的終端通過復(fù)用蜂窩用戶的授權(quán)頻譜進(jìn)行近距離通信，該技術(shù)可以提高系統(tǒng)的頻譜利用率。但D2D通信技術(shù)引入的同時也帶來了一定的挑戰(zhàn)，如嚴(yán)重的干擾問題。針對此問題，本文提出一種基于部分頻率復(fù)用(fractional frequency reuse, FFR)技術(shù)的多小區(qū)資源分配算法。首先，為減小相鄰小區(qū)之間的干擾問題，該算法將每個小區(qū)劃分為兩個區(qū)域，每個區(qū)域復(fù)用不同的頻譜資源；其次，為減小D2D用戶復(fù)用單個蜂窩用戶所產(chǎn)生的干擾，按照特定的比例復(fù)用相應(yīng)蜂窩用戶的頻譜資源。仿真結(jié)果表明，該方案不僅減小了小區(qū)間的干擾問題，保證了蜂窩通信系統(tǒng)的服務(wù)質(zhì)量，還提高了系統(tǒng)總吞吐量。

系統(tǒng)模型

軟頻率復(fù)用技術(shù)常用在多小區(qū)通信系統(tǒng)中，能夠有效地抑制相鄰小區(qū)間的同頻干擾，且每個小區(qū)都可以使用蜂窩通信系統(tǒng)中所有的頻譜資源，在頻譜資源日益緊缺，且LTE通信系統(tǒng)對帶寬的需求不斷增長的情況下，使用軟頻率復(fù)用技術(shù)分配頻譜資源對LTE的長期發(fā)展十分有利。但采用該方式分配頻譜資源時同樣會產(chǎn)生大量的干擾，本小節(jié)的主要內(nèi)容就是通過合理的資源分配算法來減小通信系統(tǒng)中的干擾問題。如圖1所示，，基站)處于每個小區(qū)的中心，每個小區(qū)內(nèi)有Mi個蜂窩用戶Nj對D2D用戶,其中，DT表示發(fā)送端用戶，DR表示接收端用戶。蜂窩用戶ci正常通信占用的資源塊數(shù)目為mci。假設(shè)基站已知蜂窩用戶和D2D用戶對之間的信道狀態(tài)信息(CSI)。

圖1 SFR算法中小區(qū)1中用戶的資源分配

如圖1所示，每個小區(qū)可分為中心區(qū)域和邊緣區(qū)域兩部分，且每個小區(qū)的頻譜資源F1、F2、F3三部分。小區(qū)中心用戶和邊緣用戶分別分配不同的頻包括譜資源，相鄰三個小區(qū)中心蜂窩用戶分別分配F1、F2、F3中任一部分資源，各小區(qū)邊緣蜂窩用戶則分別分配每個小區(qū)所剩余的頻譜資源，每個小區(qū)的中心D2D用戶復(fù)用本小區(qū)邊緣蜂窩用戶的頻譜資源，且邊緣蜂窩D2D用戶復(fù)用本小區(qū)中心蜂窩用戶的頻譜資源，兩跨小區(qū)D2D用戶則復(fù)用相鄰兩小區(qū)中心蜂窩用戶的頻譜資源，如圖1所示。以小區(qū)1為例，CCU分配F1資源，ECU分配F2和F3資源，CDU復(fù)用F2和F3資源，EDU復(fù)用F1資源，跨小區(qū)1、2的IDU復(fù)用F1或F2資源。其中，F(xiàn)1、F2、F3分別占系統(tǒng)帶寬的1/3。

以小區(qū)1為例，分析基于SFR的D2D通信系統(tǒng)模型中蜂窩用戶和D2D用戶之間的干擾。則小區(qū)1中基站受到的干擾包括：小區(qū)1中邊緣D2D用戶復(fù)用F1資源所帶來的干擾，相鄰小區(qū)邊緣蜂窩用戶使用F1資源所帶來的干擾，跨小區(qū)用戶復(fù)用F1資源所帶來的干擾。

小區(qū)1中心區(qū)域D2D接收端DT收到的干擾包括：本小區(qū)邊緣蜂窩用戶復(fù)用F2、F3資源所帶來的干擾，相鄰小區(qū)邊緣蜂窩用戶復(fù)用F2或F3資源所帶來的干擾，相鄰小區(qū)中心用戶復(fù)用F2或F3資源所帶來的干擾，跨小區(qū)用戶復(fù)用F2或F3資源所帶來的干擾。

小區(qū)1邊緣D2D接收端DT受到的干擾包括：本小區(qū)中心蜂窩用戶使用F1資源所帶來的干擾，相鄰小區(qū)中心D2D用戶復(fù)用F1資源所帶來的干擾，相鄰小區(qū)邊緣蜂窩用戶使用F1資源所帶來的干擾，跨小區(qū)用戶復(fù)用F1資源所帶來的干擾。

跨小區(qū)1和小區(qū)2的D2D接收端DT受到的干擾包括：小區(qū)1、2中心蜂窩用戶使用F1或F2資源所帶來的干擾，各小區(qū)邊緣蜂窩用戶使用F1或F2資源所帶來的干擾，各小區(qū)D2D用戶復(fù)用F1或F2資源所帶來的干擾。

基于上述分析，采用SFR技術(shù)為蜂窩用戶和D2D用戶分配頻譜資源所帶來的干擾，與采用FFR算法帶來的干擾有很大的區(qū)別，但干擾類型相差無幾，是小區(qū)k中蜂窩用戶i的發(fā)射功率，是小區(qū)k中D2D用戶j的發(fā)射功率，和分別表示小區(qū)k中基站到蜂窩用戶i和蜂窩用戶i到D2D用戶 的信道增益，表示小區(qū)k中兩D2D用戶間的信道增益，表示小區(qū)用戶所分配的資源塊RB的數(shù)目，是D2D用戶對j復(fù)用蜂窩用戶i的資源的頻率復(fù)用因子，其計算公式為：

其中，K為可復(fù)用的蜂窩用戶的個數(shù)，假設(shè)一個蜂窩用戶的部分頻譜資源只能被一個D2D用戶復(fù)用，但一對D2D用戶可以復(fù)用多個蜂窩用戶的資源塊。故被復(fù)用蜂窩用戶i的信干噪比為：

RB未被復(fù)用的蜂窩用戶i的信干噪比為：

D2D通信引入蜂窩通信系統(tǒng)之前，蜂窩用的信干噪比與未被復(fù)用部分的信干噪比計算方法相同，為進(jìn)行區(qū)分，用rci表示，計算

公式如下：

D2D用戶j的信干噪比為：

上述公式中，N0和I分別表示噪聲功率和小區(qū)間的噪聲干擾功率。由香農(nóng)公式分別計算被復(fù)用的蜂窩用戶的吞吐量rci、未被復(fù)用的蜂窩用戶的吞吐量、引入D2D通信前，蜂窩用戶的吞吐量和D2D用戶的吞吐量rdj，

其中Bc、和Bd分別表示蜂窩用戶被復(fù)用的帶寬、蜂窩

ij用戶未被復(fù)用的帶寬和D2D用戶的帶寬。則該通信系統(tǒng)的吞吐量rsum為：

其中，mc表示每個蜂窩分配的RB數(shù)，

i分別表示蜂窩用戶ci在被復(fù)用部分的資源上、未被復(fù)用部分資源上所獲取的吞吐量即為所有蜂窩用戶的總吞吐量； 表示所有 D2D用戶的吞吐量，則rsum表示蜂窩用戶和D2D用戶的吞吐量之和，即整個蜂窩通信系統(tǒng)的總吞吐量。

表示引入D2D通信前蜂窩用戶ci的吞吐量。表示蜂窩用戶ci未被復(fù)用部分的吞吐量，表示蜂窩用戶ci被復(fù)用部分的吞吐量，表示D2D用戶dj復(fù)用蜂窩用戶ci的比例的頻譜資源所產(chǎn)生的吞吐量，則r表示引入D2D通信后，D2D用戶dj和蜂窩用戶ci所產(chǎn)生的吞吐量。引入D2D通信前蜂窩通信系統(tǒng)的總吞吐量為：

由此可得，引入D2D通信前后，系統(tǒng)吞吐量增益為：

本文的主要目標(biāo)是最大化通信系統(tǒng)的吞吐量增益Δrsum，且該目標(biāo)函數(shù)為的函數(shù)，因此優(yōu)化的目標(biāo)函數(shù)為：

不等式(11.1)和不等式(11.2)分別保證蜂窩用戶和D2D用戶的正常通信。在本文算法中，D2D用戶可復(fù)用多個蜂窩用戶的部分頻譜資源，但每個蜂窩用戶的頻譜資源只能被一個D2D用戶復(fù)用，故不等式(11.3)保證任一D2D用戶對復(fù)用的所有蜂窩用戶的總頻譜不超過每個蜂窩用戶固定分配的頻譜資源；(11.4)保證每個蜂窩用戶可被復(fù)用的頻譜資源不能超過其固有的頻譜資源；(11.5)表示每對D2D用戶復(fù)用任一蜂窩用戶的頻譜資源的頻率復(fù)用因子均在[0,1]區(qū)間內(nèi)取值。上述公式(11)為一個非確定性多項式問題，直接求解比較困難，故提出一種基于FFR的資源分配算法求解該問題。

基于圖論的多小區(qū)D2D通信資源分配算法

為求解上述最大化問題，本文從圖論的角度出發(fā)，將多小區(qū)D2D通信系統(tǒng)吞吐量增益的最大化問題轉(zhuǎn)化為求解二分圖的最優(yōu)匹配問題。二分圖是一種簡單的無向圖，由兩個相互正交的頂點集和兩頂點集間連線所構(gòu)成的邊集組成。其中邊集表示所連接的兩定點間的關(guān)系，且每條邊所連接的兩個頂點分別屬于兩個頂點集。假設(shè)蜂窩用戶和D2D用戶對分別對應(yīng)兩個頂點集，D2D用戶復(fù)用蜂窩用戶的頻譜資源用邊集表示，邊的權(quán)值表示D2D用戶復(fù)用蜂窩用戶的頻譜資源所帶來的吞吐量增益。下面對該算法進(jìn)行詳細(xì)的介紹。

圖2 圖論模型

定義一個無向二分圖 Φ = (C,D,E)，如圖2所示頂點集由兩個相互獨立的子集：蜂窩用戶集C和D2D用戶對集D組成，邊集由D2D用戶與蜂窩用戶間的復(fù)用關(guān)系表示，D2D用戶對dj與蜂窩用戶ci滿足其正常通信的信干噪比閾值且D2D用戶dj能夠復(fù)用蜂窩用戶ci的頻譜資源，則該蜂窩用戶ci與D2D用戶對dj之間連線構(gòu)成邊ei,j，否則，ci和dj之間不能連接成線，即不構(gòu)成復(fù)用關(guān)系。邊的權(quán)值表示D2D用戶對復(fù)用蜂窩用戶頻譜資源所產(chǎn)生的吞吐量增益，則W為權(quán)值矩陣。圖2所示的權(quán)值矩陣為：

蜂窩用戶分為CCU和ECU，D2D用戶分為CDU、EDU和IDU。根據(jù)SFR資源分配算法對不同區(qū)域的蜂窩用戶分配不同的頻譜資源，相對應(yīng)的，為不同區(qū)域的D2D用戶選擇合適的備選資源。在已知D2D用戶對復(fù)用的備選蜂窩用戶集之后，本文以最大化吞吐量增益為目標(biāo)，選擇D2D對最終復(fù)用的蜂窩用戶及對應(yīng)的頻率復(fù)用因子。下面給出具體的基于圖論的D2D對復(fù)用蜂窩用戶頻譜資源的啟發(fā)式算法。

1）將該特定區(qū)域的D2D用戶集Dd等效為圖論模型中點集D，備選的可復(fù)用蜂窩用戶集CC等效為圖論模型中點集C，并初始化D2D用戶和蜂窩用戶所對應(yīng)的用戶狀態(tài)信息。

2）根據(jù)信干噪比公式分別計算Cc中蜂窩用戶和Dd中D2D用戶的信干噪比，并判斷其是否滿足其正常通信的信干噪比門限，若不能滿足，則證明D2D用戶不能復(fù)用蜂窩用戶的頻譜資源，與不能連接成線，表示為

4）使用最優(yōu)匹配算法求得蜂窩用戶和D2D用戶構(gòu)成虛擬矩陣的完美匹配，輸出對應(yīng)的分配矩陣R。

6）更新可復(fù)用的蜂窩用戶集，步驟4）中已被復(fù)用的蜂窩用戶不能再次被復(fù)用，在CC中除去步驟4）中被復(fù)用的蜂窩用戶，得更新的可復(fù)用蜂窩用戶集CC，并在虛擬復(fù)用矩陣ω中將對應(yīng)的吞吐量增益ωωi,j設(shè)為∞，得更新的虛擬復(fù)用矩陣W。

7）循環(huán)步驟4）、5）、6）K次，若蜂窩D2D用戶可復(fù)用的蜂窩用戶個數(shù)L等于K，則復(fù)用該K個蜂窩用戶的頻譜資源，否則，復(fù)用L個蜂窩用戶的頻譜資源，并輸出相對應(yīng)的頻率復(fù)用因子矩陣，i算法結(jié)束。

仿真分析

為驗證所提算法的可靠性，本文采用MATLAB仿真軟件對其進(jìn)行驗證。小區(qū)采用正六邊形，小區(qū)半徑為500m，設(shè)系統(tǒng)帶寬為20MHz，小區(qū)頻帶分為三部分F1、F2和F3，每部分帶寬相等，均為小區(qū)帶寬的1/3，每個RB帶寬為180KHz。為驗證本文所提算法的可行性和有效性，作者引入兩個對比算法進(jìn)行對比驗證。方案1在多小區(qū)D2D通信系統(tǒng)中引入經(jīng)典軟頻率復(fù)用SFR技術(shù)，D2D用戶分別在各自備選蜂窩用戶的頻譜資源中隨機(jī)進(jìn)行復(fù)用。方案2在多小區(qū)D2D通信系統(tǒng)中不使用任何干擾抑制技術(shù)，D2D用戶隨機(jī)復(fù)用蜂窩用戶的頻譜資源。采用這兩種算法與本文中的SFR技術(shù)下基于圖論的多小區(qū)D2D通信資源分配算法（簡稱GBFR）進(jìn)行對比，可有效驗證本文所提算法的優(yōu)勢。

圖3 蜂窩用戶通信穩(wěn)定性隨D2D用戶信干噪比的變化曲線

圖2 是蜂窩用戶通信穩(wěn)定性隨D2D用戶信干噪比的變化曲線，仿真結(jié)果表明，蜂窩用戶的穩(wěn)定性隨D2D用戶信干噪比的增大而逐漸降低。這是因為隨著D2D用戶信干噪比增大，D2D用戶的發(fā)射功率也會逐漸增大，從而D2D用戶對蜂窩用戶的干擾也逐漸增大，蜂窩用戶的通信穩(wěn)定逐漸降低。此外，分別取D2D用戶可復(fù)用的蜂窩用戶個數(shù)（K值）是1、3、5、8時驗證蜂窩用戶的通信穩(wěn)定性。仿真結(jié)果表明，隨著D2D用戶復(fù)用蜂窩用戶個數(shù)的增加，蜂窩用戶的穩(wěn)定性逐漸增強(qiáng)。這是因為D2D用戶復(fù)用多個蜂窩用戶的頻譜資源時將干擾信號分到多個蜂窩用戶上，減輕了對單個蜂窩用戶的干擾，增強(qiáng)蜂窩用戶的通信穩(wěn)定性。

圖4為系統(tǒng)吞吐量的累積分布函數(shù)曲線，由圖可以看出，SRA算法、SFR算法和GBFR算法的吞吐量依次遞增。這是因為SFR算法是在SRA算法的基礎(chǔ)上使用了小區(qū)間干擾抑制技術(shù)，減輕了相鄰小區(qū)間的同頻干擾，增強(qiáng)蜂窩用戶和D2D用戶的通信質(zhì)量。GBFR算法是在SFR算法的基礎(chǔ)上對D2D用戶的備選頻譜資源進(jìn)行重分配，進(jìn)一步減小蜂窩用戶和D2D用戶間的干擾，同時增加了蜂窩用戶和D2D用戶的吞吐量。

圖5為D2D用戶的平均接入數(shù)量隨蜂窩用戶的信干噪比的變化曲線。由圖可以看出，D2D用戶的平均接入數(shù)量隨蜂窩用戶信干噪比的增大逐漸降低。這是因為蜂窩用戶的信干噪比增大的同時會給D2D用戶造成更嚴(yán)重的干擾，導(dǎo)致D2D用戶的通信性能減弱，D2D用戶的平均接入數(shù)量亦隨之減少。此外，在蜂窩用戶信干噪比一定時，SRA算法、SFR算法和GBFR算法的平均接入數(shù)量逐漸增加，這是因為三種算法的抗干擾能力依次增強(qiáng)，GBFR算法和SFR算法均采用經(jīng)典的軟頻率復(fù)用技術(shù)應(yīng)用在多小區(qū)中，抑制了相鄰小區(qū)間的干擾。且GBFR進(jìn)一步使用了抑制干擾的一對多資源復(fù)用方案，減輕了蜂窩用戶和D2D用戶之間的同頻干擾問題，增強(qiáng)了D2D通信系統(tǒng)的通信性能。

圖4 系統(tǒng)吞吐量的累積分布函數(shù)曲線

圖5 D2D用戶的平均接入數(shù)量隨蜂窩用戶的信干噪比的變化曲線

針對多小區(qū)D2D通信場景，本文結(jié)合經(jīng)典的軟頻率復(fù)用技術(shù)，提出一種基于圖論的多小區(qū)D2D通信資源分配算法。該算法在減小相鄰小區(qū)間干擾的同時，充分利用小區(qū)頻譜資源，將D2D用戶和備選的蜂窩用戶等效為二分圖中兩不相關(guān)的頂點集，以最大化系統(tǒng)吞吐量增益為目標(biāo)函數(shù)，采用最優(yōu)匹配算法為D2D用戶選擇最終復(fù)用的K個蜂窩用戶，并計算其相應(yīng)的復(fù)用比例。仿真結(jié)果表明，該算法有效的提升了通信系統(tǒng)的頻譜利用率，增加了D2D通信系統(tǒng)的吞吐。