孫 謀，曾子維，王 剛

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

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

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

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

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

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)境，頻率也有所限制。所以本文采用更接近真實環(huán)境的對數(shù)-距離損耗模型，該模型將RSSI（Received signal strength indication）值轉(zhuǎn)化為距離。RSSI 值越大，代表兩個節(jié)點間的距離越近。對數(shù)距離損耗模型表達式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法流程如圖1所示。

3 算法的改進

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

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

慣性權(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）進行改進，讓慣性權(quán)重按照正態(tài)函數(shù)遞減的方式進行變化，使前期的慣性權(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 混沌機制

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

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

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

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

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

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

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

4 仿真實驗與結(jié)果分析

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

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

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

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

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

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

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

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

5 結(jié) 論

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