基于垂直平分線的非測(cè)距定位算法

鄒東堯，李　晨，劉碧微

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，鄭州　450001)

?

基于垂直平分線的非測(cè)距定位算法

鄒東堯，李晨，劉碧微

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，鄭州450001)

摘要：在無(wú)線傳感器網(wǎng)絡(luò)定位機(jī)制中，近似三角形內(nèi)點(diǎn)測(cè)試(APIT)定位算法因思想簡(jiǎn)單、硬件成本低、定位精度高而被廣泛應(yīng)用，但算法性能會(huì)因錨節(jié)點(diǎn)分布不均勻受到嚴(yán)重影響；為提高節(jié)點(diǎn)定位精度和解決APIT定位算法邊緣效應(yīng)的問(wèn)題，提出一種基于垂直平分線的非測(cè)距定位算法；該算法利用接收信號(hào)強(qiáng)度指示值(RSSI)值篩選錨節(jié)點(diǎn)并與等腰三角形底邊中垂線過(guò)頂點(diǎn)的幾何原理結(jié)合進(jìn)行定位，可以得到比較合理的定理精度，性能相對(duì)穩(wěn)定；仿真結(jié)果表明，該算法可有效提高無(wú)線傳感器網(wǎng)絡(luò)定位的精度和覆蓋率。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；近似三角形內(nèi)點(diǎn)測(cè)試；接收信號(hào)強(qiáng)度指示； 定位精度；定位覆蓋率

0引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)中節(jié)點(diǎn)的位置信息至關(guān)重要。對(duì)于無(wú)線傳感器網(wǎng)絡(luò)中所得到的感知數(shù)據(jù)，沒(méi)有相應(yīng)的位置信息，通常是無(wú)意義的[1-2]。實(shí)時(shí)地確定事件發(fā)生的位置也是提供安全反恐、國(guó)防軍事、環(huán)境監(jiān)測(cè)與預(yù)報(bào)位置信息的前提，所以定位技術(shù)對(duì)有效應(yīng)用無(wú)線傳感器網(wǎng)絡(luò)起著關(guān)鍵作用[3-5]。

根據(jù)定位過(guò)程中是否依靠測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為基于測(cè)距和基于非測(cè)距兩種?；跍y(cè)距的定位算法主要有AOA、TOA、TDOA、RSSI[6-7]；基于非測(cè)距的定位算法主要有質(zhì)心算法、DV-hop算法、Amorphous算法、APIT算法[8-13]。基于測(cè)距的定位技術(shù)比基于非測(cè)距的定位技術(shù)精確度更優(yōu)，但測(cè)距過(guò)程在一定程度上加大了通信量和計(jì)算量，也會(huì)使硬件成本增加。因此，基于測(cè)距的定位技術(shù)在大規(guī)模傳感器網(wǎng)絡(luò)中受到限制，而基于非測(cè)距的定位技術(shù)硬件成本合理，能耗低，適用范圍比較廣泛，但定位精度較低。APIT定位算法是經(jīng)典的無(wú)需測(cè)距的定位算法之一，該算法在密集網(wǎng)絡(luò)中,定位精度較為合理, 性能相對(duì)穩(wěn)定, 網(wǎng)絡(luò)成本低, 實(shí)現(xiàn)也相對(duì)容易。但在隨機(jī)分布網(wǎng)絡(luò)中會(huì)造成定位誤差較大、覆蓋率較低的現(xiàn)象。

為了提高定位的精度和覆蓋率，本文提出了一種基于垂直平分線的非測(cè)距定位算法(perpendicular bisector algorithm，PB算法)。該算法只需提取接收到的RSSI值，且不需要將其轉(zhuǎn)化為具體的距離值，減小了計(jì)算復(fù)雜度,并且對(duì)錨節(jié)點(diǎn)分布的方向沒(méi)有要求，因此提高了定位精度、解決了邊緣節(jié)點(diǎn)無(wú)法定位的問(wèn)題。

1APIT算法存在的問(wèn)題

APIT算法是一種適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的分布式非測(cè)距定位算法。該算法原理是首先從未知節(jié)點(diǎn)周圍選取3個(gè)錨節(jié)點(diǎn)組成一個(gè)三角形，若未知節(jié)點(diǎn)在三角形內(nèi)部，則將其標(biāo)記，按照相同原理對(duì)未知節(jié)點(diǎn)周圍的錨節(jié)點(diǎn)進(jìn)行不同組合組成不同三角形，并分別標(biāo)記[14]。最終計(jì)算出所標(biāo)記的所有三角形的重疊區(qū)域，求其質(zhì)心位置即為定位結(jié)果。APIT定位算法存在的問(wèn)題如下：

1)APIT定位算法只有在錨節(jié)點(diǎn)數(shù)量足夠多時(shí)，才可將未知節(jié)點(diǎn)完全覆蓋到錨節(jié)點(diǎn)構(gòu)成的三角形區(qū)域中。但由于WSNs的節(jié)點(diǎn)是隨機(jī)部署的，可能出現(xiàn)因某些區(qū)域分布不均勻而導(dǎo)致部分節(jié)點(diǎn)無(wú)法定位的現(xiàn)象，并且影響定位精度。

2)在WSNs中某些小區(qū)域內(nèi)因未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)個(gè)數(shù)量少于3個(gè)無(wú)法構(gòu)成三角形進(jìn)行定位，從而形成未確定節(jié)點(diǎn)。當(dāng)未知節(jié)點(diǎn)不在鄰居錨節(jié)點(diǎn)所構(gòu)成的三角形內(nèi)也會(huì)成為未確定節(jié)點(diǎn)。

3)APIT定位算法由質(zhì)心計(jì)算公式得出重疊部分的質(zhì)心位置，但是由公式所得到的質(zhì)心位置不是節(jié)點(diǎn)的準(zhǔn)確位置，所以會(huì)造成一定的誤差。

4)通常會(huì)采用增加錨節(jié)點(diǎn)數(shù)量的方法解決APIT 定位過(guò)程出現(xiàn)的 OutToIn或InToOut問(wèn)題。然而錨節(jié)點(diǎn)數(shù)量的增加會(huì)使整個(gè)網(wǎng)絡(luò)的能量消耗及成本增多。

2PB算法

2.1算法描述

錨節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播自己的ID編號(hào)、位置信息、發(fā)射信號(hào)強(qiáng)度，未知節(jié)點(diǎn)接收通信半徑內(nèi)錨節(jié)點(diǎn)的廣播信息并計(jì)算接收到的RSSI值。未知節(jié)點(diǎn)根據(jù)設(shè)定的閥值RSSIf，選取其接收的RSSI值中所有大于RSSIf的錨節(jié)點(diǎn)。

如圖1所示，選擇RSSI數(shù)值相差小的兩組錨節(jié)點(diǎn)，RSSI值相差小即錨節(jié)點(diǎn)與未知節(jié)點(diǎn)距離接近。例如P1和P2，P3和P4，分別連接P1和P2得線段c1，連接P3和P4得線段c2，線段c1和c2即表示為兩個(gè)等腰三角形的底邊。分別作兩個(gè)三角形底邊c1和c2的垂直平分線l1和l2，設(shè)兩條垂直平分線相交于點(diǎn)P，根據(jù)垂直平分線定理可知，點(diǎn)P即為未知節(jié)點(diǎn)的定位坐標(biāo)。

圖1　PB定位算法

由于最終的定位結(jié)果是通過(guò)計(jì)算垂直平分線l1和l2的交點(diǎn)所得，所以當(dāng)?shù)走叢缓线m時(shí)，對(duì)定位的結(jié)果影響較大，甚至?xí)?dǎo)致無(wú)法定位。例如若直線l1和l2平行則無(wú)法計(jì)算出定位坐標(biāo)。如圖2所示，此時(shí)l1和l2相交于無(wú)窮遠(yuǎn)處，即使兩直線不平行，斜率相近也會(huì)造成誤差的較大。

圖2　垂直平分線平行

此外若選取的錨節(jié)點(diǎn)過(guò)近，如圖3所示，此時(shí)的線段P1P和P2P長(zhǎng)度差距不大，但由于錨節(jié)點(diǎn)P1和P2相距過(guò)近使得偏差嚴(yán)重?cái)U(kuò)大，導(dǎo)致定位結(jié)果誤差過(guò)大。因此，選取錨節(jié)點(diǎn)時(shí)對(duì)應(yīng)的垂直平分線不能平行，還要限制選取錨節(jié)點(diǎn)間的距離，避免過(guò)近而造成較大的定位誤差。

圖3　錨節(jié)點(diǎn)距離過(guò)近

設(shè)選定的錨節(jié)點(diǎn)坐標(biāo)P1(x1,y1)，P2(x2,y2)，P3(x3,y3)，P4(x4,y4)，為防止底邊平行而無(wú)法定位，建立限制條件：

(1)

為避免圖3所示的底邊過(guò)短情況的出現(xiàn)，建立限制條件：

(2)

2.2算法步驟

2.2.1提取信息

各錨節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播自己的位置信息，未知節(jié)點(diǎn)接收其通信半徑內(nèi)或RSSI值大于閥值的錨節(jié)點(diǎn)信息，將錨節(jié)點(diǎn)的RSSI值和坐標(biāo)放入矩陣S，如公式(3)，其中錨節(jié)點(diǎn)Pi(xi,yi)的RSSI值為Si，矩陣S第一行為錨節(jié)點(diǎn)的RSSI值，第二行第三行為對(duì)應(yīng)錨節(jié)點(diǎn)的橫縱坐標(biāo)。設(shè)接收到附近N個(gè)錨節(jié)點(diǎn)的RSSI數(shù)據(jù)，那么矩陣S為三行N列矩陣：

(3)

其中:Si≥RSSIf(i=0,1,2，...，N-1)。

2.2.2整理錨節(jié)點(diǎn)信息矩陣

(4)

2.2.3除去不符合條件的錨節(jié)點(diǎn)

2.2.4連接符合條件的錨節(jié)點(diǎn)和未知節(jié)點(diǎn)組成三角形，并作以兩個(gè)錨節(jié)點(diǎn)為底邊的垂直平分線，垂線的交點(diǎn)為定位結(jié)果。

首先選取矩陣SS的前兩列，既相對(duì)差距最小且符合條件的兩組錨節(jié)點(diǎn)，會(huì)得到3個(gè)或4個(gè)錨節(jié)點(diǎn)。設(shè)有4個(gè)錨節(jié)點(diǎn)P1(x1,y1)，P2(x2,y2)，P3(x3,y3)，P4(x4,y4)。將P1和P2相連得到直線l1，P3和P4相連得到直線l2，l1和l2垂直平分線的焦點(diǎn)為未知節(jié)點(diǎn)定位結(jié)果。

3算法仿真與分析

3.1錨節(jié)點(diǎn)最小距離

在1.1節(jié)算法描述部分，提到為了控制算法誤差，設(shè)定了錨節(jié)點(diǎn)的最小距離參數(shù)dF。表示在選定到未知節(jié)點(diǎn)距離相同或相近的錨節(jié)點(diǎn)時(shí)，兩個(gè)錨節(jié)點(diǎn)的最小距離不能小于dF。為了分析參數(shù)dF的變化對(duì)定位精度的影響，仿真環(huán)境設(shè)置為100 m×100 m的方形區(qū)域，節(jié)點(diǎn)通信半徑為10 m，節(jié)點(diǎn)總數(shù)為400個(gè)，錨節(jié)點(diǎn)數(shù)量占節(jié)點(diǎn)總數(shù)的20%、22.5%、25%……50%遞增變化，每種情況測(cè)試10次，最終結(jié)果取其均值以減少誤差，則dF在(0,12]內(nèi)取值時(shí)，平均誤差如圖4所示。

圖4　dF與平均定位誤差關(guān)系圖

由圖4可以看出，當(dāng)dF小于2 m時(shí)定位誤差非常大，此時(shí)會(huì)出現(xiàn)圖3中的錨節(jié)點(diǎn)過(guò)近而造成的定位偏離。此現(xiàn)象可以通過(guò)直線的斜率公式解釋，設(shè)直線AB上兩點(diǎn)A(x1,y1)，B(x2,y2)，若直線的斜率存在則可以表示為k= (y1-y2)/ (x1-x2)。點(diǎn)A和B比較接近時(shí)可以表示為：y1≈y2，x1≈x2。那么y1-y2或x1-x2有很小的變動(dòng)都會(huì)導(dǎo)致斜率k的較大變化，此時(shí)誤差會(huì)得到進(jìn)一步擴(kuò)大。因此限制所選取的錨節(jié)點(diǎn)距離有其必要性。

當(dāng)dF大于10.25 m時(shí)，由于dF過(guò)大，滿足條件的錨節(jié)點(diǎn)不足以滿足定位需求而無(wú)法定位，出現(xiàn)圖4中所示的后段無(wú)數(shù)據(jù)情況。當(dāng)dF取值過(guò)小時(shí)，因垂直平分線可能偏離嚴(yán)重而造成誤差較大，dF取值過(guò)大時(shí)，因符合條件的錨節(jié)點(diǎn)過(guò)少而無(wú)法定位。而在4 ~6 m的取值范圍內(nèi)取值時(shí)，平均誤差較小且變化幅度不大。因此，取4 ~6 m之間平均誤差最小的點(diǎn)為最優(yōu)dF值，即dF=5.25 m。

3.2定位精度和覆蓋率

節(jié)點(diǎn)定位精度和覆蓋率是評(píng)價(jià)一個(gè)定位算法性能好壞的關(guān)鍵指標(biāo)[15]。在實(shí)驗(yàn)過(guò)程中，我們利用隨機(jī)生成的場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)，比較兩個(gè)算法在相同實(shí)驗(yàn)條件下的定位精度和覆蓋率。在100 m×100 m的方形區(qū)域進(jìn)行測(cè)試，節(jié)點(diǎn)通信半徑為10 m，節(jié)點(diǎn)總數(shù)為400個(gè)，每種情況測(cè)試10次得到相應(yīng)數(shù)據(jù)，取其均值為最終結(jié)果。APIT算法和PB算法定位誤差如圖5所示。

圖5　PB算法與APIT算法定位誤差比較

由圖5可以看出，當(dāng)錨節(jié)點(diǎn)數(shù)量達(dá)到32.5%時(shí)，PB算法的定位誤差趨于一個(gè)定值，其定位誤差低于APIT算法。在錨節(jié)點(diǎn)密度較低時(shí)，很多未知節(jié)點(diǎn)不能收到足夠多的錨節(jié)點(diǎn)信息，因此APIT算法不能對(duì)此類節(jié)點(diǎn)進(jìn)行定位，而PB算法可以對(duì)此類節(jié)點(diǎn)進(jìn)行定位，但由于此類節(jié)點(diǎn)收到的錨節(jié)點(diǎn)信息較少，所以定對(duì)位誤差較大，使PB算法整體定位誤差提高。APIT算法和PB算法定位覆蓋率如圖6所示。

圖6　定位覆蓋率比較圖

由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的隨機(jī)分布特點(diǎn)，導(dǎo)致了節(jié)點(diǎn)分布不均勻和邊緣效應(yīng)情況的出現(xiàn)。使用APIT算法定位會(huì)存在一些無(wú)法定位的節(jié)點(diǎn)，定位覆蓋率也會(huì)隨之下降。從圖6中可以看出，兩種算法隨著錨節(jié)點(diǎn)比例的增加定位覆蓋率都有所增加。由于PB算法只需根據(jù)錨節(jié)點(diǎn)建立兩條直線，解出兩條直線的垂直平分線交點(diǎn)即可，所以定位覆蓋率要高于APIT算法。

采用PB算法進(jìn)行定位，定位精度和覆蓋率均優(yōu)于APIT算法。此外在組網(wǎng)階段，PB算法不需要進(jìn)行網(wǎng)格劃分，形成網(wǎng)格陣列，從而降低了組網(wǎng)過(guò)程的復(fù)雜度。定位過(guò)程中APIT算法要進(jìn)行多次區(qū)域劃分，尋找重疊區(qū)域，該過(guò)程計(jì)算量大對(duì)硬件要求較高，而PB算法只需根據(jù)錨節(jié)點(diǎn)建立兩條直線求其垂直平分線的交點(diǎn)，減少了計(jì)算難度。

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

本文提出了一種基于垂直平分線的非測(cè)距定位算法，利用RSSI值篩選錨節(jié)點(diǎn)并根據(jù)等腰三角形底邊中垂線過(guò)頂點(diǎn)的幾何原理進(jìn)行定位，解決了APIT算法中錨節(jié)點(diǎn)分布不均勻定位誤差大和邊緣效應(yīng)的問(wèn)題。實(shí)驗(yàn)結(jié)果表明：在組網(wǎng)復(fù)雜性、計(jì)算難度、定位精度和覆蓋率方面，PB算法相比APIT算法均有所改善。

參考文獻(xiàn)：

[1] 杜楊洋,毛永毅.基于多功率移動(dòng)錨節(jié)點(diǎn)WSN 智能定位算法[J].電子技術(shù)應(yīng)用, 2015,41(6):88-90,94.

[2] 王焱,單欣欣,姜偉.無(wú)線傳感網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)定位技術(shù)研究[J].傳感技術(shù)學(xué)報(bào),2011,24(9):1326-1330.

[3] 史躍飛,馮秀芳,高昊.一種基于動(dòng)態(tài)錨節(jié)點(diǎn)的改進(jìn)加權(quán)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(10):151-154.

[4] 毛科技,金洪波,苗春雨，等.無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)位置驗(yàn)證方法[J].傳感技術(shù)學(xué)報(bào),2015,28(6):850-857.

[5] 周帆,江維,李樹全，等.基于粒子濾波的移動(dòng)物體定位和追蹤算法[J].軟件學(xué)報(bào), 2013,24(9):2196-2213.

[6] 鄒東堯,鄭道理,李晨.RSSI曲線擬合的誤差分析與分段方法[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版),2014,29(2):62-66.

[7] 何中勝,朱宇光,莊燕濱.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制技術(shù)綜述[J].計(jì)算機(jī)測(cè)量與控制,2012,20(7):1737-1739,1749.

[8] Nieolescu D, Nath B. Ad Hoc positioning systems(APS)[A].Global Telecommunications Conference[C].San Antonio,2001:2926-2931.

[9] 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.

[10] Rout C S, Krishna S H, Vivekchand S R C. Hydrogen and ethanol sensors based on ZoO nano wires and natotubes[J].Chemical Physics Letter,2006.

[11] 黃海輝,李龍連.WSN 中一種基于RSSI 的移動(dòng)節(jié)點(diǎn)改進(jìn)定位算法[J].電子技術(shù)應(yīng)用,2015,41(1):86-89.

[12] 高洪波,廖明潮.一種改進(jìn)的DV-HOP 算法在WSN 中的定位研究[J].科技通報(bào),2014,30(9):160-166.

[13] 鞏麗濤.無(wú)線傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)定位算法研究[D]. 無(wú)錫:江南大學(xué),2013.

[14] 黃小瑛.基于近似三角形內(nèi)點(diǎn)測(cè)試(APIT)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].太原:太原理工大學(xué),2010.

[15] 熊茂華,熊昕.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014.

A Non-distance Localization Algorithm Based on Perpendicular Bisector

Zou Dongyao, Li Chen, Liu Biwei

(College of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou450001,China)

Abstract:In wireless sensor network positioning schemes, APIT is widely used because it is easy, entails low hardware cost and provides high positioning accuracy. But its algorithm performance is severely affected by uneven distribution of anchors. A non-distance localization algorithm based on perpendicular bisector is proposed to improve node positioning accuracy and solve the edge effect problem of APIT. The proposed algorithm selects anchors using RSSI values and fixes the position by combining with the geometrical principle that the mid perpendicular of the base line in the isosceles triangle passes the vertex. The positioning accuracy is enhanced in this way and the stable performance is achieved. Simulation results show that the proposed algorithm can effectively improve positioning accuracy and coverage of the wireless sensor network.

Keywords:wireless sensor networks(WSNs); APIT; RSSI; positioning accuracy; localization coverage

文章編號(hào)：1671-4598(2016)02-0202-03

DOI：10.16526/j.cnki.11-4762/tp.2016.02.056

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：鄒東堯(1973-)，男，河南許昌人，博士，副教授，主要從事物聯(lián)網(wǎng)信息感知、無(wú)線傳感器節(jié)點(diǎn)定位技術(shù)方向的研究。

基金項(xiàng)目：河南省科技廳科技攻關(guān)項(xiàng)目(112102210321)；河南省產(chǎn)學(xué)研合作項(xiàng)目(122107000022)；2014年鄭州輕工業(yè)學(xué)院研究生創(chuàng)新基金項(xiàng)目。

收稿日期：2015-08-21；修回日期：2015-08-29。