0 引言

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

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

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

1 空間插值

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

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

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

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

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

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

1.2 改進型MSM算法

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

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

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

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

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

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

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

    理想的空間插值是將離散的數(shù)據(jù)點擴展為連續(xù)的數(shù)據(jù)曲面，而實際中為了將點數(shù)據(jù)盡可能擴充為面數(shù)據(jù)，常利用網(wǎng)格化的思想，即將插值區(qū)域按一定的分辨率（即網(wǎng)格大小）劃分為網(wǎng)格區(qū)域，并對每一個網(wǎng)格點進行空間插值。無線電環(huán)境地圖（REM）的生成就是將若干個位置的RSS擴展為區(qū)域性的綜合信號強度，利用已知數(shù)據(jù)點進行網(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)格點數(shù)M=X_points×Y_points。(X_points、Y_points為兩個坐標軸上的網(wǎng)格點數(shù))

    (2)初始化：

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

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

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

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

        double[] w1=new double[Nq]

        double[] w2=new double[Nw]

        double[] q=new double[Nw]

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

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

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

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

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

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

    ③輸出結(jié)果：

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

2.2 復(fù)雜度分析

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

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

3 實驗及分析

3.1 實驗場景

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

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

3.2 誤差分析

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

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

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

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

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

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

4 結(jié)論

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

參考文獻

[1] 黃標，李景春，譚海峰，等.認知無線電及頻譜管理[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] 趙友平，譚琨，姚遠.認知軟件無線電系統(tǒng)原理與實驗[M].北京：清華大學出版社，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中無線電環(huán)境地圖的生成技術(shù)研究[D].重慶：重慶大學，2011.

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

[10] 李偉，馮巖，熊能，等.基于無線電環(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] 高遠，周文虎，匡正.無線電環(huán)境地圖技術(shù)實現(xiàn)與前景[J].上海信息化，2015(11)：66-67.

[13] 張夢潔.結(jié)合GIS的室外WiFi信號覆蓋強度分析研究[D].汕頭：汕頭大學，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] 陳嶺，許曉龍，楊清，等.基于三次樣條插值的無線信號強度衰減模型[J].浙江大學學報(工學版)，2011，45(9)：1521-1527.

[17] 劉志建，關(guān)維國，華海亮.基于克里金空間插值的位置指紋庫建立算法[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.

作者信息:

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

（云南大學 信息學院，云南 昆明650500）