無線傳感器網絡節點協作分布式相對定位算法

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