混沌粒子群在節(jié)點(diǎn)定位中的應(yīng)用

楊鵑

摘要：該文基于節(jié)點(diǎn)定位中經(jīng)常用到方程組的求解問題，采用混沌粒子群算法用于最優(yōu)解的求解?；煦缌Ｗ尤夯趥鹘y(tǒng)粒子群，具有建模容易，算法簡單，收斂速度快的優(yōu)點(diǎn)；考慮到粒子群的局部最優(yōu)問題，該文在傳統(tǒng)粒子群的基礎(chǔ)上，添加混沌擾動，擴(kuò)大粒子群的應(yīng)用范圍，擺脫局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，在相同工作條件下，混沌粒子群算法相比于最小二乘算法，定位誤差明顯降低，達(dá)到了預(yù)期的目標(biāo)。

關(guān)鍵詞：節(jié)點(diǎn)定位；粒子群算法；混沌擾動；最優(yōu)解

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）35-8578-02

Chaos PSO for the Application of the Node Localization

YANG Juan

（Cheng De Petroleum College， Chengde 067000，China）

Abstract： In this paper， considered the equations problem of solving in node localization， this paper is usde chaos particle swarm optimization （pso） algorithm used in the solution of the optimal solution. Chaotic particle swarm based on the traditional particle swarm with the advantages ofeasy modeling， simple algorithm ， fast convergence rate ； Considering the local optimal problem of particle swarm， in this paper， on the basis of the traditional particle swarm， add the chaos disturbance， enlarge the application range of particle swarm， get rid of the local optimum. Experimental results show that under the same working conditions， the chaos particle swarm optimization （pso） compared to the least squares algorithm， the position error is decreased obviously， and has reached the expected goal.

Key words： node localization； Particle swarm optimization algorithm； Chaos disturbance； The optimal solution

Zigbee無線傳感網(wǎng)絡(luò)基于IEEE802.15.4協(xié)議，通過節(jié)點(diǎn)間射頻信號的發(fā)射和接收，實(shí)現(xiàn)數(shù)據(jù)的傳輸。節(jié)點(diǎn)定位是zigbee無線通信研究的重點(diǎn)內(nèi)容之一[1]，如何實(shí)現(xiàn)簡單算法、低硬件配置以及高定位精度現(xiàn)已成為熱點(diǎn)的研究內(nèi)容[2]?；跍y距和無需測距的定位算法，以本文研究的DV-HOP算法為例，往往需要用到方程組的求解[3]， 粒子群優(yōu)化算法在求解最優(yōu)解方面具有較大的優(yōu)勢，該算法計(jì)算簡單，收斂速度快，具有廣泛的應(yīng)用性，近年來許多學(xué)者將粒子群算法應(yīng)用在節(jié)點(diǎn)定位的方程組求解中，但粒子群容易出現(xiàn)局部最優(yōu)的問題，限制了PSO算法的使用。該文采用混沌粒子群算法，將混沌搜索添加到粒子群算法中，擴(kuò)大算法的搜索范圍，提高節(jié)點(diǎn)的定位精度。

1 DV-Hop定位算法[4]

無需測距的DV-Hop定位算法利用未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間的平均跳距和跳數(shù)估算節(jié)點(diǎn)間的距離，通過求解方程組估算未知節(jié)點(diǎn)的坐標(biāo)[5]。

DV-Hop定位算法[6]的定位過程如下：

1） 未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間跳數(shù)：跳數(shù)初始值為0，錨節(jié)點(diǎn)將跳數(shù)加1后，向鄰居節(jié)點(diǎn)廣播自身信息和跳數(shù)，未知節(jié)點(diǎn)記錄每個(gè)錨節(jié)點(diǎn)的信息和與最小跳數(shù)。

2） 未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的平均跳距：根據(jù)記錄的錨節(jié)點(diǎn)位置和跳數(shù)，估算每跳的實(shí)際距離。錨節(jié)點(diǎn)將計(jì)算的平均跳距廣播至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)記錄接收到的第一個(gè)平均跳距，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。

3） 建立未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離方程組：平均跳距和跳數(shù)的乘積就是相鄰兩節(jié)點(diǎn)間的距離，根據(jù)記錄的錨節(jié)點(diǎn)的平均跳距和跳數(shù)，計(jì)算從未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的線段和，即可建立節(jié)點(diǎn)間的距離方程。

4） 求解距離方程組。

2 方程組的求解

DV-Hop算法的定位計(jì)算最終轉(zhuǎn)化為方程組的求解，最優(yōu)解的求解影響到算法的定位精度，距離方程組如下所示。

其中（[xi]，[yi]）為未知節(jié)點(diǎn)坐標(biāo)，（[xj]，[yj]）為錨節(jié)點(diǎn)坐標(biāo)，[dij]為估算的節(jié)點(diǎn)間的距離值。最優(yōu)解的求解目前較多采用遺傳算法、粒子群算法以及最小二乘算法。該文考慮到節(jié)點(diǎn)定位的工作環(huán)境，采用粒子群算法求解方程組，該算法是一種基于隨機(jī)優(yōu)化的算法，在最優(yōu)解求解計(jì)算方面突出特點(diǎn)有：

1） 算法概念簡單，建模容易，搜索個(gè)體無需太多；

2） 計(jì)算量和存儲量相對較少，收斂速度快；

3） 算法具有魯棒性。個(gè)別錯(cuò)誤數(shù)據(jù)不影響算法的求解。

3 粒子群算法

粒子群優(yōu)化算法利用群體之間的協(xié)作與競爭實(shí)現(xiàn)方程組最優(yōu)解的求解?；趥鹘y(tǒng)DV-Hop定位算法對未知節(jié)點(diǎn)的位置估計(jì)誤差較大，可利用粒子群（PSO）優(yōu)化算法，計(jì)算方程組的最優(yōu)解，提高定位精度。

3.1 PSO算法[7]-[8]

粒子群的執(zhí)行過程如下：

假定搜索空間是D維的，群體中共有m個(gè)粒子，第i個(gè)粒子表示為[Xi=（xi1，xi2，…xiD）]，其最優(yōu)的位置為[Pi=（Pi1，Pi2，…PiD）]，粒子的每個(gè)位置就是待求解問題的潛在解，把位置帶入到目標(biāo)函數(shù)，就可以計(jì)算得到適應(yīng)度值，根據(jù)適應(yīng)度值的大小判定粒子的優(yōu)劣。粒子算法的位置和速度按照以下公式計(jì)算。

[vk+1id=ωvkid+c1r1（Pid-xkid）+c2r2（Pgd-xkid）] （2）

[xk+1id=xkid+vk+1id] （3）

其中，[r1]和[r2]是用于保持群體多樣性的隨機(jī)因子，[ω]為慣性權(quán)重，[c1]和[c2]為學(xué)習(xí)因子，使得粒子通過自我總結(jié)和學(xué)習(xí)，逐漸向最優(yōu)解靠近。[ω]值決定了當(dāng)前速度對下次迭代速度的影響程度，取值過大，粒子全局搜索能力較強(qiáng)，但不利于算法的而收斂。如果[ω]值過小，局部挖掘能力較強(qiáng)，有利于算法的收斂，但由于收斂速度較快，容易陷入局部最優(yōu)的問題。當(dāng)[ω]的取值隨著算法迭代次數(shù)逐漸減小時(shí)，算法的收斂性較強(qiáng)。

[ω=ωmax-k（ωmax-ωmin）kmax] （4）

最優(yōu)解的求解程度用適應(yīng)度函數(shù)來表示，基于距離方程組最優(yōu)解的適應(yīng)度函數(shù)采用如下定義。

[f=i=1m（x-xi）2+（y-yi）2-di]

3.2 PSO算法的執(zhí)行過程

1） 初始化粒子群。設(shè)定粒子的初始位置和初始速度；

2） 計(jì)算種群中各個(gè)粒子的適應(yīng)度值；

3） 對種群中的每個(gè)粒子，將它當(dāng)前位置的適應(yīng)度值[f]與它經(jīng)歷過的最好位置[Pi]的適應(yīng)度值[fibest]進(jìn)行比較，如果[f

4） 對種群中的每個(gè)粒子，將它當(dāng)前位置的適應(yīng)度值[fibest]與群體中所經(jīng)歷的最好位置[Pg]的適應(yīng)度值[fbest]進(jìn)行比較，如果[fi

5） 調(diào)整種群中各個(gè)粒子的速度和位置；

6） 達(dá)到預(yù)期精度值或者迭代最大次數(shù)，則結(jié)束計(jì)算。否則，將距最優(yōu)解最遠(yuǎn)的粒子從算法中釋放后，轉(zhuǎn)到步驟2。

7） 輸出全局極值對應(yīng)的粒子位置。

4 混沌粒子群

混沌粒子群基于粒子群算法，添加粒子變異，擴(kuò)大算法的迭代范圍，有利于減少局部最優(yōu)的存在。具體的改進(jìn)思路是首先基于PSO算法，初始化種群，計(jì)算每個(gè)粒子的適應(yīng)度，選出個(gè)體極值和全局極值，利用式（1）和（2）開始迭代尋優(yōu)過程，當(dāng)運(yùn)算到預(yù)先設(shè)定的次數(shù)后，啟動混沌搜索，對歷史最優(yōu)解 [Pg]施加混沌擾動，獲得最優(yōu)解[Pg′]，計(jì)算其適應(yīng)值[fgbest′]并與歷史最優(yōu)解[fgbest] 的適應(yīng)值進(jìn)行比較，如果 [fgbest′

混沌點(diǎn)列的生成過程：

1） 假設(shè)粒子的m維位置向量[xi=（xi1，xi2，…xim）]，映射向量[yi=（yi1，yi2，…yim）]，其中[yik=xik-akbk-ak]，[ak]和[bk]分別是[xik]的下界和上界。

2） 采用Tent映射，對[yi]進(jìn)行變異，產(chǎn)生混沌序列變異[yi′]，變異公式如下。

[yik+1=2yik， 0≤yik≤0.52（1-yik），0.5

3） 將[yi′]映射回[xi′]點(diǎn)列，其中[xik′=ak+yik′（bk-ak）]

5 算法仿真與分析

5.1 仿真環(huán)境

為了驗(yàn)證改進(jìn)算法的有效性，設(shè)定在100×100m的范圍內(nèi)，通信半徑初始距離為50m，初始隨機(jī)生成100個(gè)節(jié)點(diǎn)，錨節(jié)點(diǎn)為28個(gè)，網(wǎng)絡(luò)內(nèi)添加均值為0，方差為5的高斯噪聲，計(jì)算節(jié)點(diǎn)定位的平均誤差值。網(wǎng)絡(luò)初始設(shè)定最大迭代次數(shù)100，誤差因子5%，學(xué)習(xí)因子均為1.8，最大速度6，[ωmax]=0.9，[ωmin=0.5]。

5.2 仿真結(jié)果分析

5.2.1 通信半徑對定位結(jié)果影響

如圖1所示，對比PSO算法和混沌PSO算法，調(diào)整通信半徑值，觀察定位誤差的變化。從圖可以看出，混沌PSO算法比最小二乘算法更能達(dá)到更小的定位誤差。在相同錨節(jié)點(diǎn)密度情況下，通信半徑越小，定位效果越明顯，這也說明該算法相比于最小二乘算法，對節(jié)點(diǎn)密度的要求更低，適用于節(jié)點(diǎn)稀疏的情況。

5.2.2 不同錨節(jié)點(diǎn)數(shù)的定位結(jié)果比較

調(diào)整仿真區(qū)域內(nèi)錨節(jié)點(diǎn)個(gè)數(shù)，觀察在錨節(jié)點(diǎn)密度不同的情況下，平均定位誤差的變化，仿真結(jié)果如圖2所示。比較最小二乘算法和混沌PSO算法的仿真結(jié)果，可看出在相同錨節(jié)點(diǎn)布局情況下，混沌PSO算法比最小二乘算法平均定位誤差相對偏低，定位效果更好。

6 結(jié)束語

本文基于節(jié)點(diǎn)定位的方程組求解問題，采用粒子群算法求解最優(yōu)解，粒子群算法收斂速度快但可能陷入局部最優(yōu)，為了解決此問題，采用混沌搜索引入算法，當(dāng)?shù)螖?shù)達(dá)到設(shè)定次數(shù)，啟動混沌變異，有效提高了 PSO 算法的全局搜索能力，提高了定位算法的精度。

參考文獻(xiàn)：

[1] 張小龍，謝慧英，趙小建.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DV-Hop定位算法[J].計(jì)算機(jī)應(yīng)用，2007，27（11）：2672-2674.

[2] 王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào)，2005，16（5）：857-868.

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

[4] 胡鵬莎.WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)研究[D].南京林業(yè)大學(xué)，2013.

[5] 黃炎炎，陳向東，倪進(jìn)權(quán)，等.改進(jìn)的DV-HOP無線傳感器網(wǎng)絡(luò)定位算法[J].通信技術(shù)，2014，47（7）：765-769.

[6] 李冬.基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究與改進(jìn)[D].南京理工大學(xué)，2013.

[7] 林雯，張烈平，王守峰.改基于粒子群優(yōu)化算法的WSN節(jié)點(diǎn)定位方法研究[J].煤礦機(jī)械，2013，34（5）：84-86.

[8] 魯雅靜.基于DV-Hop的基于粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].合肥工業(yè)大學(xué)，2012.

[9] 徐文星.混沌粒子群優(yōu)化算法及應(yīng)用研究[D].北京化工大學(xué)，2012.