一種改進(jìn)的粒子群算法在WSN中的定位研究

傅 彬

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

一種改進(jìn)的粒子群算法在WSN中的定位研究

傅 彬

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

針對無線傳感網(wǎng)中的節(jié)點(diǎn)定位問題,采用RSSI測距技術(shù)測量未知節(jié)點(diǎn)之間的距離,并采用粒子群算法進(jìn)行優(yōu)化,針對粒子群算法的不足,首先通過引入動態(tài)擾動因子和懲罰函數(shù)提高算法的性能,其次采用距離誤差修正和修正定位誤差模型來優(yōu)化節(jié)點(diǎn)定位的效果。通過仿真實(shí)驗(yàn)將所提算法與基本粒子群算法進(jìn)行比較,結(jié)果表明所提算法在算法的收斂性能和定位精度上取得了比較好的效果,提高了節(jié)點(diǎn)的定位效果。

無線傳感網(wǎng)；動態(tài)擾動因子；懲罰函數(shù)

0 引言

無線傳感網(wǎng)中的節(jié)點(diǎn)定位是衡量無線傳感網(wǎng)絡(luò)數(shù)據(jù)傳輸效率高低的一個重要標(biāo)準(zhǔn)[1]。節(jié)點(diǎn)定位不但受到自然界中客觀條件的影響,還容易受到來自自身節(jié)點(diǎn)傳輸信號強(qiáng)弱、傳輸距離以及節(jié)點(diǎn)能量等條件的限制,因此如何進(jìn)行節(jié)點(diǎn)定位的優(yōu)化一直都是學(xué)者們不斷研究的方向。國內(nèi)外學(xué)者從不同的角度對節(jié)點(diǎn)定位提出了自己的研究方向。文獻(xiàn)[2]提出一種基于小波支持向量機(jī)(WSVM)的定位算法,取得了比較好的定位效果;文獻(xiàn)[3]從全網(wǎng)平均每跳距離角度出發(fā),分析每個信標(biāo)節(jié)點(diǎn)的平均每跳距離誤差,有效地提高了節(jié)點(diǎn)定位精度;文獻(xiàn)[4]提出一種基于接收信號強(qiáng)度指示測距的蒙特卡羅盒定位算法;文獻(xiàn)[5]提出采用人工蜂群算法來修正最小二乘定位誤差的傳感器節(jié)點(diǎn)定位算法,該算法能夠有效地提高無線傳感器節(jié)點(diǎn)的定位精度;文獻(xiàn)[6]提出了一種改進(jìn)粒子群算法與DV-Hop的融合算法。

本文在以上研究的基礎(chǔ)上,采用粒子群算法對使用RSSI測距技術(shù)的節(jié)點(diǎn)之間的距離進(jìn)行優(yōu)化,通過對粒子群算法采用動態(tài)擾動因子、懲罰函數(shù)、誤差修正和修正定位模型等方法提高算法的性能,提高算法定位的效果。

1 接收信號強(qiáng)度(RSSI)

在真實(shí)的無線傳感網(wǎng)中，硬件設(shè)備是非常重要的必備工具，其優(yōu)點(diǎn)是設(shè)計(jì)簡單，缺點(diǎn)是處理能力有限,因此需要布置大量的傳感器。而RSSI測距技術(shù)不需要復(fù)雜的硬件設(shè)備,它僅僅依靠節(jié)點(diǎn)發(fā)射信號的功率與接收信號功率之間的差值來初步估算兩點(diǎn)之間的損耗,并轉(zhuǎn)換為兩個節(jié)點(diǎn)之間的距離,計(jì)算公式模型如下:

PR(d)=PtGtGrλ2/16π2d2L

(1)

式中,PR(d)表示接收節(jié)點(diǎn)與發(fā)射節(jié)點(diǎn)相距d的功率,Pt為發(fā)射節(jié)點(diǎn)的功率,Gt、Gr分別為發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)的增益,L為損耗定量,d為距離,λ為波長。

理論研究中，無線傳感網(wǎng)中的節(jié)點(diǎn)定位模型都是在假設(shè)一定理論條件成立的情況下建立的,但在實(shí)際情況中,無線傳感網(wǎng)絡(luò)可能受到來自自然界中的溫度、濕度、障礙物等影響,網(wǎng)絡(luò)中傳輸?shù)男盘柨隙〞艿讲煌潭鹊挠绊?因此采用RSSI測量獲得的節(jié)點(diǎn)的估計(jì)距離和真實(shí)距離具有一定的差距。因此如何降低誤差成為了研究的主要方向。

2 改進(jìn)的粒子群算法

2.1 粒子群算法簡述

在一個D維的搜索空間中,種群由M個粒子組成,其中第i個粒子的位置為Xi=[xi1,xi2,…xiD],飛行速度為Vi=[vi1,vi2,…，viD],設(shè)定Pi是第i個粒子當(dāng)前搜索的個體最佳位置,Pi=[pi1,pi2,…，pID]；Pg為當(dāng)前搜索到的全局最優(yōu)位置,Pg=[pg1,pg2,…，pgD],因此粒子的位置和速度的調(diào)整方向如下:

(2)

(3)

式中的k為迭代次數(shù)；r1和r2是0～1之間的隨機(jī)數(shù),用來保持種群具有的多樣性；ω為慣性權(quán)重值；c1和c2是學(xué)習(xí)因子,用來掌握粒子個體的最優(yōu)位置以及整個粒子群中的全局最優(yōu)位置,合理地調(diào)節(jié)算法,提高算法的收斂速度。在粒子群算法中，對每一個粒子的個體來說,個體最優(yōu)解Pi和粒子全局最優(yōu)解Pg的更新如下:

(4)

f(Pg)=min[f(Pi)]

(5)

2.2 改進(jìn)的粒子群算法

文獻(xiàn)[7]證明粒子群算法在進(jìn)化過程中與粒子的速度沒有直接的關(guān)系,因此將粒子群優(yōu)化算法的位置更新簡化為如下形式:

(6)

2.2.1 引入動態(tài)擾動因子

公式(6)雖然進(jìn)行了簡化,但仍然可以發(fā)現(xiàn)該算法具有收斂速度快、容易陷入局部最優(yōu)解的可能。為了解決這個問題,首先引入擾動因子概念,當(dāng)個體的最優(yōu)解和全局最優(yōu)解停滯的時候,使用擾動因子對其進(jìn)行擾動,使得算法遠(yuǎn)離當(dāng)前搜索區(qū)域,向其他區(qū)域擴(kuò)散。因此擾動因子設(shè)置如下:

(7)

(8)

式中,t0和tg分別表示個體最優(yōu)解和全局最優(yōu)解的停滯次數(shù),而T0和Tg分別對應(yīng)個體最優(yōu)解和全局最優(yōu)解的停滯的閾值。

從以上分析中發(fā)現(xiàn)，當(dāng)t0>T0,tg>Tg的時候,算法停滯,當(dāng)算法再次執(zhí)行的時候只有在局部獲得最優(yōu)值后才可以執(zhí)行,從而可以對當(dāng)前個體極值和全局極值進(jìn)行擾動,因此算法必須停滯T0或者Tg步之后才能進(jìn)行下一次迭代運(yùn)算。雖然設(shè)置了擾動因子，但存在兩個問題：一個問題是加速了節(jié)點(diǎn)定位過程中節(jié)點(diǎn)產(chǎn)生的額外消耗,從而降低傳感器的壽命；另一個問題是擾動因子有可能讓算法從一個局部最優(yōu)收斂到另一個局部最優(yōu),這樣降低了算法的時間效率和空間效率。因此為了避免以上出現(xiàn)的問題,針對式(7)和式(8)提出了動態(tài)擾動因子的概念,如下:

(9)

(10)

式中,rand1()是一個(0,1)之間的隨機(jī)數(shù),rand2()是一個(1,kmax)之間的隨機(jī)數(shù),k為當(dāng)前迭代次數(shù),kmax為最大迭代次數(shù)。因此公式(6)的變化如下:

(11)

2.2.2 懲罰函數(shù)

粒子群算法的最優(yōu)解的確定是算法的關(guān)鍵,而可行解都需要加上一定的約束條件,為了盡可能地縮小最優(yōu)解的搜索范圍,避免算法進(jìn)行不相關(guān)的盲目搜索,降低算法搜索時間,需要將粒子產(chǎn)生最優(yōu)解問題轉(zhuǎn)換為無約束的優(yōu)化問題。當(dāng)粒子滿足約束條件的時候,懲罰值會很??；反之,則會很大。對于不滿足約束條件的粒子賦予數(shù)值較大的懲罰函數(shù)數(shù)值,這樣可以有效地降低目標(biāo)函數(shù),后續(xù)的粒子就會遠(yuǎn)離無解的區(qū)域。

粒子群算法中的粒子最優(yōu)解獲得是在一定約束條件下使得某個度量值達(dá)到最小。記f為表示問題的目標(biāo)函數(shù),A為可行解,gi(x)為約束域,得到:

minf(x),x∈A

A={x|gi(x)≥0,i=1,2,…，m}

(12)

將公式(12)中的不等式約束轉(zhuǎn)換為等式約束問題:

minf(x),x∈A

s.t.min(0,gi(x))=0

(13)

(14)

式(14)中,F(x,M)為懲罰函數(shù),當(dāng)F(x,M)的最優(yōu)解逼近約束問題最優(yōu)解的時候,可行解的約束條件gi(x)的值必須達(dá)到很小,反之則很大,因此懲罰項(xiàng)Mp(x)對于非可行解進(jìn)行了懲罰,這樣能夠有效地保證約束問題可以轉(zhuǎn)化為非約束優(yōu)化問題。

3 改進(jìn)的粒子群算法的定位優(yōu)化

3.1 距離誤差修正

根據(jù)2.2.2節(jié)描述,在總結(jié)了無線傳感網(wǎng)的能量消耗后,應(yīng)該最大限度地降低未知節(jié)點(diǎn)的可行解的范圍,進(jìn)而降低未知節(jié)點(diǎn)所在區(qū)域限制,從而可能加快算法達(dá)到最優(yōu),引入文獻(xiàn)[8]中的修正系數(shù)來進(jìn)行限定。首先,通過RSSI技術(shù)得到未知節(jié)點(diǎn)X(x,y)到錨節(jié)點(diǎn)之間的距離為d1,d2,…，dm,其次,從這些錨節(jié)點(diǎn)中選取三個錨節(jié)點(diǎn)作為參考節(jié)點(diǎn)來計(jì)算一個未知節(jié)點(diǎn)的距離。

(15)

(16)

因此得到的定位模型的約束條件為:

(17)

3.2 構(gòu)造約束定位模型

目標(biāo)函數(shù)為:

(18)

根據(jù)公式(17)得到兩個約束條件為:

(19)

因此構(gòu)造后懲罰函數(shù)為:

(20)

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

4.1 實(shí)驗(yàn)環(huán)境

4.2 算法的收斂性比較

兩種定位算法的收斂性比較如圖1所示。從圖中發(fā)現(xiàn),本文算法與基本粒子群算法相比收斂速度更快,定位函數(shù)值更快。本文算法當(dāng)?shù)螖?shù)為90的時候,算法基本收斂,而基本粒子群算法迭代次數(shù)為130次才收斂,因此算法的效率提高了30.76%。究其原因是在本文算法中進(jìn)一步簡化了算法粒子的速度項(xiàng)，這樣降低了由于算法的速度引起算法收斂的問題，通過動態(tài)擾動因子和懲罰函數(shù)，有效降低算法的局部收斂可能性，使得算法能夠以更快的速度獲得全局最優(yōu)解。

圖1 兩種定位算法收斂比較

兩種算法誤差比較如表1所示。由表1看出,在測距誤差不斷變大的情況下,本算法的定位誤差遠(yuǎn)遠(yuǎn)小于基本粒子群算法,這主要是因?yàn)榫嚯x誤差的修正使得算法縮小了可行解的搜索范圍,使得算法定位更加精確,同時動態(tài)擾動算子解決了算法的局部收斂,避免了算法過早產(chǎn)生最優(yōu)解,最終使得算法能夠找到最優(yōu)解。

表1 兩種算法誤差比較

4.3 平均定位誤差比較

兩種算法的平均定位誤差比較如圖2所示。從圖中發(fā)現(xiàn),當(dāng)測距誤差所占的比例逐漸增大的時候,兩種算法的平均定位誤差都在呈現(xiàn)上升的趨勢。另外，在同一個測距誤差比例的條件下,本文算法的平均定位誤差要明顯小于基本粒子群算法,并且測距誤差所占比例不斷地增大的時候,兩者之間的定位誤差也在增大,這說明從整體上本文算法都要小于基本粒子群算法,說明了本文算法定位精度較高。圖中曲線的平緩度從另一個側(cè)面說明了本文算法的定位精度波動較小。這主要是因?yàn)橥ㄟ^粒子的位置去控制算法的進(jìn)化過程,導(dǎo)致了算法在后期的運(yùn)算過程中收斂速度變慢，特別是動態(tài)擾動因子的引入，進(jìn)一步防止了算法的局部收斂,有效地提高了算法性能,減少了找到節(jié)點(diǎn)位置的時間,距離誤差修正系數(shù)的引入,保證了可行解產(chǎn)生的區(qū)域,降低了搜索消耗的時間,更加準(zhǔn)確地找到節(jié)點(diǎn)的位置。

圖2 兩種算法平均定位誤差比較

4.4 定位均方差比較

兩種算法的定位均方差比較如圖3所示。從圖中發(fā)現(xiàn),當(dāng)測距誤差比例逐漸增大的時候,兩種算法的定位均誤差都在不斷地增加。兩種算法的曲線都比較平緩,在相同的測距誤差比例下,本文定位算法誤差都要小于基本粒子群算法。伴隨著定位誤差值的不斷增大,本文均方誤差增長速度減慢,說明算法定位穩(wěn)定性很高。這主要是因?yàn)楸苊饬怂俣冗x項(xiàng)所帶來的影響,采用位置來控制算法的進(jìn)化,距離誤差修正系數(shù)的引入限定了算法的搜索范圍,使得算法更加穩(wěn)定。

圖3 兩種算法定位均方差比較

5 結(jié)論

如何能夠降低節(jié)點(diǎn)定位帶來的誤差是無線傳感網(wǎng)中研究的主要方向,本文使用傳統(tǒng)的RSSI測距技術(shù)來獲得未知節(jié)點(diǎn)的位置,并采用改進(jìn)后的粒子群算法對未知節(jié)點(diǎn)的位置進(jìn)行優(yōu)化,取得了比較好的效果。通過仿真實(shí)驗(yàn)說明本文的算法優(yōu)于基本的粒子群算法的定位,算法效果明顯。

[1] 葉阿勇,馬建峰,裴慶祺.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位安全研究進(jìn)展[J].通信學(xué)報,2009,30(S1):74-84.

[2] 梁娟,吳媛.采用WSVM的三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2016,37(1):79-83.

[3] 宋西軍，吳梅梅.一種改進(jìn)的DV-Hop無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[J].科技通報,2016,32(7):143-145.

[4] 武曉琳,單志龍,曹樹林.基于接收信號強(qiáng)度指示測距的蒙特卡羅盒移動節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用,2015,34(4):916-920.

[5] 程麗玲.基于ABC-LS的傳感器節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(5):258-261.

[6] 于泉,孫順遠(yuǎn),徐保國.基于改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J].計(jì)算機(jī)應(yīng)用,2015,35(6):1519-1522.

[7] 胡旺,李志蜀.一種更簡單而高效的粒子群優(yōu)化算法[J].軟件學(xué)報,2007,18(4): 861-868.

[8] 石瑩.基于粒子群的無線傳感器網(wǎng)絡(luò)定位技術(shù)的研究[D].哈爾濱:哈爾濱工程大學(xué),2010.

[9] GEETHA V, PRANESH V, KALLAPURB. Clustering in wireless sensor networks: performance comparison of LEACH & LEACH-C protocols using NS2[J]. Procedia Technology, 2012(4): 163-170.

Research on the positioning of an improved particle swarm algorithm in WSN

Fu Bin

(Shaoxing Vocational & Technical College,Shaoxing 312000, China)

Aiming at node positioning in wireless sensor network, this paper adopts RSSI measuring technology to measure the distance between unknown nodes, and uses particle swarm algorithm for optimization. Aiming at the deficiency of particle swarm algorithm, this paper firstly introduces dynamic disturbance factors and penalty functions to improve the performance of the algorithm, and then it adopts the distance error modification and modification positioning error model to optimize the effect of node optimization. Through comparing basic particle swarm algorithm in the simulation experiment, good effects have been achieved in the algorithm’s convergence performance and positioning accuracy, improving the positioning effect of the node.

wireless sensor network; dynamic disturbance factor; penalty function

TP393

A

10.19358/j.issn.1674- 7720.2017.08.020

傅彬.一種改進(jìn)的粒子群算法在WSN中的定位研究[J].微型機(jī)與應(yīng)用，2017,36(8)：63-66.

2016-11-20)

傅彬(1980-),男,碩士,講師,主要研究方向：信息安全,無線傳感。

________________________