一種雙信標機制下的指紋庫構建方法

秦寧寧，吳憶松，孫順遠

(1.江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2南京航空航天大學 電磁頻譜空間認知動態系統工信部重點實驗室，江蘇 南京 211106)

近年來，隨著通信技術的進步，室內位置服務研究得以飛速發展。受GPS工作局限與固件配置約束的影響，以信號能量為尺度的指紋定位方法成為室內定位技術研究的重要方向。雖然該方法回避信號載體差異與內容細節，但是定位精度不可避免地易受離線指紋庫構建的速度與效率影響[1]。

室內定位的指紋庫構建方法多種多樣，例如全采法、眾包法和預測法等[2]。全采法的思想是在室內場景中規劃無線接入點(Access Point，AP)和指紋點位置后，采集并處理得到各個指紋點處來自各無線接入點的信號強度均值數據，與其物理坐標構建組成指紋庫。盡管利用全采法構建的指紋庫精度較高，但對給定大面積定位區域時，該方法會帶來大量采集成本消耗，因此實用性較差。為縮減采集成本，眾包法[3]結合群智感知理論，利用系統用戶的移動設備采集并上傳指紋數據，但用戶數據本身不精準的位置坐標極大地限制了眾包法的推廣應用。

相比于全采法與眾包法繁復的離線采樣與建庫方案，預測法將部分指紋點標記為信標，僅需采集信標處RSS，挖掘信標信號間的深層關系來預測非信標指紋點的RSS，極大地減小了建庫開銷[4]。常用的預測法目前有空間插值法[5]和矩陣填充法[6]。作為典型的空間插值法，反距離加權(Inverse Distance Weighted，IDW) 算法邏輯簡潔，位置權重僅與物理距離負相關，但對多干擾源的復雜場景的預測不精確；而克里金(Kriging)算法在預測前需要擬合場景相關的變異函數，由此帶來計算復雜、結果波動率高的缺陷[7]。為平衡計算復雜度，文獻[8]采用泛克里金插值法對位置指紋進行預處理，但減少的人工和時間成本有限，且構建精度受變異函數的影響較大。文獻[9]因勢利導地利用RSS特征設計IDW預測指紋庫，但受IDW算法粒度較粗的屬性影響，精度改善效果不明顯。矩陣填充方法是利用定位場景中指紋點位置在物理距離層面的強相關性，為高維指紋庫數據降秩，從而更快捷地預測空缺指紋數據。文獻[10]和文獻[11]在離線階段擴充指紋庫時都引入了矩陣填充法，對比其他構建方法后均發現，矩陣填充法普遍依賴大量信標信息，從而未能充分發揮預測法省時省力的優勢。

融合反距離加權的簡單易行，引入徑向基神經網絡深層聯系特征，筆者提出一種基于雙信標的徑向基位置指紋庫構建算法(Dual Beacon-Radial Basis Function，DB-RBF)，以拉丁超立方抽樣(Latin Hypercube Sampling，LHS)確立主次雙信標點的機制，來減少采樣信標數量；利用反距離加權和徑向基神經網絡(Radial Basis Function Neyral Network，RBFNN)來預測未知接收信號強度信息。DB-RBF相比全采法犧牲可接受范圍內的指紋庫精度與定位性能，從而節省了大量人力與時間成本的建庫開銷。

1 理論模型

1.1 拉丁超立方抽樣

拉丁超立方抽樣是一種從多元參數分布中近似分層隨機抽樣的技術，其關鍵是對輸入概率的分布進行分層。基于單一維度上抽樣概率相等的區間要求，拉丁超立方抽樣要求在給定D維空間中，將每個維度均等地劃分為v個不重合的區間，實現在各維度抽樣區間內隨機獲取一個樣本值，恰好構建成v個抽樣樣本。

1.2 接收信號強度的反距離加權插值

(1)

若給定場景內有信標點集合ΩB，包含L個信標點PB l(l=1，2，…，L)，則將反距離加權映射到該室內場景，在已知坐標為(xl，yl)的信標點PB l處，采集來自于無線接入點的接收信號強度，與其坐標組成指紋信號：

PB l={(xl，yl)，rl} ，

(2)

其中，rl表示PB l接收到來自無線接入點的接收信號強度。若場景內包含F個待估計點PEf(f=1，2，…，F)，則可得到坐標為(xf，yf)的PEf相應的指紋信息為

(3)

(4)

1.3 徑向基神經網絡插值

徑向基神經網絡是一種三層神經網絡，其包括輸入層、隱含層、輸出層。徑向基神經網絡的插值結果最少只需由一個中心點即可確定，因此將其應用于稀疏信標的指紋預測場景中，可充分發揮其小尺度指紋庫優勢。

在定位場景中，徑向基神經網絡預測任意一個PEf的接收信號強度僅依賴于PEf與各PB l之間的關系范式‖PEfPB l‖，基函數g可表示為

g=φ(‖PEfPB l‖) ，

(5)

其中，‖PEfPB l‖通常可以構造為歐式距離、余弦相似度和皮爾遜相關系數等。在已有ΩB的情況下，已知信標點PB l的指紋信息，可以利用徑向基神經網絡插值模型預測PEf的RSS為

(6)

為了求得給定場景下的ω，可通過將信標點集合ΩB作為測試樣本集，代入式(6)，則存在關系式：

r=φω，

(7)

其中，r=[r1，r2，…，rl，…，rL]T，為已有信標點的接收信號強度矩陣，φ為基函數矩陣：

(8)

由此，可解得權重系數矩陣：

ω=φ-1r。

(9)

2 雙信標機制

指紋庫構建過程中信標點與待估計點的比例選取很大程度決定了構建效率。若信標點比例過小，則會導致最終的指紋庫與真實指紋偏差較大，無法用于室內定位；若信標點比例過大，則又會導致指紋庫擴張不充分。為了靈活調整指定場景下的信標點比例，引入雙信標機制，尋求平衡指紋精度和擴張效率的最優信標點比例。

2.1 確定主次信標點位置

為構建參考指紋信息，首先要選取合適的抽樣方法確定場景中部分位置作為主信標點。鑒于所有信標地位平等的特征，非概率采樣方法因其樣本概率的差異性而不宜采納；而在等概率抽樣方法中，簡單隨機抽樣可能無法選出足夠多代表場景特性的主信標點，整群抽樣方法的結果集位置又過于集中。以拉丁超立方抽樣為代表的分層抽樣方法兼顧隨機性與均勻性，是定位場景選取初始信標點的最佳選擇。

在給定Ω=sasb，(sa≥sb)的矩形區域內，選取一定比例的主次信標點位置。完全隨機地選取信標點具有偶然性，不能很好地反映指紋庫構建算法的構建效果，均勻地選取則費時費力。基于室內定位場景的獨特性，對給定Ω區域，采用改進的拉丁超立方抽樣獲取主次信標點。

步驟1 初始化。劃分數量v，迭代次數Z，信標點集合ΩB=?，主信標點集合ΩM=?，次信標點集合ΩS=?；

步驟2 將sa邊均等分為v段區間Ai(i=1，2，…，v)，取Ai中點作為區間代表位置，編號i；

步驟3 將sb邊均等分為u=[vsb/sa]段區間Bj(i=1，2，…，u)，取Bj中點作為區間代表位置，編號j；

步驟4 將編號滿足i為奇數的位置(i，j)選為信標點PB l(l=1，2，…，L)，并聚類到ΩB；

步驟5 分別令i=1，3，5，…，不重復產生隨機數j∈[1，u]，標記位置(i，j)為主信標點PM。重復此步驟Z次，得到P=[Zv/2]個主信標點PMp(p=1，2，…，P)，并聚類到ΩM；

步驟6 將ΩB中未被選為PMp的位置(i，j)記為次信標點PSq(q=1，2，…，Q)，即PSq∈ΩB且PSq?ΩM，并聚類到ΩS；

在定位場景內采用拉丁超立方抽樣的方法確定一定比例的主次信標位置，對主信標采集信號強度作為其指紋信息，以反距離加權估計次信標信號強度。圖1為利用該算法確定主次信標位置及信號強度過程的示意圖。以v=14，Z=6時主次信標拉丁超立方抽樣示意圖為例，如圖2所示。圖中標注的位置(7，6)表示第3輪迭代時選中的主信標點之一，而位置(11，6)屬于ΩB且未被抽為PMp，因此標記為次信標點。由抽樣結果可以看到，拉丁超立方抽樣確保任意維度的任意區間之間樣本數量差不超過1，其分層抽樣特征屬性可以以公平概率的方式抽取信標，且能支持多次重復進行，在兼顧抽樣公平代表性的同時，能消除構建信標集合的偶然性。

圖1 雙信標指紋確定過程示意圖

圖2 v=14，Z=6的LHS抽樣示意圖

2.2 確定主次信標點RSS信息

(10)

通過上述插值過程，已經具備完整的雙信標指紋信息。由抽樣過程可知，信標點集合ΩB由ΩM和ΩS組合而成，即三者存在如下關系：

(11)

其中，信標點PB l的序號滿足1≤l≤L=P+Q。

3 指紋庫擴充

由于反距離加權插值算法只考慮到信標點的位置相關性，未能充分利用數據的空間相關性，因此對于預測距離較遠的未知點信息貢獻不大。眾所周知，神經網絡算法具有極強的非線性映射能力，理論上只要隱層神經元數目足夠多，神經網絡能以任意精度逼近一個非線性函數。而神經網絡方法的缺陷在于，只有在信標點信息達到一定數量的情況下，才可以充分利用數據間的相關性和全局性，保證較高的預測精度。因此，為了保證指紋庫的構建精度，同時減小建庫的人工和時間成本，DB-RBF選擇借助反距離加權預測少量次信標點的指紋信息，而在大幅擴張指紋庫階段采用更為精準的神經網絡方法來插值。在最常用的神經網絡算法中，反向傳播神經網絡(Back Propagation Neyral Network)存在神經元數目太多導致網絡過適性的缺陷[12]，因而具有更強的輸入輸出映射功能，且學習過程收斂速度快的徑向基神經網絡更適合預測指紋點的接收信號強度[13]。

RBF能夠在選取一定范圍的參考點作為已知量下，依次對標記點上來自同一個無線接入點的接收信號強度擬合信號曲面。在遍歷完所有無線接入點后，即可完成對指紋點上接收信號強度向量的估計。

由于指紋定位場景中PB l與待估計點PEf的信號量以物理距離呈現強相關性，因而文中將基函數g的自變量‖PEfPB l‖構造為兩點之間的坐標歐式距離，即

φ(‖PEfPB l‖)=φ(dfl)=φ(((xf-xl)2+(yf-yl)2)1/2) 。

(12)

基于式(6)，式(12)在求解權重系數ωl(l=1，2，…，L)中得到

(13)

考慮室內環境復雜，無線接入點信號波動等因素，已測ΩB很難完全覆蓋待估計點的信號特征。因此在實際的插值逼近問題中，需要對基函數進行調節。引入調節參數β，更新基函數φ(dfl)=(dfl2+β)1/2，代入式(13)，得

(14)

由式(9)可解得權重系數矩陣ω，代入式(6)，即可求解PEf來自相應無線接入點的接收信號強度。

4 實驗與結果分析

4.1 實驗場景

實驗環境為如圖3所示的江南大學物聯網工程學院某辦公室，定位區域總面積為9 m×7 m。從圖3可以看到，室內布置了較多辦公桌椅，符合一般室內環境的靜態干擾條件。定位區域內規劃指紋點間距d0=1 m，指紋點總數N=80。室內包含I=12個iBeacon藍牙節點[11]，型號為尋息m0u，發射功率選用-20 dBm。將藍牙節點作為無線接入點放置在圖3中的位置，標記為AP1，AP2，…，AP12。為了分析論文算法建立的位置指紋庫與實際指紋庫的誤差，文中先采用全采法構建位置指紋庫，選用安卓手機作為采集端對定位區域內所有參考點進行接收信號強度值的采集。同時考慮到接收信號強度數據的時變性，為保證獲取到的接收信號強度數據的準確性，對每個參考點采樣100次，平均采集時間t約為3 min。由于室內環境的干擾，采集到的信號會有較多偏離值。對于信號濾波技術的選取，考慮到與對比算法保持公平性，采用普遍適用的高斯濾波[14]，將濾波處理后的數據樣本求幾何平均值作為每個參考點的接收信號強度信號。

圖3 實驗場景示意圖

4.2 抽樣穩定性對比

為了驗證文中算法采用的拉丁超立方抽樣方法的穩定性，實驗對比了完全隨機抽樣與拉丁超立方的抽樣結果對定位精度的影響。為保證對比的公平性，兩種抽樣方法得到的信標點均用反距離加權進行插值和加權最近鄰節點算法(Weighted K-Nearest Neighbour，WKNN)定位測試。以平均定位誤差e來衡量定位精度：

(15)

在節4.1的定位場景下，分別采用完全隨機抽樣與拉丁超立方抽樣在Z=5的情況下重復試驗80次。圖4為實驗結果的概率分布對比圖。

圖4 兩種抽樣方式的定位穩定性對比

表1為定位效果的對比。可以看出，兩種抽樣方法獲得的最低定位誤差分別為1.60 m和1.65 m，差異比僅為3.1%。但是隨機抽樣容易出現極大誤差值，最高為3.21 m，同時隨機抽樣結果的方差26.7遠大于拉丁超立方抽樣的8.5，其數值波動幅度和范圍較大。相反地，拉丁超立方抽樣能夠在信標點比例可控的前提下，給后續插值與定位工作提供穩定高效的主信標選擇方案。

表1 兩種抽樣方式的平均定位誤差對比

4.3 徑向基神經網絡插值

4.3.1 插值效果分析

徑向基神經網絡插值的優勢在于能夠充分利用已有少量信標點互相之間的聯系，批量快速地估測到平面內任意位置的接收信號強度信息。論文利用這一特點將指紋點的間隔縮短為0.2 m，得到覆蓋整個定位場景的指紋信息。不失一般性，圖5以來自AP12的指紋信號預測結果為例，展現徑向基神經網絡插值結果，其中主次信標點位置以圓形離散點表示，預測所得的指紋數據以三維熱度圖的形式展現。圖中信號曲面整體具備高斯分布的特征，預測結果受經典信號傳播模型約束；曲面中也包含若干個局部范圍的信號波動，可見文中插值方法真實反映了場景內干擾源的位置及強度，能提供符合個體特征的指紋數據。

圖5 RBF預測信號熱圖

4.3.2 調節參數β取值分析

參數s主要影響基函數φ(df l)的取值，從而影響徑向基神經網絡插值精度。為了得到具備場景特性的參數β，實驗對比了不同β取值下，徑向基神經網絡插值結果對e的影響。如圖6所示，β從0開始，以0.05為步長間隔向上尋找本場景下最優定位精度時的匹配取值。當β≤0.25時，φ(df l)受到β的調節作用并且e隨著β增大而減小；但β>0.25后，實驗得到誤差隨β增大而陡增，對于基函數的調節起負作用。不失一般性地，β的取值范圍為[0，0.4]。

圖6 β與定位誤差

4.3.3 誤差對比

為了分析經DB-RBF插值得到的接收信號強度信號的準確性，實驗對比了IDW、SA-ABC-Kriging[15]以及DB-RBF的插值結果與真實測量值之間的誤差，如圖7和圖8所示。對比可知，反距離加權的插值結果整體比真實測量值偏小，平均誤差達到4.2 dBm，這與其信標點權重體系固定的插值策略直接相關，固定的加權冪指數ρ使得部分位置過度參考遠距離信標點。而SA-ABC-Kriging所得預測值誤差波動較大，存在若干偏差達到7 dBm的點，對指紋庫構建精度影響嚴重。通過DB-RBF插值所得的指紋數據與真實測量值較接近且誤差變化幅度小，計算得到平均誤差為2.21 dBm，較小的誤差換來極大的人工成本節省，徑向基神經網絡插值能夠在保證插值準確性的同時快速構建指紋庫。

圖7 預測值與測量值對比

圖8 算法間預測誤差箱型圖

4.4 定位精度對比

為驗證DB-RBF信號預測對定位效果的影響，本實驗對比了無插值、IDW、SA-ABC-Kriging、DB-RBF、全采法5種指紋庫構建方法擴展得到的指紋庫，分別用于在線定位階段時的定位精度。

4.4.1 平均定位誤差

為分析各預處理方法對定位誤差的影響，實驗對比了5種擴充指紋庫在WKNN定位算法下的平均定位誤差。從圖9顯示的WKNN算法近鄰點數量K與各算法定位誤差的關系，可以看到，總體上隨著K的增加，5種算法的e都呈下降趨勢。其中由于指紋點分布稀疏，無插值方法在K=1時誤差極高且下降速率較慢，整體誤差高于其他算法0.5 m以上；而DB-RBF和全采法受益于較為精準的指紋信息，下降速率最快。

圖9 算法的平均定位誤差對比

從最優近鄰點數量下的平均誤差來看，DB-RBF相較于無插值、IDW、SA-ABC-Kriging三者，具有最低的誤差值。其中無插值方法定位誤差最高，比DB-RBF高出0.61 m；同時DB-RBF的平均誤差也比IDW和SA-ABC-Kriging分別降低0.25 m和0.22 m，占比分別約為20.21%和15.38%，可見文中算法具有良好的定位效果。另外，全采法具有最低的平均誤差e=1.58 m，低于文中的DB-RBF方法的約10.8%。在犧牲較小定位精度的前提下，DB-RBF做到了擴充1倍以上指紋庫容量，且采集比例可根據場景特性調整，具有高度的靈活性。

4.4.2 誤差累積概率

給定應用下的emax∈[0，4.2 m]容忍范圍內，通過實驗可確定各擴充指紋庫的測試點定位結果滿足e≤emax的概率pe，記為誤差累積概率。本實驗給出了在不同的emax限制下，上述5種算法的pe對比情況。從圖10可以看出，5種算法的pe均隨誤差容忍范圍的擴大而升高，最終達到100%。當給定emax≤0.9 m時，由于允許誤差小于一個單位的指紋點間隔距離，因而5種算法的pe相差不大且都較低，此時的誤差水平受到指紋點設定影響。而誤差容忍范圍繼續擴大后，DB-RBF的pe曲線表現出僅次于全采法的上升速率。當emax≤3 m時，DB-RBF的pe已經達到約90.4%，可見該場景下DB-RBF的定位誤差基本能夠控制在3倍指紋點間隔距離以內，具備良好的定位穩定性。

圖10 算法的誤差累積概率對比

5 結束語

針對室內定位中傳統指紋庫構建工作繁復，一般擴充方法精度有限且所需信標點較多的問題，筆者提出了基于雙信標機制，采用徑向基神經網絡進行插值的指紋庫擴充方法。DB-RBF算法能夠依賴少量信標點，插值得到精度較高的指紋信息，同時大幅減少了采集工作量。然而，本著客觀的態度，必須看到，對于極少數存在的不規則角落的應用場景，和其他大多數方法一樣，DB-RBF也可能存在參考信標不足而預測準度欠佳的遺憾。另外，實驗的室內環境未引入動態干擾條件。因此，面向場景死角中的指紋構建和匹配計算問題和動態干擾源條件下的預測穩定性將會是定位研究的重點方向。