基于dv-oh的錨節(jié)點位置校正

基于dv-oh的錨節(jié)點位置校正

0節(jié)點定位算法無線傳感器網絡（無線傳感器網絡）集成了傳感器技術、嵌入式控制技術、無線傳感器網絡技術、分布式數(shù)據處理技術和電子技術。這是目前的一個新興和熱點研究領域。節(jié)點定位是無線傳感器網絡的關鍵應用支撐技術,對于大多數(shù)應用來說,帶有位置信息的傳感數(shù)據才具有實際意義,隨著無線傳感器網絡技術的不斷進步,會出現(xiàn)更多基于位置信息的協(xié)議和應用。然而WSN節(jié)點的計算和通信能力都十分有限而且大量節(jié)點的部署往往無法人為控制,因此設計高效的節(jié)點定位算法就顯得十分重要。非基于測距(range-free)的算法原理簡單,但是定位比較粗糙,而目前幾乎所有節(jié)點的無線射頻模塊都具有獲取信號接收強度指示值(ReceivedSignalStrengthIndex,RSSI)的能力,在range-free算法基礎上使用測距技術對節(jié)點估計位置進一步求精是一種比較有效的定位機制,近年來不少學者也將各種智能計算方法引入到WSN的節(jié)點定位問題中來,設計綜合的定位算法是一種新的思路。1智能算法的改進文獻利用距離矢量路由的概念提出APS系列算法,其中的DV-Hop成為range-free算法的典型,在之后的研究中被廣泛利用。文獻提出了一種Malguki算法,該算法中的強迫矢量的構建方式與本文所提出的位置校正矢量(LocationCorrectionVector,LCV)相似,但是前者對網絡通信能力和錨節(jié)點的分布具有很強的依賴性,而且單個節(jié)點計算量過大;而后者充分利用了所有鄰居節(jié)點之間的測距信息,算法具有很好的彈性和擴展性。文獻都將智能優(yōu)化算法引入到WSN的定位問題中,其中前者使用了實數(shù)編碼的遺傳算法,該算法只有在網絡連通度很高的情況下才能取得較為理想的定位精度,而且遺傳算法的計算量對于節(jié)點來說有些偏大;后者提出一種基于模擬退火算法的定位方法,系統(tǒng)的計算量比較大,耗時比較長。綜上所述,已有的這些改進對于算法性能普遍欠缺綜合考慮,對于把高效節(jié)能放在重要位置的WSN來說還有待改進。本文提出一種集合了range-free算法、測距技術和智能優(yōu)化算法的節(jié)點定位綜合算法,并通過仿真實驗證明它具有優(yōu)良的定位性能。2軸分類質控算法本文提出一種基于位置校正矢量的節(jié)點定位綜合算法,首先用DV-Hop算法取得粗糙的節(jié)點位置估計,然后對鄰居節(jié)點間RSSI的測量距離與估計位置間的計算距離進行比較,構建一個位置校正矢量(只有方向);以各錨節(jié)點為簇頭,把未知節(jié)點以最近鄰原則分簇,錨節(jié)點以最小化簇內距離誤差總和的原則,利用改進的粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)求得簇內每個節(jié)點的校正步長Step,未知節(jié)點把自身的LCV與Step相乘即得到位置校正值,節(jié)點當前的估計位置加上這個位置校正值就得到新的估計位置;考慮到簇內最優(yōu)化結果并不能使全局網絡最優(yōu)化,在每個簇的邊緣節(jié)點與鄰簇的邊緣節(jié)點之間構建附加位置校正矢量,然后由簇頭利用自身的位置和測距信息得到附加校正步長,將附加LCV與附加Step的乘積作為簇邊緣節(jié)點的位置調整附加值,也就是調整簇與簇的相對位置,以避免局部最優(yōu)化。2.1節(jié)點s的合成lcv本文引入位置校正矢量的概念,目的在于充分利用由測距信息得到的節(jié)點間相對位置關系,來校正節(jié)點的估計位置。未知節(jié)點通過range-free算法得到自身的估計位置,同時可以通過通信獲取鄰居節(jié)點的估計位置,把兩個估計位置之間的距離記為“計算距離”;而未知節(jié)點通過接收鄰居節(jié)點發(fā)來的數(shù)據包可以獲得信號強度值RSSI,從而得到兩者之間的“測量距離”。引入位置校正矢量的目的就是通過調整節(jié)點的位置,盡可能縮小計算距離與測量距離之間的差距,因此LCV的每個分量的方向由未知節(jié)點指向某個鄰居節(jié)點,分量大小為對應的計算距離減去測量距離。從物理意義上來講,當兩個相鄰未知節(jié)點之間的距離計算值小于測量值時,用背向鄰居節(jié)點的校正矢量來拉遠兩個節(jié)點之間的估計位置;反之,則用指向鄰居節(jié)點的校正矢量來拉近兩個節(jié)點之間的估計位置。假設節(jié)點S通信范圍內有N個鄰居節(jié)點,節(jié)點自身的估計位置為PS=(xS,yS),N個鄰居節(jié)點的估計位置為Pi=(xi,yi),節(jié)點S獲得的N個測距值為dmi(i=1,2,…,N)。那么節(jié)點S與第i個鄰居節(jié)點的計算距離為dci:節(jié)點S與第i個鄰居節(jié)點的差異值可以表示為diffi:diffi=dci-dmi(2)節(jié)點S與第i個鄰居節(jié)點差異值的矢量方向表示為vi:vi→=pSpi?→?∥pSpi?→?∥(3)vi→=pSpi→∥pSpi→∥(3)因此,節(jié)點S的合成LCV為VS:VS?→=∑idiffi×vi→VS→=∑idiffi×vi→;i=1,2,…,N(4)圖1中,實線表示節(jié)點實際位置,虛線表示節(jié)點估計位置,細箭頭是校正矢量的分量,粗箭頭表示合成的校正矢量。2.2計算每相線的方法來計算由于每個未知節(jié)點同時調整自身的位置,因此LCV只能給出節(jié)點位置的調整方向,而沿這個方向移動的距離(我們稱之為校正步長)需要通過另外的方法來計算。如果直接從全局網絡最優(yōu)化的角度計算所有節(jié)點的校正步長,不符合無線傳感器網絡分布式計算的原則,而如果由每個節(jié)點單獨計算自身的校正步長,那么計算量又太大而且不能兼顧其他節(jié)點的位置調整情況,因此我們考慮使用分簇的計算方式來獲取校正步長。同時,考慮到算法的盡可能簡單化和錨節(jié)點的計算通信能力比較強,將每個錨節(jié)點作為簇頭,未知節(jié)點以自身的當前估計位置為準,加入距離最近的錨節(jié)點所在的簇。2.2.1目標函數(shù)的建立分簇后,以簇內網絡整體位置最優(yōu)化為目標來計算簇內節(jié)點的校正步長。位置校正矢量的作用是使簇內所有鄰居節(jié)點之間經過位置校正后,計算距離與測量距離差值的總和最小化,因此求校正步長的問題可以描述為一個多元函數(shù)最小化問題。假設簇內有Nm個未知節(jié)點,它們的估計位置分別為pmi=(xmi,ymi),LCV分別為Vmi?→?(i=1,2???Nm)Vmi→(i=1,2???Νm),待求步長為Step。問題的目標函數(shù)可以表示為:F(Step)=∑ijdisij≤R|∥p′mip′mj?→????∥?dmij|(5)F(Step)=∑ijdisij≤R|∥p′mip′mj→∥-dmij|(5)其中:p′mi=pmi+Step×Vmi?→??p′mj=pmj+Step×Vmj?→??dmijp′mi=pmi+Step×Vmi→?p′mj=pmj+Step×Vmj→?dmij為簇內節(jié)點i,j之間的RSSI距離測量值,disij為簇內節(jié)點i,j之間的實際距離,R為節(jié)點的通信半徑。由于這個目標函數(shù)是帶有絕對值的高次函數(shù),形式比較復雜,本文引入粒子群算法來求解這個最小化問題。2.2.2適應度函數(shù)的建立PSO是一種群智能優(yōu)化算法,粒子通過跟蹤兩個“極值”來更新自己,一個是粒子本身所找到的最優(yōu)解p_Best,另一個是整個種群目前找到的最優(yōu)解g_Best。PSO很多方面與遺傳算法相似,但與遺傳算法比較,在大多數(shù)情況下,所有的粒子可能更快地收斂于最優(yōu)解,而且PSO容易實現(xiàn),并且沒有許多參數(shù)需要調整,計算量很小。在本文所述的定位算法中,PSO用來求解校正步長,PSO粒子的長度等于簇內未知節(jié)點的個數(shù),每一維分量對應一個節(jié)點的校正步長,將前文提到的以校正步長為自變量的目標函數(shù)作為適應度函數(shù)?？紤]到WSN節(jié)點的特殊情況,為了減少算法的計算量和運算時間,本文對PSO算法作了改進:在每一次迭代計算粒子的速度之前,比較所有粒子的p_Best,將離最優(yōu)解最遠的粒子從種群中去除,這樣從整個PSO算法的角度來說計算量有明顯下降。2.3打造附加位置校正由于上述的最優(yōu)化過程是在各個簇內進行,簇內的距離誤差總和最小只能使簇內節(jié)點的相對位置在一定程度上最優(yōu)化,而并不意味著全局網絡所有節(jié)點的位置實現(xiàn)了最優(yōu)化,可能存在簇間距離誤差反而增大的問題。因此考慮對簇與簇之間的位置進行調整,具體方法如下。由簇的每個邊緣節(jié)點查找所有不屬于本簇但是在自身通信半徑內的所有鄰居節(jié)點(也就是鄰簇的邊緣節(jié)點),利用它們之間的計算距離和測量距離構建一個附加位置校正矢量。由于簇頭(錨節(jié)點)的位置在一定程度上能反映整個簇在全局網絡中的位置,因此我們利用錨節(jié)點的自身信息來計算附加位置校正矢量的步長:首先計算錨節(jié)點的估計位置與其真實位置的誤差距離,再利用錨節(jié)點與其鄰居節(jié)點的測距值構建錨節(jié)點的位置校正矢量,將誤差距離值除以這個位置校正矢量模值得到的結果作為附加校正步長,簇內所有邊緣節(jié)點都采用這個附加校正步長調整自身位置,以減小簇與簇的相對位置誤差,避免了陷入局部最優(yōu)。3在網絡連通度為10時，節(jié)點的跳數(shù)閾值選取在對基于LCV的節(jié)點定位綜合算法仿真之前,本文先對DV-Hop算法的錨節(jié)點數(shù)和跳數(shù)閾值的選取作了研究。Matlab仿真環(huán)境設置:在邊長為100的正方形區(qū)域內隨機均勻分布100個未知節(jié)點,節(jié)點的有效通信半徑為20,網絡的連通度約為10(連通度是指平均每個節(jié)點通信半徑內的鄰居節(jié)點個數(shù),網絡的連通度反映了網絡的密度)。仿真中使用的RSSI測量距離為真實距離加上一個高斯隨機誤差。本文所說的定位誤差是指整個網絡所有節(jié)點平均位置誤差與通信半徑的比值,比如20%的定位誤差,即節(jié)點平均位置誤差為20×20%=4。錨節(jié)點的個數(shù)分別選取9,16,25,對應的錨節(jié)點密度分別為8.2%,13.8%,20%,錨節(jié)點和未知節(jié)點一樣,也是隨機均勻分布在網絡中。跳數(shù)閾值的選擇范圍為5到10,定位誤差的實驗結果如表1和圖2。對實驗結果的圖表進行分析,可以得出以下幾個結論:1)在連通度為10的情況下,跳數(shù)閾值為7是最佳選擇,且與錨節(jié)點密度無關。2)跳數(shù)閾值增大不一定使定位誤差下降,遠處錨節(jié)點的信息對定位不一定起正面作用。3)錨節(jié)點達到一定密度時,再增加錨節(jié)點對定位精度的提高幫助很小,因此無限制地增加錨節(jié)點是沒有意義的。以上三點結論,反映了以DV-Hop為典型的基于距離矢量路由的定位算法的特點,對于選取這種類型定位算法的參數(shù)具有明確的指導意義。后面的仿真實驗以這個實驗結果為前提,即跳數(shù)閾值取7,錨節(jié)點數(shù)為16,錨節(jié)點比例為13.8%,在如上參數(shù)的條件下,DV-Hop算法仿真的定位誤差為39.34%,仿真結果如圖2(a)。圖中“+”表示錨節(jié)點的位置,每條線段的一端是“○”,表示節(jié)點的真實位置,另一端則是定位算法運行后的節(jié)點估計位置,線段的長度即表示節(jié)點真實位置與估計位置的誤差距離。圖2(b)是以DV-Hop為基礎的基于LCV的節(jié)點定位綜合算法的仿真實驗,結果證明該算法定位誤差可以減小到9.41%,圖3就是仿真結果。以上的實驗數(shù)據均在網絡連通度為10的情況下得到,而下面的實驗數(shù)據表明本文提出的算法在低連通度的網絡中也具有良好的定位效果。從圖3中可以看到,當網絡連通度僅為5時,基于LCV的算法依然可以使DV-Hop原本的定位誤差下降將近50%;當連通度為8時,DV-Hop的定位誤差已經可以下降60%以上,證明