基于改進APIT算法的無線傳感器網絡節點定位*

戴天虹, 李　昊

(東北林業大學 機電工程學院，黑龍江 哈爾濱 150040)

?

基于改進APIT算法的無線傳感器網絡節點定位*

戴天虹, 李昊

(東北林業大學 機電工程學院，黑龍江 哈爾濱 150040)

摘要:定位技術是無線傳感器網絡中一個比較重要的技術。近似三角形內點測試(APIT)算法是一種比較常用的算法，為了提高無線傳感器網絡(WSNs)定位精度，在APIT算法的基礎上進行改進，將三角形進行中垂線分割成4個或者6個小區間，通過對各個節點接收到目標節點信號強度進行比較，判斷目標節點位于哪一個小區域內。通過仿真可以得到，改進的APIT算法精度上有了很大的提高。

關鍵詞：無線傳感器網絡； 近似三角形內點測試算法； 節點定位； 中垂線分割

0引言

無線傳感器網絡(WSNs)具有著低成本、低損耗的特點，能夠在惡劣的環境下進行數據的采集和收發,目前正在快速發展[1]。

傳感器的定位問題是無線傳感器網絡中的一項非常重要的技術，多種無線傳感器網絡節點定位算法已經提出。通過對節點位置估測機制的不同可分為兩類：基于距離的定位算法和距離無關的定位算法[2]。前者需要知道兩個相鄰節點之間的絕對距離和方位，根據節點之間的實際距離來確定未知節點的坐標；后者需要知道未知節點和錨節點之間的連通能力來估算出和錨節點之間的距離[3]。前者的精確度比較高，后者只能估算出節點的大致位置。其中，與距離無關的定位算法由于能夠減少節點的能量消耗，并且延長整個網路的生命周期而得到了廣泛的研究和應用。典型的算法有：DV-Hop、質心定位、近似三角形內點(approximate point-in-triangulation,APIT)測試定位等。

本文定位采用APIT定位算法，并針對該算法定位中的不足提出改進的APIT定位算法，提高定位的精度，對改進的定位算法進行仿真，并對仿真結果進行了分析[4]。

1APIT算法

1.1APIT算法的基本原理

圖1　APIT定位原理圖Fig 1　Principle diagram of APIT positioning

APIT算法的最重要的部分是確定未知節點位于三角形的內部還是外部。對此，可以采用最佳三角形內點[5](perfect point-in-triang-ulation，PIT) 測試算法來判斷該未知節點是否位于三角形的內部。圖2表示的是具體的PIT算法原理。

圖2　PIT原理示意圖Fig 2　PIT principle diagram

A,B,C為三角形的三個頂點，M為需要確認的未知節點。讓M點向任意的方向發生移動，若M點在運動過程中，存在一個點，在向該點移動時，M點離A,B,C的距離是同時增大或者減小的，那么,點M位于三角形的外部;反之，M位于三角形的內部，這就是PIT原理[6]。

1.2改進的APIT算法

在整個無線傳感器網絡的邊緣地區，傳感器的數量相對來說比較少，錨節點較少，這樣組成的三角形的數量也會降低。在進行PIT算法進行定位時，會出現由于重疊區域過大造成實際位置與定位位置偏差過大的現象。圖3所示的是運用APIT定位誤差較大的一種情況。

圖3　APIT定位誤差Fig 3　APIT positioning error

為了提高無線傳感器網絡的定位精度，提出一種改進的APIT算法[7]。改進的APIT算法是根據錨節點接收到未知節點的信號強度的變化來作為依據所實現的。如圖2左圖所示，目標節點在向1方向移動的過程中，可用三角形3個錨節點接收到的信號強度會發生變化，A錨節點接收到的信號強度會越來越大，B,C目標節點接收到的信號強度會越來越小。

改進的APIT算法是縮小未知節點M在三角形內的區域范圍，提高節點的定位精度。具體實現是將三角形進行分割。對三角形進行中垂線分割，那么,三角形將會被進一步分割成幾個小區間。由三角形中垂線分割可知，銳角三角形會被分割成6個小區域，直角三角形和鈍角三角形會被分割成4個小區域[8]。圖4(a),(b),(c)分別為銳角三角形、直角三角形和鈍角三角形中垂線分割圖。

圖4　三角形中垂分割線Fig 4　Perpendicular segmentation of three kinds of triangles

由圖4可知，經分割后，三角形被分割成三角形、四邊形、五邊形三種小區間。通過對三角形3個錨節點A,B,C接收到未知節點的信號強度的比較可以判斷出未知節點位于分割后的哪個小區間內[9]。

以圖4(a)銳角三角形中垂線分割為例,通過對A,B,C三點接收到位置節點M發出的信號強度進行比較，若A點接收到的信號強度大于B點和C點接收到的信號強度，并且B點接收到的信號強度大于C點接收到的信號強度，那么,未知節點位于分割小區域1,2,3,4,5,6中的小區域6內，6即為可用小區域。若A點接收到信號強度大于B,C兩點接收到的信號強度，B點接收到的信號強度等于C點接收到的信號強度，那么,未知節點位于BC的中垂線上，在這種情況下，可以選擇1,6這2個小區組成的共同區域作為可用小區域[10]。

對所有的可用三角形進行分割，則有多少個可用三角形就有多少個可用小區域。找出所有可用小區域的重疊部分，求出重疊區域的質心位置，將質心位置作為未知節點的估計位置[11]。

1)改進的APIT算法與APIT算法相似，首先需要知道目標節點周圍所有錨節點的信息，包括錨節點的位置和錨節點接收到目標節點的信號強度大小。

2)所有能夠和目標節點進行信息通信的錨節點組成錨節點集。任意選取3個錨節點組成三角形，判斷目標節點位于三角形的內部還是外部。已知三個錨節點接收到目標的信號強度大小，若存在一個點，該點接收到的三角形3個錨節點的信號強度比目標節點接收到的信號強度均大于或者小于，那么，該目標節點位于三角形的外部；否則，目標節點位于三角形的內部。

3)選出所有包含目標節點的三角形，將三角形進行中垂線分割，則將三角形分成四部分或者六部分。若三角形為銳角三角形，則被分割成6個小區間，若三角形為直角三角形或者鈍角三角形，則被分割成4個小區間。通過對 3個錨節點接收到的目標節點發出的信號的強度大小進行比較，確定目標節點位于哪一個小區間內。

4)找出所有小區間的重疊區域，并且求出重疊區域的質心位置，將該質心位置作為目標節點的位置。改進APIT算法的流程圖如圖5所示。

2仿真研究

2.1仿真環境與參數設置

本文用VC來進行仿真驗證，并采用無線傳感器網絡定位技術仿真，主要方法是將100，200，300個點隨機分布在一個100 m×100 m的區域內，在仿真中分別加入APIT和改進的APIT算法，通過對平均誤差的比較，驗證改進算法的可行性。

在仿真過程中，節點是隨機分布在該區域內的。錨節點的密度從1 %開始慢慢增大，得出不同的錨節點密度下的平均誤差。平均誤差是由定位誤差和通信半徑之比得到[12]。定位誤差即為定位的位置和節點真實的位置差。通常，錨節點的數量越少，定位的難度就會越大，定位的精度就會越小，平均誤差就會越大。

圖5　算法流程圖Fig 5　Algorithm flow chart

在實驗過程中，目標節點周圍錨節點的數量不同，會出現以下四種情況:

1)目標節點不能接收到任何錨節點發出的信號時，將該區域的中心位置作為定位點[13]。

2)目標節點只能接收到1個錨節點發出的信號時，將該錨節點作為定位點。

3)目標節點只能接收到2個錨節點發出的信號時，將兩點的中間位置作為定位點。

4)目標節點能夠接收到3個及其以上錨節點發出的信號時，若目標節點位于組成的三角形外部，則取該三角形的質心作為定位點。若位于三角形的內部，則采用APIT算法和改進的APIT算法分別進行定位得出定位點。

2.2仿真結果

圖6為總節點數分別為100，200，300時的定位誤差。

圖6　不同總節點數時的定位誤差Fig 6　Positioning error of different total number of nodes

由圖6可知，APIT算法和改進的APIT算法都隨著錨節點密度的增加定位的精度也不斷提高。在整個過程中，出現以下三種情況:

1)在錨節點密度比較低時，由于許多目標節點不能夠接收到錨節點發出的信息，定位的精度比較低。APIT算法和改進的APIT算法都有著較高的定位誤差，曲線幾乎是重合的。

2)隨著錨節點密度的逐漸增大，目標節點接收到的錨節點的信息強度和數量都在不斷增大，此時，APIT算法開始發揮作用，錨節點組成的可用三角形的數量也在不斷地增多，平均誤差不斷減小。未知節點的定位精度也在不斷提高。但改進的APIT算法的平均誤差要小于APIT算法，改進APIT算法的定位精度要高于APIT算法[14]。

3)當錨節點的密度達到一定程度之后，改進的APIT算法和APIT算法定位精度逐漸趨向穩定，但改進的APIT算法仍然優于APIT算法。

圖7表示的改進的APIT算法相對于APIT算法定位精度提高百分比。從圖中可以看出，改進的APIT算法比APIT算法的定位精度是先增加后減小的。出現這種情況的原因是因為整個區域中的錨節點數量較少時，兩種算法都不能夠起到作用，精確度都比較低。隨著錨節點的數量不斷增多，兩種算法都開始發揮作用，但改進的APIT算法精確度要遠遠高于APIT算法導致曲線開始上升。最后，由于錨節點慢慢趨于飽和，可用三角形的數量也在不斷增加，兩種算法的精確度都比較高，導致定位精度提高百分比開始下降。從圖中還可以看出，在100 m×100 m的區域中，當區域中節點的數目為40個時，改進的算法提高精度的幅度最大。整體來說，改進的APIT算法有著比APIT算法較高的精度，定位的更加精確。

圖7　改進的APIT相對于APIT算法定位精度提高Fig 7　Improvement of positioning precision improvedAPIT relative to APIT algorithm

3結論

改進的APIT算法適用于設施比較簡單的情況。其主要思想就是在APIT算法的基礎上，將三角形進行中垂線分割，分割成四部分或者六部分，通過對錨節點接收到的目標節點的信號強度大小的比較，確定目標節點位于三角形的哪一個小區域，求出所有可用小區域重疊部分的質心位置，將該點作為目標節點的定位位置。仿真發現：改進的APIT算法比APIT算法在錨節點數量不算太多的情況下定位精度有所提高，隨著錨節點數量的增加，定位精度提高的更快。

參考文獻:

[1]彭勇.無線傳感器網絡中能量高效的目標跟蹤協議研究[D].長沙:中南大學,2009.

[2]周祖德，王晟.一種適用于復雜環境的無線傳感定位算法[J].武漢理工大學學報,2006,15(11):121-124.

[3]薛霞，孫勇.監測煤礦的一種無線傳感器網絡節點定位算法[J].傳感器與微系統,2010,29(9):119-121.

[4]盧迪，劉世琦.無線傳感網絡改進APIT定位算法[J].哈爾濱理工大學學報,2014,16(4):95-99.

[5]Liu Yu,Yi Xiao,He You.A novel centroid localization for wireless sensor networks[C]∥International Conf on Distributed Sensor Networks,ACM,2012:689-694.

[6]何登平,范茂林.一種基于APIT的無線傳感器網絡混合型定位算法[J].傳感器與微系統,2015,34(2):133-135.

[7]王亞子，楊建輝.改進粒子群算法的無線傳感器網絡節點定位[J].計算機工程與應用,2014(18):99-102.

[8]楊驥，劉鋒.無線傳感器網絡基于中垂線分割的APIT的改進定位算法[J].傳感技術學報,2008,23(8):1453-1457.

[9]Sheng Xiaohong,Yu Henhu.Sequential acoustic energy based source localization using particle filter in a distributed sensor network[C]∥IEEE International Conference on Acoustics,Speech,and Signal Processing，Piscataway,USA:IEEE,2004:961-972.

[10] 謝國新，李新.短波干擾有效壓制距離的計算方法[J].航天電子對抗,2005,2(1):53-55.

[11] 曹磊,徐晨.無線傳感器網絡近似三角形內點測試定位算法改進[J].電子技術應用,2007(11):80-82.

[12] 李琳.基于WSNs的非測距定位算法研究[D].天津:天津工業大學,2014.

[13] 祁會波.無線傳感器網絡中基于移動錨節點的定位算法研究[D].太原:太原理工大學,2006.

[14] 張驍航.基于跳距誤差修正和粒子群優化的無線傳感器網絡定位算法研究[D].重慶: 重慶郵電大學,2012.

戴天虹(1963-)，男，黑龍江哈爾濱人，博士，教授，主要從事林業工程自動化等方面的教學與科研工作。

Node localization of wireless sensor networks based on improved APIT algorithm*

DAI Tian-hong, LI Hao

(School of Mechanical and Electrical Engineering,Northeast Forestry University, Harbin 150040，China)

Abstract:Localization technology is a very important technology in wireless sensor networks(WSNs).Approximate point-in-triangulation(APIT)test algorithm is a common algorithm,in order to improve positioning precision,improvement is carried out on the basis of the algorithm,triangle perpendicular bisector is divided into four or six quarters,through comparing target node signal intensity received by each node,judge which small area is target node located in.By simulation,the improved APIT algorithm can be improved greatly in precision.

Key words:wireless sensor networks(WSNs); approximate point-in-triangulation(APIT)test algorithm; node localization; midperpendicular segmentation

作者簡介:

中圖分類號：TN 926

文獻標識碼：A

文章編號：1000—9787(2016)01—0135—04

*基金項目：哈爾濱市科技創新人才(優秀學科帶頭人計劃類)基金資助項目(2014RFXXJ086)

收稿日期：2015—11—09

DOI:10.13873/J.1000—9787(2016)01—0135—04