基于改進(jìn)APIT算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位*

戴天虹, 李　昊

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040)

?

基于改進(jìn)APIT算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位*

戴天虹, 李昊

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040)

摘要:定位技術(shù)是無線傳感器網(wǎng)絡(luò)中一個(gè)比較重要的技術(shù)。近似三角形內(nèi)點(diǎn)測(cè)試(APIT)算法是一種比較常用的算法，為了提高無線傳感器網(wǎng)絡(luò)(WSNs)定位精度，在APIT算法的基礎(chǔ)上進(jìn)行改進(jìn)，將三角形進(jìn)行中垂線分割成4個(gè)或者6個(gè)小區(qū)間，通過對(duì)各個(gè)節(jié)點(diǎn)接收到目標(biāo)節(jié)點(diǎn)信號(hào)強(qiáng)度進(jìn)行比較，判斷目標(biāo)節(jié)點(diǎn)位于哪一個(gè)小區(qū)域內(nèi)。通過仿真可以得到，改進(jìn)的APIT算法精度上有了很大的提高。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； 近似三角形內(nèi)點(diǎn)測(cè)試算法； 節(jié)點(diǎn)定位； 中垂線分割

0引言

無線傳感器網(wǎng)絡(luò)(WSNs)具有著低成本、低損耗的特點(diǎn)，能夠在惡劣的環(huán)境下進(jìn)行數(shù)據(jù)的采集和收發(fā),目前正在快速發(fā)展[1]。

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

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

1APIT算法

1.1APIT算法的基本原理

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

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

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

A,B,C為三角形的三個(gè)頂點(diǎn)，M為需要確認(rèn)的未知節(jié)點(diǎn)。讓M點(diǎn)向任意的方向發(fā)生移動(dòng)，若M點(diǎn)在運(yùn)動(dòng)過程中，存在一個(gè)點(diǎn)，在向該點(diǎn)移動(dòng)時(shí)，M點(diǎn)離A,B,C的距離是同時(shí)增大或者減小的，那么,點(diǎn)M位于三角形的外部;反之，M位于三角形的內(nèi)部，這就是PIT原理[6]。

1.2改進(jìn)的APIT算法

在整個(gè)無線傳感器網(wǎng)絡(luò)的邊緣地區(qū)，傳感器的數(shù)量相對(duì)來說比較少，錨節(jié)點(diǎn)較少，這樣組成的三角形的數(shù)量也會(huì)降低。在進(jìn)行PIT算法進(jìn)行定位時(shí)，會(huì)出現(xiàn)由于重疊區(qū)域過大造成實(shí)際位置與定位位置偏差過大的現(xiàn)象。圖3所示的是運(yùn)用APIT定位誤差較大的一種情況。

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

為了提高無線傳感器網(wǎng)絡(luò)的定位精度，提出一種改進(jìn)的APIT算法[7]。改進(jìn)的APIT算法是根據(jù)錨節(jié)點(diǎn)接收到未知節(jié)點(diǎn)的信號(hào)強(qiáng)度的變化來作為依據(jù)所實(shí)現(xiàn)的。如圖2左圖所示，目標(biāo)節(jié)點(diǎn)在向1方向移動(dòng)的過程中，可用三角形3個(gè)錨節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度會(huì)發(fā)生變化，A錨節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度會(huì)越來越大，B,C目標(biāo)節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度會(huì)越來越小。

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

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

由圖4可知，經(jīng)分割后，三角形被分割成三角形、四邊形、五邊形三種小區(qū)間。通過對(duì)三角形3個(gè)錨節(jié)點(diǎn)A,B,C接收到未知節(jié)點(diǎn)的信號(hào)強(qiáng)度的比較可以判斷出未知節(jié)點(diǎn)位于分割后的哪個(gè)小區(qū)間內(nèi)[9]。

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

對(duì)所有的可用三角形進(jìn)行分割，則有多少個(gè)可用三角形就有多少個(gè)可用小區(qū)域。找出所有可用小區(qū)域的重疊部分，求出重疊區(qū)域的質(zhì)心位置，將質(zhì)心位置作為未知節(jié)點(diǎn)的估計(jì)位置[11]。

1)改進(jìn)的APIT算法與APIT算法相似，首先需要知道目標(biāo)節(jié)點(diǎn)周圍所有錨節(jié)點(diǎn)的信息，包括錨節(jié)點(diǎn)的位置和錨節(jié)點(diǎn)接收到目標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度大小。

2)所有能夠和目標(biāo)節(jié)點(diǎn)進(jìn)行信息通信的錨節(jié)點(diǎn)組成錨節(jié)點(diǎn)集。任意選取3個(gè)錨節(jié)點(diǎn)組成三角形，判斷目標(biāo)節(jié)點(diǎn)位于三角形的內(nèi)部還是外部。已知三個(gè)錨節(jié)點(diǎn)接收到目標(biāo)的信號(hào)強(qiáng)度大小，若存在一個(gè)點(diǎn)，該點(diǎn)接收到的三角形3個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度比目標(biāo)節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度均大于或者小于，那么，該目標(biāo)節(jié)點(diǎn)位于三角形的外部；否則，目標(biāo)節(jié)點(diǎn)位于三角形的內(nèi)部。

3)選出所有包含目標(biāo)節(jié)點(diǎn)的三角形，將三角形進(jìn)行中垂線分割，則將三角形分成四部分或者六部分。若三角形為銳角三角形，則被分割成6個(gè)小區(qū)間，若三角形為直角三角形或者鈍角三角形，則被分割成4個(gè)小區(qū)間。通過對(duì) 3個(gè)錨節(jié)點(diǎn)接收到的目標(biāo)節(jié)點(diǎn)發(fā)出的信號(hào)的強(qiáng)度大小進(jìn)行比較，確定目標(biāo)節(jié)點(diǎn)位于哪一個(gè)小區(qū)間內(nèi)。

4)找出所有小區(qū)間的重疊區(qū)域，并且求出重疊區(qū)域的質(zhì)心位置，將該質(zhì)心位置作為目標(biāo)節(jié)點(diǎn)的位置。改進(jìn)APIT算法的流程圖如圖5所示。

2仿真研究

2.1仿真環(huán)境與參數(shù)設(shè)置

本文用VC來進(jìn)行仿真驗(yàn)證，并采用無線傳感器網(wǎng)絡(luò)定位技術(shù)仿真，主要方法是將100，200，300個(gè)點(diǎn)隨機(jī)分布在一個(gè)100 m×100 m的區(qū)域內(nèi)，在仿真中分別加入APIT和改進(jìn)的APIT算法，通過對(duì)平均誤差的比較，驗(yàn)證改進(jìn)算法的可行性。

在仿真過程中，節(jié)點(diǎn)是隨機(jī)分布在該區(qū)域內(nèi)的。錨節(jié)點(diǎn)的密度從1 %開始慢慢增大，得出不同的錨節(jié)點(diǎn)密度下的平均誤差。平均誤差是由定位誤差和通信半徑之比得到[12]。定位誤差即為定位的位置和節(jié)點(diǎn)真實(shí)的位置差。通常，錨節(jié)點(diǎn)的數(shù)量越少，定位的難度就會(huì)越大，定位的精度就會(huì)越小，平均誤差就會(huì)越大。

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

在實(shí)驗(yàn)過程中，目標(biāo)節(jié)點(diǎn)周圍錨節(jié)點(diǎn)的數(shù)量不同，會(huì)出現(xiàn)以下四種情況:

1)目標(biāo)節(jié)點(diǎn)不能接收到任何錨節(jié)點(diǎn)發(fā)出的信號(hào)時(shí)，將該區(qū)域的中心位置作為定位點(diǎn)[13]。

2)目標(biāo)節(jié)點(diǎn)只能接收到1個(gè)錨節(jié)點(diǎn)發(fā)出的信號(hào)時(shí)，將該錨節(jié)點(diǎn)作為定位點(diǎn)。

3)目標(biāo)節(jié)點(diǎn)只能接收到2個(gè)錨節(jié)點(diǎn)發(fā)出的信號(hào)時(shí)，將兩點(diǎn)的中間位置作為定位點(diǎn)。

4)目標(biāo)節(jié)點(diǎn)能夠接收到3個(gè)及其以上錨節(jié)點(diǎn)發(fā)出的信號(hào)時(shí)，若目標(biāo)節(jié)點(diǎn)位于組成的三角形外部，則取該三角形的質(zhì)心作為定位點(diǎn)。若位于三角形的內(nèi)部，則采用APIT算法和改進(jìn)的APIT算法分別進(jìn)行定位得出定位點(diǎn)。

2.2仿真結(jié)果

圖6為總節(jié)點(diǎn)數(shù)分別為100，200，300時(shí)的定位誤差。

圖6　不同總節(jié)點(diǎn)數(shù)時(shí)的定位誤差Fig 6　Positioning error of different total number of nodes

由圖6可知，APIT算法和改進(jìn)的APIT算法都隨著錨節(jié)點(diǎn)密度的增加定位的精度也不斷提高。在整個(gè)過程中，出現(xiàn)以下三種情況:

1)在錨節(jié)點(diǎn)密度比較低時(shí)，由于許多目標(biāo)節(jié)點(diǎn)不能夠接收到錨節(jié)點(diǎn)發(fā)出的信息，定位的精度比較低。APIT算法和改進(jìn)的APIT算法都有著較高的定位誤差，曲線幾乎是重合的。

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

3)當(dāng)錨節(jié)點(diǎn)的密度達(dá)到一定程度之后，改進(jìn)的APIT算法和APIT算法定位精度逐漸趨向穩(wěn)定，但改進(jìn)的APIT算法仍然優(yōu)于APIT算法。

圖7表示的改進(jìn)的APIT算法相對(duì)于APIT算法定位精度提高百分比。從圖中可以看出，改進(jìn)的APIT算法比APIT算法的定位精度是先增加后減小的。出現(xiàn)這種情況的原因是因?yàn)檎麄€(gè)區(qū)域中的錨節(jié)點(diǎn)數(shù)量較少時(shí)，兩種算法都不能夠起到作用，精確度都比較低。隨著錨節(jié)點(diǎn)的數(shù)量不斷增多，兩種算法都開始發(fā)揮作用，但改進(jìn)的APIT算法精確度要遠(yuǎn)遠(yuǎn)高于APIT算法導(dǎo)致曲線開始上升。最后，由于錨節(jié)點(diǎn)慢慢趨于飽和，可用三角形的數(shù)量也在不斷增加，兩種算法的精確度都比較高，導(dǎo)致定位精度提高百分比開始下降。從圖中還可以看出，在100 m×100 m的區(qū)域中，當(dāng)區(qū)域中節(jié)點(diǎn)的數(shù)目為40個(gè)時(shí)，改進(jìn)的算法提高精度的幅度最大。整體來說，改進(jìn)的APIT算法有著比APIT算法較高的精度，定位的更加精確。

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

3結(jié)論

改進(jìn)的APIT算法適用于設(shè)施比較簡(jiǎn)單的情況。其主要思想就是在APIT算法的基礎(chǔ)上，將三角形進(jìn)行中垂線分割，分割成四部分或者六部分，通過對(duì)錨節(jié)點(diǎn)接收到的目標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度大小的比較，確定目標(biāo)節(jié)點(diǎn)位于三角形的哪一個(gè)小區(qū)域，求出所有可用小區(qū)域重疊部分的質(zhì)心位置，將該點(diǎn)作為目標(biāo)節(jié)點(diǎn)的定位位置。仿真發(fā)現(xiàn)：改進(jìn)的APIT算法比APIT算法在錨節(jié)點(diǎn)數(shù)量不算太多的情況下定位精度有所提高，隨著錨節(jié)點(diǎn)數(shù)量的增加，定位精度提高的更快。

參考文獻(xiàn):

[1]彭勇.無線傳感器網(wǎng)絡(luò)中能量高效的目標(biāo)跟蹤協(xié)議研究[D].長(zhǎng)沙:中南大學(xué),2009.

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

[3]薛霞，孫勇.監(jiān)測(cè)煤礦的一種無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].傳感器與微系統(tǒng),2010,29(9):119-121.

[4]盧迪，劉世琦.無線傳感網(wǎng)絡(luò)改進(jìn)APIT定位算法[J].哈爾濱理工大學(xué)學(xué)報(bào),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的無線傳感器網(wǎng)絡(luò)混合型定位算法[J].傳感器與微系統(tǒng),2015,34(2):133-135.

[7]王亞子，楊建輝.改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J].計(jì)算機(jī)工程與應(yīng)用,2014(18):99-102.

[8]楊驥，劉鋒.無線傳感器網(wǎng)絡(luò)基于中垂線分割的APIT的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報(bào),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] 謝國(guó)新，李新.短波干擾有效壓制距離的計(jì)算方法[J].航天電子對(duì)抗,2005,2(1):53-55.

[11] 曹磊,徐晨.無線傳感器網(wǎng)絡(luò)近似三角形內(nèi)點(diǎn)測(cè)試定位算法改進(jìn)[J].電子技術(shù)應(yīng)用,2007(11):80-82.

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

[13] 祁會(huì)波.無線傳感器網(wǎng)絡(luò)中基于移動(dòng)錨節(jié)點(diǎn)的定位算法研究[D].太原:太原理工大學(xué),2006.

[14] 張驍航.基于跳距誤差修正和粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法研究[D].重慶: 重慶郵電大學(xué),2012.

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

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

作者簡(jiǎn)介:

中圖分類號(hào)：TN 926

文獻(xiàn)標(biāo)識(shí)碼：A

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

*基金項(xiàng)目：哈爾濱市科技創(chuàng)新人才(優(yōu)秀學(xué)科帶頭人計(jì)劃類)基金資助項(xiàng)目(2014RFXXJ086)

收稿日期：2015—11—09

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