王洪元 焦筱悛 王天成

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

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

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

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

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

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

在PSO算法中，種群中共有N個粒子，每個粒子可以看成優(yōu)化問題在D維搜索空間的一個潛在解。每一個粒子都有一個由目標(biāo)函數(shù)決定的適應(yīng)度值，該值的大小決定了粒子的優(yōu)劣程度。通過所有粒子的適應(yīng)度值可以判定出每個粒子的自身最佳位置和全局最佳位置，同時每個粒子還有一個決定其飛行方向和距離的速度。所有的粒子以一定的規(guī)則在搜索空間中搜索最優(yōu)解。每次迭代時，粒子通過局部極值和全局極值來更新自己的信息。局部極值就是粒子本身到目前為止所找到的最優(yōu)位置，而全局極值就是整個種群到目前為止所找到的最優(yōu)位置。假設(shè)一個種群有N個粒子隨機(jī)地分布在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——加速因子，根據(jù)經(jīng)驗通常都取2；

k——迭代次數(shù)；

rand()——在(0,1)范圍內(nèi)的隨機(jī)數(shù)；

ω——慣性權(quán)重。

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

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

2 自適應(yīng)策略

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

2.1 慣性權(quán)重的自適應(yīng)取值方法

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

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

(7)

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

(8)

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

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

(9)

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

(10)

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

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

(11)

通過增加一個隨機(jī)擾動來對gbest進(jìn)行變異操作，其中g(shù)best_k是gbest的第k維分量。

2.3 基于自適應(yīng)策略的節(jié)點(diǎn)定位流程

(12)

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

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

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

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

3 實驗仿真

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

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

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

表1 ML算法的定位結(jié)果

表2 筆者算法的定位結(jié)果

圖1、2分別反映了測距誤差對平均定位誤差和定位方差的影響，圖3為適應(yīng)度值與迭代次數(shù)的關(guān)系。

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

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

圖3 適應(yīng)度值與迭代次數(shù)的關(guān)系

通過實驗數(shù)據(jù)可以得到：

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

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

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

4 結(jié)束語

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