一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法

曹欲曉,嚴(yán) 奎,徐金寶

(1.南京工程學(xué)院計(jì)算機(jī)工程學(xué)院,南京 211167;2.南京工程學(xué)院工業(yè)中心,南京 211167)

?

一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法

曹欲曉1*,嚴(yán) 奎2,徐金寶1

(1.南京工程學(xué)院計(jì)算機(jī)工程學(xué)院,南京 211167;2.南京工程學(xué)院工業(yè)中心,南京 211167)

當(dāng)前粒子群優(yōu)化的DV-Hop定位改進(jìn)算法,網(wǎng)絡(luò)中所有的錨節(jié)點(diǎn)都參與優(yōu)化,但是一部分到未知節(jié)點(diǎn)估算距離誤差較大的錨節(jié)點(diǎn)會(huì)引入大的定位誤差。針對(duì)這種情況,首先提出了最優(yōu)錨節(jié)點(diǎn)集合的概念;然后在定位過程中,應(yīng)用離散粒子群算法構(gòu)造了最優(yōu)錨節(jié)點(diǎn)集合;最后在最優(yōu)錨節(jié)點(diǎn)集合上應(yīng)用連續(xù)粒子群算法對(duì)定位結(jié)果進(jìn)行了優(yōu)化。仿真實(shí)驗(yàn)表明,最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop算法比DV-Hop和一次粒子群優(yōu)化的DV-Hop明顯提高了定位精度。

無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;DV-Hop算法;粒子群算法;錨節(jié)點(diǎn);最優(yōu)錨節(jié)點(diǎn)集合

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)由大量部署在監(jiān)控區(qū)域的傳感節(jié)點(diǎn)組成,用來獲取監(jiān)控區(qū)域的相關(guān)信息。在WSN的大多數(shù)應(yīng)用中,節(jié)點(diǎn)獲得的傳感數(shù)據(jù)要和自身的位置信息結(jié)合起來才有實(shí)際意義,沒有位置信息的數(shù)據(jù)往往毫無用處。因此節(jié)點(diǎn)定位是WSN領(lǐng)域中一項(xiàng)非常關(guān)鍵的支撐技術(shù)[1]。

WSN的節(jié)點(diǎn)定位根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的距離或者角度等信息,分成基于測(cè)距的定位方法和無需測(cè)距的定位方法[2]兩種?；跍y(cè)距的定位方法精度較高,但是需要額外的硬件設(shè)備支持;無需測(cè)距的定位方法精度相對(duì)要低,但是不需要額外的硬件設(shè)備,成本較低。DV-Hop即是無需測(cè)距定位方法中最為常用的一種,如何提高DV-Hop算法的定位精度具有重要的理論和實(shí)際價(jià)值[3]。很多研究者采用了多種方法來提高DV-Hop算法的定位精度。這些方法大致可以分成兩類:第1類是采用加權(quán)平均或者誤差修正的方法提高未知節(jié)點(diǎn)的平均跳距估算精度,第2類是應(yīng)用群體智能算法[4]對(duì)DV-Hop定位的結(jié)果進(jìn)行優(yōu)化。文獻(xiàn)[5]根據(jù)未知節(jié)點(diǎn)接收的多個(gè)錨節(jié)點(diǎn)的平均跳距和到不同錨節(jié)點(diǎn)的跳數(shù),把跳數(shù)的倒數(shù)作為權(quán)值進(jìn)行加權(quán)平均,重新計(jì)算未知節(jié)點(diǎn)的平均跳距。文獻(xiàn)[6]把兩個(gè)錨節(jié)點(diǎn)之間的實(shí)際距離和估計(jì)距離的誤差的倒數(shù)作為權(quán)值,對(duì)錨節(jié)點(diǎn)的平均跳距進(jìn)行加權(quán)平均。文獻(xiàn)[7]利用錨節(jié)點(diǎn)和未知節(jié)點(diǎn)實(shí)際距離和估計(jì)距離的誤差來修正每跳平均跳距。上述各種改進(jìn)算法都是基于無偏估計(jì)準(zhǔn)則計(jì)算的錨節(jié)點(diǎn)平均跳距。文獻(xiàn)[8-11]則把未知節(jié)點(diǎn)的定位抽象成一個(gè)優(yōu)化問題,應(yīng)用粒子群算法對(duì)DV-Hop的定位結(jié)果進(jìn)行了優(yōu)化,并讓全部錨節(jié)點(diǎn)參與整個(gè)優(yōu)化過程。

現(xiàn)有的基于粒子群優(yōu)化的DV-Hop(PSO DV-Hop)改進(jìn)算法,對(duì)未知節(jié)點(diǎn)的位置進(jìn)行優(yōu)化時(shí)均是讓所有的錨節(jié)點(diǎn)都參與定位優(yōu)化,但是由文獻(xiàn)[6]可知,在進(jìn)行三邊測(cè)量定位時(shí),如果某些錨節(jié)點(diǎn)的估計(jì)距離誤差過大,反而會(huì)使最終的定位誤差增大,所以并不是參加定位的錨節(jié)點(diǎn)的數(shù)量越多越好,應(yīng)該在保證錨節(jié)點(diǎn)數(shù)量大于等于3個(gè)的前提下,選擇一個(gè)最優(yōu)的錨節(jié)點(diǎn)集合進(jìn)行定位。本文應(yīng)用兩重粒子群算法對(duì)DV-Hop定位進(jìn)行了改進(jìn),提出了一種新的DV-Hop改進(jìn)算法:在三邊定位階段,首先應(yīng)用離散粒子群算法構(gòu)造一個(gè)到未知節(jié)點(diǎn)距離誤差最小的最優(yōu)錨節(jié)點(diǎn)集合,接著再應(yīng)用連續(xù)粒子群算法在最優(yōu)錨節(jié)點(diǎn)集合上進(jìn)行定位優(yōu)化。仿真結(jié)果表明,本文算法在無需額外增加硬件設(shè)備的情況下,明顯提高了未知節(jié)點(diǎn)定位的精度。

1 DV-Hop算法

DV-Hop算法把未知節(jié)點(diǎn)的平均每跳距離乘以其到錨節(jié)點(diǎn)的跳數(shù),以乘積作為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。當(dāng)獲得到達(dá)3個(gè)或3個(gè)以上錨節(jié)點(diǎn)的距離時(shí),應(yīng)用三邊測(cè)量法或極大似然法求出未知節(jié)點(diǎn)的坐標(biāo)。DV-Hop的定位過程可以分成3個(gè)階段[12]。

第1階段:計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)。通過泛洪廣播的方式,網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)均可獲得到達(dá)所有錨節(jié)點(diǎn)的最小跳數(shù)。

第2階段:計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離。每個(gè)錨節(jié)點(diǎn)根據(jù)第1階段獲得的其他錨節(jié)點(diǎn)的位置信息分組,利用式(1)計(jì)算自身的平均每跳距離。式(1)中,(xi,yi)是錨節(jié)點(diǎn)i的坐標(biāo),(xj,yj)是錨節(jié)點(diǎn)j的坐標(biāo),hij是錨節(jié)點(diǎn)i到j(luò)的跳數(shù)。

(1)

錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播自己的平均每跳距離,未知節(jié)點(diǎn)接收第1個(gè)平均跳距,利用式(2)計(jì)算自己到每個(gè)錨節(jié)點(diǎn)的距離,其中hi是第1階段獲得的到錨節(jié)點(diǎn)的跳數(shù)。

di=Hopsizei×hi

(2)

第3階段:計(jì)算未知節(jié)點(diǎn)坐標(biāo)。未知節(jié)點(diǎn)根據(jù)第2階段計(jì)算出的di,利用三邊測(cè)量法或極大似然法計(jì)算自身坐標(biāo)。

2 粒子群算法[13]

2.1 連續(xù)粒子群算法

(3)

(4)

式(4)中:w是慣性因子,c1是個(gè)體學(xué)習(xí)因子,c2是全局學(xué)習(xí)因子,r1和r2是區(qū)間[0,1]上的隨機(jī)數(shù),PB是粒子的個(gè)體極值,GB是粒子群的全局極值。

2.2 離散粒子群算法

連續(xù)粒子群算法用來求解連續(xù)優(yōu)化問題,為了解決組合優(yōu)化問題,在連續(xù)粒子群的基礎(chǔ)上又提出了離散粒子群算法。二進(jìn)制粒子群優(yōu)化算法BPSO[14](Binary Particle Swarm Optimization)屬于離散粒子群算法中的一種。BPSO算法的位置矢量由實(shí)數(shù)空間變成了二進(jìn)制空間,即粒子在每一維上的取值只能是0或1兩個(gè)值中的一個(gè),但粒子的速度矢量仍然位于實(shí)數(shù)空間。BPSO算法的速度矢量更新公式用式(4)表示不變,位置矢量更新改用式(5)表示。

(5)

(6)

3 最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop算法

3.1 最優(yōu)錨節(jié)點(diǎn)集合

設(shè)WSN中有m個(gè)錨節(jié)點(diǎn),n個(gè)未知節(jié)點(diǎn),現(xiàn)要對(duì)未知節(jié)點(diǎn)A進(jìn)行定位。若A的定位坐標(biāo)為(x,y),m個(gè)錨節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1)、(x2,y2)、…、(xm,ym),A到m個(gè)錨節(jié)點(diǎn)的估計(jì)距離分別是d1、d2、…、dm,實(shí)際距離分別是r1、r2、…、rm,則由兩點(diǎn)間的距離公式可得:

(7)

設(shè)A到m個(gè)錨節(jié)點(diǎn)估算距離的誤差分別是ε1、ε2、…、εm,則|ri-di|≤εi,把式(7)代入|ri-di|≤εi得,

(8)

求解(x,y),使式(9)取得最小值的解即是與未知節(jié)點(diǎn)A的真實(shí)坐標(biāo)最為接近的定位結(jié)果。

(9)

式(9)的意義是:(x,y)作為計(jì)算出的未知節(jié)點(diǎn)A的坐標(biāo),如果(x,y)到各錨節(jié)點(diǎn)的實(shí)際距離ri與估算距離di的誤差的平方的和越小,則(x,y)就越接近A的真實(shí)坐標(biāo),那么定位的結(jié)果就越精確。為求得更為精確的(x,y),可以通過使式(9)的值最小來實(shí)現(xiàn)。這樣就把WSN節(jié)點(diǎn)的定位問題轉(zhuǎn)化成了一個(gè)優(yōu)化問題,故可以應(yīng)用粒子群算法求解。

由文獻(xiàn)[6]可知,如果未知節(jié)點(diǎn)到某些錨節(jié)點(diǎn)的估算距離di的誤差過大,反而會(huì)降低未知節(jié)點(diǎn)定位的精度,因此在定位過程中如果能排除這類di誤差過大的錨節(jié)點(diǎn),而是在m個(gè)錨節(jié)點(diǎn)中選擇k個(gè)估算距離di誤差較小的錨節(jié)點(diǎn)參加定位,則能提高定位結(jié)果的精度,這樣的一組錨節(jié)點(diǎn)構(gòu)成的集合稱為最優(yōu)錨節(jié)點(diǎn)集合BANS(Best Anchor Nodes Set)。

3.2 兩重粒子群優(yōu)化的DV-Hop原理

從m個(gè)錨節(jié)點(diǎn)中選擇k個(gè)構(gòu)造一個(gè)最優(yōu)錨節(jié)點(diǎn)集合,對(duì)網(wǎng)絡(luò)中任意一個(gè)錨節(jié)點(diǎn),或者被選中進(jìn)入最優(yōu)錨節(jié)點(diǎn)集合,或者不被選中。選擇多少個(gè)錨節(jié)點(diǎn),選擇哪些錨節(jié)點(diǎn)才能使錨節(jié)點(diǎn)集合最優(yōu)屬于組合優(yōu)化問題,可以應(yīng)用離散粒子群算法求解。在構(gòu)造最優(yōu)錨節(jié)點(diǎn)集合過程中使用的粒子群稱為種群1。

構(gòu)造出最優(yōu)錨節(jié)點(diǎn)集合后,再使用另外一個(gè)把粒子對(duì)應(yīng)到了未知節(jié)點(diǎn)坐標(biāo)的粒子群,應(yīng)用連續(xù)粒子群算法對(duì)定位結(jié)果尋優(yōu)。在這個(gè)過程中使用的粒子群稱為種群2。對(duì)定位結(jié)果的優(yōu)化即為使適應(yīng)值函數(shù)取得最小值為優(yōu)化目標(biāo),以未知節(jié)點(diǎn)的坐標(biāo)作為粒子的位置矢量,經(jīng)過多次迭代,可以求得最為接近未知節(jié)點(diǎn)真實(shí)坐標(biāo)的定位結(jié)果。

因?yàn)槲粗?jié)點(diǎn)到錨節(jié)點(diǎn)的距離是由未知節(jié)點(diǎn)的平均跳距和它到錨節(jié)點(diǎn)的跳數(shù)相乘估算得到的,未知節(jié)點(diǎn)到哪些錨節(jié)點(diǎn)的估計(jì)距離誤差較小事先無法得知,所以最優(yōu)錨節(jié)點(diǎn)集合的構(gòu)造只能在求解未知節(jié)點(diǎn)坐標(biāo)(x,y)的過程中,通過使適應(yīng)值函數(shù)取得最小值來動(dòng)態(tài)的構(gòu)造。這就需要把構(gòu)造最優(yōu)錨節(jié)點(diǎn)集合的離散粒子群算法和在最優(yōu)錨節(jié)點(diǎn)集合上最優(yōu)化(x,y)的連續(xù)粒子群算法融合成一個(gè)整體來求解,這種方法稱為兩重粒子群優(yōu)化的DV-Hop算法DBPSO DV-Hop(Double PSO DV-Hop)。

3.3 兩重粒子群優(yōu)化的DV-Hop粒子編碼

應(yīng)用粒子群算法求解優(yōu)化問題的首要任務(wù)是粒子編碼。下面首先給出求解最優(yōu)錨節(jié)點(diǎn)集合的離散粒子群編碼方案。從m個(gè)錨節(jié)點(diǎn)中選出k個(gè)構(gòu)成最優(yōu)錨節(jié)點(diǎn)集合,m個(gè)錨節(jié)點(diǎn)中的任意一個(gè)或者是集合中的一個(gè)元素,或者不是,只有兩種可能,因此可以構(gòu)造一個(gè)m維的二進(jìn)制空間作為粒子的搜索空間。

應(yīng)用連續(xù)粒子群算法優(yōu)化DV-Hop的粒子編碼,采用文獻(xiàn)[8-11]中給出的方案,即每個(gè)粒子對(duì)應(yīng)未知節(jié)點(diǎn)的一個(gè)定位優(yōu)化結(jié)果,粒子的兩個(gè)位置分量表示未知節(jié)點(diǎn)的兩個(gè)坐標(biāo),粒子在二維空間中飛行尋優(yōu)。

3.4 兩重粒子群優(yōu)化的DV-Hop適應(yīng)值函數(shù)

由式(9)知,通過離散粒子群算法求解出的最優(yōu)錨節(jié)點(diǎn)集合對(duì)最終定位結(jié)果的優(yōu)化程度,需要通過di和ri(1≤i≤m)誤差的平方和來判定,所以DBPSO DV-Hop算法的離散粒子群和連續(xù)粒子群要共用同一個(gè)適應(yīng)值函數(shù),這個(gè)函數(shù)如式(10)所示。適應(yīng)值函數(shù)的設(shè)計(jì)思想是參加定位的錨節(jié)點(diǎn)的di和ri的誤差的平方和的平均值最小。

(10)

式(10)中的XDi(1≤i≤m)是種群1中粒子的位置分量,x和y是種群2中粒子的位置分量,β是未知節(jié)點(diǎn)到錨節(jié)點(diǎn)跳數(shù)的倒數(shù)。

3.5 兩重粒子群優(yōu)化的DV-Hop步驟

①初始化種群1、種群2的規(guī)模都是Q,確定慣性因子w、學(xué)習(xí)因子c1和c2的值。

②分別初始化種群1、種群2中每個(gè)粒子的位置和速度。種群1粒子的初始位置和速度由式(11)、式(12)給出,m是網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)的個(gè)數(shù),T(Q)是(0,1)區(qū)間上的一個(gè)閾值。

(11)

(12)

種群2的位置和速度由式(13)～式(15)給出。Xmax和Ymax是網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)橫坐標(biāo)和縱坐標(biāo)的最大值,Vmin和Vmax是粒子速度的最小值和最大值,r(0,1)是區(qū)間[0,1]上的隨機(jī)數(shù),rand()是隨機(jī)數(shù)函數(shù)。

(13)

(14)

(15)

③計(jì)算種群1中粒子和種群2中粒子的笛卡爾積,把笛卡爾積中的每個(gè)元素看做一個(gè)復(fù)合粒子,求出每個(gè)復(fù)合粒子的個(gè)體極值和全部復(fù)合粒子的全局極值。

④利用式(5)和式(4)更新種群1中每個(gè)粒子的位置和速度,利用式(3)和式(4)更新種群2中每個(gè)粒子的位置和速度。

⑤重復(fù)步驟③、步驟④,直到完成規(guī)定的迭代次數(shù)。此時(shí)復(fù)合粒子的全局極值就是優(yōu)化后的待定位節(jié)點(diǎn)的坐標(biāo)。

4 仿真結(jié)果及分析

4.1 3種算法使用的錨節(jié)點(diǎn)比較

由3.1知,對(duì)同一個(gè)未知節(jié)點(diǎn)定位,使用的錨節(jié)點(diǎn)不同會(huì)導(dǎo)致定位的精度有差別。DBPSO DV-Hop算法的核心思想是在所有錨節(jié)點(diǎn)中選出一個(gè)能使定位結(jié)果誤差最小的最優(yōu)錨節(jié)點(diǎn)集合。下面給出錨節(jié)點(diǎn)比例為15%時(shí),DV-Hop、PSO DV-Hop、DBPSO DV-Hop 3種算法定位階段所使用的錨節(jié)點(diǎn)的數(shù)量、未知節(jié)點(diǎn)到錨節(jié)點(diǎn)估算距離和實(shí)際距離誤差的平均值、平均定位誤差的比較。

表1 3種定位算法使用的錨節(jié)點(diǎn)比較

從表1還可以看出DBPSO DV-Hop算法經(jīng)過多次迭代,選出的最優(yōu)錨節(jié)點(diǎn)集合中的錨節(jié)點(diǎn)估計(jì)距離和實(shí)際距離的誤差較小,使用最優(yōu)錨節(jié)點(diǎn)集合進(jìn)行優(yōu)化,定位結(jié)果的平均誤差也較小。

4.2 3種算法定位結(jié)果比較

(16)

為了驗(yàn)證本文提出的DBPSO DV-Hop算法的性能,應(yīng)用MATLAB軟件對(duì)DV-Hop、PSO DV-Hop、DBPSO DV-Hop 3種算法進(jìn)行仿真。仿真環(huán)境設(shè)為:WSN分布在一個(gè)100 m×100 m的正方形區(qū)域中,隨機(jī)生成錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的坐標(biāo),節(jié)點(diǎn)的通信半徑是50 m。種群1和種群2的規(guī)模均是20,慣性因子w=0.9,學(xué)習(xí)因子c1=c2=2,迭代次數(shù)為200次。為了減少隨機(jī)誤差的干擾,每種算法均運(yùn)行100次取平均值作為最終的實(shí)驗(yàn)結(jié)果。

圖1給出了在節(jié)點(diǎn)總數(shù)維持200不變,錨節(jié)點(diǎn)比例變化的情況下3種定位算法的平均誤差比較結(jié)果。由圖1可以看出,隨著錨節(jié)點(diǎn)比例的增大,3種定位方法的平均定位誤差都在減小,PSO DV-Hop和DBPSO DV-Hop的減小要快于DV-Hop。PSO DV-Hop比DV-Hop平均提高定位精度11%,DBPSO DV-Hop比DV-Hop平均提高定位精度26%。在錨節(jié)點(diǎn)比例從15%～25%的區(qū)間內(nèi),DBPSO DV-Hop定位精度遠(yuǎn)高于PSO DV-Hop,但是當(dāng)錨節(jié)點(diǎn)比例超過25%以后,兩者的差距反而減小。

圖1 節(jié)點(diǎn)總數(shù)不變錨節(jié)點(diǎn)比例改變的定位誤差比較

圖2 錨節(jié)點(diǎn)比例不變節(jié)點(diǎn)總數(shù)改變的定位誤差比較

圖2給出了在錨節(jié)點(diǎn)比例維持10%不變,節(jié)點(diǎn)總數(shù)變化的情況下3種定位算法的平均誤差比較結(jié)果。由圖2可以看出,在錨節(jié)點(diǎn)比例保持不變的情況下,隨著節(jié)點(diǎn)總數(shù)的增加,錨節(jié)點(diǎn)總數(shù)也隨之增加,3種定位算法的平均誤差均呈下降趨勢(shì)。PSO DV-Hop比DV-Hop平均提高定位精度16%,DBPSO DV-Hop比DV-Hop平均提高定位精度43%。

從以上兩種情況下的仿真結(jié)果可以看出,DBPSO DV-Hop算法的節(jié)點(diǎn)定位精度要明顯好于DV-Hop和PSO DV-Hop算法。

5 結(jié)語(yǔ)

粒子群算法作為一種性能良好、實(shí)現(xiàn)簡(jiǎn)單的群體智能算法,被很多研究者應(yīng)用到了WSN的節(jié)點(diǎn)定位中,但是目前的粒子群優(yōu)化DV-Hop算法存在一個(gè)共同的問題,即定位尋優(yōu)時(shí)使用了所有可以使用的錨節(jié)點(diǎn),而有些錨節(jié)點(diǎn)的測(cè)距誤差過大,反而會(huì)降低最后定位的精度。因此本文的工作在于首先選出一組測(cè)距誤差較小的錨節(jié)點(diǎn)構(gòu)成最優(yōu)錨節(jié)點(diǎn)集合,只使用最優(yōu)錨節(jié)點(diǎn)參加定位以減小測(cè)距誤差對(duì)定位結(jié)果的影響。在所有的錨節(jié)點(diǎn)中確定最優(yōu)者時(shí),由于哪些錨節(jié)點(diǎn)的測(cè)距誤差較小并不知道,所以采用了離散粒子群算法在所有錨節(jié)點(diǎn)中組合尋優(yōu)進(jìn)行查找。在確定了最優(yōu)錨節(jié)點(diǎn)集合之后,再應(yīng)用連續(xù)粒子群算法最終確定未知節(jié)點(diǎn)的坐標(biāo)。

仿真實(shí)驗(yàn)表明,本文提出的DBPSO DV-Hop算法在定位時(shí)使用的錨節(jié)點(diǎn)在數(shù)量上少于DV-Hop和PSO DV-Hop,但在錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的距離精度上好于上述兩種算法。最終的定位結(jié)果也表明DBPSO DV-Hop比DV-Hop和PSO DV-Hop在很大程度上減小了定位誤差,提高了定位精度。但是DBPSO DV-Hop由于采用了兩次粒子群算法,增加了計(jì)算的復(fù)雜度,并且粒子群算法參數(shù)的選取也缺乏相應(yīng)的理論指導(dǎo),這是以后需要繼續(xù)研究改進(jìn)之處。

[1]Niclescu D,Americ N L. Communication Paradigms for Sensor Network[J]. IEEE Communications Maganize,2005,43(3):116-122.

[2]Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magzine,2000,7(5):28-34.

[3]張震,閆連山,劉江濤,等. 基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J]. 傳感技術(shù)學(xué)報(bào),2011,24(10):1470-1472.

[4]Hackwood S,Beni G. Self-Organization of Sensors for Swarm Intelligence[C]//IEEE International Conference on Robotics and Automation. Piscataway,NJ,USA:IEEE Press,1992:819-829.

[5]劉峰,張翰,楊驥. 一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計(jì)算法[J]. 電子與信息學(xué)報(bào),2008,30(5):1222-1225.

[6]趙雁航,錢志鴻,尚小航,等. 基于跳距修正粒子群優(yōu)化的WSN定位算法[J]. 通信學(xué)報(bào),2013,34(9):105-114.

[7]石為人,賈傳江,梁煥煥. 一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2011,24(1):83-87.

[8]張迅,王平,邢建春,等. 傳感器網(wǎng)絡(luò)中改進(jìn)的粒子群優(yōu)化定位算法[J]. 計(jì)算機(jī)科學(xué),2012,39(12):51-54.

[9]蔡紹濱,高振國(guó),潘海為,等. 帶有罰函數(shù)的無線傳感器網(wǎng)絡(luò)粒子群定位算法[J]. 計(jì)算機(jī)研究與發(fā)展,2012,49(6):1228-1234.

[10]崔煥慶,王英龍,呂家亮,等. 基于隨機(jī)微粒群算法的分布式節(jié)點(diǎn)定位算法[J]. 山東大學(xué)學(xué)報(bào):理學(xué)版,2012,47(9):51-55.

[11]陳星舟,廖明宏,林建華. 基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用,2010,30(7):1736-1738.

[12]Niculescu D,Nat h B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems,2003,22(14):267-280.

[13]Kennedy J,Eberhart R C. Particle Swarm Optimization[C]//IEEE International Conference on Neural Networks,Ⅳ. Piscataway,NJ,USA:IEEE Service Center,1995:1942-1948.

[14]Kennedy J,Eberhart R C. A Discrete Binary Version of the Particle Swarm Algorithm[C]//The 1997 Conference on System,Cybernetics and Informatics. Piscataway,NJ USA:IEEE Press,1997:4104-4109.

A Kind of Double Particle Swarm Optimization DV-Hop Localization Algorithm Based on Best Anchor Nodes Set

CAOYuxiao1*,YANKui2,XUJinbao1

(1.School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China;2.Industrial Center,Nanjing Institute of Technology,Nanjing 211167,China)

For the improved DV-Hop algorithms based on particle swarm optimization,almost all the anchor nodes in the network are involved in the locating optimization. However,the anchor nodes which have obvious errors between anchor and unknown nodes will lead to big errors of localization. Hence,the concept of best anchor nodes set is proposed. During the process of location,the best anchor nodes set is constructed by employing the discrete particle swarm optimization algorithm. Then the continuous particle swarm optimization algorithm is used to optimize localization for the best anchor nodes set. The simulation results show that the proposed method is effective.

wireless sensor network;node localization;DV-Hop algrothrim;particle swarm optimization algrothrim;anchor node;best anchor nodes set

曹欲曉(1971-),男,山東臨沂人,碩士,講師.主要研究方向?yàn)橹悄芩惴?、無線傳感器網(wǎng)絡(luò),caoyx@njit.edu.cn;

嚴(yán) 奎(1976-),男,四川南充人,碩士,講師,主要究研方向?yàn)榭刂评碚撆c控制工程,yankui@njit.edu.cn;

徐金寶(1970-),男,江蘇南京人,碩士,副教授.主要研究方向?yàn)閿?shù)據(jù)挖掘,智能算法,xujb@njit.edu.cn。

2014-10-20 修改日期:2014-12-22

C:7030;6150P

10.3969/j.issn.1004-1699.2015.03.022

TP393

A

1004-1699(2015)03-0424-06