王山　馮鋒　王洪偉

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

關鍵詞：WSN；三維定位；RSSI；估計位置過濾；DBSCAN

中圖分類號：TP393 文獻標識碼：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)技術的迅猛發(fā)展，無線傳感網(wǎng)絡（WSN）迅速成為21世紀最具影響力的技術之一[1]，由于無線傳感網(wǎng)絡綜合了傳感技術、網(wǎng)絡傳輸技術、無線通訊技術、無線定位技術、數(shù)據(jù)融合技術、嵌入式技術等多種技術，使得WSN成為當今研究的熱點。而無線傳感節(jié)點的定位是支撐無線傳感網(wǎng)絡的核心技術[2]，在目標定位、目標跟蹤、地理信息獲取等方面發(fā)揮著巨大作用，因此對無線傳感網(wǎng)絡定位算法的研究具有重要的意義。

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

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

2 相關研究

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

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

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

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

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

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

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

3 基于估計位置過濾的改進定位算法

3.1 估計位置過濾

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

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

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

DBSCAN具體算法描述如下：

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

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

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

（4）重復步驟1）～3），直到所有對象都歸入了某個簇或標記為噪聲。

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

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

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

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

3.2 改進后的定位算法

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

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

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

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

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

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

3.3定位誤差

定位誤差公式：

4 仿真試驗

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

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

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

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

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

4 總結

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

參考文獻：

[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.