吉灤巒，謝 宏

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

0 引 言

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

本文為了進(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算法主要分為三個階段。第一和第二階段通過跳數(shù)和平均跳距計算未知節(jié)點到錨節(jié)點的估計距離di。在第三階段利用最小二乘法、智能優(yōu)化算法等方法計算未知節(jié)點坐標(biāo)。

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

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

(1)

式中m為錨節(jié)點數(shù)目，(x,y)為未知節(jié)點坐標(biāo)，(xi,yi)為第i個錨節(jié)點坐標(biāo),di為節(jié)點之間的距離。式中如果fitness(x,y) 最小，則未知節(jié)點的解和實際值之間的誤差就越小，而此時(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算法，提出重心反向粒子群算法，同時計算粒子的正向解和反向解，擴(kuò)大粒子搜索范圍，提高種群的多樣性，并且針對粒子群在后期搜索過程中，粒子收斂精度較低，速度較慢的問題，對算法的粒子運行速度進(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)能力。其主要思想是：同時計算可行解及其反向解，擇優(yōu)使用。在此基礎(chǔ)上，Rahnamayan S等人[9]提出重心反向?qū)W習(xí)(centroid opposition-based learning，COBL)策略，本文將COBL應(yīng)用到粒子群算法，利用整個種群的搜索信息，以整個群體的重心為參考計算反向點，重心與重心反向點的定義如下：

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

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

(2)

(3)

當(dāng)反向點超出搜索空間時，按式(4)重新計算反向點

(4)

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

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

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

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

(5)

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

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

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

(6)

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

3 定位算法流程

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

4.1 仿真環(huán)境

在MATLAB2016a的平臺上進(jìn)行仿真實驗，擬定無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)空間為100 m×100 m的二維網(wǎng)絡(luò)空間，為了使COPSO算法更具有說服力，采用DV-Hop算法進(jìn)行對比實驗，從不同錨節(jié)點比例、不同網(wǎng)絡(luò)節(jié)點、不同通信半徑三個方面進(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。為減小實驗中隨機(jī)誤差的干擾，最終結(jié)果取20次實驗的平均值。采用平均定位誤差來評價算法性能，平均定位誤差為

(7)

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

4.2 不同錨節(jié)點比例時的節(jié)點定位

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

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

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

4.4 不同通信半徑時的節(jié)點定位

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

圖1 仿真結(jié)果

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

5 結(jié) 論

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