基于RSSI的三維空間定位算法研究

王山　馮鋒　王洪偉

摘要：在無線傳感網(wǎng)絡(luò)（WSN）的三維定位的過程中，由于實(shí)際環(huán)境的復(fù)雜性，會(huì)在定位過程中產(chǎn)生不穩(wěn)定的接收信號強(qiáng)度（RSSI），同時(shí)還會(huì)導(dǎo)致無線傳感網(wǎng)絡(luò)中的未知節(jié)點(diǎn)產(chǎn)生不可靠定位數(shù)據(jù)，這些都會(huì)影響定位的精度。據(jù)此，本文提出了一種位置過濾算法，該算法首先利用高斯過濾模型對RSSI值進(jìn)行過濾得到穩(wěn)定的RSSI值，然后使用四面體質(zhì)心算法計(jì)算得到未知節(jié)點(diǎn)的估計(jì)位置，最后結(jié)合DBSCAN算法對得到的估計(jì)位置進(jìn)行過濾，從而剔除計(jì)算過程中獲得的不可靠數(shù)據(jù)。本算法通過與傳統(tǒng)的定位算法進(jìn)行仿真對比，結(jié)果表明，本算法有效地提高了定位精度，對特定條件下的三維空間定位工程具有較強(qiáng)的借鑒意義。

關(guān)鍵詞：WSN；三維定位；RSSI；估計(jì)位置過濾；DBSCAN

中圖分類號：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1009-3044（2016）19-0221-04

Study of Three-dimensional Location Space Algorithm Based on RSSI

WANG Shan1， FENG Feng1， WANG Shong-wei2

（1.College of Mathematics and Computer Science， Ningxia University， Yinchuan 750000， China； 2.Engineering University of CAPF， Xian 710086， China）

Abstract： In the process of wireless sensor networks （WSN） positioned in three dimensional localization， due to the complexity of the physical environment， it will produce an unstable Received Signal Strength Indication （RSSI） during positioning， but also lead to unknown wireless sensor networks node generates unreliable positioning data， which will affect the positioning accuracy. Hereby， this paper proposes a position filtering algorithm， the proposed algorithm first using gauss filter model to filter the RSSI value and get the stability of the RSSI values， and then use the tetrahedron centroid algorithm to calculate the estimates of the unknown node position， finally combining with DBSCAN algorithm to filter the estimated location， thus to reject the unreliable data obtained from the calculation. Compared with the traditional positioning algorithm， the results show that the algorithm can effectively improve the positioning accuracy， and it can be used for reference in the three-dimensional space localization project under certain conditions.

Key words： WSN； three dimensional localization；RSSI； filter the estimated location；DBSCAN

1 引言

隨著物聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，無線傳感網(wǎng)絡(luò)（WSN）迅速成為21世紀(jì)最具影響力的技術(shù)之一[1]，由于無線傳感網(wǎng)絡(luò)綜合了傳感技術(shù)、網(wǎng)絡(luò)傳輸技術(shù)、無線通訊技術(shù)、無線定位技術(shù)、數(shù)據(jù)融合技術(shù)、嵌入式技術(shù)等多種技術(shù)，使得WSN成為當(dāng)今研究的熱點(diǎn)。而無線傳感節(jié)點(diǎn)的定位是支撐無線傳感網(wǎng)絡(luò)的核心技術(shù)[2]，在目標(biāo)定位、目標(biāo)跟蹤、地理信息獲取等方面發(fā)揮著巨大作用，因此對無線傳感網(wǎng)絡(luò)定位算法的研究具有重要的意義。

目前，無線傳感網(wǎng)絡(luò)定位在二維平面中的應(yīng)用已非常成熟，但隨著社會(huì)的發(fā)展，三維定位需求日益成明顯，三維定位使得傳感器節(jié)點(diǎn)呈現(xiàn)出立體分布，而非平面分布的特點(diǎn)，因此在平面上的定位算法已不能滿足空間場景的定位需求。為了解決上述問題，人們提出了基于三維的節(jié)無線傳感網(wǎng)絡(luò)定位算法。無線傳感器網(wǎng)絡(luò)中的定位方法較多，可以根據(jù)數(shù)據(jù)采集和數(shù)據(jù)處理方式的不同來進(jìn)行分類。在數(shù)據(jù)采集方式上。算法根據(jù)需要對采集的數(shù)據(jù)有所側(cè)重，比如角度、時(shí)間、周圍節(jié)點(diǎn)信息等，其目的是采集與定位相關(guān)的數(shù)據(jù)。在數(shù)據(jù)處理方面，不管數(shù)據(jù)時(shí)被自身節(jié)點(diǎn)處理還是上傳到其他設(shè)備上處理，其結(jié)果是將數(shù)據(jù)轉(zhuǎn)換為定位坐標(biāo)，從而完成定位。 其中依據(jù)距離測量與否算法可劃分為兩大類：基于測距的定位和與距離無關(guān)的定位。目前，在測距的定位算法中基于接收信號強(qiáng)度（RSSI）的定位是研究的熱點(diǎn)。相對于與距離無關(guān)的定位方法，基于RSSI的定位方法增添了額外的通信鏈路質(zhì)量信息，并且獲取簡單，對于定位精度的提高具有一定的作用。

RSSI通過比較發(fā)射結(jié)點(diǎn)發(fā)送信號強(qiáng)度和接收結(jié)點(diǎn)接收信號的強(qiáng)度，再考慮信號在傳播過程中的損失，使用理論或者經(jīng)驗(yàn)的信號傳播模型將傳播損耗轉(zhuǎn)化為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的距離[3]。在實(shí)際應(yīng)用環(huán)境中，由于復(fù)雜的環(huán)境中的多徑干擾，非視線關(guān)系等因素，該方法的定位精度不高。但由于這種基于RSSI的測距技術(shù)，具有方法簡單、成本低、效率高、設(shè)備少、距離遠(yuǎn)等優(yōu)點(diǎn)，因此，許多定位算法都結(jié)合了RSSI技術(shù)[4]。

2 相關(guān)研究

基于RSSI理論的研究已經(jīng)比較成熟，根據(jù)無線電傳播理論，無線電信號在傳播過程中會(huì)有能量損耗，這種損耗與無線電傳播路徑相關(guān)，測距模型正是基于這種相關(guān)性從而得出待測節(jié)點(diǎn)到參考點(diǎn)之間的距離，在實(shí)際環(huán)境中，由于多徑衰落、反射以及擾射、不規(guī)則傳播等因素，使得模型比較復(fù)雜，同時(shí)使得定位誤差較大。目前普遍使用的統(tǒng)計(jì)模型[5]如下：

式1中d為距信號源的距離，單位一般為km；d0為參考距離，P（d）為在距離d處的信號強(qiáng)度值，np為路徑衰減因子，一般取值為2～4，環(huán)境不同取值不同。室內(nèi)環(huán)境通常取1.4～1.8，P0是在參考距離d0處的信號強(qiáng)度（dBm）。由于式1參考模型的理論環(huán)境與復(fù)雜的實(shí)際環(huán)境有較大的差別，使得無線電傳播路徑損耗在一定的程度上與理論值相比并不吻合，這就使得實(shí)際測量存值存在誤差。通?；赗SSI技術(shù)的定位機(jī)制使用各種算法來減少測距誤差對定位的影響，其中包括多次測量、循環(huán)定位求精等算法。

由于無線傳感網(wǎng)分布的地理位置及環(huán)境復(fù)雜多變，無線信號會(huì)受到環(huán)境的各種因素影響，導(dǎo)致接收節(jié)點(diǎn)接收到的信號，并不是全部對定位有幫助，有時(shí)會(huì)增大誤差，所以對接收的信號進(jìn)行預(yù)處理就顯得很有必要了。通過RSSI距離模型可知，當(dāng)未知節(jié)點(diǎn)距離錨節(jié)點(diǎn)越近，接收到的RSSI值波動(dòng)越?。ㄗ畲笾岛妥钚≈抵钤叫。?，說明由RSSI值計(jì)算得到的距離越接近實(shí)際距離。當(dāng)未知節(jié)點(diǎn)距離錨節(jié)點(diǎn)越遠(yuǎn)，由于實(shí)際環(huán)境的多徑效應(yīng)使得測得的RSSI值波動(dòng)變大，導(dǎo)致誤差也大。為了消除較大波動(dòng)值對定位的影響，我們首先將周圍錨節(jié)點(diǎn)的RSSI值聚集起來形成一個(gè)數(shù)據(jù)集，并且從大到小排好序。數(shù)據(jù)集形式如下：

我們從數(shù)據(jù)集中選取RSSI值較大的錨節(jié)點(diǎn)，進(jìn)行多次RSSI值采集，記錄，結(jié)合高斯濾波模型，舍去波動(dòng)較大的RSSI值，最后對于收集到的N個(gè)該錨節(jié)點(diǎn)RSSI值取算數(shù)平均數(shù)作為該錨節(jié)點(diǎn)的最終RSSI值。表達(dá)式如下：

在進(jìn)行定位時(shí)，如果待測節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離已知，則至少需要4個(gè)不位于同一個(gè)平面內(nèi)的參考節(jié)點(diǎn)才能唯一確定待測節(jié)點(diǎn)的坐標(biāo)值，否則無法進(jìn)行定位[6]。我們假設(shè)這4個(gè)錨節(jié)點(diǎn)的坐標(biāo)為Pi=（xi，yi，zi），i=1，2，3，4；待測節(jié)點(diǎn)到4個(gè)錨節(jié)點(diǎn)的距離為di，i=1，2，3，4，根據(jù)三維空間兩點(diǎn)間距離公式有：

方程組中四個(gè)方程三個(gè)未知量，那么就可以確定未知節(jié)點(diǎn)N（x，y，z）的坐標(biāo)：

根據(jù)以上理論基礎(chǔ)，許多學(xué)者對三維定位方法做了深入的研究。例如，文獻(xiàn)[7]提出了坐標(biāo)四面體質(zhì)心定位算法，該算法比傳統(tǒng)算法定位精度要高。文獻(xiàn)[8]提出了一種利用四面體質(zhì)心算法替換三維APIT算法的網(wǎng)格掃描法。文獻(xiàn)[9]提出了一種基于多次測量提高定位精度的思想等。但是目前的這些研究對于由客觀或主觀因素會(huì)產(chǎn)生不可靠數(shù)據(jù)的情況，都未涉及，因此，本文提出一種基于估計(jì)位置進(jìn)行過濾的改進(jìn)定位算法。

3 基于估計(jì)位置過濾的改進(jìn)定位算法

3.1 估計(jì)位置過濾

在三維空間定位過程中通常需要布置較多的錨節(jié)點(diǎn)，所以對于某個(gè)待定節(jié)點(diǎn)周圍存在多個(gè)1跳參考點(diǎn)，由相關(guān)研究的理論可知對于任意四個(gè)錨節(jié)點(diǎn)都能計(jì)算得到一個(gè)估計(jì)位置，所以在計(jì)算的結(jié)果中會(huì)有多個(gè)估計(jì)位置，譬如，當(dāng)周圍環(huán)境中有10個(gè)錨節(jié)點(diǎn)時(shí)，取其中4個(gè)作為參考節(jié)點(diǎn)，那么就會(huì)有C104=210種取法。對于位置的估計(jì)，由于存在一些主觀因素和客觀因素，如選取節(jié)點(diǎn)不合理、數(shù)據(jù)傳輸錯(cuò)誤等。存在某些明顯已知的錯(cuò)誤，使得這些估計(jì)位置對定位精度影響較大，所以對這些位置需要屏蔽過濾，以提高定位精度。對于多組估計(jì)位置，如果很多估計(jì)位置比較集中，而少數(shù)估計(jì)位置距離群體比較遠(yuǎn)，則可以認(rèn)為這幾個(gè)少數(shù)位置是不可靠的，因此可以剔除掉，其他的位置則認(rèn)為是可靠位置點(diǎn)。如圖1所示，假如對一個(gè)位置估計(jì)得到如下六個(gè)估計(jì)位置（A，B，C，D，E，F(xiàn)），由圖中可以看出A，B，C，D，E五個(gè)位置較為集中，而F這個(gè)位置距離群體較遠(yuǎn)，如果將這六個(gè)點(diǎn)求平均值作為未知節(jié)點(diǎn)的最終估計(jì)位置的話，會(huì)造成誤差較大，因此將F剔除，僅對A，B，C，D，E五個(gè)點(diǎn)進(jìn)行算術(shù)平均運(yùn)算，結(jié)果作為未知節(jié)點(diǎn)的估計(jì)位置。

其中對于只有兩個(gè)估計(jì)位置的點(diǎn)不采取位置過濾，取這兩個(gè)估計(jì)位置連線的中點(diǎn)作為節(jié)點(diǎn)的最終估計(jì)位置。

對于估計(jì)位置較多的，本文采用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法，DBSCAN[10]算法是一種基于密度的聚類算法[11，12]，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，所以該算法可以有效識(shí)別噪聲，即不可靠位置。

DBSCAN具體算法描述如下：

（1）檢測數(shù)據(jù)庫中尚未檢查過的對象p，如果p為被處理（歸為某個(gè)簇或者標(biāo)記為噪聲），則檢查其鄰域，若包含的對象數(shù)不小于，建立新簇C，將中所有點(diǎn)加入C；

（2）對C中所有尚未被處理的對象q，檢查其鄰域，若中至少包含個(gè)對象，則將中未歸入任何一個(gè)簇的對象加入C；

（3）重復(fù)步驟2），繼續(xù)檢查C中未處理的對象，知道沒有新的對象加入當(dāng)前簇C；

（4）重復(fù)步驟1）～3），直到所有對象都?xì)w入了某個(gè)簇或標(biāo)記為噪聲。

輸入數(shù)據(jù)：數(shù)據(jù)對象集合D，半徑Eps，密度閾值MinPts

輸出數(shù)據(jù)：聚類C

從算法中我們可以看出DBSCAN算法通過檢查數(shù)據(jù)庫中每個(gè)點(diǎn)的Eps-鄰域來尋找聚類。如果一個(gè)點(diǎn)P的Eps-鄰域包含多于MinPts個(gè)點(diǎn)，則創(chuàng)建一個(gè)以P作為核心對象的新簇。然后，DBSCAN反復(fù)地尋找從這些核心對象直接密度可達(dá)的對象并加入該簇，直到?jīng)]有新的點(diǎn)可以被添加，該過程結(jié)束。

由于該算法可以有效地去除噪聲即不可靠數(shù)據(jù)，因此DBSCAN算法能夠很好的應(yīng)用到空間位置過濾中去除空間不可靠數(shù)據(jù)。

3.2 改進(jìn)后的定位算法

1）錨節(jié)點(diǎn)周期性發(fā)送自身信息：節(jié)點(diǎn)ID、自身位置信息。

2）待測節(jié)點(diǎn)接收其通訊范圍內(nèi)的所有節(jié)點(diǎn)的信息，并記錄他們的RSSI值，建立從大到小的RSSI數(shù)據(jù)集，選取通訊RSSI值較大的錨節(jié)點(diǎn)進(jìn)行多次通訊測值，并運(yùn)用高斯濾波，舍去波動(dòng)較大的RSSI值，得到N組 RSSI值取其算術(shù)平均值：

作為該錨節(jié)點(diǎn)的最終RSSI值。

3）如果未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)的個(gè)數(shù)N<=3，則執(zhí)行5）。否則隨機(jī)選擇一組錨節(jié)點(diǎn)組成四面體，并根據(jù)三維APIT算法判斷未知節(jié)點(diǎn)是否在四面體中。如果不在則舍棄，如果在則記錄這組錨節(jié)點(diǎn)并重復(fù)該過程，直到選取次數(shù)大于一個(gè)閥值M。

4）由3）得到四面體后，運(yùn)用四邊測量算法來對集合中的所有組合計(jì)算坐標(biāo)位置。對計(jì)算得到N組坐標(biāo)值過濾，對于只有兩個(gè)估計(jì)位置的點(diǎn)不采取位置過濾，取這兩個(gè)估計(jì)位置連線的中點(diǎn)作為節(jié)點(diǎn)的最后估計(jì)位置。對于估計(jì)位置較多的點(diǎn)，采用DBSCAN算法，選取集合最大的所有數(shù)據(jù)進(jìn)行計(jì)算平均值作為最終坐標(biāo)估計(jì)值。

5）若未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)個(gè)數(shù)N<=3或者四面體集合為空，則對所有錨節(jié)點(diǎn)采用RSSI均值加權(quán)質(zhì)心算法來進(jìn)行未知節(jié)點(diǎn)估計(jì)。對于接收到P個(gè)錨節(jié)點(diǎn)信號，相應(yīng)的RSSI的值為R1，R2，...，Rp，則第i個(gè)錨節(jié)點(diǎn)的加權(quán)系數(shù)為那么RSSI均值加權(quán)算法估計(jì)坐標(biāo)為：

3.3定位誤差

定位誤差公式：

4 仿真試驗(yàn)

為了比較本文改進(jìn)的定位算法和傳統(tǒng)定位算法的性能，利用MATLAB建立了一100m×100m×100m的仿真環(huán)境，錨節(jié)點(diǎn)均勻地分布在這個(gè)范圍內(nèi)，在數(shù)據(jù)中添加方差為20、均值為3的隨機(jī)噪聲，用來模擬現(xiàn)實(shí)環(huán)境的影響。500個(gè)定位結(jié)果是在相同的環(huán)境下運(yùn)行50次試驗(yàn)的平均值，部分區(qū)域仿真結(jié)果對比如圖3、圖4所示：

由圖3和圖4的仿真結(jié)果對比可以看出，由于在實(shí)際應(yīng)用的環(huán)境中會(huì)出現(xiàn)節(jié)點(diǎn)異常或者環(huán)境異常帶來的不可靠數(shù)據(jù)，會(huì)對系統(tǒng)定位精度產(chǎn)生影響，我們通過對采集的RSSI值過濾和估計(jì)位置進(jìn)行過濾，定位結(jié)果要比未進(jìn)行位置過濾和RSSI值高斯過濾的誤差要小，提高了定位精度。

如圖5所示，在錨節(jié)點(diǎn)小于10個(gè)的時(shí)候本文算法定位精度明顯優(yōu)于傳統(tǒng)算法，這是因?yàn)殄^節(jié)點(diǎn)較少時(shí)環(huán)境誤差對定位精度影響較大，造成了傳統(tǒng)算法的定位不精確，而本文所提出的改進(jìn)算法具有明顯的優(yōu)點(diǎn)。但隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加兩種算法的精度都在不斷提高，這是因?yàn)殡S著錨節(jié)點(diǎn)的增加，由于最后取幾何均值使得環(huán)境誤差數(shù)據(jù)對總的定位結(jié)果影響較少，所以定位精度就得到了提高。

圖6給出的是定位誤差隨通訊距離變化的趨勢。由圖中可知隨著通訊距離的增加，傳統(tǒng)算法和本文算法的定位誤差都減小。因?yàn)樵黾庸?jié)點(diǎn)的通訊距離后，會(huì)使距離估計(jì)更加接近節(jié)點(diǎn)間的歐氏距離。

由以上結(jié)果分析可知，在定位過程中節(jié)點(diǎn)的噪聲數(shù)據(jù)會(huì)影響定位的精度，本文在質(zhì)心定位算法的基礎(chǔ)上先通過對RSSI值進(jìn)行高斯過濾從而優(yōu)化了采集的RSSI值，保證了入口數(shù)據(jù)的準(zhǔn)確性和穩(wěn)定性。然后對計(jì)算結(jié)果進(jìn)行基于DBSCAN算法的估計(jì)位置過濾，通過仿真結(jié)果可以看出該算法有效的減少了不可靠數(shù)據(jù)對定位的影響，提高了定位精度。

4 總結(jié)

本文在研究了傳統(tǒng)的三維定位算法的基礎(chǔ)上，提出了一種估計(jì)位置過濾算法。該算法通過高斯過濾模型對采集的RSSI的值進(jìn)行過濾得到穩(wěn)定的RSSI值，然后對待定位的節(jié)點(diǎn)進(jìn)行估計(jì)位置過濾，去除了在定位過程中由于主觀或者客觀因素帶來的不可靠位置，減少了其對定位精度的影響。文章通過仿真對比了本文算法和傳統(tǒng)算法在定位精度上的優(yōu)劣，由對比結(jié)果可知本文算法在定位精度上有了明顯的提高，能夠有效的減少實(shí)際應(yīng)用中隨機(jī)噪聲對定位的影響，該算法在三維定位中有著較大的應(yīng)用潛力。

參考文獻(xiàn)：

[1] SUOMELA J. Computational complexity of relay placement in sensor networks[J]. Lecture Notes in Computer Science， 2006， 3831：521-529.

[2] KIM S， KO J G，YOON J， et al. Multiple-objective metric for placing multiple base stations in wireless sensor networks[A]. Proc of the 2rd International Symposium on Wireless Pervasive Computing[C].Pis-cataway，USA，2007：627-631.

[3] Zhang Jie， Wu Ling-xi，Tang Zhi-jun. Ranging Method and Accuracy Analysis Based on RSSI of Wireless SensorNetwork[J].Telcommunication Engineering，2010，50（4）：83-87

[4] WU Jie，F(xiàn)ENG Feng，DING Zhi-yi Research on coal mine underground localization algorithm based on integration of RFID and WSN[J].Computer Engineering And Design.2014（7）：2278-2282.

[5] SHEN X， WANG Z， JIANG P， et al. Connectivity and RSSI based localization scheme for wireless sensor networks[J]. Lecture Notes in Computer Science， 2005， 3645（2）：578-587.

[6] Laitinen E， Lohan E S， Talvitie J， et al. Access point significance measures in WLAN-basedlocation[C]//Positioning Navigation and Communication （WPNC）， 2012 9th Workshop on. IEEE，2012：24-29.

[7] Chen Hong-yang， Huang Pei， Martins M. Novel Centroid Localization Algorithm for Three Dimensional Wireless Sensor Networks[C]//WiCOM'08 4th International Conference on Wireless C'ommunications，Networking and Mobile Computing. 2008：1-4

[8] Liu Zhuang，F(xiàn)ang Zhi-yi，Ren Nai-ji. A New Range-Free Localization Algorithm Based on Annulus Intersection and Grid Scan in Wireless Sensor Networks [J].Journal of Information and Computational Science，2012，9（4）：831-841

[9] VIANI F， LIZZI L， ROCCA P， et al. Object tracking through RSSI measurements in wireless sensor networks[J]. Electronics Letters， 2008， 44（10）： 653-654.

[10] ESTER M， KRIEGEL H， SANDER J， et al. A den-sity-based algorithm for discovering clusters in largespatial databases with noise[C]// Proc of the 19962nd Int' l Conf on Knowledge Discovery and DataMining.Portland： AAAI Press， 1996：226-231.

[11] QIAN Wei-ning， GONG Xue-qing， Ao Ying-zhou.Clustering in very large databases based on distanceand density[J]. Journal of Computer Science and Technology， 2003， 18（1）： 67-76.

[12] ZHOU Shui-Geng，ZHOU Ao-Ying，CAO Jing.A fast densite-based clustering algorithm[J].Journal Of Computer Research And Development.2000，37（11）：1287-1292.