改進(jìn)圖著色算法的PCI自動(dòng)分配方法

劉 為，廖仁波，王 琳

(中國(guó)電子科技集團(tuán)公司第七研究所，廣東 廣州 510310)

0 引 言

物理小區(qū)ID(physical cell ID，PCI)是長(zhǎng)期演進(jìn)(long-term evolution，LTE)系統(tǒng)中終端區(qū)分不同小區(qū)的無(wú)線信號(hào)標(biāo)識(shí)，是小區(qū)最基本的配置參數(shù)。LTE應(yīng)用的PCI數(shù)量為504個(gè)，取值范圍0-503，分成168組，每組包含3個(gè)PCI[1]。現(xiàn)實(shí)組網(wǎng)不可避免要對(duì)PCI進(jìn)行復(fù)用，可能造成相同PCI由于復(fù)用距離過(guò)小產(chǎn)生沖突或者混淆[2]。PCI規(guī)劃的目的就是為每個(gè)演進(jìn)型Node B(evolved node B，eNB)小區(qū)分配無(wú)沖突、無(wú)混淆的PCI。

目前已提出圖著色方法應(yīng)用于LTE PCI分配的方法[3]，但未考慮同頻組網(wǎng)時(shí)不同小區(qū)導(dǎo)頻信號(hào)之間的干擾控制問(wèn)題。

本文提出了一種基于改進(jìn)圖著色方法的PCI自動(dòng)分配方法，既能夠保證相鄰小區(qū)PCI無(wú)沖突、無(wú)混淆，同時(shí)使得同頻小區(qū)間的導(dǎo)頻信號(hào)干擾抑制能得到優(yōu)化。

1 PCI復(fù)用和分配原則

小區(qū)間復(fù)用PCI時(shí)應(yīng)考慮以下情況：

(1)PCI無(wú)沖突

兩個(gè)或以上直接相鄰的小區(qū)分配相同的PCI，稱為PCI沖突，如圖1所示。該情況會(huì)導(dǎo)致重疊區(qū)域中至多只有一個(gè)小區(qū)會(huì)被終端搜索同步，而該小區(qū)不一定是最合適的。

圖1 PCI沖突

(2)PCI無(wú)混淆

小區(qū)(ID=B)的兩個(gè)及以上的相鄰小區(qū)具有相同的PCI(ID均為A)，稱為PCI混淆，如圖2所示。此情況下，該小區(qū)下的終端請(qǐng)求切換到PCI為m的小區(qū)，則小區(qū)A無(wú)法分辨目標(biāo)小區(qū)，進(jìn)而導(dǎo)致切換失敗。

圖2 PCI混淆

(3)同頻干擾抑制

LTE系統(tǒng)中，PCI的取值顯式地決定了無(wú)線傳輸參考信號(hào)(reference signal，RS)的結(jié)構(gòu)[4]。下行方向上，終端與基站間的同步保持依賴于小區(qū)的主同步信號(hào)(primary synchronous signal，PSS)、輔同步信號(hào)(secondary synchronous signal，SSS)和小區(qū)參考信號(hào)(cell reference signal，CRS)。同頻組網(wǎng)時(shí)，位于小區(qū)邊緣的終端可同時(shí)接收到多個(gè)相鄰小區(qū)的PSS/SSS同步信號(hào)和CRS信號(hào)。PCI模三不同時(shí)，PSS基于不同的ZC根序列產(chǎn)生，接收端互相關(guān)檢測(cè)性能更好；PCI模六不同時(shí)，CRS的頻域位置不同，下行同頻干擾相對(duì)較小[1]。上行方向上，基站依賴終端發(fā)送的解調(diào)參考信號(hào)(demodulation RS，DM-RS)接收數(shù)據(jù)。LTE系統(tǒng)中，對(duì)應(yīng)PCI模三十不同，定義了30個(gè)不同的序列組(sequence groups)用于生成DM-RS，此時(shí)DM-RS互相關(guān)性能較佳，進(jìn)而同頻小區(qū)間上行干擾相對(duì)較小[1]。由上述討論可見(jiàn)，合理分配PCI(即盡量避免模三、模六、模三十相同)可優(yōu)化同頻組網(wǎng)小區(qū)間干擾抑制。

此外，PCI分配還需考慮如下原則進(jìn)行：

(1)共站小區(qū)PCI不同；

(2)“鄰區(qū)”和“鄰區(qū)的鄰區(qū)”P(pán)CI不同；

(3)同一個(gè)站點(diǎn)的多個(gè)小區(qū)之間盡量保證PCI模三不等，本小區(qū)與最近鄰區(qū)盡量PCI模三不等；

(4)復(fù)用PCI的兩個(gè)小區(qū)之間距離盡量遠(yuǎn)。

2 PCI自動(dòng)分配設(shè)計(jì)方案

2.1 總體設(shè)計(jì)

從全局來(lái)看，PCI自優(yōu)化的所需的信息都在操作維護(hù)中心(operation and maintenance center，OMC)，OMC可以全局規(guī)劃，得出無(wú)沖突、無(wú)混淆的PCI下發(fā)給eNB。eNB只有本地及鄰區(qū)的信息，負(fù)責(zé)分布式的PCI沖突和PCI混淆檢測(cè)。

PCI自動(dòng)分配方案包括兩方面內(nèi)容：PCI分配和PCI優(yōu)化。PCI分配指小區(qū)初始化階段從OMC獲取有效PCI配置。PCI優(yōu)化指已有小區(qū)在運(yùn)作過(guò)程中對(duì)PCI的自我優(yōu)化過(guò)程。其中，PCI優(yōu)化過(guò)程又包括兩個(gè)階段：PCI沖突和混淆檢測(cè)以及PCI重分配。前者是發(fā)現(xiàn)問(wèn)題的過(guò)程，執(zhí)行者為OMC和eNB。后者是解決問(wèn)題的過(guò)程，執(zhí)行者為OMC。

PCI自動(dòng)分配方案的總體設(shè)計(jì)如下：

(1)OMC比eNB更清楚整個(gè)網(wǎng)絡(luò)覆蓋的PCI分配，能夠從宏觀上把握PCI沖突混淆的解決。eNB作為PCI分配的最終執(zhí)行者，只能從微觀的角度判斷配置的有效性。因此，eNB只負(fù)責(zé)PCI沖突混淆的檢測(cè)，發(fā)現(xiàn)沖突或者混淆后上報(bào)警報(bào)(Alarm)信息給OMC，并不決定如何解決，而OMC負(fù)責(zé)PCI沖突混淆的解決，在得到Alarm信息之后通過(guò)優(yōu)化算法最終決定PCI更改的方案并且實(shí)施。

(2)OMC所采用的PCI優(yōu)化算法必須保證每次向eNB分配的PCI具有一定的準(zhǔn)確性，即PCI配置后發(fā)生混淆沖突的幾率足夠小。

(3)在建立兩個(gè)eNB之間的邏輯連接(X2連接)的時(shí)候，兩端的eNB都會(huì)進(jìn)行PCI檢測(cè)。如果發(fā)現(xiàn)沖突或者混淆，兩端都上報(bào)Alarm給OMC。最終由OMC根據(jù)收集到的多個(gè)Alarm信息決定PCI更改方案。

2.2 基于圖著色的PCI分配設(shè)計(jì)

基于圖著色的PCI分配設(shè)計(jì)分為3個(gè)階段：網(wǎng)絡(luò)初始化階段，網(wǎng)絡(luò)增長(zhǎng)增量分配階段，以及混淆解決階段。

(1)網(wǎng)絡(luò)初始化階段

在網(wǎng)絡(luò)初始化階段，OMC根據(jù)已有小區(qū)和新加入小區(qū)的相關(guān)信息，包括地理位置，功率覆蓋，鄰區(qū)關(guān)系等因素，進(jìn)行初始化PCI分配，排除無(wú)效PCI，并給出無(wú)沖突無(wú)混淆的PCI配置，一個(gè)小區(qū)對(duì)應(yīng)唯一一個(gè)PCI配置。

將所有基站映射為圖著色節(jié)點(diǎn)，每對(duì)鄰區(qū)節(jié)點(diǎn)和鄰區(qū)的鄰區(qū)節(jié)點(diǎn)之間用關(guān)系線連接起來(lái)。通過(guò)使用圖著色方法，可保證連接節(jié)點(diǎn)之間采用不同的顏色，從而實(shí)現(xiàn)PCI合理分配的目的，如圖3所示。

圖3 圖著色PCI分配方法

(2)網(wǎng)絡(luò)增長(zhǎng)增量分配階段

通過(guò)迭代，對(duì)小區(qū)中每一個(gè)PCI節(jié)點(diǎn)進(jìn)行著色，最終使得每對(duì)相鄰節(jié)點(diǎn)采用不用的顏色(即不同PCI ID)。

定義：

一級(jí)鄰區(qū)：當(dāng)前小區(qū)的直接鄰區(qū)。

二級(jí)鄰區(qū)：當(dāng)前小區(qū)直接鄰區(qū)的鄰區(qū)。

三級(jí)鄰區(qū)：當(dāng)前小區(qū)直接鄰區(qū)的鄰區(qū)的鄰區(qū)。

步驟1 檢查當(dāng)前節(jié)點(diǎn)的三級(jí)鄰區(qū)PCI集合是否是在一級(jí)鄰區(qū)和二級(jí)鄰區(qū)中未被使用，如果結(jié)果非空，從結(jié)果中選擇PCI集合；如果結(jié)果為空，執(zhí)行下一步；

步驟2 檢查在一級(jí)鄰區(qū)和二級(jí)鄰區(qū)中未被使用的PCI集合是否包含在已使用的PCI集合中，如果結(jié)果非空，從結(jié)果中選擇PCI集合；如果結(jié)果為空，繼續(xù)；

步驟3 如果可用的PCI集合和已使用的PCI集合相同，全網(wǎng)重新規(guī)劃；否則，從可用的PCI集合中(但不在已使用的PCI集合中)選擇最小的PCI作為當(dāng)前節(jié)點(diǎn)的PCI。

(3)混淆解決階段

步驟1 為當(dāng)前節(jié)點(diǎn)的一級(jí)鄰區(qū)中使用相同PCI建立一個(gè)列表；

步驟2 將列表中的節(jié)點(diǎn)降序排列；

步驟3 從列表中移除最上面的節(jié)點(diǎn)；

步驟4 更改列表中剩余節(jié)點(diǎn)的PCI。

2.3 PCI沖突和混淆檢測(cè)流程設(shè)計(jì)

PCI沖突檢測(cè)流程設(shè)計(jì)如圖4所示。PCI混淆檢測(cè)流程設(shè)計(jì)如圖5所示。

圖4 PCI沖突檢測(cè)流程

(1)建立X2連接的兩端eNB都檢查PCI沖突混淆，發(fā)現(xiàn)沖突混淆后上報(bào)PCI沖突混淆警報(bào)信息給OMC，包括沖突混淆雙方的相關(guān)信息，時(shí)間和觸發(fā)沖突混淆檢測(cè)的原因。

(2)OMC在得到PCI沖突混淆警報(bào)信息之后，觸發(fā)對(duì)指定eNB進(jìn)行PCI更改操作。OMC通過(guò)鄰區(qū)關(guān)系拓?fù)洌捎酶倪M(jìn)圖著色方法取得合適的PCI，并檢測(cè)PCI的修改是否會(huì)導(dǎo)致現(xiàn)有eNB網(wǎng)絡(luò)存在PCI沖突混淆。如無(wú)沖突混淆，OMC下發(fā)指令通知eNB更新小區(qū)PCI的配置。否則，重新生成有效PCI。

(3)eNB收到配置指令之后，檢查需要更新的PCI是否存在沖突混淆的情況。一般情況下，OMC和eNB鄰區(qū)關(guān)系信息一致，不存在OMC認(rèn)為某個(gè)PCI沒(méi)有沖突混淆，但eNB檢測(cè)到?jīng)_突混淆的情況。這里eNB進(jìn)行檢測(cè)只是進(jìn)行再次確認(rèn)而已。

(4)如無(wú)沖突混淆，eNB向所有鄰區(qū)eNB發(fā)送X2配置更新消息，更新本小區(qū)信息。否則上報(bào)PCI沖突混淆警報(bào)信息給OMC。

(5)eNB修改PCI配置并通知OMC更新成功。OMC給出解決前后的網(wǎng)絡(luò)性能變化及解決過(guò)程中所造成的用戶掉話統(tǒng)計(jì)，以及從發(fā)現(xiàn)沖突混淆到解決所花費(fèi)的時(shí)間。

2.4 PCI分配設(shè)計(jì)的進(jìn)一步改進(jìn)

對(duì)PCI分配方法進(jìn)行改進(jìn)，盡量從未使用PCI集合中提取，目的在于使得復(fù)用PCI的小區(qū)盡可能遠(yuǎn)離。在分配PCI的時(shí)候，優(yōu)先考慮同一基站(Intra-eNB)下的小區(qū)，首先檢查可否分配模三不同PCI，其次考慮模六不同PCI，最

圖5 PCI混淆檢測(cè)流程

后考慮模三十不同PCI。對(duì)于不同基站(Inter-eNB)的相鄰小區(qū)，若已經(jīng)有6個(gè)以上鄰區(qū)采用不同的PCI模六值，則隨機(jī)選擇模六相同的PCI值。中心點(diǎn)的獲取是根據(jù)待分配PCI隊(duì)列來(lái)選擇首位節(jié)點(diǎn)。具體流程如圖6所示。

其中：

未著色隊(duì)列：網(wǎng)絡(luò)中需要進(jìn)行PCI配置的節(jié)點(diǎn)集合。

待著色隊(duì)列：與當(dāng)前節(jié)點(diǎn)有關(guān)聯(lián)的節(jié)點(diǎn)集合。每個(gè)節(jié)點(diǎn)著色之后，將其所有未著色鄰區(qū)放入該隊(duì)列中。

3 仿真實(shí)驗(yàn)

本文根據(jù)基于改進(jìn)圖著色方法的LTE小區(qū)PCI自動(dòng)分配設(shè)計(jì)方案進(jìn)行了仿真實(shí)驗(yàn)。假定同一基站站點(diǎn)部署3個(gè)小區(qū)，仿真將其抽象為3個(gè)相鄰的圓，按照地理位置和覆蓋范圍粗略估計(jì)鄰區(qū)關(guān)系。結(jié)果如下：

(1)根據(jù)物理位置和覆蓋范圍，將基站映射為待著色節(jié)點(diǎn)。

(2)根據(jù)“鄰區(qū)”和“鄰區(qū)的鄰區(qū)”關(guān)系，初始化分配PCI，如圖7所示。使用圖著色方法，使得每對(duì)相鄰節(jié)點(diǎn)采用不用的顏色作為PCI標(biāo)識(shí)。

(3)對(duì)于新加入小區(qū)節(jié)點(diǎn)引起的PCI混淆，進(jìn)行自動(dòng)修復(fù)，如圖8所示。新小區(qū)節(jié)點(diǎn)加入后，兩個(gè)相同PCI的鄰區(qū)被重新進(jìn)行分配，解決了PCI混淆問(wèn)題。

(4)采用改進(jìn)PCI分配方法，避免模三相同，如圖9所示。避免模六相同，如圖10所示。該仿真暫未實(shí)現(xiàn)鄰區(qū)PCI模三十不同。

4 結(jié)束語(yǔ)

本文設(shè)計(jì)的基于改進(jìn)圖著色方法的LTE小區(qū)PCI自動(dòng)

圖6 改進(jìn)PCI分配設(shè)計(jì)流程

圖7 PCI初始分配

圖8 新加入小區(qū)

圖10 PCI分配圖(模六不同)

分配方案，實(shí)現(xiàn)了多小區(qū)PCI無(wú)沖突、無(wú)混淆分配，并支持PCI沖突和混淆的接入網(wǎng)分布式檢測(cè)以及集中式的重分配處理。該方案的創(chuàng)新性在于同時(shí)考慮到PCI取值直接關(guān)聯(lián)到物理層主輔同步信號(hào)和小區(qū)參考信號(hào)的生成與頻域位置復(fù)用，因此可通過(guò)控制模N不同PCI的選取，使得小區(qū)間上下行導(dǎo)頻信號(hào)的同頻干擾下降。結(jié)合初始和新加入小區(qū)分配PCI的用例，仿真實(shí)例顯示算法實(shí)用有效。下一步工作將增強(qiáng)PCI分配算法以支持PCI模三十不同和異構(gòu)小區(qū)組網(wǎng)。

[1]Stefania Sesia,Issam Toufik,Matthew Baker.LTE-The UMTS long term evolution:From theory to practice[M].2nd ed.Chichester,UK:John Wiley & Sons,2011.

[2]3rd Generation Partnership Project.3GPP TS 36.300 technical specification group radio access network;evolved universal terrestrial radio access(E-UTRA) and evolved universal terrestrial radio access network (E-UTRAN);overall description;Stage 2[S].France:3rd Generation Partnership Project,2016:234-237.

[3]Bandh T,Carle G,Sanneck H.Graph coloring based physical-Cell-ID assignment for LTE networks[C]//ACM Internatio-nal Conference on Wireless Communications and Mobile Computing,2009:116-120.

[4]3rd Generation Partnership Project.3GPP TS 36.211 technical specification group radio access network;evolved universal terrestrial radio access (E-UTRA);physical channels and modulation[S].France:3rd Generation Partnership Project,2016:105-130.

[5]Hasan MR,Kawser MT,Islam MR.An automatic GSM neighbor cell list update procedure enhancing SON in LTE[C]//International Conference on Electrical & Computer Engineering,2010:143-146.

[6]LI Qing.Research of TD-LTE PCI planning[J].Radio Communications Technology,2013,39(5):66-68(in Chinese).[李青.TD-LTE系統(tǒng)PCI規(guī)劃方法研究[J].綜合電子信息技術(shù),2013,39(5):66-68.]

[7]Lukasz Chrost,Krzysztof Grochla.Conservative graph coloring:A robust method for automatic PCI assignment in LTE[J].Communications in Computer and Information Science,2013,370:268-276.

[8]Saqib Nawaz M,Fayyaz Awan M.Graph coloring algorithm using adjacency matrices[J].International Journal of Scientific & Engineering Research,2013,4(4):1840-1842.

[9]Basit Shahab M,Abdul Aziz Bhatti.Neural networks based physical cell identity assignment for self organized 3GPP long term evolution[J].International Journal of Advances in Telecommunications,Electrotechnics,Signals and Systems,2013,2(3):104-110.

[10]Labeeb Mohsin Abdullah,Mohd Dani Baba,Sinan Ghassan Abid Ali.Self-configuration concept to solve physical cell ID conflict for SON LTE-based femtocell environment[J].International Journal on Recent Trends in Engineering & Technology,2014,10(2):165-171.

[11]Acedo-Hernandez R,Toril M,Luna-Ramírez S,et al.Analysis of the impact of PCI planning on downlink throughput performance in LTE[J].Computer Networks,2015,76:42-54.

[12]Kreitmair F.Self-configuration in LTE self organizing networks[J].Network,2013,145:145-150.

[13]Furqan Ahmed,Junquan Deng,Olav Tirkkonen.Self-orga-nizing networks for 5G:Directional cell search in MMW networks[C]//IEEE 27th Annual International Symposium on Personal Indoor and Mobile Radio Communications,2016:1-5.

[14]Mhiri F,Sethom K,Bouallegue R.A survey on interference management techniques in femtocell self organizing networks[J].Journal of Network and Computer Applications,2012,36(1):58-65.

[15]Abdullah LM,Baba MD,Ali SGA.Self-configuration concept to solve physical cell ID conflict for SON LTE-based femtocell environment[J].International Journal on Recent Trends in Engineering & Technology,2014,10(2):165.