LTE基于圖論與遺傳算法的PCI重規(guī)劃研究

孫克雄+魯飛+俞晨晟+韓明+李海江+陳超

【摘 要】為了解決LTE網(wǎng)絡(luò)小區(qū)PCI規(guī)劃中邊界網(wǎng)絡(luò)適配困難、模三干擾改善困難的問(wèn)題，引入了基于圖論與遺傳算法的小區(qū)PCI規(guī)劃算法。該算法利用道路測(cè)試與網(wǎng)管采集的網(wǎng)絡(luò)運(yùn)行數(shù)據(jù)構(gòu)建新的小區(qū)干擾關(guān)系矩陣，將PCI規(guī)劃粒度精細(xì)化到小區(qū)級(jí)別，從模三干擾、復(fù)用距離、復(fù)用層數(shù)、沖突規(guī)避四個(gè)維度對(duì)PCI重規(guī)劃過(guò)程進(jìn)行約束，以此獲得最優(yōu)的PCI分配方案。通過(guò)對(duì)一個(gè)縣級(jí)市的LTE運(yùn)行數(shù)據(jù)進(jìn)行綜合分析，給出了PCI重規(guī)劃后的預(yù)測(cè)結(jié)果，并通過(guò)PCI規(guī)劃方案的執(zhí)行以及評(píng)估，驗(yàn)證了預(yù)測(cè)結(jié)果的準(zhǔn)確性和算法的實(shí)用性。

【關(guān)鍵詞】模三干擾 PCI重規(guī)劃 干擾矩陣 無(wú)向全連通圖 遺傳算法

doi：10.3969/j.issn.1006-1010.2016.20.001 中圖分類號(hào)：TN929.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-1010（2016）20-0005-06

1 引言

目前，我國(guó)LTE商用網(wǎng)絡(luò)普遍采用20 MHz同頻組網(wǎng)，頻率復(fù)用系數(shù)為1，小區(qū)間的同頻干擾較為嚴(yán)重。在LTE同頻組網(wǎng)規(guī)劃中，小區(qū)間的模三或模六干擾是對(duì)網(wǎng)絡(luò)質(zhì)量影響最大的因素[1]。產(chǎn)生模三還是模六干擾主要是看網(wǎng)絡(luò)所采用的MIMO（Multiple-Input Multiple-Output，多輸入多輸出）技術(shù)，如果采用單天線則只產(chǎn)生模六干擾，而采用雙天線或更多天線時(shí)就會(huì)產(chǎn)生模三干擾。模三干擾與負(fù)載關(guān)系如表1所示。

模三干擾是指同一覆蓋區(qū)域內(nèi)兩個(gè)或兩個(gè)以上小區(qū)的PCI（Physical Cell Identifier，物理小區(qū)標(biāo)識(shí)）除以三的余數(shù)相同而產(chǎn)生的小區(qū)間互相干擾。同頻組網(wǎng)時(shí)，小區(qū)間的PCI復(fù)用距離越遠(yuǎn)越好，應(yīng)盡量避免相同覆蓋區(qū)域的小區(qū)出現(xiàn)同頻同PCI現(xiàn)象。

PCI規(guī)劃結(jié)果決定LTE網(wǎng)絡(luò)同頻小區(qū)干擾指標(biāo)，是LTE小區(qū)參數(shù)規(guī)劃最重要的環(huán)節(jié)。傳統(tǒng)PCI規(guī)劃算法一般基于傳統(tǒng)的蜂窩網(wǎng)模型，將每個(gè)基站等效為一個(gè)規(guī)則的蜂窩網(wǎng)絡(luò)進(jìn)行PCI規(guī)劃。實(shí)際上由于站高、地形、地理位置的差異性，不同小區(qū)覆蓋范圍存在差異，普通的建模方式并不能體現(xiàn)這種差別，即使使用無(wú)線傳播模型進(jìn)行覆蓋預(yù)測(cè)，也會(huì)嚴(yán)重依賴電子地圖的精度和基站工參的準(zhǔn)確性，且運(yùn)算量巨大，耗時(shí)較長(zhǎng)[3]。

為了解決傳統(tǒng)PCI規(guī)劃算法的不足，本文在建立真實(shí)干擾矩陣基礎(chǔ)上引入圖論、遺傳算法來(lái)解決PCI重規(guī)劃的一些問(wèn)題，從減少模三干擾、PCI復(fù)用距離、PCI復(fù)用層數(shù)、PCI沖突規(guī)避四個(gè)維度對(duì)PCI重規(guī)劃過(guò)程進(jìn)行約束，進(jìn)而獲得最優(yōu)的PCI分配方案。

2 PCI重規(guī)劃原則

2.1 模三干擾減少原則

在LTE網(wǎng)絡(luò)中，手機(jī)收到的信號(hào)是以CRS（Cell Reference Signal，小區(qū)參考信號(hào)）強(qiáng)度來(lái)表現(xiàn)的。LTE系統(tǒng)中常見(jiàn)的雙天線端口CRS分布圖如圖1所示。

LTE網(wǎng)絡(luò)中PCI的取值范圍為0～503，如果兩個(gè)同頻小區(qū)的PCI模三相同，則這兩個(gè)小區(qū)的CRS時(shí)頻域完全重疊，導(dǎo)致終端下行相干解調(diào)性能降低，SINR（Signal to Interference plus Noise Ratio，信號(hào)與干擾加噪聲比）變差。PCI模三后只有3種取值（0，1，2），而同一區(qū)域服務(wù)小區(qū)添加鄰區(qū)一般會(huì)超過(guò)3個(gè)甚至更多，所以在實(shí)際網(wǎng)絡(luò)中模三干擾不可能完全消除，只能通過(guò)小區(qū)天饋調(diào)整或者PCI調(diào)整盡量減少。而減少的原則就是盡量避免同一覆蓋區(qū)域內(nèi)服務(wù)小區(qū)與鄰區(qū)模三相同，如果無(wú)法避免，則通過(guò)優(yōu)化手段使模三相同鄰區(qū)的CRS信號(hào)強(qiáng)度盡可能比服務(wù)小區(qū)低。

常規(guī)PCI調(diào)整和規(guī)劃的依據(jù)是以路測(cè)數(shù)據(jù)或模三切換次數(shù)為準(zhǔn)，而不是綜合考慮，規(guī)劃方法存在局限性。而基于圖論與遺傳算法的PCI重規(guī)劃算法是從路測(cè)數(shù)據(jù)、小區(qū)切換數(shù)據(jù)、掃頻數(shù)據(jù)和MR（Measurement Report，測(cè)量報(bào)告）數(shù)據(jù)中選取2至4個(gè)維度綜合分析及判斷，使PCI調(diào)整效果達(dá)到最優(yōu)。

2.2 PCI復(fù)用距離和復(fù)用層數(shù)原則

（1）PCI復(fù)用距離：與該小區(qū)同PCI的小區(qū)復(fù)用距離的最小值[4]。

（2）PCI復(fù)用層數(shù)：與該小區(qū)同PCI的小區(qū)復(fù)用層數(shù)的最小值，和復(fù)用距離含義類似。復(fù)用層數(shù)新算法是以兩個(gè)小區(qū)之間的連線為直徑畫一個(gè)圓，以兩個(gè)小區(qū)頂點(diǎn)畫正六邊形，且正六邊形的六個(gè)頂點(diǎn)均在圓上，正六邊形內(nèi)部的室外基站數(shù)量即為間隔層數(shù)。如圖2所示，A點(diǎn)與B點(diǎn)之間的站點(diǎn)數(shù)為6個(gè)，則間隔層數(shù)就定為6層。

綜上所述，PCI復(fù)用距離和復(fù)用層數(shù)越大越好。

2.3 PCI沖突和混淆規(guī)避原則

（1）PCI沖突規(guī)避：互為鄰區(qū)的小區(qū)不能使用相同的PCI。

（2）PCI混淆規(guī)避：同一個(gè)小區(qū)的鄰區(qū)間不能使用相同的PCI，否則移動(dòng)終端在切換時(shí)不知道哪個(gè)為目標(biāo)小區(qū)，會(huì)導(dǎo)致切換失敗[5]。

在PCI分配過(guò)程中，要避免發(fā)生PCI沖突和混淆。

3 基于圖論與遺傳算法的PCI重規(guī)劃

3.1 預(yù)測(cè)干擾矩陣建立

干擾矩陣描述了小區(qū)之間的相關(guān)性，建立該相關(guān)性的數(shù)據(jù)源包括路測(cè)數(shù)據(jù)、切換數(shù)據(jù)（網(wǎng)管統(tǒng)計(jì)）、掃頻數(shù)據(jù)或MR數(shù)據(jù)，可以使用其中的一種或多種。

PCI規(guī)劃的最終目的是為了提高無(wú)線網(wǎng)絡(luò)的SINR和小區(qū)吞吐率，因此構(gòu)建合理的干擾矩陣，重點(diǎn)關(guān)注服務(wù)小區(qū)與鄰小區(qū)電平差值對(duì)SINR和下行吞吐率的影響。由于在不同的無(wú)線網(wǎng)絡(luò)環(huán)境（包括傳播模型和網(wǎng)絡(luò)負(fù)荷）中這種影響存在差異，所以通過(guò)現(xiàn)網(wǎng)的統(tǒng)計(jì)數(shù)據(jù)中獲得服務(wù)小區(qū)和鄰小區(qū)電平差值與SINR和小區(qū)下行吞吐率的對(duì)應(yīng)關(guān)系比較可靠。本文采用的預(yù)測(cè)方法如下：

（1）平均SINR值預(yù)測(cè)

基于SINR值提升進(jìn)行PCI重規(guī)劃效果預(yù)測(cè)：通過(guò)對(duì)現(xiàn)網(wǎng)路測(cè)、切換、掃頻或MR數(shù)據(jù)等方法采集的數(shù)據(jù)進(jìn)行平均化處理，建立一個(gè)服務(wù)小區(qū)RSRP（Reference Signal Receiving Power，參考信號(hào)接收功率）與鄰區(qū)RSRP差值的二元關(guān)系矩陣A，該矩陣行列關(guān)系為31×60。其中，31行對(duì)應(yīng)服務(wù)小區(qū)與鄰區(qū)RSRP的差值范圍（-15～15 dBm），60列對(duì)應(yīng)服務(wù)小區(qū)電平強(qiáng)度RSRP的范圍（-115～-55 dBm），SINR均值即為該二元矩陣對(duì)應(yīng)的數(shù)值。矩陣又分為服務(wù)小區(qū)與鄰區(qū)具有模三關(guān)系和非模三關(guān)系的兩張表，服務(wù)小區(qū)電平與鄰區(qū)電平差值二元關(guān)系矩陣A表（局部）如表2所示。

對(duì)某個(gè)小區(qū)PCI規(guī)劃后SINR預(yù)估方法：以干擾矩陣為基礎(chǔ)，以每個(gè)預(yù)估點(diǎn)模三和非模三鄰區(qū)干擾疊加后對(duì)主小區(qū)SINR值的影響來(lái)計(jì)算此預(yù)估點(diǎn)的SINR。具體方法是將每個(gè)預(yù)估點(diǎn)的SINR值累加后除以總的采樣點(diǎn)數(shù)量，就可以預(yù)測(cè)此小區(qū)的SINR平均值。以此類推擴(kuò)展到整個(gè)規(guī)劃區(qū)域的小區(qū)，并以此SINR預(yù)估值作為評(píng)估PCI規(guī)劃方案優(yōu)劣的依據(jù)。

（2）小區(qū)下行吞吐率預(yù)測(cè)

通過(guò)對(duì)現(xiàn)網(wǎng)采集的數(shù)據(jù)進(jìn)行處理，計(jì)算出不同SINR對(duì)應(yīng)的下行平均速率，以此建立SINR與小區(qū)下行吞吐率的對(duì)應(yīng)關(guān)系一元表B，如表3所示：

對(duì)某個(gè)小區(qū)PCI規(guī)劃后吞吐率預(yù)估可以通過(guò)B表計(jì)算。將預(yù)估點(diǎn)的小區(qū)吞吐率數(shù)值累加后除以總的采樣點(diǎn)數(shù)量，即可預(yù)測(cè)此小區(qū)下行吞吐率平均值。類似地，可擴(kuò)展到規(guī)劃的整個(gè)區(qū)域，以此下行吞吐率預(yù)估值作為PCI規(guī)劃方案優(yōu)劣的依據(jù)。

通過(guò)上面的評(píng)估算法，可以得出SINR最優(yōu)或下行吞吐率最優(yōu)的兩大類方案供選擇（還可以給出多種折中方案），增加方案選擇的靈活性，再根據(jù)預(yù)測(cè)結(jié)果在方案執(zhí)行后驗(yàn)證預(yù)估的準(zhǔn)確性。

3.2 無(wú)向全連通圖模擬鄰區(qū)關(guān)系

圖論中的圖定義為由若干個(gè)不同頂點(diǎn)與連接其中頂點(diǎn)的邊組成的圖形，如果圖內(nèi)任意一個(gè)頂點(diǎn)通過(guò)現(xiàn)有連線均可以走到另外的任一點(diǎn)，就稱之為全連通圖[6]。如果邊是沒(méi)有方向的，就稱之為無(wú)向全連通圖。

將每個(gè)小區(qū)位置作為頂點(diǎn)，小區(qū)之間有鄰區(qū)關(guān)系的畫一條無(wú)向邊連線，連線的長(zhǎng)度為兩個(gè)小區(qū)之間的實(shí)際距離，直接把一張通信網(wǎng)變成一張頂點(diǎn)固定的無(wú)向全連通圖。在該模型中，小區(qū)之間的連線代表小區(qū)之間有鄰區(qū)關(guān)系，從一個(gè)小區(qū)出去的鄰區(qū)連線的距離和方向表示該小區(qū)與周圍小區(qū)的實(shí)際距離和方向，完全反映了網(wǎng)絡(luò)的真實(shí)情況。后續(xù)PCI重規(guī)劃過(guò)程中，模三干擾、PCI復(fù)用距離和復(fù)用層數(shù)、PCI沖突和混淆均基于該無(wú)向全連通圖來(lái)評(píng)估。

3.3 構(gòu)建小區(qū)模擬沖突關(guān)系

上文中對(duì)有切換次數(shù)的鄰區(qū)關(guān)系（或MR中達(dá)到一定測(cè)量門限的鄰區(qū)）之間都做了連線，如果從一個(gè)小區(qū)到另外一個(gè)小區(qū)經(jīng)過(guò)的最小連線數(shù)量為1或2且PCI相同，這兩個(gè)小區(qū)即為沖突關(guān)系。沖突關(guān)系實(shí)際上已經(jīng)反映了小區(qū)的覆蓋范圍（此處范圍不是指絕對(duì)的面積，而是相對(duì)的影響的小區(qū)數(shù)），如果與一個(gè)小區(qū)的沖突鄰區(qū)少，則說(shuō)明與該小區(qū)重疊覆蓋的鄰區(qū)少，該小區(qū)覆蓋范圍?。蝗绻c該小區(qū)沖突關(guān)系較多，則說(shuō)明該小區(qū)覆蓋范圍較大，影響鄰區(qū)多。在規(guī)劃過(guò)程中，每分配一個(gè)小區(qū)的PCI后，與該小區(qū)有沖突關(guān)系的鄰區(qū)就不再規(guī)劃該P(yáng)CI，否則會(huì)產(chǎn)生PCI沖突。沖突關(guān)系的計(jì)算采用圖論中的標(biāo)號(hào)法計(jì)算兩點(diǎn)間最短距離[7]，由于該方法屬于圖論的基本算法，本文不再贅述。

3.4 從邊緣到中心的遺傳生長(zhǎng)算法

與傳統(tǒng)規(guī)劃算法從中心向邊緣擴(kuò)展的方法不同，新算法以非規(guī)劃區(qū)域?yàn)槠瘘c(diǎn)，采用從邊緣向中心擴(kuò)展的規(guī)劃方式。每個(gè)基站分配的PCI需滿足：PCI復(fù)用距離和復(fù)用層數(shù)高于設(shè)定的最低值、模三干擾影響最?。ㄍㄟ^(guò)3.1節(jié)中的預(yù)測(cè)干擾矩陣進(jìn)行評(píng)估）、沖突小區(qū)PCI不相同，滿足這些條件的PCI組為待分配基站的合格PCI組。

錨點(diǎn)基站的選擇：即從未分配PCI的所有基站中選擇一個(gè)待分配PCI的基站。由于周邊小區(qū)PCI已經(jīng)分配，待分配PCI的基站能夠選擇的合格PCI組受限，這里選擇的錨點(diǎn)基站即為合格PCI組最少的基站，也就是受周邊制約最大的基站。

由于錨點(diǎn)基站可分配的不止一個(gè)合格PCI組，需要采用最優(yōu)組篩選算法確定哪組最優(yōu)，每分配一個(gè)基站的PCI就會(huì)造成后續(xù)要分配的基站無(wú)法選擇該P(yáng)CI，所以最優(yōu)組的選擇采用影響未分配基站最少的組作為最終選定組。

算法不停地重復(fù)錨點(diǎn)基站選擇、評(píng)估確定最優(yōu)組這兩個(gè)過(guò)程，直至PCI分配完成。該過(guò)程可能對(duì)PCI復(fù)用距離和復(fù)用層數(shù)、PCI沖突的要求過(guò)于嚴(yán)格，導(dǎo)致某個(gè)基站無(wú)合格PCI組，分配過(guò)程宣告失敗。如果發(fā)生分配失敗，則適當(dāng)降低對(duì)三者的要求，直至能夠完成所有基站的PCI規(guī)劃，算法計(jì)算完成。遺傳算法流程圖如圖3所示。

3.5 PCI重規(guī)劃前的無(wú)線優(yōu)化

PCI規(guī)劃效果與LTE網(wǎng)絡(luò)結(jié)構(gòu)息息相關(guān)。根據(jù)規(guī)劃經(jīng)驗(yàn)，一般小區(qū)高重疊覆蓋度（鄰區(qū)RSRP與服務(wù)小區(qū)RSRP差值在6 dB以內(nèi)，小區(qū)點(diǎn)數(shù)不小于3個(gè)，且最強(qiáng)小區(qū)RSRP不小于-105 dBm[9]）區(qū)域越多，小區(qū)間相關(guān)性越強(qiáng)，造成規(guī)劃算法中的約束條件就越強(qiáng)，方案改善幅度也越小。

因此，在PCI重規(guī)劃項(xiàng)目開始前需要先做一輪無(wú)線環(huán)境優(yōu)化，主要對(duì)過(guò)覆蓋及重疊覆蓋度影響較高的小區(qū)進(jìn)行天饋調(diào)整和優(yōu)化。

4 基于圖論和遺傳算法的PCI重規(guī)劃應(yīng)用案例

下面選擇了一個(gè)縣級(jí)市范圍內(nèi)的LTE小區(qū)作為PCI重規(guī)劃對(duì)象，區(qū)域包括周圍的高速、國(guó)道，如圖4的藍(lán)色區(qū)域，共涉及1253個(gè)小區(qū)。其中，黃色區(qū)域?yàn)楸臼蟹且?guī)劃區(qū)域；綠色區(qū)域?yàn)猷徥蟹且?guī)劃站點(diǎn)。

PCI重規(guī)劃前后的對(duì)比效果如下：

（1）PCI復(fù)用距離和復(fù)用層數(shù)改善情況

PCI重規(guī)劃前后復(fù)用距離對(duì)比圖如圖5所示。PCI重規(guī)劃后，復(fù)用距離由規(guī)劃前的1～9km變?yōu)?～9km的區(qū)間分布，且主要分布在9km以上，復(fù)用距離改善明顯。

PCI重規(guī)劃前后復(fù)用層數(shù)對(duì)比圖如圖6所示。PCI重規(guī)劃后，復(fù)用層數(shù)由規(guī)劃前的30層以內(nèi)為主變?yōu)橐?guī)劃后的90層以上為主，復(fù)用層數(shù)改善明顯。

（2）測(cè)試指標(biāo)對(duì)比

下面分別對(duì)SINR、下載速率、模三切換及采樣點(diǎn)占比和改善情況進(jìn)行對(duì)比分析，如表4所示。

具體如下：

◆SINR：平均有1.29 dB的提升（規(guī)劃預(yù)改善1.05 dB），

除高速提升不明顯外（由于高速小區(qū)是線性覆蓋，容易規(guī)劃，因此模三干擾相對(duì)較少），其它網(wǎng)元的SINR都有0.59～1.83 dB的提升，改善明顯；

◆下載速率：平均有1.65 Mbps的提升；

◆模三占比：模三切換占比減少了1.03%，模三采樣點(diǎn)占比減少了1.22%，模三干擾有所減少，PCI重規(guī)劃效果明顯。

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

本文對(duì)傳統(tǒng)的LTE小區(qū)PCI規(guī)劃方法進(jìn)行了改進(jìn)，引入圖論與遺傳算法，并結(jié)合網(wǎng)絡(luò)道路測(cè)試、掃頻、切換、MR數(shù)據(jù)建立干擾矩陣對(duì)PCI進(jìn)行重規(guī)劃，以達(dá)到減少小區(qū)PCI模三干擾且提升網(wǎng)絡(luò)整體SINR和下載速率的目的。該方法在實(shí)際的網(wǎng)絡(luò)PCI規(guī)劃中得到了驗(yàn)證，網(wǎng)絡(luò)現(xiàn)場(chǎng)測(cè)試和后臺(tái)統(tǒng)計(jì)指標(biāo)都有較明顯的提升及改善，從而證明了算法和工具的有效性。

參考文獻(xiàn)：

[1] Stefania Sesia， Issam Toufik， Matthew Baker. LTE——UMTS長(zhǎng)期演進(jìn)理論與實(shí)踐[M]. 馬霓，鄔鋼，張曉博，等譯. 北京： 人民郵電出版社， 2009.

[2] 龍青良，張磊. 基于用戶感知的LTE網(wǎng)絡(luò)優(yōu)化關(guān)鍵問(wèn)題研究[J]. 郵電設(shè)計(jì)技術(shù)， 2014（10）： 14-20.

[3] 韓斌杰. GSM原理及其網(wǎng)絡(luò)優(yōu)化[M]. 北京： 機(jī)械工業(yè)出版社， 2001.

[4] 元泉. LTE輕松進(jìn)階[M]. 北京： 電子工業(yè)出版社， 2012.

[5] 張守國(guó)，張建國(guó)，李曙海，等. LTE無(wú)線網(wǎng)絡(luò)優(yōu)化實(shí)踐[M]. 北京： 人民郵電出版社， 2014.

[6] Gary Chartrand， Ping Zhang. 圖論導(dǎo)引[M]. 范益政，汪毅，龔世才，譯. 北京： 人民郵電出版社， 2007.

[7] 徐俊明. 圖論及其應(yīng)用[M]. 合肥： 中國(guó)科學(xué)技術(shù)大學(xué)出版社， 2004.

[8] 周明，孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京： 國(guó)防工業(yè)出版社， 1999.

[9] 趙康成，王國(guó)梁，李鳳花. TD-LTE無(wú)線網(wǎng)絡(luò)中重疊覆蓋優(yōu)化解決方案分析[J]. 山東通信技術(shù)， 2014（3）： 40-43.

[10] 李青. TD-LTE系統(tǒng)PCI規(guī)劃方法研究[J]. 無(wú)線電通信技術(shù)， 2013，39（5）： 66-67.