基于RSSI和融合智能優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法

張先超，劉興長(zhǎng)，鐘一洋，張春園

(后勤工程學(xué)院 a.后勤信息與軍事物流工程系;b.學(xué)員旅，重慶 401311)

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)是由隨機(jī)部署在目標(biāo)區(qū)域內(nèi)的數(shù)量巨大的離散傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)［1］。節(jié)點(diǎn)的位置信息至關(guān)重要，在導(dǎo)航、跟蹤、監(jiān)控等應(yīng)用中起關(guān)鍵性作用。根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的距離，定位可以分為基于測(cè)距(range-based)的定位和無(wú)需測(cè)距(range-free)的定位;根據(jù)部署的場(chǎng)合可分為室外定位和室內(nèi)定位［2］。通常情況下，基于測(cè)距的定位算法的定位精度高于無(wú)需測(cè)距的定位算法的定位精度?；跍y(cè)距定位的常用方法包括角度定位(AOA)［3］、三邊定位(trilateration)和極大似然估計(jì)等。常用的測(cè)距方式包括接收信號(hào)指示強(qiáng)度(RSSI)［4］、信號(hào)傳播時(shí)間/時(shí)間差/往返時(shí)間(TOA/TDOA/RTOF)［5］、接收信號(hào)相位差(PDOA)、近場(chǎng)電磁測(cè)距(NFER)等。由于基于RSSI的測(cè)距方式無(wú)需增加額外設(shè)備、簡(jiǎn)單易行，在近年來(lái)發(fā)表的研究成果中得到廣泛采用。

近年來(lái)，許多學(xué)者將智能算法應(yīng)用于基于測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)定位算法中。文獻(xiàn)［6－7］使用粒子群優(yōu)化算法定位，取得了優(yōu)于極大似然估計(jì)法等算法的定位結(jié)果，但是由于單一智能算法性能存在缺陷，必須進(jìn)行改進(jìn)以滿足無(wú)線傳感器網(wǎng)絡(luò)定位的實(shí)際應(yīng)用。文獻(xiàn)［8－10］針對(duì)粒子群優(yōu)化算法的缺點(diǎn)提出改進(jìn)算法，克服了粒子群優(yōu)化算法后期易陷入局部最優(yōu)的缺陷，進(jìn)一步提高了定位精度。但是上述改進(jìn)算法避免粒子陷入局部最優(yōu)的能力有限，不能保證粒子有效逃離局部最優(yōu)。針對(duì)基于粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)定位算法后期易陷入局部最優(yōu)、算法穩(wěn)定性較差的缺陷，提出一種粒子群和人工魚群融合優(yōu)化算法，將其應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中，以克服上述缺陷，提高定位算法的性能。

1 RSSI測(cè)距模型

節(jié)點(diǎn)在通信時(shí)可以直接獲取RSSI值，估計(jì)出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離。很多學(xué)者對(duì)RSSI測(cè)距進(jìn)行了深入研究，根據(jù)實(shí)驗(yàn)環(huán)境的不同建立了多種基于RSSI的測(cè)距模型。其中，對(duì)數(shù)－常態(tài)分布模型(log-distance distribution)考慮了實(shí)際環(huán)境的復(fù)雜性，能反映信號(hào)傳播過(guò)程中引入的噪聲對(duì)測(cè)距結(jié)果的影響［11－12］。對(duì)數(shù)－常態(tài)分布模型路徑損耗計(jì)算公式如下:

式(1)中:d為發(fā)射端與接收端之間的距離;PL(d)是經(jīng)過(guò)距離d后的路徑損耗;n為信道衰減指數(shù)，一般取值為2～5;Xδ是均值為0、標(biāo)準(zhǔn)差為δ的高斯隨機(jī)噪聲變量，標(biāo)準(zhǔn)差的取值一般為4～10;d0是參考距離，一般取1 m。對(duì)式(1)化簡(jiǎn)得到:

式(2)中A為1 m處的RSSI值。通常情況下，測(cè)距誤差隨著測(cè)量距離的增加而增大［13］，即由較大的RSSI值計(jì)算得到的距離值誤差較小，而由較小的RSSI值計(jì)算得到的距離值誤差較大。

2 相關(guān)知識(shí)

2.1 粒子群優(yōu)化算法

粒子群優(yōu)化(particle swarm optimization，PSO)算法是在無(wú)線傳感器網(wǎng)絡(luò)定位中常用的一種群體智能優(yōu)化算法，文獻(xiàn)［6－10］均采用PSO算法或改進(jìn)的PSO算法。PSO算法是一種操作簡(jiǎn)單的群體智能優(yōu)化算法，其實(shí)現(xiàn)原理如下:

假設(shè)在D維的搜索空間內(nèi)，存在一個(gè)種群大小為M的粒子群;存在一個(gè)數(shù)量為N的搜索目標(biāo)群。每個(gè)粒子在空間中的位置坐標(biāo) xi=(xi1，xi2，…，xid)，搜索速度 vi=(vi1，vi2，…，vid)，搜索到的個(gè)體最優(yōu)位置為pi=(pi1，pi2，…，pid)，搜索到的全局最優(yōu)位置為gb=(gb1，gb2，…，gbd)，其中，i=(1，2，…，M)，d=(1，2，…，D)。算法采用下列公式對(duì)粒子進(jìn)行操作［14］:

式中:學(xué)習(xí)因子c1和c2是非負(fù)的常數(shù)，常設(shè)c1=c2=2;r1和r2是介于［0，1］的隨機(jī)數(shù);w為慣性權(quán)重，用來(lái)保持局部搜索和全局搜索的平衡，較大的w有利于算法的全局搜索能力，較小的w有利于算法的局部搜索能力;vid∈［－vmax，vmax］，vmax過(guò)大容易使粒子飛離最優(yōu)解，vmax過(guò)小容易使粒子陷入局部最優(yōu)，粒子的速度通常設(shè)為每維變換范圍的10%～20%;k為當(dāng)前迭代次數(shù);T為終止迭代次數(shù)。

2.2 人工魚群算法

人工魚群(artificial fish school，AFS)算法由李曉磊等于2002年提出［15］，是一種全局尋優(yōu)能力強(qiáng)、簡(jiǎn)單、易操作的群體智能優(yōu)化算法。該算法通過(guò)模擬魚類的覓食、群聚、追尾、隨機(jī)等行為在搜索域中進(jìn)行尋優(yōu)。AFS算法的數(shù)學(xué)模型中各變量參數(shù)描述如下:人工魚群個(gè)體大小為N;人工魚個(gè)體的狀態(tài) Xi=(x1，x2，…，xn)，其中xi(i=1，2，…，n)為待優(yōu)化變量;第i條人工魚當(dāng)前所在位置的食物濃度即目標(biāo)函數(shù)Yi;人工魚個(gè)體之間的距離為di，j;人工魚的感知范圍為Visual;人工魚移動(dòng)的最大步長(zhǎng)為Step;擁擠度為delta;覓食行為嘗試的最大次數(shù)為try_number;當(dāng)前覓食行為次數(shù)為n;最大迭代次數(shù)為MAXGEN。

1)覓食行為

設(shè)Xi為人工魚當(dāng)前的狀態(tài)，Xj為其感知范圍Visual內(nèi)隨機(jī)選擇的一個(gè)狀態(tài)，如果待優(yōu)化問(wèn)題是求極大值，則當(dāng)Yi＜Yj時(shí)人工魚向Xj方向前進(jìn)1步(若待優(yōu)化問(wèn)題是求極小值，則當(dāng)Yi＞Yj時(shí)人工魚向Xj方向前進(jìn)1步);反之，在感知范圍內(nèi)重新選擇狀態(tài)Xj，判斷是否滿足上述條件。當(dāng)嘗試次數(shù)達(dá)到最大值try_number時(shí)，若仍未找到滿足條件的Xj，人工魚則隨機(jī)移動(dòng)1步。

2)聚群行為

對(duì)于人工魚探索當(dāng)前范圍內(nèi)(即di，j＜Visual)的伙伴數(shù)目nf及中心位置Xc，若滿足Yc/nf＞delta*Yi，則表明伙伴中心的食物濃度較高并且人工魚數(shù)量不多，則人工魚朝伙伴的中心位置方向移動(dòng)1步;否則執(zhí)行覓食行為。

3)追尾行為

對(duì)于人工魚探索當(dāng)前范圍內(nèi)(即di，j＜Visual)的伙伴數(shù)目nf及食物濃度最大的伙伴Xj，若滿足Yj/nf＞delta*Yi，則表明伙伴Xj處的食物濃度較高并且周圍人工魚數(shù)量不多，則人工魚朝伙伴Xj位置方向移動(dòng)1步;否則執(zhí)行覓食行為。

4)隨機(jī)行為

隨機(jī)行為即人工魚在Visual內(nèi)隨機(jī)選擇一個(gè)移動(dòng)方向Xi ext，人工魚按如下公式進(jìn)行該行為:

其中r是［－1，1］區(qū)間內(nèi)的隨機(jī)數(shù)。

2.3 WSN 定位原理

假設(shè)在一定區(qū)域內(nèi)布置有M個(gè)錨節(jié)點(diǎn)，N個(gè)未知節(jié)點(diǎn)。錨節(jié)點(diǎn)的坐標(biāo)為Ai(xi，yi)，i=(1，2，…，M)，未知節(jié)點(diǎn)的坐標(biāo)為Nj(xj，yj)，j=(1，2，…，N)，已知錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的距離測(cè)量值di?；跍y(cè)距的WSN定位問(wèn)題可描述為如下的最優(yōu)化問(wèn)題:

基于群體智能優(yōu)化的WSN定位方法采用式(7)作為適應(yīng)度函數(shù)，WSN的錨節(jié)點(diǎn)相當(dāng)于該算法中的種群S，未知節(jié)點(diǎn)的坐標(biāo)即要搜索的位置。

3 基于粒子群和人工魚群融合優(yōu)化的WSN定位算法

3.1 算法基本思想

PSO算法和AFS算法都是典型的群體智能優(yōu)化算法。PSO算法具有收斂速度快的特點(diǎn)，但在算法后期，由于粒子同一化，算法易陷入局部最優(yōu);AFS算法尋優(yōu)速度較快，并具有全局尋優(yōu)的能力，但算法精度略低于PSO算法。綜合利用兩種算法的優(yōu)點(diǎn)，提出一種適合WSN定位的粒子群和人工魚群融合優(yōu)化(hybrid optimization algorithm based on particle swarm and artificial fish swarm algorithm，PSO-AFS)算法，該算法能克服兩種算法各自存在的缺點(diǎn)。

3.2 算法分析和實(shí)現(xiàn)

PSO-AFS算法的具體執(zhí)行過(guò)程如下:

1)初始化種群S。在尋優(yōu)區(qū)域內(nèi)隨機(jī)或固定部署一個(gè)大小為S的種群，合理設(shè)置PSO算法和AFS算法各變量的參數(shù)，算法的參數(shù)設(shè)置如下:

① 對(duì)于PSO 算法，c1=c2=2，vmax=5，vmin=－5，wmax=0.9，wmin=0.4;

② 對(duì)于AFS算法visual=3.5，step=1，delta=0.618，try_number=50;

③PSO-AFS算法的參數(shù)與PSO算法和AFS算法對(duì)應(yīng)的參數(shù)相同。

2)設(shè)置公告板。公告板數(shù)值為besty，用來(lái)記錄每次迭代產(chǎn)生的適應(yīng)度函數(shù)的最優(yōu)值，公告板初值為初始化的種群S對(duì)應(yīng)的適應(yīng)度函數(shù)值。

3)迭代尋優(yōu)。在每次迭代中對(duì)種群分別用PSO算法、AFS算法進(jìn)行操作，PSO算法每次迭代得到適應(yīng)度函數(shù)最優(yōu)值為T1，AFS算法每次迭代得到適應(yīng)度函數(shù)最優(yōu)值為T2。

4)種群變異。分別對(duì)兩種算法各自種群個(gè)體的適應(yīng)度函數(shù)值排序，對(duì)其中最差的30%個(gè)體按式:X=bestx+rand進(jìn)行變異操作，PSO算法和AFS算法各自更新種群，分別得到新的種群S1、S2。

5)更新公告板和種群。比較兩種算法得到的適應(yīng)度函數(shù)最優(yōu)值T1和T2，對(duì)公告板和種群進(jìn)行更新，其偽代碼如下:

6)停止迭代，輸出結(jié)果。當(dāng)尋優(yōu)的誤差小于控制值或達(dá)到最大迭代次數(shù)MAXGEN時(shí)停止迭代，輸出尋優(yōu)結(jié)果及其對(duì)應(yīng)的種群個(gè)體的狀態(tài)，即未知節(jié)點(diǎn)位置。

4 算法仿真與分析

本文采用Matlab進(jìn)行仿真實(shí)驗(yàn)，分別考慮兩種仿真環(huán)境:①在一定區(qū)域內(nèi)進(jìn)行單個(gè)未知節(jié)點(diǎn)定位;②模擬具體環(huán)境，在一定區(qū)域內(nèi)鋪設(shè)大量未知節(jié)點(diǎn)進(jìn)行整體定位。

4.1 仿真場(chǎng)景1

在30 m×30 m的面積內(nèi)隨機(jī)部署8個(gè)錨節(jié)點(diǎn)，1個(gè)未知節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑為30 m，算法的最大迭代次數(shù)MAXGEN為50次。

1)算法穩(wěn)定性和收斂速度仿真結(jié)果分析

設(shè)定位誤差控制值為0 m，測(cè)距誤差為10%。圖1是3種算法的收斂曲線，由圖可知:PSO-AFS算法的收斂曲線與PSO算法、AFS算法相比始終更加平滑、穩(wěn)定，且收斂速度明顯快于另外兩種算法。

圖1 算法的收斂曲線

設(shè)平均定位誤差(誤差控制值)為0.5 m，測(cè)距誤差0%，獨(dú)立進(jìn)行20次實(shí)驗(yàn)，分析每次實(shí)驗(yàn)中3種算法的終止迭代次數(shù)。由圖2可知:相同精度下PSO-AFS算法每次最終迭代次數(shù)的值波動(dòng)較小，說(shuō)明PSO-AFS算法的穩(wěn)定性較好，明顯優(yōu)于另外兩種算法。

2)算法的定位精度仿真結(jié)果分析

為了驗(yàn)證基于PSO-AFS算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法的性能，設(shè)置不同仿真參數(shù)，研究迭代次數(shù)和測(cè)距誤差對(duì)定位誤差的影響，分別獨(dú)立進(jìn)行100次實(shí)驗(yàn)。

設(shè)測(cè)距誤差為0%，設(shè)置不同最大迭代次數(shù)進(jìn)行仿真實(shí)驗(yàn)。圖3為3種算法的平均定位誤差隨迭代次數(shù)的變化情況。由于PSO-AFS算法的收斂速度明顯快于AFS、PSO兩種算法，所以在迭代次數(shù)較少的情況下，PSO-AFS算法的定位精度明顯高于其他兩種算法，體現(xiàn)了PSO-AFS算法的優(yōu)越性。由于PSO-AFS算法在進(jìn)行迭代尋優(yōu)時(shí)收斂速度和尋優(yōu)精度性能更好，用較短的計(jì)算時(shí)間即可得到較精確的計(jì)算結(jié)果。

圖2 算法的終止迭代次數(shù)

圖3 迭代次數(shù)對(duì)平均定位誤差的影響

設(shè)最大迭代次數(shù)MAXGEN為10次，研究3種算法在不同測(cè)距誤差情況下的定位精度。由圖4可知，隨著平均測(cè)距誤差的增加，3種算法的定位誤差均呈上升趨勢(shì)，這是由于基于測(cè)距的定位算法受測(cè)距誤差影響較大造成的。盡管3種算法的定位誤差均受測(cè)距誤差影響較大，但PSO-AFS算法的定位誤差始終小于其他兩種算法。PSO-AFS算法與PSO算法相比平均定位誤差減小了0.6 m左右，與AFS算法相比平均定位誤差減小了0.4 m左右。

圖4 平均測(cè)距誤差對(duì)平均定位誤差的影響

4.2 仿真場(chǎng)景2

改變傳感器節(jié)點(diǎn)部署區(qū)域和節(jié)點(diǎn)數(shù)目，在100 m×100 m的二維平面內(nèi)隨機(jī)部署n個(gè)錨節(jié)點(diǎn)和30個(gè)未知節(jié)點(diǎn);節(jié)點(diǎn)通信半徑為30 m;設(shè)最大迭代次數(shù)MAXGEN為20次;RSSI測(cè)距算法中，設(shè)信道衰減指數(shù)n為4，為了盡量模擬實(shí)際環(huán)境噪聲的影響，設(shè)零均值高斯隨機(jī)噪聲變量Xδ的標(biāo)準(zhǔn)差δ為4。

圖5為未知節(jié)點(diǎn)平均定位誤差隨錨節(jié)點(diǎn)個(gè)數(shù)的變化情況，由圖可知:隨著錨節(jié)點(diǎn)數(shù)目的增加，3種算法的平均定位誤差均呈下降趨勢(shì)，但當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)增加到一定程度時(shí)，平均定位誤差的變化趨勢(shì)減小甚至達(dá)到了臨界狀態(tài)，但PSO-AFS算法的平均定位誤差始終小于其他兩種算法的平均定位誤差。

圖5 錨節(jié)點(diǎn)數(shù)目對(duì)平均定位誤差的影響

5 結(jié)束語(yǔ)

由于單一智能優(yōu)化算法存在不同的性能缺陷，基于單一智能優(yōu)化算法的WSN定位算法也存在著不足。PSO算法收斂速度快、尋優(yōu)精度高，但后期易陷入局部最優(yōu)，導(dǎo)致個(gè)別時(shí)候?qū)?yōu)結(jié)果較差;AFS算法的穩(wěn)定性較好，全局尋優(yōu)能力強(qiáng)，不易陷入局部最優(yōu)，但其收斂速度慢于PSO算法，且尋優(yōu)精度略低于PSO算法。PSO-AFS算法綜合利用了PSO算法收斂速度快、尋優(yōu)精度高和AFS算法全局尋優(yōu)能力強(qiáng)、穩(wěn)定性好的優(yōu)點(diǎn)，克服了各自存在的不足?；赑SO-AFS算法的WSN定位算法比基于單一PSO算法或AFS算法的WSN定位算法的性能更加優(yōu)越。仿真結(jié)果表明:PSO-AFS定位算法只需較少的迭代次數(shù)即可得出較準(zhǔn)確的定位結(jié)果，且定位精度和穩(wěn)定性較好，適合于WSN的應(yīng)用。

［1］宋文，王兵，周應(yīng)兵，等.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京:電子工業(yè)出版社，2007:1－10.

［2］李曉維，徐勇軍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京:北京理工大學(xué)出版社，2007:191－192.

［3］Al-Jazzar Saleh，Ghogho Mounir，McLernon Desmond.A joint TOA/AOA constrained minimization method for locating wireless devices in non-line-of-sight environment［J］.IEEE Transactions on Vehicular Technology，2009，58(1):468－472.

［4］方震，趙湛，郭鵬，等.基于RSSI的測(cè)距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20(11):2528－2530.

［5］Savvides A，Han C C，Strivastava M B.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//Proc.of MOBICOM.［S.l.］:［s.n.］，2001:166－179.

［6］Low K S，Nguyenh A G.Optimization of sensor node locations in a wireless sensor network［C］//ICNC’08 4th Int Conf on Natural Computation.Piscataway:IEEE，2008:286－290.

［7］陳志奎，司威.傳感器網(wǎng)絡(luò)的粒子群優(yōu)化定位算法［J］.通信技術(shù)，2011，44(1):102－104，108.

［8］黃艷，臧傳治，于海斌.基于改進(jìn)粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.控制與決策，2012，27(1):156－160.

［9］馮秀芳，呂淑芳.基于RSSI和分步粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.控制與決策，2014，29(11):1－7.

［10］王俊，李樹強(qiáng)，劉剛.無(wú)線傳感器網(wǎng)絡(luò)三維定位交叉粒子群算法［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45(5):233－238.

［11］陳維克，李文鋒，首珩，等.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心算法定位［J］.武漢理工大學(xué)學(xué)報(bào)，2006，30(2):265－268.

［12］張先超，劉興長(zhǎng)，張春園.基于次錨節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)加權(quán)質(zhì)心定位算法［J］.傳感器與微系統(tǒng)，2015，34(2):143－146.

［13］Chen W，Mei T，Sun L，et al.Error analyzing for RSSI-based localization in wireless sensor networks［C］//Intelligent Control and Automation，2008.WCICA 2008.7th World Congress on.IEEE.［S.l.］:IEEE，2008:2701－2706.

［14］史峰，王輝.MATLAB智能算法30個(gè)案例分析［M］.北京:北京航空航天大學(xué)出版社，2011:102－107.

［15］李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法［D］.杭州:浙江大學(xué)，2003.