王洪元 焦筱悛 王天成

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

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

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

傳統(tǒng)的節(jié)點(diǎn)定位算法常采用最小二乘法求解非線(xiàn)性方程組，很容易受到測(cè)距誤差的影響。為了進(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)化性能不佳的問(wèn)題。

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

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

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

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

(1)

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

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

(2)

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

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

(3)

整個(gè)種群的全局極值可表示為：

gbest=(pg1,pg2,…,pgD)

(4)

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

(5)

(6)

式中c1、c2——加速因子，根據(jù)經(jīng)驗(yàn)通常都取2；

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

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

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

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

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

2 自適應(yīng)策略

筆者提出的基于自適應(yīng)策略的改進(jìn)算法主要包括兩個(gè)方面:一是慣性權(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ù)，其反映了粒子先前的飛行速度對(duì)現(xiàn)在值的影響。當(dāng)其取值較大時(shí)，全局搜索能力強(qiáng)，收斂速度快，但缺點(diǎn)是得到的解精度不夠；當(dāng)取值較小時(shí)，局部搜索能力強(qiáng)、得到的解的精度高，但存在收斂速度較慢且可能陷入局部極值的缺點(diǎn)。合適的ω值能夠平衡算法的全局搜索能力和局部搜索能力，從而得到最佳的優(yōu)化解。

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

(7)

其中當(dāng)ω2>ω1時(shí)，一般取ω1=0.3、ω2=0.8，T為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)。為了防止ω(i)在迭代后期取值過(guò)小，筆者對(duì)ω(i)的值設(shè)置了下限0.2，當(dāng)ω(i)低于下限值時(shí)ω(i)=0.2。f(i)為第i個(gè)粒子的適應(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)度值看作一個(gè)樣本，這個(gè)樣本的方差就可以用來(lái)定量描述整個(gè)種群的聚集程度。種群越密集，表明整個(gè)種群的群居搜索能力變差，此時(shí)就需要對(duì)全局最優(yōu)位置進(jìn)行變異操作，保證整個(gè)種群能跳出當(dāng)前的搜索區(qū)域。粒子群的種群適應(yīng)度值方差δ2的計(jì)算公式為：

(9)

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

(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)

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

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

(12)

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

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

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

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

3 實(shí)驗(yàn)仿真

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

在本實(shí)驗(yàn)中，假設(shè)無(wú)線(xiàn)傳感器節(jié)點(diǎn)部署在100m×100m的二維平面區(qū)域中，在此區(qū)域內(nèi)隨機(jī)分布5個(gè)傳感器節(jié)點(diǎn)，其中4個(gè)為錨節(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)的實(shí)際坐標(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。為了減少實(shí)驗(yàn)中隨機(jī)誤差的干擾，進(jìn)行100次定位實(shí)驗(yàn)得到最終的實(shí)驗(yàn)數(shù)據(jù)。在無(wú)線(xiàn)傳感器節(jié)點(diǎn)定位過(guò)程中，測(cè)距誤差直接決定著定位的進(jìn)度和穩(wěn)定度。因此，本實(shí)驗(yàn)以測(cè)距誤差作為實(shí)驗(yàn)的前提條件，在不同測(cè)距誤差的條件下比較ML算法和筆者算法的性能優(yōu)劣。在引入相同測(cè)距誤差的條件下，分別對(duì)兩種算法做100次的定位運(yùn)算，并在不同測(cè)距誤差的情況下，重復(fù)進(jìn)行上述定位運(yùn)算。兩種算法定位結(jié)果分別見(jiàn)表1、2。

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

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

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

圖1 測(cè)距誤差對(duì)平均定位誤差的影響

圖2 測(cè)距誤差對(duì)定位方差的影響

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

通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以得到：

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

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

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

4 結(jié)束語(yǔ)

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