無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法_第1頁
無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法_第2頁
無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法_第3頁
無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法_第4頁
無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法_第5頁
已閱讀5頁,還剩1頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法

無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)受到能耗和低利率的限制。許多節(jié)點(diǎn)不能通過外部方法(gps)獲取位置信息,但沒有位置數(shù)據(jù)的節(jié)點(diǎn)信息通常沒有實(shí)際意義。因此,節(jié)點(diǎn)的定位應(yīng)該通過節(jié)點(diǎn)的合作和位置來計(jì)算。節(jié)點(diǎn)通常隨機(jī)分布在特定的區(qū)域,受節(jié)點(diǎn)分布、消息沖突、障礙物等因素的影響,一些節(jié)點(diǎn)無法滿足位置計(jì)算的條件,而是迷失了自己的節(jié)點(diǎn)。為了解決這個(gè)問題,提出了相對(duì)定位聯(lián)合算法的方法,并將二次集群和三邊定位結(jié)合起來,以提高節(jié)點(diǎn)的效率。1節(jié)點(diǎn)分簇、節(jié)點(diǎn)局部轉(zhuǎn)換與節(jié)點(diǎn)局部失效相對(duì)定位算法的定位過程一般是以網(wǎng)絡(luò)中一部分位置特殊的未知節(jié)點(diǎn)作為參考節(jié)點(diǎn)建立坐標(biāo)系,其余節(jié)點(diǎn)通過消息傳遞和相互協(xié)作獲得自身與參考節(jié)點(diǎn)的相對(duì)位置并計(jì)算相對(duì)坐標(biāo).對(duì)于基于距離的相對(duì)定位算法,由于存在測(cè)距誤差,節(jié)點(diǎn)間大范圍的消息傳遞會(huì)造成誤差累積.將節(jié)點(diǎn)分簇進(jìn)行定位的方法可以減少測(cè)距誤差的累積.分簇算法一般是通過在網(wǎng)絡(luò)中選取多個(gè)參考節(jié)點(diǎn)分別建立局部相對(duì)坐標(biāo)系,其余節(jié)點(diǎn)在獲取局部的相對(duì)坐標(biāo)之后運(yùn)用坐標(biāo)變換或矢量計(jì)算的方法實(shí)現(xiàn)坐標(biāo)統(tǒng)一.分簇方法實(shí)現(xiàn)定位只在局部區(qū)域進(jìn)行消息傳輸,多跳傳遞較少,能減少計(jì)算過程中的累積誤差.但是節(jié)點(diǎn)簇轉(zhuǎn)換過程受到局部區(qū)域失效節(jié)點(diǎn)的影響比較嚴(yán)重,一旦節(jié)點(diǎn)簇內(nèi)協(xié)助轉(zhuǎn)換的節(jié)點(diǎn)失效,將會(huì)導(dǎo)致整個(gè)節(jié)點(diǎn)簇都無法定位.通過二次分簇增加鄰居節(jié)點(diǎn)簇?cái)?shù)量,結(jié)合三邊定位方法增加協(xié)助轉(zhuǎn)換節(jié)點(diǎn)數(shù)量,可以解決轉(zhuǎn)換過程受節(jié)點(diǎn)局部失效影響而導(dǎo)致的節(jié)點(diǎn)簇失效問題.由于大部分節(jié)點(diǎn)簇只需一次轉(zhuǎn)換就實(shí)現(xiàn)最終定位,減少了重復(fù)轉(zhuǎn)換,一方面能降低通信量,另一方面能夠增強(qiáng)算法對(duì)節(jié)點(diǎn)分布的適應(yīng)性.2相對(duì)定位算法2.1跳段距離的計(jì)算法國(guó)巴黎大學(xué)的FaridBenbadis等人提出的GFF算法是一種距離無關(guān)算法.該算法使用類似DV-hop算法中距離矢量路由的思想,通過跳數(shù)估算節(jié)點(diǎn)之間的距離.主要流程是在靠近網(wǎng)絡(luò)邊界的區(qū)域選取三個(gè)點(diǎn)作為參考節(jié)點(diǎn)建立一個(gè)全局相對(duì)坐標(biāo)系.其余節(jié)點(diǎn)接收自身到三個(gè)參考節(jié)點(diǎn)的最小跳數(shù),然后以跳數(shù)代替直線距離使用三邊定位法計(jì)算坐標(biāo).該算法實(shí)現(xiàn)簡(jiǎn)單,定位過程不涉及復(fù)雜運(yùn)算,對(duì)硬件要求較低.不過該算法要求節(jié)點(diǎn)密度較高,并且和DV-hop定位算法一樣,以跳段距離代替直線距離,存在一定的誤差.2.2確定相對(duì)坐標(biāo)系美國(guó)密蘇里大學(xué)哥倫比亞分校的XiaoliLi等人提出的Map-growing算法是基于距離的算法,該算法通過遞歸調(diào)用三邊定位法實(shí)現(xiàn)節(jié)點(diǎn)坐標(biāo)獲取.首先在網(wǎng)絡(luò)中節(jié)點(diǎn)密度較大的區(qū)域選取一個(gè)點(diǎn)作為相對(duì)坐標(biāo)系的坐標(biāo)原點(diǎn),在其鄰居節(jié)點(diǎn)里面選取兩個(gè)點(diǎn)構(gòu)建相對(duì)坐標(biāo)系,選取原則是三點(diǎn)能構(gòu)成一個(gè)良好三角形(三個(gè)內(nèi)角都大于30度).能同時(shí)與這三個(gè)節(jié)點(diǎn)直接通信的未知節(jié)點(diǎn)通過三邊定位方法計(jì)算得出坐標(biāo),其余節(jié)點(diǎn)只要有三個(gè)鄰居節(jié)點(diǎn)已經(jīng)實(shí)現(xiàn)定位,就能夠使用相同的方法計(jì)算坐標(biāo)并將坐標(biāo)信息發(fā)布,直至所有滿足條件的節(jié)點(diǎn)都實(shí)現(xiàn)定位.該算法通信量小,在節(jié)點(diǎn)密集的區(qū)域能獲得較高的節(jié)點(diǎn)定位覆蓋率,并且對(duì)節(jié)點(diǎn)分布沒有特殊要求.但是受到測(cè)距誤差累積的影響,遠(yuǎn)離坐標(biāo)原點(diǎn)的節(jié)點(diǎn)定位誤差較大.2.3聚類pet算法美國(guó)仁斯利爾理工學(xué)院RajagopalIyengar等人提出的聚類SPA算法是典型的分簇定位算法,算法采用TOA測(cè)距方式,定位過程分局部坐標(biāo)建立階段和全局坐標(biāo)轉(zhuǎn)換階段兩步.算法開始運(yùn)行之后,通過自身攜帶的定時(shí)器選取主節(jié)點(diǎn),主節(jié)點(diǎn)一跳以內(nèi)的其它節(jié)點(diǎn)聲明為該主節(jié)點(diǎn)的從節(jié)點(diǎn).主節(jié)點(diǎn)隨機(jī)選擇互為鄰居節(jié)點(diǎn)的兩個(gè)從節(jié)點(diǎn)建立局部坐標(biāo)系,并計(jì)算得到其他從節(jié)點(diǎn)的局部坐標(biāo).在坐標(biāo)轉(zhuǎn)換階段,主節(jié)點(diǎn)ID號(hào)大的節(jié)點(diǎn)簇向ID號(hào)比它小的相鄰節(jié)點(diǎn)簇轉(zhuǎn)換,最終以ID號(hào)最小的主節(jié)點(diǎn)為原點(diǎn)建立全局坐標(biāo)系.聚類SPA算法通過分簇建立局部坐標(biāo),使得執(zhí)行坐標(biāo)變換的是每個(gè)節(jié)點(diǎn)簇,相比于每個(gè)節(jié)點(diǎn)都需要參與轉(zhuǎn)換的算法,通信量和計(jì)算量得到了降低,并減少了測(cè)距誤差的累積.但是該算法對(duì)節(jié)點(diǎn)密度和節(jié)點(diǎn)分布都有較高要求,在節(jié)點(diǎn)密度不高且分布不均勻的區(qū)域,失效節(jié)點(diǎn)較多.相對(duì)定位算法無需錨節(jié)點(diǎn),適合于遠(yuǎn)距離信號(hào)接收受限或有障礙物阻隔的區(qū)域.但是現(xiàn)有相對(duì)定位算法往往需要在高節(jié)點(diǎn)密度和較規(guī)則的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中才能獲得比較好的定位效果,一定程度上限制了相對(duì)定位算法的應(yīng)用.3節(jié)點(diǎn)合作算法針對(duì)現(xiàn)有算法對(duì)節(jié)點(diǎn)密度和節(jié)點(diǎn)分布要求較高的情況,提出通過節(jié)點(diǎn)協(xié)作分簇方式實(shí)現(xiàn)定位,以降低節(jié)點(diǎn)密度和節(jié)點(diǎn)分布對(duì)定位結(jié)果的影響.3.1節(jié)點(diǎn)分布不均勻?qū)?jié)點(diǎn)定位覆蓋率的影響對(duì)聚類SPA算法節(jié)點(diǎn)失效進(jìn)行分析.在局部坐標(biāo)定位階段,在定時(shí)器計(jì)時(shí)完成之后生成節(jié)點(diǎn)簇,簇的主節(jié)點(diǎn)為坐標(biāo)原點(diǎn),收到兩個(gè)主節(jié)點(diǎn)聲明的節(jié)點(diǎn)為邊界節(jié)點(diǎn).局部坐標(biāo)系中任一個(gè)點(diǎn)都需要除原點(diǎn)以外的兩個(gè)已知局部坐標(biāo)的鄰居節(jié)點(diǎn)才能計(jì)算自身坐標(biāo),將無法滿足該計(jì)算條件的從節(jié)點(diǎn)記作第一類失效節(jié)點(diǎn).由于邊界節(jié)點(diǎn)處于節(jié)點(diǎn)簇邊緣地帶,更容易成為第一類失效節(jié)點(diǎn).在坐標(biāo)轉(zhuǎn)換階段,受到節(jié)點(diǎn)分布和第一類失效節(jié)點(diǎn)的影響,一些鄰居節(jié)點(diǎn)簇?zé)o法找到兩個(gè)以上的有效邊界節(jié)點(diǎn)(獲得局部坐標(biāo)的邊界節(jié)點(diǎn))以實(shí)現(xiàn)轉(zhuǎn)換.節(jié)點(diǎn)簇轉(zhuǎn)換一旦失敗,該簇的從節(jié)點(diǎn)都會(huì)成為失效節(jié)點(diǎn),將這類失效節(jié)點(diǎn)記作第二類失效節(jié)點(diǎn).由于以簇為單位,第二類失效節(jié)點(diǎn)比第一類失效節(jié)點(diǎn)數(shù)量多,對(duì)節(jié)點(diǎn)定位覆蓋率有很大影響.由于通過定時(shí)器確定主節(jié)點(diǎn)是隨機(jī)的,程序每次運(yùn)行都會(huì)產(chǎn)生不同的主節(jié)點(diǎn).為了驗(yàn)證主節(jié)點(diǎn)位置分布的不同對(duì)聚類SPA算法的影響,以及第一類失效節(jié)點(diǎn)和最終定位節(jié)點(diǎn)數(shù)量的關(guān)系,在節(jié)點(diǎn)分布不變的情況下,重復(fù)運(yùn)行程序10次,得出第一類失效節(jié)點(diǎn)與節(jié)點(diǎn)定位覆蓋率的關(guān)系,如表1所示.運(yùn)行環(huán)境設(shè)定為20m×20m的區(qū)域上隨機(jī)布置100個(gè)節(jié)點(diǎn),節(jié)點(diǎn)密度為0.25,節(jié)點(diǎn)通信半徑為3m.10次運(yùn)行結(jié)果顯示,100個(gè)節(jié)點(diǎn)中第一類失效節(jié)點(diǎn)最多占到16%,但是由于其中大部分,甚至全部都是邊界節(jié)點(diǎn)失效,導(dǎo)致后一步的坐標(biāo)變換難以完成,再加上節(jié)點(diǎn)分布不均勻?qū)λ惴ǖ挠绊?使得節(jié)點(diǎn)定位覆蓋率偏低,最多不超過35%.綜合分析可知,用于協(xié)助轉(zhuǎn)換的有效邊界節(jié)點(diǎn)數(shù)量不足是定位結(jié)果不理想的主要原因.在局部坐標(biāo)建立階段盡量減少第一類失效邊界節(jié)點(diǎn)數(shù)量,并在坐標(biāo)轉(zhuǎn)換階段增加新的邊界節(jié)點(diǎn)有助于減少失效節(jié)點(diǎn)數(shù)量,提高節(jié)點(diǎn)定位覆蓋率.3.2局部定位功能基于上述的分析,提出一種以聚類SPA算法分簇思想為基礎(chǔ),通過節(jié)點(diǎn)協(xié)作定位,輔以三邊定位實(shí)現(xiàn)節(jié)點(diǎn)之間相對(duì)坐標(biāo)獲取的節(jié)點(diǎn)協(xié)作分布式相對(duì)定位算法ADRP(AssistantandDistributedRelativePositioningAlgorithm).算法使用TOA技術(shù)測(cè)量鄰居節(jié)點(diǎn)間距,分局部坐標(biāo)建立階段和全局坐標(biāo)轉(zhuǎn)換階段兩步.(1)局部坐標(biāo)建立階段.使用定時(shí)器確定主節(jié)點(diǎn)及節(jié)點(diǎn)簇,收到兩個(gè)以上主節(jié)點(diǎn)聲明的從節(jié)點(diǎn)為邊界節(jié)點(diǎn).圖1為節(jié)點(diǎn)分簇示意圖,O為主節(jié)點(diǎn),M為距離主節(jié)點(diǎn)O最近的從節(jié)點(diǎn),N是M的鄰居節(jié)點(diǎn)中距離O點(diǎn)最近的從節(jié)點(diǎn).將M點(diǎn)和N點(diǎn)作為輔助節(jié)點(diǎn)構(gòu)建局部坐標(biāo)系MON,如圖1所示,圖中實(shí)線連接的兩點(diǎn)距離可測(cè)距得到,虛線則表示所連接的兩點(diǎn)不是鄰居節(jié)點(diǎn).在局部區(qū)域內(nèi),節(jié)點(diǎn)分布相對(duì)規(guī)則,以距離主節(jié)點(diǎn)最近的點(diǎn)確定x軸和y軸,實(shí)現(xiàn)簡(jiǎn)單,且有利于覆蓋大部分從節(jié)點(diǎn).圖中節(jié)點(diǎn)J同時(shí)與M和N為鄰居節(jié)點(diǎn),通過余弦公式可得θ1、θ2、θ3,根據(jù)三個(gè)角之間關(guān)系以及主節(jié)點(diǎn)O與節(jié)點(diǎn)J之間的距離dOJ求出未知節(jié)點(diǎn)J在局部坐標(biāo)系中的坐標(biāo)值,具體如式(1).對(duì)于與節(jié)點(diǎn)M和節(jié)點(diǎn)N都不是鄰居節(jié)點(diǎn)的從節(jié)點(diǎn)需要在已經(jīng)獲取坐標(biāo)的節(jié)點(diǎn)中重新取兩個(gè)點(diǎn)進(jìn)行定位.?????x=dOJ×cosθ2θ1=|θ2?θ3|?y=dOJ×sinθ2θ1≠|(zhì)θ2?θ3|?y=?dOJ×sinθ2(1){x=dΟJ×cosθ2θ1=|θ2-θ3|?y=dΟJ×sinθ2θ1≠|(zhì)θ2-θ3|?y=-dΟJ×sinθ2(1)局部坐標(biāo)建立完成之后,獲得局部坐標(biāo)的從節(jié)點(diǎn)組成集合ue6e6(MON).沒有獲得局部坐標(biāo)的節(jié)點(diǎn)分兩種情況,第一種是只有一個(gè)鄰居節(jié)點(diǎn)計(jì)算得出局部坐標(biāo),第二種是沒有鄰居節(jié)點(diǎn)實(shí)現(xiàn)局部定位.對(duì)于第一種情況,可以通過排除法定位.例如在圖1中,節(jié)點(diǎn)P的鄰居節(jié)點(diǎn)中只有節(jié)點(diǎn)L獲得局部坐標(biāo),由于條件不足,通過計(jì)算出現(xiàn)P和P’兩個(gè)待定結(jié)果,二者以O(shè)L為中軸相互對(duì)稱.由于在集合ue6e6(MON)內(nèi)只有節(jié)點(diǎn)L和主節(jié)點(diǎn)O在節(jié)點(diǎn)P通信范圍內(nèi),若有第三個(gè)節(jié)點(diǎn)能與待定位置通信,可將該位置排除.ue6e6(MON)中的節(jié)點(diǎn)將兩個(gè)待定位置分別進(jìn)行計(jì)算,通過節(jié)點(diǎn)M可將錯(cuò)誤結(jié)果P’排除,從而節(jié)點(diǎn)P的局部坐標(biāo)得以確定,同時(shí)節(jié)點(diǎn)P也加入ue6e6(MON)協(xié)助其余從節(jié)點(diǎn)實(shí)現(xiàn)定位,以減少第一類失效節(jié)點(diǎn)的產(chǎn)生.(2)全局網(wǎng)絡(luò)坐標(biāo)轉(zhuǎn)換.當(dāng)所有的局部坐標(biāo)系建立完成之后,相鄰節(jié)點(diǎn)簇?cái)?shù)量最多的節(jié)點(diǎn)簇聲明為主簇,其主節(jié)點(diǎn)聲明為全局網(wǎng)絡(luò)的坐標(biāo)原點(diǎn),同時(shí)主簇內(nèi)所有獲得局部坐標(biāo)的從節(jié)點(diǎn)升級(jí)為已定位節(jié)點(diǎn),其他的節(jié)點(diǎn)簇根據(jù)距離主簇的遠(yuǎn)近逐步完成坐標(biāo)變換,主要分為兩步.第一步:對(duì)于與主簇相鄰,并與主簇有兩個(gè)以上有效邊界節(jié)點(diǎn)的節(jié)點(diǎn)簇,可以利用文獻(xiàn)中提出的方法向主簇進(jìn)行坐標(biāo)變換,其它的節(jié)點(diǎn)簇等待轉(zhuǎn)換消息.完成坐標(biāo)變換的節(jié)點(diǎn)簇聲明為已定位簇,同時(shí)更新坐標(biāo).為了使無法直接進(jìn)行坐標(biāo)轉(zhuǎn)換的節(jié)點(diǎn)簇實(shí)現(xiàn)定位,將已定位的節(jié)點(diǎn)簇與主簇合并,進(jìn)行二次分簇.如圖2所示,節(jié)點(diǎn)簇k和n實(shí)現(xiàn)定位以后與主簇i結(jié)合,形成簇集A.在A中邊界節(jié)點(diǎn)使用轉(zhuǎn)換以后的新坐標(biāo)向外發(fā)布坐標(biāo)消息,其余未定位簇只要與簇集A有兩個(gè)有效邊界節(jié)點(diǎn),即可實(shí)現(xiàn)定位.在圖2中,節(jié)點(diǎn)p是節(jié)點(diǎn)簇m與節(jié)點(diǎn)簇k的有效邊界節(jié)點(diǎn),節(jié)點(diǎn)q是節(jié)點(diǎn)簇m與節(jié)點(diǎn)簇n的有效邊界節(jié)點(diǎn),這樣便可通過p和q協(xié)助節(jié)點(diǎn)簇m定位.p和q發(fā)布的坐標(biāo)信息是已經(jīng)更新的新坐標(biāo),所以簇m將直接和主簇進(jìn)行坐標(biāo)變換,這樣只需要轉(zhuǎn)換一次即可完成最終定位,減少了計(jì)算量和多次坐標(biāo)轉(zhuǎn)換帶來的計(jì)算累積誤差.轉(zhuǎn)換完成后,節(jié)點(diǎn)簇m也加入簇集A中,協(xié)助相鄰分簇定位.二次分簇方法使得未知節(jié)點(diǎn)簇可以通過多個(gè)相鄰的已定位簇協(xié)作定位,減少了失效邊界節(jié)點(diǎn)對(duì)定位的影響.分簇轉(zhuǎn)換過程需要傳遞大量的消息,采用二次分簇方法可以減少轉(zhuǎn)換次數(shù),達(dá)到降低通信量的目的.在圖3所示的局部網(wǎng)絡(luò)拓?fù)渲?4號(hào)節(jié)點(diǎn)簇和1、3號(hào)節(jié)點(diǎn)簇相鄰,5號(hào)節(jié)點(diǎn)簇和2、3號(hào)節(jié)點(diǎn)簇相鄰,并假設(shè)1號(hào)節(jié)點(diǎn)簇首先實(shí)現(xiàn)定位.聚類SPA算法是以主節(jié)點(diǎn)ID號(hào)由大到小轉(zhuǎn)換為原則,最終所有節(jié)點(diǎn)的相對(duì)坐標(biāo)都應(yīng)該以1號(hào)節(jié)點(diǎn)簇主節(jié)點(diǎn)為原點(diǎn),每次轉(zhuǎn)換中各簇需要向ID號(hào)比它小的鄰居簇轉(zhuǎn)換一次.以5號(hào)節(jié)點(diǎn)簇為例,在第一次轉(zhuǎn)換中,分別向3號(hào)和2號(hào)轉(zhuǎn)換一次,以此類推,圖3的局部網(wǎng)絡(luò)需要8次轉(zhuǎn)換才能完成定位;并且1號(hào)節(jié)點(diǎn)簇在不同位置所需轉(zhuǎn)換的次數(shù)不同,最差的情況是高ID的主節(jié)點(diǎn)需要向局部區(qū)域內(nèi)每個(gè)ID號(hào)比它低的主節(jié)點(diǎn)都轉(zhuǎn)換一次才能實(shí)現(xiàn)定位,進(jìn)一步增加了通信量.二次分簇方法所采取的轉(zhuǎn)換順序是:4向1轉(zhuǎn)換,3向4轉(zhuǎn)換,5向3轉(zhuǎn)換,2向5轉(zhuǎn)換.經(jīng)過4次轉(zhuǎn)換即可實(shí)現(xiàn)定位,而且1號(hào)節(jié)點(diǎn)簇的位置變化只會(huì)導(dǎo)致轉(zhuǎn)換順序的不同,轉(zhuǎn)換次數(shù)不會(huì)改變.二次分簇方法始終以最少轉(zhuǎn)換次數(shù)實(shí)現(xiàn)定位,減少了通信量和計(jì)算量,并使算法具有更好的穩(wěn)定性.第二步:完成第一步之后,網(wǎng)絡(luò)中還沒有實(shí)現(xiàn)定位的未定位簇可分為與簇集A有一個(gè)有效邊界節(jié)點(diǎn)的C簇,和與簇集A沒有有效邊界節(jié)點(diǎn)的D簇.節(jié)點(diǎn)簇發(fā)布聲明消息,相互之間能取得聯(lián)系的未定位簇構(gòu)成節(jié)點(diǎn)域.各節(jié)點(diǎn)域中主節(jié)點(diǎn)ID號(hào)最小的C簇聲明為原點(diǎn)簇,與原點(diǎn)簇相鄰且具有兩個(gè)以上有效邊界節(jié)點(diǎn)的未定位簇直接向原點(diǎn)簇進(jìn)行轉(zhuǎn)換.對(duì)于無法直接轉(zhuǎn)換的節(jié)點(diǎn)簇需要升級(jí)新的邊界節(jié)點(diǎn)協(xié)助轉(zhuǎn)換.節(jié)點(diǎn)簇中與從節(jié)點(diǎn)相鄰的已經(jīng)在主簇內(nèi)實(shí)現(xiàn)局部定位的節(jié)點(diǎn)數(shù)量記為z.如果z≥3,則該從節(jié)點(diǎn)可以通過三邊定位法計(jì)算得出自身在主簇中的局部坐標(biāo),進(jìn)而升級(jí)為新的邊界節(jié)點(diǎn)協(xié)助節(jié)點(diǎn)簇轉(zhuǎn)換.節(jié)點(diǎn)簇轉(zhuǎn)換完成后加入簇集B,并使用二次分簇的方法將簇集B擴(kuò)展,如圖4所示.最終形成的簇集B只要包括兩個(gè)C簇即可完成定位,進(jìn)一步減少失效節(jié)點(diǎn).通過節(jié)點(diǎn)協(xié)作和升級(jí)新的邊界節(jié)點(diǎn)的定位方式,使得各局部坐標(biāo)系受失效邊界節(jié)點(diǎn)的影響減小,同時(shí)減少了第二類失效節(jié)點(diǎn)的數(shù)量,提高了節(jié)點(diǎn)定位覆蓋率,增強(qiáng)了算法對(duì)網(wǎng)絡(luò)拓?fù)渥兓倪m應(yīng)性.4節(jié)點(diǎn)位置變化的適應(yīng)性利用NS-2網(wǎng)絡(luò)仿真軟件,從通信量、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適應(yīng)性和節(jié)點(diǎn)定位覆蓋率三個(gè)方面分析比較ADRP與聚類SPA算法.圖5和圖6是二者分別在30m×30m和40m×40m區(qū)域內(nèi)的通信量比較,環(huán)境設(shè)定節(jié)點(diǎn)均勻分布,通信半徑為2m,節(jié)點(diǎn)之間通信無障礙.圖5和圖6表明,ADRP算法的通信量低于聚類SPA算法,并且隨著節(jié)點(diǎn)數(shù)量的增加,差距逐漸明顯.由于ADRP算法在坐標(biāo)轉(zhuǎn)換階段需要轉(zhuǎn)換的次數(shù)少,減少了多余轉(zhuǎn)換產(chǎn)生的通信量,隨著節(jié)點(diǎn)簇?cái)?shù)量增多,二次分簇方法優(yōu)勢(shì)逐漸明顯,通信量的差距逐漸加大.圖7是兩種算法在主節(jié)點(diǎn)位置適應(yīng)性方面的對(duì)比.設(shè)定節(jié)點(diǎn)區(qū)域?yàn)?0m×20m,節(jié)點(diǎn)通信半徑3m.在網(wǎng)絡(luò)節(jié)點(diǎn)分布不變的情況下,對(duì)兩種算法分別運(yùn)行10次以對(duì)比節(jié)點(diǎn)定位覆蓋率.由于主節(jié)點(diǎn)由定時(shí)器隨機(jī)選擇,每次運(yùn)行時(shí)主節(jié)點(diǎn)位置都會(huì)有所變化,通過圖7的實(shí)驗(yàn)結(jié)果可以得出兩種算法對(duì)主節(jié)點(diǎn)位置變化的適應(yīng)性.區(qū)域設(shè)定隨機(jī)分布100個(gè)節(jié)點(diǎn),節(jié)點(diǎn)密度為0.25,網(wǎng)絡(luò)連通度為6,圖中橫軸為執(zhí)行次數(shù).圖8是在節(jié)點(diǎn)密度較低時(shí)節(jié)點(diǎn)定位覆蓋率的對(duì)比,節(jié)點(diǎn)區(qū)域和通信半徑與圖7相同,每一個(gè)節(jié)點(diǎn)密度下隨機(jī)運(yùn)行20次取均值以減少主節(jié)點(diǎn)位置變動(dòng)的影響.如圖7所示,ADRP算法的節(jié)點(diǎn)定位覆蓋率是聚類SPA的兩倍左右,而且曲線波動(dòng)不大,性能相對(duì)穩(wěn)定.聚類SPA算法受到主節(jié)點(diǎn)位置變動(dòng)的影響較大,曲線波動(dòng)嚴(yán)重,且定位節(jié)點(diǎn)數(shù)量不多.聚類SPA算法由于節(jié)點(diǎn)簇之間單獨(dú)進(jìn)行轉(zhuǎn)換,轉(zhuǎn)換過程是否能順利進(jìn)行很大程度上取決于主節(jié)點(diǎn)的位置,從而導(dǎo)致曲線較大的波動(dòng).ADRP算法采取不同主節(jié)點(diǎn)間不斷合并、相互協(xié)作的定位方式,主節(jié)點(diǎn)位置變動(dòng)對(duì)算法穩(wěn)定性的影響較小.圖8以節(jié)點(diǎn)密度對(duì)算法性能的影響為出發(fā)點(diǎn),不考慮主節(jié)點(diǎn)位置變動(dòng)對(duì)算法產(chǎn)生的影響,為了獲得較為平均的結(jié)果,在每個(gè)節(jié)點(diǎn)密度上都經(jīng)過多次運(yùn)行,因此所得曲線較為平滑.聚類SPA算法對(duì)應(yīng)的節(jié)點(diǎn)定位覆蓋率較低,并在有些位置出現(xiàn)了一些波動(dòng).相比之下,ADRP算法對(duì)應(yīng)的曲線很少出現(xiàn)大的跳動(dòng),在節(jié)點(diǎn)密度較低的情況下,ADRP算法也能實(shí)現(xiàn)大部分節(jié)點(diǎn)定位,節(jié)點(diǎn)定位覆蓋率平均值在75%

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論