鄒東堯，李　晨，劉碧微

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

?

基于垂直平分線的非測距定位算法

鄒東堯，李晨，劉碧微

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

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

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

0引言

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

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

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

1APIT算法存在的問題

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

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

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

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

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

2PB算法

2.1算法描述

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

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

圖1　PB定位算法

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

圖2　垂直平分線平行

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

圖3　錨節(jié)點距離過近

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

(1)

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

(2)

2.2算法步驟

2.2.1提取信息

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

(3)

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

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

(4)

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

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

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

3算法仿真與分析

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

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

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

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

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

3.2定位精度和覆蓋率

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

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

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

圖6　定位覆蓋率比較圖

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

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

4結(jié)束語

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

參考文獻：

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

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

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

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

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

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

[7] 何中勝,朱宇光,莊燕濱.無線傳感器網(wǎng)絡(luò)中覆蓋控制技術(shù)綜述[J].計算機測量與控制,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 的移動節(jié)點改進定位算法[J].電子技術(shù)應(yīng)用,2015,41(1):86-89.

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

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

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

[15] 熊茂華,熊昕.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].西安:西安電子科技大學出版社,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

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

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

中圖分類號：TP393

文獻標識碼：A

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

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

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