基于APIT的無線傳感器網(wǎng)絡(luò)三維定位算法
①節(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é)點只負責監(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ù)男в谩kS著信標節(jié)點比例的上升,TDAPIT的定位覆蓋率更是明顯地上升,在信標節(jié)點比例為20%左右時,定位覆蓋率就達到了90%以上。在這以后,信標節(jié)點比例的增加對定位覆蓋率的影響大大降低。這是因為在算法中采用了循環(huán)擴散的思想,即將已知節(jié)點當做信標節(jié)點來實現(xiàn)定位,最大限度地減少了不良節(jié)點的數(shù)目。在信標節(jié)點比例達到30%左右時,APIT算法的定位覆蓋率在85%左右,而且仍然還有上升的趨勢,說明APIT算法對信標節(jié)點比例的依賴程度比較高。
電容式觸摸屏相關(guān)文章:電容式觸摸屏原理
評論