通常，無線傳感器網絡（Wireless Sensor Networks，WSN）信息采集節點是被隨機放置或是從飛機上隨機拋撒的。因此如何確定節點的具體位置成為無線傳感器網絡研究的難點和重點。

WSN的定位主要分對節點自身的定位和對外部目標的跟蹤定位。WSN自身定位方法分為基于測距的方法和非基于測距的方法。基于測距的定位通過測量相鄰節點之間的絕對距離或方位等來計算未知節點的位置，需要特定的硬件設備，定位精度較高。而非基于測距的定位機制無需測距或角度信息，不用直接測量這些信息，僅根據網絡的連通性等信息實現節點的定位，典型的有質心算法、DV-Hop算法、凸規劃算法和APIT算法等。

參考文獻提出了一種IAPIT的定位方法，主要思路是將3邊測量法以及幾何上的由已知兩點在輔助條件下求解兩圓交點的方法融入到APIT算法中，但是算法仍然局限于二維宅間中的定位。參考文獻通過對單跳質心算法進行多跳擴展以改善定位比率，并加入場強加權過程和去中心化過程以提高定位精度。參考文獻提出將所有收集到的來自于同一信標節點的RSSI值做平均，作為未知節點接收到此固定信標節點的RSSI值，進行定位計算。參考文獻結合三角形測試原理（PIT），主要針對信標節點分布不均勻的情況提出了CBPIT算法。參考文獻提出了一種節點自身的定位方法，能夠通過相對準確的測試來確定節點所在的區域，但是沒有考慮未知節點監聽到信標節點數目較少的情況。

本文針對三維空間的節點定位提出了改進的TDAPIT算法。

1 算法描述

1．1 術語定義

①信標節點：已知位置并能協助未知節點定位的節點，也稱錨節點。

②鄰居節點：在節點的通信范圍內，并可與這個節點直接通信的所有節點。

③未知節點：不知道自身的位置，需使用信標節點的位置信息并運用一定的算法得到估計位置的節點，也稱待定位節點。

④已知節點：圩始時不知道自身的位置信息，但是經過一段時間的定位后，已經通過信標節點的位置信息并用一定的算法得到了位置信息的節點。

⑤不良節點：定位過程結束后，仍然不能夠實現定位的節點。

實際上，WSN的節點定位即未知節點在信標節點的協助下轉變成已知節點的過程。在實際定位過程中，由于種種原因，難免會出現不良節點，應當盡力減少不良節點的個數。

1．2 APIT算法

APIT算法的基本思想是未知節點任選3個相鄰信標節點，測試是否位于它們所組成的三角形中，使用不同信標節點組合重復測試，直到窮盡所有組合或達到所需定位精度。最后，計算包含目標節點的所有三角形交集的質心位置，并以此作為目標節點位置。

APIT算法理論基礎是PIT測試。如果存在一個方向，并且沿著此方向運動的未知節點會同時遠離或者是接近三角形的三個頂點，那么此未知節點在三角形的外部，否則在三角形的內部。

在實際測試中，可以用未知節點和它的鄰居節點來模擬此運動。若未知節點的鄰節點都沒有同時遠離或靠近3個信標節點，那么此未知節點就在三角形內，否則在三角形外。PIT測試時，一般采用信號強度來判斷遠離或者是接近信標節點。

PIT測試誤差分析如下：

①PIT測試中容易出現InToOut和OutToIn錯誤。InToOut錯誤即將三角形內部的點誤判為在三角形外面。PIT測試圖像如圖1所示。當未知節點靠近或者正好在三角形的一條邊上時，就容易出現上述的錯誤。

②如果信標節點和未知節點的鄰居節點密度過小，對定位結果的影響很大，抑或使得有些節點不能被定位，定位覆蓋率較低。

③在網絡的中間部分和未知節點相鄰的信標節點可能很多，但是其中任意3個節點所組成的三角形可能都不包括未知節點，因此在算法完成后仍不能定位這類節點。

④在網絡的邊緣部分，容易造成無法滿足APIT的定位條件，當和未知節點相鄰的信標節點數目少于3個時，造成未知節點無法定位。

⑤對重疊區域的重心計算中，采用的是網格掃描的算法，效率較低，計算精度不高。

⑥算法中，未知節點不僅要與信標節點交互信息，還要與其他的鄰居節點進行協調信息處理，使得網絡中節點的計算量增大，通信開銷也上升了很多。

1．3 基于APIT的三維定位方法

1．3．1 TDAPIT算法原理

信標節點是WSN空間中已經知道自身坐標位置的固定節點（如通過GPRS定位等），空間中的任意一個未知節點，能夠監聽到信標節點的數目為n，那么從n中任意選取4個點組成一個四面體，共有C4n個四面體；然后，測試該未知節點是否在這4個信標節點組成的四面體內，重復這種測試，直到監聽到所有信標節點的組合或者是達到了要求的精度；最后，計算包含未知節點的所有四面體的重疊區域，將重疊區域的質心作為未知節點的位置。

1．3．2 TDAPIT測試

若存在一個方向，沿著這個方向未知節點M會同時遠離或接近四面體的四個頂點，則M位于四面體外，否則M位于四面體內部。

在隨機部署的傳感器網絡中，有一些節點偵聽到的信標節點個數小于4，則這些節點不能進行PIT測試；有些節點盡管接收到的信標節點數目大于或等于4個，也能進行PIT測試，但是卻仍然無法判斷其位置。在測試中，利用如下方法判斷未知節點位置：

①通過未知節點接收到信標節點的RSS值大小來判斷節點和信標節點之間的距離。

②通過未知節點的鄰居節點來模擬未知節點的移動，即假設未知節點移動到它的鄰居節點。

③通過對未知節點所有鄰居節點的模擬來近似地遍歷未知節點的所有方向。

④為了減少InToOut和OutToIn錯誤，我們可以通過在節點上設置相應的MAXrss和MINrss閾值來進一步判斷。對于初步判定為在三角形外部的節點，如果未知節點接收到的信號強度值大于設置的閾值，則認為判定錯誤；同樣，對于判定為在三角形內部的節點，如果接收到的信號強度小于設定的閾值，則認為發生OutToIn錯誤。

1．3．3 TDAPIT算法流程

TDAPIT算法流程步驟如下：

①節點部署完成后，網絡初始化配置。信標節點向網絡廣播消息（消息應該包含信標節點的ID、位置坐標等信息），而未知節點監聽信標節點的消息。此階段未知節點應隨時更新接收到的信息，以防止岡網絡的拓撲變化而造成的誤差影響。

②設未知節點M監聽到的信標節點數目為n（n=0，1，2，3，4，5，6…）。信標節點的坐標為A1，A2，A3，A4，…，An，未知節點將監聽到的信標節點的坐標存入數組，如果n小于5則繼續下一步，否則轉向步驟④；

③當n=4、3或2時，即未知節點只能監聽到4、3或2個信標節點。以未知節點所能監聽到的信標節點為圓心，以通信距離為半徑分別作球，兩球分別相交，分別求出4個球體、3個球體、2個球體重疊區域的質心作為未知節點的坐標。

當n=1或0時，即未知節點只能監聽到1或0個信標節點。此時，未知節點等待一段時間t（這里t應設置為略小于定位周期）后，向其所有鄰居節點廣播消息，請求獲知鄰居節點的坐標信息。若沒有鄰居節點返回消息，那么重復執行此步驟；若有鄰居節點返回消息但鄰居節點尚未定位，則信標節點繼續等待一小段隨機的時間后，重復請求消息；若有鄰居節點返回消息并且鄰居節點已經定位完畢，此時鄰居節點成為已知節點，則未知節點把已知節點當成信標節點，重復執行步驟①。

④從n個信標節點中任取4個節點組成i（i=1，2，3，4，…，C4n）個四面體，得到包含未知節點的所有四面體，根據四面體相交后的重疊區域計算此重疊區域的質心坐標作為未知節點的坐標。

1．3．4 算法分析

信標節點廣播消息時，采用洪泛的方法，使得通信距離內的未知節點都可以監聽到消息，而且未知節點只負責監聽消息，并不需要和相鄰節點進行消息交換。這樣就大大減少了網絡中未知節點的通信量，增加了網絡生命周期。但是為了使得未知節點能夠監聽到更多的信標節點，我們設定能量較多的信標節點來廣播兩次消息。第一次廣播消息時同時監聽周圍的信標節點的廣播，將監聽到的其他信標節點的消息記錄下來。第二次廣播時，將所知道的所有的信標節點的信息都廣播出去，此時監聽的節點將接收到的消息和第一次接收的消息對比，若發現有新的信標節點則及時更新信息。

對于未知節點監聽到的信標節點，不能構成四面體相交的，利用球體重合區域的質心作為未知節點的坐標。如果未知節點監聽到的信標節點數目較少，可以利用已經定位完畢的節點來對未知節點進行定位。在求解球體重合區域的質心時，可以利用網格掃面算法，計算量較大、誤差較小；也可以利用四面體質心掃面算法，計算量較小但是誤差較大，根據實際情況予以選擇。

1．4 算法流程

整個算法的流程如圖2所示。

2 實驗仿真與評估

本文中采用的仿真軟件是Visual C++與Matlab7．5，選取的實驗參數是定位覆蓋率和定位誤差。仿真實驗中，200個節點是隨機部署在邊長為80 m的正方體監測區域內，信標節點和未知節點的通信半徑都是一樣的。為了減少隨機分布和偶然因素帶來的影響，仿真的結果是在相同的參數下仿真50次的平均值。通過比較二維空間中的APIT和文中提出的三維TDAPIT算法在不同的信標節點比例的情況下的定位覆蓋率和定位誤差，最后來分析擴展后算法的優劣。

2．1 定位覆蓋率

定位覆蓋率隨信標節點比例變化圖如圖3所示。在信標節點比例為5％時，APIT定位覆蓋率約為10％，而TDAPIT約為30％，這說明相對于二維空間中的APIT定位，TDAPIT定位在三維空間中的定位覆蓋率在信標節點比例較小時，仍能發揮相當的效用。隨著信標節點比例的上升，TDAPIT的定位覆蓋率更是明顯地上升，在信標節點比例為20％左右時，定位覆蓋率就達到了90％以上。在這以后，信標節點比例的增加對定位覆蓋率的影響大大降低。這是因為在算法中采用了循環擴散的思想，即將已知節點當做信標節點來實現定位，最大限度地減少了不良節點的數目。在信標節點比例達到30％左右時，APIT算法的定位覆蓋率在85％左右，而且仍然還有上升的趨勢，說明APIT算法對信標節點比例的依賴程度比較高。

2．2 定位誤差

定位誤差隨信標節點比例變化圖如圖4所示。該仿真結果說明，在網絡部署一定時，當兩種算法的定位誤差達到35％左右時，兩者的定位精度很難再得到明顯改善。在信標節點比例為5％左右時，TDAPIT的定位誤差明顯大于APIT的定位誤差，這是因為在網絡的初始階段，APIT可定位的節點數目較少，而TDAPIT能夠定位的節點相對較多，而且TDAPIT定位時，利用了本身定位就有誤差的已知節點，使得定位出的節點的誤差得到累加，明顯加大了定位誤差。當信標節點比例在20％左右時，兩種算法的定位誤差變化不明顯，此時增加信標節點比例時，TDAP IT略顯優秀，但定位誤差仍然在30％以上，由此可見這種非基于測距的定位方法雖然成本較低、實現簡單，但是定位誤差比較大，而且當信標節點比例達到30％時，定位誤差仍然在30％以上，此時即使增加信標節點的比例也很難改變定位誤差。

結語

本文基于平面中的APIT算法，提出了擴展的三維TDAPIT算法。并在分析APIT誤差來源的基礎上，對TDAPIT進行了相應的改進。擴展的TDAPIT算法能夠較好的在三維空間中實現節點的定位。通過仿真實驗，雖然在網絡的初始階段，TDAPIT的定位覆蓋率在信標節點很少的情況下較高，但這是以增加定位誤差為代價的。
責任編輯；zl