0 引言

    近年來(lái)，推行動(dòng)態(tài)頻譜管理已成為國(guó)際主流趨勢(shì)。認(rèn)知無(wú)線電（Cognitive Radio，CR）的提出打破了傳統(tǒng)封閉式、保護(hù)式的頻率劃分機(jī)制，允許無(wú)線通信設(shè)備及系統(tǒng)對(duì)周?chē)l譜環(huán)境進(jìn)行動(dòng)態(tài)感知，并以高效、靈活的方式進(jìn)行頻譜接入^[1]。為進(jìn)一步改善認(rèn)知無(wú)線電系統(tǒng)性能，無(wú)線電環(huán)境地圖（Radio Environment Map，REM）技術(shù)應(yīng)運(yùn)而生。

    REM是對(duì)復(fù)雜無(wú)線電環(huán)境的一種數(shù)字化抽象，反映多維無(wú)線電環(huán)境及場(chǎng)景信息，其概念最早由學(xué)者趙友平于2005年提出^[2]，現(xiàn)已得到創(chuàng)新無(wú)線國(guó)際論壇（Wireless Innovation Forum）的認(rèn)同以及IEEE、ITU-R、ETSI相關(guān)標(biāo)準(zhǔn)文件的采納或引用^[3]。2010年，歐盟第七框架計(jì)劃（Framework Program 7，F(xiàn)P7）啟動(dòng)研究項(xiàng)目FARAMIR（Flexible and Spectrum-Aware Radio Access through Measurements and Modelling in Cognitive Radio Systems），其核心任務(wù)就是開(kāi)發(fā)一套完整的REM原型系統(tǒng)，增強(qiáng)歐洲工業(yè)在無(wú)線頻譜優(yōu)化、無(wú)線電監(jiān)管方面的創(chuàng)新能力^[4-7]。目前，多個(gè)大學(xué)、研究機(jī)構(gòu)對(duì)基于REM的頻譜管理技術(shù)做了研究^[8-12]。

    空間插值（Spatial Interpolation）是一種利用已知數(shù)據(jù)點(diǎn)來(lái)估計(jì)其他未知節(jié)點(diǎn)，從而填補(bǔ)數(shù)據(jù)點(diǎn)之間的空白的方法[13]，廣泛應(yīng)用于地理信息系統(tǒng)（GIS）、圖像處理及室內(nèi)定位等領(lǐng)域。常用的空間插值算法有反距離加權(quán)（Inverse Distance Weighting，IDW）法^[14-15]、自然鄰域法^[13]、樣條函數(shù)插值法^[16]及克里金插值法^[17]等。本文對(duì)空間插值算法進(jìn)行比較、改進(jìn)，將空間插值算法應(yīng)用于無(wú)線電環(huán)境分析，提出一種基于接收信號(hào)強(qiáng)度（RSS）以及空間插值的REM生成方法。

1 空間插值

1.1 通用模型及經(jīng)典算法

    空間相似性是空間插值的基本原理，即越接近數(shù)據(jù)點(diǎn)的值，與數(shù)據(jù)點(diǎn)相似程度越大。空間插值的通用模型為：

其中，P(x₀，y₀)為待插值點(diǎn)(x₀，y₀)某屬性的估計(jì)值，P(x_i，y_i)為N個(gè)已知數(shù)據(jù)點(diǎn)在各個(gè)位置(x_i，y_i)上的屬性值，ω_i(x₀，y₀)為各數(shù)據(jù)點(diǎn)對(duì)待插值點(diǎn)分配的權(quán)值。

    經(jīng)典IDW算法是一種全局空間插值算法，最早由SHEPARD D提出^[14]。該方法將已知數(shù)據(jù)點(diǎn)對(duì)待插值點(diǎn)的權(quán)值ω_i視為距離的負(fù)冪指數(shù)。該方法實(shí)現(xiàn)簡(jiǎn)單，提出后被廣泛應(yīng)用。

    由RENKA R J提出的優(yōu)化型Shepard算法（Modified Shepard′s Method，MSM）^[15]對(duì)經(jīng)典IDW算法進(jìn)行了較大改進(jìn)。為提高計(jì)算效率，MSM算法定義待插值點(diǎn)的影響半徑R，只考慮d_i≤R范圍內(nèi)數(shù)據(jù)點(diǎn)對(duì)待插值點(diǎn)的影響，從而將權(quán)值ω_i計(jì)算式定義為：

其中，d_i為待插值點(diǎn)(x₀，y₀)與某一數(shù)據(jù)點(diǎn)(x_i，y_i)之間的歐式距離，d_exp為權(quán)重指數(shù)。該算法的理想模型為所有數(shù)據(jù)點(diǎn)在區(qū)域中按正方形網(wǎng)格均勻分布。

1.2 改進(jìn)型MSM算法

    本文在MSM算法基礎(chǔ)上，提出一種改進(jìn)型MSM算法（Revised Modified Shepard′s Method，RMSM），從以下3個(gè)方面進(jìn)行改進(jìn)：

    (1)進(jìn)一步優(yōu)化權(quán)值計(jì)算。由于REM應(yīng)用場(chǎng)景中，數(shù)據(jù)點(diǎn)分布不一定為理想模型。當(dāng)數(shù)據(jù)點(diǎn)少、分布不均時(shí)，MSM算法將會(huì)出現(xiàn)權(quán)值ω_i分配不合理的情況。因此，RMSM算法將權(quán)值ω_i定義為一個(gè)相對(duì)值：

其中，i=1，2，…，N；ω₀為距離待插值點(diǎn)最近點(diǎn)的權(quán)值，ω_i仍利用式(2)計(jì)算。

    (2)靈活地使用局部特征。MSM算法提出了將數(shù)據(jù)點(diǎn)擬合為節(jié)點(diǎn)方程Q(x，y)的思想，其目的是利用某一數(shù)據(jù)點(diǎn)(x_i，y_i)影響半徑R內(nèi)其他數(shù)據(jù)點(diǎn)的局部特性，對(duì)其自身RSS值P(x_i，y_i)進(jìn)行優(yōu)化調(diào)整。但在實(shí)際REM場(chǎng)景下，影響半徑R的選取存在一定局限性，如：當(dāng)數(shù)據(jù)點(diǎn)分布不均（如集中于某一點(diǎn)附近）時(shí)，MSM算法可能會(huì)出現(xiàn)影響半徑R內(nèi)數(shù)據(jù)點(diǎn)較少甚至無(wú)數(shù)據(jù)點(diǎn)的情況。為此，RMSM算法通過(guò)選取N_W個(gè)近鄰節(jié)點(diǎn)進(jìn)行待插值點(diǎn)RSS值的估計(jì)，并選取N_q個(gè)近鄰數(shù)據(jù)點(diǎn)來(lái)對(duì)這N_W個(gè)點(diǎn)進(jìn)行節(jié)點(diǎn)方程Q(x，y)的擬合。

    區(qū)域中某一數(shù)據(jù)點(diǎn)(x_k，y_k)的節(jié)點(diǎn)方程Q_k(x，y)可為多種形式，而為了更貼近REM場(chǎng)景下無(wú)線電傳播特性，RMSM算法采用式(4)所示的二次形式來(lái)擬合：

式中，1<N_q，N_W≤N；d_j為區(qū)域中某一已知數(shù)據(jù)點(diǎn)(x_i，y_i)與選取的N_q個(gè)數(shù)據(jù)點(diǎn)中某一數(shù)據(jù)點(diǎn)(x_j，y_j)的歐式距離；d_k為待插值點(diǎn)(x，y)與選取的N_W個(gè)數(shù)據(jù)點(diǎn)中某一數(shù)據(jù)點(diǎn)(x_k，y_k)的歐式距離，如圖1所示。N_q、N_W無(wú)必然聯(lián)系，可以相等，也可不等。

    (3)高效的近鄰搜索法。為了找到待插值點(diǎn)(x₀，y₀)的N_W個(gè)近鄰節(jié)點(diǎn)以及其中每一個(gè)點(diǎn)的N_q個(gè)近鄰節(jié)點(diǎn)，RMSM算法通過(guò)構(gòu)造KD-Tree數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行兩次近鄰搜索。KD-Tree（k-Dimensional Tree）數(shù)據(jù)結(jié)構(gòu)^[18]通常用于k維空間中的范圍搜索及近鄰搜索。KD-Tree通過(guò)超平面分割空間，將空間中的數(shù)據(jù)點(diǎn)劃分為一種特殊的二叉樹(shù)結(jié)構(gòu)，在進(jìn)行近鄰搜索時(shí)只用通過(guò)其子樹(shù)回溯查找，無(wú)需遍歷所有數(shù)據(jù)點(diǎn)，當(dāng)數(shù)據(jù)點(diǎn)多時(shí)可大大減少搜索次數(shù)。搜索結(jié)束后，將選取的N_W個(gè)數(shù)據(jù)點(diǎn)RSS值優(yōu)化為：

    理想的空間插值是將離散的數(shù)據(jù)點(diǎn)擴(kuò)展為連續(xù)的數(shù)據(jù)曲面，而實(shí)際中為了將點(diǎn)數(shù)據(jù)盡可能擴(kuò)充為面數(shù)據(jù)，常利用網(wǎng)格化的思想，即將插值區(qū)域按一定的分辨率（即網(wǎng)格大?。﹦澐譃榫W(wǎng)格區(qū)域，并對(duì)每一個(gè)網(wǎng)格點(diǎn)進(jìn)行空間插值。無(wú)線電環(huán)境地圖（REM）的生成就是將若干個(gè)位置的RSS擴(kuò)展為區(qū)域性的綜合信號(hào)強(qiáng)度，利用已知數(shù)據(jù)點(diǎn)進(jìn)行網(wǎng)格化插值。

2 算法流程及復(fù)雜度分析

2.1 算法主要流程

    (1)輸入：

    ①RMSM算法相關(guān)參數(shù)：N、d_exp、N_q、N_W。

    ②網(wǎng)格區(qū)域相關(guān)參數(shù)：X_min、X_max、Y_min、Y_max，網(wǎng)格點(diǎn)數(shù)M=X_points×Y_points。(X_points、Y_points為兩個(gè)坐標(biāo)軸上的網(wǎng)格點(diǎn)數(shù))

    (2)初始化：

    ①數(shù)據(jù)點(diǎn)矩陣points：

        double[，] points=new double[N，3]

    并輸入數(shù)據(jù)：

    ②權(quán)值矩陣ω′與節(jié)點(diǎn)方程值矩陣q：

        double[] w1=new double[Nq]

        double[] w2=new double[Nw]

        double[] q=new double[Nw]

    ③網(wǎng)格點(diǎn)（即所有待插值點(diǎn)）矩陣XY：

        double[，] XY=new double[xPoints，yPoints]

    (3)將points中的數(shù)據(jù)集構(gòu)造為二維KD-Tree數(shù)據(jù)結(jié)構(gòu)；

    (4)從第一個(gè)網(wǎng)格點(diǎn)(m=1)開(kāi)始，重復(fù)以下步驟①~③：

    ①搜索待插值點(diǎn)的N_W個(gè)近鄰數(shù)據(jù)點(diǎn)，利用式(4)計(jì)算權(quán)值，從而：

    ②分別搜索N_W個(gè)數(shù)據(jù)點(diǎn)的N_q個(gè)近鄰數(shù)據(jù)點(diǎn)，利用式(6)進(jìn)行節(jié)點(diǎn)方程擬合，輸出節(jié)點(diǎn)方程值矩陣q：

    ③輸出結(jié)果：

    (5)直至最后一個(gè)網(wǎng)格點(diǎn)(m=M)計(jì)算完畢，輸出M個(gè)結(jié)果，算法結(jié)束。

2.2 復(fù)雜度分析

    IDW Classic算法是一種全局插值法，利用空間中所有數(shù)據(jù)點(diǎn)進(jìn)行插值，當(dāng)數(shù)據(jù)點(diǎn)為N時(shí)，其復(fù)雜度為O(N)；當(dāng)空間中網(wǎng)格點(diǎn)數(shù)為M時(shí)，利用該算法生成無(wú)線電環(huán)境地圖（REM）復(fù)雜度將達(dá)到O(MN)。MSM與RMSM均為局部插值法，一般情況局部數(shù)據(jù)點(diǎn)數(shù)N′<N（取決于影響半徑R及參數(shù)N_q/N_W的選?。?，兩種算法都使用復(fù)雜度為O(logN)的近鄰（NN）搜索法尋找局部數(shù)據(jù)點(diǎn)，因此總體復(fù)雜度均為O(MlogN)。

    不難看出，MSM及RMSM算法較IDW Classic在計(jì)算效率上已明顯提高，而選取的網(wǎng)格越密，則REM越接近連續(xù)的數(shù)據(jù)面，但帶來(lái)的計(jì)算量也越大。

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)場(chǎng)景

    本實(shí)驗(yàn)在一個(gè)15 m×20 m的室內(nèi)區(qū)域進(jìn)行，存在一定的墻、障礙物等非視距傳播環(huán)境，總體傳播環(huán)境良好。區(qū)域內(nèi)均勻分布6個(gè)路由器(圖2中TX1~TX6)發(fā)射2.4 GHz WiFi信號(hào)，用手機(jī)測(cè)量其信號(hào)強(qiáng)度（RSS）。

    本文的算法均在Visual Studio 2010開(kāi)發(fā)平臺(tái)下利用C#實(shí)現(xiàn)，并使用SQL Server 2008數(shù)據(jù)庫(kù)存儲(chǔ)相關(guān)數(shù)據(jù)。首先，利用6個(gè)路由器隨機(jī)組合6種不同的無(wú)線電場(chǎng)景，每個(gè)場(chǎng)景測(cè)量50個(gè)不同位置的信號(hào)強(qiáng)度（RSS，單位為dBm）。之后，使用前文所述的算法進(jìn)行實(shí)驗(yàn)，每個(gè)場(chǎng)景選擇3個(gè)點(diǎn)(圖2中誤差分析點(diǎn)P1~P3)來(lái)計(jì)算插值(即每個(gè)點(diǎn)計(jì)算3×6=18次)。實(shí)驗(yàn)相關(guān)參數(shù)設(shè)置見(jiàn)表1。

3.2 誤差分析

    圖3展示了3種算法(IDW Classic、MSM及RMSM)在不同數(shù)據(jù)點(diǎn)N下的誤差棒圖，圖中柱狀圖表示該算法的平均絕對(duì)誤差（MAE）：

式中，分別為RSS測(cè)量值與計(jì)算值，S為實(shí)驗(yàn)次數(shù)（此處S=18）。線段的長(zhǎng)度表示誤差的標(biāo)準(zhǔn)差，關(guān)于平均誤差值對(duì)稱，其大小反映了一個(gè)算法的穩(wěn)定性。

    IDW Classic算法由于使用所有數(shù)據(jù)點(diǎn)進(jìn)行計(jì)算，復(fù)雜度較高，加之測(cè)量數(shù)據(jù)本身具有一定誤差，其穩(wěn)定性不如其他算法(標(biāo)準(zhǔn)差大)，平均絕對(duì)誤差(MAE)也較大；MSM算法雖然穩(wěn)定性優(yōu)于IDW Classic，但在數(shù)據(jù)點(diǎn)較少時(shí)性能最差，如圖3(a)所示；而由于RMSM算法優(yōu)化了權(quán)值分配并靈活地選擇數(shù)據(jù)點(diǎn)，與IDW Classic算法相比，圖3中可明顯看出穩(wěn)定性提高了近一半（N=30、N=50時(shí)分別提高了50.4%、55.37%)，在數(shù)據(jù)點(diǎn)較低時(shí)也能保持較低的MAE及良好的穩(wěn)定性。

    圖4展示了RMSM算法在不同N_q/N_W選取下的情況。由于室內(nèi)傳播環(huán)境良好，因此N_q=20時(shí)算法性能較好，如圖4(b)所示，最佳情況為N_q=20，N_W=30，此時(shí)MAE≈2.85 dB(與IDW Classic相比降低了1.96 dB)，算法穩(wěn)定性也良好，標(biāo)準(zhǔn)差在2.48 dB左右。若傳播環(huán)境較差(存在較多非視距傳播情況)，則需選取較大N_q、N_W值進(jìn)行實(shí)驗(yàn)。

3.3 無(wú)線電環(huán)境地圖(REM)的生成

    基于以上分析，本實(shí)驗(yàn)采用各方面性能較為良好的RMSM算法。實(shí)驗(yàn)場(chǎng)景仍為圖2所示場(chǎng)景，6個(gè)路由器（TX1~TX6）同時(shí)工作。隨機(jī)選取50個(gè)位置測(cè)量信號(hào)強(qiáng)度RSS(即數(shù)據(jù)點(diǎn)N=50)其中設(shè)置參數(shù)N_q=20，N_W=30。圖5展示了不同網(wǎng)格點(diǎn)數(shù)M下生成的REM示意圖，圖5(a)網(wǎng)格點(diǎn)數(shù)M=1 200，圖5(b)M=30 000，可見(jiàn)，離發(fā)射機(jī)越近的位置信號(hào)強(qiáng)度(RSS)越大；另外，M越大，REM越接近于連續(xù)的數(shù)據(jù)曲面。

4 結(jié)論

    本文在國(guó)內(nèi)外認(rèn)知無(wú)線電(CR)、無(wú)線電環(huán)境地圖(REM)領(lǐng)域相關(guān)文獻(xiàn)的研讀及FARAMIR項(xiàng)目技術(shù)報(bào)告的學(xué)習(xí)基礎(chǔ)上，介紹了空間插值的一般模型，提出了一種基于接收信號(hào)強(qiáng)度(RSS)及空間插值的REM生成技術(shù)，為當(dāng)前及未來(lái)的動(dòng)態(tài)頻譜管理提供了靈活的手段及一定的信息支撐。文章通過(guò)誤差分析比較了各個(gè)算法的性能，實(shí)驗(yàn)表明，RMSM空間插值算法具有計(jì)算效率高、誤差較小、穩(wěn)定性好等優(yōu)點(diǎn)，可用于REM的生成。未來(lái)將考慮結(jié)合無(wú)線電傳播模型的自適應(yīng)N_q/N_W算法以及基于REM的指紋庫(kù)構(gòu)建研究。

參考文獻(xiàn)

[1] 黃標(biāo)，李景春，譚海峰，等.認(rèn)知無(wú)線電及頻譜管理[M].北京:人民郵電出版社,2014.

[2] ZHAO Y P，REED J.Network support：The radio environment map[M].Cognitive Radio Technology-Bruce Fette(Ed.1).Ch 11，Elsevier 2006：337-339.

[3] 趙友平，譚琨，姚遠(yuǎn).認(rèn)知軟件無(wú)線電系統(tǒng)原理與實(shí)驗(yàn)[M].北京：清華大學(xué)出版社，2016.

[4] Deliverable D2.4：Final System Architecture.EC FP7-248351 FARAMIR project[R].2011：8-10.

[5] Deliverable D4.1：Final System Architecture.EC FP7-248351 FARAMIR project[R].2011：8-12.

[6] Deliverable D4.3：Final System Architecture.EC FP7-248351 FARAMIR project[R].2012：7-15.

[7] Deliverable D6.2：Final System Architecture.EC FP7-248351 FARAMIR project[R].2011：10-22.

[8] 王嶺.WRAN中無(wú)線電環(huán)境地圖的生成技術(shù)研究[D].重慶：重慶大學(xué)，2011.

[9] 李曄.基于高鐵頻譜環(huán)境地圖的切換技術(shù)研究[D].成都：西南交通大學(xué)，2013.

[10] 李偉，馮巖，熊能，等.基于無(wú)線電環(huán)境地圖的頻譜共享網(wǎng)絡(luò)研究[J].電視技術(shù)，2016，40(10)：60-66.

[11] Luo Yuan，Gao Lin，Huang Jianwei.Economics of data-base-assisted spectrum sharing[M].Wireless Networks，2016.

[12] 高遠(yuǎn)，周文虎，匡正.無(wú)線電環(huán)境地圖技術(shù)實(shí)現(xiàn)與前景[J].上海信息化，2015(11)：66-67.

[13] 張夢(mèng)潔.結(jié)合GIS的室外WiFi信號(hào)覆蓋強(qiáng)度分析研究[D].汕頭：汕頭大學(xué)，2012.

[14] SHEPARD D.A two dimensional interpolation function for irregularly spaced data[C].In proc.of the 23rd National Conf.of the Association for Computing Machinery，Princeton，NJ，ACM，1968：517-524.

[15] RENKA R J.Multivariate interpolation of large sets of scattered data[J].ACM Transactions on Mathematical.Software，1988，14(2)：139-148.

[16] 陳嶺，許曉龍，楊清，等.基于三次樣條插值的無(wú)線信號(hào)強(qiáng)度衰減模型[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2011，45(9)：1521-1527.

[17] 劉志建，關(guān)維國(guó)，華海亮.基于克里金空間插值的位置指紋庫(kù)建立算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33(10)：3139-3142.

[18] BENTLEY J L，F(xiàn)RIEDMAN J H.Data structures for range searching[J].ACM Computing Surveys，1979，11(4)：397-409.

作者信息:

字  然，常  俊，宗  容，王若男，廖貴文

（云南大學(xué) 信息學(xué)院，云南 昆明650500）