楊鵑

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

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

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

1 DV-Hop定位算法[4]

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

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

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

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

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

4） 求解距離方程組。

2 方程組的求解

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

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

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

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

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

3 粒子群算法

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

3.1 PSO算法[7]-[8]

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

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

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

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

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

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

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

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

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

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

2） 計算種群中各個粒子的適應度值；

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

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

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

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

7） 輸出全局極值對應的粒子位置。

4 混沌粒子群

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

混沌點列的生成過程：

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

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

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

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

5 算法仿真與分析

5.1 仿真環(huán)境

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

5.2 仿真結(jié)果分析

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

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

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

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

6 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

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

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