Min-Max節點定位算法的分析與改進*

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

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

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

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

1 基于RSSI測距模型

1.1 測距模型的建立

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

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

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

1.2 模型參數的分析

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

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

參數A表示的是兩個節點相距1 m時的平均接收信號強度絕對值，實際應用中節點使用不同的硬件或在不同的環境下，甚至節點電池電量的變化對A值的影響都很大。為了研究不同的A值對測距模型的影響，先假設n不變，A變化，得如圖1所示的關系曲線圖，其中橫軸表示距離，縱軸表示對應于該距離獲取的RSSI值。

圖1 A取不同值時RSSI與距離曲線圖

由圖1所示，隨著距離的增加，RSSI值越來越小，尤其是在10 m內信號衰減非常快，遠距離時信號衰減變得緩慢。由圖可見在相同距離時A取值越大RSSI值越小，即在1 m處接收到的信號強度越小，這與理論分析也是相符的，因為A表示在1 m處接收到的信號強度的絕對值。

當A取值不變，n改變時可得RSSI與信號傳輸距離關系如圖2。

圖2 n取不同值時RSSI與距離曲線圖

其中n表示的是路徑損耗指數，由圖可知n越小，信號在傳輸過程的衰減就越小，因此信號也能傳輸到更遠的距離。越理想的環境下，干擾越小，信號傳輸距離越遠，當然實際應用中不一定n越小越好，而是越適合該環境下的n值越好，適當的選取A，n的值可以極大的提高測距精度。

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

2 Min-Max定位算法

Min-Max定位算法相對三邊測量定位法和極大似然估計定位法是一個非常簡單有效的定位方法，在實際使用中因其計算復雜度小而使節點工作過程能耗低并具有較高實時性等優點而得以大力推廣[7－8]。它是一種基于幾何學原理的定位方法，原理如圖3所示。

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

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

由Min-Max算法原理可知，其定位過程中主要的運算是計算復雜度較小的加減及比較運算，除了在計算未知節點位置時需要一些相除運算外，總體所需要的計算量是很少的，而這在實際節點定位應用中表現為更小的功耗及更短的定位延遲時間，這對于資源有限的節點來說尤其可貴。因此研究如何提高Min-Max定位算法的精度對低成本、低功耗且對實時性要求比較高的無線傳感器網絡節點定位是非常具有價值的。

3 Min-Max算法的分析與改進

對Min-Max定位算法的仿真發現，在定位區域中心附近的節點定位精度普遍高于邊緣區域節點。通過對Min-Max定位算法原理分析，總結了兩點可能導致這種情況的原因:①定位邊緣區域錨節點較少，即邊緣區域未知節點所能接收到的錨節點數量較少，導致定位誤差大于中心區域的未知節點;②定位處于邊緣區域未知節點的正方形有可能超出定位區域，即重合矩形區域有可能有一部分在定位區域以外，進而在計算未知節點位置時導致誤差增大。

第1種情況，邊緣錨節點數量對算法定位精度的影響是顯而易見的，實際應用中可以通過增加錨節點的數量或適當調整錨節點的部署來解決這個問題。本文主要分析第2種情況的影響。

3.1 矩形邊緣越界檢測法

為了驗證第2種情況，即定位邊緣未知節點的重合矩形區域的邊界越界問題對節點定位精度的影響，我們提出了一種方法進行修正，叫“矩形邊緣越界檢測法”。其原理如圖4所示。

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

圖4 改進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分別表示定位區域的右邊界值和上邊界值。經過邊界值判定后可以確保定位所有未知節點的重合矩形區域在有效定位區域內，并且能有效縮小重合區域的范圍，減小未知節點的定位誤差。

3.2 仿真與分析

為了檢驗Min-Max及其改進定位算法的性能，本文對傳統Min-Max定位算法和改進算法在Matlab平臺上分別進行仿真對比分析。其中錨節點和未知節點的位置都是隨機產生，節點通信半徑R=20 m。

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

圖5 錨節點靠近邊緣區域定位效果圖

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

為了驗證改進Min-Max算法在大規模多個節點環境下的定位性能，我們分別在300 m×300 m定位區域內相同位置部署50個錨節點和100個未知節點，使用兩種算法分別進行仿真得到定位結果如圖6所示。

圖6 定位100個未知節點效果圖

由圖6(a)和(b)比較可以看到靠近定位邊緣的未知節點的估計位置與實際位置之間的誤差有一定的減小，但是靠近中心區域節點的位置是不變的，因為定位它們的重合矩形區域越界的概率是比較小的。總的來說，改進Min-Max算法在改進邊緣區域未知節點的定位精度上是非常顯著的，因此從總體上提高了系統的定位精度。

為了更直觀的比較這兩種算法的定位性能，本文利用平均定位誤差來表示系統的整體定位性能，設各未知節點的實際位置為(x，y)，估計位置為(xi，yi)，節點通信半徑為R，平均定位誤差定義如下[6]:

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

圖7 不同錨節點比率下平均定位誤差圖

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

圖8 不同節點總數下平均定位誤差圖

4 總結

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

[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]陳紅陽.基于測距技術的無線傳感器網絡定位技術研究[D].成都，西南交通大學，2006:3－6.

[3]郜麗鵬，朱梅冬，楊丹.基于Zigbee的加權質心定位算法的仿真與實現[J].傳感技術學報，2010，23(1):149－152.

[4]方震，趙湛，郭鵬.基于 RSSI測距分析[J].傳感技術學報，2007，20(11):2526－2530.

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

[6]趙清華，劉少飛，張朝霞.一種無需測距節點定位算法的分析與改進[J].傳感技術學報，2010，23(1):122－127.

[7]Awad A，Frunzke 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]戴瑩，王建平，張崇巍.無線傳感器網絡節點定位算法的研究與改進[J].傳感技術學報，2010，23(4):567－570.

[11]彭宇，王丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報，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.