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

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

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