基于虛擬參考標簽的RSSI質心定位算法*

雷 謙，杜慶治，龍 華，邵玉斌

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

WSN傳感器節點定位技術是無線傳感器網絡(Wireless Sensor Networks)[1]的核心技術之一。目前無線傳感器網絡定位算法可以分為兩類：基于距離的 （Rangebased）和與距離無關的(Range-free)[2]。參考文獻[3]介紹了一種新的節點定位技術——質心算法。該算法屬于距離無關的定位算法，計算的復雜度較參考文獻[4]中的最小二乘法有了很大的降低，且網絡生存率較強，但未知節點的定位精度不高。

為了解決質心算法定位精度不高的問題，本文提出的一種改進的質心算法。該算法與VIRE[5]算法類似，利用信號傳播模型[6]在定位區域內構造虛擬參考標簽的RSSI[7]信息，通過最小二乘法結合質心算法的方式，進一步縮小了未知節點的估計區域。實驗證明，雖然該算法的計算復雜度有所增加，但定位的精確度有了進一步的提高，約為 33%。

1相關工作介紹

1.1 VIRE算法

VIRE系統閱讀器Rp1和參考標簽Lm1(p1,m1∈N+)分布如圖1所示，待定位標簽Zq1在區域內(q1∈N+)。VIRE方法的核心思想是將每4個參考標簽看作一個單元網格，再將其進一步等分為 N1×N1(N1∈N+)個小網格，在小網格處加入虛擬參考標簽。如圖2所示。

圖1 VIRE系統閱讀器和標簽的分布

圖2 網格虛擬參考標簽分布

參考標簽的位置和場強值已知，虛擬參考標簽在水平和垂直方向上的場強值可由下式(1)和式(2)求出。

其中，Ep1(Gi1,j1)(i1,j1∈R)表示第 p1個閱讀器讀取的(i1,j1)坐標位置上的場強值；a=i1/N1」，b=j1/N1」，」 表示向下取整；t(0≤t=i1%N1≤N1-1)為待測虛擬參考標簽與已知起始標簽在 X軸的間隔；u(0≤u=j1%N1≤N1-1)為待測虛擬參考標簽與已知起始標簽在Y軸的間隔。

可見，所有參考標簽和虛擬參考標簽的位置坐標和場強值都為已知量。然后，采用LANDMARC[8]算法選取一定閾值并求解最鄰近參考標簽權值，將參考標簽權值加權得到最終待定位標簽的定位結果。

1.2 無線信號傳輸模型

式中，n1為信號衰減因子，n1∈[2,4]；d為待定位節點與參考節點之間的距離，單位為m；k1為1 m時所測得的RSSI值，單位為 dBm。

2 基于虛擬參考標簽的系統構造及算法實現

2.1 VIRE系統的構建及虛擬參考標簽的選取

本文提出的基于虛擬參考標簽的定位方法與VIRE系統類似。

對于二維平面的定位系統，定位區域的大小記為S×T，參考標簽為區域的四個頂點 A1(0,0),B1(0,T),C1(S,T),D1(S,0)，4個閱讀器R1,R2,R3,R4置于參考標簽 A1,B1,C1,D1上。如圖3所示，記區域中任意一個虛擬參考標簽的 坐 標 為(xi2,yi2)(i2∈N+)。

圖3 虛擬參考標簽區域的定義

由幾何關系可知：該虛擬參考標簽到參考標簽A的距離 D(A)為，到參考標簽 B的距離 D(B)為， 到參考標簽C的距離D (C)為，到參考標簽D的距離D (D)為通過 式(3), 將 距離 D(A)、D(B)、D(C)和D(D)轉化為RSSI，并由4個閱讀器來讀取。因此區域中每個虛擬參考標簽都對應4個RSSI，記為RSSIRj2_m2(Rj2表示第 j2個閱讀器讀取的 RSSI，j2=1,2,3,4;m2表示第幾個虛擬參考標簽，m2∈N+)。若每個虛擬參考標簽之間沿著X和Y坐標軸方向上的間隔均為N2(N2∈R)，那么沿X軸方向需要部署(S/N2+1)個虛擬參考標簽，沿Y軸方向需要部署(T/N2+1)個虛擬參考標簽，虛擬參考標簽的個數為(S/N2+1)×(T/N2+1)。

通過測量，被4個閱讀器讀取的待測點RSSI值記為(RSSIR1、RSSIR2、RSSIR3、RSSIR4)。 將其 與 4 個 閱讀器 中對應的虛擬參考標簽的RSSI值相比較|RSSIRj2-RSSIRj2_m2|,然后，針對每個閱讀器Rj2選絕對值最小的虛擬參考標簽(可能不止一個)，如圖 4所示。

圖4 選取虛擬參考標簽的過程

所選取的虛擬參考標簽為An2(XAn2,YAn2)，n2∈N+。以及其被 4個閱讀器讀取的 RSSI值,記為RSSIRj2_An2。

2.2 VIRE系統算法的實現

2.2.1 傳統的質心算法

由傳統的質心算法[6]可知，所選的虛擬參考標簽形成的封閉區域，構成了待測節點的估計區域。用式(4)計算待測點的估計坐標：

2.2.2 改進的質心算法

質心算法定位精確的提高，關鍵在于縮小待測區域。改進算法的流程圖如圖5所示。

具體過程，分為以下三個步驟：

(1)將已選取的虛擬參考標簽進行組合，假設n3為已選取的虛擬參考標簽的個數，n3∈N+，組合方式為

圖5 改進的質心算法流程圖

(2)然后利用最小二乘法來計算估計點的位置，這樣可以得出多個估計點Bn4(XBn4,YBn4)，n4∈N+,如圖6所示。

圖6 改進的質心算法示意圖

(3)取估計點 Bn4(XBn4,YBn4)，n4∈N+的質心 ，作為待測點的估計坐標(Xtest,Ytest)，用式(5)：

3仿真及誤差分析

本文采用Matlab7.6.0軟件進行仿真實驗。在無線傳感網絡中以定位精確度、計算復雜度、網絡覆蓋率、功耗等因素作為常用評價指標。在本文中取計算復雜度和定位精確度兩項指標為評價標準。在仿真實驗中，無線傳感器網絡區域設置為S=T=90，即在90 m×90 m的正方形區域。讀卡器在仿真區域的4個頂點，虛擬參考標簽的個數為7×7。待測節點的定位誤差率定義如下：

式中s1為仿真的次數。

3.1 計算復雜度與定位精度的關系

當所選取的虛擬參考標簽An2(XAn2,YAn2)，n2∈N+的個數增加時,傳統質心算法定位精度的比較如圖7所示。

圖7 質心定位精確度的比較

實驗組數為100次的統計平均值，由式(6)可知：

由圖可知，當n2增加時，定位的精確度得到了提高，約為16%。但當n2=4時計算的次數較n2=2時增加了一倍，從而提高了計算的復雜度。

3.2 改進算法與原算法定位精確度的比較

改進的質心算法與傳統質心算法的比較,如圖8所示。

圖8 兩種算法的誤差對比

對改進算法進行300次仿真，由式(6)可知：AverageError1=5.295 9 7.907 8°。通過仿真結果可知，改進的質心算法較傳統的質心算法，定位精確度提高了約33%。但改進的質心算法由于加入了最小二乘法，使得計算的次數較傳統的質心算法有了明顯的增加，也就增加了計算的復雜度。

3.3 仿真分析

(1)在選取虛擬參考標簽時，可能無法選擇待測點附近的虛擬參考標簽，或者是所選擇的虛擬參考標簽有重復，從而造成誤差過大。這可能與無線信號傳播模型有關，因為信號不是在自由空間中傳輸，受到了外界環境的干擾。可以通過多次測量，再取統計平均，達到減小誤差的目的。本文通過取統計平均減小了誤差，但還需進一步改進。

(2)本文通過增加計算的次數來換取定位精確度的提高。在未來，需要進一步試驗新算法，在不增加計算復雜度的基礎上，進一步提高定位的精確度。

無線傳感器網絡中節點定位一直是該領域的熱點問題之一。本文結合VIRE系統，提出了一種改進的質心算法。該算法計算的復雜度有所增加，待測節點的定位精度較傳統質心算法有一定的提高，在一定程度上解決了傳統質心算法定位精度較低的問題。

[1]鄭永奇.無線傳感器網絡關鍵技術研究[J].微型機與應用,2013，32(5):57-59.

[2]ERRARNILLI V,BESTAVROS A.On the interaction between data aggregation and topology control in wireless sensor networks[C].Proc of the 1st Annual IEEE Communications Society Conference,2004:557-565.

[3]BULUSU N,HEIDEMANN J.ESTRIN D.GPS.1ess Low Cost Outdoor Localization for Very Small Devices m[J].IEEE Personal Communications,2000,7(5):28-34.

[4]MOORE D,LEONARD J,RUS D,et al.Robust distributed network localization with noisy range measurements[C].In:Proc of the 2th Intemational Conference on Embedded Networked Sensor Systems.Baltimore,USA,2004:50-61.

[5]Zhao Yiyang,Liu Yunhao.VIRE:Active RFID-based localization using virtual reference elimination[C].XiAn:2007 International Conference on Parallel Processing,2007:56-63.

[6]CULLAR D,STRVASTAVA M.Overview of sensor network[J].Computer,2004,37(8):41-49.

[7]丁凡,周永明.基于RSSI的WSN吞吐量自適應優化策略[J].電子技術應用,2013,39(4):91-95.

[8]LIONEL M N,Liu Yunhao,LAU Y C et al.LANDMARC:indoor location sensing using active RFID[J].WirelessNetworks,2004,10(6):70l-7l0.