戴天虹, 李　昊

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

?

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

戴天虹, 李昊

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

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

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

0引言

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

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

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

1APIT算法

1.1APIT算法的基本原理

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

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

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

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

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

在整個無線傳感器網(wǎng)絡(luò)的邊緣地區(qū)，傳感器的數(shù)量相對來說比較少，錨節(jié)點較少，這樣組成的三角形的數(shù)量也會降低。在進(jìn)行PIT算法進(jìn)行定位時，會出現(xiàn)由于重疊區(qū)域過大造成實際位置與定位位置偏差過大的現(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é)點接收到未知節(jié)點的信號強(qiáng)度的變化來作為依據(jù)所實現(xiàn)的。如圖2左圖所示，目標(biāo)節(jié)點在向1方向移動的過程中，可用三角形3個錨節(jié)點接收到的信號強(qiáng)度會發(fā)生變化，A錨節(jié)點接收到的信號強(qiáng)度會越來越大，B,C目標(biāo)節(jié)點接收到的信號強(qiáng)度會越來越小。

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

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

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

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

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

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

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

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

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

2仿真研究

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

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

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

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

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

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

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

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

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

2.2仿真結(jié)果

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

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

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

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

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

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

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

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

3結(jié)論

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

參考文獻(xiàn):

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

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

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

[4]盧迪，劉世琦.無線傳感網(wǎng)絡(luò)改進(jìn)APIT定位算法[J].哈爾濱理工大學(xué)學(xué)報,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é)點定位[J].計算機(jī)工程與應(yīng)用,2014(18):99-102.

[8]楊驥，劉鋒.無線傳感器網(wǎng)絡(luò)基于中垂線分割的APIT的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報,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] 曹磊,徐晨.無線傳感器網(wǎng)絡(luò)近似三角形內(nèi)點測試定位算法改進(jìn)[J].電子技術(shù)應(yīng)用,2007(11):80-82.

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

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

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

戴天虹(1963-)，男，黑龍江哈爾濱人，博士，教授，主要從事林業(yè)工程自動化等方面的教學(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

作者簡介:

中圖分類號：TN 926

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

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

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

收稿日期：2015—11—09

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