基于角度判斷的無線傳感器網(wǎng)絡(luò)APIT 定位算法研究*

胡中棟，賈方方

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000)

0 引 言

在無線傳感器研究領(lǐng)域中傳感器節(jié)點(diǎn)定位是一項基本技術(shù)［1］。根據(jù)是否測量節(jié)點(diǎn)間的距離，節(jié)點(diǎn)定位分為2 類［2］:測距與非測距。后者成本小，能耗低，適用于大規(guī)模環(huán)境中，應(yīng)用前景較好，但在定位精度上不及前者?；诜菧y距的經(jīng)典算法有 DV－Hop［3］、質(zhì)心算法［4］、近似三角形內(nèi)點(diǎn)測試(APIT)［5］等。APIT 算法在節(jié)點(diǎn)密度比較高的情況下有較好的定位性能，可以得到比較滿意的精度，成本比較低，實現(xiàn)也比較容易。但是如果在隨機(jī)分布的網(wǎng)絡(luò)環(huán)境中，節(jié)點(diǎn)密度相對稀疏的情況下，誤差較大。

基于以上研究，本文選擇在節(jié)點(diǎn)密度比較稀疏的情況下利用角度求和判斷對APIT 算法進(jìn)行了進(jìn)一步改進(jìn)，改進(jìn)算法可以盡量避免出現(xiàn)未知節(jié)點(diǎn)誤判的情況，以提高定位精度，減小定位誤差。本文中稱已知節(jié)點(diǎn)為錨節(jié)點(diǎn)，待定位節(jié)點(diǎn)稱為未知節(jié)點(diǎn)。

1 APIT 算法

1.1 基本思想

APIT 算法是由He T 等人在2003 年提出的一種算法。這種算法的基本思想就是未知節(jié)點(diǎn)可以在其通信半徑內(nèi)監(jiān)聽自己鄰居錨節(jié)點(diǎn)的信息，假設(shè)未知節(jié)點(diǎn)周圍鄰居錨節(jié)點(diǎn)個數(shù)為m 個，那么，從這m 個錨節(jié)點(diǎn)中任選3 個組成1 個三角形，共有C3m種組合，然后采用三角形內(nèi)點(diǎn)測試(PIT)法，判斷未知節(jié)點(diǎn)是否位于每一個三角形中，窮盡所有組合，最后取所有包括未知節(jié)點(diǎn)三角形重合區(qū)域?qū)ζ淝筚|(zhì)心，即認(rèn)為此質(zhì)心為未知節(jié)點(diǎn)的位置坐標(biāo)，如圖1 中的陰影部分則是三角形的重合區(qū)域，對此不規(guī)則多邊形求質(zhì)心，即可得到估計位置坐標(biāo)。

圖1 APIT 算法定位原理Fig 1 APIT algorithm positioning principle

APIT 算法的基本理論基礎(chǔ)是PIT，它是在較高的節(jié)點(diǎn)密度的網(wǎng)絡(luò)環(huán)境中模擬節(jié)點(diǎn)移動，即未知節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間相互交換信息，通過比較無線信號的強(qiáng)度大小來判斷是否遠(yuǎn)離或靠近錨節(jié)點(diǎn)。PIT 基本思想是:如圖2 所示，當(dāng)節(jié)點(diǎn)向某一方向移動一定距離，如果它同時遠(yuǎn)離或同時接近三角形的3 個頂點(diǎn)，則判斷此節(jié)點(diǎn)位于三角形外部(圖2(b))，否則，判斷在三角形內(nèi)部(圖2(a))。

圖2 模擬節(jié)點(diǎn)移動圖Fig 2 Moving diagram of simulated node

1.2 誤判分析

由于APIT 算法只能判定有限方向，與鄰居節(jié)點(diǎn)的位置密切相關(guān)，所以容易出現(xiàn)誤判情況。如圖3 所示，D 是未知節(jié)點(diǎn)N 的鄰居節(jié)點(diǎn)。圖3(a)所示是未知節(jié)點(diǎn)誤判在外部(in－to－out error)的情況，圖3(b)所示是未知節(jié)點(diǎn)誤判在內(nèi)部(out－to－in error)的情況。

圖3 誤判情況Fig 3 Situation of misjudgment

出現(xiàn)上面2 種錯誤判斷主要是由于節(jié)點(diǎn)密度較低或其他一些特殊原因造成，因為PIT 測試方法對鄰居節(jié)點(diǎn)的依賴性很高，雖然算法復(fù)雜度較低，性能穩(wěn)定，但是在節(jié)點(diǎn)相對稀疏的情況下，誤判在外部和誤判在內(nèi)部是造成算法誤差較大的一個重要原因，所以，對APIT 算法進(jìn)行改進(jìn)是非常有必要的。

2 APIT 改進(jìn)算法

2.1 算法思想

根據(jù)文獻(xiàn)［5］可知，APIT 算法對節(jié)點(diǎn)密度要求較高，因為未知節(jié)點(diǎn)需要和鄰居節(jié)點(diǎn)交換信息來判斷是否在三角形內(nèi)部，如果在節(jié)點(diǎn)密度比較稀疏的情況下，未知節(jié)點(diǎn)周圍可能沒有鄰居節(jié)點(diǎn)，或者是距離較遠(yuǎn)，就很容易出現(xiàn)如圖2、圖3 中的2 種誤判情況。

針對此類誤判情況，本文提出一種改進(jìn)算法，利用角度求和來判斷未知節(jié)點(diǎn)是否位于三角形內(nèi)部。如圖4 所示，D 為未知節(jié)點(diǎn)，圖4(a)所示的是D 節(jié)點(diǎn)在三角形內(nèi)部的情況，從圖中可以看出:∠ADB + ∠ADC + ∠BDC =360°，而圖4(b)所示的是D 節(jié)點(diǎn)在三角形外部的情況，從圖中可以看出4 個點(diǎn)組成一個四邊形，那么，∠ADC + ∠BDC =∠ADB ＜180°，從而推出∠ADC + ∠BDC + ∠ADB ＜ 360°。反之，通過求得未知節(jié)點(diǎn)與三角形頂點(diǎn)連接的三角之和是否為3 60°就可以判斷出未知節(jié)點(diǎn)位于三角形內(nèi)部還是三角形外部。本文改進(jìn)算法與經(jīng)典算法比較，最大的優(yōu)勢是在判斷未知節(jié)點(diǎn)位置時節(jié)點(diǎn)本身就可以進(jìn)行判斷，而不需要與鄰居節(jié)點(diǎn)進(jìn)行信息交換。

圖4 角度求和原理圖Fig 4 Principle diagram of summation of angle

通過算法分析，首先采用RSSI［6］算法求得節(jié)點(diǎn)間距離，利用已知發(fā)射信號強(qiáng)度，接收節(jié)點(diǎn)根據(jù)收到的信號強(qiáng)度，計算信號在傳播過程中的損耗，使用理論或經(jīng)驗的信號傳播模型將傳播損耗轉(zhuǎn)換為距離。其次，求出角度，也是本算法關(guān)鍵點(diǎn)。假設(shè)已知三角形AB，AC 和BC 三邊的長度，由三角形余弦定理得

利用反余弦即可以得出∠ABC 的值。如圖4 所示，利用此原理分別可以求得∠ADB，∠ADC 和∠BDC 的值，計算三角之和，如果三角之和近似等于360°，判定該未知節(jié)點(diǎn)在三角形內(nèi)，如果三角之和小于360°，判定該未知節(jié)點(diǎn)在三角形外?，F(xiàn)實環(huán)境中由于測量誤差和求反余弦時會有一定偏差，根據(jù)分析與實驗，如果三角之和在360° ±20°范圍內(nèi)，就認(rèn)為是在三角形內(nèi)。

2.2 誤判分析

雖然改進(jìn)算法避免了依靠與鄰居節(jié)點(diǎn)相互交換信息來進(jìn)行判斷，減少了誤判在外部和誤判在內(nèi)部2 種誤判情況，但是，當(dāng)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)重合的時候這種算法就會出現(xiàn)誤判，通過觀察圖5，如果D 節(jié)點(diǎn)與A 節(jié)點(diǎn)重合，那么它就是三角形頂點(diǎn)，算法就會失效。另一種情況就是，當(dāng)D 節(jié)點(diǎn)非常接近三角形一條邊時，∠ADB 幾乎等于180°，所以，三角之和非常接近于360°，就有可能將未知節(jié)點(diǎn)誤判在三角形內(nèi)部。再出現(xiàn)誤判的情況下，未知節(jié)點(diǎn)也已非常接近三角形一邊，定位誤差會相對較小，對定位影響較小。

圖5 誤判情況Fig 5 Situation of misjudgement

3 仿真實驗

采用Matlab 7.1 進(jìn)行仿真，實驗環(huán)境設(shè)定在一個二維平面50 m ×50 m 范圍內(nèi)，通信半徑設(shè)定為30 m，測量距離設(shè)定最大為10 %的隨機(jī)誤差，節(jié)點(diǎn)隨機(jī)分布，平均運(yùn)行50 次。由于本文選擇在節(jié)點(diǎn)稀疏環(huán)境下比較改進(jìn)算法與經(jīng)典算法的誤差，所以，選擇組節(jié)點(diǎn):第一組錨節(jié)點(diǎn)為15 個，未知節(jié)點(diǎn)為20 個;第二組錨節(jié)點(diǎn)為20 個，未知節(jié)點(diǎn)為35 個。

圖6(a)，(b)分別是對2 組節(jié)點(diǎn)運(yùn)行50 次得出的相對誤差曲線圖。

圖6 誤差比較圖Fig 6 Error comparison diagram

分析數(shù)據(jù)可以得出，在節(jié)點(diǎn)相對稀疏的情況下，經(jīng)典算法即使大部分可以被定位，但誤差太大，這是由于誤判而造成的;改進(jìn)算法雖然有些節(jié)點(diǎn)不能被定位，但是比例較少，誤差相對較小，定位精度比較高。隨著節(jié)點(diǎn)密度增加，改進(jìn)算法中不能被定位的節(jié)點(diǎn)比例下降。在稀疏環(huán)境下改進(jìn)算法比經(jīng)典算法誤差更小，精度更高。

4 結(jié)束語

本文首先介紹了APIT 算法的基本思想和2 種誤判情況，針對這種情況提出了一種改進(jìn)的算法，利用角度求和來判斷未知節(jié)點(diǎn)是否位于三角形內(nèi)部，經(jīng)仿真實驗表明:改進(jìn)算法在節(jié)點(diǎn)密度比較稀疏的情況下比經(jīng)典算法定位誤差更小，精度更高，算法復(fù)雜度較小。當(dāng)然改進(jìn)算法也存在缺陷，由于測距帶來的耗能較高，也有一定誤差，但綜合分析，本算法對一些特定環(huán)境下還是有很大實用價值的。

［1］ Mechitov K，Sundresh S，Kwon Y，et al.Cooperative tracking with binary detection sensor networks［C］∥Proceedings of the 1st Intemational Conference on Embedded Networked Sen－sor Systems，New York:ACM Press，2003:332 －333.

［2］ 史 龍，王福豹.無線傳感器網(wǎng)絡(luò)Range－Free 自身定位機(jī)制與算法［J］.計算機(jī)工程與應(yīng)用，2004，40(23):127 －151.

［3］ Nieolescu D，Nath B.Ad Hoc positioning systems(APS)［C］∥Proc of the 2001 IEEE Conf on Global Telecommunications，San Antonio:IEEE Communications Society，2001:2926 － 2931.

［4］ 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.

［5］ He Tian，Huang Chengdu，Blum B M，et a1.Range－free localization schemes in large scale sensor networks［C］∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，MOBICOM’2003，San Diego，CA，USA，2003:81 －95.

［6］ Luthy K A，Egrant D，Henderson T C.Leveraging RSSI for robtic repair of disconnc－ted wireless sensor networks［C］∥Prodeedings of 2007 IEEE International Conference on Robotics and Automation，Rome，Italy，2007:10 －14.