基于遺傳算法的PCI分配方案

李盼星，王靜

（中國(guó)通信建設(shè)集團(tuán)設(shè)計(jì)院有限公司第一分公司，河北 保定 071000）

基于遺傳算法的PCI分配方案

李盼星，王靜

（中國(guó)通信建設(shè)集團(tuán)設(shè)計(jì)院有限公司第一分公司，河北 保定 071000）

針對(duì)傳統(tǒng)人工PCI規(guī)劃全局性差和耗時(shí)耗力的問題，提出一種基于遺傳算法的PCI分配方法（GA-PCIAS），該方法考慮了PCI規(guī)劃不沖突、不混淆的原則，并且通過將干擾矩陣引入適應(yīng)度函數(shù)可降低規(guī)劃區(qū)域內(nèi)的干擾程度，某密集市區(qū)的仿真實(shí)驗(yàn)證明，基站規(guī)模較小時(shí)，該算法相對(duì)于PCI順序規(guī)劃方案可有效降低規(guī)劃區(qū)域的干擾程度。

物理小區(qū)標(biāo)識(shí)；遺傳算法；LTE

1 引言

PCI（physical cell identity，物理小區(qū)標(biāo)識(shí)）是 LTE 網(wǎng)絡(luò)中與小區(qū)搜索和小區(qū)切換相關(guān)的參數(shù)，該參數(shù)會(huì)直接影響參考信號(hào)的位置［1］，若PCI規(guī)劃不合理會(huì)導(dǎo)致干擾問題的發(fā)生，極端情況下還可能產(chǎn)生掉話和切換失敗，因此合理的PCI規(guī)劃十分重要。目前傳統(tǒng)的人工PCI分配和優(yōu)化具有全局性差和耗時(shí)耗力等缺點(diǎn)，自分配和自優(yōu)化將成為今后的主要研究方向［2］。目前在PCI規(guī)劃方面的主要研究如下：

［2］提出一種基于蟻群算法的PCI規(guī)劃方法，該方法不但考慮了SON（self-organized network，自組織網(wǎng)絡(luò)）規(guī)范中提出的不沖突、不混淆原則，還可有效降低小區(qū)間的PCI干擾；

· 參考文獻(xiàn)［3，4］通過理論分析給出了 PCI配置原則和建議；

· 參考文獻(xiàn)［5，6］對(duì)PCI自配置方法進(jìn)行了研究；

· 參考文獻(xiàn)［7］提出一種PCI評(píng)估方法，可對(duì)整個(gè)網(wǎng)絡(luò)的PCI模三干擾情況進(jìn)行評(píng)估；

· 參考文獻(xiàn)［8］提出一種基于小區(qū)相關(guān)性的PCI調(diào)整方法，該方法通過計(jì)算優(yōu)化區(qū)域內(nèi)的總體干擾情況對(duì)模三干擾進(jìn)行調(diào)整，以得到最佳方案。提出若規(guī)劃基站過多可采用遺傳算法進(jìn)行計(jì)算，但并未給出詳細(xì)計(jì)算方法。

本文借鑒參考文獻(xiàn)［2］利用仿生學(xué)算法求解PCI最優(yōu)分配方案的思想，提出一種基于遺傳算法的PCI分配方案（GA-PCIAS），該方案考慮了PCI不沖突、不混淆的原則，并借鑒參考文獻(xiàn)［5］的思想將干擾矩陣引入適應(yīng)度函數(shù)以衡量模三干擾程度，通過確定性按比例選擇遺傳算法的計(jì)算得到使規(guī)劃區(qū)域內(nèi)干擾程度較低的分配方案。

2 GA-PCIAS算法描述

2.1 符號(hào)及數(shù)據(jù)結(jié)構(gòu)定義

（1）符號(hào)定義

本文所使用的符號(hào)定義見表1。

表1 符號(hào)定義

（2）干擾矩陣

干擾矩陣表示本小區(qū)與其他小區(qū)的干擾情況，本文定義的干擾矩陣格式見表2。其中，Iij為本小區(qū)與其他小區(qū)的干擾概率，在LTE為同頻組網(wǎng)的情況下，Iij為同頻干擾的概率。

2.2 PCI分配問題建模

PCI規(guī)劃應(yīng)遵循的原則如下。

· 可用號(hào)碼范圍：協(xié)議規(guī)定可用PCI為504個(gè)［9］，實(shí)際規(guī)劃中可能單獨(dú)規(guī)定某區(qū)域可用號(hào)碼范圍。

· 不沖突、不混淆原則［10］：相同的 PCI號(hào)碼間應(yīng)保證足夠的復(fù)用距離（至少間隔4層小區(qū)，并且距離大于5倍小區(qū)半徑［8］），并且同一小區(qū)下鄰區(qū)列表內(nèi)的小區(qū)PCI應(yīng)不同。

·避免模三干擾原則：雙天線端口要避免模三干擾，一般應(yīng)保證同基站下的3個(gè)扇區(qū)模三不同，相鄰基站對(duì)打的小區(qū)盡量保證模三不同，單天線端口要避免模六干擾。本文重點(diǎn)考慮模三干擾的情況。

針對(duì)以上PCI規(guī)劃原則，本文所設(shè)計(jì)的基于遺傳算法的PCI分配模型需滿足如下約束條件。

（1）針對(duì)可選號(hào)碼范圍

應(yīng)保證規(guī)劃區(qū)域的PCI號(hào)碼在可用號(hào)碼范圍內(nèi)。

（2）針對(duì)PCI號(hào)碼沖突和混淆的問題

對(duì)于小區(qū)數(shù)小于PCI可用號(hào)碼范圍的情況，本文采用不分配重復(fù)PCI的方法解決。例如設(shè)定某地區(qū)PCI可用號(hào)碼為0～200，按常規(guī)每基站3個(gè)扇區(qū)計(jì)算，可保證67個(gè)基站的PCI號(hào)碼不重疊分配，因此若該地區(qū)基站數(shù)小于67，則分配PCI時(shí)應(yīng)保證互不重疊；對(duì)于小區(qū)數(shù)大于PCI可用號(hào)碼范圍的情況，應(yīng)首先計(jì)算兩兩基站間的距離，若兩基站間距離小于允許的復(fù)用距離，則應(yīng)保證該兩基站PCI不同。本文主要研究遺傳算法在PCI分配問題上的應(yīng)用，因此重點(diǎn)研究小區(qū)數(shù)小于PCI可用號(hào)碼范圍的情況，對(duì)于小區(qū)數(shù)大于PCI可用號(hào)碼范圍的情況，只需額外考慮兩基站間距離小于復(fù)用距離時(shí)保證PCI不同即可。

表2 干擾矩陣

（3）針對(duì)模三干擾問題

在建立初始矩陣和遺傳算子操作時(shí)，都應(yīng)保證同一基站下3小區(qū)的模三不同。常規(guī)基站以三扇區(qū)為主，本文主要考慮常規(guī)每基站3個(gè)小區(qū)的情況，對(duì)于每基站小區(qū)數(shù)大于3個(gè)的情況，模三干擾不可避免。規(guī)劃時(shí)，應(yīng)盡量減小規(guī)劃區(qū)域內(nèi)總的干擾程度，對(duì)于干擾程度的衡量依靠前文提出的干擾矩陣。

本文要解決的問題為利用遺傳算法尋找滿足以上3個(gè)約束條件的n個(gè)小區(qū)的PCI號(hào)碼分配的最優(yōu)方案，優(yōu)化的目標(biāo)為小區(qū)間總的干擾函數(shù)盡量小。

2.3 GA-PCIAS中使用的遺傳算法規(guī)則

本文采用參考文獻(xiàn)［11］中所提出的確定性按比例選擇的遺傳算法，該算法是指在遺傳算子操作中采用按確定的百分比選擇參與操作的個(gè)體，相對(duì)于傳統(tǒng)的遺傳算法，具有可充分挖掘父代中最優(yōu)解信息、收斂速度快、易實(shí)施等優(yōu)點(diǎn)。

（1）染色體表示及編碼

常見的染色體編碼有二進(jìn)制編碼法和自然編碼法等，本文的PCI分配問題采用自然編碼法。通過列舉所有待規(guī)劃小區(qū)所使用的PCI號(hào)碼的方式進(jìn)行編碼。例如，某基站的 3 個(gè)小區(qū) site1-（0）、site1-（1）、site1-（2）所分配的 PCI號(hào)碼分別為 0、1、2，則該 PCI分配方案染色體編碼為［0、1、2］。按照 PCI定義，可選編碼最大取值范圍為 0～503，共504個(gè)值。針對(duì)于n個(gè)小區(qū)的場(chǎng)景，則染色體表示為［PCI1，PCI2，…，PCIn］。

（2）適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評(píng)價(jià)個(gè)體優(yōu)越性的標(biāo)準(zhǔn)，函數(shù)本身的優(yōu)劣會(huì)直接影響遺傳算法的可行性和收斂速度。本文中的適應(yīng)度函數(shù)為Fitness=1／Itotal，其中Itotal為干擾函數(shù)。定義如下：

其中：

可以看出，干擾函數(shù)為與模三干擾相關(guān)的干擾值，若兩小區(qū)間的 PCI模三相等，則 Cij=Iij；若不相等，則為 0，在干擾矩陣中Iij與Iji不一定相同。

（3）初始種群形成

初始種群的產(chǎn)生有兩種：一種是隨機(jī)產(chǎn)生，適合于毫無先驗(yàn)知識(shí)的情況；另一種是將某些先驗(yàn)知識(shí)轉(zhuǎn)化為約束條件，然后再產(chǎn)生滿足條件的樣本。如前文所述，本文初始種群的產(chǎn)生需要滿足以下3個(gè)條件：一是同一基站下3個(gè)小區(qū)的PCI模三不同；二是為增加初始種群的多樣性，加快收斂速度，基站間各小區(qū)的模三值順序應(yīng)不同；三是產(chǎn)生的PCI號(hào)碼應(yīng)在所規(guī)定的可用號(hào)碼范圍內(nèi)。例如，某地區(qū)有n個(gè)小區(qū)，規(guī)定其 PCI可選范圍為 0～100，則產(chǎn)生的初始種群見表3，其中染色體種群數(shù)量為m。

（4）選擇算法

采用確定性按比例選擇算法，將每代適應(yīng)度最高的前a%個(gè)體遺傳到下一代，以保證最優(yōu)個(gè)體的保存，加快收斂速度。

（5）交叉算法

交叉的操作方法有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等，本文采用單點(diǎn)交叉的方法，即從父代選擇適應(yīng)度較低的b%個(gè)體進(jìn)行兩兩交叉。交叉操作的目的主要是實(shí)現(xiàn)站間PCI值的整體互換。為保證同基站下3個(gè)小區(qū)PCI號(hào)碼的模三不同，交叉節(jié)點(diǎn)應(yīng)選擇3的倍數(shù)，交叉后若個(gè)體中有重復(fù)PCI號(hào)碼出現(xiàn)，應(yīng)將該重復(fù)號(hào)碼替換為該個(gè)體中未使用過且與該重復(fù)號(hào)碼模三相同的PCI，并且替換號(hào)碼也應(yīng)在規(guī)定的PCI可選范圍內(nèi)。具體操作如圖1所示，假定PCI可選范圍為0～20，待交叉染色體A、B交叉后染色體B產(chǎn)生重復(fù)號(hào)碼 “3”，則應(yīng)在0～10中選擇B未使用過且模三同樣等于0的號(hào)碼“0”或“9”進(jìn)行替代。

表3 產(chǎn)生的初始種群

（6）變異算法

從子代選擇適應(yīng)度較差的c%個(gè)體進(jìn)行變異操作，變異操作的目的主要是實(shí)現(xiàn)同一基站下小區(qū)內(nèi)PCI值互換，如圖2所示。具體變異方法如下：從染色體A中選擇變異節(jié)點(diǎn)（為保證同基站下3個(gè)小區(qū)PCI號(hào)碼模三不同，變異節(jié)點(diǎn)同樣應(yīng)為3的倍數(shù)），將變異節(jié)點(diǎn)前同一基站下3個(gè)小區(qū)的PCI值進(jìn)行隨機(jī)互換。變異操作也應(yīng)保證非法PCI的生成。

（7）微調(diào)

若現(xiàn)網(wǎng)要求同一基站下SSS（secondary synchronization signal，輔同步信號(hào)）號(hào)碼相同，則需要對(duì)遺傳算法執(zhí)行的結(jié)果進(jìn)行微調(diào)，微調(diào)的原則為：替換的號(hào)碼應(yīng)在PCI可選范圍內(nèi)，且其他基站未使用過；替換的號(hào)碼模三值與被替換號(hào)碼相同；號(hào)碼替換后同一基站下SSS相同，如圖3所示。

圖1 交叉算法示意

圖2 變異算法示意

圖3 微調(diào)過程示意

3 仿真與分析

為驗(yàn)證本文所提算法的有效性，擬對(duì)某密集市區(qū)站數(shù)分別為 13、22、31、55、72、90 時(shí)的 6 種場(chǎng)景進(jìn)行仿真，建立仿真環(huán)境如下：制式為 TD-LTE，頻段為 1.8 GHz，帶寬為20 MHz，DL：UL 為 2：2，天線傳輸模式為自適應(yīng)模式。

3.1 算法的有效性驗(yàn)證

以場(chǎng)景一（基站數(shù)為13個(gè)）為例對(duì)算法的有效性進(jìn)行說明。在上述仿真場(chǎng)景下，由網(wǎng)絡(luò)規(guī)劃軟件獲得場(chǎng)景一下干擾矩陣部分?jǐn)?shù)據(jù)見表4。

利用本文所提GA-PCIAS對(duì)上述13個(gè)基站進(jìn)行PCI規(guī)劃，設(shè)置遺傳算法選擇比例約為23%，交叉比例約為77%，變異比例為30%，最大迭代次數(shù)為100次，則干擾函數(shù)與迭代次數(shù)的關(guān)系如圖4所示。

圖4 遺傳算法計(jì)算過程

由圖4中可以看出，隨著迭代次數(shù)的增加，干擾函數(shù)在逐漸減小，即規(guī)劃區(qū)域內(nèi)總的干擾值在下降，迭代次數(shù)為11次時(shí)即達(dá)到了最優(yōu)。達(dá)到最優(yōu)值時(shí)對(duì)應(yīng)的PCI分配方案見表5。

若要求SSS相同，則微調(diào)后結(jié)果見表6，經(jīng)過微調(diào)后可以發(fā)現(xiàn) PSS（primary synchronization signal，主同步信號(hào)）未發(fā)生變化，而同一基站下的SSS變?yōu)橄嗤怠?/p>

表4 干擾矩陣

3.2 算法優(yōu)化效果驗(yàn)證

為驗(yàn)證算法的優(yōu)化效果及適用范圍，將本文所提出的GA-PCIAS 與 PCI順序分配方案（即 site1-（0）、site1-（1）、site1-（2）、site2-（0）等小區(qū)的 PCI分配依次為 0、1、2、3…）輸入網(wǎng)絡(luò)規(guī)劃軟件Atoll中，分別對(duì)6種場(chǎng)景進(jìn)行仿真，由于PCI規(guī)劃對(duì)于空載和建網(wǎng)初期加載量較小時(shí)的RS-SINR （reference signal-signal to interference plus noise ratio，參考信號(hào)的信號(hào)與干擾加噪聲比）影響較大，因此設(shè)置加載量為5%，得到兩種分配方案在規(guī)劃區(qū)域內(nèi)RS-SINR≥-3 dB的覆蓋面積對(duì)比效果，如圖5所示。

表5 最優(yōu)分配方案

表6 對(duì)最優(yōu)方案進(jìn)行微調(diào)

由圖5可見，基站規(guī)模較小時(shí)，GA-PCIAS的分配方案所得的RS-SINR要明顯優(yōu)于順序分配方案；隨著基站規(guī)模增大，遺傳算法收斂變慢，迭代次數(shù)增加，其相對(duì)于順序分配方案的優(yōu)勢(shì)減弱。多次仿真結(jié)果顯示，當(dāng)基站規(guī)模為72個(gè)、90個(gè)時(shí)，GA-PCIAS的最優(yōu)解與順序分配方案相同，建議基站規(guī)模較小時(shí)，采用GA-PCIAS算法；基站規(guī)模較大時(shí)，可考慮采用順序分配方案。

圖5 覆蓋面積對(duì)比效果

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

本文提出一種基于遺傳算法的PCI分配方案，該方案可通過遺傳算法進(jìn)行全局搜索，且具有收斂速度快、操作簡(jiǎn)單易實(shí)施的優(yōu)點(diǎn)，仿真結(jié)果表明，基站規(guī)模較小時(shí)，該算法相對(duì)于順序分配方案可以有效降低規(guī)劃區(qū)域內(nèi)的干擾程度，在網(wǎng)絡(luò)規(guī)劃初期可以結(jié)合網(wǎng)絡(luò)規(guī)劃軟件輸出的干擾矩陣進(jìn)行使用，或者應(yīng)用于可插拔、代價(jià)小的小基站PCI配置中；基站規(guī)模較大時(shí)，可考慮采用順序分配方案。

參考文獻(xiàn)：

［1］3GPP TS 36.211.Technical specification group radio access network；evolved universal terrestrial radio access （E-UTRA）；physical channels and modulation（Release 10）［S］.2012.

［2］劉金燦.TD-LTE系統(tǒng)的 PCI規(guī)劃研究與應(yīng)用［D］.北京：北京郵電大學(xué)，2014.LIU J C.Research and application of PCI planning in TD-LTE system ［D］. Beijing： Beijing University of Posts and Telecommunications，2014.

［3］李青.TD-LTE系統(tǒng)PCI規(guī)劃方法研究 ［J］.無線電通信技術(shù)，2013，39（5）：66-67，92.LI Q.Research ofTD-LTE PCI planning ［J］.Radio Communications Technology，2013，39（5）：66-67，92.

［4］李壽鵬，張國(guó)棟，蘇雷.TD-LTE 系統(tǒng) PCI配置分析［J］.電信工程技術(shù)與標(biāo)準(zhǔn)化，2012（9）：50-54.LI S P，ZHANG G D，SU L.Research of TD-LTE PCI configuration ［J］. Telecom Engineering Technics and Standardization，2012（9）：50-54.

［5］孫成丹，張洪巖，魏垚，等.LTE-Advanced系統(tǒng)中PCI自配置仿真研究［J］.電信科學(xué)，2013，29（7）：30-36.SUN C D，ZHANG H Y，WEI Y，et al.Simulation research for PCI automatic allocation in LTE-Advanced system ［J］.Telecommunications Science，2013，29（7）：30-36.

［6］朱曉光，江華.LTE基站系統(tǒng)的PCI自配置技術(shù)研究［J］.電信科學(xué)，2014，30（7）：130-134.ZHU X G，JIANG H.Research on PCI self-configuration technology of LTE eNB system［J］.Telecommunications Science，2014，30（7）：130-134.

［7］郭建光，高克儉，王猛.TD-LTE 網(wǎng)絡(luò) PCI評(píng)估研究［J］.電信工程技術(shù)與標(biāo)準(zhǔn)化，2015（2）：35-38.GUO J G，GAO K J，WANG M.Research on TD-LTE network PCI assessment ［J］.Telecom Engineering Technics and Standardization，2015（2）：35-38.

［8］侯優(yōu)優(yōu)，隋延峰.基于小區(qū)相關(guān)性的PCI優(yōu)化方法研究［J］.電信工程技術(shù)與標(biāo)準(zhǔn)化，2013（3）：25-29.HOU Y Y，SUI Y F.PCI optimization method based on the cell correlation ［J］. Telecom Engineering Technics and Standardization，2013（3）：25-29.

［9］3GPP TS 36.300.Technical specification group radio access network；evolved universal terrestrial radio access （E-UTRA）；physical channels and modulation（Release 9）［S］.2012.

［10］3GPP TR 36.902.Evolved universal terrestrial radio access network solutions［S］.2011.

［11］王振朝，王靜，荊鑫.基于遺傳算法的多路徑錄用研究［J］.計(jì)算機(jī)工程，2011，37（20）：197-199.WANG Z C，WANG J，JING X.Multipath routing of genetic algorithm in Ad Hoc networks ［J］.Computer Engineering，2011，37（20）：197-199.

PCI planning method based on genetic algorithm in LTE network

LI Panxing，WANG Jing
The First Branch of China International Telecommunication Construction Group Design Institute Co.，Ltd.，Baoding 071000，China

In order to avoid local optimum and the consumption on time and strength in traditional manual planning，an method of PCI planning based on genetic algorithm（GA-PCIAS）was proposed，the method took full consideration of the PCI planning principle，and the interference matrix was introduced to fitness function to reduce the interference in planned area.The simulation results in an dense area show that GA-PCIAS can improve RS-SINR（reference signal-signal to interference plus noise ratio）comparing with the classical sequential PCI allocation on small-scale base station.

physical cell identity，genetic algorithm，LTE

TN929.5

A

10.11959／j.issn.1000-0801.2016082

2015-09-25；

2016-02-18

李盼星（1982-），男，中國(guó)通信建設(shè)集團(tuán)設(shè)計(jì)院有限公司第一分公司工程師，主要從事無線網(wǎng)絡(luò)規(guī)劃、決策方法研究等工作。

王靜（1986-），女，中國(guó)通信建設(shè)集團(tuán)設(shè)計(jì)院有限公司第一分公司工程師，主要從事無線網(wǎng)絡(luò)規(guī)劃等工作。