無線傳感器網(wǎng)絡(luò)三維APIT網(wǎng)格化算法

相衛(wèi)華，賈 超，王華奎，孫高峰

(太原理工大學(xué)信息工程學(xué)院，太原030002)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是一種由成千上萬的微型傳感器節(jié)點(diǎn)協(xié)同工作的分布式自組織網(wǎng)絡(luò)，其主要目的就是對(duì)感知對(duì)象進(jìn)行信息的監(jiān)測(cè)，采集并及時(shí)上報(bào)給觀測(cè)者［1－3］。根據(jù)傳感器網(wǎng)絡(luò)的應(yīng)用場(chǎng)景觀測(cè)數(shù)據(jù)往往是不同的，但是有一類信息與這些數(shù)據(jù)是密不可分的，即節(jié)點(diǎn)的位置信息。沒有位置信息的數(shù)據(jù)是沒有意義的，某些情況下如環(huán)境監(jiān)測(cè)、軍事偵查、城市交通等直接需求就是目標(biāo)位置信息［4－5］，因此如何對(duì)目標(biāo)位置進(jìn)行定位是傳感器網(wǎng)絡(luò)起關(guān)鍵作用。

目前傳感器節(jié)點(diǎn)定位研究平臺(tái)通常分為兩大類:基于測(cè)量距離定位方法(Range-Based)和與測(cè)量距離無關(guān)的定位方法(Range-Free)［6］。與測(cè)距有關(guān)的定位方法通信開銷大，對(duì)節(jié)點(diǎn)硬件要求高，雖然精度上較高不適用于這種低能耗、低成本、一次性電源的傳感器節(jié)點(diǎn)［7］。實(shí)驗(yàn)表明，非測(cè)距定位算法不僅通信開銷較小，而且能夠滿足WSN網(wǎng)絡(luò)對(duì)定位精度要求，因此這目前普遍研究的是這種定位機(jī)制［8－9］。

由弗吉尼亞大學(xué)的研究者提出的APIT(Approximate Point-In-Triangle)［10］算法是一種比較優(yōu)秀的非測(cè)距定位方法，主要方法是利用PIT原理獲取估算區(qū)域的優(yōu)選集進(jìn)行定位。PIT算法的核心內(nèi)容是利用三角形特性來判定未知節(jié)點(diǎn)是否在其內(nèi)部，從而估算位置區(qū)域。

隨著定位技術(shù)應(yīng)用領(lǐng)域的升級(jí)，首先面對(duì)的問題就是節(jié)點(diǎn)空間的開拓，傳統(tǒng)的無線傳感網(wǎng)絡(luò)定位算法主要是針對(duì)二維平面而設(shè)計(jì)的［11］，但三維空間更符合實(shí)際情況，在復(fù)雜地形的叢林，山區(qū)等環(huán)境中，二維空間定位已不再適用，APIT算法就局限此范圍上。為此本文在分析APIT算法的基礎(chǔ)上，提出3D-GPIT定位算法(Three-Dimensional Grid Based on APIT)，通過仿真比較證明了策略的有效性。

1 APIT定位方法

APIT算法的基本原理是:未知節(jié)點(diǎn)偵聽自身附近錨節(jié)點(diǎn)的信息，根據(jù)信號(hào)強(qiáng)度門限選取符合要求的錨節(jié)點(diǎn)，這些錨節(jié)點(diǎn)任意選取三個(gè)節(jié)點(diǎn)組成三角形。設(shè)有n個(gè)符合要求的錨節(jié)點(diǎn)共組成C3n個(gè)三角形，未知節(jié)點(diǎn)對(duì)這些三角形逐一判斷是否位于每個(gè)三角形內(nèi)部，包含未知節(jié)點(diǎn)的三角形無限重疊，最后最大的重疊區(qū)域就是未知節(jié)點(diǎn)的區(qū)域，將重疊區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估算位置。如圖1所示，陰影部分區(qū)域是包含未知節(jié)點(diǎn)的所有三角形的最大重疊區(qū)域。即為未知節(jié)點(diǎn)的估算位置，如圖1(a)。

圖1 APIT算法概述

三角形測(cè)試方法的理論基礎(chǔ)是最佳三角形內(nèi)點(diǎn)測(cè)試，即 PIT測(cè)試(Perfect Poin-In-Triangulation Test)。如圖2所示，假設(shè)點(diǎn)M代表未知節(jié)點(diǎn)，在三角形周圍如果存在某個(gè)方向使得點(diǎn)M會(huì)同時(shí)遠(yuǎn)離或接近三角形的3個(gè)端點(diǎn)A，B，C，則M位于△ABC外;否則，M位于△ABC內(nèi)。需要說明的是，在靜態(tài)網(wǎng)絡(luò)中，未知節(jié)點(diǎn)依靠網(wǎng)絡(luò)的連通性，通過與鄰居節(jié)點(diǎn)交換信息模擬節(jié)點(diǎn)移動(dòng)，完成PIT測(cè)試。

圖2 PIT定位原理

2 3D-GPIT定位算法

2.1 APIT算法的三維擴(kuò)展

通過對(duì)APIT算法的分析，限制維數(shù)的主要原因是以PIT測(cè)試?yán)碚摓榛A(chǔ)，因此首先對(duì)PIT算法進(jìn)行改進(jìn)，將原來基于平面的三角形內(nèi)點(diǎn)測(cè)試的算法改為基于空間的四面體內(nèi)點(diǎn)測(cè)試，為此提出3DPIT測(cè)試［12］，即:假如存在一個(gè)方向，沿著這個(gè)方向若未知節(jié)點(diǎn)M會(huì)同時(shí)遠(yuǎn)離或接近設(shè)一個(gè)四面體(Tetrahedron，這里記為TABCD)的全部四個(gè)頂點(diǎn)A，B，C，D，則M位于TABCD外;否則，M位TABCD內(nèi)。證明見文獻(xiàn)［12］。

圖3 三維PIT定位原理

在靜態(tài)網(wǎng)絡(luò)，M點(diǎn)固定無法執(zhí)行三維PIT測(cè)試，為此提出了三維APIT測(cè)試APIT-3D(Approximate PIT-3D)利用網(wǎng)絡(luò)中未知節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)收到信標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度來模擬節(jié)點(diǎn)移動(dòng)，以判斷其是否處于信標(biāo)節(jié)點(diǎn)四面體中。在圖4(a)中，節(jié)點(diǎn)M假如自身運(yùn)動(dòng)至鄰居節(jié)點(diǎn)2處，可以根據(jù)節(jié)點(diǎn)M與節(jié)點(diǎn)2的RSSI值表，得知節(jié)點(diǎn)M將同時(shí)遠(yuǎn)離錨節(jié)點(diǎn)A、B、C、D(A、B、C、D 的 RSSI值同時(shí)變小)，故判斷自身在TABCD外。如果不存在這樣的點(diǎn)即RSSI值同時(shí)增大或減小的則判定在TABCD內(nèi)，如圖4(b)所示。

2.2 APIT-3D 算法分析

(1)定位誤判分析

首先分析以下兩種情況:如圖4(a)所示，未知節(jié)點(diǎn)M靠近四面體的一條邊，且鄰居節(jié)點(diǎn)1位于四面體外部，節(jié)點(diǎn)C較之未知節(jié)點(diǎn)M同時(shí)遠(yuǎn)離3個(gè)端點(diǎn)A、B、C，根據(jù)三維APIT的定義，未知節(jié)點(diǎn)M就做出TABCD外的錯(cuò)誤判斷，稱作In-To-Out Error。反之做出在TABCD內(nèi)的誤判，稱作Out-To-In Error，如圖5所示。

圖5

對(duì)出現(xiàn)兩種誤判情況分析如下:

①3D-APIT算法是建立在空間方向矢量的完備性基礎(chǔ)上完成的，因此定位精度的高低與節(jié)點(diǎn)密度密切相關(guān)，當(dāng)出現(xiàn)只能判斷有限的方向，誤判出現(xiàn)概率大大增加。

②從定位過程來看未知節(jié)點(diǎn)尋找同時(shí)接近或遠(yuǎn)離所有錨節(jié)點(diǎn)的方向，設(shè)這個(gè)方向矢量為→LM，當(dāng)出現(xiàn)→LM方向立即判外，這點(diǎn)過于絕對(duì)。因?yàn)楫?dāng)節(jié)點(diǎn)稀疏情況下，方向矢量較少，不易出現(xiàn)→LM，容易出現(xiàn)Out-to-in error，而節(jié)點(diǎn)密集情況下，方向矢量較多，→LM出現(xiàn)概率大幅度增加，容易出現(xiàn)In-to-out error。針對(duì)以上情況可以通過增加判定次數(shù)的比較進(jìn)行改進(jìn)，如圖6所示。

圖6 算法示意圖

未知節(jié)點(diǎn)在找到→LM后并不立即判定，而是對(duì)所有的方向矢量進(jìn)行比較，可以在節(jié)點(diǎn)內(nèi)部設(shè)置一個(gè)計(jì)數(shù)器(Counter)，記為ξ=0，若根據(jù)某一鄰居節(jié)點(diǎn)方向矢量判定在四面體內(nèi)，ξ加1，反之減1，所有鄰居節(jié)點(diǎn)判斷統(tǒng)計(jì)完成后，若ξ＞0則判內(nèi)，若ξ＜0則判外。

(2)重疊區(qū)域的定位問題

3D-APIT測(cè)試完成后，下一步是找到估算區(qū)域的優(yōu)選集合，這就要求將包含未知節(jié)點(diǎn)的所有四面體所在區(qū)域進(jìn)行重疊，找到最大的覆蓋空間范圍，文獻(xiàn)［6］中提出找到重疊區(qū)域的重心來確定未知節(jié)點(diǎn)的位置，但此過程較為復(fù)雜;在前一節(jié)誤判分析中，為提高定位精度提出了逐次判斷方法，現(xiàn)在利用三維網(wǎng)格定位與3D-APIT算法結(jié)合，可就下述三個(gè)方面，對(duì)以上兩點(diǎn)進(jìn)行改進(jìn):

①節(jié)點(diǎn)部署完成后，對(duì)監(jiān)測(cè)區(qū)域進(jìn)行網(wǎng)格劃分，假設(shè)其中的一個(gè)錨節(jié)點(diǎn)作為中心O(xo，yo，zo)，建立空間直角坐標(biāo)系，并設(shè)網(wǎng)格的分辨率為a。

②設(shè)三維空間區(qū)域?yàn)檎⒎襟wψ，對(duì)于其中的任何一個(gè)網(wǎng)格有 φi∈ψ，網(wǎng)格重心為 φ(x，y，z)，設(shè)區(qū)域的體積V，共有V/a3個(gè)網(wǎng)格，每個(gè)網(wǎng)格都是動(dòng)態(tài)的，每個(gè)網(wǎng)格設(shè)置跳矢計(jì)數(shù)器HCV(Hop Count Vector)，如圖7(a)。

圖7 網(wǎng)格投票示意圖

2.3 3D-GPIT 算法流程

通過以上分析，提出在3D-APIT算法定法中增加區(qū)域網(wǎng)格定位(Grid Location)這一關(guān)鍵步驟，稱為3D-GPIT算法，即三維APIT網(wǎng)格化算法，具體步驟如下:

(1)初始化階段:在網(wǎng)絡(luò)部署完成后，錨節(jié)點(diǎn)廣播信息，未知節(jié)點(diǎn)和鄰居節(jié)點(diǎn)信息記錄接收到的錨節(jié)點(diǎn)信號(hào)強(qiáng)度指示值RSSI(Received Signal Strength Indicator)。如表1所示。

表1 節(jié)點(diǎn)收到的RSSI值

(2)未知節(jié)點(diǎn)與鄰居節(jié)點(diǎn)交換信息，對(duì)每個(gè)方向矢量進(jìn)行3D-PIT測(cè)試，例如表中的位置節(jié)點(diǎn)M與SS1比較得在TABCD外，與SS2比較得TABCD內(nèi)。未知節(jié)點(diǎn)統(tǒng)計(jì)判內(nèi)判外的次數(shù)，

(3)對(duì)三維空間進(jìn)行網(wǎng)格劃分，判定結(jié)束后，開始對(duì)網(wǎng)格進(jìn)行投票，每個(gè)網(wǎng)格記錄投票次數(shù)，找到所求的網(wǎng)格優(yōu)選集P={lmax}，即為估計(jì)位置。

3 仿真結(jié)果

作者采用MATLAB進(jìn)行仿真，設(shè)置以下參數(shù)來評(píng)估定位方法的性能:

(1)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的通信半徑比ANR(Anchor to Node Range Ratio):ANR越大，錨節(jié)點(diǎn)的有效通信距離越大，網(wǎng)絡(luò)的連通度越好。

(2)平均可見錨節(jié)點(diǎn)數(shù)目AH(Anchors Heard):未知節(jié)點(diǎn)能夠接收到的所有錨節(jié)點(diǎn)的平均數(shù)量。

(3)網(wǎng)格分辨率:即所劃分的網(wǎng)格的大小，若網(wǎng)格越小分辨率越高。

(4)無線信號(hào)不規(guī)則度DOI(Degree of Irregularity)。

如圖8所示在100 m×100 m×100 m的三維平面內(nèi)的節(jié)點(diǎn)部署圖，在此區(qū)域內(nèi)隨機(jī)分布150個(gè)未知節(jié)點(diǎn)，此時(shí)首先設(shè)置5×5×5個(gè)均勻分布的錨節(jié)點(diǎn)。網(wǎng)格分辨率即為25 m。然后逐步改變錨節(jié)點(diǎn)數(shù)量。

圖8 100 m×100 m×100 m區(qū)域節(jié)點(diǎn)部署圖

逐步改變上述參數(shù)對(duì)性能進(jìn)行評(píng)估

(1)不同的網(wǎng)格分辨率ρ與通信半徑比ANR對(duì)平均定位誤差的影響。

圖9是在理想環(huán)境下的分辨率ρ與ANR對(duì)定位誤差的影響，圖中顯示在ANR相同的情況下，網(wǎng)格分辨率越小，定位誤差越小，首先是因?yàn)榉直媛始创砹硕ㄎ坏木龋直媛试骄?xì)那么未知節(jié)點(diǎn)的定位也就越準(zhǔn)確。如果當(dāng)分辨率ρ一定時(shí)，隨著ANR逐步增加定位誤差為下降的趨勢(shì)，最后達(dá)到一個(gè)平緩的狀態(tài)，這是因?yàn)锳NR代表了未知節(jié)點(diǎn)可與之進(jìn)行通信的錨節(jié)點(diǎn)的數(shù)目，如果ANR越大，通信的錨節(jié)點(diǎn)數(shù)目越多，那么包括的四面體就越多，誤判也隨之減小，從而重疊的區(qū)域更加精確，誤差減小最后達(dá)到定位精度的極限值。

圖9 理想環(huán)境下(DOI=1)，ANR對(duì)定位誤差影響

(2)不同的AH對(duì)平均定位誤差的影響

從圖10中可以在理想環(huán)境下，若ANR一定，隨著AH的增大定位誤差呈下降的趨勢(shì)，這是因?yàn)锳H反映了網(wǎng)絡(luò)的連通度，AH越大，未知節(jié)點(diǎn)能夠通信的錨節(jié)點(diǎn)數(shù)目就越多，網(wǎng)絡(luò)連通性越好。在理想環(huán)境下(DOI=0)，AH的增加，包含未知節(jié)點(diǎn)的四面體就越多，從而重疊區(qū)域更加精確，定位誤差越小。

圖10 理想環(huán)境下(DOI=1)，AH定位誤差影響

(3)不同的DOI對(duì)平均定位誤差的影響

圖11描述了DOI與定位誤差的關(guān)系，從圖中看出，隨之DOI的增加誤差而增大，呈線性關(guān)系，這是由于信號(hào)傳輸不規(guī)則性使得未知節(jié)點(diǎn)與鄰節(jié)點(diǎn)和錨節(jié)點(diǎn)交換信息出現(xiàn)錯(cuò)誤信息幅值，從而出現(xiàn)誤判導(dǎo)致錯(cuò)誤率增加。為了克服無線信號(hào)傳輸不規(guī)則性的影響，可以采用重復(fù)廣播信息的方法來減小誤判。

圖11 DOI對(duì)定位誤差影響

4 結(jié)論

通過空間網(wǎng)格化將3D-GPIT算法后續(xù)的定位過程進(jìn)行了改進(jìn)，簡(jiǎn)化了尋找四面體重心這一繁瑣的過程，并分析了定位過程中的誤判問題，提出的分類比較計(jì)算方法有效的降低了誤判率，這些都是在網(wǎng)絡(luò)有很好的連通度(N＞6)［13］情況下進(jìn)行研究的，如果節(jié)點(diǎn)稀疏將導(dǎo)致算法失效進(jìn)而無法完成網(wǎng)格定位，這個(gè)問題需要進(jìn)一步解決。

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

［2］ Wang Lei，Wang Xiaopeng，Du Xiaotong.Some Issues on WSN Localization Based on MLE［C］//Intelligent Control and Automation(WCICA)，2010 8th World Congress on，2010:796－800.

［3］ 包志華，周暉，邵世煌.基于智能估計(jì)的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2008，21(10):1755－1769.

［4］ Hady S A，Stephan O.A 3D-Localization and Terrain Modeling Technique for Wireless Sensor Networks［C］//Proc.of the 2nd ACM Int’l Workshop on Foundations of Wireless Ad-Hoc and Sensor Networking and Computing.2009，37－46.

［5］ 趙清華，劉少飛，張朝霞，等.一種無需測(cè)距節(jié)點(diǎn)定位算法的分析和改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2010，23(1):122－127.

［6］ 戴瑩，王建平，張崇巍.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究與改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2010，23(4):567－570.

［7］ Bin Lu，Thomas G Habetler，Ronald G Harley.A Novel Motor Energy Monitoring Scheme Using Wireless Sensor Networks［C］//Industry Applications Conference，2006.41st IAS Annual Meeting.Conference Record of the 2006 IEEE Vofume 5，Oct.2006:2177－2184.

［8］ 吳凌飛，孟慶虎，梁華為.一種基于共線度的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22(5):722－727.

［9］ 蔡紹濱，李希，田鷹，等.基于圓形選擇技術(shù)的循環(huán)三邊組合測(cè)量法的研究［J］.計(jì)算機(jī)研究與發(fā)展，2010，47(2):238－244.

［10］ He Tian，Chengdu，Blum B M，et al.Range-Free Localization Schemes in Large Scale Sensor Networks［C］//Proceedings of the 9th Annual International Conference on Mobile Computing and Net-Working，MOBIHOC 2003，San Diego(CA，USA)，2003.New York(NY，USA):ACM Press，2003:81－95.

［11］陳積明，林瑞仲，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)通信體系研究［J］.傳感技術(shù)學(xué)報(bào)，2006，19(4):1290－1295.

［12］劉玉恒，蒲菊華，赫陽，等.無線傳感器網(wǎng)絡(luò)三維自身定位方法［J］.北京航空航天大學(xué)學(xué)報(bào)，2008，34(6):647－651.

［13］周祖德，胡鵬，劉泉，等.一種基于MDS的無線傳感器網(wǎng)絡(luò)快速定位算法［J］.傳感技術(shù)學(xué)報(bào)，2007，20(10):2303－2307.