基于APIT的無線傳感器網絡三維定位算法

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算法對信標節點比例的依賴程度比較高。