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

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

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

3、距方法得到的與鄰居節(jié)點(diǎn)間的距離記為“測(cè)量距離”。 引入位置校正矢量的目的就是通過(guò)調(diào)整節(jié)點(diǎn)的位置，盡可能縮小計(jì)算距離與測(cè)量距離之間的差別，因此LCV的每個(gè)分量是沿著未知節(jié)點(diǎn)到某個(gè)鄰居節(jié)點(diǎn)的方向，分量的大小為對(duì)應(yīng)的計(jì)算距離與測(cè)量距離的差值。2.1 位置校正矢量位置校正矢量圖1 位置矯正矢量圖固定節(jié)點(diǎn)的位置校正矢量2.1 位置校正矢量位置校正矢量假設(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與第i個(gè)鄰居節(jié)點(diǎn)的計(jì)算距離為dci22()()cisisidxxyyicimiudd2.1 位置校正矢量位置校正矢量節(jié)點(diǎn)S

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

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

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

7、知節(jié)點(diǎn)以自身的當(dāng)前估計(jì)位置為準(zhǔn)，加入距離最近的錨節(jié)點(diǎn)所在的簇。問(wèn)題描述問(wèn)題描述分簇后，以 為目標(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)題。2.2 分簇計(jì)算矯正步長(zhǎng)分簇計(jì)算矯正步長(zhǎng)簇內(nèi)網(wǎng)絡(luò)整體位置最優(yōu)化假設(shè)簇內(nèi)有N個(gè)未知節(jié)點(diǎn)，它們的估計(jì)位置分別為Pi=(xi, yi) ，LCV分別為 ，i=1，2， ，N，待求步長(zhǎng)為step，step是一個(gè)由stepi組成的N維向量。問(wèn)題的目標(biāo)函數(shù)可以表示為iv_()|p |ijdRijm ijijF steppd 其中，iiiip

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

9、點(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)。利用它們之間的計(jì)算距離和測(cè)量距離構(gòu)建附加位置校正矢量。 首先用rangefree算法計(jì)算錨節(jié)點(diǎn)的估計(jì)位置，然后求其與錨節(jié)點(diǎn)真實(shí)位置的誤差。再利用錨節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的測(cè)距值構(gòu)建位置校正矢量，將誤差距離值除以位置校正矢量模值作為附加校正步長(zhǎng)。 簇內(nèi)所有邊緣節(jié)點(diǎn)都采用這個(gè)附加校正步長(zhǎng)。每個(gè)簇的邊緣節(jié)點(diǎn)都通過(guò)上述的過(guò)程調(diào)整自身的位置，以此減小簇與簇的相對(duì)位置誤差，避免陷入局部最優(yōu)化。

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