無線傳感器網絡三維APIT網格化算法

相衛華，賈 超，王華奎，孫高峰

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

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

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

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

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

1 APIT定位方法

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

圖1 APIT算法概述

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

圖2 PIT定位原理

2 3D-GPIT定位算法

2.1 APIT算法的三維擴展

通過對APIT算法的分析，限制維數的主要原因是以PIT測試理論為基礎，因此首先對PIT算法進行改進，將原來基于平面的三角形內點測試的算法改為基于空間的四面體內點測試，為此提出3DPIT測試［12］，即:假如存在一個方向，沿著這個方向若未知節點M會同時遠離或接近設一個四面體(Tetrahedron，這里記為TABCD)的全部四個頂點A，B，C，D，則M位于TABCD外;否則，M位TABCD內。證明見文獻［12］。

圖3 三維PIT定位原理

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

2.2 APIT-3D 算法分析

(1)定位誤判分析

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

圖5

對出現兩種誤判情況分析如下:

①3D-APIT算法是建立在空間方向矢量的完備性基礎上完成的，因此定位精度的高低與節點密度密切相關，當出現只能判斷有限的方向，誤判出現概率大大增加。

②從定位過程來看未知節點尋找同時接近或遠離所有錨節點的方向，設這個方向矢量為→LM，當出現→LM方向立即判外，這點過于絕對。因為當節點稀疏情況下，方向矢量較少，不易出現→LM，容易出現Out-to-in error，而節點密集情況下，方向矢量較多，→LM出現概率大幅度增加，容易出現In-to-out error。針對以上情況可以通過增加判定次數的比較進行改進，如圖6所示。

圖6 算法示意圖

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

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

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

①節點部署完成后，對監測區域進行網格劃分，假設其中的一個錨節點作為中心O(xo，yo，zo)，建立空間直角坐標系，并設網格的分辨率為a。

②設三維空間區域為正立方體ψ，對于其中的任何一個網格有 φi∈ψ，網格重心為 φ(x，y，z)，設區域的體積V，共有V/a3個網格，每個網格都是動態的，每個網格設置跳矢計數器HCV(Hop Count Vector)，如圖7(a)。

圖7 網格投票示意圖

2.3 3D-GPIT 算法流程

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

(1)初始化階段:在網絡部署完成后，錨節點廣播信息，未知節點和鄰居節點信息記錄接收到的錨節點信號強度指示值RSSI(Received Signal Strength Indicator)。如表1所示。

表1 節點收到的RSSI值

(2)未知節點與鄰居節點交換信息，對每個方向矢量進行3D-PIT測試，例如表中的位置節點M與SS1比較得在TABCD外，與SS2比較得TABCD內。未知節點統計判內判外的次數，

(3)對三維空間進行網格劃分，判定結束后，開始對網格進行投票，每個網格記錄投票次數，找到所求的網格優選集P={lmax}，即為估計位置。

3 仿真結果

作者采用MATLAB進行仿真，設置以下參數來評估定位方法的性能:

(1)錨節點與未知節點的通信半徑比ANR(Anchor to Node Range Ratio):ANR越大，錨節點的有效通信距離越大，網絡的連通度越好。

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

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

(4)無線信號不規則度DOI(Degree of Irregularity)。

如圖8所示在100 m×100 m×100 m的三維平面內的節點部署圖，在此區域內隨機分布150個未知節點，此時首先設置5×5×5個均勻分布的錨節點。網格分辨率即為25 m。然后逐步改變錨節點數量。

圖8 100 m×100 m×100 m區域節點部署圖

逐步改變上述參數對性能進行評估

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

圖9是在理想環境下的分辨率ρ與ANR對定位誤差的影響，圖中顯示在ANR相同的情況下，網格分辨率越小，定位誤差越小，首先是因為分辨率即代表了定位的精度，分辨率越精細那么未知節點的定位也就越準確。如果當分辨率ρ一定時，隨著ANR逐步增加定位誤差為下降的趨勢，最后達到一個平緩的狀態，這是因為ANR代表了未知節點可與之進行通信的錨節點的數目，如果ANR越大，通信的錨節點數目越多，那么包括的四面體就越多，誤判也隨之減小，從而重疊的區域更加精確，誤差減小最后達到定位精度的極限值。

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

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

從圖10中可以在理想環境下，若ANR一定，隨著AH的增大定位誤差呈下降的趨勢，這是因為AH反映了網絡的連通度，AH越大，未知節點能夠通信的錨節點數目就越多，網絡連通性越好。在理想環境下(DOI=0)，AH的增加，包含未知節點的四面體就越多，從而重疊區域更加精確，定位誤差越小。

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

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

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

圖11 DOI對定位誤差影響

4 結論

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

［1］ 孫利民，李建中，陳渝，等.無線傳感器網絡［M］.1版.北京，清華大學出版社，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］.傳感技術學報，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］ 趙清華，劉少飛，張朝霞，等.一種無需測距節點定位算法的分析和改進［J］.傳感技術學報，2010，23(1):122－127.

［6］ 戴瑩，王建平，張崇巍.無線傳感器網絡節點定位算法的研究與改進［J］.傳感技術學報，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］ 吳凌飛，孟慶虎，梁華為.一種基于共線度的無線傳感器網絡定位算法［J］.傳感技術學報，2009，22(5):722－727.

［9］ 蔡紹濱，李希，田鷹，等.基于圓形選擇技術的循環三邊組合測量法的研究［J］.計算機研究與發展，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］陳積明，林瑞仲，孫優賢.無線傳感器網絡通信體系研究［J］.傳感技術學報，2006，19(4):1290－1295.

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

［13］周祖德，胡鵬，劉泉，等.一種基于MDS的無線傳感器網絡快速定位算法［J］.傳感技術學報，2007，20(10):2303－2307.