基于距離區(qū)間概率測距的無線傳感器網(wǎng)絡(luò)定位算法研究

胡良梁

(重慶第二師范學(xué)院，重慶 400067)

1 概述

無線傳感器網(wǎng)絡(luò)具有自組織、分布式、多跳性等特性，能夠?qū)崿F(xiàn)傳感數(shù)據(jù)的采集、傳輸及加工，目前在軍事、農(nóng)業(yè)及工業(yè)上有著廣泛的應(yīng)用。無線傳感器網(wǎng)絡(luò)由大量節(jié)點(diǎn)構(gòu)成，其節(jié)點(diǎn)的位置信息至關(guān)重要。受規(guī)模及成本的限制，網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)的位置信息未知，未知節(jié)點(diǎn)需要利用測距模型或邏輯跳距來測量相鄰節(jié)點(diǎn)間的距離，再結(jié)合定位技術(shù)實(shí)現(xiàn)自身位置的獲取。

測距技術(shù)根據(jù)測量原理可以分為物理測距和邏輯測距，物理測距是通過輔助設(shè)備來測量節(jié)點(diǎn)間的距離，邏輯測距是用跳數(shù)來表示節(jié)點(diǎn)間的距離。常用的物理測距技術(shù)包括三種：接收信號強(qiáng)度指示法(RSSI)[1]、基于到達(dá)時(shí)間的測距方法(TOA）[2]、到達(dá)時(shí)間差法(TDOA)[3]。RSSI（Received Signal Strength Indicator）是基于信號強(qiáng)度衰減的測距方法，通過模型將節(jié)點(diǎn)間信號衰減值轉(zhuǎn)換成節(jié)點(diǎn)間距離，該方法不需要額外的硬件便可實(shí)現(xiàn)。通常RSSI測距模型是基于經(jīng)驗(yàn)的測距模型，在實(shí)際應(yīng)用中，信號受障礙物、反射、多徑傳播等影響，基于經(jīng)驗(yàn)的測距模型中RSSI與距離映射存在多值問題，導(dǎo)致測距會存在較大的誤差。本文利用基于距離區(qū)間概率的RSSI測距方法來消除多值問題，提高測距模型的測量精度，并減少定位算法的定位誤差。

2 相關(guān)工作

2.1 基于經(jīng)驗(yàn)的測距模型

大量的實(shí)驗(yàn)測試得出，信號強(qiáng)度衰減與距離存在一定的相關(guān)性。基于經(jīng)驗(yàn)的測距模型如下：

其中Δ0為參考距離，一般取Δ0=1；P0表示節(jié)點(diǎn)離發(fā)射節(jié)點(diǎn)Δ0處的信號強(qiáng)度值；np為環(huán)境影響因子，其值依賴于部署的環(huán)境，一般取3～5；dkl表示相鄰節(jié)點(diǎn)k，l之間的距離；Pkl表示相鄰節(jié)點(diǎn)k，l之間的信號強(qiáng)度值。考慮到實(shí)際環(huán)境中信號傳播會受環(huán)境、天氣、障礙物等影響，在傳播模型上引入服從正態(tài)分布的隨機(jī)變量Xσ，如式(2)所示。

基于經(jīng)驗(yàn)的測距模型簡單實(shí)用，但在實(shí)際的傳播過程中信號易受環(huán)境、天氣、障礙物等影響，RSSI與距離d之間并非一一映射關(guān)系，會存在某一距離下存在多個(gè)RSSI值，因此基于經(jīng)驗(yàn)的測距模型建立的＜RSSI，d＞的對應(yīng)關(guān)系存在較大的誤差。

2.2 基于距離區(qū)間概率的測距模型

為了解決基于經(jīng)驗(yàn)的傳播模型在實(shí)際應(yīng)用中存在的多值問題，提高測距模型的測距精度，文獻(xiàn)[4]提出了一種基于區(qū)間概率的測距模型。測距模型分兩個(gè)階段：(1)離線測量階段；(2)在線測量階段。

離線測量階段通過實(shí)驗(yàn)建立起RSSI值與距離的映射＜Rk，Dk＞，其中Rk為實(shí)驗(yàn)測量中某個(gè)RSSI值，Dk是與之對應(yīng)的距離值的集合，利用貝葉斯公式計(jì)算RSSI值為Rk時(shí)節(jié)點(diǎn)位于各個(gè)測量點(diǎn)的概率，將RSSI值與距離的映射＜Rk，Dk＞擴(kuò)展為＜Rk，Dk＝{d1(Pk1)，d2(Pk2)，…，dn(Pkn)}＞，則最終得到RSSI值為Rk對應(yīng)的映射距離可通過式（3）計(jì)算，并將Rk和d的映射關(guān)系存到映射關(guān)系數(shù)據(jù)庫中。

在線測量階段在某個(gè)位置上測量多個(gè)RSSI值，并將這些值與映射關(guān)系數(shù)據(jù)庫中的能量值進(jìn)行比較，取相等或者差值最小值的平均值作為移動節(jié)點(diǎn)的最終位置。

2.3 MDS-MAP定位算法[5]

設(shè)m維空間中有N個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)i的坐標(biāo)xi=(xi1，xi2，…，xim),節(jié)點(diǎn)j的坐標(biāo)xj=(xj1，xj2，…，xjm)，dij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離，則N個(gè)節(jié)點(diǎn)的距離矩陣為D，如式（4）所示。

對B進(jìn)行奇異值分解為B=VΛVT的形式，其中Λ是矩陣B的特征值由大到小組成的對角線矩陣，V是特征值對應(yīng)的特征向量組成的正交矩陣，取Λ前k個(gè)特征值構(gòu)成Λk，取V前k個(gè)特征向量Vk，B可以表示成：

由式（5）和（6）可以得出k維空間坐標(biāo)解：Xk=VkΛ1/2k，Xk為節(jié)點(diǎn)相對坐標(biāo)，結(jié)合錨節(jié)點(diǎn)的坐標(biāo)信息，可以將Xk轉(zhuǎn)換成節(jié)點(diǎn)絕對坐標(biāo)。

3 基于距離區(qū)間概率測距MDS-MAP定位算法

本文提出了一種改進(jìn)的MDS-MAP定位算法，該算法利用基于距離區(qū)間概率測距方法消除傳統(tǒng)測距模型中存在的多值問題。該算法包括如下步驟：（1）基于距離區(qū)間概率測距階段；（2）距離矩陣D的建立；（3）對距離矩陣D采用MDSMAP方法求出各節(jié)點(diǎn)的絕對坐標(biāo)。

第一階段：基于距離區(qū)間概率測距

首先通過實(shí)驗(yàn)離線建立Rk和d的映射關(guān)系數(shù)據(jù)庫。將節(jié)點(diǎn)通信半徑R分成若干等分，在每個(gè)距離點(diǎn)上收集n個(gè)RSSI值，根據(jù)式（3），建立Rk和d的映射關(guān)系數(shù)據(jù)庫。網(wǎng)絡(luò)部署并初始化完成后，節(jié)點(diǎn)根據(jù)在線測量方法，將接收到的RSSI轉(zhuǎn)化成節(jié)點(diǎn)間的最終距離。

第二階段：對鄰居節(jié)點(diǎn)的距離矩陣D'利用最短路徑算法求出任意兩個(gè)節(jié)點(diǎn)之間的距離，建立距離矩陣D。

第三階段：對第二階段中建立的距離矩陣D利用MDSMAP方法，獲得k維網(wǎng)絡(luò)的相對坐標(biāo)系統(tǒng)，一般取k=2或k=3，結(jié)合錨節(jié)點(diǎn)坐標(biāo)信息，將相對坐標(biāo)系統(tǒng)轉(zhuǎn)化成絕對坐標(biāo)系統(tǒng)。

4 算法仿真驗(yàn)證

算法仿真是在MATLAB環(huán)境下進(jìn)行。如圖1所示，250個(gè)節(jié)點(diǎn)隨機(jī)部署在一個(gè)100m*100m的方形區(qū)域里，其中含有5個(gè)錨節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑為R=15m,錨節(jié)點(diǎn)用*來表示，未知節(jié)點(diǎn)用小圓圈來表示。定位算法性能用平均定位誤差來評價(jià)，其定義為未知節(jié)點(diǎn)真實(shí)坐標(biāo)到估計(jì)坐標(biāo)的歐氏距離與通信半徑的比值。假設(shè)未知節(jié)點(diǎn)經(jīng)定位后的估計(jì)坐標(biāo)為(xe，ye)，其真實(shí)坐標(biāo)為(xt，yt)，則單個(gè)節(jié)點(diǎn)定位誤差為平均定位誤差（其中(n-m)表示未定位節(jié)點(diǎn)的個(gè)數(shù)）。改進(jìn)的MDS-MAP定位算法測距環(huán)節(jié)中的離線實(shí)驗(yàn)階段，將節(jié)點(diǎn)通信半徑為R分成30等分，并在每個(gè)距離點(diǎn)上采集100個(gè)RSSI。圖2給出了改進(jìn)的MDS-MAP定位算法與基于經(jīng)驗(yàn)的傳播模型（np=4）的MDS-MAP定位算法在不同通信半徑下的對比分析圖，從圖中可以得出在不同的通信半徑下，本文提出的改進(jìn)算法的定位精度均優(yōu)于基于經(jīng)驗(yàn)的傳播模型MDS-MAP算法。

圖1 方形區(qū)域鄰居關(guān)系圖

圖2 不同通信半徑下定位誤差對比分析圖

5 結(jié)論

傳統(tǒng)的MDS-MAP算法在測距階段當(dāng)信號存在干擾或障礙物時(shí)，節(jié)點(diǎn)間的RSSI值與距離d存在多值問題，導(dǎo)致基于經(jīng)驗(yàn)傳播模型存在較大的測距誤差。本文提出了一種改進(jìn)的MDS-MAP定位算法，在測距階段利用基于距離區(qū)間概率測距，消除RSSI值與距離d存在多值問題，提高了測距模型的抗干擾能力。改進(jìn)算法提高了RSSI測量值的精度，進(jìn)而提高了定位算法的精度。

[1]Bahl Paramvir,Padmanabhan Venkata N.RADAR:an inbuilding RF-based user Location and tracking system[A].Proceedings-IEEE INFOCOM[C],Tel Aviv,Isr,2000:775-784.

[2]L.Girod and D.estrin.Robust range estimation using acoustic and multimodal sensing[A].IEEE International Conference on Intelligent Robots and Systems[C],Maui,Hl,United states,2001:1312-1320.

[3]X.Cheng,T.A,G.Xue,D.Chen.TPS:A time-based Positioning scheme for outdoor Wireless sensor networks[A].Proceedings-IEEE INFOCOM[C],HongKong,China,2004:2685-2696.

[4]王媛媛,官娜娜.基于距離區(qū)間概率加權(quán)的RSSI測距方法[J].電子科技大學(xué)學(xué)報(bào),2013.6（42）：862-868.

[5]Shang Y，Ruml W，Zhang Y.Localization from connectivity in sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2004，15（11）：961-974.