劉　宏，王其濤，夏未君

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

?

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

劉宏，王其濤，夏未君

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

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

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

0　引言

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

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

1　RSSI測距及最大似然法

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

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

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

(1)

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

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

(2)

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

(3)

對式(3)進行求解得到未知節(jié)點的坐標X：

(4)

式中，

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

2　PBIL算法基本原理

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

PBIL算法原理如下：

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

minf(s)

(5)

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

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

2)初始化學習概率P：概率向量pi=0.5，即進化初期si取0或1的概率是相等的。

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

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

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

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

(6)

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

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

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

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

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

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

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

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

W=0.75R

(7)

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

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

(8)

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

(9)

3.3PBIL定位算法流程

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

圖1　定位算法流程圖

4　仿真實驗

4.1實驗設(shè)計

(10)

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

4.2實驗結(jié)果分析

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

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

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

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

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

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

圖3　PBIL與ML定位誤差曲線對比

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

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

圖4　對比不同測距誤差下的平均定位誤差

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

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

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

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

5　結(jié)束語

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

[1]趙仕俊，唐懿芳．無線傳感器網(wǎng)絡(luò)[M]．北京：科學出版社，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é)點定位算法研究[J]．計算機仿真，2011,28(9):161-164．

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

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

[7]方旺盛，曾晶．基于量子遺傳算法的非測距節(jié)點定位算法研究[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測距分析[J]．傳感技術(shù)學報，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。

國家自然科學基金資助項目(61163063)。

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

1671-4598(2016)01-0334-04

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

TP393

A