一種基于APIT 的無線傳感器網(wǎng)絡混合型定位算法

何登平，范茂林

(1.重慶郵電大學 通信新技術(shù)應用研究中心，重慶400065;2.重慶信科設計有限公司，重慶400065)

0 引 言

無線傳感器網(wǎng)絡(WSNs)作為一種全新的信息獲取和處理技術(shù)在目標跟蹤、入侵監(jiān)測及一些定位相關(guān)領域有廣泛的應用前景。定位作為無線傳感器網(wǎng)絡應用的基礎和關(guān)鍵技術(shù)之一，對傳感器節(jié)點明確自身位置和了解傳感器節(jié)點的位置分布狀況這兩個重要信息是非常必要的［1，2］。

無線傳感器網(wǎng)絡定位算法根據(jù)距離分類［3］，可以分為:1)基于距離(range-based)的定位算法，主要方法有:RSSI［4］，TOA［1，2］，TDOA［1，2］和AOA［1，2］等;2)與 距 離 無 關(guān)(range-free)的定位算法，常見的有:近似三角形內(nèi)點測試(approximate point in trianlge test，APIT)算法［1，2］、DV-Hop(distance vector-hop)算法［1，2］、Amorphous 算法［1］和MAP算法［2，5］等。這些算法中，APIT 定位算法是一種適用環(huán)境廣、算法復雜度低、成本低、實現(xiàn)相對容易的算法。為了提高APIT 算法的定位精度，文獻［6］提出了利用角度求和來減小未知節(jié)點是否位于三角形內(nèi)的誤判;為了提高APIT 算法在信標節(jié)點稀疏的環(huán)境下的定位覆蓋率，文獻［7］提出了一種基于RSSI 和APIT 的混合定位算法減小定位誤差和提高定位覆蓋率。

本文提出一種混合型算法，它通過減小三角形內(nèi)點測試(PIT)的三角形誤判、選擇優(yōu)良的三角形，提高了信標節(jié)點密集環(huán)境下的定位精度，并且在此基礎上，結(jié)合DV-Hop算法與兩點定位法在稀疏環(huán)境下能計算出未知節(jié)點坐標的優(yōu)點，提高了信標節(jié)點稀疏環(huán)境下的定位覆蓋率。

1 APIT 算法分析

1.1 APIT 算法基本原理

APIT 算法［1，2］的基本原理是:未知節(jié)點通過信息發(fā)送，接收在它通信半徑內(nèi)的信標節(jié)點;然后，對接收到的信標節(jié)點通過PIT，判斷未知節(jié)點是否在由任意3 個信標節(jié)點組成的三角形區(qū)域內(nèi)部，當由n 個信標節(jié)點時，就進行C3n次PIT;最后，對于未知節(jié)點位于三角形內(nèi)的區(qū)域覆蓋成一個多邊形區(qū)域，這個多邊形的質(zhì)心就作為是未知節(jié)點的位置。

1.2 APIT 算法存在的問題

1)在判斷未知節(jié)點是否在3 個信標節(jié)點組成的三角形區(qū)域內(nèi)部，容易產(chǎn)生兩個錯誤，即In-To-Out 和Out-To-In。例如:圖1(a)圖，當節(jié)點M 從實際位置1 模擬移動到位置2 時，收到來自A，B，C 的信號強度同時變?nèi)?，?jié)點M 同時遠離了A，B，C 三個點，就會判定為M 處于三角形外，即，In-To-Out error。同理，圖1(b)，當節(jié)點M 從實際位置1 模擬移動到位置2 時，根據(jù)信號強度測得節(jié)點M 就遠離了A，并同時靠近了B，C 兩點，就會判定為M 處于三角形內(nèi)，即，out-to-in error。

圖1 兩種誤判情況Fig 1 Two situations of misjudgement

2)在無線傳感器節(jié)點密集的環(huán)境下，假設未知節(jié)點的鄰居信標節(jié)點有n 個組成的集合，此時，有個三角形對未知節(jié)點進行定位，而n 取值比較大時，經(jīng)三角形判斷后，仍然存在一部分信號強度弱的PIT 節(jié)點對節(jié)點定位，每增加一個信號強度弱的三角形區(qū)域，就改變了多邊形的質(zhì)心，影響了定位精度。

3)在無線傳感器節(jié)點稀疏的環(huán)境下，當偵聽到信標節(jié)點數(shù)量小于3 時，未知節(jié)點無法定位;當偵聽到信標節(jié)點數(shù)量不小于3 時，但如果不存在PIT 三角形使未知節(jié)點位于其內(nèi)，未知節(jié)點也是無法定位的。因此，在這種信標節(jié)點稀疏的環(huán)境下APIT 算法的定位覆蓋率是很低的。

2 算法的改進

針對上述問題，結(jié)合DV-Hop 算法與兩點定位法對APIT 算法進行改進，提出了一種混合型算法，該算法的流程圖如圖2 所示。

在對信標節(jié)點進行PIT 判斷未知節(jié)點是否在由任意3 個信標節(jié)點組成的三角形區(qū)域內(nèi)部時，判斷條件在原APIT算法條件下，增加此原則［6］:通過RSSI 方法求得信標節(jié)點A，B，C 和未知節(jié)點M 這4 個節(jié)點的兩兩之間的距離，再利用三角形余弦定理求角度，若∠AMC+∠AMB+∠BMC=360°，M 位于三角形內(nèi);反之，判斷M 位于三角形外。

圖2 混合型算法流程圖Fig 2 Flow chart of mixed algorithm

在選擇優(yōu)良的三角形，除去信號強度弱的三角形，選擇原則:在信標節(jié)點密集時，設置一個門閾值P，P 為未知節(jié)點在PIT 點內(nèi)的所有三角形3 個節(jié)點的信號強度和的平均值(記三角形個數(shù)為K)，不等式左邊表示當前三角形3 個節(jié)點的信號強度之和，即限制條件公式為

在信標節(jié)點稀疏環(huán)境下，并且鄰居信標節(jié)點不小于3時，利用DV-Hop 算法［1，2］進行定位。因為它通過距離矢量路由方法計算未知節(jié)點與信標節(jié)點的最小跳數(shù)，并計算每跳的平均距離，每跳平均距離與最小跳數(shù)的乘積就作為未知節(jié)點與信標節(jié)點之間的估算距離，當存在3 個信標節(jié)點時，使用三邊測量法或最大似然估計法計算出未知節(jié)點的坐標。

只有2 個鄰居信標節(jié)點的環(huán)境下，利用兩點定位法［7］進行節(jié)點定位，它根據(jù)RSSI［4］分別測得未知節(jié)點與2 個信標節(jié)點的距離，再根據(jù)這2 個信標節(jié)點的坐標，求得未知節(jié)點的坐標。

3 仿真結(jié)果與分析

本實驗在Matlab 仿真平臺實現(xiàn)，實驗模型的特點及其參數(shù)如下:

1)無線傳感器網(wǎng)絡覆蓋范圍:1 000 m×1 000 m 的二維平面。

2)本網(wǎng)絡布放200 個傳感器節(jié)點，信標節(jié)點與未知節(jié)點是比例根據(jù)實驗參數(shù)而定，各個節(jié)點是隨機分布的，通信半徑是200 m，都具有相同的通信、感知、存儲能力。

3)此環(huán)境是理想的虛擬環(huán)境，沒有考慮外部環(huán)境對無線信號在傳播過程沒有干擾，無線信號只因距離傳播才會出現(xiàn)能量損耗。

對APIT 算法進行改進后(即減小PIT 時的三角形誤判和選擇優(yōu)良的三角形)，根據(jù)仿真結(jié)果，如圖3 所示，信標節(jié)點比例稀疏時，改進后的APIT 算法定位精度提高較小(在3%以下);隨著信標節(jié)點的增加，定位精度明顯提高(提高4%～8%左右)。整體而言，改進后的APIT 算法定位精度較大提高。

圖3 改進前后APIT 算法定位精度比較Fig 3 Localization precision comparison between APIT and improved APIT algorithm

根據(jù)混合型算法的仿真結(jié)果，如圖4 所示，在信標節(jié)點稀疏時，隨著混合型算法定位覆蓋率的增大，定位精度受到一定的影響。但隨著信標節(jié)點比例的增大，在信標節(jié)點密集環(huán)境下混合型算法的定位精度也將增大。如圖5 所示，在信標節(jié)點比例稀釋條件下，混合型算法的定位覆蓋率比APIT 算法將明顯增大。因此，這種混合型算法大大提高了信標節(jié)點稀疏環(huán)境下的定位覆蓋率。

圖4 APIT 和混合型算法定位精度比較圖Fig 4 Localization precision comparison between APIT algorithm and mixed algorithm

4 結(jié) 論

圖5 定位覆蓋率比較圖Fig 5 Localization coverage rate comparison

為了提高信標節(jié)點密集環(huán)境下的定位精度、稀疏環(huán)境下的覆蓋率，本文以APIT算法為基礎，提出了一種混合型定位算法。通過減小PIT 的三角形誤判、選擇優(yōu)良的三角形，對APIT 算法進行改進，提高了信標節(jié)點密集環(huán)境下的定位精度，并在此基礎上，根據(jù)DV-Hop 算法的優(yōu)點和兩點定位算法的特點，提高了信標節(jié)點稀疏環(huán)境下的定位覆蓋率。

［1］ 孫利民，李建中，陳 渝，等.無線傳感器網(wǎng)絡［M］.北京:清華大學出版社，2006.

［2］ 鄭 軍，張寶賢.無線傳感器網(wǎng)絡技術(shù)［M］.北京:機械工業(yè)出版社，2012:133-147.

［3］ He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks［C］∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，ACM，2003:81-95.

［4］ Sahu P K，Wu E H，Sahoo J.DuRT:Dual RSSI trend based localization for wireless sensor networks［J］.IEEE Sensors Journal，2013，13(8):3115-3123.

［5］ Ssu K F，Ou C H，Jiau H C.Localization with mobile anchor points in wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2005，54(3):1187-1197.

［6］ 胡中棟，賈方方.基于角度判斷的無線傳感器網(wǎng)絡APIT 定位算法研究［J］.傳感器與微系統(tǒng)，2013，32(1):73-75.

［7］ Chen B，Sun J，Xu W B，et al.A mixed localization algorithm based on RSSI and APIT with fitness analysis and optimization［C］∥2012 11th International Symposium on Distributed Computing and Applications to Business，Engineering＆Science(DCABES)，IEEE，2012:164-168.