分層組網場景下小基站ID分配算法研究

魏垚，韓斌

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

1 引言

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

圖1 分層異構組網場景示意圖

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

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

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

2 系統模型

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

圖2 隨機部署場景示意圖

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

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

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

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

式（4）定義了當前解S 下網絡沖突數量，那么算法的目標是找出最小代價解，即：

3 基于圖論的PCI交換算法

對于一個一定規?；緮盗繛镹 的網絡來說，PCI配置的解空間是PCI數量M 的節點數量N 次方，通過窮舉法求解顯然需要浪費大量的計算資源。GIDSA能在較少的迭代次數和較低的計算代價下使結果收斂于最優解，具體算法步驟如下：

（1）在配置解空間中隨機選取任一初始狀態S 作為初始解，通過鄰區關系矩陣R和PCI復用指示矩陣P計算當前狀態下的沖突矩陣C。

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

◆若當前狀態下代價函數滿足COST(S’)

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

（3）以新解S’作為當前狀態解并進行下一次迭代，直到無法滿足代價函數，則將該解作為最終值。

以圖3 為例， 假設圖中網絡的點集合包括V={1,2,3,4,5,6,7,8}，可供使用的PCI資源集合為PCI={A,B,C}。算法初期，在初始狀態解S 中，由于配置得不合理，具有鄰區關系的節點使用相同的ID，圖中由虛線變為實線。算法的目標是通過某兩個節點ID的交換減少網絡中ID沖突的個數。

圖3 沖突節點 的PCI置換示意圖

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

表1 小區3和 小區7的R、P、C矩陣

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

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

4 仿真驗證

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

表2 系統仿真參數設置

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

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

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

圖5 泰森多邊形隨機網絡場景下的用戶CIR性能

圖6 正六邊形蜂窩網絡場景下的用戶CIR性能

5 結束語

本文將分層異構場景下小基站的ID分配問題轉化為平面圖問題，并提出了基于圖理論的小區ID交換配置算法。該算法通過引入代價函數將配置不合理的ID進行交換和替換，從當前最優解逐步迭代最終達到全局最優化的效果。仿真驗證結果顯示，所提算法能有效降低網絡PCI沖突和混淆概率，在相同PCI資源數量的情況下具有更高用戶信干比性能增益，實現基站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.★