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

1．3．3 TDAPIT算法流程

TDAPIT算法流程步驟如下：

①節(jié)點(diǎn)部署完成后，網(wǎng)絡(luò)初始化配置。信標(biāo)節(jié)點(diǎn)向網(wǎng)絡(luò)廣播消息(消息應(yīng)該包含信標(biāo)節(jié)點(diǎn)的ID、位置坐標(biāo)等信息)，而未知節(jié)點(diǎn)監(jiān)聽信標(biāo)節(jié)點(diǎn)的消息。此階段未知節(jié)點(diǎn)應(yīng)隨時更新接收到的信息，以防止岡網(wǎng)絡(luò)的拓?fù)渥兓斐傻恼`差影響。

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

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

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

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

1．3．4 算法分析

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

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

1．4 算法流程

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

2 實(shí)驗(yàn)仿真與評估

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

2．1 定位覆蓋率

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