胡中棟，賈方方

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

0 引 言

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

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

1 APIT 算法

1.1 基本思想

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

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

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

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

1.2 誤判分析

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

圖3 誤判情況Fig 3 Situation of misjudgment

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

2 APIT 改進算法

2.1 算法思想

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

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

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

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

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

2.2 誤判分析

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

圖5 誤判情況Fig 5 Situation of misjudgement

3 仿真實驗

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

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

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

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

4 結束語

本文首先介紹了APIT 算法的基本思想和2 種誤判情況，針對這種情況提出了一種改進的算法，利用角度求和來判斷未知節(jié)點是否位于三角形內部，經仿真實驗表明:改進算法在節(jié)點密度比較稀疏的情況下比經典算法定位誤差更小，精度更高，算法復雜度較小。當然改進算法也存在缺陷，由于測距帶來的耗能較高，也有一定誤差，但綜合分析，本算法對一些特定環(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］ 史 龍，王福豹.無線傳感器網絡Range－Free 自身定位機制與算法［J］.計算機工程與應用，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.