基于自適應粒子群優(yōu)化算法的節(jié)點定位研究

王洪元 焦筱悛 王天成

(常州大學，江蘇 常州 213164)

無線傳感器網絡是由大量小型低功耗、低成本并具有感知、計算和通信功能的傳感器組成的[1]，通過無線通信方式形成一個自組織網絡系統(tǒng)，現已被廣泛應用于環(huán)境監(jiān)測、軍事應用及科學研究等領域。無線傳感器網絡最基本的功能之一是適時地獲知事件發(fā)生的位置信息或獲取信息的節(jié)點位置。比如，礦井人員定位系統(tǒng)及公共交通管理系統(tǒng)等應用中需要獲取位置信息。所以說節(jié)點定位技術是無線傳感器網絡在應用中的關鍵技術之一[2,3]。

無線傳感器定位可分為基于測距的定位算法和無需測距的定位算法，其主要區(qū)別在于是否需要距離信息?；跍y距的定位算法中節(jié)點需使用測距技術獲得距離信息，優(yōu)點是定位精度高但需要額外的硬件設備，常用的測距技術有接收信號強度RSSI、信號到達時間TOA、信號到達時間差TDOA及信號到達角度AOA等；無需測距的定位算法僅依靠相鄰節(jié)點間的連通關系進行定位，無需基礎網絡設施的支持，但定位精度較低[4]。

傳統(tǒng)的節(jié)點定位算法常采用最小二乘法求解非線性方程組，很容易受到測距誤差的影響。為了進一步提高定位精度，筆者將自適應策略引入到粒子群優(yōu)化節(jié)點定位算法中，有效地克服了粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法容易產生種群的趨同效應，出現早熟收斂、易陷入局部極值、在搜索后期停滯不前而導致種群的優(yōu)化性能不佳的問題。

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

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是由Kennedy和Eberhart在1995年提出的。PSO算法是一種模擬鳥群遷徙和覓食行為的群體智能全局隨機優(yōu)化計算方法，通過種群中個體間的競爭與協(xié)調，搜索復雜空間的最優(yōu)解。PSO算法將種群中的每個個體看成一個質量和體積都為零的粒子，粒子根據自身歷史最優(yōu)位置和種群歷史最優(yōu)位置不斷更新自身的速度和位置，從而實現進化[5]。

在PSO算法中，種群中共有N個粒子，每個粒子可以看成優(yōu)化問題在D維搜索空間的一個潛在解。每一個粒子都有一個由目標函數決定的適應度值，該值的大小決定了粒子的優(yōu)劣程度。通過所有粒子的適應度值可以判定出每個粒子的自身最佳位置和全局最佳位置，同時每個粒子還有一個決定其飛行方向和距離的速度。所有的粒子以一定的規(guī)則在搜索空間中搜索最優(yōu)解。每次迭代時，粒子通過局部極值和全局極值來更新自己的信息。局部極值就是粒子本身到目前為止所找到的最優(yōu)位置，而全局極值就是整個種群到目前為止所找到的最優(yōu)位置。假設一個種群有N個粒子隨機地分布在D維搜索空間中，其中第i個粒子在搜索空間中的位置向量可表示為：

Xi=(xi1,xi2,…,xiD),i=1,2,…,N

(1)

第i個粒子的飛行速度向量可表示為：

Vi=(vi1,vi2,…,viD),i=1,2,…,N

(2)

第i個粒子到目前為止搜索的局部極值表示為：

Pbest=(pi1,pi2,…，piD),i=1,2,…,N

(3)

整個種群的全局極值可表示為：

gbest=(pg1,pg2,…,pgD)

(4)

每個粒子按如下公式更新自己的速度向量和位置向量：

(5)

(6)

式中c1、c2——加速因子，根據經驗通常都取2；

k——迭代次數；

rand()——在(0,1)范圍內的隨機數；

ω——慣性權重。

式(5)右邊可分為3個部分，第一部分稱為“慣性部分”，反映粒子維持先前速度的程度；第二部稱為“認知部分”，反映粒子本身歷史最佳位置對現在的影響；第三部分稱為“社會部分”，反映種群對粒子的影響，粒子有向全局最佳位置靠攏的趨勢。為了防止粒子飛出搜索空間，通常對粒子的速度進行一定的限制。

在PSO算法中存在粒子向種群全局歷史最佳位置和自身局部歷史最佳位置聚集時容易產生種群趨同效應的現象，并導致早熟收斂、易陷入局部極值、在搜索后期停滯不前而導致種群的優(yōu)化性能不佳的問題，同時，PSO算法的優(yōu)化性能還依賴于參數的取值情況。為克服這些不足，文獻[6]提出了用指數變化的慣性權重取值方法來優(yōu)化復雜的非線性方程組，筆者在此基礎上進一步簡化算法，提出了一種基于自適應策略的粒子群優(yōu)化節(jié)點定位算法，該算法從慣性權重和全局最優(yōu)位置兩個方面對原有的PSO算法進行改進，實現了在不增加額外硬件的條件下對無線傳感器網絡節(jié)點定位在定位精度和計算耗時上的進一步優(yōu)化。

2 自適應策略

筆者提出的基于自適應策略的改進算法主要包括兩個方面:一是慣性權重的自適應取值方法；二是從適應度值進行改進的全局最優(yōu)位置的自適應變異操作。

2.1 慣性權重的自適應取值方法

慣性權重ω是PSO算法中最重要的改進參數，其反映了粒子先前的飛行速度對現在值的影響。當其取值較大時，全局搜索能力強，收斂速度快，但缺點是得到的解精度不夠；當取值較小時，局部搜索能力強、得到的解的精度高，但存在收斂速度較慢且可能陷入局部極值的缺點。合適的ω值能夠平衡算法的全局搜索能力和局部搜索能力，從而得到最佳的優(yōu)化解。

筆者提出的自適應的慣性權重取值方法，其設計思想主要有兩個過程：在定位算法迭代前期ω取較大值，實現快速收斂到最優(yōu)解附近，后期則取較小值求高精度解；同時該算法在適應度值越大時全局搜索能力越高，從而加快向全局最優(yōu)位置的聚集速度，粒子適應度值較小時局部搜索能力越高，從而得到高精度的解。筆者提出的慣性權重的自適應取值公式如下：

(7)

其中當ω2>ω1時，一般取ω1=0.3、ω2=0.8，T為當前迭代次數，Tmax為最大迭代次數。為了防止ω(i)在迭代后期取值過小，筆者對ω(i)的值設置了下限0.2，當ω(i)低于下限值時ω(i)=0.2。f(i)為第i個粒子的適應度值，fmax、fmin為所有種群中粒子適應度值的最大值和最小值，相應的粒子速度更新公式變?yōu)橄率剑?/p>

(8)

2.2 全局最優(yōu)位置的自適應變異操作

粒子的適應度值可以反映粒子當前位置的優(yōu)劣程度，把種群所有粒子的當前適應度值看作一個樣本，這個樣本的方差就可以用來定量描述整個種群的聚集程度。種群越密集，表明整個種群的群居搜索能力變差，此時就需要對全局最優(yōu)位置進行變異操作，保證整個種群能跳出當前的搜索區(qū)域。粒子群的種群適應度值方差δ2的計算公式為：

(9)

其中favg為種群中所有粒子適應度值的平均值；F為歸一化因子，通常F=max(1,|f(i)-favg|)。其全局最優(yōu)位置發(fā)生變異的概率計算公式如下：

(10)

其中pmax、pmin分別為gbest進行變異操作概率的最大值和最小值，通常取pmax=0.4，pmin=0.3。全局最優(yōu)位置變異操作的公式為：

gbest_k=gbest_k(1+0.4η),η∈N(0,1)

(11)

通過增加一個隨機擾動來對gbest進行變異操作，其中gbest_k是gbest的第k維分量。

2.3 基于自適應策略的節(jié)點定位流程

(12)

其值越小，對該點的定位就越精確。節(jié)點定位的具體流程如下：

a. 在搜索空間(目標區(qū)域)隨機部署一定數目的錨節(jié)點和未知節(jié)點，節(jié)點啟動后錨節(jié)點以周期T向相鄰節(jié)點發(fā)送自己的信息(主要包括節(jié)點ID、位置信息)；

b. 未知節(jié)點根據鄰居連通錨節(jié)點的相關信息和RSSI模型公式計算出自身到錨節(jié)點間的距離；

c. 存在鄰居連通錨節(jié)點的未知節(jié)點在自身處運行筆者改進后的PSO算法，計算自身定位結果。

3 實驗仿真

在MATLAB R2008a中對基于自適應策略的粒子群優(yōu)化節(jié)點定位算法的性能進行驗證，并與常用的極大似然估計(Maximum Likelihood，ML)進行對比分析。

在本實驗中，假設無線傳感器節(jié)點部署在100m×100m的二維平面區(qū)域中，在此區(qū)域內隨機分布5個傳感器節(jié)點，其中4個為錨節(jié)點，其坐標分別為A(22.23,48.64)、B(62.48,2.46)、C(44.60,80.42)、D(85.22,70.48)，未知節(jié)點的實際坐標為E(82.24,46.32)。

基于自適應策略的粒子群優(yōu)化定位算法中的參數設置為：ω1=0.3、ω2=0.8，pmax=0.4，pmin=0.3，ω(i)min=0.2，c1=c2=2。種群粒子總數大小N=30，總的迭代次數T=100，粒子每維最大位置為100m，最大速度為10m/s。為了減少實驗中隨機誤差的干擾，進行100次定位實驗得到最終的實驗數據。在無線傳感器節(jié)點定位過程中，測距誤差直接決定著定位的進度和穩(wěn)定度。因此，本實驗以測距誤差作為實驗的前提條件，在不同測距誤差的條件下比較ML算法和筆者算法的性能優(yōu)劣。在引入相同測距誤差的條件下，分別對兩種算法做100次的定位運算，并在不同測距誤差的情況下，重復進行上述定位運算。兩種算法定位結果分別見表1、2。

表1 ML算法的定位結果

表2 筆者算法的定位結果

圖1、2分別反映了測距誤差對平均定位誤差和定位方差的影響，圖3為適應度值與迭代次數的關系。

圖1 測距誤差對平均定位誤差的影響

圖2 測距誤差對定位方差的影響

圖3 適應度值與迭代次數的關系

通過實驗數據可以得到：

a. 從圖1可看出，在給定的5種測距誤差條件下，筆者算法的平均定位誤差要比ML算法小，說明該算法的定位精度要高于ML算法的。從圖2可以看出，筆者算法的定位方差要比ML算法小，說明該算法的穩(wěn)定性要高于ML算法的。

b. 從圖1、2可以進一步發(fā)現，當系統(tǒng)測距誤差較小時，兩種定位算法的性能相差無幾，但隨著距離誤差變大，筆者算法的優(yōu)良定位性能就凸顯出來，說明該算法在一定程度上可以減輕測距誤差對定位精度的影響。

c. 圖3是筆者算法在測距誤差為5%時的一次定位過程，從圖中可以看出算法在迭代不到10次時就可以收斂到一個精度較高的優(yōu)化解，收斂速度較快，能耗較低，適合應用在對能耗有較高要求的無線定位系統(tǒng)中。

4 結束語

筆者針對基本粒子群優(yōu)化算法在無線傳感器網絡定位中的不足之處，在文獻[8]中用指數變化的慣性權重取值方法來優(yōu)化復雜的非線性方程組的基礎上進一步簡化算法，提出了一種基于自適應策略的粒子群優(yōu)化節(jié)點定位算法，該策略從慣性權重和全局最優(yōu)位置兩個方面對原有的PSO算法進行改進，實現了在不增加額外硬件的條件下對無線傳感器網絡節(jié)點定位在定位精度和計算耗時上的進一步優(yōu)化。通過與極大似然估計定位算法的定位結果進行對比，證明了筆者算法具有收斂快、能耗小、精度高和穩(wěn)定性好的優(yōu)點，適合應用在無線傳感器網絡的定位中。