王雪，劉京，孫佳妮，張繼真，錢志鴻

（1.吉林大學通信工程學院，吉林 長春 130012；2.中國科學院長春光學精密機械與物理研究所，吉林 長春 130033）

1 引言

隨著5G 通信系統(tǒng)的發(fā)展，越來越多的智能連接設備帶來了指數(shù)級的網(wǎng)絡流量增長。傳統(tǒng)的頻譜管理方案和蜂窩結構已經(jīng)不能滿足激增的流量需求[1-2]。傳統(tǒng)蜂窩結構通過宏基站覆蓋通信用戶，針對宏基站的占地面積大、部署基建成本高昂且不能保障小區(qū)邊緣用戶的服務質(zhì)量等難題，超密集異構蜂窩網(wǎng)絡（UDN，ultra-dense heterogeneous cellular network）在這種背景下應運而生[3]。5G 關鍵技術的目標之一是使移動數(shù)據(jù)量達到當前長期演進（LTE，long term evolution）系統(tǒng)的1 000 倍，而UDN正是實現(xiàn)此目標的關鍵技術之一[4]。UDN 通常由大量不同類型的低功率小型基站（BS，base station）組成，其部署密度遠高于當前的移動通信網(wǎng)絡，遍布車站、商場和辦公樓等熱點區(qū)域，或信號難以到達的陰影區(qū)域，可以大幅提高流量容量和數(shù)據(jù)的傳輸速率[5]。但是，UDN 不斷增加的網(wǎng)絡規(guī)模勢必會帶來越來越嚴重的小區(qū)干擾，因此緩解干擾并尋找有效的資源分配方案來提高系統(tǒng)性能，逐漸成為UDN 的關鍵問題之一，且受龐大的計算復雜度限制，傳統(tǒng)有效的資源分配難以直接利用在UDN 之中[6-8]。

為了解決UDN 場景資源緊缺的問題，文獻[9]提出了一種基于服務質(zhì)量的UDN 跨層合作傳輸方案，定義了宏基站和微基站的發(fā)射功率之比的協(xié)作信噪比閾值，并利用隨機幾何理論分析了其對信號數(shù)目的影響，從而優(yōu)化了子載波分配和功率分配，減輕了干擾并提高整個網(wǎng)絡的吞吐量。除此之外，采用聚類分析的資源分配方案逐漸展現(xiàn)出優(yōu)勢，可以通過把微基站分簇成數(shù)個子網(wǎng)絡，大大簡化網(wǎng)絡拓撲，從而有效降低UDN 資源分配的復雜度[10]，同時也更方便研究降低基站間干擾的問題，提高了算法的可行性。文獻[11]提出了一種基于圖著色的集群資源分配算法，將控制平面和用戶計劃分開，有效地利用宏基站節(jié)點向用戶分配資源。文獻[12]考慮實際場景中的鄰域關系，提出了一種圖聚類方案，并將每個小區(qū)簇中的用戶設備分組，為每個用戶組分配子信道實現(xiàn)干擾降低。文獻[13]使用改進的基站聚類算法，根據(jù)基站的密度動態(tài)調(diào)整聚類的數(shù)量，同樣將用戶設備劃分為多個組，通過資源分配使用戶集群內(nèi)干擾最小。文獻[14]則在通過構建用戶沖突圖提出一種低復雜度的用戶聚類將用戶分組，并考慮在用戶簇間的干擾提出一種子信道分配算法，可以進一步減少頻譜復用帶來的干擾。文獻[15]提出一種新穎聚類算法，可以通過甄別信道獨特的特點，將二級用戶分組進行資源分配來提高集群的吞吐量。雖然聚類分析方案具有一定優(yōu)勢，但是現(xiàn)階段基于聚類分析的資源分配方案研究大多是從地理位置上進行基站分簇，并且很少抓住用戶之間的干擾關系進行用戶分組來進行信道劃分。因此，十分有必要改進聚類分析模型，實現(xiàn)在頻率資源分配階段弱化同頻干擾，提高系統(tǒng)性能。

超密集異構蜂窩網(wǎng)絡不僅面臨頻率資源緊張的問題，而且龐大數(shù)量的通信設備所帶來的功耗問題也變得更加嚴重，綠色通信已成為下一代網(wǎng)絡的主要追求目標[16]，因此需要將研究重點從追求提高數(shù)據(jù)速率和容量轉(zhuǎn)移到提高能量效率上，能量效率也逐漸成為新的系統(tǒng)性能指標。文獻[17]推導驗證了以用戶為中心的異構蜂窩網(wǎng)絡中整個網(wǎng)絡的能量效率表達式，為提高網(wǎng)絡的能量效率、達到綠色通信的網(wǎng)絡部署提供了理論指導。文獻[18]提出了一種基于聚類的節(jié)能資源管理方案來減輕干擾，基于兩步子信道分配和基于非合作博弈的功率分配方案來最大化網(wǎng)絡能量效率。文獻[19]提出應用兩級子信道分配算法和基于對數(shù)函數(shù)的功率控制方案在保證系統(tǒng)能效的同時，有助于提高系統(tǒng)的吞吐量和頻譜效率。但是受限于龐大的基站數(shù)目，這些能量效率優(yōu)化方法在異構超密集網(wǎng)絡下并不具備良好的適應性。

因此，面對超密集異構網(wǎng)絡亟待解決的能量效率問題，在密集部署的基站場景中，需要結合聚類分析資源分配方案簡化模型的優(yōu)勢，改進聚類分析模型，削弱同頻干擾，合理進行功率分配來有效提高系統(tǒng)能效?；诖?，本文在下行兩層異構蜂窩超密集網(wǎng)絡模型下，研究非凸、非線性、多變量耦合的能效優(yōu)化問題，主要的創(chuàng)新性工作如下。

1) 建立頻率資源分配子問題模型，從頻率資源分配過程中基站、用戶、資源塊3 個層面改進聚類分析模型，分別對應提出了改進的k-means 算法對通信網(wǎng)絡內(nèi)的微基站分簇，定義了局部基站分布密度概念，自適應動態(tài)劃分基站簇大小和聚類中心的位置，極大降低簇間干擾；結合信道損失構建用戶干擾關系權重圖，提出了基于譜聚類算法的基站簇內(nèi)用戶分組策略，快速高效地得到同頻干擾差異用戶組；結合貪婪資源塊分配算法為不同的用戶組分配正交的頻率資源，有效削弱了簇內(nèi)干擾。

2) 針對較大基站數(shù)量模型下的功率適配問題，以優(yōu)化能效為目標建立功率資源分配子問題模型，利用Dinkelbach 方法將分式非凸問題轉(zhuǎn)換為凸函數(shù)約束尋優(yōu)問題，結合拉格朗日乘子數(shù)學理論算法的精確高效等優(yōu)勢，創(chuàng)新性應用于UDN 多基站模型，推導并解決多基站模型下的功率迭代表達式，得到各基站各資源塊下的最佳功率，對每個基站簇內(nèi)的功率進行合理分配。仿真結果表明，本文算法具有很好的收斂性，并且在提升異構蜂窩超密集網(wǎng)絡的能效方面具有良好的性能。

2 系統(tǒng)模型

本文考慮兩層異構蜂窩下行超密集網(wǎng)絡，即在網(wǎng)絡中含有一個中心宏蜂窩基站（MBS,macro base station）和多個微蜂窩基站（FBS,femto base station），如圖1 所示。宏基站節(jié)點和所有的微基站節(jié)點全部連接到一個局域網(wǎng)關服務器中，通過這個服務器作為中心控制器管理調(diào)度整個網(wǎng)絡的資源分配任務。所有微基站用集合F 表示，即F={1,…,f,…,F}，為了模擬實際的應用場景，微基站被隨機地分布在二維歐氏空間A 中，構造密度為λf的齊次泊松點過程（HPPP,homogeneous poisson point process）[2]，同樣，戶外的用戶設備（UE,user equipment）按照密度為λout的HPPP 隨機分布在空間A 中，其中MBS 直接覆蓋范圍Rmac內(nèi)的宏用戶，用集合Im表示，其余的UE 把距離最近的微基站作為各自提供通信服務的基站，所有由微基站服務的UE 用集合If表示，即 I={1,…,i,…,I}。

圖1 異構蜂窩超密集網(wǎng)絡模型

考慮異構蜂窩下行鏈路所有的FBS 復用同一個頻譜，基站節(jié)點到UE 建立瑞利信道衰落模型，可以將每個頻譜均分成K個正交的資源塊（RB,resource block），資源塊的集合可以表示為K={1,…,k,…,K}。假設一個RB 最多被安排給一個UE 使用，并且在信號覆蓋區(qū)域內(nèi)，復用同資源塊的UE 在通信中會產(chǎn)生干擾，而采用不同資源塊的UE 由于資源塊之間是正交的，故在通信中不會產(chǎn)生干擾。

針對下行鏈路的通信過程，對于小區(qū)中的每一個宏基站用戶i來說，其通信業(yè)務由宏基站直接提供服務，并且單獨復用一個頻段，不與微基站頻段產(chǎn)生重疊，因此，用戶i在宏基站m服務下資源塊k上的信號與干擾加噪聲比（SINR,signal to interference plus noise ratio）可以表示為

對于復用另外頻段的微基站的用戶i，其在微基站f服務下資源塊k上的SINR 為

其中，表示微基站f在資源塊k上的發(fā)射功率，Gf,i表示從微基站f到用戶i之間的信道增益，If,k表示由微基站f提供服務且采用資源塊k的用戶。

進一步地，可以得到宏基站用戶和微基站用戶的在資源塊k上的傳輸速率為

其中，B表示每個資源塊上的帶寬。定義二進制布爾變量表示用戶i是否復用宏基站m或微基站f的資源塊k，即

整個網(wǎng)絡的吞吐量可以表示為

其中，P 表示每個基站的功率可行域。

對于每個基站的功率消耗問題，可以分為2 個部分，即傳輸功率和電路功率[20]，在下行傳輸過程中，系統(tǒng)的總功率消耗可以定義為

其中，Pcir,m和Pcir,f分別代表單個宏基站和單個微基站的電路功率。

因此，整個網(wǎng)絡的能量效率可以定義為網(wǎng)絡總吞吐量與總功率消耗的比值，通過優(yōu)化資源塊和功率的分配方案，可以將最大化能量效率的優(yōu)化問題表示為P1。

其中，約束條件C1、C2、C6、C7 表示資源塊僅能分配給一個用戶，且一個用戶只能被分配一個資源塊；約束條件C3、C4 表示被分配的功率不能是負值；約束條件C5 表示分配給所有用戶的功率總和不能超過當前基站的負荷。

3 基于譜聚類分析的UDN 資源分配方案

通過分析異構超密集蜂窩模型可以看出，尋找解決數(shù)量更多的微基站的資源分配問題的方案，是提高系統(tǒng)網(wǎng)絡能量效率的重點，因此本文主要以微基站資源分配算法分析為主。

從式(8)可以看出，同時優(yōu)化頻率資源塊X和功率P的分配方案是一個難以直接解決的NP-hard 問題[21]。為了在合理的復雜度內(nèi)解決資源分配的問題，原問題可以分解為資源塊分配和功率分配2 個子問題。盡管如此，從超密集異構蜂窩網(wǎng)絡的大量微基站中搜集分析資源分配的策略和信息仍舊是一個很大工作量的難題，因此，本文針對性地提出基于能效的聚類分組的資源分配方案，該方案可從聚類分組層面和資源分配層面進行分析。

由現(xiàn)狀分析可知，改進并利用聚類分析模型可簡化網(wǎng)絡拓撲，從而有效降低UDN 的資源分配的復雜度，本文從基站分簇和用戶分組兩部分改進聚類分組層面模型，首先，針對現(xiàn)有常用k-means 聚類算法難以確定聚類中心數(shù)目及位置的不足，本文采用改進的k-means 算法，引入密度篩選前置過程，對蜂窩小區(qū)中的微基站進行自適應分簇，將相互間干擾最大的基站分成一個簇，使簇間干擾盡可能降至最小，甚至忽略不計。接著，為了降低基站簇內(nèi)的干擾，針對現(xiàn)有基于聚類分析的資源分配方案研究多從地理位置上進行基站分簇，很少抓住用戶之間的干擾關系進行用戶分組來進行信道劃分的不足，本文利用譜聚類算法，在發(fā)揮降維分組優(yōu)勢的同時，結合用戶之間的干擾關系，對基站簇內(nèi)的用戶進行分組，將相互影響較小的用戶分為一組，為其分配同一資源塊，而不同的用戶組則分配正交的頻率資源塊，避免不同用戶組之間產(chǎn)生干擾。通過提出改進k-means 基站分簇與譜聚類用戶分組策略，從物理位置與個性化干擾關系上詳盡分析并區(qū)分了干擾類別，盡可能地降低簇間干擾與簇內(nèi)干擾。資源分配層面包含頻率資源分配和功率資源分配。首先，在基站分簇與用戶分組之后，正如用戶分組的目的，將正交的資源塊按照貪婪算法分配順序分給不同的用戶組，降低簇內(nèi)干擾。頻率資源塊分配完成后，在功率分配階段，以能量效率為目標，采用Dinkelbach 方法將能量效率的非凸優(yōu)化問題轉(zhuǎn)化為凸問題，同時結合聚類方法，利用拉格朗日乘子法迭代求解大數(shù)量基站功率分配的約束尋優(yōu)問題。

由此，通過執(zhí)行改進的k-means 微基站分簇算法、譜聚類的用戶分組算法、正交資源塊分配以及基于Dinkelbach 和拉格朗日乘子法聯(lián)合功率分配算法四步順序性過程，實現(xiàn)了網(wǎng)絡能效最優(yōu)的UDN資源分配方案。

3.1 基站分簇問題

傳統(tǒng)的k-means 算法簡單易行，收斂速度快，且常以歐幾里得距離作為相似性度量，從而基于一些預定聚類中心獲得最佳分類聚類[22]。通常情況下，微基站往往會對鄰近的其他微基站產(chǎn)生較強的干擾，因此將這些基站分到同一個基站簇內(nèi)，然后給它們安排正交的資源塊從而減少簇內(nèi)干擾。鑒于存在相互干擾的基站之間往往距離很小，為了準確地對微基站進行聚類，本文引入局部分布密度代替距離來評估微基站的靠近程度。首先定義微基站j的分布密度λj為所有微基站兩兩距離之和與微基站f到所有其他基站的距離之和的比值，即

其中，dj,k和dm,n皆表示2 個微基站之間的距離，顯然，越多的微基站位于微基站j附近，其分布密度就越大。

特別地，為了避免區(qū)域邊界較遠的基站之間距離的值對分布密度計算產(chǎn)生的誤差，本文引入截斷距離dtr，可依據(jù)區(qū)域范圍、仿真分簇結果以及經(jīng)驗數(shù)據(jù)設置，忽略超過截斷距離的基站間距離，即，則局部分布密度可以更新為

在局部分布密度的基礎上，利用本文提出的改進k-means 基站聚類算法，定義所有微基站的平均分布密度為

首先，計算整個蜂窩小區(qū)中所有微基站的分布密度及小區(qū)平均分布密度，選出密度高于平均密度的基站，將它們的位置點坐標加入聚類中心候選集C。至此，在聚類中心候選集中，存在聚類中心較接近的情況，這不利于k-means 聚類，為進一步篩選，定義距離閾值為

其中，μ是調(diào)整聚類大小的比例系數(shù)，隨基站密度動態(tài)變化，可設置為關聯(lián)于實際應用場景范圍、用戶密度的系數(shù)函數(shù)，依照實際場景和經(jīng)驗調(diào)整系數(shù)。當聚類中心候選集中某2 個點坐標的距離小于距離閾值Rc時，需要對2 個點對應的微基站的分布密度進行比較，選取較大點進行保留，將較小點從聚類中心候選集中移除，如二者相等，則任意保留其中一個。遍歷所有點之后，最終得到的聚類中心候選集中的坐標，即為k-means 聚類的初始聚類中心點的位置。根據(jù)初始聚類中心和微基站之間的距離，采用k-means 聚類算法最終得到基站簇的聚類結果。詳細的聚類過程執(zhí)行步驟如算法1 所示。

算法1改進k-means 基站分簇策略算法

初始化依據(jù)式(9)～式(11)計算每個微基站的局部分布密度λ'和平均分布密度；依據(jù)式(12)及實際需求，計算閾值距離Rc；微基站待選集F，聚類中心候選集C；

圖2 展示了2 種不同數(shù)量微基站場景下，執(zhí)行算法1 中改進k-means 基站分簇策略后的聚類結果示意。其中，微基站和用戶皆按照HPPP 隨機分布。由圖2 可知，宏基站處在區(qū)域正中央，其近區(qū)域覆蓋范圍內(nèi)的用戶接收到的宏基站信號較強，故采取直接由宏基站服務的策略，微基站依據(jù)動態(tài)選取的聚類中心被劃分為多個基站簇，除受宏基站服務的用戶外，其余隨機分布的用戶按照基站簇的范圍歸入不同的基站簇并由該簇內(nèi)的微基站服務。圖2(a)和圖2(b)分別展示了隨機部署微基站的數(shù)量為63 個和243 個時的分簇劃分情況。從圖2 中可以看出，當微基站的數(shù)目變多時，聚類中心即基站簇的數(shù)目也在增加，這是因為所提基站分簇算法可以動態(tài)調(diào)整基站簇的數(shù)目，并且每個基站簇內(nèi)的微基站數(shù)分布較平均。

圖2 隨機部署基站分簇示意

3.2 用戶分組問題

由于存在頻率復用，在每個基站簇內(nèi)，同一頻率下還是會存在很強的干擾。為了最大限度地降低簇內(nèi)干擾，在基站簇內(nèi)為用戶分配使用正交的頻率資源。但由于用戶數(shù)目較多，為減少算法復雜度，本文提出一種基于譜聚類[23-24]的用戶分組算法，其本質(zhì)是一個切割無向權重圖，強化子圖內(nèi)部相似度、弱化子圖間相似度的過程，且其求取特征向量降維的過程常常用在高維聚類中，十分適用于本文的用戶分組場景中，使干擾較小的用戶成為一組，為不同的用戶組分配正交的資源。

首先，在異構蜂窩網(wǎng)絡中，以其中一個基站簇為例，基站簇中的所有微基站用集合Fc= {1,2,…,Fc}表示。將宏蜂窩用戶和微蜂窩用戶看作圖的頂點，構造一個無方向權值連接圖 G((V,E)，向量集合V= {v1,v2,…,vn}表示當前基站簇內(nèi)的用戶集合，E表示連接頂點的邊的集合，即點與點之間的關聯(lián)矩陣，本文根據(jù)基站簇內(nèi)的用戶之間的信道干擾代替?zhèn)鹘y(tǒng)的點點之間的歐氏距離建立邊集。

假設用戶a,b都受基站簇內(nèi)微基站服務，首先定義用戶a,b的相關信道損失值β分別為

其中，微基站i指代的是為用戶傳輸信號的基站，微基站j指代的是基站簇中除傳輸信號基站外的其他基站，這些基站產(chǎn)生的信號會對用戶產(chǎn)生干擾，pl為信道損失[25]。顯然，相關信道損失值反映了微基站在基站簇中信道表現(xiàn)的情況，β值越小，代表傳輸有用信號的信道質(zhì)量較好，有干擾的信道影響較小，更有利于信號的傳輸。

然后，需要建立關聯(lián)矩陣，即構造一個無方向權值連接圖G 的邊集，利用提出的相關信道損失值β的概念，定義權重邊值為

其中，w為譜聚類算法中相似度矩陣中元素。

根據(jù)式(15)，構建兩用戶之間的相似度關聯(lián)矩陣

且規(guī)定相似度矩陣的每行元素的和為該頂點的度，故損失干擾圖G 的度矩陣為，其中，，定義圖G 的非規(guī)范化拉普拉斯矩陣為L=D?W，對矩陣L進行規(guī)范化處理，得到規(guī)范化拉普拉斯矩陣

最后，計算矩陣Lsym前K個最小特征值所對應的特征向量v={v1,v2,…,vK}，并定義v作為第一矩陣，即，接著規(guī)范化第一矩陣U1的每一行，得到第二矩陣

利用k-means 算法對矩陣U2進行聚類，得到用戶組分組結果。至此，完成聚類分組層面的過程。詳細的譜聚類過程執(zhí)行步驟如算法2 所示。

算法2譜聚類用戶分組策略算法

初始化計算基站簇內(nèi)所有用戶到所有基站的信道損耗pl，依據(jù)式(13)～式(16)初始化無方向權值連接圖 G(U,E)；隨機初始化m個聚類中心；

1) 依據(jù)式(17)計算得到規(guī)范化拉普拉斯矩陣Lsym；

2) 計算矩陣Lsym前K個最小特征值所對應的特征向量v={v1,v2,…,vK}；

4) 利用k-means 算法對矩陣U2進行聚類；

5) 重復執(zhí)行步驟4)的k-means算法直至聚類中心不再發(fā)生變化；

6) 返回用戶組聚類結果。

3.3 資源塊分配問題

完成聚類分組層面的過程之后，將進行資源分配層面的步驟，首先要對正交的資源塊進行合理的分配。本文采用貪婪算法的思想，依據(jù)信道增益為各個用戶組分配滿足其吞吐量最大的相互正交的資源塊，最終得到整個系統(tǒng)的頻率資源分配方案。詳細的資源塊分配過程執(zhí)行步驟如算法3 所示。

算法3資源塊分配策略算法

初始化按照用戶組GU 中包含用戶的數(shù)量進行用戶組的降序排序，得到用戶組排序集合；剩余資源塊集合L；

3.4 功率分配問題

完成頻率資源塊分配后，雖然平均分配資源塊功率簡便易行，但在利用不均的資源塊上分配相同的功率，無疑增加了功率的浪費，明顯不能適合高能效的性能目標，因此本文以能量效率為目標，優(yōu)化功率分配。由于超密集異構網(wǎng)絡中的微基站數(shù)量眾多，統(tǒng)一控制所有基站的功率分配是不切實際的。功率分配算法[26]雖能交替求解增廣拉格朗日函數(shù)中的每個變量，解決單個基站能效目標函數(shù)中多變量的優(yōu)化問題，較適合應用在分布式結構網(wǎng)絡中，但是在集中覆蓋的超密集網(wǎng)絡功率分配問題上，集中控制的全局調(diào)控十分必要，對于整個網(wǎng)絡的能效提升更加有效；拉格朗日乘子方法作為傳統(tǒng)有效的凸優(yōu)化解決方法，解決全局最優(yōu)問題便捷，但無法直接移植應用在高維度的密集場景中，且現(xiàn)有研究尚未結合聚類方法應用在密集復雜的場景模型中。因此，本文通過結合前文聚類結果，利用拉格朗日乘子方法給每個基站簇分配功率以最大化其自身的能量效率，在降低總體復雜度的同時，提高整個系統(tǒng)的能效。

結合基站分簇的結果，以其中一個基站簇為例，在基站簇的范圍內(nèi)，所有的微基站用集合Fc={1,2,…,fc,…,Fc}表示，分配可用的資源塊用集合 Kc= {1,2,…,kc,…,Kc}表示，所有的用戶用集合Ic= {1,2,…,ic,…,Ic}表示。對于微基站fc復用資源塊kc的用戶ic，結合上文系統(tǒng)干擾模型可知，微基站fc的SINR 表示為

用戶ic的傳輸速率為

基站簇內(nèi)的總吞吐量為

其中，Pc是基站簇待分配功率的可行域。

在下行傳輸過程中，基站簇系統(tǒng)的總功率消耗可以定義為

因此，整個基站簇網(wǎng)絡的能量效率可以定義為網(wǎng)絡的總吞吐量與網(wǎng)絡總功率消耗的比值，通過優(yōu)化功率分配方案，可以將最大化能量效率的優(yōu)化問題表示為P2。

其中，約束條件C1、C4 表示資源塊僅能分配給一個用戶，且一個用戶只能被分配一個資源塊；約束條件C2 表示被分配的功率不能是負值；約束條件C3 表示分配給所有用戶的功率總和不能超過當前基站的負荷。

從結構中可以看出，P2 是一個混合整數(shù)非線性分數(shù)規(guī)劃問題，難以在一個多項式時間中求解[27]。首先，本文采用Dinkelbach 算法[28]將能量效率的非凸優(yōu)化問題轉(zhuǎn)化為凸問題。定義q*為P2 的最優(yōu)解，即則優(yōu)化能效的P2 可以看作

當且僅當q=q*時，有

因此，問題P2 可以等同轉(zhuǎn)化成一個減式形式問題P3。

記Dinkelbach 迭代的索引和最大迭代次數(shù)分別為n∈ {1,2,…,Iouter}和Iout。假設在第n次迭代中，計算的功率值和q值分別表示為和q(n)，定義拉格朗日函數(shù)為

根據(jù)KKT（Karush-Kuhn-Tucker）條件，可以求得最優(yōu)解

拉格朗日乘子更新為

其中，τ∈ {1,2,…,Iinner}表示拉格朗日乘子的迭代次數(shù)，Iinner為拉格朗日對偶分解的最大迭代次數(shù)；δ表示迭代更新時每次變化的步長。具體功率分配算法過程如算法4 所示。

算法4基于Dinkelbach 和拉格朗日乘子方法的功率分配策略算法

初始化初始化外循環(huán)索引n，內(nèi)循環(huán)索引τ,優(yōu)化因子q(0)；拉格朗日乘子θ；最大迭代次數(shù)Iouter,Iinner；功率初值；收斂偏差 Δ1,Δ2；

4 復雜度分析

本文提出的能效優(yōu)化算法由4 個部分組成，分別是微基站分簇過程、用戶分組過程、資源塊分配過程和功率分配過程。對于微基站分簇過程，采用改進的 k-means 算法，最大復雜度為O(2F2+FC nn)，其中，O(2F2)是最差情況下計算F個微基站分布密度、確定聚類中心過程的復雜度，O(FC nn) 是k-means 聚類算法的復雜度，Cn是基站聚類中心的數(shù)目，即基站簇的數(shù)目，n是k-means聚類算法的迭代次數(shù)。用戶分組過程采用譜聚類算法，在每一個基站簇中，最大復雜度為O(K c2t)，其中Kc既是資源塊的數(shù)目，也是用戶組的數(shù)目，譜聚類算法只取前Kc最小特征值所對應的特征向量構建關系矩陣進行k-means 聚類，t是對應的迭代次數(shù)。資源塊分配過程的最大復雜度為。功率分配過程的最大復雜度為O(FcK cIouterIinner)，其中，Iouter和Iinner分別為外循環(huán)和內(nèi)循環(huán)的最大迭代次數(shù)。因此，整體上完成基站分簇，并在每個基站簇內(nèi)分別完成資源分配最大化能量效率，所提資源分配方案的最大復雜度為。

對于整個異構蜂窩超密集網(wǎng)絡，在不進行基站分簇以及用戶分組的情況下，直接進行資源分配方案的最大復雜度應為O(FKI+FKIouterIinner)，其中，F(xiàn)?Fc。因此可以看出，隨著基站密度增加，盡管在本文所提方案中的基站分簇和用戶分組過程引入了一些算法的復雜性，但它們實現(xiàn)了動態(tài)分配聚類中心，簡化了網(wǎng)絡分析拓撲結構，有效地弱化了同頻干擾，并且降低了UDN 場景下資源分配的計算復雜性，基站密度越大，所帶來的復雜度優(yōu)化越明顯。

5 仿真分析

本文進行了超密集異構蜂窩網(wǎng)絡的仿真驗證，對所提通過降低干擾和優(yōu)化能效的資源分配方案的有效性進行了分析，在300 m×300 m 的仿真UDN覆蓋范圍中，經(jīng)過多次仿真參數(shù)調(diào)試，最終確定了改進k-means 基站分簇算法中截斷距離dtr和比例系數(shù)μ的取值，具體設置和環(huán)境參數(shù)取值如表1所示。

表1 仿真參數(shù)

本文提出的基于譜聚類的異構蜂窩超密集網(wǎng)絡高能效資源分配方法包括基站分簇、用戶分組、資源塊分配、功率分配4 個過程，具體對應第3 節(jié)中所陳述的4 種算法，即算法1 改進k-means 基站分簇策略算法，算法2 譜聚類用戶分組策略算法，算法3 資源塊分配策略算法，算法4 基于Dinkelbach和拉格朗日乘子方法的功率分配策略算法。將所提方案與其他6 種資源分配方案進行對比，在單一環(huán)節(jié)上采用不同算法，從而形成差異的資源分配方案，比較不同算法在不同通信環(huán)節(jié)中的性能差異，具體資源分配方案如表2 所示。方案S2、S3 著重對比用戶分組和資源塊分配算法性能，方案S4、S5、S6、S7 對比了不同功率分配算法下的性能。其中，采用了文獻[15]中的依照信道損失值建立用戶間聯(lián)系，利用k-means 對二級基站用戶預分組算法（以下簡稱KMUG 算法）；文獻[13]中的2 種對比算法，分別為直接隨機為每個用戶復用資源塊的隨機分配算法（以下簡稱RARB 算法）和將微基站可用功率平均等分給每個資源塊的平均功率分配算法（以下簡稱AGPA 算法）；文獻[26]中的基于交替方向乘子方法的資源塊功率分配算法，本文場景中，在每個基站簇內(nèi)以每個基站的能量效率為優(yōu)化目標函數(shù)，交替求解增廣拉格朗日函數(shù)中每個基站資源塊上的功率（以下簡稱ADMM 算法）。

表2 資源分配方案

圖3 給出了單個基站簇不同用戶數(shù)目下分別采用譜聚類和k-means 聚類的基站平均分簇時間。隨著基站簇內(nèi)用戶數(shù)目的不斷增多，k-means 聚類算法的時間在不斷增加，而本文的譜聚類算法在用戶數(shù)目較多時也能保持高速分簇，但在用戶數(shù)目相對較少時，每個用戶的關聯(lián)性不高，求解的特征向量矩陣相對復雜，故曲線上存在一個下降的趨勢，隨著用戶數(shù)目增多，受限于地理位置，用戶間的關聯(lián)性越來越明顯，曲線趨于穩(wěn)定。這是因為譜聚類算法是一種基于圖論的聚類方法，通過對樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進行聚類，從而達到對樣本數(shù)據(jù)聚類的目的，可以理解為將高維空間的數(shù)據(jù)映射到低維，然后在低維空間用其他聚類算法進行聚類，這種降維的方式在處理大數(shù)據(jù)時可以明顯提高效率，大大縮短計算時間。

圖3 用戶分組時間與基站簇內(nèi)用戶個數(shù)的關系

平均功率分配狀態(tài)下，圖4 給出了在進行基站分簇和用戶分組后不同微基站密度下的網(wǎng)絡吞吐量。從圖4 中可以看出，隨著微基站密度的增大，網(wǎng)絡的吞吐量基本呈上升趨勢，這是因為布置大量的微基站可以有效兼顧每個用戶，從而提高網(wǎng)絡的吞吐量。同時，可以看到，所提的譜聚類用戶分組算法在進行資源分配后，對吞吐量的提升明顯優(yōu)于k-means 聚類算法和隨機分配算法。另外，方案S4 和S5 的曲線都要優(yōu)于方案S6，這是因為用戶分組在提升利用了信道損失構建關系矩陣，通過分組有效地降低了簇內(nèi)干擾，提高了網(wǎng)絡的吞吐量。方案S4 的曲線優(yōu)于S5，這是由于譜聚類算法在處理稀疏矩陣時更能抓住數(shù)據(jù)特征，用戶分組更加合理。

圖4 網(wǎng)絡吞吐量與基站密度的關系

為多方面驗證所提算法的收斂性，圖5 給出了所提功率分配算法過程中各基站簇與平均能量效率隨迭代次數(shù)的變化情況。其中，C1～C8 對應基站簇的編號。圖5(a)中每條曲線分別代表一個基站簇內(nèi)的功率分配過程，可以看出，受基站分簇的影響，不同基站簇內(nèi)的基站數(shù)和用戶數(shù)的不同影響了該基站簇的能量效率的大小，但每個基站簇的能量效率都在5 次迭代左右可以達到收斂。圖5(b)則是整個網(wǎng)絡的平均能量效率隨迭代次數(shù)的變化，同樣可以看出，平均能量效率在5 次左右達到穩(wěn)定，這也證實了本文提出的功率分配算法是收斂的。

圖5 平均能量效率與迭代次數(shù)關系

圖6～圖8分別給出了不同對比方案的系統(tǒng)平均能量效率隨基站密度的變化。從圖6 中可以看出，S4、S5、S6 這3 條曲線都為下降趨勢，這是因為在平均功率分配下，隨著基站密度的增加，吞吐量的提升是有限的，而傳輸能耗和電路能耗也在大幅增加，結合圖4 網(wǎng)絡吞吐量與基站密度的關系，在不受功率分配算法影響時，網(wǎng)絡吞吐量隨著微基站密度的增長逐漸變化不是很明顯，故在基站密度變化的整個過程，系統(tǒng)吞吐量的增益帶來能量效率的增益無法補償功耗增加帶來的負面影響，引起了系統(tǒng)能量效率的降低，其中方案S4、S5 要優(yōu)于方案S6，這是因為用戶分組算法有效降低了簇內(nèi)干擾，提高了網(wǎng)絡速率，進而提高了能量效率，而譜聚類算法效果要優(yōu)于k-means 聚類算法，故方案S4效果最好。

圖6 方案S4、S5、S6 的網(wǎng)絡平均能量效率與基站密度的關系

從圖7 中可以看出，方案S1、S7 的曲線呈現(xiàn)波動的趨勢，原因是本文所提算法中的自適應控制基站簇的數(shù)目變化時，影響了基站簇中基站和用戶的數(shù)量，故呈現(xiàn)出的能量效率會有突然的變化，但由于無法補償功耗不斷增加帶來的負面影響，總體上還是隨著基站的密度呈現(xiàn)下降的趨勢。S2 和S3則是呈現(xiàn)一種隨基站簇數(shù)目略顯波動的整體穩(wěn)定趨勢，這是因為在本文的仿真環(huán)境中，隨著微基站密度的不斷增大，基站間的干擾不斷增強，吞吐量的提升就變得有限，功率分配算法也會接近優(yōu)化能力的極限，導致能量效率不再上升，趨于穩(wěn)定，同樣，方案S1 與S7 在0.002 5 個/m2與0.0027 個/m2這2 個密度時，已經(jīng)開始出現(xiàn)接近能力飽和的趨勢，而方案S2 和S3 對應的資源塊分配算法由于避免干擾的能力有限，相較S1 和S7 對應的譜聚類分組資源塊分配算法提前達到了能力極限，并且隨著微基站密度不斷增加，所有方案算法上的優(yōu)勢最終會由于基站過于密集而弱化，能量效率會呈現(xiàn)出相近的狀態(tài)，算法帶來的優(yōu)勢不再明顯。對比S1、S2、S3、S7 這4 條曲線，方案S1、S2、S7 在能量效率上相較S3 均有明顯提升。這是因為功率分配算法不僅進一步降低了簇內(nèi)基站的干擾提高了吞吐量，同時還節(jié)省了功率，進而提升了能量效率。從S1 和S7的曲線明顯優(yōu)于S2 可以看出，譜聚類用戶分組算法的優(yōu)勢更加明顯，而S1 的曲線隨著基站密度的增加，逐漸接近并反超S7 曲線，這是因為ADMM算法雖能交替求解增廣拉格朗日函數(shù)中的每個變量，解決單個基站能效目標函數(shù)中多變量的優(yōu)化問題，但是因為每個基站的能量效率并不是面向全局調(diào)控的，所以在高基站密度下，其優(yōu)化能效表現(xiàn)不如本文所提算法。

圖8 將7 種資源分配方案的能效優(yōu)化情況放在一起對比，可以明顯看出，方案S1、S2、S3、S7這4 條曲線要遠高于S4、S5、S6 這3 條曲線，隨著微基站的密度越來越高，方案S1 的優(yōu)化效果最佳，Small Cell 論壇中提出超密集網(wǎng)絡的基站密度量化指標為室外場景中每平方千米部署150～1 000個小基站，對應的密度即0.000 15～0.001 個/m2。從圖8 中可以明顯看出，高于此范圍時S1 方案的效果是最優(yōu)的。除此之外，結合之前的結論，S1 方案對應的譜聚類用戶分組方案，其在分組效率上也優(yōu)于S2 方案對應的k-means 用戶分組方案，因此，雖然隨著基站密度增長，能量效率的優(yōu)勢不再明顯，但是綜合考慮能量效率和計算效率，S1 方案是更適合應用在高基站密度下的 UDN 場景的資源分配方案。

圖9 和圖10 分別給出了功率分配前后網(wǎng)絡平均能效（λf= 0.002 5個/m2）的累計分布函數(shù)曲線。從圖9 中可以看出，資源分配方案S4、S5 曲線在方案S6 右側，這表明采用用戶分組方案可以有效提高用戶效率；方案S4 在最右側也說明了譜聚類用戶分組算法的通過有效降低簇內(nèi)用戶干擾，明顯提高了網(wǎng)絡的能量效率。

從圖10 可以看出，在高密度的UDN 場景下，方案S1 能量效率提升的效果也要優(yōu)于方案S2、S3和S7。同時，對比圖9 中的數(shù)據(jù)可以看出，功率分配后網(wǎng)絡平均能效要遠優(yōu)于功率分配之前的能效，這是因為所提功率算法通過為不同基站上的不同資源塊分配恰當?shù)墓β剩粌H降低了同資源塊下的傳輸信號干擾，同時節(jié)省了功率，顯著提高了能量效率。

圖9 功率分配前網(wǎng)絡平均能效的累計分布函數(shù)曲線

圖10 功率分配后網(wǎng)絡平均能效的累計分布函數(shù)曲線

算法復雜度和仿真結果分析表明，本文所提組合方案將資源分配過程中基站、用戶、資源塊3 個層面以及功率分配過程各環(huán)節(jié)的算法相結合解決NP-hard 問題，在結合基站分簇與用戶分組降低算法復雜度和干擾的基礎上，利用功率分配實現(xiàn)能效提升。具體到各環(huán)節(jié)，本文所提資源分配方案在UDN 模型中，利用改進的k-means 基站分簇算法實現(xiàn)了動態(tài)分配初始聚類中心和聚類大小，有效降低了資源分配的計算復雜性，并且基站密度越大，所帶來的復雜度優(yōu)化越明顯；利用譜聚類用戶分組的資源塊分配算法，相較KMUG 用戶分組算法有效改善了簇內(nèi)干擾，極大提升了網(wǎng)絡總吞吐量，并且譜聚類算法通過對樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進行聚類，這種降維的思想大大節(jié)約了用戶分組的時間，提高了算法效率；采用基于Dinkelbach的拉格朗日功率分配算法，合理分配各基站資源塊上的發(fā)射功率，在節(jié)約功率消耗的同時，進一步削弱了同頻干擾，在高基站密度下，較ADMM 和AGPA 功率分配算法明顯提升了能量效率。但是，在動態(tài)調(diào)整基站簇大小時，會一定程度地影響基站簇中用戶的數(shù)量，造成能量效率的波動，這需要在未來工作中進行改善。

6 結束語

本文研究面向能效最優(yōu)的異構蜂窩超密集網(wǎng)絡資源分配方案，建立了下行兩層異構蜂窩超密集網(wǎng)絡模型，將超密集網(wǎng)絡資源分配這一非凸、非線性、多變量耦合的能效優(yōu)化NP-hard 問題，拆分成了以弱化同頻干擾的頻譜資源分配子問題和最大能效的功率資源分配子問題。在頻率資源分配方面，改進UDN 聚類分析模型，定義了基站分布密度，利用改進的k-means 算法為基站分簇，并結合信道損失構造干擾權重圖，提出了基于譜聚類的基站簇內(nèi)用戶分組策略，為不同的用戶組分配正交的資源，最大限度地降低簇間和簇內(nèi)干擾。在功率資源分配方面，利用Dinkelbach 方法將目標函數(shù)轉(zhuǎn)化為減數(shù)形式，創(chuàng)新性地將拉格朗日乘子法應用于大數(shù)量基站的功率與干擾特性的UDN 中，推導迭代求解公式，優(yōu)化資源塊分配功率，大大降低了同資源塊下的傳輸信號干擾，在一定程度上提高了廣泛部署微基站的能量效率，適合應用在高基站密度下的UDN 場景中。