吉灤巒，謝 宏

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引 言

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的主要技術(shù)之一，并具有廣泛的應(yīng)用領(lǐng)域[1]。針對(duì)無線傳感器節(jié)點(diǎn)定位問題，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，目前的定位算法主要分為兩種：基于測(cè)距的算法和無需測(cè)距的算法。無需測(cè)距的定位算法不需要額外的硬件支持，主要包括質(zhì)心算法[2]、距離矢量—跳數(shù)( distance vector-hop,DV-Hop) 算法[3]、無定形( amorphous)算法[4]和APIT算法[5]。其中，DV-Hop算法實(shí)現(xiàn)簡(jiǎn)單，無需額外硬件支持，具有部署網(wǎng)絡(luò)成本低的優(yōu)點(diǎn)，是目前研究最廣泛的算法之一。針對(duì)DV-Hop算法定位精度不高的問題，許多學(xué)者將遺傳算法、鳥算法、蟻群算法、粒子群優(yōu)化(particle swarm optimization,PSO)算法[6～8]等智能算法應(yīng)用于節(jié)點(diǎn)定位，利用群體的智能尋優(yōu)能力來對(duì)未知節(jié)點(diǎn)定位，這已經(jīng)成為一個(gè)新的研究方向。

本文為了進(jìn)一步提高定位效果，在充分研究傳統(tǒng)DV-Hop算法和標(biāo)準(zhǔn)PSO算法的基礎(chǔ)之上，提出重心反向粒子群優(yōu)化(centroid oppositional particle swarm optimization,COPSO)算法，用COPSO算法來校正DV-Hop算法定位結(jié)果。

1 相關(guān)問題描述

1.1 DV-Hop定位

DV-Hop算法主要分為三個(gè)階段。第一和第二階段通過跳數(shù)和平均跳距計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離di。在第三階段利用最小二乘法、智能優(yōu)化算法等方法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

1.2 構(gòu)建適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來評(píng)價(jià)粒子的品質(zhì)，引導(dǎo)粒子在解空間中的搜索方向。計(jì)算適應(yīng)度函數(shù)公式為

(1)

式中m為錨節(jié)點(diǎn)數(shù)目，(x,y)為未知節(jié)點(diǎn)坐標(biāo)，(xi,yi)為第i個(gè)錨節(jié)點(diǎn)坐標(biāo),di為節(jié)點(diǎn)之間的距離。式中如果fitness(x,y) 最小，則未知節(jié)點(diǎn)的解和實(shí)際值之間的誤差就越小，而此時(shí)(x,y)就為最優(yōu)解。

1.3 標(biāo)準(zhǔn)PSO算法的描述

在PSO算法中，粒子容易過早收斂，陷入局部最優(yōu)，最終導(dǎo)致算法的搜索精度不高。為了優(yōu)化PSO算法，將重心反向?qū)W習(xí)應(yīng)用到PSO算法，提出重心反向粒子群算法，同時(shí)計(jì)算粒子的正向解和反向解，擴(kuò)大粒子搜索范圍，提高種群的多樣性，并且針對(duì)粒子群在后期搜索過程中，粒子收斂精度較低，速度較慢的問題，對(duì)算法的粒子運(yùn)行速度進(jìn)行改進(jìn)，進(jìn)一步提高算法精度和穩(wěn)定性。

2 COPSO算法的構(gòu)建

2.1 重心反向?qū)W習(xí)策略

反向?qū)W習(xí)(opposition-based learning，OBL)可以提高優(yōu)化算法的尋優(yōu)能力。其主要思想是：同時(shí)計(jì)算可行解及其反向解，擇優(yōu)使用。在此基礎(chǔ)上，Rahnamayan S等人[9]提出重心反向?qū)W習(xí)(centroid opposition-based learning，COBL)策略，本文將COBL應(yīng)用到粒子群算法，利用整個(gè)種群的搜索信息，以整個(gè)群體的重心為參考計(jì)算反向點(diǎn)，重心與重心反向點(diǎn)的定義如下：

定義1重心。令(x1，x2，…，xN)為D維搜索空間中帶有質(zhì)量的N個(gè)點(diǎn)，然后整體重心可以定義如下

M=(x1+x2+…+xN)/N

(2)

(3)

當(dāng)反向點(diǎn)超出搜索空間時(shí)，按式(4)重新計(jì)算反向點(diǎn)

(4)

本文首次提出用COPSO對(duì)無線傳感器定位進(jìn)行優(yōu)化，在COPSO算法中種群在前期利用粒子搜索經(jīng)驗(yàn)充分探索搜索空間，算法后期能更多地保留群體信息，保持種群的多樣性。COPSO算法由重心反向粒子群初始化、粒子運(yùn)行速度和重心反向粒子群更新組成。

2.2 重心反向粒子群初始化和更新

反向粒子群的初始化和更新可以進(jìn)一步增加種群多樣性、提高解的質(zhì)量[10]。對(duì)于一個(gè)D維優(yōu)化問題，設(shè)尋優(yōu)空間有N個(gè)粒子，每個(gè)粒子按如下方式計(jì)算正向解和反向解：

1)隨機(jī)產(chǎn)生N個(gè)粒子的粒子群X，可依據(jù)式(5)求得粒子i在D維的正向位置X

(5)

2)根據(jù)式子(3)和式(4)計(jì)算反向粒子的位置OX；

2.3 反向粒子運(yùn)行速度改進(jìn)

針對(duì)粒子后期容易陷入局部最優(yōu)問題，本文對(duì)粒子速度進(jìn)行改進(jìn)，公式為

(6)

式中w為慣性權(quán)重;c1,c2為學(xué)習(xí)因子，r1,r2和r3為在區(qū)間[0,1]上均勻分布的隨機(jī)數(shù);k為[0,1]之間的常數(shù)(依實(shí)驗(yàn)情況而定);t為當(dāng)前粒子迭代次數(shù);T為最大迭代次數(shù)。算法在粒子速度更新公式中加入了隨機(jī)波動(dòng)的線性遞增項(xiàng)，在迭代前期粒子速度較大，有利于全局搜索，線性遞增項(xiàng)對(duì)速度的影響可以忽略；隨著迭代次數(shù)t的增加，粒子尋優(yōu)速度減慢，線性遞增項(xiàng)值增大，且隨機(jī)數(shù)r3增強(qiáng)了線性遞增項(xiàng)的隨機(jī)波動(dòng)性，可以有效地使粒子跳出局部最優(yōu)。

3 定位算法流程

4 仿真試驗(yàn)與結(jié)果分析

4.1 仿真環(huán)境

在MATLAB2016a的平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)，擬定無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)空間為100 m×100 m的二維網(wǎng)絡(luò)空間，為了使COPSO算法更具有說服力，采用DV-Hop算法進(jìn)行對(duì)比實(shí)驗(yàn)，從不同錨節(jié)點(diǎn)比例、不同網(wǎng)絡(luò)節(jié)點(diǎn)、不同通信半徑三個(gè)方面進(jìn)行仿真。設(shè)置參數(shù)值k=0.5,種群數(shù)N=50,最大迭代次數(shù)T=100,慣性權(quán)重wmax=0.9，wmin=0.2,學(xué)習(xí)因子c1=c2=1.494 5。為減小實(shí)驗(yàn)中隨機(jī)誤差的干擾，最終結(jié)果取20次實(shí)驗(yàn)的平均值。采用平均定位誤差來評(píng)價(jià)算法性能，平均定位誤差為

(7)

式中L為未知節(jié)點(diǎn)個(gè)數(shù)，R為通信半徑，Q為實(shí)驗(yàn)次數(shù)；(xi,yi) 為未知節(jié)點(diǎn)i的實(shí)際坐標(biāo)，(x′iq,y′iq)為未知節(jié)點(diǎn)i在第q次實(shí)驗(yàn)的坐標(biāo)估計(jì)值。

4.2 不同錨節(jié)點(diǎn)比例時(shí)的節(jié)點(diǎn)定位

規(guī)定無線傳感器網(wǎng)絡(luò)空間的分布形式：傳感器節(jié)點(diǎn)總數(shù)為100個(gè)，通信半徑為35 m，當(dāng)錨節(jié)點(diǎn)比例分別為10 %,15 %,20 %,25 %,30 %,35 %,40 %和45 %時(shí)，兩種定位算法定位誤差如圖1(a)所示?？梢钥闯觯S著錨節(jié)點(diǎn)比例的增加，這兩種定位算法的定位誤差整體呈下降趨勢(shì)，COPSO算法的未知節(jié)點(diǎn)定位能力強(qiáng)于DV-Hop算法，定位精度比DV-Hop算法提高了17.24 %，有明顯的優(yōu)越性。

4.3 不同節(jié)點(diǎn)總數(shù)時(shí)的節(jié)點(diǎn)定位

規(guī)定無線傳感器網(wǎng)絡(luò)空間分布形式：通信半徑為35 m，錨節(jié)點(diǎn)比例為30 %，對(duì)于節(jié)點(diǎn)總數(shù)分別為50,60,80,100,120,140,160,180，200個(gè)時(shí)，分別采取兩種定位算法定位，定位誤差如圖1(b)所示?？芍?，隨著網(wǎng)絡(luò)空間內(nèi)節(jié)點(diǎn)總數(shù)的增多，兩種節(jié)點(diǎn)定位方法的定位精度均得到了有效的提高，誤差呈下降趨勢(shì)。顯然，COPSO算法定位誤差較小，相較DV-Hop算法，精度提高了13.08 %。

4.4 不同通信半徑時(shí)的節(jié)點(diǎn)定位

規(guī)定無線傳感器網(wǎng)絡(luò)空間分布形式：傳感器節(jié)點(diǎn)總數(shù)為100個(gè)，錨節(jié)點(diǎn)比例為30 %，對(duì)于傳感器的信號(hào)覆蓋半徑為15，20，25，30，35，40，45,50 m時(shí)，分別采取兩種定位算法對(duì)網(wǎng)絡(luò)空間內(nèi)的未知節(jié)點(diǎn)定位，定位誤差如圖1(c)所示。

圖1 仿真結(jié)果

根據(jù)圖1(c)可知，隨著錨節(jié)點(diǎn)通信半徑的增大，這兩種節(jié)點(diǎn)定位算法的定位誤差均不斷減小，相比于標(biāo)準(zhǔn)DV-Hop算法，COPSO算法精度提高了20.93 %，節(jié)點(diǎn)定位精度明顯提高。

5 結(jié) 論

將算法應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位。仿真結(jié)果表明:該算法避免了粒子陷入早熟，加快了算法收斂速度，有較好的全局尋優(yōu)能力，提高了定位性能，與傳統(tǒng)DV-Hop算法相比，基于重心反向?qū)W習(xí)的粒子群算法的網(wǎng)絡(luò)節(jié)點(diǎn)定位效果更好，精度更高。在下一步研究中，將繼續(xù)優(yōu)化算法，減小算法的復(fù)雜度，進(jìn)一步提高定位精度。