混沌粒子群和差分進(jìn)化優(yōu)化的RSSI質(zhì)心定位算法

孫 謀，曾子維，王 剛

（遼寧科技大學(xué) 計(jì)算機(jī)與軟件工程學(xué)院，遼寧 鞍山 114051）

無線傳感器網(wǎng)絡(luò)（Wireless sensor network，WSN）是由大量傳感器以自組織或者多跳的方式構(gòu)成的無線網(wǎng)絡(luò)，具有低功耗、可擴(kuò)張性強(qiáng)等優(yōu)點(diǎn)。傳感器類型眾多，在軍事作戰(zhàn)、環(huán)境監(jiān)測、室內(nèi)監(jiān)控等領(lǐng)域具有廣闊的應(yīng)用前景。然而在真實(shí)環(huán)境中拋灑大量帶有GPS定位的節(jié)點(diǎn)會(huì)導(dǎo)致成本過高，并且傳感器的使用環(huán)境大多較為苛刻，無法保證所有的傳感器都帶有GPS 定位。因此，節(jié)點(diǎn)的定位技術(shù)成為WSN領(lǐng)域的關(guān)鍵技術(shù)之一，而提高節(jié)點(diǎn)的定位精度則成為WSN 領(lǐng)域中的一大熱點(diǎn)。

無線傳感器網(wǎng)絡(luò)定位大致分為兩類，基于測距的range-based 定位與無需測距的range-free 定位［1］。range-based定位要測量節(jié)點(diǎn)間的絕對距離，再利用三邊測量、極大似然估計(jì)［2］等方法來計(jì)算未知節(jié)點(diǎn)的位置，包括 TOA［3］、TDOA［4］、AOA 等算法，算法的定位精度較高，但相應(yīng)的功耗和成本也較大。range-free定位利用節(jié)點(diǎn)的估計(jì)距離實(shí)現(xiàn)定位，主要包括質(zhì)心、DV-HOP［5］、Amorphous、MDSMAP［6］等定位算法。range-free定位算法雖然在定位精度上不如range-based定位算法，但成本較低，且定位精度已經(jīng)能夠滿足大部分應(yīng)用的需求。

目前，國內(nèi)外學(xué)者對于傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位問題已經(jīng)取得了諸多研究成果。Singh等［7］提出一種新的接收信號強(qiáng)度（Received signal strength indicator，RSSI）方法，通過引入噪聲因子進(jìn)行參數(shù)模型構(gòu)建，來減小定位誤差。Hyunmin Cho 等［8］將 PDR（Pedestrian dead reckoning，PDR）定位與無線傳感器網(wǎng)絡(luò)室內(nèi)定位方法結(jié)合，來降低非直瞄定位誤差。國內(nèi)許多學(xué)者將智能優(yōu)化算法引入節(jié)點(diǎn)定位技術(shù)中，并與range-free 定位方法結(jié)合，進(jìn)一步提高了節(jié)點(diǎn)定位精度。王改云等［9］將粒子群算法與模擬退火算法結(jié)合，并應(yīng)用到基于RSSI 的質(zhì)心算法中，具有較高的定位精度。李騰宇等［10］將基于RSSI的加權(quán)質(zhì)心算法與遺傳模擬退火方法結(jié)合，降低了傳感器網(wǎng)絡(luò)中的平均定位誤差。

傳統(tǒng)的質(zhì)心定位算法的定位原理是將多個(gè)錨節(jié)點(diǎn)連接起來組成一個(gè)多邊形，多邊形質(zhì)心的位置即為估算的未知節(jié)點(diǎn)的位置，即未知節(jié)點(diǎn)的坐標(biāo)為多個(gè)錨節(jié)點(diǎn)坐標(biāo)求和取平均值。質(zhì)心算法實(shí)現(xiàn)容易，耗費(fèi)成本較低，但定位精度也較低。所以在現(xiàn)有研究的基礎(chǔ)上，本文將混合粒子群（Particle swarm optimization，PSO）與差分進(jìn)化算法（Diffe-rence algorithm，DE）以及基于RSSI 測距的質(zhì)心算法相結(jié)合，建立以未知節(jié)點(diǎn)坐標(biāo)為參數(shù)的適應(yīng)度函數(shù)；并利用混沌搜索的隨機(jī)性、遍歷性以及動(dòng)態(tài)變化的慣性權(quán)重來提高算法的搜索能力，進(jìn)一步減小節(jié)點(diǎn)的定位誤差。

1 RSSI加權(quán)質(zhì)心定位算法

1.1 RSSI測距模型

無線傳感器網(wǎng)絡(luò)中的信號傳播模型主要包括3 種：自由空間傳輸模型（Free space propagation model）［11］、對數(shù)-距離損耗模型（Log-distance path loss model）［12］、哈他模型（Hata model）［13］。自由空間傳輸模型主要應(yīng)用于理想環(huán)境，發(fā)射信號端與接收信號端之間不存在路徑損耗。哈他模型應(yīng)用于城市環(huán)境，頻率也有所限制。所以本文采用更接近真實(shí)環(huán)境的對數(shù)-距離損耗模型，該模型將RSSI（Received signal strength indication）值轉(zhuǎn)化為距離。RSSI 值越大，代表兩個(gè)節(jié)點(diǎn)間的距離越近。對數(shù)距離損耗模型表達(dá)式

式中：PL(dab)代表距離ab之間的路徑損耗；d0是錨節(jié)點(diǎn)間的參考距離，通常取1 m；λ是路徑損耗因子，根據(jù)環(huán)境的不同，取值不同；σ是正態(tài)分布因子。

1.2 加權(quán)質(zhì)心定位原理

傳統(tǒng)的質(zhì)心算法是由距離未知節(jié)點(diǎn)最近的幾個(gè)錨節(jié)點(diǎn)（xi，yi）組成一個(gè)多邊形，多邊形的質(zhì)心即為估算所得的未知節(jié)點(diǎn)的位置

質(zhì)心算法實(shí)現(xiàn)簡單，但未知節(jié)點(diǎn)的定位容易受到周圍錨節(jié)點(diǎn)數(shù)量的影響。周圍的錨節(jié)點(diǎn)越多，定位精度越高。反之，定位精度則較低。

為了防止單個(gè)錨節(jié)點(diǎn)對未知節(jié)點(diǎn)的位置測量影響較大，加權(quán)質(zhì)心算法［14］以錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離的倒數(shù)為權(quán)值，距離未知節(jié)點(diǎn)越遠(yuǎn)的錨節(jié)點(diǎn)對于未知節(jié)點(diǎn)的定位影響越小。pi是錨節(jié)點(diǎn)的權(quán)值，未知節(jié)點(diǎn)的坐標(biāo)為

2 PSO-DE-RSSI優(yōu)化算法

2.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是節(jié)點(diǎn)定位技術(shù)中的誤差評價(jià)標(biāo)準(zhǔn)。為了減小定位誤差，需要多次進(jìn)行循環(huán)迭代求出適應(yīng)度函數(shù)的最小值。本文適應(yīng)度函數(shù)的構(gòu)建選取距離未知節(jié)點(diǎn)最近的三個(gè)錨節(jié)點(diǎn)（xi，yi）（i=1,2,3），未知節(jié)點(diǎn)的估計(jì)位置為（x，y），錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離為

根據(jù)RSSI測距得到的三個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的真實(shí)距離為da、db、dc，則適應(yīng)度函數(shù)的定義為

f值越小，節(jié)點(diǎn)定位精度越高。

2.2 優(yōu)化算法步驟

粒子群算法參數(shù)設(shè)置簡單，搜索速度快，但在種群規(guī)模大，搜索空間維度高時(shí)，種群中個(gè)體的差異會(huì)隨著時(shí)間的推移而減小，從而陷入局部最優(yōu)解無法跳出。差分進(jìn)化算法會(huì)隨機(jī)選擇種群中的個(gè)體來構(gòu)造差分向量，將產(chǎn)生的變異個(gè)體與原始種群中的個(gè)體進(jìn)行交叉操作構(gòu)造后代，并選擇種群中適應(yīng)度較好的個(gè)體來更新種群。粒子群算法進(jìn)行快速尋優(yōu)后，可以通過差分進(jìn)化算法繼續(xù)進(jìn)行優(yōu)化，使得陷入局部最優(yōu)的個(gè)體快速跳出當(dāng)前區(qū)域，進(jìn)而探索全局最優(yōu)解。

本文采用的PSO-DE-RSSI 算法，先通過RSSI測距找到與未知節(jié)點(diǎn)最近的三個(gè)錨節(jié)點(diǎn)，利用三個(gè)錨節(jié)點(diǎn)構(gòu)造三角形，并設(shè)置群粒子在三角形的質(zhì)心位置；再將粒子群與差分進(jìn)化算法相結(jié)合并進(jìn)行混沌搜索，去計(jì)算未知節(jié)點(diǎn)的位置。PSO-DERSSI算法的步驟：

步驟1：初始化種群，設(shè)置種群規(guī)模與最大迭代次數(shù)，初始化粒子的位置x(t)與速度v(t)，計(jì)算種群中每個(gè)粒子的適應(yīng)度值。

步驟2：更新粒子的速度與位置

步驟3：計(jì)算種群的平均適應(yīng)度，將種群中適應(yīng)度值較高的個(gè)體執(zhí)行差分進(jìn)化算法中的變異、交叉、選擇操作。

變異：在每次迭代中隨機(jī)生成三個(gè)染色體xa(t)、xb(t)、xc(t)，將其中兩個(gè)染色體的差值乘以加權(quán)因子F，再加到第三個(gè)染色體上，產(chǎn)生變異個(gè)體Vi(t)

交叉：將第t代的種群個(gè)體xij(t)與變異個(gè)體按照式（8）產(chǎn)生交叉?zhèn)€體，CR是交叉概率

選擇：選擇父代個(gè)體與交叉后的種群中適應(yīng)度較小的個(gè)體

步驟4：將原始種群中低于平均適應(yīng)度的個(gè)體，與經(jīng)過差分進(jìn)化算法更新后的種群進(jìn)行合并。

步驟5：在每代的最優(yōu)解附近進(jìn)行混沌搜索，將混沌搜索后得到的個(gè)體與每代最優(yōu)解進(jìn)行適應(yīng)度比較，取適應(yīng)度最優(yōu)的個(gè)體。

步驟6：判斷算法是否滿足最大迭代次數(shù)，如果滿足則比較每代最優(yōu)解的適應(yīng)度值，取適應(yīng)度值最低的個(gè)體作為全局最優(yōu)解輸出，否則返回步驟2繼續(xù)進(jìn)行迭代。

算法流程如圖1所示。

3 算法的改進(jìn)

3.1 慣性權(quán)重的修改

慣性權(quán)重是粒子群算法中評價(jià)粒子速度的重要參數(shù)，慣性權(quán)重越大，粒子的速度越快，粒子的全局搜索能力就會(huì)越強(qiáng)。慣性權(quán)重越小，粒子的速度越小，粒子就會(huì)具有較強(qiáng)的局部搜索能力。

慣性權(quán)重不變的粒子群算法雖然具有較快的收斂速度，但后期容易陷入局部最優(yōu)。Shi等提出了慣性權(quán)重線性遞減的策略［15］

式中：ωmax和ωmin分別代表慣性權(quán)重的最大值和最小值，一般分別取0.9和0.4；k是當(dāng)前迭代次數(shù)；N是最大迭代次數(shù)。

本文在慣性權(quán)重的遞減公式中加入正態(tài)函數(shù)，對式（10）進(jìn)行改進(jìn)，讓慣性權(quán)重按照正態(tài)函數(shù)遞減的方式進(jìn)行變化，使前期的慣性權(quán)重變化較快，算法的收斂速度降低，容易獲得局部最優(yōu)解；使后期慣性權(quán)重變化較慢，提高算法的收斂速度。

式中：a，b為常數(shù)，可根據(jù)算法的迭代次數(shù)選擇不同的值。

加入ωmin可以保證慣性權(quán)重取值為正數(shù)，并在0.4～0.9 之間變化。設(shè)置均值為0，將標(biāo)準(zhǔn)正態(tài)函數(shù)的右半部分作為慣性權(quán)重的變化趨勢，如圖2所示。曲線前期是凸函數(shù)，后期是凹函數(shù)，從而保證算法前期的局部收斂能力與后期的全局收斂能力。

3.2 混沌機(jī)制

混沌運(yùn)動(dòng)是一種非隨機(jī)運(yùn)動(dòng)，存在于非線性動(dòng)力系統(tǒng)中，具有隨機(jī)性和遍歷性?；煦邕\(yùn)動(dòng)的遍歷性可以幫助算法避免落入局部陷阱。目前，混沌技術(shù)已引入到優(yōu)化算法中，混沌系統(tǒng)動(dòng)力學(xué)模型種類繁多，選用較為經(jīng)典的Logistic方程［16］

本文在粒子群算法中用混沌變量代替隨機(jī)變量，并在算法每代最優(yōu)解附近繼續(xù)進(jìn)行混沌搜索，利用混沌變量的隨機(jī)性與遍歷性來提高算法的搜索能力。原始的粒子群算法速度更新為

式中：ω是慣性權(quán)重；c1和c2是學(xué)習(xí)因子；r1和r2是（0，1）之間的隨機(jī)數(shù)；pt是個(gè)體當(dāng)前搜索到的最優(yōu)解；pg是群體當(dāng)前搜索到的最優(yōu)解。

加入混沌搜索［17］后，粒子速度更新為

式中：cr根據(jù)式（12）計(jì)算。

為了提高算法的深度搜索能力，本文將粒子群與差分進(jìn)化算法結(jié)合后，再在每代的最優(yōu)解附近進(jìn)行精細(xì)搜索

式中：n是在每代最優(yōu)解附近進(jìn)行混沌搜索的次數(shù)；Cn是混沌變量；xbest是每次迭代的最優(yōu)解；α是方向因子，讓xn在正反兩個(gè)方向搜索，提高算法的隨機(jī)性；rand是在（0，1）中均勻分布的隨機(jī)數(shù)。

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的PSO-DE-RSSI算法的性能，將本文提出的算法與其它算法通過MATLAB仿真實(shí)驗(yàn)比較算法的優(yōu)劣。仿真實(shí)驗(yàn)中，在1 000 m×1 000 m的正方形區(qū)域內(nèi)隨機(jī)拋灑1 000個(gè)傳感器節(jié)點(diǎn)，包括未知節(jié)點(diǎn)與錨節(jié)點(diǎn)。節(jié)點(diǎn)的分布如圖3所示。

錨節(jié)點(diǎn)周期性地向周圍環(huán)境發(fā)送自身信息，其它節(jié)點(diǎn)根據(jù)接受的信號強(qiáng)度判斷自身與錨節(jié)點(diǎn)之間的鄰居關(guān)系。節(jié)點(diǎn)的鄰居關(guān)系如圖4所示。

無線傳感器網(wǎng)絡(luò)通常采用平均定位誤差作為評價(jià)標(biāo)準(zhǔn)。節(jié)點(diǎn)的平均定位誤差是傳感器網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)的定位誤差的平均值，定義為

式中：N是未知節(jié)點(diǎn)的個(gè)數(shù)；R是節(jié)點(diǎn)的通信半徑；（x，y）是節(jié)點(diǎn)的真實(shí)位置；（xi，yi）是節(jié)點(diǎn)的估計(jì)位置。

改變錨節(jié)點(diǎn)的個(gè)數(shù)與錨節(jié)點(diǎn)的通信半徑，對比本文PSO-DE-RSSI算法與普通的粒子群算法和基于RSSI的加權(quán)質(zhì)心算法的節(jié)點(diǎn)定位誤差。節(jié)點(diǎn)的參數(shù)設(shè)置：節(jié)點(diǎn)個(gè)數(shù)300、種群粒子個(gè)數(shù)20、慣性權(quán)重初始值0.9、學(xué)習(xí)因子2、最大迭代次數(shù)500、變異概率0.5、交叉概率0.6。

圖5是錨節(jié)點(diǎn)半徑為210 m，錨節(jié)點(diǎn)個(gè)數(shù)為90個(gè)時(shí)的節(jié)點(diǎn)定位誤差圖。圖中的實(shí)線代表估計(jì)的未知節(jié)點(diǎn)的位置與節(jié)點(diǎn)真正所在位置的距離。實(shí)線越短，定位的誤差越小。

圖6 是錨節(jié)點(diǎn)的個(gè)數(shù)為90 時(shí)，通信半徑與定位誤差的關(guān)系。隨著通信半徑的增大，三個(gè)算法的平均定位誤差都是呈下降的趨勢。因?yàn)殄^節(jié)點(diǎn)的通信半徑越大，未知節(jié)點(diǎn)周圍的錨節(jié)點(diǎn)也就越多，更有利于節(jié)點(diǎn)定位，也說明錨節(jié)點(diǎn)的通信半徑影響著節(jié)點(diǎn)的定位誤差。通信半徑相同時(shí)，與粒子群算法與基于RSSI的加權(quán)質(zhì)心算法相比，PSODE-RSSI 算法的平均定位誤差最低。這是因?yàn)樵撍惴▽⒉罘诌M(jìn)化與粒子群算法結(jié)合，加強(qiáng)了算法的全局尋優(yōu)能力，避免算法陷入局部最優(yōu)解的陷阱，該算法可以提高節(jié)點(diǎn)的定位精度。

圖7 為錨節(jié)點(diǎn)的個(gè)數(shù)與平均定位誤差的關(guān)系。隨著錨節(jié)點(diǎn)個(gè)數(shù)的增多，三個(gè)算法的平均定位誤差都在減小。說明錨節(jié)點(diǎn)的個(gè)數(shù)越多，定位精度越高。而本文提出的算法的平均定位誤差比基于RSSI的加權(quán)質(zhì)心定位算法下降了10%～15%，比普通的粒子群算法下降了6%左右。

5 結(jié) 論

本文將智能優(yōu)化算法與基于RSSI測距的質(zhì)心算法相結(jié)合，來減小節(jié)點(diǎn)的定位誤差。粒子群算法雖然搜索速度快、效率高，但容易陷入局部最優(yōu)，將差分進(jìn)化算法與粒子群算法相結(jié)合，通過不斷迭代計(jì)算，保留優(yōu)良個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索向全局最優(yōu)解逼近。并在此基礎(chǔ)上加入動(dòng)態(tài)慣性權(quán)重與混沌搜索，進(jìn)一步保證算法在尋優(yōu)性能較好的基礎(chǔ)上擁有更小的定位誤差。實(shí)驗(yàn)結(jié)果表明，與基于RSSI 的加權(quán)質(zhì)心算法和粒子群算法相比，本文提出的PSO-DE-RSSI 算法可以在一定程度上提高節(jié)點(diǎn)的定位精度。