基于垂直平分線的無線傳感器網絡定位改進算法

董海棠，萬國峰，駱巖紅

(1．蘭州交通大學機電工程學院，蘭州730070;2．西北民族大學電氣工程學院，蘭州730030)

1 概述

無線傳感器網絡(Wireless Sensor Network，WSN)通常利用已知坐標位置的信標節點去推算其余未知目標節點的位置坐標［1-2］，因此產生了很多定位算法。其中，研究和應用最廣泛的當屬質心算法［3］。質心算法的定位精度受網絡節點分布和錨節點位置影響較大，尤其當錨節點所接收的信息的方差很大時，定位精度就會變得很低［4］。接收信號強度指示(Received Signal Strength Indication，RSSI)距離測量無需額外硬件，實現簡單，具備低功耗、低成本等特點，應用十分廣泛［5］。文獻［6］等將RSSI與質心算法相結合，得到多種基于RSSI的加權質心定位算法，定位精度有所提高，但當參與定位的錨節點構成的多邊形比較扁平或分布在區域中心時，定位覆蓋率較低。文獻［7］提出了基于三角形角度的加權質心算法，能較好地解決這個問題。而文獻［8］用粒子群優化的方法，文獻［9］用遺傳算法，文獻［10］用模擬退火算法提高定位精度。

為克服基于單跳的定位算法因為參與定位的錨節點初始坐標相同而使可計算的有效節點數目減少，未知節點最終無法進行定位求精的缺點，文獻［11］提出基于跳數的無線傳感器網絡定位求精算法。

前面提到的算法有的定位精度很低，有的計算量和通信開銷大，且都存在定位覆蓋率不夠高的缺點。為此，文獻［12］提出基于區域的無需測距的APIT定位算法，但該算法一方面通信開銷大，另一方面定位覆蓋率很低。文獻［13］提出的基于垂直平分線的區域定位算法(Midnormel-based area Location Algorithm，MBLA)和文獻［14］提出的 IAPIT算法(Improved Approximate PIT Test)力圖分別解決上述2個問題。

在文獻［15］提出的無線電傳播對數路徑損耗模型基礎上，文獻［16］提出了基于參考錨節點的高斯校正模型(Reference-Gauss)。運用高斯分布函數處理未知節點收集到的n個從同一個發送節點發出的RSSI值，濾除概率密度小于0．6的RSSI值，然后求剩余的平均值，得到最終的優化RSSI值。不但消除了小概率事件對測量值造成的誤差，而且消除了環境散逸因子的影響，適合各種環境下的RSSI值測距。本文運用這一理論進行測距，根據待定位節點接收到的2個錨節點RSSI值的比值，將定位區域分割，以提高定位精度，降低迭代次數。同時為防止惡意攻擊，還提出防攻擊模型。

2 相關工作

2．1 IAPIT 算法

IAPIT算法是將三邊測量法以及幾何上的由已知兩點在輔助條件下求解兩圓交點的方法與APIT算法相結合，對于不能用APIT定位的節點，當與其通信的錨節點數為3個及以上時，用三邊測量法定位，等于2個時，以兩錨節點為圓心，通信距離為半徑作圓，兩圓的相交部分的幾何中心就是節點的估計位置。這一算法存在2個缺點:(1)算法復雜;(2)仍有無法定位的節點，說明定位覆蓋率還是不夠。

2．2 MBLA 算法

MBLA算法的核心思想是在與待定位節點能通信的錨節點集合中任意選擇2個，這2個錨節點連線的垂直平分線把整個區域分成兩部分。比較待定位節點與這兩個錨點的信號強度，則待定位節點一定位于信號強度強的錨點駐留的一側。在圖1中，待定位節點一定位于垂直平分線的a側。

圖1 MBLA判定原理

顯然，如果用該算法，每次定位的范圍比較大，定位精度不夠高，要達到要求的定位精度，需要迭代的次數較多，節點能量消耗大，不適合能量受限的無線傳感器網絡。

為解決傳統算法定位精度低、算法復雜、迭代次數多、消耗能量多等缺點，本文提出以待定位節點接收到的2個錨節點的RSSI值的比值為權值的改進垂直平分線定位算法(Improved Midnormal-based Localization Algorithm，IMBLA)。

3 IMBLA算法

IMBLA算法根據未知節點接收到的兩錨節點的RSSI值的比值，移動兩錨點的垂直平分線，然后確定待定位節點位置在移動后的垂直平分線的哪一側。

3．1 算法描述

3．1．1 理想情況下的IMBLA算法

IMBLA在可與之通信的錨點集合中以數學上排列組合的方式選擇2個錨點，則未知節點與錨點的關系一般為圖2所示的情況。

圖2 定位情況

對于滿足式(1)的情況，以 B點為基點，按dB/(dB+dC)比例對BC做垂線，這樣把整個區域分成兩部分，則可以肯定未知節點在錨節點C所在的這部分區域。

若滿足式(2)，則將BC的垂直平分線移動到C點，未知節點一定在B點的對側區域。

整個定位過程就是不斷地重復這個判定過程，每一次判定都會縮小待定位節點可能的所在區域，直到所有的錨節點窮盡，或定位精度已達到所需精度，則算法結束。

3．1．2 非理想情況下的IMBLA算法

假設所有節點都布置在X-Y平面，如圖3(a)所示的節點Ni和Nj分別以角pij和pji相互能看見，兩點之間的距離為dij。那么節點Nj相對于Ni的坐標為 xij=dijcospij和 yij=dijsinpij，同理，節點 Ni相對于 Nj的坐標 xji=dijcospji和 yji=dijsinpji。如果距離和角度的測量沒有誤差，則(xij+xji)=0，(yij+yji)=0。

當有障礙物時，由于多徑傳播，一個待定位節點可能會接收到一個錨點的多個RSSI值，如圖3(b)所示。節點Ni看到的節點Nj有2個位置(xij，yij)和(x'ij，y'ij)，其 RSSI值也不同，分別是 RSSIij和 RSSI'ij。同理，節點Nj看到的節點Ni也有2個坐標(xji，yji)和(x'ji，y'ji)。

圖3 定位誤差監測圖

顯然，(xij+xji)和(yij+yji)的值最小者為節點Nj相對于節點Ni的真實位置，即滿足式(3):

其中，TS是事先給定的誤差閾值。

3．1．3 算法對惡意攻擊的應對

所有節點與其相鄰節點交換信息，對于符合式(3)的節點，給可信任標志值，而對超過閾值TS的節點，給不可信任標志。當節點受到攻擊時(不論內部攻擊還是外部攻擊)，將不符合式(3)，則這樣的節點就是不可信任節點，不能參與定位，從而避免了惡意攻擊對算法的影響。由于該算法是基于區域定位的算法，顯然在防止惡意攻擊方面要比質心算法等優越。

3．2 算法步驟

算法步驟如下:

(1)各個錨節點周期性地向周圍廣播自身節點ID和位置。

(2)未知節點則收到與其能通信的錨節點的信息，從而構成各自的錨節點集合，并根據接收到的錨節點的RSSI值確定其與錨點之間的距離。

(3)在該錨點集合中用排列組合方式取2個點，與待定位節點構成圖2。用余弦定理判定∠ACB的大小，若小于，則按dB/(dB+dC)的比例作BC的垂線，把區域分成2個區域，未知節點就在錨點C所在的區域，否則，在對側區域。若滿足式(2)，則通過C點作BC的垂線，把區域分成2個區域，未知節點就在B點的對側區域。

(4)若定位精度未達到要求或還有錨節點組合沒有被測試，則重復步驟(3)，否則執行步驟(5)。

(5)計算重疊區域的重心(若已經達到定位精度，則此步驟不用)。

4 仿真結果

在Matlab7．10環境下進行仿真。節點通信半徑為R;節點隨機布置在一個5R×5R的正方形區域內。

定位誤差計算公式如下:

其中，xia和tia分別是未知節點的估計坐標和實際坐標。

4．1 迭代次數對定位誤差的影響

設總共有200個節點，其中錨節點占15%，所有節點通信半徑 R=10 m，MBLA和 IMBLA及IAPIT3種算法的仿真結果如圖4所示。可以看出，IAPIT的誤差比較大，其最小誤差略小于1 m;MBLA進行17次迭代后誤差減小到0．5 m，而IMBLA算法只用了4次迭代，誤差就降到0．5 m以下，最終接近0．25 m。迭代次數的減少能有效減小節點能量消耗，對于能量受限的無線傳感器網絡具有較大的意義。

圖4 定位誤差與迭代次數的關系

4．2 定位誤差率與可通信錨節點比例的關系

總節點數不變，改變錨節點的比例，對3種算法進行仿真，得出定位誤差率(定位誤與通信半徑之比)與錨節點比例的關系，結果如圖5所示。

圖5 定位誤差率與錨節點比例的關系

由圖5可知，錨節點比例在5%以下時，IMBLA算法的定位誤差率是MBLA的1/3左右，其原因是MBLA是以錨節點連線的垂直平分線劃分區域，當錨節點數量比較少時，區域劃分粗略，待定位節點可能的位置的范圍大，而IMBLA是根據接收到的錨節點的信號強度的大小把區域劃分成兩部分，區域劃分比較精細，有效縮小了待定位節點所在的范圍，誤差率大大減小。錨節點比例增加到10%以后，IMBLA的定位誤差率在10%以下，另兩種算法的定位誤差率還在20%以上。隨著錨節點比例的逐漸增加，劃分的區域越來越小，MBLA算法的定位精度逐漸接近IMBLA的定位精度。IAPIT算法的定位誤差率比前兩種算法大，當錨節點比例為15%時，誤差率是IMBLA的4倍，是MBLA的2倍，不過，定位精度也隨錨節點的增加而逐漸提高。錨節點比例達到35%以后，三者的定位精度接近。

4．3 網絡的定位覆蓋程度

圖6是在錨節點比例變化下，3種算法中可定位節點數的比較。當錨節點比例為5%時3種算法的定位覆蓋率(能夠定位的節點數與總節點數之比)基本一樣，都很低。隨著錨節點比例的增加，IAPIT算法定位覆蓋率上升緩慢，IMBLA和MBLA算法都迅速上升，但前者的定位覆蓋率明顯比后者高。錨節點比例上升到35%后，IMBLA算法的定位覆蓋率接近100%，另兩種算法的定位覆蓋率則分別是90%和87%。

圖6 定位覆蓋率與錨節點比例的關系

5 結束語

本文在分析MLBA算法、APIT算法和IAPIT算法優缺點的基礎上，借鑒加權質心算法，提出了MLBA算法的改進算法IMBLA。仿真結果表明，與MBLA和IAPIT算法相比，該算法定位精度和網絡覆蓋率較高，但其缺點是算法復雜度比MLBA高，雖然迭代次數比 MLBA少，但每次迭代耗時較MLBA高，因此，下一步將就此做一步改進。

［1］ Liu Yunhao，Yang Zheng，Wang Xiaoping．Location，Localization，and Localizability［J］．Journal of Computer Science and Technology，2010，25(2):274-297．

［2］ Yang Zheng，Liu Yunhao．Quality ofTrilateration:Confidence-based Iterative Localization［J］．IEEE Transactions on Parallel and Distributed Systems，2010，21(5):631-640．

［3］ Bulusu N，Heidemann J，Estrin D．GPS-less Low Cost Outdoor Localization for Very Small Devices［J］．IEEE Personal Communications Magazine，2000，7(5):28-34．

［4］ 劉運杰，金明錄，崔承毅．基于RSSI的無線傳感器網絡修正加權定位算法［J］．傳感技術學報，2010，23(5):717-721．

［5］ Zhong Ziguo，He Tian．Achieving Range-free Localization Beyond Connectivity［C］//Proceedings of the 7th International Conference on Embedded Net-worked Sensor Systems．New York，USA:ACM Press，2009:281-294．

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

［7］ 劉 瑾．基于測距的無線傳感器網絡的定位算法的研究［J］．航空計算技術，2009，39(6):124-126．

［8］ 王新芳，張 冰，馮友兵．基于粒子群優化的改進加權知心定位算法［J］．計算機工程，2012，38(1):90-95．

［9］ 章 磊，段莉莉，錢紫鵑，等．基于遺傳算法的WSN節點定位技術［J］．計算機工程，2010，36(10):85-87．

［10］ Kannan A A，MaoGuoqiang，VuceticB．Simulated Annealing Based Localization in Wireless Sensor Network Localization with Flip Ambiguity Mitigation［C］//Proceedings ofthe 63rd IEEE Vehicular Technology Conference．Washington D．C．，USA:IEEE Press，2006:1022-1026．

［11］ 郭永紅，萬江文，于 寧，等．基于跳數的無線傳感器網絡定位求精算法［J］．計算機工程，2009，35(3):145-147．

［12］ Ribeiro V J，RiediR H，Baraniuk R G．Locating Available Band-width Bottlenecks［J］．IEEE Internet Computing，2004，8(5):34-41．

［13］ 戴佩華，薛小平，邵玉華．基于垂直平分線的區域定位算法［J］．計算機工程，2009，35(2):105-108．

［14］ 周四清，陳銳標．無線傳感器網絡APIT定位算法及其改進［J］．計算機工程，2009，35(7):87-89．

［15］ 汪 煬，黃劉生，肖明軍，等．一種基于RSSI校驗的無線傳感器網絡節點的定位算法［J］．小型微型計算機系統，2009，30(1):59-62．

［16］ 萬國峰．基于錨節點和高斯函數的測距算法［J］．計算機工程，2013，39(2):73-76．