基于APIT的無線傳感器網(wǎng)絡(luò)三維定位算法

1．3．3 TDAPIT算法流程

TDAPIT算法流程步驟如下：

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

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

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

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

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

1．3．4 算法分析

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

對于未知節(jié)點監(jiān)聽到的信標節(jié)點，不能構(gòu)成四面體相交的，利用球體重合區(qū)域的質(zhì)心作為未知節(jié)點的坐標。如果未知節(jié)點監(jiān)聽到的信標節(jié)點數(shù)目較少，可以利用已經(jīng)定位完畢的節(jié)點來對未知節(jié)點進行定位。在求解球體重合區(qū)域的質(zhì)心時，可以利用網(wǎng)格掃面算法，計算量較大、誤差較??；也可以利用四面體質(zhì)心掃面算法，計算量較小但是誤差較大，根據(jù)實際情況予以選擇。

1．4 算法流程

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

2 實驗仿真與評估

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

2．1 定位覆蓋率

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