節(jié)點定位綜合算法)

1、目錄1 引言2基于校正矢量和粒子群優(yōu)化的節(jié)點定位綜合算法3 算法仿真實驗及結(jié)果4 總結(jié) 引言引言TDOA(Time Difference of Arrival)算法RSSI(Received signed Strength Indicator)算法已知基站發(fā)送端發(fā)射功率，在接收節(jié)點測量接收功率，計算信號的傳播損耗；使用信號衰減模型將傳播損耗轉(zhuǎn)化為距離。在節(jié)點上安裝超聲波收發(fā)器和RF收發(fā)器,記錄兩種不同信號在兩個節(jié)點中的傳播時間差；由傳播時間差計算得到距離。1引言引言DV-HOP 定位算法質(zhì)心定位算法錨節(jié)點每隔一段時間向鄰節(jié)點廣播一個信號(自身ID 和位置信息)。當未知節(jié)點接收到來自不同錨節(jié)點的

2、信號數(shù)量超過某一個值后，則確定位置為這些錨節(jié)點所組成的多邊形的質(zhì)心。計算未知節(jié)點與錨節(jié)點的最小跳數(shù)；根據(jù)估算距離公式，計算未知節(jié)點和錨節(jié)點的實際距離；利用三邊測量法計算位置信息1引言引言1引言引言1引言引言 基于校正矢量和粒子群優(yōu)化的節(jié)點定位綜合算法2基于校正矢量和粒子群優(yōu)化的節(jié)點定位綜合算法基于校正矢量和粒子群優(yōu)化的節(jié)點定位綜合算法2.1 位置校正矢量（LCV）2.2 分簇計算校正步長位置校正矢量校正步長位置校正值位置校正值2.3 簇邊緣附加矯正2.1 位置校正矢量位置校正矢量未知節(jié)點通過DV-hop算法得到自身的估計位置，將其與鄰居節(jié)點估計位置之間的距離記為“計算距離”。而通過RSSI等測

3、距方法得到的與鄰居節(jié)點間的距離記為“測量距離”。 引入位置校正矢量的目的就是通過調(diào)整節(jié)點的位置，盡可能縮小計算距離與測量距離之間的差別，因此LCV的每個分量是沿著未知節(jié)點到某個鄰居節(jié)點的方向，分量的大小為對應(yīng)的計算距離與測量距離的差值。2.1 位置校正矢量位置校正矢量圖1 位置矯正矢量圖固定節(jié)點的位置校正矢量2.1 位置校正矢量位置校正矢量假設(shè)節(jié)點S通信范圍內(nèi)有N個鄰居節(jié)點，節(jié)點自身的估計位置為PS=(xs, ys)，N個鄰居節(jié)點的估計位置為Pi=(xi, yi) ，節(jié)點S與第i個鄰居節(jié)點的計算距離為dci22()()cisisidxxyyicimiudd2.1 位置校正矢量位置校正矢量節(jié)點S

4、獲得的N個測距值為dmi，i=1，2， ，N。節(jié)點S與第i個鄰居節(jié)點的差異值的大小可以表示為ui2.1 位置校正矢量位置校正矢量iv節(jié)點S與第i個鄰居節(jié)點位置校正矢量的矢量方向表示為sv因此，節(jié)點S的合成LCV為,1,2,siiivuv i，N|siisip pvp p圖2 位置矯正矢量圖 （實線為節(jié)點實際位置，虛線為節(jié)點估計位置）2.1 位置校正矢量位置校正矢量移動節(jié)點的位置矯正矢量2.1 位置校正矢量位置校正矢量對于移動節(jié)點，初始位置估計方法：移動節(jié)點Sm在tk+1時刻的初步估計位置等于其在tk時刻的定位結(jié)果的基礎(chǔ)上加上1ktk新加入鄰居節(jié)點坐標總和離開通信范圍的節(jié)點坐標總和時刻鄰居節(jié)點數(shù)

5、t 時刻鄰居節(jié)點數(shù)2.1 位置校正矢量位置校正矢量2.1 位置校正矢量位置校正矢量假設(shè)節(jié)點密度不變SStktk+10XY圖3 移動節(jié)點的初始定位1ktk新加入鄰居節(jié)點坐標總和離開通信范圍的節(jié)點坐標總和時刻鄰居節(jié)點數(shù)t 時刻鄰居節(jié)點數(shù)移動節(jié)點用距離變化值代替距離值構(gòu)建LCV（位置校正矢量），過程如下： 2.1 位置校正矢量位置校正矢量Sm與第i個鄰居節(jié)點的計算距離為測量距離為tk時刻Sm與第i個鄰居節(jié)點的計算距離為測量距離為tk+1時刻kcidkmid1kcid1kmid111()()kkkkkicicimimiudddd差異值表示為：2.1 位置校正矢量位置校正矢量iv節(jié)點Sm與第i個鄰居節(jié)點

6、位置校正矢量的矢量方向表示為sv因此，節(jié)點S的合成LCV為1,1,2,mksiiivuv i，N|mmsiisip pvp p圖2 位置矯正矢量圖 （實線為節(jié)點實際位置，虛線為節(jié)點估計位置）2.1 位置校正矢量位置校正矢量LCV矢量的合成方法與固定節(jié)點相同。2.2 分簇計算矯正步長分簇計算矯正步長由于每個未知節(jié)點同時調(diào)整自身的位置，因此LCV只能給出節(jié)點位置的調(diào)整方向，而沿這個方向移動的距離(將其稱之為校正步長)需要通過另外的方法來計算。為了避免集中式算法，同時兼顧節(jié)點的能耗，考慮使用分簇的計算方式來獲取校正步長。考慮到算法的盡可能簡單化和錨節(jié)點的計算通信能力比較強，就將每個錨節(jié)點作為簇頭，未

7、知節(jié)點以自身的當前估計位置為準，加入距離最近的錨節(jié)點所在的簇。問題描述問題描述分簇后，以 為目標來計算簇內(nèi)節(jié)點的校正步長。位置校正矢量的作用是使簇內(nèi)所有鄰居節(jié)點之間經(jīng)過位置校正后，計算距離與測量距離差值的總和最小化，因此求校正步長的問題可以描述為一個多元函數(shù)最小化問題。2.2 分簇計算矯正步長分簇計算矯正步長簇內(nèi)網(wǎng)絡(luò)整體位置最優(yōu)化假設(shè)簇內(nèi)有N個未知節(jié)點，它們的估計位置分別為Pi=(xi, yi) ，LCV分別為 ，i=1，2， ，N，待求步長為step，step是一個由stepi組成的N維向量。問題的目標函數(shù)可以表示為iv_()|p |ijdRijm ijijF steppd 其中，iiiip

8、pstepvjjjjppstepvR為節(jié)點的通信半徑_m ijd為簇內(nèi)節(jié)點i、j之間的距離測量值為簇內(nèi)節(jié)點之間的實際距離ijd2.2 分簇計算矯正步長分簇計算矯正步長2.2 分簇計算矯正步長分簇計算矯正步長粒子群算法粒子群算法2.2 分簇計算矯正步長分簇計算矯正步長 粒子群優(yōu)化(PSO)算法是一種新穎的演化算法, PSO的優(yōu)勢在于簡單而又功能強大。它屬于一類隨機全局優(yōu)化技術(shù), PSO算法通過粒子間的相互作用在復(fù)雜搜索空間中發(fā)現(xiàn)最優(yōu)區(qū)域。參數(shù)只需要最簡單的設(shè)置：PSO粒子的長度等于簇內(nèi)未知節(jié)點的個數(shù)每一維分量對應(yīng)一個節(jié)點的校正步長目標函數(shù)作為適應(yīng)度函數(shù)2.3 簇邊緣附加矯正簇邊緣附加矯正 簇內(nèi)節(jié)

9、點的相對位置的最優(yōu)化并不意味著全局網(wǎng)絡(luò)所有節(jié)點的位置實現(xiàn)了最優(yōu)化，有可能存在簇整體平移或者簇間距離誤差反而增大的問題。因此考慮對簇與簇之間的位置進行調(diào)整。 由簇的每個邊緣節(jié)點查找所有不屬于本簇但是在自身通信半徑內(nèi)的鄰居節(jié)點。利用它們之間的計算距離和測量距離構(gòu)建附加位置校正矢量。 首先用rangefree算法計算錨節(jié)點的估計位置，然后求其與錨節(jié)點真實位置的誤差。再利用錨節(jié)點與鄰居節(jié)點的測距值構(gòu)建位置校正矢量，將誤差距離值除以位置校正矢量模值作為附加校正步長。 簇內(nèi)所有邊緣節(jié)點都采用這個附加校正步長。每個簇的邊緣節(jié)點都通過上述的過程調(diào)整自身的位置，以此減小簇與簇的相對位置誤差，避免陷入局部最優(yōu)化。

10、2.3 簇邊緣附加矯正簇邊緣附加矯正|,1,2,iiiuviN，N步長：算法仿真及結(jié)果分析仿真環(huán)境：MATLAB區(qū)域：邊長為100的正方形節(jié)點數(shù)：隨機布置了100個未知節(jié)點節(jié)點通信半徑：20網(wǎng)絡(luò)的連通度：約為10測量距離：真實距離加上一個誤差不超過10%的高斯隨機變量3 算法仿真及結(jié)果分析算法仿真及結(jié)果分析圖4 DV-hop定位結(jié)果3 算法仿真及結(jié)果分析算法仿真及結(jié)果分析錨節(jié)點數(shù)為16個，錨節(jié)點比例為13.8。在如上參數(shù)的條件下，DV-hop算法仿真的定位誤差為39.34。3 算法仿真及結(jié)果分析算法仿真及結(jié)果分析粒子群算法的初始粒子數(shù)為20個，粒子群算法的更新次數(shù)是10次。圖5是以DV-hop為基礎(chǔ)的基于LCV和粒子群優(yōu)化的節(jié)點定位綜合算法的仿真實驗。圖5 基于LCV的節(jié)點定位綜合算法的定位結(jié)果3 算法仿真及結(jié)果分析算法仿真及結(jié)果分析圖6 算法循環(huán)次數(shù)與錨節(jié)點計算時間以及定位誤差的關(guān)系3