分層組網(wǎng)場(chǎng)景下小基站ID分配算法研究

魏垚，韓斌

（1.中國(guó)電信股份有限公司廣州研究院，廣東 廣州 510630；2.中國(guó)電信股份有限公司技術(shù)創(chuàng)新中心，北京 100031）

1 引言

分層異構(gòu)組網(wǎng)技術(shù)是后4G時(shí)代用于增強(qiáng)網(wǎng)絡(luò)容量的重要手段。在LTE-B、LTE-C版本增強(qiáng)了組網(wǎng)技術(shù)的研究，其容量增益預(yù)測(cè)將遠(yuǎn)高于其他關(guān)鍵技術(shù)[1]。如圖1所示，小型化網(wǎng)絡(luò)節(jié)點(diǎn)將分層部署，六扇區(qū)裂變、HEW（High Efficiency WLAN）、C-RAN等新型無線接入和組網(wǎng)技術(shù)重疊覆蓋以增強(qiáng)室內(nèi)容量。然而，LTE系統(tǒng)中小區(qū)ID資源有限，過于密集的小基站組網(wǎng)對(duì)小區(qū)ID的規(guī)劃分配是新的挑戰(zhàn)。

圖1 分層異構(gòu)組網(wǎng)場(chǎng)景示意圖

LTE系統(tǒng)中采用物理小區(qū)標(biāo)識(shí)（PCI，Physical Cell Identity）區(qū)分小區(qū)[2]。與傳統(tǒng)的蜂窩無線通信系統(tǒng)不同，LTE系統(tǒng)不再采用小區(qū)半徑和基站距離來規(guī)劃ID，而使用鄰區(qū)關(guān)系作為判決單位：互為鄰區(qū)的兩個(gè)小區(qū)避免使用相同ID；一個(gè)小區(qū)避免同時(shí)與兩個(gè)相同ID的小區(qū)互為鄰區(qū)，即所謂的“沖突”和“混淆”[3]。在超密集的組網(wǎng)場(chǎng)景中，沖突和混淆是極易發(fā)生的，例如在一個(gè)半徑為500m的宏基站覆蓋下，不能同時(shí)存在配置相同ID的兩個(gè)小基站與宏基站互為鄰區(qū)，否則將發(fā)生“混淆”。

目前，PCI配置算法主要基于分布式的協(xié)商、復(fù)用熵以及地理位置信息等方法[4-5]。采用圖理論解決PCI配置問題也是常用的方法之一，一種啟發(fā)式的算法[6]將PCI配置問題轉(zhuǎn)化為圖著色問題，該算法通過將相鄰的小區(qū)用直線相連，然后為每個(gè)節(jié)點(diǎn)著色，凡是存在同一條邊相連的節(jié)點(diǎn)著不同顏色。該算法采用集中式的算法有效地避免了ID沖突和混淆問題。但是在網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化的情況下，仍然無法保證小區(qū)與第三級(jí)鄰區(qū)的沖突和混淆問題。因此，一種改進(jìn)的算法[7]提出了超圖著色的方法（ HGCBA，Hypergraph Coloring based Algorithm），該方法在上一個(gè)算法的基礎(chǔ)上，通過使用“度”的概念來定義小區(qū)相隔的個(gè)數(shù)，即直接相鄰的度為1，鄰區(qū)的鄰區(qū)其度為2，以此類推。通過對(duì)度的動(dòng)態(tài)調(diào)節(jié)，可以保持PCI的復(fù)用距離足夠遠(yuǎn)，有效地降低網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化引起的沖突和混淆，同時(shí)也可以控制ID復(fù)用距離不至于太遠(yuǎn)，節(jié)約PCI的使用。

本文面向4G無線接入系統(tǒng)，針對(duì)密集分層異構(gòu)組網(wǎng)場(chǎng)景，提出一種基于圖理論的小區(qū)ID交換配置算法（GIDSA，Graph based ID Switching Algorithm），通過搜索當(dāng)前局部最優(yōu)解逐步實(shí)現(xiàn)全局最優(yōu)化，有效減少ID復(fù)用沖突混淆概率。仿真部分詳細(xì)地評(píng)估了所提算法的用戶載干比、ID沖突混淆概率等性能指標(biāo)，并驗(yàn)證了該算法的有效性和優(yōu)越性。

2 系統(tǒng)模型

隨機(jī)部署場(chǎng)景示意圖如圖2所示：

圖2 隨機(jī)部署場(chǎng)景示意圖

將多層的網(wǎng)絡(luò)拓?fù)涑橄蟪杀馄降臒o向連通平面圖G=G(V,E)，如圖2所示，其中三角形、十字形和點(diǎn)分別表示宏基站、小基站和終端。圖G 含網(wǎng)絡(luò)節(jié)點(diǎn)頂點(diǎn)集合V 和邊集合E，邊定義為頂點(diǎn)間的鄰區(qū)關(guān)系。在組網(wǎng)規(guī)劃初期，由于沒有更多的終端支持，基站間的鄰區(qū)關(guān)系依靠點(diǎn)到點(diǎn)的信號(hào)估計(jì)進(jìn)行。這種評(píng)估通過一個(gè)基站到達(dá)另一個(gè)基站站點(diǎn)的信號(hào)強(qiáng)弱來判斷。信號(hào)由一個(gè)發(fā)送端xj發(fā)出，到一個(gè)接收端xk截止，并根據(jù)不同的無線信道環(huán)境進(jìn)行衰落，那么發(fā)送端xj到接收端xk的干擾功率Ijk可定義為：

其中，Pj為發(fā)送端xj的發(fā)射功率；α為路徑損耗因子；jk為隨機(jī)的服從對(duì)數(shù)為正態(tài)分布的陰影衰落所造成的信號(hào)損耗。在異構(gòu)組網(wǎng)場(chǎng)景中，小基站發(fā)射功率沒有宏基站大，考慮到圓桶矮邊效應(yīng)，它們與宏基站是否存在鄰區(qū)關(guān)系取決于功率大的一邊。因此，基站間是否存在鄰區(qū)關(guān)系可由rjk定義：

其中，Thweight是鄰區(qū)關(guān)系的判決門限，判斷兩基站間的接收信號(hào)高于該門限，則rjk=1存在鄰區(qū)關(guān)系，不同頂點(diǎn)之間鄰區(qū)關(guān)系rjk組成網(wǎng)絡(luò)鄰區(qū)關(guān)系矩陣R。另外，PCI復(fù)用指示矩陣P表示基站間配置ID的沖突情況，基站xj與基站xk若配置了相同的ID，則pj,k=1，否則pj,k=0。那么，網(wǎng)絡(luò)中所有基站之間的ID沖突可以通過鄰區(qū)關(guān)系矩陣R和PCI復(fù)用指示矩陣P的Hadamard乘積計(jì)算得到：

其中，cj,k=rj,k×pj,k，取值為0或1。當(dāng)cj,k=1時(shí)，基站xj與基站xk不僅存在鄰區(qū)關(guān)系，而且ID沖突。引入代價(jià)函數(shù)定義為：

式（4）定義了當(dāng)前解S 下網(wǎng)絡(luò)沖突數(shù)量，那么算法的目標(biāo)是找出最小代價(jià)解，即：

3 基于圖論的PCI交換算法

對(duì)于一個(gè)一定規(guī)模基站數(shù)量為N 的網(wǎng)絡(luò)來說，PCI配置的解空間是PCI數(shù)量M 的節(jié)點(diǎn)數(shù)量N 次方，通過窮舉法求解顯然需要浪費(fèi)大量的計(jì)算資源。GIDSA能在較少的迭代次數(shù)和較低的計(jì)算代價(jià)下使結(jié)果收斂于最優(yōu)解，具體算法步驟如下：

（1）在配置解空間中隨機(jī)選取任一初始狀態(tài)S 作為初始解，通過鄰區(qū)關(guān)系矩陣R和PCI復(fù)用指示矩陣P計(jì)算當(dāng)前狀態(tài)下的沖突矩陣C。

（2）計(jì)算每個(gè)節(jié)點(diǎn)沖突數(shù)量并排序，交換沖突最多的節(jié)點(diǎn)ID，得到新解S’并進(jìn)行評(píng)估：

◆若當(dāng)前狀態(tài)下代價(jià)函數(shù)滿足COST(S’)

◆否則，返回步驟（2）重新尋找沖突次多的節(jié)點(diǎn)進(jìn)行ID交換。

（3）以新解S’作為當(dāng)前狀態(tài)解并進(jìn)行下一次迭代，直到無法滿足代價(jià)函數(shù)，則將該解作為最終值。

以圖3 為例， 假設(shè)圖中網(wǎng)絡(luò)的點(diǎn)集合包括V={1,2,3,4,5,6,7,8}，可供使用的PCI資源集合為PCI={A,B,C}。算法初期，在初始狀態(tài)解S 中，由于配置得不合理，具有鄰區(qū)關(guān)系的節(jié)點(diǎn)使用相同的ID，圖中由虛線變?yōu)閷?shí)線。算法的目標(biāo)是通過某兩個(gè)節(jié)點(diǎn)ID的交換減少網(wǎng)絡(luò)中ID沖突的個(gè)數(shù)。

圖3 沖突節(jié)點(diǎn) 的PCI置換示意圖

表1（a）、（b）截取了節(jié)點(diǎn)3和節(jié)點(diǎn)7的鄰區(qū)關(guān)系矩陣R 及PCI 復(fù)用指示矩陣P，通過這2 個(gè)矩陣Hadamard乘積后得到網(wǎng)絡(luò)PCI沖突數(shù)量，表1（c）的沖突矩陣C顯示節(jié)點(diǎn)3和節(jié)點(diǎn)7分別存在3個(gè)及2個(gè)ID沖突。因此，優(yōu)先對(duì)這2個(gè)節(jié)點(diǎn)進(jìn)行交換得到新解S’，通過代價(jià)函數(shù)評(píng)估得到COST(S)>COST(S’)，滿足新解狀態(tài)優(yōu)于初始解，交換后更新PCI復(fù)用指示矩陣P’、沖突矩陣C’如表1（d）和（e）所示。

表1 小區(qū)3和 小區(qū)7的R、P、C矩陣

PCI的交換方法在特定的場(chǎng)景中并不適用，極端情況下，如網(wǎng)絡(luò)中全部使用一個(gè)ID，僅依靠交換是無法解決，因此還需要有替換過程進(jìn)行補(bǔ)充，即在算法步驟（2）中選擇引起沖突最多的節(jié)點(diǎn)并使其替換成其他PCI。PCI的選擇可從PCI池中找出使用頻率最低的，替換要滿足代價(jià)函數(shù)要求。交換和替換過程分別應(yīng)對(duì)由于拓?fù)浣Y(jié)構(gòu)性的失誤及數(shù)量上的不均勻而引起的PCI配置不合理問題。算法通過反復(fù)的迭代計(jì)算，優(yōu)先調(diào)整網(wǎng)絡(luò)中沖突最多的ID，逐步優(yōu)化ID分配結(jié)構(gòu)。算法的結(jié)束必然是算法無法再找到更優(yōu)解，此時(shí)網(wǎng)絡(luò)ID沖突已經(jīng)收斂于一個(gè)穩(wěn)態(tài)，網(wǎng)絡(luò)中無沖突存在；亦或是網(wǎng)絡(luò)中沖突仍然存在，但此時(shí)的矛盾在于過少的PCI資源和過于密集的網(wǎng)絡(luò)部署，只能通過增加PCI數(shù)量來解決。

GIDSA初始配置可以從任何狀態(tài)開始，甚至從隨機(jī)撒點(diǎn)狀態(tài)開始，或者從其他算法的結(jié)果獲得粗略的配置出發(fā)，減少迭代次數(shù)并縮短算法運(yùn)行需要的時(shí)間。算法通過對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)使用ID進(jìn)行調(diào)整，能均勻地進(jìn)行配置，有效地實(shí)現(xiàn)網(wǎng)絡(luò)干擾沖突總量最小化。

4 仿真驗(yàn)證

本文將利用MATLAB計(jì)算機(jī)靜態(tài)仿真平臺(tái)驗(yàn)證所提算法GIDSA和對(duì)比算法HGCBA的性能，包括PCI沖突概率、PCI混淆概率和用戶載干比CIR等性能。仿真場(chǎng)景主要考慮大規(guī)模小基站部署場(chǎng)景，分別采用泰森多邊形隨機(jī)網(wǎng)絡(luò)（見圖2）和正六邊形網(wǎng)絡(luò)進(jìn)行對(duì)比。在泰森多邊形網(wǎng)絡(luò)場(chǎng)景中，宏基站與小基站均為撒點(diǎn)部署，小基站根據(jù)信號(hào)電平值與宏小區(qū)互為鄰區(qū)，同時(shí)與信號(hào)估計(jì)超過設(shè)定門限的其他小基站互為鄰區(qū)。用戶同樣隨機(jī)生成，按照接收信號(hào)功率強(qiáng)度接入最強(qiáng)的基站。具體的仿真參數(shù)設(shè)置如表2所示：

表2 系統(tǒng)仿真參數(shù)設(shè)置

從算法的配置結(jié)果來看，圖4 給出了GIDSA、HGCBA的PCI沖突和混淆概率。總體來說，算法的沖突率和混淆率都隨著PCI資源的增加呈現(xiàn)下降趨勢(shì)。沖突率在PCI數(shù)量為5個(gè)時(shí)基本趨于0，而混淆率由于要求兩圈鄰區(qū)PCI不復(fù)用，因此收斂速度明顯偏慢，當(dāng)PCI資源達(dá)到25個(gè)時(shí)，資源相對(duì)充足，此時(shí)小區(qū)的平均二級(jí)鄰區(qū)在25個(gè)左右，數(shù)量與PCI數(shù)基本持平，混淆率下降至0.5；伴隨著PCI資源的繼續(xù)增長(zhǎng)，密集地區(qū)也能得到充足資源，混淆率進(jìn)一步降低。相對(duì)而言，GIDSA在相同資源條件下效果比HGCBA更優(yōu)，這是由于GIDSA是通過交換和替換進(jìn)行PCI配置的優(yōu)化，當(dāng)輪詢的次數(shù)達(dá)到一定數(shù)量時(shí)，配置結(jié)果接近理論最優(yōu)化。

圖 4 GIDSA和HGCBA算法的沖突混淆率

圖5、圖6則給出了泰森多邊形隨機(jī)網(wǎng)絡(luò)場(chǎng)景和正六邊形蜂窩網(wǎng)絡(luò)場(chǎng)景下GIDSA、HGCBA及隨機(jī)分配算法的用戶載干比CDF曲線。仿真結(jié)果顯示，在PCI=10/30/50這3種數(shù)量條件下，GIDSA算法的CDF曲線最靠右，性能也最優(yōu)，且與其他算法性能差異隨著資源數(shù)量的增加而不斷擴(kuò)大，這主要是因?yàn)樵谫Y源數(shù)量少的情況下，算法受限于資源數(shù)目，算法性能用戶總體載干比性能接近；當(dāng)資源數(shù)量富裕時(shí)，GIDSA算法性能優(yōu)勢(shì)變得明顯，此時(shí)用戶載干比受接近最優(yōu)化的算法機(jī)制影響；相比正六邊形規(guī)章場(chǎng)景，HGCBA并不適用于隨機(jī)部署場(chǎng)景，即使在PCI數(shù)量為50時(shí)，性能與GIDSA還相差3dB。另外，隨機(jī)配置給出了在相同場(chǎng)景下沒有優(yōu)化的性能比較。從圖中配置結(jié)果來看，在PCI資源數(shù)量缺乏時(shí)，信干比性能更多地受限于資源數(shù)量，隨機(jī)分配算法性能接近于其他算法。而在PCI數(shù)量充足的情況下，CIR性能受限于能否合理地保證相同ID的復(fù)用距離足夠遠(yuǎn)，因此隨機(jī)分配算法性能遠(yuǎn)遠(yuǎn)落后于其他算法。

圖5 泰森多邊形隨機(jī)網(wǎng)絡(luò)場(chǎng)景下的用戶CIR性能

圖6 正六邊形蜂窩網(wǎng)絡(luò)場(chǎng)景下的用戶CIR性能

5 結(jié)束語

本文將分層異構(gòu)場(chǎng)景下小基站的ID分配問題轉(zhuǎn)化為平面圖問題，并提出了基于圖理論的小區(qū)ID交換配置算法。該算法通過引入代價(jià)函數(shù)將配置不合理的ID進(jìn)行交換和替換，從當(dāng)前最優(yōu)解逐步迭代最終達(dá)到全局最優(yōu)化的效果。仿真驗(yàn)證結(jié)果顯示，所提算法能有效降低網(wǎng)絡(luò)PCI沖突和混淆概率，在相同PCI資源數(shù)量的情況下具有更高用戶信干比性能增益，實(shí)現(xiàn)基站ID的準(zhǔn)確識(shí)別。

[1] E Dahlman, S Parkvall, J Sk?ld, et al. 3G Evolution-HSPA and LTE for Mobile Broadband[J]. Elsevier, 2007.

[2] 3GPP TR 36.211 V10.2.0. Physical Channels and Modulation[S]. 2011.

[3] 3GPP TR 36.902 V9.3.1. Self-Configuring and Self-Optimizing Network (SON) Use Cases and Solutions[S]. 2011.

[4] R3-080376. SON Use Case: Cell Physical ID Automated Configuration[S]. 3GPP RAN3 #59, 2008.

[5] R3-080812. Configuration of Physical Cell Identity Use Case[S]. 3GPP RAN3 #59bis, 2008.

[6] Tobias Bandh, Georg Carle. Graph Coloring Based Physical Cell ID Assignment for LTE Network[A]. International Conference on Communications and Mobile Computing[C]. 2009: 116-120.

[7] Haitao Xu, Xianwei Zhou, Yuan Li. Model of Hypergraph Colouring for Self-Configuration in LTE Networks[J]. Information Management, Innovation Management and Industrial Engineering (ICIII), 2011(1): 393-396.★