王亞子，楊建輝

周口師范學院數學與統(tǒng)計學院，河南周口 466001

改進粒子群算法的無線傳感器網絡節(jié)點定位

王亞子，楊建輝

周口師范學院數學與統(tǒng)計學院，河南周口 466001

1 引言

無線傳感器由許多微型、能量有限的節(jié)點組成，節(jié)點具有計算、通信和采集數據功能，它們通過多跳形式將采集的數據傳送到匯聚節(jié)點，然后匯聚節(jié)點將數據融合到基站，最后將數據發(fā)送給需要的用戶[1]。無線傳感器網絡在實際監(jiān)測應用中，節(jié)點要確定自身的位置信息，然后才可以對目標進行準確追蹤和定位，如果自身的位置信息不準確，那么其采集的信息不可靠，沒有任何實際應用意義[2]。同時由于無線傳感器網絡節(jié)點的規(guī)模十分龐大，有時節(jié)點達到數以萬計，如果采用人工定位或為每一個節(jié)點安裝一個全球定位系統(tǒng)，成本將相當高，而且網絡不易擴展，因此如何設計高精度的傳感器節(jié)點定位算法，提高無線傳感器網絡節(jié)點性能，具有重要理論和實用價值[3]。

由于無線傳感器網絡節(jié)點定位具有重要實用價值，引起了人們廣泛的關注，根據定位機制，節(jié)點定位分為兩大類：基于測距和非測距的定位[4]。測距定位方法首先計算傳感器節(jié)點之間的距離或角度信息，然后采用最大似然估計法、三角測量法得到傳感器節(jié)點的位置信息，它們具有較高的節(jié)點定位精度，但通信開銷大、計算復雜度高，而傳感器節(jié)點的能量有限，這樣影響整個傳感器網絡的生存時間[5-7]。無需測距定位方法可以依靠網絡連通性信息實現節(jié)點位置確定，成本相對較低，而且對硬件要求不高，定位性能受環(huán)境因素的影響小，十分適合于大規(guī)模傳感器網絡，可以滿足網絡應用要求，因此當前傳感器節(jié)點定位主要采用該類算法，主要包括：Amorphous算法、DV-Hop算法、質心算法以及APIT算法等[8-10]。然而該類算法通過求解方程組進行節(jié)點定位，因此，節(jié)點間測距誤差對節(jié)點的定位精度影響相當大，為了降低測距誤差，提高節(jié)點定位精度，許多學者將群體智能優(yōu)化算法引入到無線傳感器網絡的節(jié)點定位過程中，如遺傳算法、蟻群算法、模擬退火算法、粒子群算法（Particle Swarm Optimization algorithm，PSO）等[11-14]，但這些算法需要錨節(jié)點數量相當大，這樣導致算法計算量大，傳感器節(jié)點的定位精度有待進一步提高。

為了提高無線傳感器節(jié)點的定位精度，提出一種改進粒子群優(yōu)化算法（Modified Particle Swarm Optimization algorithm，MPSO）的無線傳感器網絡節(jié)點定位方法。首先根據錨節(jié)點選擇準則，把上一代和當代計算的節(jié)點位置均值作為下一代目標節(jié)點的參考節(jié)點，然后采用改進粒子群優(yōu)化算法對節(jié)點定位結果進行優(yōu)化，最后在Matlab 2012平臺上實現仿真實驗。結果表明，相對其他定位算法，改進粒子群算法加快了無線傳感器節(jié)點定位速度，提高了定位精度。

2 改進粒子群算法的節(jié)點定位

2.1 改進粒子群算法

設粒子群優(yōu)化（PSO）的種群規(guī)模為N，每個粒子由位置、速度向量組成，它們分別為：Xi={xi，1，xi，2，…，.xi，D}，Vi={vi，1，vi，2，…，vi，D}，個體最優(yōu)位置向量：pi={pi，1，pi，2，…，pi，D}，種群當前最優(yōu)位置為：pg={pg，1，pg，2，…，pg，D}，粒子群在搜索過程中，根據個體和全局最優(yōu)不斷更新其速度和位置，具體為：

式中，ω為慣性權重；C1、C2為學習因子；rand()為隨機函數[15]。

在粒子群搜索過程中，粒子經常會處于相對穩(wěn)定階段，該階段搜索速度較慢，全局最優(yōu)點位置變化很小，如果在PSO算法的搜索后期，粒子極有可能陷入局部極小值，此時粒子飛行速度很慢，若沒有外力的干涉，粒子難以逃逸局部極小點。針對該缺陷，本文提出了一種改進粒子群優(yōu)化（MPSO）算法。通過函數評價結果對粒子進行調整，具體為：

（1）獲取穩(wěn)定階段前的全局最優(yōu)點Xex-best。

（2）將粒子Xbest位置設置為當前搜索到的全局最優(yōu)點的位置，速度設置為0。

（3）將Xbest位置的第i維值替換為Xex-best的第i維值，替換后調用函數評價，如果評價結果優(yōu)于當前全局最優(yōu)值，調整結束，不然將第i維值改回原值，繼續(xù)第i+1維的替換和測試，直到所有維測試完畢。

2.2 迭代節(jié)點位置的計算

在無線傳感器節(jié)點定位過程中，由于外界環(huán)境因素的影響，再加上參考節(jié)點選擇的隨機性，傳感器定位帶來不同程度的誤差，計算出的多個節(jié)點位置作為參考節(jié)點，導致定位誤差不斷傳播，因此本文采用迭代平均算法計算每一代位置信息。

假設t+1代的待定位節(jié)點oi的參考節(jié)點數為L(L≥3)，并且含K個錨節(jié)點，迭代平均算法選擇參考節(jié)點的原則為：

（1）如果L≤6，那么選擇全部參考節(jié)點。

（2）如果L＞6，而且K≥6，則隨機選擇6個錨節(jié)點作為參考節(jié)點；若K＜6，那么首先選擇全部錨節(jié)點作為參考點，然后從L-K中隨機選擇剩余的6-K個節(jié)點作為參考節(jié)點。

設(x′i，t+1，y′i，t+1)表示t+1代節(jié)點oi坐標，其通過MPSO算法計算，計算與t代求出的同一節(jié)點oi的坐標(xi，t，yi，t)的平均值，那么最終坐標位置(xi，t+1，yi，t+1)為：

2.3 適應度函數設計

適應度函數用來評價粒子個體的好壞，引導粒子群算法在解空間的搜索方向，具體計算公式為：

式中，m≥3代表目標節(jié)點周圍的參考節(jié)點數；(x，y)表示目標節(jié)點坐標，(xi，yi)表示第i個參考節(jié)點坐標。

2.4 改進粒子群算法的無線傳感器節(jié)點定位步驟

步驟1在無線網絡監(jiān)測區(qū)域隨機部署若干個傳感器節(jié)點，包括錨節(jié)點和待定位節(jié)點，錨節(jié)點比例較小，它們個數和位置均已知，所有待定位節(jié)點間的通信半徑相同。

步驟2計算未知無線傳感器節(jié)點和相鄰傳感器參考節(jié)點之間的距離d?i。

步驟3采用MPSO算法對未知無線傳感器節(jié)點的位置進行計算，并得到節(jié)點位置與上代位置進行求平均，作為當代節(jié)點迭代的位置，然后將自己的位置信息通過無線網絡通知其他未知節(jié)點。

步驟4計算每一代無線傳感器節(jié)點的定位誤差，具體公式為：

式中，(xi，yi)為未知節(jié)點i的實際位置；k表示每代定位的傳感器節(jié)點數；(x?i，y?i)為未知節(jié)點的估計位置。

步驟5不斷重復步驟2～4，直到達到最大迭代代數，輸出所有未知節(jié)點的估計位置。

3 仿真實驗

3.1 仿真環(huán)境

為了測試MPSO算法的無線傳感器節(jié)點定位性能，在Intel雙核2.86 GHz CPU，2 GB的內存，Matlab 2012的平臺上進行仿真模擬實驗。40個未知傳感器節(jié)點和若干個錨節(jié)點隨機分布于100 m×100 m長方形區(qū)域，節(jié)點通信半徑為R。為了使MPSO算法的結果更具說服力，選擇標準PSO算法進行對比實驗，粒子數為20，最大迭代次數為500，慣性權重ωmax=0.9，ωmin=0.25，粒子最大速度為5 m/s。采用定位誤差率對節(jié)點定位算法性能進行評價，其計算公式為：

式中，R表示節(jié)點通信半徑，n表示待定位節(jié)點數目。

3.2 結果與分析

3.2.1 定位結果比較

MPSO算法和PSO算法未知傳感器節(jié)點估計結果如圖1所示。從圖1可以看出，MPSO算法和PSO算法可以較好地對未知傳感器節(jié)點的位置進行較正確的估計，但是相對于PSO算法，MPSO算法的節(jié)點估計位置與節(jié)點實際位置偏差更小，定位精度相對更高，這主要由于MPSO算法利用了每代估算的節(jié)點作為參考節(jié)點時，節(jié)點位置定位誤差變小，定位結果更加可靠。

圖1 兩種算法的估計結果對比

3.2.2 定位速度對比

MPSO算法和PSO算法對未知傳感器節(jié)點平均定位時間（ms）如圖2所示。由圖2可清楚地看出，MPSO算法的平均定位時間遠遠小于PSO算法的平均定位時間，提高了傳感器節(jié)點的定位速度，這樣可以較好地滿足無線傳感器節(jié)點的定位實時性、在線性要求，應用范圍更加廣泛。

3.2.3 錨節(jié)點數對定位誤差的影響

圖2 兩種算法的定位速度對比

MPSO算法和PSO算法的定位誤差與錨節(jié)點數的關系如圖3所示。從圖3可知，當錨節(jié)點數等于3時，MPSO算法的定位誤差已經到0.5 m以下，而PSO算法在錨節(jié)點數為7時，定位誤差才達到0.5 m以下，而且隨著錨節(jié)點個數的增加，無線傳感器節(jié)點定位精度趨于穩(wěn)定，可以較好地滿足節(jié)點定位的實際應用要求。

圖3 定位誤差與錨節(jié)點數關系

3.2.4 通信半徑對定位精度的影響

在錨節(jié)點比例為10%的情況下，MPSO算法和PSO算法平均定位錯誤與通信半徑之間的關系如圖4所示。從圖4可知，隨著通信半徑增加，MPSO算法和PSO算法的平均定位誤差呈下降趨勢，這主要是由于隨著通信半徑的增大，未知傳感器節(jié)點的可定位錨節(jié)點數增加，同時信號強度增加，測距更加準確，但在相同通信半徑情況下，MPSO算法的平均定位誤差更小，具有明顯的優(yōu)越性。

圖4 定位誤差受通信半徑的影響

3.2.5 噪聲方差對定位誤差的影響

噪聲方差的大小影響了節(jié)點定位精度，方差值大，說明測距中含有的噪聲大，那么優(yōu)化算法得到的節(jié)點位置較真實位置偏差就大，反之偏差小。不同噪聲方差條件下，MPSO算法和PSO算法的平均定位誤差如圖5所示。由圖5可知，兩種定位算法的定位誤差都隨噪聲方差的增大而增大。相對于PSO算法，MPSO的節(jié)點平均定位誤差增長相對較慢，這是因為噪聲方差增大，引起的測距誤差也增大，進而增大節(jié)點定位誤差，但由于MPSO采用迭代平均思想，減小了每代的定位誤差，從而減緩了增長的趨勢。

圖5 不同噪聲方差下的平均定位誤差

4 結束語

為了提高無線傳感器定位精度，提出一種改進粒子群優(yōu)化算法的無線傳感器節(jié)點定位方法，首先根據錨節(jié)點選擇準則，把上一代和當代節(jié)點位置的平均值作為下一代目標節(jié)點的參考節(jié)點，有效地減少了誤差的傳播，然后采用改進粒子群優(yōu)化算法對定位結果進行優(yōu)化，進一步提高節(jié)點定位精度，最后通過仿真實驗證明了MPSO算法的有效性和優(yōu)越性。

[1]周正.無線傳感器網絡的節(jié)點自定位技術[J].中興通訊技術，2005，11（4）：51-56.

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

[3]胡彧，姚維照.基于線性回歸的無線傳感器加權質心定位算法[J].太原理工大學學報，2011，42（5）：499-502.

[4]Attoungble K J M，Okada K.Localization with Ratio-Distance（LRD）for distributed and accurate localization in Wireless Sensor Networks[J].IEICE Transactions on Communications，2011，94（7）：1944-1951.

[5]陳維克，李文鋒，首珩，等.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報：交通科學與工程版，2006，30（2）：265-268.

[6]劉瑾.基于測距的無線傳感器網絡的定位算法的研究[J].航空計算技術，2009，39（6）：124-126.

[7]劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網絡修正加權定位算法[J].傳感技術學報，2009，23（5）：717-721.

[8]周彥，文寶，李建勛.無線傳感器網絡節(jié)點近點加權質心定位方法[J].計算機工程與應用，2012，48（1）：87-89.

[9]Kim S W，Lee J M，Lee J H.Distributed network localization for Wireless Sensor Networks[J].Applied Mathematics&Information Sciences，2012，6（3）：1109-1115.

[10]Zhong Y P，Kuang X H，Huang P W.Improved algorithm for distributed localization in wireless sensor networks[J]. Journal of Shanghai Jiaotong University：Science，2010，15：64-69.

[11]安恂，蔣挺，周正.一種用于無線傳感器網絡的質心定位算法[J].計算機工程與應用，2007，43（20）：136-138.

[12]Gopakumar A，Jacob L.Localization in wireless sensor networks using particle swarm optimization[C]//IET International Conference on Wireless，Mobile and Multimedia Networks，2008，11：227-230.

[13]Chagas S H，Martins J B，Oliveira L L.Genetic algorithms and simulated annealing optimization methods in Wireless Sensor Networks localization using artificial neural networks[C]//IEEE International Midwest Symposium on MWSCAS，2012：928-931.

[14]趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網絡定位算法[J].計算機應用與軟件，2009，26（10）：189-192.

[15]陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無線傳感器網絡節(jié)點定位改進[J].計算機應用，2010，30（7）：1736-1739.

WANG Yazi,YANG Jianhui

School of Mathematics and Statistics,Zhoukou Normal University,Zhoukou,Henan 466001,China

In order to improve the localization accuracy,a novel localization meothd in wireless sensor network based on improved particle swarm optimization algorithm is proposed.The average of the location of the node in the last generation and the location of the same node in the current generation is regarded as the current generation node location following with the criteria of choosing beacon nodes,and the improved particle swarm optimization algorithm is used to optimize the localization results.The simulation experiments are carried out.The results show that the proposed algorithm not only fastens the localization speed and has improved the localization accuracy effectively compared with the PSO algorithm,so it has wider application range.

wireless sensor networks;Modified Particle Swarm Optimization（MPSO）algorithm;distributed iterative average localization;localization error

為了提高無線傳感器節(jié)點的定位精度，針對粒子群優(yōu)化算法存在的問題，提出一種改進粒子群優(yōu)化算法的無線傳感器網絡節(jié)點定位方法。根據錨節(jié)點選擇準則，把上一代和當代節(jié)點位置的平均值作為下一代目標節(jié)點的參考節(jié)點，采用改進粒子群算法對節(jié)點的定位結果進行優(yōu)化，在Matlab 2012平臺上進行仿真對比實驗。仿真結果表明，相對于標準粒子群算法，改進粒子群算法加快了定位速度，提高了無線傳感器節(jié)點定位精度，應用范圍更廣。

無線傳感器網絡；改進粒子群優(yōu)化（MPSO）算法；分布式迭代平均定位；定位誤差

A

TP393

10.3778/j.issn.1002-8331.1402-0079

WANG Yazi,YANG Jianhui.Localization in wireless sensor network based on improved particle swarm optimization algorithm.Computer Engineering and Applications,2014,50（18）：99-102.

周口師范學院青年科學基金重點資助項目（No.zksyqn201310B）；河南省人民政府人才培養(yǎng)聯(lián)合基金項目（No.U1204618）。

王亞子（1978—），男，講師，主要研究領域：智能算法、數學建模；楊建輝（1980—），男，講師，主要研究領域：智能算法、數學建模。

2014-02-13

2014-03-28

1002-8331（2014）18-0099-04