基于垂直平分線的無(wú)線傳感器網(wǎng)絡(luò)定位改進(jìn)算法

董海棠，萬(wàn)國(guó)峰，駱巖紅

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

1 概述

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

為克服基于單跳的定位算法因?yàn)閰⑴c定位的錨節(jié)點(diǎn)初始坐標(biāo)相同而使可計(jì)算的有效節(jié)點(diǎn)數(shù)目減少，未知節(jié)點(diǎn)最終無(wú)法進(jìn)行定位求精的缺點(diǎn)，文獻(xiàn)［11］提出基于跳數(shù)的無(wú)線傳感器網(wǎng)絡(luò)定位求精算法。

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

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

2 相關(guān)工作

2．1 IAPIT 算法

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

2．2 MBLA 算法

MBLA算法的核心思想是在與待定位節(jié)點(diǎn)能通信的錨節(jié)點(diǎn)集合中任意選擇2個(gè)，這2個(gè)錨節(jié)點(diǎn)連線的垂直平分線把整個(gè)區(qū)域分成兩部分。比較待定位節(jié)點(diǎn)與這兩個(gè)錨點(diǎn)的信號(hào)強(qiáng)度，則待定位節(jié)點(diǎn)一定位于信號(hào)強(qiáng)度強(qiáng)的錨點(diǎn)駐留的一側(cè)。在圖1中，待定位節(jié)點(diǎn)一定位于垂直平分線的a側(cè)。

圖1 MBLA判定原理

顯然，如果用該算法，每次定位的范圍比較大，定位精度不夠高，要達(dá)到要求的定位精度，需要迭代的次數(shù)較多，節(jié)點(diǎn)能量消耗大，不適合能量受限的無(wú)線傳感器網(wǎng)絡(luò)。

為解決傳統(tǒng)算法定位精度低、算法復(fù)雜、迭代次數(shù)多、消耗能量多等缺點(diǎn)，本文提出以待定位節(jié)點(diǎn)接收到的2個(gè)錨節(jié)點(diǎn)的RSSI值的比值為權(quán)值的改進(jìn)垂直平分線定位算法(Improved Midnormal-based Localization Algorithm，IMBLA)。

3 IMBLA算法

IMBLA算法根據(jù)未知節(jié)點(diǎn)接收到的兩錨節(jié)點(diǎn)的RSSI值的比值，移動(dòng)兩錨點(diǎn)的垂直平分線，然后確定待定位節(jié)點(diǎn)位置在移動(dòng)后的垂直平分線的哪一側(cè)。

3．1 算法描述

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

IMBLA在可與之通信的錨點(diǎn)集合中以數(shù)學(xué)上排列組合的方式選擇2個(gè)錨點(diǎn)，則未知節(jié)點(diǎn)與錨點(diǎn)的關(guān)系一般為圖2所示的情況。

圖2 定位情況

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

若滿足式(2)，則將BC的垂直平分線移動(dòng)到C點(diǎn)，未知節(jié)點(diǎn)一定在B點(diǎn)的對(duì)側(cè)區(qū)域。

整個(gè)定位過(guò)程就是不斷地重復(fù)這個(gè)判定過(guò)程，每一次判定都會(huì)縮小待定位節(jié)點(diǎn)可能的所在區(qū)域，直到所有的錨節(jié)點(diǎn)窮盡，或定位精度已達(dá)到所需精度，則算法結(jié)束。

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

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

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

圖3 定位誤差監(jiān)測(cè)圖

顯然，(xij+xji)和(yij+yji)的值最小者為節(jié)點(diǎn)Nj相對(duì)于節(jié)點(diǎn)Ni的真實(shí)位置，即滿足式(3):

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

3．1．3 算法對(duì)惡意攻擊的應(yīng)對(duì)

所有節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)交換信息，對(duì)于符合式(3)的節(jié)點(diǎn)，給可信任標(biāo)志值，而對(duì)超過(guò)閾值TS的節(jié)點(diǎn)，給不可信任標(biāo)志。當(dāng)節(jié)點(diǎn)受到攻擊時(shí)(不論內(nèi)部攻擊還是外部攻擊)，將不符合式(3)，則這樣的節(jié)點(diǎn)就是不可信任節(jié)點(diǎn)，不能參與定位，從而避免了惡意攻擊對(duì)算法的影響。由于該算法是基于區(qū)域定位的算法，顯然在防止惡意攻擊方面要比質(zhì)心算法等優(yōu)越。

3．2 算法步驟

算法步驟如下:

(1)各個(gè)錨節(jié)點(diǎn)周期性地向周圍廣播自身節(jié)點(diǎn)ID和位置。

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

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

(4)若定位精度未達(dá)到要求或還有錨節(jié)點(diǎn)組合沒(méi)有被測(cè)試，則重復(fù)步驟(3)，否則執(zhí)行步驟(5)。

(5)計(jì)算重疊區(qū)域的重心(若已經(jīng)達(dá)到定位精度，則此步驟不用)。

4 仿真結(jié)果

在Matlab7．10環(huán)境下進(jìn)行仿真。節(jié)點(diǎn)通信半徑為R;節(jié)點(diǎn)隨機(jī)布置在一個(gè)5R×5R的正方形區(qū)域內(nèi)。

定位誤差計(jì)算公式如下:

其中，xia和tia分別是未知節(jié)點(diǎn)的估計(jì)坐標(biāo)和實(shí)際坐標(biāo)。

4．1 迭代次數(shù)對(duì)定位誤差的影響

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

圖4 定位誤差與迭代次數(shù)的關(guān)系

4．2 定位誤差率與可通信錨節(jié)點(diǎn)比例的關(guān)系

總節(jié)點(diǎn)數(shù)不變，改變錨節(jié)點(diǎn)的比例，對(duì)3種算法進(jìn)行仿真，得出定位誤差率(定位誤與通信半徑之比)與錨節(jié)點(diǎn)比例的關(guān)系，結(jié)果如圖5所示。

圖5 定位誤差率與錨節(jié)點(diǎn)比例的關(guān)系

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

4．3 網(wǎng)絡(luò)的定位覆蓋程度

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

圖6 定位覆蓋率與錨節(jié)點(diǎn)比例的關(guān)系

5 結(jié)束語(yǔ)

本文在分析MLBA算法、APIT算法和IAPIT算法優(yōu)缺點(diǎn)的基礎(chǔ)上，借鑒加權(quán)質(zhì)心算法，提出了MLBA算法的改進(jìn)算法IMBLA。仿真結(jié)果表明，與MBLA和IAPIT算法相比，該算法定位精度和網(wǎng)絡(luò)覆蓋率較高，但其缺點(diǎn)是算法復(fù)雜度比MLBA高，雖然迭代次數(shù)比 MLBA少，但每次迭代耗時(shí)較MLBA高，因此，下一步將就此做一步改進(jìn)。

［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］ 劉運(yùn)杰，金明錄，崔承毅．基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)修正加權(quán)定位算法［J］．傳感技術(shù)學(xué)報(bào)，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差分修正的加權(quán)質(zhì)心定位算法［J］．傳感器與微系統(tǒng)，2012，31(5):139-144．

［7］ 劉 瑾．基于測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)的定位算法的研究［J］．航空計(jì)算技術(shù)，2009，39(6):124-126．

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

［9］ 章 磊，段莉莉，錢紫鵑，等．基于遺傳算法的WSN節(jié)點(diǎn)定位技術(shù)［J］．計(jì)算機(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］ 郭永紅，萬(wàn)江文，于 寧，等．基于跳數(shù)的無(wú)線傳感器網(wǎng)絡(luò)定位求精算法［J］．計(jì)算機(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］ 戴佩華，薛小平，邵玉華．基于垂直平分線的區(qū)域定位算法［J］．計(jì)算機(jī)工程，2009，35(2):105-108．

［14］ 周四清，陳銳標(biāo)．無(wú)線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)［J］．計(jì)算機(jī)工程，2009，35(7):87-89．

［15］ 汪 煬，黃劉生，肖明軍，等．一種基于RSSI校驗(yàn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法［J］．小型微型計(jì)算機(jī)系統(tǒng)，2009，30(1):59-62．

［16］ 萬(wàn)國(guó)峰．基于錨節(jié)點(diǎn)和高斯函數(shù)的測(cè)距算法［J］．計(jì)算機(jī)工程，2013，39(2):73-76．