基于混沌粒子群與Taylor算法的協(xié)同定位算法研究

康 婷，魏勝非

(東北師范大學(xué)物理學(xué)院，吉林長(zhǎng)春 130024)

0 引言

在無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，節(jié)點(diǎn)的位置信息非常重要，按照是否需要測(cè)量節(jié)點(diǎn)間的距離或角度，將無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方式分為2種，距離相關(guān)和距離無(wú)關(guān)。距離相關(guān)的定位算法主要有利用信號(hào)到達(dá)時(shí)間差[1]、接收信號(hào)強(qiáng)度[2]、信號(hào)到達(dá)時(shí)間[3]、信號(hào)到達(dá)角度[4]等信息測(cè)量相鄰節(jié)點(diǎn)距離，這些算法定位精度相對(duì)較高[5]。

本文選擇TDOA(time difference of arrival)定位方法，其核心是通過測(cè)量從未知節(jié)點(diǎn)發(fā)出的無(wú)線信號(hào)傳播到已知坐標(biāo)信息的多個(gè)信標(biāo)節(jié)點(diǎn)之間的時(shí)間差來確定未知節(jié)點(diǎn)的位置。無(wú)線信號(hào)在傳輸時(shí)易受到很多因素影響，例如多徑效應(yīng)、遠(yuǎn)近效應(yīng)和非視距傳播等，致使TDOA測(cè)量值存在誤差，所以轉(zhuǎn)換成求解TDOA測(cè)量值構(gòu)成的非線性雙曲線方程組的問題[6]。目前有很多種求解的方法，如Fang算法[7]、Taylor算法[8]、PSO算法[9]等。

針對(duì)Taylor算法定位時(shí)存在受初值影響的情況，本文提出一種混沌粒子群與Taylor算法協(xié)同定位的方式：首先用混沌粒子群算法求解TDOA方程組，獲得一個(gè)精度較高的未知節(jié)點(diǎn)的估計(jì)坐標(biāo)值，然后將這個(gè)估計(jì)值作為Taylor算法的初值來迭代運(yùn)算，最后完成對(duì)未知節(jié)點(diǎn)的坐標(biāo)估計(jì)。

1 基于TDOA的節(jié)點(diǎn)定位方法

(1)

式中：c為電波傳播速度；di,1為TDOA測(cè)量值；cni,1為測(cè)量時(shí)加入的噪聲。

未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離由以下公式計(jì)算可得：

所以

(2)

可以得到

ΔR=Ri-R1+cN=

(3)

當(dāng)M≥3時(shí)，采用極大似然法求解未知節(jié)點(diǎn)坐標(biāo)，由于Ri,1服從高斯分布，滿足均值為Ri-R1、方差為α2，因此似然函數(shù)為

(4)

求當(dāng)似然函數(shù)的值最大時(shí)，所得到的坐標(biāo)值，等價(jià)于求解

即

(x,y)=arg{min[(ΔR-Ri+R1)T(ΔR-Ri+R1)]}

(5)

當(dāng)此非線性函數(shù)方程值最小時(shí)，得到未知節(jié)點(diǎn)的估計(jì)值，若用解析法去求解會(huì)非常困難。因此，本文采用混沌粒子群算法求解，得到未知節(jié)點(diǎn)的初始坐標(biāo)估計(jì)值。

2 W-CLSPSO算法

2.1 標(biāo)準(zhǔn)粒子群算法

PSO[11]算法是一種集群智能方法，它的提出是因?yàn)槭艿搅锁B群捕食行為的啟發(fā)，利用群體間的競(jìng)爭(zhēng)與協(xié)作從而找到全局最優(yōu)解，該算法容易實(shí)現(xiàn)，并具有快速的搜索能力。迭代時(shí)，粒子更新自己的位置和速度是通過跟蹤個(gè)體極值pi,j和群體極值pg,j，更新方式如下：

vi,j(t+1)=w×vi,j(t)+c1×r1×[pi,j-xi,j(t)]+
c2×r2×[pg,j-xi,j(t)]

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1)

(7)

式中：c1和c2為學(xué)習(xí)因子；r1和r2為0到1之間均勻分布的隨機(jī)數(shù)；w為慣性權(quán)重。

粒子群優(yōu)化算法的主要優(yōu)點(diǎn)是容易工程實(shí)現(xiàn)，計(jì)算簡(jiǎn)便，但也有明顯的缺點(diǎn)，容易陷入局部極值點(diǎn)、進(jìn)化后期收斂速度慢、定位精度低等。

2.2 基于線性權(quán)重遞減的混沌粒子群優(yōu)化算法(W-CLSPSO)

為克服標(biāo)準(zhǔn)PSO這些缺點(diǎn)，將混沌的思想引入到粒子群算法[12]當(dāng)中，本文選擇Logistic混沌系統(tǒng)：

Zn+1=μZn(1-Zn)

(8)

式中μ為控制變量。

當(dāng)μ值一定后，隨機(jī)給定一個(gè)初始值Z0∈[0,1]就可以迭代出一個(gè)時(shí)間序列Z1，Z2，Z3，…。

由于混沌運(yùn)動(dòng)具有遍歷性，因此混沌粒子群算法主要利用這個(gè)特性，以目前粒子群搜索到的最優(yōu)位置為基礎(chǔ)，產(chǎn)生一個(gè)混沌序列，把這個(gè)混沌序列中的最優(yōu)位置粒子替代當(dāng)前粒子群中任意一個(gè)粒子的位置[13]。

在粒子群算法中，慣性權(quán)重w對(duì)算法的挖掘能力和搜索能力有一定的控制能力。文獻(xiàn)[14]通過實(shí)驗(yàn)證明，w隨算法迭代次數(shù)線性減小時(shí)，算法具有很強(qiáng)的收斂性。

消費(fèi)價(jià)格包括出口價(jià)格和分銷成本，其中pj(φ)表示以本國(guó)貨幣表示的出口價(jià)格，τj表示本國(guó)出口到目的地j的冰山成本，εj表示本國(guó)與目的地j名義匯率[注]本文采用間接標(biāo)價(jià)法，即εj越大說明本國(guó)貨幣相對(duì)于目的地(國(guó))的貨幣升值。，λ表示企業(yè)參與垂直專業(yè)化程度，0≤λ≤1。假設(shè)產(chǎn)品質(zhì)量越高則產(chǎn)品的分銷成本越高，ηj表示目的地j的實(shí)際分銷成本，wj表示出口目j的地的工資。代表性家庭對(duì)產(chǎn)品φ的需求為：

(9)

式中：wmax為初始慣性權(quán)重；wmin為終止慣性權(quán)重；t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。

算法[15]步驟如下：

步驟1：對(duì)各個(gè)參數(shù)進(jìn)行初始化設(shè)置。學(xué)習(xí)因子c1和c2，種群規(guī)模N，慣性權(quán)重wmax和wmin，混沌尋優(yōu)的次數(shù)和進(jìn)化的次數(shù)。

步驟2：隨機(jī)產(chǎn)生粒子數(shù)為N的種群。

步驟3：利用式(6)、式(7)、式(9)更新粒子的位置、速度和權(quán)重。

步驟4：運(yùn)用混沌對(duì)最優(yōu)位置Pg=(pg1,pg2,pg3,…，pgD)進(jìn)行優(yōu)化。Logistic方程(8)的定義域?yàn)閇0，1]，將Pgi(i=1,2,…，D)映射到此定義域中，其中：

Zi=(Pgi-ai)/(bi-ai),i=1,2,…,D

式中：ai和bi為第i維變量的取值范圍。

步驟5：從當(dāng)前的種群中隨機(jī)挑選出一個(gè)粒子用得到的最優(yōu)解p*來代替。

3 Taylor算法

Taylor算法是一種遞歸算法，它將初始位置代入到算法，通過求解TDOA測(cè)量誤差的局部最小二乘(LS)來改進(jìn)。這種算法首先在未知節(jié)點(diǎn)的估計(jì)位置對(duì)其泰勒級(jí)數(shù)展開，對(duì)展開式中的二階以上分量可以忽略不計(jì)，那么就有如下方程式：

h=GΔ+ε

(10)

式中：

Ri(i=1,2,…,M)為各個(gè)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離。式(10)的加權(quán)最小二乘解為

Δ=[ΔxΔy]T=(GTQ-1G)-1GTQ-1h

(11)

式中Q為測(cè)量值的協(xié)方差矩陣。

Taylor算法迭代循環(huán)的過程如下：首先選擇ε當(dāng)門限，用來判斷是否可以結(jié)束此次迭代，然后通過比較迭代次數(shù)是否大于預(yù)先設(shè)定好的迭代次數(shù)，決定是否結(jié)束迭代，如果迭代結(jié)束，則此時(shí)的[x+Δx,y+Δy]將作為未知節(jié)點(diǎn)的坐標(biāo)值。

4 W-CLSPSP/Taylor協(xié)同定位

Taylor算法是一種需要給定一個(gè)初值進(jìn)行泰勒級(jí)數(shù)展開的算法，假如節(jié)點(diǎn)的真實(shí)值和估計(jì)值差距很大，將會(huì)導(dǎo)致算法不容易收斂，定位精度就會(huì)較低。所以使用W-CLSPSO初步估計(jì)未知節(jié)點(diǎn)的坐標(biāo)，這樣就保證了Taylor算法的初值具有了一定的精度，然后利用Taylor算法迭代計(jì)算，使得最終獲得的坐標(biāo)值具備較高的精度。

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

為驗(yàn)證算法的有效性，用Matlab仿真平臺(tái)對(duì)算法進(jìn)行仿真，設(shè)節(jié)點(diǎn)分布在2 m×2 m的正方形區(qū)域內(nèi)，在該區(qū)域部署6個(gè)節(jié)點(diǎn)，5個(gè)錨節(jié)點(diǎn)坐標(biāo)分別為(0，0)，(0，2)，(2，0) ，(2，2)，(1，1)；1個(gè)作為未知節(jié)點(diǎn)，其真實(shí)坐標(biāo)為(0.6，1.6)，單位是m。

算法初始化參數(shù)設(shè)置為：粒子群個(gè)數(shù)為20，學(xué)習(xí)因子c1=c2=1.494 45，最大迭代次數(shù)為500，其中標(biāo)準(zhǔn)PSO中w=0.7，CLSPSO中w=0.7，W-CLSPSO中wmax=0.9，wmin=0.4，Taylor算法的門限為ε=0.002，初始估計(jì)坐標(biāo)為(0.6,1.6)，最大迭代次數(shù)30。節(jié)點(diǎn)測(cè)距時(shí)加入一個(gè)噪聲N×randn，此噪聲服從正態(tài)分布，單位是m。3種粒子群算法的收斂圖如圖1所示。

圖1 算法收斂圖

與標(biāo)準(zhǔn)PSO和CLSPSO算法相比，W-CLSPSO算法大約經(jīng)過100次迭代，就可以達(dá)到滿意的解，說明該算法定位速度很快。

在相同條件下，對(duì)標(biāo)準(zhǔn)PSO、CLSPSO、W-CLSPSO 3種算法在不同噪聲下進(jìn)行200次坐標(biāo)估計(jì)，求平均估計(jì)坐標(biāo)(x,y)，如表1所示，其RMSE=[(x-x0)2+(y-y0)2]1/2，如圖2所示。

表1 PSO、CLSPSO、W-CLSPSO 3種算法的估計(jì)坐標(biāo)

m

圖2 PSO、CLSPSO、W-CLSPSO3種算法估計(jì)坐標(biāo)的均方差比較

通過表1和圖2可以看出，當(dāng)噪聲指數(shù)在0.1 m以下時(shí)，3種算法的RMSE值差別很小，在噪聲指數(shù)N增大的過程中，W-CLSPSO算法的RMSE比PSO和CLSPSO算法都要小，實(shí)驗(yàn)表明，W-CLSPSO算法相比于其他兩種算法，具有更好的定位精度和收斂性。

在相同條件下對(duì)Fang算法、Taylor算法和W-CLSPSO以及W-CLSPSO/Taylor協(xié)同算法在不同噪聲下進(jìn)行200次坐標(biāo)估計(jì)，求平均估計(jì)坐標(biāo)(x,y)，如表2所示，RMSE如圖3所示。

表2 Fang、Taylor、W-CLSPSO、W-CLSPSO/Taylor4種算法的估計(jì)坐標(biāo) m

圖3 Fang、Taylor、W-CLSPSO、W-CLSPSO/Taylor4種算法坐標(biāo)估計(jì)的均方差比較

通過表2和圖3可以看出，當(dāng)噪聲指數(shù)在0.15 m以下時(shí)，4種算法的RMSE值差別很小，在噪聲指數(shù)N從0.15 m增大的過程中，W-CLSPSO/Taylor算法的RMSE明顯小于其他3種算法，實(shí)驗(yàn)表明，W-CLSPSO/Taylor算法對(duì)坐標(biāo)估計(jì)具有較高的精度。

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

在無(wú)線傳感器網(wǎng)絡(luò)中，針對(duì)TDOA定位方式，Taylor算法容易受初值影響較大致使節(jié)點(diǎn)定位精度低、后期不容易收斂等缺陷，提出了一種W-CLSPSO與Taylor算法協(xié)同定位的方式。經(jīng)實(shí)驗(yàn)表明，W-CLSPSO/Taylor算法與其他定位算法相比擁有其明顯的優(yōu)勢(shì)，極大提高了定位精度和全局搜索能力，為無(wú)線傳感器網(wǎng)絡(luò)的定位問題提供良好的參考價(jià)值。