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

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

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