0 引言

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

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

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

1 空間插值

1.1 通用模型及經典算法

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

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

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

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

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

1.2 改進型MSM算法

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

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

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

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

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

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

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

    理想的空間插值是將離散的數據點擴展為連續的數據曲面，而實際中為了將點數據盡可能擴充為面數據，常利用網格化的思想，即將插值區域按一定的分辨率（即網格大?。﹦澐譃榫W格區域，并對每一個網格點進行空間插值。無線電環境地圖（REM）的生成就是將若干個位置的RSS擴展為區域性的綜合信號強度，利用已知數據點進行網格化插值。

2 算法流程及復雜度分析

2.1 算法主要流程

    (1)輸入：

    ①RMSM算法相關參數：N、d_exp、N_q、N_W。

    ②網格區域相關參數：X_min、X_max、Y_min、Y_max，網格點數M=X_points×Y_points。(X_points、Y_points為兩個坐標軸上的網格點數)

    (2)初始化：

    ①數據點矩陣points：

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

    并輸入數據：

    ②權值矩陣ω′與節點方程值矩陣q：

        double[] w1=new double[Nq]

        double[] w2=new double[Nw]

        double[] q=new double[Nw]

    ③網格點（即所有待插值點）矩陣XY：

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

    (3)將points中的數據集構造為二維KD-Tree數據結構；

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

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

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

    ③輸出結果：

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

2.2 復雜度分析

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

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

3 實驗及分析

3.1 實驗場景

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

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

3.2 誤差分析

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

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

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

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

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

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

4 結論

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

參考文獻

[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] 趙友平，譚琨，姚遠.認知軟件無線電系統原理與實驗[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中無線電環境地圖的生成技術研究[D].重慶：重慶大學，2011.

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

[10] 李偉，馮巖，熊能，等.基于無線電環境地圖的頻譜共享網絡研究[J].電視技術，2016，40(10)：60-66.

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

[12] 高遠，周文虎，匡正.無線電環境地圖技術實現與前景[J].上海信息化，2015(11)：66-67.

[13] 張夢潔.結合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] 劉志建，關維國，華海亮.基于克里金空間插值的位置指紋庫建立算法[J].計算機應用研究，2016，33(10)：3139-3142.

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

作者信息:

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

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