Min-Max節(jié)點(diǎn)定位算法的分析與改進(jìn)*

劉 慶，吳哲夫，何熊熊，劉 愷

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

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)通常可分為兩類，一類是已經(jīng)知道自身位置的節(jié)點(diǎn)，一般叫錨節(jié)點(diǎn)(Anchor Node)或參考節(jié)點(diǎn)(Reference Node);另一類是不知道自身位置的節(jié)點(diǎn)，通常叫未知節(jié)點(diǎn)(Unknown Node)或盲節(jié)點(diǎn)(Blind Node)。確定節(jié)點(diǎn)的位置信息是非常重要的，沒(méi)有位置信息的節(jié)點(diǎn)幾乎是沒(méi)有任何意義的[1]。未知節(jié)點(diǎn)往往需要利用錨節(jié)點(diǎn)來(lái)確定自身的位置，常見(jiàn)的WSN節(jié)點(diǎn)定位算法有很多，按是否需要測(cè)距可分為無(wú)需測(cè)距(Range Free)的定位算法和基于測(cè)距技術(shù)(Range Based)的定位算法，本文主要研究基于測(cè)距的定位技術(shù)。

基于測(cè)距的定位算法一般分為3個(gè)步驟:測(cè)距階段;定位階段;循環(huán)求精階段。其中測(cè)距階段表示選擇一種測(cè)距技術(shù)來(lái)測(cè)量錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的距離，常見(jiàn)的測(cè)距技術(shù)有[2]:基于到達(dá)時(shí)間(TOA)、基于到達(dá)時(shí)間差(TDOA)、基于到達(dá)角度(AOA)以及基于接收信號(hào)強(qiáng)度(RSSI)等方法。其中TOA和TDOA測(cè)距技術(shù)是以信號(hào)的傳播速度及傳輸時(shí)間作為輸入來(lái)計(jì)算距離，這要求設(shè)備具有高精度的時(shí)鐘實(shí)現(xiàn)同步，其優(yōu)點(diǎn)是定位準(zhǔn)確度高，但是成本高昂;AOA測(cè)距技術(shù)是利用天線陣列等額外的硬件設(shè)備來(lái)測(cè)量參考節(jié)點(diǎn)和盲節(jié)點(diǎn)間連線與參考線形成的角度，實(shí)現(xiàn)起來(lái)具有一定的困難;而RSSI測(cè)距技術(shù)是用理論或經(jīng)驗(yàn)信號(hào)衰減模型將傳播損耗映射為傳播距離，這種方法容易實(shí)現(xiàn)且具有較高的定位精度得到廣泛使用，這也是本文仿真中選用的測(cè)距技術(shù)。定位階段就是利用前面測(cè)距方法測(cè)得錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離，再選取一種合適的定位算法來(lái)計(jì)算未知節(jié)點(diǎn)的位置的過(guò)程，常見(jiàn)的定位方法有[3]:三邊測(cè)量定位法(Trilateration-based positioning algorithm)、極大似然估計(jì)定位法(Maximum likelihood estimation algorithm)和最小－最大定位法(Min-Max localization algorithm)，本文選取最簡(jiǎn)單也最容易實(shí)現(xiàn)的Min-Max定位方法，并對(duì)其在室內(nèi)環(huán)境中靠近定位邊緣區(qū)域未知節(jié)點(diǎn)的定位誤差較大的問(wèn)題分析了兩種原因并分別提出了改進(jìn)方法，最后進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明改進(jìn)方法能有效改善定位邊界區(qū)域未知節(jié)點(diǎn)的定位精度。最后循環(huán)求精階段是可選的，且對(duì)本文Min-Max及其改進(jìn)算法的性能比較無(wú)影響，暫不做討論。

1 基于RSSI測(cè)距模型

1.1 測(cè)距模型的建立

不同于TOA、TDOA和AOA，基于RSSI測(cè)距技術(shù)由于不需要添加額外的硬件，因此在低成本、低功耗、低復(fù)雜度的無(wú)線傳感器網(wǎng)絡(luò)中得以廣泛使用。本文在測(cè)距階段也使用基于RSSI測(cè)距方法。一個(gè)完整的定位系統(tǒng)的定位精度一直受測(cè)距誤差和定位誤差的影響，一個(gè)精確的測(cè)距模型能夠有效的減小定位誤差，通過(guò)實(shí)際測(cè)量并利用高斯濾波、線性回歸分析等方法都能有效的得到實(shí)際環(huán)境中的信號(hào)傳輸模型[4－5]。常用無(wú)線信號(hào)在環(huán)境中的傳輸模型是Shadowing模型[6]，如式(1)所示:

其中d0為參考距離(一般取1 m);p0表示距離為d0處接收到的信號(hào)強(qiáng)度;d為真實(shí)距離;ξ是以db為單位的遮蔽因子，其均值為0，均方差為σdb(db)的正態(tài)隨機(jī)變量;p表示在真實(shí)距離d處的接收信號(hào)強(qiáng)度;n是路徑損耗指數(shù)，在不同環(huán)境下取不同值。在實(shí)際環(huán)境中，對(duì)信號(hào)傳輸影響最嚴(yán)重的是非視距(NLOS)的影響，因此傳輸模型可以不考慮遮擋因子對(duì)信號(hào)的影響，所以實(shí)際測(cè)量中可以選用以下模型:

射頻參數(shù)A被定義為用dBm表示的距離發(fā)射節(jié)點(diǎn)1 m處接收到的平均能量絕對(duì)值，也就是發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)相距1 m時(shí)的接收信號(hào)強(qiáng)度絕對(duì)值，一般取值在30～50之間，實(shí)際應(yīng)用中可實(shí)際測(cè)量求其精確值;n是路徑損耗指數(shù)，不同環(huán)境和建筑物下值都是不同的;d為真實(shí)距離。因此當(dāng)節(jié)點(diǎn)接收到RSSI值后可由式(2)計(jì)算其距離如下:

1.2 模型參數(shù)的分析

通過(guò)RSSI測(cè)距模型可以看出:接收信號(hào)強(qiáng)度與信號(hào)傳輸距離之間的關(guān)系取決于常數(shù)A和n的取值，因此要利用式(2)進(jìn)行信號(hào)強(qiáng)度測(cè)距時(shí)，首先得確定這兩個(gè)常數(shù)的取值。很多文獻(xiàn)通過(guò)實(shí)際的研究給出了不同環(huán)境下參數(shù)A，n的取值范圍如表1所示，以下分別分析這2個(gè)常數(shù)的取值對(duì)信號(hào)傳輸模型的影響。

表1 不同環(huán)境下A，n的取值[4]

參數(shù)A表示的是兩個(gè)節(jié)點(diǎn)相距1 m時(shí)的平均接收信號(hào)強(qiáng)度絕對(duì)值，實(shí)際應(yīng)用中節(jié)點(diǎn)使用不同的硬件或在不同的環(huán)境下，甚至節(jié)點(diǎn)電池電量的變化對(duì)A值的影響都很大。為了研究不同的A值對(duì)測(cè)距模型的影響，先假設(shè)n不變，A變化，得如圖1所示的關(guān)系曲線圖，其中橫軸表示距離，縱軸表示對(duì)應(yīng)于該距離獲取的RSSI值。

圖1 A取不同值時(shí)RSSI與距離曲線圖

由圖1所示，隨著距離的增加，RSSI值越來(lái)越小，尤其是在10 m內(nèi)信號(hào)衰減非常快，遠(yuǎn)距離時(shí)信號(hào)衰減變得緩慢。由圖可見(jiàn)在相同距離時(shí)A取值越大RSSI值越小，即在1 m處接收到的信號(hào)強(qiáng)度越小，這與理論分析也是相符的，因?yàn)锳表示在1 m處接收到的信號(hào)強(qiáng)度的絕對(duì)值。

當(dāng)A取值不變，n改變時(shí)可得RSSI與信號(hào)傳輸距離關(guān)系如圖2。

圖2 n取不同值時(shí)RSSI與距離曲線圖

其中n表示的是路徑損耗指數(shù)，由圖可知n越小，信號(hào)在傳輸過(guò)程的衰減就越小，因此信號(hào)也能傳輸?shù)礁h(yuǎn)的距離。越理想的環(huán)境下，干擾越小，信號(hào)傳輸距離越遠(yuǎn)，當(dāng)然實(shí)際應(yīng)用中不一定n越小越好，而是越適合該環(huán)境下的n值越好，適當(dāng)?shù)倪x取A，n的值可以極大的提高測(cè)距精度。

常見(jiàn)室內(nèi)環(huán)境下受到信號(hào)反射、多徑效應(yīng)等影響，路徑損耗指數(shù)一般比較大，因此室內(nèi)的節(jié)點(diǎn)精確定位也是很多文章研究的重點(diǎn)。為了研究Min-Max及其改進(jìn)算法在惡劣的室內(nèi)環(huán)境中的定位效果，本文選取A=50，n=3的作為RSSI測(cè)距模型，以后的討論及仿真都是基于此模型下進(jìn)行的。

2 Min-Max定位算法

Min-Max定位算法相對(duì)三邊測(cè)量定位法和極大似然估計(jì)定位法是一個(gè)非常簡(jiǎn)單有效的定位方法，在實(shí)際使用中因其計(jì)算復(fù)雜度小而使節(jié)點(diǎn)工作過(guò)程能耗低并具有較高實(shí)時(shí)性等優(yōu)點(diǎn)而得以大力推廣[7－8]。它是一種基于幾何學(xué)原理的定位方法，原理如圖3所示。

圖3 Min-Max定位算法原理圖

其中未知節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度RSSIi(i=1，2，…，n)分別計(jì)算該錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離為di(i=1，2，…，n)，然后以每個(gè)錨節(jié)點(diǎn)為中心分別向上下左右擴(kuò)展di畫(huà)一個(gè)正方形，即正方形邊長(zhǎng)是2di。算法實(shí)現(xiàn)過(guò)程就是去計(jì)算這些正方形所包圍的最小的重合矩形區(qū)域，并以該區(qū)域的中心點(diǎn)作為未知節(jié)點(diǎn)的估計(jì)位置[9－11]。設(shè)各正方形的邊界值分別為:左(xi－di)，右(xi+di)，上(yi+di)，下(yi－di)，則重合矩形區(qū)域的邊界值應(yīng)該是:左max(xi－di)，右 min(xi+di)，上 min(yi+di)，下 max(yidi)。因此未知節(jié)點(diǎn)的位置可以計(jì)算如下:

由Min-Max算法原理可知，其定位過(guò)程中主要的運(yùn)算是計(jì)算復(fù)雜度較小的加減及比較運(yùn)算，除了在計(jì)算未知節(jié)點(diǎn)位置時(shí)需要一些相除運(yùn)算外，總體所需要的計(jì)算量是很少的，而這在實(shí)際節(jié)點(diǎn)定位應(yīng)用中表現(xiàn)為更小的功耗及更短的定位延遲時(shí)間，這對(duì)于資源有限的節(jié)點(diǎn)來(lái)說(shuō)尤其可貴。因此研究如何提高M(jìn)in-Max定位算法的精度對(duì)低成本、低功耗且對(duì)實(shí)時(shí)性要求比較高的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位是非常具有價(jià)值的。

3 Min-Max算法的分析與改進(jìn)

對(duì)Min-Max定位算法的仿真發(fā)現(xiàn)，在定位區(qū)域中心附近的節(jié)點(diǎn)定位精度普遍高于邊緣區(qū)域節(jié)點(diǎn)。通過(guò)對(duì)Min-Max定位算法原理分析，總結(jié)了兩點(diǎn)可能導(dǎo)致這種情況的原因:①定位邊緣區(qū)域錨節(jié)點(diǎn)較少，即邊緣區(qū)域未知節(jié)點(diǎn)所能接收到的錨節(jié)點(diǎn)數(shù)量較少，導(dǎo)致定位誤差大于中心區(qū)域的未知節(jié)點(diǎn);②定位處于邊緣區(qū)域未知節(jié)點(diǎn)的正方形有可能超出定位區(qū)域，即重合矩形區(qū)域有可能有一部分在定位區(qū)域以外，進(jìn)而在計(jì)算未知節(jié)點(diǎn)位置時(shí)導(dǎo)致誤差增大。

第1種情況，邊緣錨節(jié)點(diǎn)數(shù)量對(duì)算法定位精度的影響是顯而易見(jiàn)的，實(shí)際應(yīng)用中可以通過(guò)增加錨節(jié)點(diǎn)的數(shù)量或適當(dāng)調(diào)整錨節(jié)點(diǎn)的部署來(lái)解決這個(gè)問(wèn)題。本文主要分析第2種情況的影響。

3.1 矩形邊緣越界檢測(cè)法

為了驗(yàn)證第2種情況，即定位邊緣未知節(jié)點(diǎn)的重合矩形區(qū)域的邊界越界問(wèn)題對(duì)節(jié)點(diǎn)定位精度的影響，我們提出了一種方法進(jìn)行修正，叫“矩形邊緣越界檢測(cè)法”。其原理如圖4所示。

其工作原理是先對(duì)所有的定位未知節(jié)點(diǎn)的重合矩形區(qū)域進(jìn)行越界判定，如果有一個(gè)邊界超出定位區(qū)域，就以該方向的定位區(qū)域的值作為矩形的邊界值。這樣可以縮小重合的矩形區(qū)域，并在求未知節(jié)點(diǎn)的估計(jì)位置時(shí)減小與實(shí)際位置之間的偏差，減小定位誤差。其偽代碼表示如下:

圖4 改進(jìn)Min-Max定位算法原理圖

矩形左邊界值判定:if max(xi－di)＜0，max(xidi)=0，else max(xi－di);

矩形右邊界值判定:if min(xi+di)＞right，min(xi+di)=right，else min(xi+di);

矩形上邊界值判定:if min(yi+di)＞up，min(yi+di)=up，else min(yi+di);

矩形下邊界值判定:if max(yi－di)＜0，max(yidi)，=0，else max(yi－di);

其中right，up分別表示定位區(qū)域的右邊界值和上邊界值。經(jīng)過(guò)邊界值判定后可以確保定位所有未知節(jié)點(diǎn)的重合矩形區(qū)域在有效定位區(qū)域內(nèi)，并且能有效縮小重合區(qū)域的范圍，減小未知節(jié)點(diǎn)的定位誤差。

3.2 仿真與分析

為了檢驗(yàn)Min-Max及其改進(jìn)定位算法的性能，本文對(duì)傳統(tǒng)Min-Max定位算法和改進(jìn)算法在Matlab平臺(tái)上分別進(jìn)行仿真對(duì)比分析。其中錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的位置都是隨機(jī)產(chǎn)生，節(jié)點(diǎn)通信半徑R=20 m。

首先在一個(gè)較小的區(qū)域，設(shè)為10 m×10 m空間內(nèi)，在相同位置部署3個(gè)錨節(jié)點(diǎn)和一個(gè)未知節(jié)點(diǎn)。考慮到未知節(jié)點(diǎn)靠近定位邊緣區(qū)域時(shí)錨節(jié)點(diǎn)的位置主要有3種情況，第1種是錨節(jié)點(diǎn)都靠近中心區(qū)域;第2種有部分錨節(jié)點(diǎn)在中心區(qū)域，部分錨節(jié)點(diǎn)在邊緣區(qū)域;第3種是錨節(jié)點(diǎn)都靠近邊緣區(qū)域。由改進(jìn)算法的原理及仿真結(jié)果顯示在這3種情況下改進(jìn)算法都能有效的提升定位精度，但是第3種情況下的改進(jìn)效果最明顯，因?yàn)殄^節(jié)點(diǎn)和未知節(jié)點(diǎn)都處于邊緣區(qū)域時(shí)矩形重合區(qū)域也最有可能出界，進(jìn)而在確定未知節(jié)點(diǎn)的位置時(shí)產(chǎn)生更大的定位誤差。由于篇幅所限，本文只給出錨節(jié)點(diǎn)及未知節(jié)點(diǎn)都處于邊緣區(qū)域時(shí)，在相同情況下分別對(duì)Min-Max算法及其改進(jìn)算法的一次仿真結(jié)果，如圖5所示。

圖5 錨節(jié)點(diǎn)靠近邊緣區(qū)域定位效果圖

由圖5(a)可知在錨節(jié)點(diǎn)及未知節(jié)點(diǎn)都處于邊緣區(qū)域時(shí)使用Min-Max定位算法得到的定位誤差約為4 m，雖然隨著節(jié)點(diǎn)分布的改變定位誤差也會(huì)有不同，但如此大的誤差實(shí)在不可取，而圖5(b)中利用改進(jìn)定位算法的定位誤差是約為2 m，定位精度提高了1倍。這證明利用矩形邊緣越界檢測(cè)法確實(shí)能有效的縮小靠近定位邊緣區(qū)域未知節(jié)點(diǎn)的定位誤差，提高其定位精度。

為了驗(yàn)證改進(jìn)Min-Max算法在大規(guī)模多個(gè)節(jié)點(diǎn)環(huán)境下的定位性能，我們分別在300 m×300 m定位區(qū)域內(nèi)相同位置部署50個(gè)錨節(jié)點(diǎn)和100個(gè)未知節(jié)點(diǎn)，使用兩種算法分別進(jìn)行仿真得到定位結(jié)果如圖6所示。

圖6 定位100個(gè)未知節(jié)點(diǎn)效果圖

由圖6(a)和(b)比較可以看到靠近定位邊緣的未知節(jié)點(diǎn)的估計(jì)位置與實(shí)際位置之間的誤差有一定的減小，但是靠近中心區(qū)域節(jié)點(diǎn)的位置是不變的，因?yàn)槎ㄎ凰鼈兊闹睾暇匦螀^(qū)域越界的概率是比較小的。總的來(lái)說(shuō)，改進(jìn)Min-Max算法在改進(jìn)邊緣區(qū)域未知節(jié)點(diǎn)的定位精度上是非常顯著的，因此從總體上提高了系統(tǒng)的定位精度。

為了更直觀的比較這兩種算法的定位性能，本文利用平均定位誤差來(lái)表示系統(tǒng)的整體定位性能，設(shè)各未知節(jié)點(diǎn)的實(shí)際位置為(x，y)，估計(jì)位置為(xi，yi)，節(jié)點(diǎn)通信半徑為R，平均定位誤差定義如下[6]:

圖7顯示的是在100 m×100 m區(qū)域內(nèi)部署150個(gè)節(jié)點(diǎn)，錨節(jié)點(diǎn)比率分別為10%、15%、…、40%下傳統(tǒng)Min-Max定位算法與改進(jìn)算法的平均定位誤差圖。如圖7所示，隨著錨節(jié)點(diǎn)比例的增加，兩種算法的平均定位誤差都呈下降的趨勢(shì)，但是改進(jìn)Min-Max算法由于在定位邊緣未知節(jié)點(diǎn)方面比傳統(tǒng)Min-Max算法更精確，所以其平均定位誤差普遍比傳統(tǒng)Min-Max算法要低。

圖7 不同錨節(jié)點(diǎn)比率下平均定位誤差圖

圖8是在100 m×100 m區(qū)域內(nèi)保持錨節(jié)點(diǎn)比率為20%，節(jié)點(diǎn)總數(shù)從100到400分別運(yùn)行兩種算法得到的平均定位誤差圖。從圖可以看出隨著節(jié)點(diǎn)數(shù)量的增加，兩種算法的平均定位誤差都呈下降趨勢(shì)。但是隨著節(jié)點(diǎn)總數(shù)的增加，處于邊緣區(qū)域的未知節(jié)點(diǎn)也增加了，而此時(shí)利用改進(jìn)Min-Max算法定位這些節(jié)點(diǎn)的精度提高也更明顯，由圖可知在相同條件下改進(jìn)Min-Max算法比傳統(tǒng)Min-Max算法平均定位誤差都要低，且隨著節(jié)點(diǎn)數(shù)量的增加改進(jìn)Min-Max算法的降低幅度更大。

圖8 不同節(jié)點(diǎn)總數(shù)下平均定位誤差圖

4 總結(jié)

節(jié)點(diǎn)的位置信息對(duì)于WSN來(lái)說(shuō)是非常重要的。如何獲取更精確的位置信息也是很多文章研究的重點(diǎn)，而基于RSSI測(cè)距的定位技術(shù)由于其低成本、低復(fù)雜度廣受歡迎[12]。論文在RSSI測(cè)距模型基礎(chǔ)上對(duì)Min-Max定位算法進(jìn)行了詳細(xì)的分析與討論，并著重對(duì)算法在定位邊緣區(qū)域未知節(jié)點(diǎn)的精度不足方面提出了矩形邊緣越界檢測(cè)法進(jìn)行改進(jìn)，該方法能有效的檢測(cè)重合矩形區(qū)域是否越界并做出相應(yīng)的改進(jìn)，以提高位于邊緣區(qū)域未知節(jié)點(diǎn)的定位精度。理論及仿真結(jié)果表明在未知節(jié)點(diǎn)處于邊緣區(qū)域時(shí)，其定位誤差與錨節(jié)點(diǎn)的所處的位置有關(guān)系，但是改進(jìn)算法都能有效的提高定位精度，尤其是錨節(jié)點(diǎn)也處于邊緣區(qū)域時(shí)改進(jìn)效果更明顯。無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法往往受到功耗、延時(shí)等限制，簡(jiǎn)單有效的Min-Max定位方法在實(shí)際應(yīng)用中具有較大的實(shí)用價(jià)值。

[1]Priyantha N B，Balakrishnam H，Demaine E，et.Anchor-Free Distributed Localization in Sensor Networks，Technical Report MITLCS-TR-892[R].Cambrige:MIT Lab for Computer Science，2003.

[2]陳紅陽(yáng).基于測(cè)距技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D].成都，西南交通大學(xué)，2006:3－6.

[3]郜麗鵬，朱梅冬，楊丹.基于Zigbee的加權(quán)質(zhì)心定位算法的仿真與實(shí)現(xiàn)[J].傳感技術(shù)學(xué)報(bào)，2010，23(1):149－152.

[4]方震，趙湛，郭鵬.基于 RSSI測(cè)距分析[J].傳感技術(shù)學(xué)報(bào)，2007，20(11):2526－2530.

[5]朱明輝，張會(huì)清.基于RSSI的室內(nèi)測(cè)距模型的研究[J].傳感器與微系統(tǒng)，2010，29(8):19－22.

[6]趙清華，劉少飛，張朝霞.一種無(wú)需測(cè)距節(jié)點(diǎn)定位算法的分析與改進(jìn)[J].傳感技術(shù)學(xué)報(bào)，2010，23(1):122－127.

[7]Awad A，F(xiàn)runzke T，Dressler F.A Daptivedistance Estimation and Localization in WSNs Using RSSI Measures.[C]//IEEE 10th EuromicroConference on DigitalSystem Design Architectures Methods and Tools，Aug.2007:471－478.

[8]Goldoni E，Savioli A，Risi M，et al.Experimetal Analysis of RSSIBased Indoor Localization with IEEE 802.15.4[C]//Proc.2010 European Wireless Conference，Pavia，Italy，2010，71－77.

[9]Savvides A，Park H，Srivastava M.The Bits and Flops of the n-Hop Multilateration Primitive for Node Localization Problems[C]//Proc.ACM WSNA 2002，Atlanta，Georgia，USA，September 28，2002，112－121.

[10]戴瑩，王建平，張崇巍.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究與改進(jìn)[J].傳感技術(shù)學(xué)報(bào)，2010，23(4):567－570.

[11]彭宇，王丹.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測(cè)量與儀器學(xué)報(bào)，2011，25(5):389－399.

[12]Desai J，Tureli U.Evaluating Performance of Various Localization Algorithmsin Wireless and Sensor Networks[C]//Proc.IEEE PIMRC 2007，Athens，Greece，September 3－7，2007，1－5.