基于PBIL算法的無線傳感器網(wǎng)絡(luò)三維定位方法

劉　宏，王其濤，夏未君

(江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州　341000)

?

基于PBIL算法的無線傳感器網(wǎng)絡(luò)三維定位方法

劉宏，王其濤，夏未君

(江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州341000)

為了提高無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維定位精度，提出了基于人口增量學(xué)習(xí)(population based incremental learning，PBIL)算法的無線傳感器網(wǎng)絡(luò)三維定位方法；算法首先通過RSSI技術(shù)進(jìn)行測(cè)距，設(shè)立閾值消除包含誤差較大的測(cè)量距離，然后使用人口增量學(xué)習(xí)算法對(duì)適應(yīng)度函數(shù)進(jìn)行求解，根據(jù)Heb規(guī)則更新概率向量并產(chǎn)生新的個(gè)體，最后經(jīng)過循環(huán)尋優(yōu)得到最優(yōu)解；利用MATLAB進(jìn)行仿真，結(jié)果表明：算法的定位精度和穩(wěn)定性相較于最大似然法有了明顯的提高。

無線傳感器網(wǎng)絡(luò)；測(cè)距；PBIL；三維定位

0　引言

隨著無線通信、數(shù)據(jù)融合等技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)[1](wireless sensor networks，WSN)的發(fā)展也取得了長足的進(jìn)步，使其在智慧地球中發(fā)揮著越來越大的作用。在實(shí)際應(yīng)用中，無線傳感器網(wǎng)絡(luò)工作的環(huán)境往往是高突不平的，同時(shí)人們對(duì)信息質(zhì)量的要求也越來越高，二維平面定位技術(shù)已經(jīng)越來越無法滿足需求，因此實(shí)現(xiàn)WSN節(jié)點(diǎn)快速而準(zhǔn)確的三維定位就顯得尤為重要[2]。

把進(jìn)化算法[3](evolutionary algorithms, EAs)應(yīng)用于WSN節(jié)點(diǎn)定位是眾多專家學(xué)者的研究重點(diǎn)，文獻(xiàn)[4]使用遺傳算法對(duì)DV-hop算法得到的位置坐標(biāo)進(jìn)行校正，算法在不提高成本的情 況下，相較于DV-hop算法提高了定位精度并擴(kuò)大了定位范圍；文獻(xiàn)[5]對(duì)蝙蝠算法加以改進(jìn)并應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中，降低了平均跳距引起的定位誤差，提高了網(wǎng)絡(luò)節(jié)點(diǎn)的定位精度；文獻(xiàn)[6]把蟻群算法應(yīng)用于礦井下的WSN節(jié)點(diǎn)定位中，在不添加多余硬件條件下提高了定位精度；文獻(xiàn)[7]在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中引入量子遺傳算法，利用量子遺傳算法求解模型獲得的最優(yōu)解作為節(jié)點(diǎn)的定位坐標(biāo)，提高了網(wǎng)絡(luò)的穩(wěn)定性和定位精度。傳統(tǒng)上采用最大似然法(ML算法)求解非線性方程組得到未知節(jié)點(diǎn)的坐標(biāo)，但較大的測(cè)距誤差導(dǎo)致定位精度很差，因此本文在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位中引入基于人口增量學(xué)習(xí)[8](population based incremental learning，PBIL)算法。仿真結(jié)果表明：方法不但提高了節(jié)點(diǎn)的三維定位精度，同時(shí)也可以在較低的連通度下實(shí)現(xiàn)較高的定位精度，網(wǎng)絡(luò)的穩(wěn)定性也較高。

1　RSSI測(cè)距及最大似然法

無線傳感器網(wǎng)絡(luò)中的測(cè)距技術(shù)共有4種：以電磁波到達(dá)時(shí)間為基礎(chǔ)的TOA、以電磁波和聲波到達(dá)時(shí)間差為基礎(chǔ)的TDOA、以發(fā)射信號(hào)角度為基礎(chǔ)的AOA和以射頻信號(hào)強(qiáng)度為基礎(chǔ)的RSSI。RSSI測(cè)距技術(shù)是在路徑損耗和發(fā)射端信號(hào)強(qiáng)度已知的情況下，通過測(cè)量接收信號(hào)強(qiáng)度計(jì)算兩點(diǎn)間的距離。由于現(xiàn)有的商用芯片都可以測(cè)量射頻信號(hào)的強(qiáng)度，無需添加額外的硬件。因此使用RSSI測(cè)距技術(shù)的無線傳感器網(wǎng)絡(luò)技術(shù)成熟、價(jià)格便宜、使用方便、廣受歡迎。

由于多徑、繞射等不確定因素的存在，它們單個(gè)有時(shí)甚至疊加起來，產(chǎn)生嚴(yán)重的干擾，影響了未知節(jié)點(diǎn)接收信號(hào)的強(qiáng)度，從而導(dǎo)致測(cè)量距離中含有不同比例的測(cè)距誤差。因此選擇對(duì)現(xiàn)實(shí)因素考慮最多的路徑損耗模型：對(duì)數(shù)-常態(tài)分布模型[9]，設(shè)PL(d0)[dB]為發(fā)射端信號(hào)強(qiáng)度，PL(d)[dB]為接收端信號(hào)強(qiáng)度：

PL(d)[dB]=PL(d0)[dB]+10nplg(d/d0)+Xσ

(1)

式中，d為M(錨節(jié)點(diǎn))與N(未知節(jié)點(diǎn))之間的測(cè)量距離；d0為取值1 m的近地參考距離；np為路徑損耗指數(shù)；Xσ為高斯隨機(jī)誤差。

由于Xσ是正態(tài)0均值，在實(shí)際應(yīng)用中可以簡化計(jì)算模型，得出測(cè)量距離d為：

(2)

由于測(cè)量距離d存在測(cè)距誤差，傳統(tǒng)上使用最大似然法完成無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位。設(shè)未知節(jié)點(diǎn)為N(x,y,z)，錨節(jié)點(diǎn)為M1(x1,y1,z1)、M2(x2,y2,z2)、M3(x3,y3,z3)、…、Mk(xk,yk,zk)，則存在如下關(guān)系式：

(3)

對(duì)式(3)進(jìn)行求解得到未知節(jié)點(diǎn)的坐標(biāo)X：

(4)

式中，

由于d存在測(cè)距誤差，導(dǎo)致式(3)是非線性的，當(dāng)測(cè)距誤差較大時(shí)，未知節(jié)點(diǎn)的定位精度變的較差，因此可以使用進(jìn)化算法依據(jù)適應(yīng)度函數(shù)尋找最優(yōu)坐標(biāo)。

2　PBIL算法基本原理

PBIL算法是一種新型的進(jìn)化算法，算法的個(gè)體使用概率模型進(jìn)行描述，通過統(tǒng)計(jì)學(xué)習(xí)手段從宏觀上對(duì)群體進(jìn)行描述，然后依據(jù)概率模型產(chǎn)生新的個(gè)體，反復(fù)進(jìn)行并最終實(shí)現(xiàn)群體的進(jìn)化。PBIL算法自提出以來就受到廣泛的關(guān)注，其控制參數(shù)少、簡單易實(shí)現(xiàn)，在解決多維度問題上比遺傳算法更有效，同時(shí)也降低了時(shí)間的復(fù)雜性，是一個(gè)較理想的優(yōu)化算法。

PBIL算法原理如下：

設(shè)s為解的個(gè)體，是一個(gè)二進(jìn)制串且長度為w，si(i=1,2,3,…,n)為二進(jìn)制串的第i個(gè)基因位，每個(gè)基因位的取值為0或者1，則優(yōu)化問題表示如下：

minf(s)

(5)

式中，f為尋優(yōu)適應(yīng)度函數(shù)，最小適應(yīng)值對(duì)應(yīng)的個(gè)體為最優(yōu)解。

同時(shí)設(shè)P=(p1,p2,p3,…,pn)為n維的概率向量，其中的pi表示當(dāng)前個(gè)體中對(duì)應(yīng)基因位si取值1的學(xué)習(xí)概率，則1-pi為取值0的學(xué)習(xí)概率，進(jìn)化學(xué)習(xí)過程如下。

2)初始化學(xué)習(xí)概率P：概率向量pi=0.5，即進(jìn)化初期si取0或1的概率是相等的。

2)生成解空間：由學(xué)習(xí)概率隨機(jī)產(chǎn)生L個(gè)個(gè)體，則解空間為S=(s1,s2,s3,…,sl)。

3)計(jì)算適應(yīng)值：依據(jù)適應(yīng)度函數(shù)計(jì)算解空間所有個(gè)體的適應(yīng)值并按照大小排序。

4)尋找最優(yōu)個(gè)體組：按照排序好的個(gè)體，取出適應(yīng)值最小的t(t≤L)個(gè)個(gè)體s1，s2，s3，…，st并組成最優(yōu)解組sx。

5)修正概率向量：利用步驟四中的最優(yōu)解組sx，采用機(jī)器學(xué)習(xí)中的Heb規(guī)則更新概率向量：

(6)

式中，r為學(xué)習(xí)速率：大小在[0.01，0.1]之間。r越小，收斂速度越慢，相對(duì)搜尋到的個(gè)體質(zhì)量更優(yōu)，相反，收斂速度更快，相對(duì)搜尋到的個(gè)體質(zhì)量較差。

6)停止進(jìn)化判斷：若達(dá)到最大進(jìn)化次數(shù)或者需要的精度，則算法停止，若未達(dá)到，則跳轉(zhuǎn)至2)。

3　基于PBIL算法的定位方法表述

3.1跳出局部最優(yōu)方法

PBIL算法和其它進(jìn)化算法一樣，在求解非線性多維問題時(shí)可能存在局部最優(yōu)[10]，這是因?yàn)樵谶M(jìn)化過程中對(duì)概率模型進(jìn)行學(xué)習(xí)時(shí)，解空間擬合度會(huì)慢慢增大，在算法進(jìn)化后期，種群多樣性會(huì)迅速減小，從而陷入局部最優(yōu)，因此本算法在尋優(yōu)后期引入遺傳算法中的交叉變異操作，維持種群多樣性在一定的水平，從而抑制局部最優(yōu)解的產(chǎn)生，使尋優(yōu)工作繼續(xù)進(jìn)行下去。

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

WSN定位誤差源于RSSI的測(cè)距誤差，因此本文通過剔除誤差較大的測(cè)量距離和在適應(yīng)度函數(shù)中添加權(quán)值來抑制測(cè)距誤差對(duì)定位精度的影響。

由于RSSI測(cè)距信號(hào)在近距離時(shí)衰減的很快，在遠(yuǎn)距離時(shí)信號(hào)衰減的較為緩慢，因此測(cè)量距離越近時(shí)測(cè)距誤差越小，相反測(cè)距誤差越大。設(shè)測(cè)距半徑為R，根據(jù)RSSI測(cè)距誤差變化規(guī)律：測(cè)量距離小于0.5R時(shí)，測(cè)距誤差平均小于0.1R；測(cè)量距離在0.5R和0.75R之間時(shí)，測(cè)距誤差平均在0.1R和0.2R之間；測(cè)量距離大于0.75R時(shí)，測(cè)距誤差平均在0.2R和0.4R之間，個(gè)別測(cè)距誤差甚至達(dá)到0.5R。因此必須設(shè)立閾值消除測(cè)距誤差較大的測(cè)量值，閾值設(shè)立如下：

W=0.75R

(7)

式中，W為閾值，即當(dāng)未知節(jié)點(diǎn)通信范圍內(nèi)接收到的測(cè)距信號(hào)多于4時(shí)，即可啟用閾值設(shè)定并消除誤差較大的d(d≥W)。

適應(yīng)度函數(shù)值表示當(dāng)前解的優(yōu)劣，較小的適應(yīng)值對(duì)應(yīng)解得質(zhì)量較高，相反解得質(zhì)量較小。設(shè)當(dāng)前經(jīng)PBIL算法進(jìn)化得到的最佳坐標(biāo)為N(x,y,z)，當(dāng)前未知節(jié)點(diǎn)可連接的錨節(jié)點(diǎn)共有k個(gè)，第j個(gè)錨節(jié)點(diǎn)的坐標(biāo)為M(xj,yj,zj)，未知節(jié)點(diǎn)到第j個(gè)錨節(jié)點(diǎn)的距離為dj則可得：

(8)

由于測(cè)量距離越大，測(cè)距誤差也越大，因此需要設(shè)立權(quán)值控制不同測(cè)量距離對(duì)定位精度的影響，較大的測(cè)量距離賦予較小的權(quán)值，反之賦予較大的權(quán)值，因此選擇dj的倒數(shù)作為權(quán)值，適應(yīng)度函數(shù)設(shè)計(jì)如下：

(9)

3.3PBIL定位算法流程

設(shè)群體最大進(jìn)化次數(shù)為G，則基于PBIL算法的WSN三維定位流程圖如圖1所示。

圖1　定位算法流程圖

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

4.1實(shí)驗(yàn)設(shè)計(jì)

(10)

式中，m為未知節(jié)點(diǎn)總數(shù)。

4.2實(shí)驗(yàn)結(jié)果分析

1)不同連通度對(duì)局部最優(yōu)解的影響：

進(jìn)化算法在多維度問題上一般存在局部最優(yōu)問題，在算法后期引入交叉變異操作可以較好的解決局部最優(yōu)。本算法在測(cè)距誤差為0時(shí)且未引入交叉變異的情況下，分析了連通度對(duì)局部最優(yōu)解的影響，仿真結(jié)果如圖2所示：由(a)可以得出在連通度為4時(shí)局部最優(yōu)率為5%；由(b)可以得出在連通度為5時(shí)局部最優(yōu)率為3%；由(c)可以得出在連通度為6時(shí)局部最優(yōu)率為1%。隨著連通度的增加不但局部最優(yōu)率逐漸減小而且局部最優(yōu)的節(jié)點(diǎn)的定位誤差也在減小，在仿真過程中還發(fā)現(xiàn)當(dāng)連通度大于10時(shí)，局部最優(yōu)率小于千分之一。說明在無線傳感器網(wǎng)絡(luò)三維定位中除了可以在算法中引入交叉變異來消除局部最優(yōu)解，還可以增加連通度來抑制局部最優(yōu)解。

圖2　不同連通度下的局部最優(yōu)情況

2)穩(wěn)定性及定位精度對(duì)比：

在連通度為5、測(cè)距誤差為20%的情況下共測(cè)試120個(gè)節(jié)點(diǎn)的定位誤差，形成的誤差曲線如圖3所示，進(jìn)一步對(duì)數(shù)據(jù)進(jìn)行處理，結(jié)果如表1所示。在表1中可以得出PBIL算法的最大、最小定位誤差差值為0.075 3，ML算法的最大、最小定位誤差差值為0.189 1，說明PBIL算法比ML算法的定位精度的波動(dòng)性更??；PBIL算法的平均定位誤差比ML算法小了0.099 6，說明PBIL算法的定位精度更高；PBIL算法的標(biāo)準(zhǔn)差比ML算法小了0.029 6，說明PBIL算法的穩(wěn)定性更高。從圖3中的定位誤差曲線也可以直觀的得出PBIL算法無論在定位精度還是穩(wěn)定性比ML算法都要高。

表1　穩(wěn)定性分析

圖3　PBIL與ML定位誤差曲線對(duì)比

3)測(cè)距誤差和定位精度的關(guān)系：

在實(shí)際環(huán)境中RSSI測(cè)距信號(hào)在近距離時(shí)衰減很快，在遠(yuǎn)距離時(shí)衰減的較為緩慢，導(dǎo)致在距離較遠(yuǎn)時(shí)的測(cè)距誤差急劇增大，因此在較大測(cè)距誤差下維持一個(gè)較高的定位精度就現(xiàn)的尤為重要。因此在連通度為5時(shí)測(cè)試不同測(cè)距誤差下的平均定位誤差，結(jié)果如圖4所示。由圖4可以看出隨著測(cè)距誤差的增大ML算法的誤差曲線斜率幾乎不變，定位誤差增加的很快，而PBIL算法的誤差曲線的斜率一直在下降，定位誤差的增長較為緩慢。還可以看出2種算法的平均定位誤差差值也隨著測(cè)距誤差的加大而增大。說明PBIL算法比ML算法的抗干擾能力更強(qiáng)，在測(cè)距誤差較大的情況下也維持較好的定位精度。

圖4　對(duì)比不同測(cè)距誤差下的平均定位誤差

4)平均連通度和定位精度的關(guān)系：

在較低的連通度下實(shí)現(xiàn)較高的定位精度以及減小連通度對(duì)定位精度的影響是無線傳感器網(wǎng)絡(luò)三維定位技術(shù)追求的目標(biāo)之一。在測(cè)距誤差為20%時(shí)，測(cè)試連通度由4到13平均定位誤差的變化情況，結(jié)果如圖5所示?？梢缘贸觯篜BIL算法和ML算法在連通度為4到7時(shí)平均定位誤差下降速度較快，在連通度為8到13是下降的較為緩慢；PBIL算法連通度由4到13時(shí)，平均定位誤差共下降0.038 1，ML算法共下降了0.080 1，說明PBIL算法受連

圖5　對(duì)比不同連通度下的平均定位誤差

通度的影響更小，在較小的連通度下就可以得到較高的定位精度，較適合應(yīng)用在錨節(jié)點(diǎn)稀疏的網(wǎng)絡(luò)。

5　結(jié)束語

為了減小測(cè)距誤差對(duì)無線傳感器網(wǎng)絡(luò)三維定位精度的影響，提出了一種基于人口增量學(xué)習(xí)(PBIL)算法的定位方法。算法在RSSI測(cè)距的基礎(chǔ)上，使用PBIL算法對(duì)適應(yīng)度函數(shù)進(jìn)行求解，同時(shí)通過仿真研究了本算法的性能，分析了不同連通度下對(duì)局部最優(yōu)的影響，測(cè)試了穩(wěn)定性，對(duì)比了測(cè)距誤差、連通度對(duì)定位精度的影響。仿真結(jié)果表明：PBIL算法在較高的連通度下能很好的抑制局部最優(yōu)解，同時(shí)在定位精度和穩(wěn)定性方面比ML算法有了較大的提高。

[1]趙仕俊，唐懿芳．無線傳感器網(wǎng)絡(luò)[M]．北京：科學(xué)出版社，2013．

[2]Mert B，Liu M，Shen W M，et al．Localization in cooperative wireless sensor networks: A review[A]．Proceedings of the 2009 13th International Conference on Computer Supported Cooperative Work in Design[C]. 2009：438-443．

[3]Thomas J．Analyzing evolution algorithms[M]．Berlin Heidelberg:Springer-verlag，2013．

[4]鄧力．基于遺傳算法WSN節(jié)點(diǎn)定位算法研究[J]．計(jì)算機(jī)仿真，2011,28(9):161-164．

[5]賴錦輝．基于蝙蝠優(yōu)化算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究[J]．計(jì)算機(jī)測(cè)量與控制，2014,22(8):2709-2712．

[6]梁美玉，李莉，陳坤．基于蟻群算法的井下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究[J]．煤礦機(jī)械，2010,31(12):48-50．

[7]方旺盛，曾晶．基于量子遺傳算法的非測(cè)距節(jié)點(diǎn)定位算法研究[J]．計(jì)算機(jī)應(yīng)用與軟件，2013，30(2)：180-183．

[8] Yang Shengxiang，Yao Xin．Experimental study on population-based incremental learning algorithms for dynamic optimization problems[J]．Soft comput，2005，(9):815-834．

[9]方震，趙湛．基于RSSI測(cè)距分析[J]．傳感技術(shù)學(xué)報(bào)，2007，20(11)：2526-2530．

[10]Hohfeld M，Rudolph G．Towards a theory of population based incremental learning[A].In: Proceedings of the 4th International Conference on Evolutionary Computation[C]. IEEE, 1997： 1-5．

A Method of the WSN Three-dimensional Positioning Based on PBIL Algorithm

Liu Hong,Wang Qitao,Xia Weijun

(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology, Ganzhou341000,China)

In order to improve the three-dimensional positioning accuracy of wireless sensor network node, it is proposed that wireless sensor network three-dimensional positioning method based on the population based incremental learning algorithm.At first,the algorithm by RSSI measurement of the distance and set a threshold to eliminate the error containing big measuring distance.Then it uses the population based incremental learning algorithm to find the solution to the fitness function, and according to the rules of Heb,it updates probability vector and produces new individual.Finally,it obtains the optimal solution by the cycle optimization. Through using Matlab simulation, its results show that the positioning accuracy and stability of the algorithm had obvious improvement compared with maximum likelihood method.

wireless sensor network; ranging; PBIL; three-dimensional positioning

2015-07-13；

2015-08-25。

國家自然科學(xué)基金資助項(xiàng)目(61163063)。

劉宏(1968-)，男，江西萍鄉(xiāng)人，副教授，碩士研究生導(dǎo)師，主要從事無線傳感器網(wǎng)絡(luò)基礎(chǔ)設(shè)施的理論和技術(shù)方向的研究。

1671-4598(2016)01-0334-04

10.16526/j.cnki.11-4762/tp.2016.01.093

TP393

A