基于移動錨節點的加權質心定位算法研究*

劉 洋，高美鳳

(江南大學 物聯網工程學院 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122)

0 引 言

在現有比較典型的基于非測距的定位算法[1]中，加權質心定位(weighted centroid localization，WCL)算法[2,3]易于實現，且計算較為簡單，但缺陷是：為了達到較高的定位精度，往往需要在網絡內布設大量的錨節點，造成硬件成本增加，限制了算法的應用。文獻[4]提出了在加權因子中引入修正系數來提高定位精度。文獻[5]根據節點間的不同距離，采用不同的權重系數，進一步提高了定位精度。文獻[6]提出了對加權質心定位算法的接收信號強度指示(received signal strength indication，RSSI)距離值進行差分修正，從消除RSSI誤差角度來減小累積誤差。以上算法需要網絡內部署較多數量的錨節點，導致了硬件成本增大。文獻[7]利用少量真實錨節點的定位信息構造出虛擬靜態錨節點參與定位，再結合加權質心定位算法對未知節點進行估計。文獻[8]利用單個錨節點沿DOUBLE-SCAN路線飛行移動并與鄰居節點進行通信，未知節點根據一定的篩選機制并結合簡化的加權質心定位算法估計未知節點坐標。算法雖減少了硬件成本投入，但邊界未知節點的共線問題未得到很好解決，導致節點的定位精度偏低。

針對以上問題，本文采用單個移動錨節點以既定路線遍歷整個無線傳感器網絡的監測區域，在降低投入成本的情況下，對加權質心定位算法提出了相應的改進方案，設計了WCL-TRH(WCL-triangle RSSI hop)定位算法，并通過Matlab仿真實驗對比分析了WCL-TRH,WCL,RR-WCL(WCL algorithm based on RSSI ratio)3種算法。

1 移動路徑

采用單個移動錨節點，根據折線方式[9]移動路線的思想，設計了移動路徑，如圖1所示(“·”表示移動錨節點停留位置，即虛擬錨節點；“→”表示其移動方向和路徑)。這種移動方式可以達到網絡區域的盡可能覆蓋，保證了網絡中的未知節點可以接收到足夠的移動錨節點位置信息。同時這種三角式移動廣播方式，能夠盡量保證網絡內的未知節點處于至少3個移動位置所構成的多邊形范圍內部，有效地避免了邊界節點共線問題，實現了更好的定位效果。

圖1 移動錨節點路徑規劃

移動錨節點在移動過程中以時間間隔T或拐角處向未知節點廣播當前位置，動態地與周圍鄰居未知節點建立連接關系，繼續移動，直到遍歷整個網絡。

2 基于移動錨節點的加權質心定位算法

2.1 加權質心定位算法

加權質心定位算法的計算公式為

(1)

式中 (xi,yi)為第i個錨節點的坐標；(x,y)為未知節點M的坐標；N為未知節點的鄰居錨節點個數；wi為第i個錨節點所對應的權值系數

(2)

式中di為未知節點M與第i個錨節點之間的距離，可通過式(3)無線信號傳播衰減模型[10]求得

(3)

式中RSSI(d)為距離發射點d處的接收信號強度值；RSSI(d0)為距離d0處的接收信號強度值；λ為路徑衰減因子，易受環境影響，一般取值范圍在2～4之間；d為未知節點到錨節點間的距離，一般情況下取d0=1 m；ζo為正態隨機變量，標準差為σ。

2.2 改進加權質心定位算法權重系數

為抑制環境對于RSSI值的差異影響[11]，文獻[12]提出了RR-WCL算法，采用信號強度比值作為加權值，但僅采用信號強度比值作為權值，并未充分體現出不同位置處虛擬錨節點對質心位置的影響，定位效果不佳。

本文所提出的WCL-TRH算法在采用信號強度比值作為加權值的同時，根據網絡中每個未知節點與鄰居虛擬錨節點之間的最小跳數信息，對自身位置進行修正。若只采用最小跳數的倒數作為修正因子，雖然平均相對定位誤差會降低1 %左右，但也會帶來中心化效應，即定位結果不同程度地偏向于鄰居虛擬錨節點位置的平均值。由于在小型網絡區域，節點的最小跳數信息差別很小，所以，只采用跳數的倒數作為修正因子，降低定位誤差效果不是很明顯。為了擴大最小跳數對節點間實際位置的影響程度，結合指數函數y=ex，進行修正，擴大最小跳數的差異影響。

定義Rij為未知節點M分別從虛擬錨節點Bj,Bi接收到信號強度比值

(4)

根據個體差異修正后的權值系數為

(5)

式中hi為未知節點M到虛擬錨節點i的最小跳數。

由WCL-TRH算法所求得的未知節點坐標為

(6)

式中

(7)

2.3 改進的加權質心定位算法步驟

WCL-TRH算法步驟如下：

1)所有傳感器節點隨機分布在監測區域后，采用一個移動錨節點按照規定的路線移動。在移動的過程中，移動錨節點在每個三角形路徑的拐點處停留時間T，感知周圍鄰近的未知節點并廣播數據包Message_Loca。數據包需包含有自身移動位置坐標(xi,yi)、標號IDi、間隔跳數值Hops(始化為零)以及信息源標記(source=-1表示由移動錨節點發送的信息，source=0表示由未知節點發送的信息)

Message_Loca(IDi,(xi，yi),Hops,source)

2)未知節點根據接收的移動錨節點Message_Loca信息，首先測量獲取該信息的接收功率ri，然后記錄與移動位置i的間隔跳數值Hopsi=Hops+1。如果接收的信息源標記source=-1，一定是未知節點第一次接收到的信息，無需比較，只需將跳數加一并將信息源標記改為source=0，然后進行廣播；如果未知節點接收到的廣播信息是從其他未知節點轉發，那么首先判斷是否第一次接收到位置標記i的信息包，若是，則記錄標號i，并將跳數進行加一處理；否則，比較曾記錄的跳數值，保留較小跳數值對應的標號信息，處理后繼續廣播。

3)若移動錨節點在停留當前位置j時，接收到來自未知節點發送的數據包時，如果是第一次接收到標號為i的信息時，記錄并處理標號為i的跳數值，同時記錄位置i，j的連通關系；如果不是第一次接收到該標號信息，則與原記錄值進行比較，保留較小跳數的信息。

4)移動錨節點沿既定路線移動結束后，監測區域內的未知節點根據記錄的信號強度值、最小跳數及相關虛擬錨節點的位置坐標，進行定位。若接收的虛擬錨節點數至少3個，則直接利用式(6)計算未知節點的估計坐標；若接收到的虛擬錨節點數為1或2個，則利用式(8)估算未知節點坐標

(8)

式中RSSIi為未知節點接收到的移動錨節點位于位置i處所接收到的信號強度；(xi,yi)為移動錨節點處于該位置下的坐標。

3 WCL-TRH仿真與分析

利用MATLAB對算法進行仿真實驗以驗證改進算法WCL-TRH的性能。假設在100 m×100 m的正方形區域內，隨機布設200個未知節點，節點通信半徑為10 m的圓形區域。

3.1 定位精度分析

平均相對定位誤差為

(9)

式中m,n分別為虛擬錨節點和節點數量，rest為未知節點的估計位置，rreal為未知節點的實際位置，R為節點的通信半徑。當未知節點從50增加到300個，比較WCL，RR-WCL和WCL-TRH 3種算法的相對平均定位誤差，如圖2所示。

圖2 相對平均定位誤差

可以發現：WCL的相對平均定位誤差在19.86 %～26.06 %波動；而RR-WCL和WCL-TRH的平均相對定位誤差分別在12.25 %～13.11 %,4.77 %～6.11 %波動，且隨未知節點數的增加，相對平均定位誤差總體變化趨勢較為平緩，即未知節點數量對RR-WCL和WCL-TRH算法基本無影響；WCL-TRH的定位精度較WCL算法提高了15.09 %～19.95 %，較RR-WCL算法提高了7.00 %～7.48 %。

3.2 穩定性分析

圖3 節點相對平均定位誤差標準差

可以看出：WCL，RR-WCL和WCL-TRH算法的標準差整體隨未知節點數的增大先減小后趨于穩定；WCL-TRH算法的定位誤差標準差明顯低于WCL算法和RR-WCL算法的定位誤差標準差，說明WCL-TRH的穩定性要優于WCL算法和RR-WCL算法。

3.3 廣播間距影響分析

在相同的仿真環境下，改變移動錨節點的廣播間距，從圖4中可以發現，節點的相對平均定位誤差隨廣播間距增大而增大。這是由于在網絡區域內，移動錨節點的廣播間距代表了虛擬錨節點的數量，廣播間距越小，虛擬錨節點的數量越多，定位精度越高；反之則定位精度越低。另外，通過改變移動錨節點的通信半徑大小，可以發現當移動錨節點的廣播間距與其通信半徑相同時，網絡內未知節點的相對平均定位誤差最小。因此，在考慮實際應用成本以及定位精度的情況下，選擇移動錨節點廣播間距與其通信半徑相當時定位效果最好。

圖4 移動錨節點廣播間距對相對平均定位誤差影響

3.4 通信半徑影響分析

相同的仿真環境下，改變節點的通信半徑后，節點的相對平均定位誤差如圖5所示。

圖5 通信半徑對相對平均定位誤差影響

可以看出：當移動錨節點廣播位置不變時，隨著節點的通信半徑增加，節點的相對平均定位誤差逐漸減小。這是由于在一定范圍內，節點通信半徑的增大會提高網絡的連通度，使得未知節點可以接收的移動錨節點數據包數量增多，其位置也可以越來越趨近于鄰居移動錨節點位置所構成的多邊形中心，從而使得未知節點的相對平均定位誤差有所提高。

4 結束語

在不增加硬件資源的前提下，提出了WCL-TRH算法。采用了單個移動錨節點以既定的合理路徑遍歷整個定位區域，采用了一種改進的加權系數計算方法對未知節點進行定位。在充分考慮了鄰居虛擬錨節點位置對未知節點的影響情況下，利用未知節點的接收信號強度比值以及鄰居虛擬錨節點間的最小跳數等信息對未知節點的位置進行估計。仿真實驗表明：WCL-TRH算法可以得到較小的定位誤差和較高的穩定性，且節約了硬件成本。接下來的工作是移動錨節點根據網絡內節點的不同分布情況采用動態路徑的移動方式對未知節點進行定位。

[1] 彭 宇,王 丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報,2011,25(5):389-399.

[2] Blumenthal J,Grossmann R,Golatowski F,et al. Weighted centroid localization in ZigBee-based sensor networks[C]∥IEEE International Symposium on Intelligent Signal Processing,Spain:IEEE Instrumentation and Measurement Society,2007:1-6.

[3] 王 宇.基于灰度質心法的雷達干擾源定位方法研究[J].自動化技術與應用，2016，35(2)：63-66.

[4] 張先超,劉興長，張春園.基于次錨節點的無線傳感器網絡改進加權質心定位算法[J].傳感器與微系統,2015,34(2):143-146.

[5] Zhao Jijun,Zhao Qingwei,Li Zhihua,et al.An improved weighted centroid localization algorithm based on difference of estimated distances for wireless sensor networks[J].Telecommunication System,2013,5(1):25-31.

[6] 花 超,吉小軍，蔡 萍，等.基于RSSI差分修正的加權質心定位算法[J].傳感器與微系統,2012,31(5):139-141.

[7] 于海存,石為人,冉啟可，等.基于虛擬靜態錨節點的加權質心定位算法[J].傳感技術學報,2013,26(9):1276-1283.

[8] 鮑金鳳,游曉鵬.WSNs中移動信標輔助的加權質心定位算法[J].計算機技術與發展,2013,23(10):27-30.

[9] 李瑞雪,房至一,儀婷婷.基于可規律性移動錨節點和接收信號強度指示器的改進DV-Hop定位算法及其性能分析[J].吉林大學學報:工學版,2011,41(2):435-441.

[10] Alippi C,Vanini G.Wirsless sensor networks and radio localization:A metrological analysis of the MICA2 received signal strength indicator[C]∥Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks,USA:IEEE Computer Society,2004:572-582.

[11] Rabaey J M,Ammer M J,Silva J L D,et al.Picorodio supports Ad Hoc ultra-low power wireless networking[J].Computer,2000,33(7):42-48.

[12] 楊新宇,孔慶茹,戴湘軍.一種改進的加權質心定位算法[J].西安交通大學學報,2010,44(8):1-4.

[13] Rezazadeh J,Moradi M,Ismail A S,et al.Impact of static trajectories on localization in wireless sensor networks[J].Wireless Networks,2015(3):809-827.