丁海強,齊光快,莊華亮,何熊熊

(浙江工業(yè)大學(xué)信息工程學(xué)院,杭州 310023)

?

基于負約束條件下最大似然估計的無線傳感網(wǎng)絡(luò)定位算法*

丁海強,齊光快,莊華亮*,何熊熊

(浙江工業(yè)大學(xué)信息工程學(xué)院,杭州 310023)

針對基于RSSI(Received Signal Strength Indicator)的無線傳感網(wǎng)絡(luò)定位算法精度不高的問題,提出一種負約束條件下的似然估計定位算法。當(dāng)未知節(jié)點在參考節(jié)點的通信范圍之外時,引入負約束條件來提高定位精度。主要工作可分為三部分:第一,根據(jù)RSSI值測量參考節(jié)點與未知節(jié)點之間的距離。第二,根據(jù)參考節(jié)點與未知節(jié)點通信關(guān)系建立正約束和負約束條件下的似然估計函數(shù)。第三,利用粒子群優(yōu)化算法找到未知節(jié)點的最佳位置。仿真結(jié)果表明,引入負約束條件可以提高定位精度,且優(yōu)于傳統(tǒng)的定位算法。

無線傳感器網(wǎng)絡(luò);負約束;最大似然估計;定位;粒子群優(yōu)化

20世紀(jì)90年代以來,人們就開始關(guān)注無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)技術(shù),被認為是21世紀(jì)最重要的技術(shù)之一。無線傳感網(wǎng)絡(luò)廣泛應(yīng)用于軍事、環(huán)境、工業(yè)等方面[1]。在無線傳感網(wǎng)絡(luò)技術(shù)中,節(jié)點定位是無線傳感網(wǎng)絡(luò)的主要支撐技術(shù)。定位技術(shù)可應(yīng)用于目標(biāo)識別、目標(biāo)跟蹤、移動目標(biāo)的檢測、人員定位等[2]。因此,隨著無線傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展,如何獲得準(zhǔn)確的節(jié)點位置信息也變得越來越重要。

目前,典型的定位方法主要分為兩類:無需測距和基于測距。無需測距方法不需要測量節(jié)點間的距離、角度或者其他信息,而是根據(jù)網(wǎng)絡(luò)的連接度來實現(xiàn)定位,其缺點是定位精度低。此類方法主要為質(zhì)心定位算法,DV-hop算法和APIT算法[3]?；跍y距方法主要采用額外的硬件來測量節(jié)點間的距離來實現(xiàn)定位。雖然此類方法需要額外成本并且消耗能量,但能獲得比較高的精度。此類方法主要為信號到達角度(AOA),信號到達時間(TOA),信號到達時間差(TDOA)和RSSI等[4-7]。在實際應(yīng)用過程中(尤其是室內(nèi)環(huán)境),大部分方法都采用節(jié)點間信號強度與距離之間的關(guān)系來實現(xiàn)測距[8]。

下面介紹幾種典型的定位系統(tǒng):

微軟公司的RADAR系統(tǒng)是基于IEEE802.11標(biāo)準(zhǔn)的室內(nèi)定位系統(tǒng)[9],它事先在測量區(qū)域內(nèi)大量記錄各個位置的RSSI值,定位時,根據(jù)當(dāng)前的RSSI值來與之前標(biāo)定好的RSSI進行匹配來確定節(jié)點位置(定位誤差大約在6 m)。此系統(tǒng)要求定位前需大量測試各位置的RSSI值,因此工作量大,布置成本高。

麻省理工學(xué)院的Cricket室內(nèi)定位系統(tǒng)主要由Beacon節(jié)點和Listener節(jié)點組成[10]。Beacon節(jié)點同時發(fā)射超聲波和射頻信號,Listener節(jié)點偵聽到信號后,根據(jù)TDOA測距原理(測距范圍大約在0～10 m)并用三邊定位法對未知節(jié)點進行定位。此系統(tǒng)容易受障礙物影響,非常不適合非視距(NLOS)復(fù)雜的環(huán)境。

浙江大學(xué)的INEMO系統(tǒng)根據(jù)房間的布局把建筑物分成不同的等級[11]。當(dāng)用戶(已攜帶節(jié)點)靠近附近的房間時,傳感器節(jié)點可以與之相近的參考節(jié)點交換信息,根據(jù)信號接收強度,判斷用戶所在位置。此系統(tǒng)只適用于辦公樓比較規(guī)格的室內(nèi)環(huán)境。另一方面,在定位時,因為信息通信量大,易造成能量消耗大,使得定位精度也不高。

針對上述各定位系統(tǒng)的不足,提出一種負約束條件下的似然估計定位算法。第1節(jié)中討論了RSSI測距原理,給出了距離的對數(shù)正態(tài)分布模型。第2節(jié)中根據(jù)參考節(jié)點與未知節(jié)點之間的通信關(guān)系,建立正約束和負約束條件下的最大似然函數(shù),并應(yīng)用粒子群優(yōu)化算法找到未知節(jié)點位置。第3節(jié)根據(jù)算法原理,用計算機仿真驗證算法的可行性。最后,給出本文結(jié)論。

1 RSSI測距模型

RSSI常用于無線傳感定位,它根據(jù)發(fā)送端和接收端之間的功率損耗來計算出它們之間距離。利用理論或者經(jīng)驗?zāi)Ｐ偷玫焦β蕮p耗與距離之間的關(guān)系為下式:

(1)

其中PL(d)為距離D=d時的接收信號強度,P為距離d時的接收信號強度,n為路徑損耗指數(shù),ξ為零均值標(biāo)準(zhǔn)差為σp的隨機變量。在實際應(yīng)用中,變量σp不會隨距離的變化而變化,只與所處的環(huán)境有關(guān)?；喪?1)為:

P=P0-10nlgd-ξσp

(2)

其中P0為距離1 m時的接收信號強度。通過實際測試可知,參數(shù)n和ξσp是相互獨立的,可以對測量數(shù)據(jù)進行最小二乘估計得到。因此,當(dāng)兩個節(jié)點間的RSSI值測量得到時,它們之間的距離就可以計算得到,即:

(3)

如圖1所示,測量實驗室內(nèi)RSSI值與距離之間的關(guān)系。由圖可知,隨著節(jié)點間距離的增加,RSSI值呈遞減趨勢。試驗中,采用TI公司的CC1110射頻芯片作為傳感器節(jié)點,變量ξσp和n可以通過對測量得到的RSSI值進行最小二乘估計得到。我們測試得到n=2.41,ξσp=-3.54。根據(jù)測試數(shù)據(jù),可擬合得到對數(shù)正態(tài)陰影傳播模型。

圖1 距離與RSSI之間關(guān)系

根據(jù)式(2),距離d為對數(shù)正態(tài)分布,改寫式(3)為:

lnd～N(μd,σd)

(4)

其中μd近似等于lnd,σd等于σp/10n。對于特定的物理環(huán)境,變量σd可估計得到且為常量。如圖2所示,實際測試RSSI值d=10 m時的概率密度函數(shù)曲線。圖中可以看出,曲線的最高點最為接近距離的真實值。因此,我們可以把概率密度函數(shù)的最大值的點作為對未知節(jié)點的定位。在實際環(huán)境中,一直存在遮擋效應(yīng),為了提高定位的精度,減少非視距誤差,可以使用卡爾曼濾波方法減小測距誤差[12-13]。下面介紹負約束條件下似然估計定位算法。

圖2 RSSI=-64.5 dBm時距離d的對數(shù)正態(tài)分布

2 正負約束條件下的似然估計定位

2.1 正約束條件下似然估計

在實際應(yīng)用中,未知節(jié)點在參考節(jié)點的通信范圍內(nèi)時,測得的RSSI值比較準(zhǔn)確,從而計算得到相對精確地距離。如圖3所示,待定位節(jié)點在參考節(jié)點的通信范圍之內(nèi),我們稱這種關(guān)系為正約束。

圖3 參考節(jié)點與未知節(jié)點的正約束關(guān)系

假設(shè)傳感器網(wǎng)絡(luò)由i個參考節(jié)點和j個未知節(jié)點組成。未知節(jié)點的位置向量X可定義為:

X=[x1…xjy1…yj]T

(5)

則距離dij的對數(shù)正態(tài)分布為:

(6)

(7)

因此,可以得到距離dij的概率密度函數(shù)ρij(X)為:

(8)

設(shè)概率密度函數(shù)ρij(X)為似然函數(shù),即得到正約束條件下的似然函數(shù):

(9)

然而,當(dāng)未知節(jié)點在參考節(jié)點的通信范圍之外時,也可以利用它們之間的關(guān)系進行對未知節(jié)點的定位,下面介紹負約束條件下的似然估計定位。

2.2 負約束條件下似然估計

假如參考節(jié)點和未知節(jié)點之間沒有通信鏈接(或者RSSI值小于RSSImin),則可以推測出它們之間的距離大于其通信范圍。如圖4所示,未知節(jié)點在參考節(jié)點的通信范圍之外,我們稱這種關(guān)系負約束。

圖4 參考節(jié)點與未知節(jié)點的負約束關(guān)系

(10)

(11)

(12)

(13)

(14)

(15)

(16)

為了找到最大似然估計,將式(16)轉(zhuǎn)化為最小二乘問題,即

(17)

(18)

下面介紹利用粒子群優(yōu)化算法解決最小二乘問題。

2.3 粒子群優(yōu)化定位

粒子群優(yōu)化是近年來發(fā)展起來的一種新的進化算法,它模仿于生物鳥群的社會行為。粒子群優(yōu)化算法具有收斂速度快、易實現(xiàn)的特點,是一種高效實用的搜索算法。在無線傳感網(wǎng)絡(luò)中,可使用PSO算法有效的解決定位問題[14-15]。

PSO算法首先初始化m個隨機粒子(候選解稱之為粒子),每個粒子有自己的位置且以一定的速度飛行。算法根據(jù)粒子本身和同伴的飛行經(jīng)驗動態(tài)地調(diào)整參數(shù),通過迭代計算得到目標(biāo)函數(shù)的最優(yōu)解。假設(shè)n維搜索空間中粒子的位置和速度分別為X=[x1…xjy1…yj]T和V,在每一次迭代中,粒子通過追蹤個體最優(yōu)值pbest和群體最優(yōu)值gbest來更新自己。找到這兩個最優(yōu)值時,粒子根據(jù)下式來更新自己的速度和位置。

VX(k+1)=wVX(k)+c1r1(k)(pbest(k)-X(k))+
c2r2(k)(gbest(k)-X(k))

(19)

X(k+1)=X(k)+VX(k+1)

(21)

其中c1和c2是學(xué)習(xí)因子,r1(k)和r2(k)是隨機對角矩陣并且服從[0,1]均勻分布。pbest是迭代過程中的個體最優(yōu)解,gbest是群體最優(yōu)解。粒子群優(yōu)化定位算法步驟為:

①根據(jù)RSSI測距模型的得到距離d,即式(3)。

②當(dāng)未知節(jié)點在參考節(jié)點的通信范圍之內(nèi)時,引入正約束條件得到似然函數(shù),即式(9)。

③當(dāng)未知節(jié)點在參考節(jié)點的通信范圍外時,引入負約束條件,聯(lián)合正負約束條件得到似然函數(shù),并轉(zhuǎn)化為最小二乘問題,即式(17)、(18)。

⑤把每個粒子帶入目標(biāo)函數(shù)中,得到各粒子的優(yōu)劣性,將當(dāng)前各粒子的位置存儲于pbest中。根據(jù)各粒子的優(yōu)劣性把pbest中最優(yōu)粒子存儲于gbest中,再按照式(19)、式(20)更新粒子的位置和速度。

⑤重復(fù)步驟⑤,達到所設(shè)定的迭代次數(shù)或定位精度時,停止搜索,輸出最優(yōu)粒子gbest的位置,即定位結(jié)束。

3 仿真分析

圖5 正約束條件下的似然估計定位

圖6 正負約束條件下似然估計的定位

3.1 參考節(jié)點數(shù)量對定位的影響

圖7 參考節(jié)點數(shù)對定位誤差影響

這里主要討論參考節(jié)點數(shù)對定位誤差的影響。計算仿真中,維持未知節(jié)點數(shù)量不變,持續(xù)增加參考節(jié)點的數(shù)量,如圖7所示。仿真結(jié)果表明,隨著參考節(jié)點數(shù)的增加,定位誤差不斷的減小,相比較于正約束條件下的似然估計定位,引入負約束條件可以提高定位精度。一般而言,增加參考節(jié)點數(shù),必然增加網(wǎng)絡(luò)密度,未知節(jié)點將收到更多的參考信息,必然提高定位精度。然而,當(dāng)參考節(jié)點數(shù)達到一定數(shù)量時,定位誤差趨向于某一定值,此時定位精度主要取決于測距誤差。

3.2 測距誤差對定位的影響

現(xiàn)實物理環(huán)境中,存在遮擋效應(yīng),必然在測距過程中產(chǎn)生誤差。計算仿真中,討論N1=7(N1為參考節(jié)點數(shù))和N1=11兩種情況下,比較測距誤差對傳統(tǒng)三邊定位、正約束條件下似然估計、正負約束條件下似然估計定位影響。如圖8所示,隨著距離標(biāo)準(zhǔn)差σ的不斷增大,定位誤差也隨著增大。圖中可以看出,正負約束條件下的似然估計定位誤差最小。如表1所示,相比較于正約束條件下的似然估計,引入負約束可以提高定位精度,大約為20%。相比較于傳統(tǒng)的三邊定位算法,聯(lián)合正負約束條件下的似然估計定位算法誤差可減小34.3%左右。

圖8 測距誤差對定位誤差影響

表1 參考節(jié)點N1=11時各定位算法的性能比較

注:PC為正約束,NC為負約束

3.3 算法迭代次數(shù)對定位誤差影響

仿真實驗中,布置11個參考節(jié)點來分析算法迭代次數(shù)對定位誤差的影響。如圖9所示,迭代160次時,定位誤差開始收斂于某一常數(shù),此時定位誤差主要取決于測距誤差。當(dāng)然,隨著迭代次數(shù)的增加,定位誤差必然收斂于最小值,但此時必然增加算法的復(fù)雜度。因此,在誤差能接受的范圍內(nèi),需要合理的選擇迭代次數(shù)。

4 結(jié)論

本文提出了一種負約束條件下的似然估計定位算法,該算法建立于RSSI測距基礎(chǔ)上,聯(lián)合正約束和負約束條件建立似然估計函數(shù)并利用粒子群優(yōu)化算法找到未知節(jié)點的位置。仿真結(jié)果顯示,引入負約束條件可提高定位精度,且比傳統(tǒng)的定位算法在穩(wěn)定性方面也更優(yōu)。下一步工作中,將重點考慮在不同的物理環(huán)境中怎樣合理的選擇負約束條件,使得定位誤差最小。

[1] Low K S,Win W N N,Er M J. Wireless Sensor Networks for Industrial Environments[C]//Computational Intelligence for Modelling,Control and Automation,2005 and International Conference on Intelligent Agents,Web Technologies and Internet Commerce,International Conference on.IEEE,2005,2:271-276.

[2]Arora A,Dutta P,Bapat S,et al. A Line in the Sand:a Wireless Sensor Network for Target Detection,Classification,and Tracking[J]. Computer Networks,2004,46(5):605-634.

[3]Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems,2003,22(1-4):267-280.

[4]Niculescu D,Nath B. Ad Hoc Positioning System(APS)Using AOA[C]//INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. IEEE,2003,3:1734-1743.

[5]程秀芝,朱達榮,張申,等. 基于RSSI差分校正的最小二乘——擬牛頓定位算法[J]. 傳感技術(shù)學(xué)報,2014,27(1):123-127.

[6]陶為戈,朱昳華,賈子彥. 基于RSSI混合濾波和最小二乘參數(shù)估計的測距算法[J]. 傳感技術(shù)學(xué)報,2012,25(12):1748-1753.

[7]Peng R,Sichitiu M L. Robust,Probabilistic,Constraint-Based Localization for Wireless Sensor Networks[C]//SECON. 2005:541-550.

[8]Xingbo W,Huanshui Z,Xiangyuan J. Collaborative Target Tracking in WSNs Based on Maximum Likelihood Estimation and Kalman Filter[C]//Control Conference(CCC),2011 30th Chinese. IEEE,2011:4946-4951.

[9]Bahl P,Padmanabhan V N. RADAR:An in-Building RF-Based User Location and Tracking System[C]//INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Ieee,2000,2:775-784.

[10]Priyantha N B,Chakraborty A,Balakrishnan H. The Cricket Location-Support System[C]//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. ACM,2000:32-43.

[11]Hongbin L,Xingfa S,Jun Z,et al. Inemo:Distributed RF-Based Indoor Location Determination with Confidence Indicator[J]. Eurasip Journal on Advances in Signal Processing,2007,2008:1-11.

[12]Wann C D,Hsueh C S. Non-Line of Sight Error Mitigation in Ultra-Wideband Ranging Systems Using Biased Kalman Filtering[J]. Journal of Signal Processing Systems,2011,64(3):389-400.

[13]Chang X W,Champagne B. An Improved Extended Kalman Filter for Localization of a Mobile Node with NLOS Anchors[C]//ICWMC 2013,The Ninth International Conference on Wireless and Mobile Communications. Nice:IEEE,2013:25-30.

[14]Ren X,Gao C,Xi Y. A Node Localization Algorithm Based on Simple Particle Swarm Optimization in Wireless Sensor Networks[J]. Journal of Computational Information Systems,2013,9(22):9203-9210.

[15]Kulkarni R V,Venayagamoorthy G K. Particle Swarm Optimization in Wireless-Sensor Networks:A Brief Survey[J]. Systems,Man,and Cybernetics,Part C:Applications and Reviews,IEEE Transactions on,2011,41(2):262-267.

丁海強(1991-),男,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)定位算法,dinghaiqiang666@163.com;

莊華亮(1967-),男,博士,講師,從事智能系統(tǒng)、無線傳感網(wǎng)絡(luò)方面的研究,zhuanghl@zjut.edu.cn;

何熊熊(1965-),男,博士,教授,從事控制理論與應(yīng)用、信號處理等方面的研究,hxx@zjut.edu.cn。

LocalizationinWSNBasedonMaximumLikelihoodEstimationwithNegativeConstraint*

DINGHaiqiang,QIGuangkuai,ZHUANGHualiang*,HEXiongxiong

(College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China)

In order to improve the accuracy of localization in WSN(wireless sensor network)based on RSSI(Received Signal Strength Indicator),a maximum likelihood estimation approach with negative constraints to realize the localization of the unknown nodes is proposed. If there is no communication link between anchor node and unknown node,the negative constraints can be employed to improve the localization accuracy. The main work can be divided into three parts:firstly,the distance based on RSSI from the nodes is measured. Secondly,a series of positive and negative constrains are combined to build the modeling using the maximum likelihood estimation. Finally,particle swarm optimization is employed to find the optimal position. The simulation results show that the proposed approach outperforms some existing localization algorithm without negative constrains.

wireless sensor network;negative constrains;maximum likelihood estimation;localization;particle swarm optimization

項目來源:浙江省科技廳重大專項項目(C13011);浙江省科技廳公益技術(shù)研究項目(2013C33069)

2014-06-23修改日期:2014-09-12

10.3969/j.issn.1004-1699.2014.11.019

TP393

:A

:1004-1699(2014)11-1545-06