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

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

2、法有效地提高了定位精度，對(duì)特定條件下的三維空間定位工程具有較強(qiáng)的借鑒意義。關(guān)鍵詞：wsn；三維定位；rssi；估計(jì)位置過(guò)濾；dbscan：tp393 ：a ：1009-3044（2016）19-0221-04study of three-dimensional location space algorithm based on rssiwang shan1， feng feng1， wang shong-wei2（1.college of mathematics and computer science， ningxia university， yinchuan 750000， china；

3、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，

4、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 o

5、f 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 positi

6、oning 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；dbsc

7、an1 引言隨著物聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，無(wú)線傳感網(wǎng)絡(luò)（wsn）迅速成為21世紀(jì)最具影響力的技術(shù)之一1，由于無(wú)線傳感網(wǎng)絡(luò)綜合了傳感技術(shù)、網(wǎng)絡(luò)傳輸技術(shù)、無(wú)線通訊技術(shù)、無(wú)線定位技術(shù)、數(shù)據(jù)融合技術(shù)、嵌入式技術(shù)等多種技術(shù)，使得wsn成為當(dāng)今研究的熱點(diǎn)。而無(wú)線傳感節(jié)點(diǎn)的定位是支撐無(wú)線傳感網(wǎng)絡(luò)的核心技術(shù)2，在目標(biāo)定位、目標(biāo)跟蹤、地理信息獲取等方面發(fā)揮著巨大作用，因此對(duì)無(wú)線傳感網(wǎng)絡(luò)定位算法的研究具有重要的意義。目前，無(wú)線傳感網(wǎng)絡(luò)定位在二維平面中的應(yīng)用已非常成熟，但隨著社會(huì)的發(fā)展，三維定位需求日益成明顯，三維定位使得傳感器節(jié)點(diǎn)呈現(xiàn)出立體分布，而非平面分布的特點(diǎn)，因此在平面上的定位算法已不能滿足空間場(chǎng)景的定位需求。

8、為了解決上述問(wèn)題，人們提出了基于三維的節(jié)無(wú)線傳感網(wǎng)絡(luò)定位算法。無(wú)線傳感器網(wǎng)絡(luò)中的定位方法較多，可以根據(jù)數(shù)據(jù)采集和數(shù)據(jù)處理方式的不同來(lái)進(jìn)行分類。在數(shù)據(jù)采集方式上。算法根據(jù)需要對(duì)采集的數(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ù)距離測(cè)量與否算法可劃分為兩大類：基于測(cè)距的定位和與距離無(wú)關(guān)的定位。目前，在測(cè)距的定位算法中基于接收信號(hào)強(qiáng)度（rssi）的定位是研究的熱點(diǎn)。相對(duì)于與距離無(wú)關(guān)的定位方法，基于rssi的定位方法增添了額外的通信鏈路質(zhì)量信息，并且獲

9、取簡(jiǎn)單，對(duì)于定位精度的提高具有一定的作用。rssi通過(guò)比較發(fā)射結(jié)點(diǎn)發(fā)送信號(hào)強(qiáng)度和接收結(jié)點(diǎn)接收信號(hào)的強(qiáng)度，再考慮信號(hào)在傳播過(guò)程中的損失，使用理論或者經(jīng)驗(yàn)的信號(hào)傳播模型將傳播損耗轉(zhuǎn)化為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的距離3。在實(shí)際應(yīng)用環(huán)境中，由于復(fù)雜的環(huán)境中的多徑干擾，非視線關(guān)系等因素，該方法的定位精度不高。但由于這種基于rssi的測(cè)距技術(shù)，具有方法簡(jiǎn)單、成本低、效率高、設(shè)備少、距離遠(yuǎn)等優(yōu)點(diǎn)，因此，許多定位算法都結(jié)合了rssi技術(shù)4。 2 相關(guān)研究基于rssi理論的研究已經(jīng)比較成熟，根據(jù)無(wú)線電傳播理論，無(wú)線電信號(hào)在傳播過(guò)程中會(huì)有能量損耗，這種損耗與無(wú)線電傳播路徑相關(guān)，測(cè)距模型正是基于這種相關(guān)性從而得出待測(cè)節(jié)點(diǎn)

10、到參考點(diǎn)之間的距離，在實(shí)際環(huán)境中，由于多徑衰落、反射以及擾射、不規(guī)則傳播等因素，使得模型比較復(fù)雜，同時(shí)使得定位誤差較大。目前普遍使用的統(tǒng)計(jì)模型5如下：式1中d為距信號(hào)源的距離，單位一般為km；d0為參考距離，p（d）為在距離d處的信號(hào)強(qiáng)度值，np為路徑衰減因子，一般取值為24，環(huán)境不同取值不同。室內(nèi)環(huán)境通常取1.41.8，p0是在參考距離d0處的信號(hào)強(qiáng)度（dbm）。由于式1參考模型的理論環(huán)境與復(fù)雜的實(shí)際環(huán)境有較大的差別，使得無(wú)線電傳播路徑損耗在一定的程度上與理論值相比并不吻合，這就使得實(shí)際測(cè)量存值存在誤差。通?；趓ssi技術(shù)的定位機(jī)制使用各種算法來(lái)減少測(cè)距誤差對(duì)定位的影響，其中包括多次測(cè)量、

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

12、i值較大的錨節(jié)點(diǎn)，進(jìn)行多次rssi值采集，記錄，結(jié)合高斯濾波模型，舍去波動(dòng)較大的rssi值，最后對(duì)于收集到的n個(gè)該錨節(jié)點(diǎn)rssi值取算數(shù)平均數(shù)作為該錨節(jié)點(diǎn)的最終rssi值。表達(dá)式如下：在進(jìn)行定位時(shí)，如果待測(cè)節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離已知，則至少需要4個(gè)不位于同一個(gè)平面內(nèi)的參考節(jié)點(diǎn)才能唯一確定待測(cè)節(jié)點(diǎn)的坐標(biāo)值，否則無(wú)法進(jìn)行定位6。我們假設(shè)這4個(gè)錨節(jié)點(diǎn)的坐標(biāo)為pi=（xi，yi，zi），i=1，2，3，4；待測(cè)節(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é)者對(duì)三維定位方法做了

13、深入的研究。例如，文獻(xiàn)7提出了坐標(biāo)四面體質(zhì)心定位算法，該算法比傳統(tǒng)算法定位精度要高。文獻(xiàn)8提出了一種利用四面體質(zhì)心算法替換三維apit算法的網(wǎng)格掃描法。文獻(xiàn)9提出了一種基于多次測(cè)量提高定位精度的思想等。但是目前的這些研究對(duì)于由客觀或主觀因素會(huì)產(chǎn)生不可靠數(shù)據(jù)的情況，都未涉及，因此，本文提出一種基于估計(jì)位置進(jìn)行過(guò)濾的改進(jìn)定位算法。3 基于估計(jì)位置過(guò)濾的改進(jìn)定位算法3.1 估計(jì)位置過(guò)濾在三維空間定位過(guò)程中通常需要布置較多的錨節(jié)點(diǎn)，所以對(duì)于某個(gè)待定節(jié)點(diǎn)周圍存在多個(gè)1跳參考點(diǎn)，由相關(guān)研究的理論可知對(duì)于任意四個(gè)錨節(jié)點(diǎn)都能計(jì)算得到一個(gè)估計(jì)位置，所以在計(jì)算的結(jié)果中會(huì)有多個(gè)估計(jì)位置，譬如，當(dāng)周圍環(huán)境中有10個(gè)錨

14、節(jié)點(diǎn)時(shí)，取其中4個(gè)作為參考節(jié)點(diǎn)，那么就會(huì)有c104=210種取法。對(duì)于位置的估計(jì)，由于存在一些主觀因素和客觀因素，如選取節(jié)點(diǎn)不合理、數(shù)據(jù)傳輸錯(cuò)誤等。存在某些明顯已知的錯(cuò)誤，使得這些估計(jì)位置對(duì)定位精度影響較大，所以對(duì)這些位置需要屏蔽過(guò)濾，以提高定位精度。對(duì)于多組估計(jì)位置，如果很多估計(jì)位置比較集中，而少數(shù)估計(jì)位置距離群體比較遠(yuǎn)，則可以認(rèn)為這幾個(gè)少數(shù)位置是不可靠的，因此可以剔除掉，其他的位置則認(rèn)為是可靠位置點(diǎn)。如圖1所示，假如對(duì)一個(gè)位置估計(jì)得到如下六個(gè)估計(jì)位置（a，b，c，d，e，f），由圖中可以看出a，b，c，d，e五個(gè)位置較為集中，而f這個(gè)位置距離群體較遠(yuǎn)，如果將這六個(gè)點(diǎn)求平均值作為未知節(jié)點(diǎn)的最

15、終估計(jì)位置的話，會(huì)造成誤差較大，因此將f剔除，僅對(duì)a，b，c，d，e五個(gè)點(diǎn)進(jìn)行算術(shù)平均運(yùn)算，結(jié)果作為未知節(jié)點(diǎn)的估計(jì)位置。其中對(duì)于只有兩個(gè)估計(jì)位置的點(diǎn)不采取位置過(guò)濾，取這兩個(gè)估計(jì)位置連線的中點(diǎn)作為節(jié)點(diǎn)的最終估計(jì)位置。對(duì)于估計(jì)位置較多的，本文采用dbscan（density-based spatial clustering of applications with noise）算法，dbscan10算法是一種基于密度的聚類算法11，12，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類，所以該算法可以有效識(shí)別噪聲，即不可靠位置。db

16、scan具體算法描述如下：（1）檢測(cè)數(shù)據(jù)庫(kù)中尚未檢查過(guò)的對(duì)象p，如果p為被處理（歸為某個(gè)簇或者標(biāo)記為噪聲），則檢查其鄰域，若包含的對(duì)象數(shù)不小于，建立新簇c，將中所有點(diǎn)加入c；（2）對(duì)c中所有尚未被處理的對(duì)象q，檢查其鄰域，若中至少包含個(gè)對(duì)象，則將中未歸入任何一個(gè)簇的對(duì)象加入c；（3）重復(fù)步驟2），繼續(xù)檢查c中未處理的對(duì)象，知道沒(méi)有新的對(duì)象加入當(dāng)前簇c；（4）重復(fù)步驟1）3），直到所有對(duì)象都?xì)w入了某個(gè)簇或標(biāo)記為噪聲。輸入數(shù)據(jù)：數(shù)據(jù)對(duì)象集合d，半徑eps，密度閾值minpts輸出數(shù)據(jù)：聚類c從算法中我們可以看出dbscan算法通過(guò)檢查數(shù)據(jù)庫(kù)中每個(gè)點(diǎn)的eps-鄰域來(lái)尋找聚類。如果一個(gè)點(diǎn)p的eps-鄰

17、域包含多于minpts個(gè)點(diǎn)，則創(chuàng)建一個(gè)以p作為核心對(duì)象的新簇。然后，dbscan反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象并加入該簇，直到?jīng)]有新的點(diǎn)可以被添加，該過(guò)程結(jié)束。由于該算法可以有效地去除噪聲即不可靠數(shù)據(jù)，因此dbscan算法能夠很好的應(yīng)用到空間位置過(guò)濾中去除空間不可靠數(shù)據(jù)。 3.2 改進(jìn)后的定位算法1）錨節(jié)點(diǎn)周期性發(fā)送自身信息：節(jié)點(diǎn)id、自身位置信息。2）待測(cè)節(jié)點(diǎn)接收其通訊范圍內(nèi)的所有節(jié)點(diǎn)的信息，并記錄他們的rssi值，建立從大到小的rssi數(shù)據(jù)集，選取通訊rssi值較大的錨節(jié)點(diǎn)進(jìn)行多次通訊測(cè)值，并運(yùn)用高斯濾波，舍去波動(dòng)較大的rssi值，得到n組 rssi值取其算術(shù)平均值：作為該錨節(jié)

18、點(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ù)該過(guò)程，直到選取次數(shù)大于一個(gè)閥值m。4）由3）得到四面體后，運(yùn)用四邊測(cè)量算法來(lái)對(duì)集合中的所有組合計(jì)算坐標(biāo)位置。對(duì)計(jì)算得到n組坐標(biāo)值過(guò)濾，對(duì)于只有兩個(gè)估計(jì)位置的點(diǎn)不采取位置過(guò)濾，取這兩個(gè)估計(jì)位置連線的中點(diǎn)作為節(jié)點(diǎn)的最后估計(jì)位置。對(duì)于估計(jì)位置較多的點(diǎn)，采用dbscan算法，選取集合最大的所有數(shù)據(jù)進(jìn)行計(jì)算平均值作為最終坐標(biāo)估計(jì)值。5）若未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)個(gè)數(shù)n<=3或者四面體集合為

19、空，則對(duì)所有錨節(jié)點(diǎn)采用rssi均值加權(quán)質(zhì)心算法來(lái)進(jìn)行未知節(jié)點(diǎn)估計(jì)。對(duì)于接收到p個(gè)錨節(jié)點(diǎn)信號(hào)，相應(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ī)噪聲，用來(lái)模擬現(xiàn)實(shí)環(huán)境的影響。500個(gè)定位結(jié)果是在相同的環(huán)境下運(yùn)行50次試驗(yàn)的平均值，部分區(qū)域仿真結(jié)果對(duì)比如圖3、圖4所示：由圖3和圖4的仿真結(jié)果對(duì)比可以看出，由于

20、在實(shí)際應(yīng)用的環(huán)境中會(huì)出現(xiàn)節(jié)點(diǎn)異?；蛘攮h(huán)境異常帶來(lái)的不可靠數(shù)據(jù)，會(huì)對(duì)系統(tǒng)定位精度產(chǎn)生影響，我們通過(guò)對(duì)采集的rssi值過(guò)濾和估計(jì)位置進(jìn)行過(guò)濾，定位結(jié)果要比未進(jìn)行位置過(guò)濾和rssi值高斯過(guò)濾的誤差要小，提高了定位精度。如圖5所示，在錨節(jié)點(diǎn)小于10個(gè)的時(shí)候本文算法定位精度明顯優(yōu)于傳統(tǒng)算法，這是因?yàn)殄^節(jié)點(diǎn)較少時(shí)環(huán)境誤差對(duì)定位精度影響較大，造成了傳統(tǒng)算法的定位不精確，而本文所提出的改進(jìn)算法具有明顯的優(yōu)點(diǎn)。但隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加兩種算法的精度都在不斷提高，這是因?yàn)殡S著錨節(jié)點(diǎn)的增加，由于最后取幾何均值使得環(huán)境誤差數(shù)據(jù)對(duì)總的定位結(jié)果影響較少，所以定位精度就得到了提高。圖6給出的是定位誤差隨通訊距離變化的趨勢(shì)。由

21、圖中可知隨著通訊距離的增加，傳統(tǒng)算法和本文算法的定位誤差都減小。因?yàn)樵黾庸?jié)點(diǎn)的通訊距離后，會(huì)使距離估計(jì)更加接近節(jié)點(diǎn)間的歐氏距離。由以上結(jié)果分析可知，在定位過(guò)程中節(jié)點(diǎn)的噪聲數(shù)據(jù)會(huì)影響定位的精度，本文在質(zhì)心定位算法的基礎(chǔ)上先通過(guò)對(duì)rssi值進(jìn)行高斯過(guò)濾從而優(yōu)化了采集的rssi值，保證了入口數(shù)據(jù)的準(zhǔn)確性和穩(wěn)定性。然后對(duì)計(jì)算結(jié)果進(jìn)行基于dbscan算法的估計(jì)位置過(guò)濾，通過(guò)仿真結(jié)果可以看出該算法有效的減少了不可靠數(shù)據(jù)對(duì)定位的影響，提高了定位精度。4 總結(jié)本文在研究了傳統(tǒng)的三維定位算法的基礎(chǔ)上，提出了一種估計(jì)位置過(guò)濾算法。該算法通過(guò)高斯過(guò)濾模型對(duì)采集的rssi的值進(jìn)行過(guò)濾得到穩(wěn)定的rssi值，然后對(duì)待定位

22、的節(jié)點(diǎn)進(jìn)行估計(jì)位置過(guò)濾，去除了在定位過(guò)程中由于主觀或者客觀因素帶來(lái)的不可靠位置，減少了其對(duì)定位精度的影響。文章通過(guò)仿真對(duì)比了本文算法和傳統(tǒng)算法在定位精度上的優(yōu)劣，由對(duì)比結(jié)果可知本文算法在定位精度上有了明顯的提高，能夠有效的減少實(shí)際應(yīng)用中隨機(jī)噪聲對(duì)定位的影響，該算法在三維定位中有著較大的應(yīng)用潛力。參考文獻(xiàn)：1 suomela j. computational complexity of relay placement in sensor networksj. lecture notes in computer science， 2006， 3831：521-529.2 kim s， ko j g

23、，yoon j， et al. multiple-objective metric for placing multiple base stations in wireless sensor networksa. proc of the 2rd international symposium on wireless pervasive computingc.pis-cataway，usa，2007：627-631.3 zhang jie， wu ling-xi，tang zhi-jun. ranging method and accuracy analysis based on rssi of

24、 wireless sensornetworkj.telcommunication engineering，2010，50（4）：83-874 wu jie，feng feng，ding zhi-yi research on coal mine underground localization algorithm based on integration of rfid and wsnj.computer engineering and design.2014（7）：2278-2282.5 shen x， wang z， jiang p， et al. connectivity and rss

25、i based localization scheme for wireless sensor networksj. 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-basedlocationc/positioning navigation and communication （wpnc）， 2012 9th workshop on. ieee，2012：

26、24-29.7 chen hong-yang， huang pei， martins m. novel centroid localization algorithm for three dimensional wireless sensor networksc/wicom'08 4th international conference on wireless c'ommunications，networking and mobile computing. 2008：1-48 liu zhuang，fang 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）