魏垚，韓斌

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

1 引言

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

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

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

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

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

2 系統(tǒng)模型

隨機部署場景示意圖如圖2所示：

圖2 隨機部署場景示意圖

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

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

其中，Thweight是鄰區(qū)關(guān)系的判決門限，判斷兩基站間的接收信號高于該門限，則rjk=1存在鄰區(qū)關(guā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乘積計算得到：

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

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

3 基于圖論的PCI交換算法

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真驗證

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

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

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

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

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

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

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

5 結(jié)束語

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

[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.★