基于改進(jìn)Welsh Powell的NPRACH子載波偏置自配置算法

黃炎水，謝佳銳

（中國(guó)移動(dòng)通信集團(tuán)廣東有限公司揭陽(yáng)分公司，廣東 揭陽(yáng) 522000）

1 引言

隨著3GPP標(biāo)準(zhǔn)的制定及智慧城市智能家居等產(chǎn)業(yè)的不斷發(fā)展，物聯(lián)網(wǎng)也迅猛發(fā)展?；诜涓C網(wǎng)絡(luò)的NB-IoT（Narrow Band Internet of Things，窄帶物聯(lián)網(wǎng)）技術(shù)由于具備了廣覆蓋、大連接、低功耗和低成本的特點(diǎn)，在業(yè)界備受矚目。

與LTE不同，NB-IoT主要應(yīng)用于低時(shí)延敏感性、低速率、小包業(yè)務(wù)場(chǎng)景，同時(shí)支持大連接，這樣的業(yè)務(wù)特點(diǎn)對(duì)網(wǎng)絡(luò)的接入性能提出了更高的要求。在LTE中，終端接入網(wǎng)絡(luò)時(shí)采用不同的前導(dǎo)序列，用于基站標(biāo)識(shí)不同終端。但是在NB-IoT中，終端接入網(wǎng)絡(luò)時(shí)采用相同的前導(dǎo)碼，基站標(biāo)識(shí)不同終端是通過(guò)終端接入時(shí)所采用的時(shí)頻資源。不同覆蓋等級(jí)的終端接入時(shí)采用不同的時(shí)域資源，同一覆蓋等級(jí)下的終端接入采用不同的頻域資源。終端所采用的時(shí)頻資源取決于小區(qū)的NPRACH（NB-IoT Physical Random Access Channel，NB-IoT物理隨機(jī)接入信道）配置，包括起始時(shí)間和子載波偏置配置。本文從子載波偏置配置入手，研究子載波偏置配置對(duì)NB-IoT終端接入的影響并提出可行的配置方法。

2 NPRACH子載波偏置

從時(shí)域上看，如圖1所示，NB-IoT的NPRACH由4個(gè)符號(hào)組構(gòu)成，每個(gè)符號(hào)組由1個(gè)CP（Cyclic Period，循環(huán)前綴）和5個(gè)符號(hào)組成，C P長(zhǎng)度分為兩種：66.7 μs和266.7μs。不同CP長(zhǎng)度用于支持不同的覆蓋距離，66.7 μs的CP長(zhǎng)度支持低于8 km的小區(qū)半徑。

圖1 NPRACH時(shí)域結(jié)構(gòu)

從頻域上看，NPRACH采用single-tone方式傳輸，子載波間隔3.75 kHz，180 kHz的帶寬分為48個(gè)子載波。NPRACH的傳輸采用跳頻的方式，分為兩層跳頻，一個(gè)是NPRACH中4個(gè)符號(hào)組的跳頻與重復(fù)發(fā)送時(shí)的跳頻。符號(hào)組之間的跳頻分成兩個(gè)層次，第一層次相差1個(gè)子載波，第二層次相差6個(gè)子載波，即22.5 kHz，用于第二個(gè)符號(hào)組與第三個(gè)符號(hào)組之間，如圖2所示。而重復(fù)發(fā)送時(shí)的跳頻是通過(guò)偽隨機(jī)序列來(lái)決定重復(fù)發(fā)送時(shí)的頻域起始位置。

NPRACH的初始頻域位置通過(guò)NPRACH的子載波偏置和子載波數(shù)量來(lái)決定。根據(jù)3GPP協(xié)議關(guān)于NB-IoT隨機(jī)接入信道子載波偏置的規(guī)定，子載波偏置有7種配置SC_0/SC_12/SC_24/SC_36/SC_2/SC_18/SC_34，而子載波數(shù)量有4種配置12/24/36/48，不同的子載波偏置可配置的子載波數(shù)量對(duì)應(yīng)關(guān)系如表1所示：

表1 NPRACH頻域配置

由表1可知，同頻組網(wǎng)的情況下，相鄰小區(qū)配置相同的子載波偏置時(shí)，位于兩個(gè)小區(qū)重疊覆蓋區(qū)域的用戶(hù)在發(fā)起隨機(jī)接入時(shí)，會(huì)導(dǎo)致用戶(hù)的初始頻域位置落在鄰小區(qū)NPRACH檢測(cè)頻域范圍內(nèi)，造成鄰小區(qū)的誤判，從而浪費(fèi)鄰小區(qū)的時(shí)頻資源，同時(shí)也影響鄰小區(qū)用戶(hù)的接入。相鄰小區(qū)同子載波偏置情況如圖3所示。

圖2 NPRACH跳頻傳輸

圖3 相鄰小區(qū)同子載波偏置情況

通過(guò)測(cè)試驗(yàn)證了相鄰小區(qū)同子載波偏置的影響，選取了同站點(diǎn)兩個(gè)小區(qū)，測(cè)試參數(shù)如表2所示。

在上述測(cè)試環(huán)境下，測(cè)試一個(gè)小時(shí)的隨機(jī)接入，統(tǒng)計(jì)后臺(tái)指標(biāo)，兩個(gè)小區(qū)隨機(jī)前導(dǎo)數(shù)量和沖突解決消息數(shù)量如表3所示：

表3 子載波偏置影響測(cè)試結(jié)果

由表3的測(cè)試結(jié)果可知，沖突的前導(dǎo)數(shù)量在修改后降低了65%，由此可見(jiàn)，鄰區(qū)配置相同子載波偏置的情況下，鄰區(qū)誤判的情況比較嚴(yán)重，因此，需要在規(guī)劃階段對(duì)NPRACH的子載波偏置進(jìn)行合理規(guī)劃。由表1可知，不同的子載波偏置配置使用不同范圍的子載波，同時(shí)又存在不同程度的交疊?，F(xiàn)網(wǎng)中，為了更好地利用48個(gè)子載波，同時(shí)減少?zèng)_突的數(shù)量，采用12個(gè)子載波數(shù)量更為合理，本文以12個(gè)子載波數(shù)量為例，提出基于改進(jìn)Welsh Powell染色的子載波偏置自配置算法。

3 子載波偏置自配置算法

3.1 問(wèn)題描述

在大規(guī)模建網(wǎng)的情況下，子載波偏置必須進(jìn)行復(fù)用，同時(shí)，需要保證使用相同子載波偏置的小區(qū)距離足夠遠(yuǎn)，盡可能避免重疊覆蓋。實(shí)際應(yīng)用中，功率參數(shù)、工作頻率、覆蓋區(qū)域的地理地貌等會(huì)直接影響復(fù)用的距離，可類(lèi)比于LTE中的PCI復(fù)用距離。根據(jù)Walfisch-Ikegami模型與NB-IoT的覆蓋增強(qiáng)特性，以及UE發(fā)射最大功率和基站接收NPRACH的檢測(cè)門(mén)限，可計(jì)算得出復(fù)用距離，在復(fù)用距離內(nèi)的其它小區(qū)不能采用相同的子載波偏置。

按照使用相同頻點(diǎn)的相鄰小區(qū)不能使用相同子載波偏置的原則，子載波偏置問(wèn)題可以抽象為圖的頂點(diǎn)著色問(wèn)題。給定圖G=(V, E)，稱(chēng)映射φ： V→{1, 2, 3, …,k}為G的一個(gè)k-點(diǎn)著色，稱(chēng){1, 2, 3, …, k}為色集。若對(duì)G中任意兩個(gè)相鄰頂點(diǎn)u和v均滿(mǎn)足φ(u)≠φ(v)，則稱(chēng)該著色為正常的。頂點(diǎn)著色問(wèn)題是一個(gè)NP-Hard問(wèn)題，傳統(tǒng)的解決算法有回溯算法、Welsh Powell算法等。

3.2 算法流程

子載波偏置問(wèn)題可以抽象為7-點(diǎn)著色問(wèn)題，但是又略有不同，子載波偏置問(wèn)題是存在限制條件的頂點(diǎn)著色問(wèn)題。子載波偏置問(wèn)題的限制條件在于7個(gè)子載波偏置配置中存在沖突的情況，如子載波偏置0與子載波偏置2存在頻域交疊，因此偏置0與偏置2不能相鄰，而在實(shí)際網(wǎng)絡(luò)中，又存在無(wú)法避免沖突的情況。傳統(tǒng)的Welsh Powell算法無(wú)法解決這一問(wèn)題，因此本文提出了改進(jìn)的Welsh Powell算法。改進(jìn)后的算法分成兩步，將原本的7-點(diǎn)著色問(wèn)題分解為4-點(diǎn)著色問(wèn)題和基于權(quán)值的3-點(diǎn)著色。

第一步，由于SC_0/SC_12/SC_24/SC_36這4個(gè)子載波偏置的頻域資源相互正交，因此采用Welsh Powell算法按照4-點(diǎn)著色的方式進(jìn)行著色；第二步，對(duì)于未著色的節(jié)點(diǎn)，通過(guò)基于權(quán)值的3-點(diǎn)著色算法解決，具體算法流程如圖4所示。

算法流程具體如下：

（1）根據(jù)網(wǎng)絡(luò)拓?fù)渑c各個(gè)站點(diǎn)間的距離，站點(diǎn)復(fù)用距離內(nèi)的其它站點(diǎn)視為相鄰頂點(diǎn)，生成節(jié)點(diǎn)的關(guān)聯(lián)矩陣V，距離矩陣D，將子載波偏置{SC_0, SC_12,SC_24, SC_36, SC_2, SC_18, SC_34}，記為集合c，根據(jù)各個(gè)子載波偏置對(duì)應(yīng)的交疊子載波個(gè)數(shù)通過(guò)矩陣的形式表示，得到子載波沖突矩陣，記為Ccorrupt，可以得到：

表2 子載波偏置影響測(cè)試參數(shù)

圖4 基于樹(shù)值的3-點(diǎn)著色算法流程

（2）根據(jù)關(guān)聯(lián)矩陣V計(jì)算節(jié)點(diǎn)關(guān)聯(lián)度數(shù)，將網(wǎng)絡(luò)拓?fù)渲械恼军c(diǎn)按照節(jié)點(diǎn)度數(shù)由大到小排序，生成排列s。

（3）對(duì)于排列s，先按照Welsh Powell算法進(jìn)行4-點(diǎn)著色。

◆取出SC_0，對(duì)第一節(jié)點(diǎn)進(jìn)行著色，并按排列順序?qū)εc前面著色節(jié)點(diǎn)不相鄰的每一節(jié)點(diǎn)都著上同樣的顏色；

◆對(duì)未著色的節(jié)點(diǎn)重新進(jìn)行排序，取出SC_12對(duì)尚未著色的節(jié)點(diǎn)重復(fù)步驟（3）的第一步，再取出SC_24與SC_36繼續(xù)著色。

（4）如果排列s中還存在尚未著色的節(jié)點(diǎn)，依次取出節(jié)點(diǎn)sk，計(jì)算c中7個(gè)子載波偏置的權(quán)值，記采用子載波偏置ci（0＜i≤7）且與sk相鄰的節(jié)點(diǎn)集合為b，則子載波偏置ci（0＜i≤7）的權(quán)值計(jì)算如下：

3.3 仿真驗(yàn)證

為了對(duì)比算法的實(shí)際效果，本文定義了子載波平均復(fù)用距離，通過(guò)每個(gè)子載波的最小復(fù)用距離的均值來(lái)衡量子載波沖突的程度。改進(jìn)算法與原始的Welsh Powell算法進(jìn)行對(duì)比，根據(jù)現(xiàn)實(shí)中的實(shí)際站點(diǎn)分布，采用Matlab工具仿真配置的結(jié)果。

仿真驗(yàn)證分為兩步，第一步是針對(duì)站點(diǎn)分布較為稀疏的情況，仿真13個(gè)站點(diǎn)分布的情況。對(duì)于站點(diǎn)分布較為稀疏的區(qū)域，基本通過(guò)第一步4-點(diǎn)著色可以完成區(qū)域的子載波偏置配置，稀疏區(qū)域的配置兩個(gè)算法結(jié)果相同，符合預(yù)期。圖5是稀疏區(qū)域的站點(diǎn)配置示意圖。

第二步對(duì)于站點(diǎn)密集分布的區(qū)域，沖突情況無(wú)法避免，通過(guò)權(quán)重來(lái)決定所使用的子載波偏置配置，分別對(duì)存在23個(gè)節(jié)點(diǎn)的區(qū)域和151個(gè)節(jié)點(diǎn)的區(qū)域進(jìn)行仿真，原始算法得到的結(jié)果如圖6和圖8所示，改進(jìn)后的算法配置結(jié)果如圖7和圖9所示。

圖5 稀疏區(qū)域的站點(diǎn)配置

圖6 原始算法下23個(gè)節(jié)點(diǎn)密集區(qū)域的站點(diǎn)配置

圖7 改進(jìn)算法下23個(gè)節(jié)點(diǎn)密集區(qū)域的站點(diǎn)配置

由兩個(gè)例子可以看出，在站點(diǎn)密集的情況下，盡管局部區(qū)域存在沖突，但是顏色總體布局合理，充分利用了不同的子載波偏置配置有效降低子載波偏置所帶來(lái)的沖突。計(jì)算子載波平均復(fù)用距離，得到表4的結(jié)果。

圖8 原始算法下151個(gè)節(jié)點(diǎn)密集區(qū)域的站點(diǎn)配置

圖9 改進(jìn)算法下151個(gè)節(jié)點(diǎn)密集區(qū)域的站點(diǎn)配置

表4 密集區(qū)域下不同配置算法仿真結(jié)果

從表4的結(jié)果可以看出，改進(jìn)算法對(duì)比原始算法有所提升，通過(guò)計(jì)算權(quán)重的方式可以有效地減少子載波沖突的情況。

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

本文將NB-IoT中隨機(jī)接入信道的子載波偏置配置問(wèn)題抽象成了圖論中的頂點(diǎn)著色問(wèn)題，又根據(jù)協(xié)議和現(xiàn)實(shí)情況對(duì)這一問(wèn)題進(jìn)行了研究，通過(guò)改進(jìn)的Welsh Powell算法來(lái)解決這一特定的著色問(wèn)題。本文算法可用于實(shí)際工程中NB-IoT網(wǎng)絡(luò)隨機(jī)接入信道的子載波偏置配置，可以減少時(shí)頻資源的浪費(fèi)，提高資源的利用率，同時(shí)避免沖突導(dǎo)致的用戶(hù)接入失敗以及由此引發(fā)的接入重試。同時(shí)，在算法中子載波偏置的權(quán)值采用系數(shù)法，可以通過(guò)修改系數(shù)來(lái)適用NB-IoT不同應(yīng)用場(chǎng)景下的配置，提高了算法的魯棒性。對(duì)于存在部分子載波偏置無(wú)法配置的情況，該算法也可以通過(guò)改變子載波沖突矩陣來(lái)實(shí)現(xiàn)自適應(yīng)。