基于A(yíng)PIT的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )三維定位算法

1．3．3 TDAPIT算法流程

TDAPIT算法流程步驟如下：

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

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

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

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

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

1．3．4 算法分析

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

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

1．4 算法流程

整個(gè)算法的流程如圖2所示。

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

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

2．1 定位覆蓋率

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