張臻昊，李 輝

（中國科學(xué)技術(shù)大學(xué) 中國科學(xué)院無線光電通信重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230026）

0 引 言

隨著通信技術(shù)的發(fā)展，5G時(shí)代即將來臨。用戶的吞吐量迎來爆炸性的增長，接入設(shè)備的數(shù)量也日益增多，傳統(tǒng)的蜂窩網(wǎng)絡(luò)構(gòu)架已經(jīng)無法滿足用戶的需求。針對這些問題，研究人員提出了異構(gòu)蜂窩網(wǎng)絡(luò)[1]（Heterogeneous Networks，HetNets）的概念，通過在宏基站覆蓋不到、薄弱的區(qū)域以及熱點(diǎn)區(qū)域布置較小功率的基站（如皮小區(qū)基站，家庭小區(qū)基站以及分布式天線系統(tǒng)等）來提供通信服務(wù)，從而為用戶提供更高的通信速率。

網(wǎng)絡(luò)構(gòu)架的更新帶來的是新的網(wǎng)絡(luò)模型和分析方法，傳統(tǒng)的方法已經(jīng)不再適用于異構(gòu)蜂窩網(wǎng)絡(luò)的復(fù)雜場景[2]。資源分配以及用戶歸屬問題是異構(gòu)蜂窩網(wǎng)絡(luò)中的基本問題。資源分配問題主要關(guān)注每個(gè)小區(qū)的物理資源塊該如何分配給各個(gè)用戶。用戶歸屬問題解決用戶應(yīng)該接入哪個(gè)小區(qū)基站。將一個(gè)用戶歸屬到某個(gè)基站，會影響接入該基站的其他用戶對資源塊的使用，因此用戶歸屬問題應(yīng)和資源分配方案一起解決[3]。為了提高系統(tǒng)性能，資源分配和用戶歸屬問題的優(yōu)化應(yīng)在整個(gè)網(wǎng)絡(luò)層面進(jìn)行，然而這種優(yōu)化被證明是NP難題，難以求其精確解[4]。

傳統(tǒng)的方法一般采用信噪比或者信號接收強(qiáng)度[5]作為用戶接入準(zhǔn)則。文獻(xiàn)[6]提出用信干噪比作為歸屬準(zhǔn)則。用戶選擇接入具有最大信干噪比的基站，可以獲得比以信號強(qiáng)度為準(zhǔn)則的方案更好的系統(tǒng)吞吐量。文獻(xiàn)[7]提出了在多小區(qū)網(wǎng)絡(luò)中聯(lián)合優(yōu)化部分頻率復(fù)用和負(fù)載均衡的用戶歸屬和資源分配方案。文獻(xiàn)[8]用非線性規(guī)劃方法處理多速率無線局域網(wǎng)中的用戶歸屬問題，目標(biāo)函數(shù)為最大化網(wǎng)絡(luò)中用戶帶寬收益之和。文獻(xiàn)[9]采用博弈論的方法進(jìn)行資源分配，但方法較為繁瑣。以上這些方案大多基于固定的頻率復(fù)用方案，并未考慮用戶的分布情況，但隨著網(wǎng)絡(luò)異構(gòu)性的增強(qiáng)，為了得到更高的性能增益，動態(tài)的頻率復(fù)用應(yīng)該作為資源分配考慮的重要方面。

本文提出了一種基于自動微分的用戶歸屬和資源分配聯(lián)合算法。自動微分[10]（Automatic Differentiation，AD）也稱為算法微分，是一種類似于反向傳播但比反向傳播更通用的技術(shù)，近年來被廣泛應(yīng)用于深度學(xué)習(xí)領(lǐng)域。

本文構(gòu)建了動態(tài)頻譜復(fù)用下的資源分配和用戶接入模型，將該問題轉(zhuǎn)換為動態(tài)計(jì)算圖下的目標(biāo)函數(shù)最小化問題，基于自動微分計(jì)算獲得可行解。仿真實(shí)驗(yàn)表明，所提算法相對于傳統(tǒng)的方案能顯著提升系統(tǒng)吞吐量、頻率復(fù)用率以及系統(tǒng)性能。

1 系統(tǒng)模型

異構(gòu)蜂窩網(wǎng)絡(luò)的模型如圖1所示。該網(wǎng)絡(luò)由一個(gè)宏基站與多個(gè)發(fā)射功率不同和覆蓋面積不同的微基站組成。該系統(tǒng)共有N個(gè)基站，K個(gè)用戶，NB個(gè)資源塊，小區(qū)集合為用戶集合為K= { 1,…,K}，資源塊集合為R= { 1,2,… ,NB}。

圖1 異構(gòu)蜂窩網(wǎng)絡(luò)模型

本文研究的是下行鏈路的資源分配，并做出了如下假設(shè)：

（1）區(qū)域內(nèi)系統(tǒng)總資源是固定的，即頻譜資源固定，資源集中管理，統(tǒng)一分配，各小區(qū)基站資源由系統(tǒng)實(shí)時(shí)分配，每個(gè)基站使用的資源塊數(shù)目可以不同。

（2）最小的資源單元是物理資源塊，單位資源塊的帶寬為B0。

（3）每個(gè)用戶只能接入一個(gè)基站，即只能接收從一個(gè)基站發(fā)送來的信號。

（4）系統(tǒng)中K個(gè)用戶的位置信息和信道增益信息都是已知的。用戶的位置可能是均勻分布的，也可能是非均勻分布的。

（5）若給定用戶接收到各個(gè)基站信號的信干噪比，則可以計(jì)算用戶從各基站可能獲得的速率。

1.1 變量定義

1.1.1 用戶歸屬矩陣

定義用戶歸屬矩陣，其中每個(gè)元素表示用戶集合中用戶k是否歸屬于基站n，接收從基站n發(fā)送來的數(shù)據(jù)。元素定義如下：

1.1.2 資源塊分配矩陣

資源分配矩陣定義為其元素代表資源集合中的資源塊i是否被分配給用戶k。

1.1.3 聯(lián)合分配數(shù)組

從以上兩個(gè)指示變量可以得到最終的聯(lián)合分配數(shù)組，其中：

X是一個(gè)大小為N×K×NB的三維數(shù)組，其代表著資源塊、用戶、基站三者之間的相互對應(yīng)關(guān)系。

1.2 問題描述

由以上定義的變量可以推出用戶k連接到基站n在資源塊i上的信干噪比為：

其中代表資源塊i在基站n上的功率，表示從基站n到用戶k在資源塊i上的路徑損耗，σ2表示單位資源塊上的噪聲功率。于是，用戶k從基站n處獲得的速率可表示為：

則用戶k從所有基站上獲得的實(shí)際速率為：

為了能在系統(tǒng)吞吐量和用戶公平性間取得折中，選擇用戶速率對數(shù)和作為優(yōu)化目標(biāo)，以保證用戶比例的公平性。同時(shí)，從以上的分析可以得到一系列約束條件，因此可以將異構(gòu)蜂窩網(wǎng)絡(luò)用戶歸屬和資源分配的優(yōu)化問題表述如下：

式（7）中（a）為用戶最小的速率約束，每個(gè)用戶進(jìn)行不同的通信業(yè)務(wù)需要不同的速率需求；（b）表示每個(gè)資源塊在同一個(gè)基站只能供一個(gè)用戶使用；（c）為每個(gè)用戶只能連接一個(gè)基站，在該站分配資源塊的約束條件，本文暫不考慮同一用戶同時(shí)接入不同的基站的情況；（e）為單個(gè)資源塊上速率約束，是為了消除個(gè)別信噪比過小的分配方案。以上是整個(gè)問題的數(shù)學(xué)表示。

該優(yōu)化問題的目標(biāo)是求得聯(lián)合分配數(shù)組X的解，這樣可以同時(shí)得到頻率復(fù)用方案以及用戶歸屬和資源分配方案。然而，該問題被證明是一個(gè)NP難問題，難以一步求解?，F(xiàn)有的方法大多將其分解為多個(gè)子問題，利用變量松弛法進(jìn)行拉格朗日對偶求解，解法復(fù)雜且尚未考慮動態(tài)頻率復(fù)用方案。

2 基于自動微分的資源分配算法

式（7）中的聯(lián)合資源分配和用戶歸屬是一個(gè)混合整數(shù)的不等式優(yōu)化問題，是一個(gè)NP難問題，難以用一般的方式進(jìn)行一步求解。因此，這里引入AD，使用深度學(xué)習(xí)的相關(guān)框架，將其表述為一個(gè)計(jì)算圖下的優(yōu)化問題，將系統(tǒng)目標(biāo)函數(shù)與約束條件轉(zhuǎn)換成該計(jì)算圖的目標(biāo)函數(shù)，基于反向傳播機(jī)制，采用梯度下降算法，對用戶接入與資源分配數(shù)組X進(jìn)行迭代優(yōu)化求解，最終獲得該問題的可行解。由于變量之間的關(guān)系表達(dá)式過于復(fù)雜，無法直接求出梯度的數(shù)學(xué)表達(dá)式，此時(shí)引入AD能夠有效進(jìn)行梯度的相關(guān)計(jì)算。

2.1 自動微分

微分求解有4種主要的求解方式：手動求解法、數(shù)值微分法、符號微分法以及自動微分法[10-11]。

手動求解法是直接對函數(shù)進(jìn)行導(dǎo)數(shù)計(jì)算。對于簡單的函數(shù)，此方法有效可行。但是，對于復(fù)雜的函數(shù)，手動求解法是個(gè)龐雜且易出錯(cuò)的過程。數(shù)值微分法是使用有限差分進(jìn)行近似，簡單實(shí)用，但可能會存在較大的舍入和截取誤差，隨變量數(shù)的增加計(jì)算量激增。符號微分是使用符號計(jì)算得到精確的閉合表達(dá)式的求導(dǎo)結(jié)果，但隨著函數(shù)的復(fù)雜度增加，所產(chǎn)生的符號表達(dá)式會呈指數(shù)增長，造成表達(dá)式爆炸。對于本文復(fù)雜的目標(biāo)函數(shù)和規(guī)模龐大的變量而言，以上3種方法均存在相應(yīng)的問題，而自動微分方法則克服以上缺陷，在計(jì)算大規(guī)模數(shù)據(jù)導(dǎo)數(shù)等方面更高效。

自動微分的原理是通過分析數(shù)據(jù)的相關(guān)性，基于鏈?zhǔn)角髮?dǎo)法，通過中間變量傳遞輸出變量對輸入變量的依賴關(guān)系，結(jié)合計(jì)算機(jī)程序生成微分程序的方法。它主要分為前向模式和反向模式兩種。前向模式是從輸入一步步求導(dǎo)到輸出，有幾個(gè)自變量需要求導(dǎo)幾次；反向模式則是從輸出反向求導(dǎo)到輸入。本文使用反向模式。反向模式的AD對應(yīng)于一個(gè)廣義的反向傳播算法，因?yàn)槠鋸慕o定的輸出反向傳播導(dǎo)數(shù)。

例如，對于函數(shù)[10]：

圖2為該函數(shù)計(jì)算圖，反向模式即從輸出反向求導(dǎo)到輸入。假設(shè)其初始值(x1,x2)=(3,4)，根據(jù)表1左邊的前向路徑推導(dǎo)出y之后，可根據(jù)右邊的反向路徑一次性求出y關(guān)于輸入變量x1、x2的導(dǎo)數(shù)。反向模式的一個(gè)重要優(yōu)點(diǎn)是，對于具有大量輸入變量的函數(shù)，計(jì)算成本明顯低于正向模式，可以通過一次反向求導(dǎo)完成整個(gè)過程。

圖2 示例計(jì)算圖路徑

表1 反向模式的過程示例

2.2 算法設(shè)計(jì)

本文在Pytorch框架下實(shí)現(xiàn)基于自動微分的算法[12-13]，將目標(biāo)函數(shù)以及約束條件轉(zhuǎn)化為計(jì)算圖的損失函數(shù)，基于自動微分進(jìn)行梯度下降算法求解，設(shè)計(jì)過程如下。

2.2.1 步驟1

首先將分配變量松弛為，使其成為0-1之間的連續(xù)變量，方便進(jìn)行后續(xù)梯度的計(jì)算。

本文采用Xavier方法初始化三維數(shù)組，各元素滿足標(biāo)準(zhǔn)正態(tài)分布。將該數(shù)組的用戶維度（定義經(jīng)過softmax函數(shù)得到每個(gè)資源塊的分配概率值為1，代表資源塊在基站n上僅被當(dāng)前用戶k使用。值越小，被使用概率越小，保證變量的取值范圍。

2.2.2 步驟2

原優(yōu)化問題含有不等式約束，考慮引入罰函數(shù)，用拉格朗日乘子法將約束條件疊加到目標(biāo)函數(shù)上，從而將有約束的最優(yōu)化問題轉(zhuǎn)化為無約束條件的問題。合理的罰函數(shù)可以在算法搜索到不可行點(diǎn)時(shí)，使目標(biāo)函數(shù)值變得很大。離約束條件越遠(yuǎn)，懲罰越大。因此，得到的增廣目標(biāo)函數(shù)如下：

由此將問題（7）轉(zhuǎn)化為求式（9）的最小值，其中各個(gè)loss為式（7）中不同的約束條件轉(zhuǎn)化成的數(shù)學(xué)表達(dá)式，具體如下：

（1）loss1為式（7）中有關(guān)用戶速率的約束（a），將用戶從所有基站以及資源塊上獲得的速率進(jìn)行求和，與用戶的最低速率約束進(jìn)行比較。

（2）loss2為式（7）中關(guān)于單個(gè)資源塊分配的約束（b），對于每一個(gè)xn i，其元素中最多只能有一個(gè)值為1，滿足單個(gè)資源塊在一個(gè)基站上只能分配給一個(gè)用戶約束。

（3）loss3為式（7）中有關(guān)用戶只能接入一個(gè)基站約束（c），定義矩陣同時(shí)可以定義一維向量。對X針對資源得到每個(gè)用戶從每個(gè)基站接收到的資源塊數(shù)目Y。對于矩陣Y，其基站維度只能有一個(gè)非零項(xiàng)，softmax函數(shù)能夠有效將該維度所有元素的和固定為1。令其最大值與1逼近，則保證了該維度只能有一個(gè)非零項(xiàng)，滿足約束條件。

（4）loss4是式（7）中對于單位資源塊上的最低速率約束（e），以防止單個(gè)資源塊上的信噪比過低。

最終，得到增廣目標(biāo)函數(shù)也就是計(jì)算圖的損失函數(shù)的表達(dá)形式為：

2.2.3 步驟3

對式（14）直接進(jìn)行梯度下降算法很難求出其梯度的解析形式：

因此，為了將其轉(zhuǎn)化為深度學(xué)習(xí)框架下的微分優(yōu)化問題，本文利用自動微分進(jìn)行程序編寫，將步驟2中各loss函數(shù)編寫為相應(yīng)程序。

2.2.4 步驟4

求解loss函數(shù)關(guān)于聯(lián)合分配數(shù)組X的梯度反向傳播到輸入，采用Adam梯度下降算法更新輸入，反復(fù)迭代直至收斂，得到問題的可行解。最后，將松弛后的自變量按照四舍五入原則還原成{0,1}的整數(shù)變量。

3 仿真分析

假設(shè)仿真實(shí)驗(yàn)中，異構(gòu)蜂窩網(wǎng)絡(luò)中有3種不同小區(qū)，分別為宏小區(qū)、微小區(qū)和家庭小區(qū)。用戶位置在小區(qū)覆蓋區(qū)域滿足均勻分布，基站的分布位置預(yù)先固定，信道滿足瑞利分布。部分仿真參數(shù)如表2所示。

小區(qū)的分布如圖3所示，本節(jié)的對比算法有最大信干噪比法（Max SINR）以及基于偏置的信干噪比法。Max SINR法選擇具有最大信干噪比的基站接入作為用戶歸屬準(zhǔn)則?；谄玫姆椒▌t定義SINR′nk=Cn·SINRnk，其中 SINRnk代表用戶k從基站n處的信干噪比，用戶歸屬準(zhǔn)則為接入到具有最大偏置信干噪比SINR′nk的基站，Cn為小區(qū)的偏置因子。本節(jié)中為3層小區(qū)選擇的偏置為[0,6,12]dB。對比算法按照固定頻率復(fù)用方案進(jìn)行資源分配。

表2 基本仿真參數(shù)

圖3 異構(gòu)網(wǎng)絡(luò)小區(qū)分布圖

3.1 算法收斂性

本文的進(jìn)行了20 000次的迭代實(shí)驗(yàn)，研究了算法的收斂性。

圖4 算法的收斂性

從圖4可以看出，在滿足約束的基礎(chǔ)上，經(jīng)過10 000次迭代后，目標(biāo)函數(shù)的值基本不變。隨著迭代次數(shù)的增加，系統(tǒng)趨于穩(wěn)定，由此驗(yàn)證了算法的收斂性和有效性。

3.2 頻率復(fù)用方案

通過迭代求解出聯(lián)合分配矩陣X之后，可以從X中得到整個(gè)系統(tǒng)的頻率復(fù)用情況，即每個(gè)資源塊被復(fù)用的次數(shù)。表3中的結(jié)果顯示了資源塊（Physical Resource Blocks，PRBs）數(shù)目為600、用戶數(shù)為200時(shí)每個(gè)基站使用的資源塊的數(shù)目。從表4統(tǒng)計(jì)結(jié)果可以看出，所有基站使用的資源塊數(shù)目的總和是實(shí)際PRBs數(shù)目的近4倍。算法顯著提高了頻率復(fù)用率，擴(kuò)大了系統(tǒng)容量，提升了用戶性能。

表3 200用戶時(shí)各基站頻率復(fù)用情況

表4 200用戶時(shí)頻率復(fù)用率

3.3 用戶平均速率

為了公平，采用用戶的平均速率進(jìn)行比較，分別針對改變用戶數(shù)和改變資源塊數(shù)目兩種情況進(jìn)行仿真。從圖5可以發(fā)現(xiàn)，當(dāng)總資源塊數(shù)一定(NB=1 000)的情況下，用戶的平均速率隨著總用戶數(shù)的增加隨之下降，本文提出方案的速率始終高于其他兩種方案。當(dāng)用戶數(shù)為300時(shí)，SINR bias算法已經(jīng)無法滿足用戶速率最低要求進(jìn)行分配，而Max SINR算法在用戶數(shù)為250時(shí)已經(jīng)無法進(jìn)行資源分配。本文的算法仍然可以進(jìn)行分配，主要是利用了資源塊之間的頻率復(fù)用關(guān)系。從兩圖的右坐標(biāo)軸可看出，頻率復(fù)用率隨著用戶數(shù)目增加而自適應(yīng)增大。

圖5 用戶平均速率與總用戶數(shù)的關(guān)系

當(dāng)用戶數(shù)一定(K=200)的情況下，從圖6可以看出，用戶平均速率隨著資源塊數(shù)目的提升隨之上升，本文提出的算法用戶平均速率始終在其余兩種算法之上。當(dāng)資源塊數(shù)目較少時(shí)，Max SINR算法與SINR bias算法分別在數(shù)目600與500時(shí)無法滿足用戶需求進(jìn)行分配，但本文算法仍然可以進(jìn)行分配，證明了本文算法的優(yōu)異性。隨著資源塊數(shù)目的減少，頻率復(fù)用率逐漸增大。

圖6 用戶平均速率與總資源塊數(shù)的關(guān)系

3.4 用戶非均勻分布

本文還對用戶非均勻分布情況進(jìn)行了仿真，如圖7所示，用戶主要集中在不同微基站周圍的熱點(diǎn)區(qū)域。

仿真結(jié)果如圖8、圖9所示，分別是針對固定資源塊數(shù)目為1 000改變用戶數(shù)目以及固定用戶數(shù)目為200改變資源塊數(shù)目的情況下的仿真。仿真表明，在用戶非均勻分布的情況下，本文算法仍然能夠達(dá)到比對比算法更高的用戶速率，同時(shí)能夠得到頻率復(fù)用方案和自適應(yīng)的頻率復(fù)用率，證明了本文算法的有效性。

圖7 非均勻分布用戶

圖8 用戶平均速率與總用戶數(shù)的關(guān)系

圖9 用戶平均速率與總資源塊數(shù)的關(guān)系

4 結(jié) 語

本文提出了一種異構(gòu)蜂窩網(wǎng)絡(luò)的資源分配算法。為了提高系統(tǒng)容量，將資源分配與用戶歸屬問題一同考慮，但該問題被證明為NP-hard問題難以求得精確解。本文基于自動微分方法，對聯(lián)合分配數(shù)組利用梯度下降算法迭代計(jì)算出可行解，同時(shí)可從聯(lián)合分配數(shù)組中得到動態(tài)頻率復(fù)用方案。最后，利用仿真驗(yàn)證了算法的收斂性和有效性。與最大信噪比和信噪比偏置方案相比，該方法具有更高的系統(tǒng)吞吐量。