圓外切Bounding-box WSN定位方法

羅清華，焉曉貞，彭宇，王丹，彭喜元

(1.哈爾濱工業大學(威海)信息與電氣工程學院，山東 威海264209;2.哈爾濱工業大學自動化測試與控制研究所，黑龍江哈爾濱，150080;3.通用電氣公司(上海)，上海200241;4.桂林電子科技大學廣西自動檢測技術與儀器重點實驗室，廣西 桂林541004;5.地理信息工程國家重點實驗室，陜西西安710054)

在Bounding-box方法中［1］，定位準確度不能隨距離估計精度的提高，而持續提高［2］。針對這個問題，眾多學者提出了Bounding-box的改進方法:郭海琦等人提出了三點質心定位Bounding-box和三點加權質心Bounding-box定位算法［3］，然而改善程度有限。受加權質心算法的啟發，文獻［4］提出了加權Bounding-box改進算法。姚英彪等人提出了采用邊框定界方法來確定節點存在的區域，然后將區域網格化，并用全搜索的方法找到最佳估計點［5］，但存在計算量大的問題。Sanabria-Russo等人提出了一種靈活的定位方法，可根據應用需求來選擇不同的定位方法［6］;文獻［7］提出了加權的Bounding-box定位方法，但沒有在實際應用環境中進行驗證;文獻［8］提出利用加權的最小二乘來解決室內非視距定位問題，但其計算復雜度較高。文獻［9］提出基于差分修正的加權質心定位算法，從一定程度上克服距離估計誤差對定位的影響。上述方法在一定程度上改善了Bounding-box算法的定位精度，然而仍存在著改善程度有限、計算量大的問題。而本文則從正方形區域和實際通信區域模型的差異區域入手，分析導致Bounding-box定位誤差較大的原因，并合理運用2個模型間的誤差區域，提出了圓外切的Bounding-box定位改進算法。

1 圓外切Bounding-box定位方法

在傳統的Bounding-box定位算法中，為了計算簡便，通信區域選擇以2d為邊長的正方形，其中d為未知節點與錨節點之間的距離測量值。然而，這樣將導致正方形區域與實際通信圓區域之間存在誤差區域。鑒于此，本文提出一種改進的Bounding-box定位方法，即圓外切Bounding-box定位算法，能夠減小這類誤差區域的大小，使定位估計更加準確。

在Bounding-box算法的基礎上，基于圓外切的bounding-box改進算法不再采用正方形作為通信區域，而是采用圓形作為通信區域。在正方形的定位區域中，四個角分別放置一個錨節點，平移正方形的對角線使其切于各個錨節點通信區域的圓，根據對角線的不同，該直線可以表示為y=x+bi或y=－x+bi。尋找4條切線所組成的矩形區域，并將這個區域的質心作為未知節點的估計坐標，其原理如圖1所示。

圖1 改進的Bounding-box算法原理示意圖Fig.1 The principle of improved Bounding-box

本文提出的改進方法在運算中將傳統方法中尋找正方形交集區域變換為尋找切線組成的區域，從而縮小定位的估計范圍，使定位精度得到提升。

基于以上思路和分析，基于圓外切的Bounding-box改進算法的具體實現步驟如下:

1)未知節點周期地廣播定位請求數據包。

2)錨節點在收到定位請求信息后，采集定位請求數據包的RSSI值，并向未知節點發送自身信息:節點ID、自身位置信息及RSSI值。

3)采用一定的距離估計方法，通過獲得的各個RSSI值估計出未知節點到各個錨節點的距離測量值。

4)未知節點收到后建立錨節點集合Beacon_set={a1，a2，…，am}，本實驗中m值為4。未知節點到錨節點的距離集合 Distance_set={d1，d2，…，dm}，錨節點位置集合 Position_set={(X1，Y1)，(X2，Y2)，…，(Xm，Ym)}。

5)已知切線y=x+bij與錨節點通信圓的切點:

及切線y=－x+bij與錨節點通信圓的切點:

帶入切線y=x+bij及y=－x+bij中，可以求得切線與y軸的截距:

求 min(bi1)、max(bi2)、max(bi3)、min(bi4)可得圓外切線所組成的區域:

從圖1可以看出，圓外切Bounding-box方法形成的搜索區域相對于其他Bounding-box方法所搜索的估計區域明顯減小，因此能夠大大提高定位的精度。該搜索區域的質心方程為

其坐標為

6)計算定位誤差:設節點的真實坐標為(X，Y)，定位系統估計的坐標為()，使用均方根誤差作為定位誤差參數來評價定位的準確度［10］:

2 實驗評估

首先對本文提出的圓外切Bounding-box及其他相關定位算法的性能進行評估和分析，分別采用仿真數據和實際定位環境中的RSSI值兩類實驗數據來評估定位方法的性能;然后對各定位算法的計算復雜度和能耗進行分析。

2.1 評估環境搭建

2.1.1 實驗設置

1)仿真實驗設置

定位環境為3.2 m×3.2 m的定位區域，在該區域的4個頂點布置了4個錨節點，未知節點則沿著2個坐標分別以0.8 m的間隔移動未知節點，如圖2所示。共形成25個定位點。由于在4個頂點處未知節點與錨節點重合，因此將未知節點在x方向及y方向分別向正方形內部移動0.1 m。

圖2 定位區域示意圖Fig.2 The localization field

2)實際WSN定位實驗設置

節點是自研的CC2530模塊，如圖3所示。實驗部署如圖2所示，分別在室內走廊、大廳和室外開闊環境中的3.2 m×3.2 m范圍內，進行定位試驗，遇到未知節點與錨節點重合情況時，未知節點則在2個方向上各偏離0.1 m。

圖3 節點實物Fig.3 The node used in experiments

2.1.2 評估數據集

為了全面評估所提出的定位方法，采用仿真數據和實際WSN定位數據2種評估數據集。

1)仿真數據集:向錨節點與未知節點間的距離值中加入N(0，σ2)噪聲，σ分為2種情況討論，分別為與距離d成正比的σ2=d/10，及與距離無關的σ2=0.2，為了計算在統計狀態下的誤差分布情況，在每個未知節點處計算150次均方根誤差，并得到誤差的平均值。

2)實際WSN定位數據集:在上述3種定位環境中，基于采集的實際RSSI數據(錨節點與未知節點間通信對應的RSSI值)，并采用基于RSSI數據的通信距離估計方法DEDC(distance estimation using data clustering)［4］得到距離估計值，然后對本文提出的圓外切Bounding-box定位方法的性能進行評估。

2.1.3 實驗評估參數

均方根誤差作為評估參數來評估定位方法的定位準確度，如式(7)所示，其值越小，則表示定位誤差越小，定位的準確度越高。

2.1.4 實驗設計

在實驗評估時，首先應用圓外切Bounding-box定位方法對2種仿真數據進行定位，并和其他相關定位方法進行比較分析;然后基于實際WSN定位環境中的數據集對所提出方法進行評估，并和其他相關方法進行比較分析。最后對算法的計算時間復雜度、計算量、延遲和功耗進行分析和比較。

2.2 仿真數據評估

在仿真數據中，通過向錨節點與未知節點間的距離值中加入N(0，σ2)噪聲引入距離估計誤差，σ分為2種情況討論，分別為與距離d成正比的σ2=d/10，及與距離無關的σ2=0.2，分別對這2種情況進行評估。

2.2.1 N(0，d/10)情況下定位誤差分析

向錨節點與未知節點間的距離值中加入N(0，d/10)噪聲，并應用 Bounding-box［2］(簡寫為 B-box)、三點 質 心 Bounding-box［3］、三 三 加 權 質 心 Boundingbox［3］、加權 Bounding-box［4］和圓外切 Bounding-box 5 種定位方法進行定位，并計算它們對應25個定位點的定位均方根誤差，如圖4所示。表1顯示了定位算法的平均誤差及最大誤差情況。

圖4 N(0，d/10)噪聲時各方法的定位誤差Fig.4 Localization error of different method with N(0，d/10)noise

由圖4可知，相對于其他4種定位算法，圓外切改進Bounding-box定位算法在各定位點上對應的平均定位誤差算法是最小的，說明圓外切改進Bounding-box算法具有較高的定位準確度。

表1 N(0，d/10)的噪聲時各方法的定位誤差Table 1 Localization error of different methods with N(0，d/10)noise

由表1可見，相對于Bounding-box、加權Boundingbox、三點質心Bounding-box和三三加權質心Bounding-box定位算法，圓外切改進Bounding-box算法在平均誤差上分別改善了 25.71%、7.14%、42.22%、36.59%，在最大誤差上分別改善了47.76%、10.26%、46.15%和45.31%。

因此，相對于其他相關定位算法，圓外切改進的Bounding-box定位算法具有較高的定位準確度，這主要歸因于其采用了與實際比較貼近的圓形的通信區域模型。

2.2.2 N(0，0.2)情況下定位誤差分析

向錨節點與未知節點間的距離值中加入N(0，0.2)噪聲，并應用 Bounding-box［2］(簡寫為 B-box)、三點 質 心 Bounding-box［3］、三 三 加 權 質 心 Boundingbox［3］、加權 Bounding-box［4］和圓外切 Bounding-box 5 種定位方法進行定位，并計算它們各自對應的25個定位點的定位均方根誤差，如圖5所示，表2顯示了5種定位算法的平均誤差及最大誤差情況。

圖5 N(0，0.2)噪聲時各方法的定位誤差Fig.5 Localization error of different method with N(0，0.2)noise

表2 N(0，0.2)的噪聲時各方法的定位誤差Table 2 Localization error of different methods with N(0，0.2)noise

由圖5可知，相對于其他4種定位算法，圓外切改進B-box定位算法在各定位點上對應的平均定位誤差算法是最小的。

由表2可見，相對于Bounding-box、加權Boundingbox、三點質心Bounding-box和三三加權質心Boundingbox定位算法，圓外切改進Bounding-box算法在平均定位誤差上分別改善了 35.29%、4.35%、50.00%、43.59%，在最大誤差上分別改善了 50.00%、0.00%、49.21%和49.21%。

綜上，2種噪聲情況下的實驗結果表明，本文提出的圓外切Bounding-box改進定位算法具有較高的定位準確度，同時加權的Bounding-box方法也具有較高的定位準確度。

2.3 實際WSN定位評估

在上述3種典型定位環境中，對25個定位點的RSSI數據進行采集，并采用DEDC［4］方法進行距離估計，并將得到距離估計值應用到 Bounding-box［2］、加權Bounding-box［4］、三三質心 Bounding-box［3］、三三加權質心Bounding-box［3］和本文提出的圓外切 Bounding-box定位方法中，并比較它們的定位均方根誤差。3種典型定位環境中，各定位方法對應的定位誤差如表3、表4和表5所示。表中的改善程度是圓外切Bounding-box改進算法相對于其他算法的定位誤差降低的百分比。

表3 走廊環境中25個定位點的平均定位誤差Table 3 Mean of localization error of 25 points in corridor

表4 大廳環境中25個定位點的平均定位誤差Table 4 Mean of localization error of 25 points in hall

表5 室外環境中25個定位點的平均定位誤差Table 5 Mean of localization error of 25 points in open air

2.3.1 定位方法比較分析

由表3、4和5可以看出，圓外切B-box定位算法具有較低的定位誤差:

在室內走廊環境中，相對于其他算法，圓外切Bounding-box定位算法分別將定位誤差平均改善了1.59% 、8.82% 、11.43% 和 7.46% 。

在室內大廳環境中，相對于上述其他定位方法，圓外切Bounding-box定位算法分別將定位誤差平均改善了 13.64% 、5.00% 、30.91% 和 24.00% 。

在室外開闊環境中，相對于上述其它定位方法，圓外切Bounding-box定位算法分別將定位誤差平均改善了 35.48% 、23.08% 、53.49% 和 47.37% 。

綜上，圓外切Bounding-box定位算法具有較低的定位誤差。特別是室外環境中具有很明顯的優勢，這主要是因為其考慮了無線傳感器節點的通信區域模型，并通過切線組成的區域來減小估計范圍，獲得較高精度的定位結果。同時加權Bounding-box方法也具有較好的定位結果。

2.3.2 定位環境比較分析

由表3、4和5可知，在室內走廊環境中，所有算法的定位誤差都很大，室內大廳環境中次之，而室外開闊環境中最小。因為室內走廊通信環境復雜，使得RSSI值的不確定性較大，導致定位誤差較大。而在室外開闊環境中，不確定性因素較少存在，使得定位誤差較小。因此在部署定位系統時，應考慮環境因素對系統定位準確度的影響。

2.4 計算復雜度和能耗分析

對算法的計算復雜度、延時和能耗進行分析。

2.4.1 計算復雜度分析

對 Bounding-box［2］、加權 Bounding-box［3］、三 三 質心 Bounding-box［3］、三三加權質心 Bounding-box［4］和本文提出的圓外切Bounding-box定位方法的計算時間復雜度分析如表6所示。其中，m為錨節點個數，n為要定位點的個數。從表6可以看出，上述幾種定位方法的計算復雜度是相同的。而在具體計算量上有所差異，對上述幾種方法的計算量進行分析，如表7所示。

表6 定位方法計算復雜度分析Table 6 Calculation complexity analysis of different ocalization methods

表7 定位方法的計算量分析Table 7 Calculation analysis of different localization methods

從表7可以看出，所有Bounding-box改進算法相對于其基本方法，計算量均有所增加。其中圓外切Bounding-box方法的計算量高于Bounding-box方法及加權Bounding-box方法。因此，可以看出，定位精度的提高是以增加計算量為代價的。同時基于質心的方法計算量是最大的。因此，要根據具體的應用需求，來選擇合適的定位方法。

2.4.2 延時分析

本文中無線傳感器節點的微控制單元是基于8位的SOC架構，可運行頻率在32 MHz［11］。假定采用單指令周期處理方式。執行加/減運算為1個指令周期，執行比較運算為2個指令周期，執行乘/除法運算為5個指令周期，則結合表7中的計算量分析，可得上述幾種定位方法的時延如表8所示。

表8 定位方法的時延分析Table 8 Latency analysis of different localization methods

從表8可以看出，B-box、加權B-box和圓外切B-box定位方法的延時在一個數量級，且明顯低于基于質心的B－box定位方法。因此綜合考慮定位性能和時延，圓外切B-box定位算法具有明顯的優勢。

2.4.3 能耗分析

由于能量主要耗費在節點間的無線通信上［12］，根據文獻［12］中傳感器節點能量消耗模型，可得

式中:ETX(b，d)為向距離為d的節點發送b比特數據消耗的能量;ERX(b)為接收b比特數據消耗的能量;Eelec為接收b比特數據消耗的能量，典型值為50 nJ/bit;εfs為功率放大所需的能量，典型值為10 pJ/bit/m2。

上述各方法的定位過程是相同的。均是未知節點廣播定位請求數據包，各個錨節點收到該包后，發送響應數據包，返回自己的ID、位置信息以及接收到數據包的RSSI值。假定定位請求數據包長度為136 bit，響應數據包長度為178 bit。則采用m個錨節點進行定位時，整個定位系統消耗的能量為

由式(11)可知，主要的能量消耗在無線通信上。不同定位方法的計算量有所不同，但對于無線通信而言，可以忽略。因此，應盡量減小無線通信的次數以及通信時的數據長度。

3 結束語

目前Bounding-box及其改進定位算法普遍采用正方形作為WSN節點通信范圍模型，與實際的模型不一致，導致較大的WSN定位誤差。針對該問題，本文提出了圓外切Bounding-box改進定位算法。綜合考慮定位精度、計算復雜度、計算量、時延和能耗等因素可知:圓外切Bounding-box定位方法是以提高一定計算量為代價換取定位精度的提高，為WSN定位應用系統提供了一種技術方案選擇。因此，需要根據具體的需求，選擇合適的定位方法。定位方法的優化選擇也是下一步研究的主要內容。

［1］EUNCHAN K，KISEON K.Distance estimation with weighted lease squares for mobile beacon-based localization in wireless sensor networks［J］.IEEE Signal Processing Letters，2010，17(6):559-562.

［2］詹杰，劉宏立，劉述鋼，等.基于RSSI的動態權重定位算法研究［J］.電子學報，2011，39(1):82-87.ZHAN Jie，LIU Hongli，LIU Shuxinag，et al.The study of dynamic degree weighted centriod localization algorithm based on RSSI［J］.Acta Electronica Sinica，2011，39(1):82-87.

［3］郭海琦.基于ZigBee的無線傳感器網絡定位算法的研究與應用［D］.成都:西南交通大學，2007:19-32.GUO Haiqi.Research of the localization method based on ZigBee［D］.Chengdu:Southwest Communication University，2007:19-32.

［4］王丹.基于RSSI的無線傳感器網絡定位研究［D］.哈爾濱:哈爾濱工業大學，2011:44-48.WANG Dan.Research on the localization method based on RSSI for wireless sensor network［D］.Harbin:Harbin Institute of Technology，2011:44-48.

［5］姚英彪，曾嶸，易志強.基于邊框定界的WSN分布式全搜索定位算法［J］.通信學報，2012，33(Z2):135-140.YAO Yingbiao，ZENG Rong，YI Zhiqiang.Bounding box based distributed search localization algorithm for WSN［J］.Journal of Communications，2012，33(Z2):135-140.

［6］SANABRIA-RUSSO L，CANO C，BELLALTA B.Localization procedure for randomly deployed WSNs based on the composability of position estimation protocols［C］//Proceedings of 9thInternational Wireless Communications and Mobile Computing Conference.Sardinia，Italy，2013:621-626.

［7］SHI Xin，ZHANG Linghua.High-precision weighted Bounding Box localization algorithm for wireless sensor network［C］//Proceedings of 2013 IEEE 3rd International Conference on Information Science and Technology(ICIST 2013).Yangzhou，China，2013:1110-1113.

［8］YANG Yuan，ZHAO Yubin，KYAS M.Weighted least-squares by bounding-box(B-WLS)for NLOS mitigation of indoor localization［C］//Proceedings of IEEE Vehicular Technology Conference.Yangzhou，China，2013:1110-1113.

［9］程偉，史浩山，王慶文.基于差分修正的傳感器網絡加權質心定位算法［J］.系統仿真學報，2012，24(2):389-393.CHENG Wei，SHI Haoshan，WANG Qingwen.Weighted centroid localization algorithm based on different correlation for sensor network ［J］.Journal of System Simulation，2012，24(2):389-393.

［10］LUO Qinghua，YAN Xiaozhen，LI Junbao，et al.DDEUDSC:dynamic distance estimation using uncertain data stream clustering in mobile wireless sensor networks［J］.Measurement，2014，55:423-433

［11］LUO Qinghua，PENG Yu，PENG Xiyuan，et al.Uncertain data clustering-based distance estimation in wireless sensor networks［J］.Sensors，2014，14(4):6584-6605.

［12］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.