一種基于RSSI的混合定位算法*

王 千，金 光，鈕 俊

（寧波大學信息與工程學院，浙江寧波351211）

作為一種新型的信息獲取、數據處理的智能嵌入式設備，無線傳感器網絡具有廣泛的應用領域。而在WSN應用中，節點位置信息是在目標識別、監控、跟蹤等應用方面的前提和基礎，故室內目標定位等應用，可彌補GPS等衛星定位系統在室內難于獲得位置信息的弊端，為大型商城、體育場館、會展中心、停車場、室內廣場提供目標跟蹤等實時位置信息。

目前節點定位算法主要按照基于免測距（Range-free）和基于測距（Range-based）的方法進行分類［1］。免測距方法不直接對距離進行測量，而是使用網絡的連通度來估計節點距錨節點的距離或坐標，比較典型的有質心算法［2］、距離向量算法［3］（DV-Hop）和近似三邊內角測試法（APIT）［4］等。基于測距的算法利用某種測量方法測量距離（或角度），利用測得的距離（或角度）計算未知節點坐標，如基于信號傳輸時間的方法TOA（Time Of Arrival）和基于信號傳輸時間差的方法［5］TDOA（Time Differ?ence Of Arrival，），基于信號角度方法［6］AOA（Angle Of Arrival），以及基于接收信號強度的方法RSSI（Received Signal Strength Indicator）［7］方法等。

RSSI測距技術利用接收節點收到的信號強度（RSSI）計算出信號的傳輸損耗，根據理論和經驗模型將傳輸耗損轉化為距離模型。在定位方案展開前，需對定位區域進行RSSI值測試，將不同位置得到的RSSI值保存到數據庫中，建成場強圖或擬合曲線，以供實際測試時調用［8］。一般基于該測距技術的定位算法按照圖1流程實現：

圖1 基于RSSI的定位方案

Chin-Tseng Huang等人［9］提出將因子圖框架引入測量誤差的隨機特征和數據可靠性，以提高信號接收的準確性，并對功率衰減分布作局部線性處理以降低復雜度，獲得高精確度，低復雜度的定位算法；陳錫劍等人［10］依據信號強度均方差判斷實際信號接收功率與預先存儲的匹配程度，將最小信號強度均方差的位置作為未知節點的定位坐標；王緩緩等人［11］提出基于距離區間概率加權的測距方法，以概率為權值對區間中的所有距離進行加權求和，并作為該RSSI值對應的距離；劉運杰等人［12］提出采用測試距離倒數之和代替距離和的倒數作為權重，引入修正系數，避免信息淹沒提高定位精度。劉政等人［13］提出一種基于接收信號強度的誤差自校正算法，通過利用校正節點，結合質心信標節點實際位置求得距離差，利用誤差自校正因子替換未知節點的測距誤差因子，對測距誤差進行補償，從而完成定位。

在實際應用環境中，由于受多徑衰減、環境噪音、信號傳輸的反射、繞射、衍射現象以及天線增益等問題的影響，普通的RSSI測距方法會存在較大誤差，如果后續定位方法基于該測距方案，且對于測距精度具有有限的容忍度，最終定位結果將具備較大誤差。并且，現有的定位算法大部分在Matlab、NS2等仿真軟件完成性能測試，極少在實際環境中實測完成性能，不能完全體現定位算法，尤其是基于RSSI方案在復雜環境下的真實性。

本文就上述一些問題提出一種混合定位（Hy brid Localization）算法。該算法基于TinyOS操作系統于實際場景下實驗，通過實際采集的數據，進行BP神經網絡訓練，抑制噪聲的干擾，消除對于經驗的過度依賴，建立信號強度—距離模型；然后統計在同一RSSI信號強度下，實際測量距離與模型預測距離差值，計算距離差值/預測距離的比值，從而通過統計數組的分布，建立實際測距數值可能的存在范圍；再以錨節點（Anchor Node）為圓心，預測距離結合波動范圍確定的半徑，建立實際距離概率環形區間，在信號平穩的條件下，通過多環形帶交疊方式得到盲節點（Blind Node）最大概率的落點范圍；而當信號偏移幅度較大時，則采用多邊界質心法［14］，以預測距離為基準逐步擴大范圍，界定盲節點落點區間。最終根據計算的落點區域，均衡計算得到盲節點的位置信息。

1 混合定位方法

1.1 基于BP訓練的測距模型

無線電傳播距離損耗對基于RSSI定位算法的定位精度影響很大。無線信號在環境中傳播的過程中隨著傳播距離的增加，信號強度逐漸變弱。而最常用的傳播路徑損耗模型是Shadowing模型：

在式（1）中，d0表示參考距離，一般設定為1 m，d表示實際距離，P（d）和P（d0）表示在d和d0傳播距離下路徑耗損值，n表示路徑耗損指數，該指數與環境有關，δ表示傳輸過程的噪音。一般在取得大量（RSSI，D）數對下，通過如最小二乘法、局部線性化法、雅克比迭代法等擬合方法，來確定式（1）中n的耗損指數和δ噪聲，并在后續的定位方法中作為RSSI強度的對應輸出距離。

而實際環境中的環境干擾、傳輸特性等因素，將導致lg（d/d0）和P（d）不會表現標準線性關系，并且實際噪聲雜亂無章，不會呈現仿真般的規律性，使用Shadowing模型建模本身在理論上就存在一定的誤差。針對這些問題，Shih-Hau Fang等人［15］提出通過收集信號數據，建立用于訓練的射頻覆蓋圖，使用多重判別分析組件，實現離線階段的監督和自適應網絡學習，建立可判別的自適應神經網絡。有鑒于此，本文選擇使用BP神經網絡方法用于訓練距離預測模型：①在實驗部分通過反復測試可知，RS?SI測量具有重復性和互換性，具備規律可循，可用數學模型進行表示；②相比于Shadowing模型而言，無需分別求參的方法避免了微小誤差的積累。結合本文定位需求，定義BP神經網絡用于訓練求解預測距離d=φ(RSSI)，其網絡結構定義為：①輸入輸出層的確定。本網絡輸入節點數1，RSSI信號強度為輸入節點；輸出節點數1，D距離為輸出節點。②隱含層的確定。實驗證明，雖然模型的吻合精度會隨著隱含層層數的增加而略有提高，但是將大大增加算法的復雜度。而隱含層節點個數的確定暫時未有完全理論指導，但在實驗過程中，我們將隱含層個數從個數10開始訓練，標準誤差（RMSE）值在第21個后趨向平穩并取得最小值，故隱含層數目選擇21，這將具備較快速的訓練過程以及良好的訓練結果。③BP算法的選擇［16］。由于BP算法存在收斂速度慢、易陷入局部極小點的缺陷，其實際應用面窄，故選擇針對過反復實驗和比較更有效的traincgf算法，激活函數就選擇基本的Sigmoid函數。

在本文的實驗部分中，使用同樣的采集數據，分別運用BP網絡訓練方法及Shadowing方法建立信號強度—距離預測模型，考慮后續定位的需求，將信號強度作為輸入項，將距離作為輸出項，實驗結果如圖2所示。結果表明Shadowing模型更接近于理論上自由空間的傳播耗損，但不符合室內實際環境下耗損，而BP網絡訓練結果更符合實際傳輸耗損模型。保留BP網絡各層之間的連接權值、閾值以及轉換函數等，作為定位算法的測距模型。

圖2 偏差率統計

1.2 混合定位算法

即使盡量消除噪聲對于接收的信號強度的影響，并采用高斯模型等方式剔除小概率，高干擾事件等方式，但是實際落點距離和信號強度對應關系不會是單純的遵循預估模型，實際落點會概率性的落在于一個相關于信號強度的點的浮動區間，使用精確的數學求解模型（比如加權質心法）會將測距模型的誤差累積，故使用環形區間交疊法直接考慮存在誤差，并以多邊界質心法［14］為輔助提升定位精度。

1.2.1 概率環形區間交疊定位算法

將上述測距模型中RSSI信號強度對應的預測距離作為參考，統計實際距離相對于參考點的落點范圍。本文通過定義λ為偏差率，表示實際測量值與模型預估的距離差異。

式（2）中，Disori表示實際測量距離而Dispre表示測距模型預估距離值。

由于實驗環境為室內，故而會存在某些接收信號強度由于多徑傳輸的影響出現大幅度擾動，故引入高斯模型［17］濾除特殊事件，處理λ數組，設數組個數為n：

根據實際經驗，認為該區間為偏差落點估計的高概率范圍，設在該范圍內的點個數為m，必須滿足落點個數至少要達到總數目的80%，以式（3）～式（5）高斯模型作為約束，ω從0.5開始取，實驗計算結果表明當取到0.68時滿足要求。λ數組處理后得到則可統計得到新數組上下界lower、upper，通過預測模型估算距離，并加權該上下界計算得到概率環形區間。如圖3所示陰影部分即為以錨節點為中心統計的概率環形區間。

在一般的加權質心算法中，都是通過添加權重因子作為信標節點對盲節點的影響權重，映射并量化其距離關系。該類型方法由于傳輸耗損模型更加遵循Shadowing對數模型，故其在自由環境下可能會具備良好定位精度，但是對于室內復雜環境，信號傳輸的規律性降低，完全的依賴傳輸模型并精確界定距離是不適用的，故本文通過概率區間相交疊劃分出盲節點最可能分布落點區間，消除過度的經驗依賴。信號強度—距離模型預測屬于非矢量，故而需要多組錨節點建立概率區間協同定位。

錨節點選取接收信號強度一致，且最靠近盲節點信號強度一致的三個節點，則其所受的多徑衰減、背景噪聲等因素一致。對于每個錨節點，按照圖4建立起相對應的概率環形區間，將三個環形區通過交疊的方式界定其落點區間，如圖4所示。

圖4 概率區間交疊范圍

對于錨節點A、B、C感知范圍交疊的區域，是指這三個錨節點內圓外、外圓內的相交區域，如圖藍色部分所示。設其邊界為A1、A2、B1、B2、C1、C2。在已知錨節點坐標，C節點的感知外圓與A、B的內圓交點為盲節點落點的臨界區間點，通過圓相交計算得C1、C2，同理可得六點邊界坐標。信號強度與距離在趨勢上是呈現對數的關系，但在局部區間卻具備較強的隨機性，在確定的概率區間中，認定其為同概率，則最大概率的落點即為該區域的質心。計算質心，確定盲節點位置。

但是顯然，所有實際建立的錨節點概率環形區都不會如圖4所示，在本文的定位實驗測試中，大約會出現33.3%的測量所得信號強度對應的預測距離低于統計的下界，或者高于上界，其區間交疊會呈現離散區域，定位精度下降。表現在幾何計算中則如圖5所示。

圖5 不理想的區間交疊

在圖5的交疊區間中，其交疊范圍呈散落狀。這是由于當次對應采集的RSSI信號表現出大幅度的偏移（較大幅度的信號波動），盲節點與錨節點的實際距離將超出/短于模型預估距離的概率區間，該情況下計算出的盲節點坐標誤差很大。該算法雖然在圈定的概率區間中表現良好，但是對偏移信號的容忍度低，考慮混合使用一種容忍度高的算法，即犧牲定位精度，擴大實際落點的可能區間，以一種統籌算法計算所有狀況，故提出使用多邊界質心法［13］進行輔助定位。

1.2.2 多邊界質心定位

該方法是將RSSI-D模型的預測距離Dispre作為A、B、C三個錨節點的計算感知范圍半徑，如圖6所示。

圖6 多邊界質心法

幾何上連接三點得到三條線段，每條線段都與感知圓環相交得六個交點，這六個點圍成的區間即為實際落點可能存在的區間，求取該范圍的質心確定位置。即使當信號出現偏移，幾何表現為圓內切或者圓相離，也會保證六個點及可能的落點范圍區間的存在，該方法在這方面表現了良好的容忍度。假設三點坐標為A(xA,yA)，B(xB,yB)，C(xC,yC)將采集的RSSI信號強度代入距離預測模型計算得到相應的距離dA，dB，dC。以計算A1，B1為例，結合幾何知識得到這兩個點的相交坐標為：

同理可求得其他六點的坐標，(xA2,yA2)，(xB2,yB2)，(xC1,yC1)，(xC2,yC2)。最終計算得到盲節點坐標：

2 混合定位過程

2.1 測距模型建立過程

①錨節點以相同功率、相同周期廣播信息，信息包括自身節點ID、與匯聚節點的距離D。②匯聚節點收集信息并提取信號強度，得到{RSSI［］，D}數對，RSSI［］表示在距離D下，提取的信號強度數組。③使用高斯模型處理數據，得到初始數據。將數據作為BP模型的訓練輸入，保留訓練BP網絡各層之間的連接權值、閾值以及轉換函數等，作為定位算法的測距模型。

2.2 混合定位過程

①錨節點集合Anchor［］周期廣播自身節點ID、節點坐標。②盲節點得到{RSSI［］，POS（x，y），ID}，將該發送至匯聚節點。③從錨節點集合中選擇均值avr（RSSI［］）最接近，然后最大的三個值作為參考節點。④使用測距模型，建立錨節點的概率環形區間。⑤使用交疊定位算法實現定位，當計算出現求解外圓相交無解，或內圓相交存在解時，則表示節點實際距離要高于預測距離統計疇上界，或者低于下界。這是則使用輔助定位算法多邊界質心法完成定位。

3 實驗及結果分析

3.1 實驗設備及場所

本實驗選取的傳感器其射頻芯片為TI公司的CC2420，處理器為Atemgel128a，具備短桿狀接發收天線，傳感器操作系統采用Tinyos 2.0，匯聚節點具備串口；上位機為win7版本的筆記本；實際測試環境選擇在學校理科樓內廣場，實驗范圍設定為25 m×25 m。

3.2 實驗準備及數據預處理

3.2.1 初始功率設置

總體衰減規律：近距離傳播衰減幅度大，遠距離信號強度趨近平穩。節點最大發射功率設置不同，其信號衰減方式不同。初始功率太大，其信號強度數列方差值也大，如果初始功率太小，信號強度在實際環境中的傳播距離會受到影響。將其參數化，單點通信距離在實測環境（內廣場）下至少達到35 m，功率變化范圍為［0 dBm，31 dbm（tinyos下默認發射最大功率）］，在衰減因子一致的情況下選取方差值小的，最終設置為18 dBm。

3.2.2 節點篩選

由于無線傳感單元的元件選擇和焊接工藝不一致，在相同電壓下、相同的距離、相同功率閾值設定下實際發射功率具有差異性，隨機選擇同批節點60個，設定5s定時發送20byte測試數據，使用相同的匯聚節點接收數據，記錄RSSI強度，挑選得到25個信號強度組相似的作為實驗節點，剔除因工藝差異而產生的實驗外誤差，1個節點作為匯聚節點，12個節點作為錨節點，15個節點作為盲節點，共完成12次定位實驗。

3.2.3 天線方向確定

選擇1個聚節點作為圓心，測試節點分別在圓的六分點位置發射信號，統計匯聚節點收集到的信號集之間的差別，圓半徑從2 m變化至11 m，共測試10組數據。實驗結果統計顯示每組內信號強度基本一致，表明節點方向不對數據采集產生影響。

3.2.4 數據處理

將記錄的RSSI信號強度通過高斯模型處理，方法參照本文第二部分，濾除小概率、突發波動信號，盡量還原信號衰減規律，將處理后的信號強度作為定位實驗的實際使用值。

3.3 距離預測模型實驗

初始準備工作完成后，以匯聚節點為起點，每米放置傳感器發送信號，設置距范圍為［1 m，31 m］，共收集31組數據。將采集的31組數據分別使用Shadowing方法和BP訓練法進行建模，并加入實測數據作為對比，其最后結果如圖7所示。

圖7 信號—距離預測模型圖

Shadowing模型是比較標準的對數型曲線，反映了理論傳輸環境下的傳輸耗損；而實際的曲線呈現主體趨向是對數型，局部信號表現受干擾，不規律；BP訓練模型則既反映出了與實際情況的主體吻合，又體現出了信號局部一定波動性。

3.4 定位實驗

3.4.1 三種算法的定位效果

為了驗證本文提出的混合定位算法的性能，將該方法和文獻［18］提出的加權質心算法以及文獻［19］提出的質心算法作比較。圖8～圖10分別給出了3種方法的實際定位結果。

圖8 混合定位法實驗結果

圖9 加權質心法實驗結果

圖10 質心算法實驗結果

上三圖中五角星型節點表示布置的錨節點，空心圓圈節點表示實際盲節點位置，米字型節點表示定位預測的位置，其直觀反映了實際位置與定位位置間的差距。

3.4.2 各算法性能對比

對比12個盲節點的實際坐標，計算三種定位算法預測盲節點位置和實際位置的距離差，統計結果如表1所示：

從表1結果可計算出，在25 m×25 m的內廣場定位中，混合定位算法的平均定位誤差距離為0.839 m，加權質心算為1.016 m，質心算法的誤差為1.332 m，通過比較混合定位算法相較于加權質心算法精度提高17.2%，而比未改進的質心算法提高約37%。

3.4.3 混合定位算法中兩種方法各占比重

由于信號偏移現象，概率區間交疊法不能獨自完成定位，需要多邊界質心法補充定位，表2給出了本文提出的混合定位方法兩種方法在實際定位中所使用的情況。

表1 各算法定位距離誤差值

表2 混合定位算法中各方法使用情況

4 結論

本文針對實際環境下，以BP神經網絡訓練方式來適應隨機性強、多干擾的傳播路徑，避免去擬合Shadowing模型中參數值，即可建立較準確的信號強度—距離預測模型。通過統計實際測量值與距離預測模型的實際落點范圍，建立相關于錨節點的概率環形區間。針對定位算法的非精確性，覆蓋盲節點最大概率的落點范圍，在信號平穩的情況下，縮小區間，可以較準確的判斷出盲節點的落點區域；而當信號受到擾動較大時，采用多邊界質心法，以預估的距離為標桿，逐步擴大節點可能存在的范圍，以六點界定該區間。在本文中，界定的區域中盲節點的落點概率被認為是一致的，故而通過求取質心，最終定位盲節點。雖然算法復雜度略高，但最后實驗證明了混合算法對于實際環境具備較強適應性，以及較高的精度，符合一般的使用場景。同樣，本文算法對于范圍性粗定位需求亦具備良好效果。

［1］彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，2011：25-389.

［2］Pawel K，Javier A，Esteban E，，et al.Angle-of-Arrival Localiza?tion Based on Antenna Arrays for Wireless Sensor Networks［J］.Computers and Electrical Engineering，2010，36（6），1181-1186.

［3］Xu D Y，Liu C X.An Improved DV-Hop Localization Algorithm Based-on Local Area in Nonhomogeneous Density WSN［C］//2010 International Conference on Computational Intelligence and Software Engineering，Wuhan，Dec.10-12，2010：1-3.

［4］Wang J，Fu J Q.Research on APIT and Monte Carlo Method of Lo?calization Algorithm for Wireless Sensor Networks［C］//Interna?tional Conference on Life System Modeling and Simulation，Wuxi，Sep.17-20，2010：128-137.

［5］Le T N，Kim J，Shin Y.TDOA Localization Based on Particle Swarm Optimization in UWB Systems［J］.IEICE Transactions on Communications，2011，E94.B（7）：2013-2021.

［6］Brida P，Machaj J，Benikovsky J，et al.A New Complex Angle of Arrival Location Method for Ad Hoc Networks［C］//2010 7th Workshop on Positioning Navigation and Communication（WPNC）.Dresden：IEEE Press，2010：284-290.

［7］Goldoni E，Savioli A，Risi M.Experimental Analysis of RSSIBased Indoor Localization with IEEE 802.15.4［C］//2010 Euro?pean Wireless Conference，Lucca，Apr.12-15，2010：71-77.

［8］李同松.基于ZigBee技術的室內定位系統研究與實現［D］.大連：大連理工大學，2008：25-40.

［9］Chin-Tseng Huang，Cheng-Hsuan，Yao-Nan Lee，Jiunn-Tsair Chen.A Novel Indoor RSS-Based Position Location Algorithm Us?ing Factor Graphs［J］.IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS，2009（8）：3050-3058.

［10］陳錫劍，程良倫.基于RSSI的功率匹配定位算法的研究與實現［J］.傳感技術學報，2013，26（5）：709-714.

［11］王緩緩，宮娜娜.基于距離區間概率加權的RSSI測距方法［J］.電子科技大學學報，2013，42（6）：862-868.

［12］劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網絡修正加權質心定位算法［J］.傳感技術學報，2010，23（5）：717-721.

［13］劉政.基于接收信號強度指示的誤差自校正定位算法［J］.傳感技術學報，2014，27（7）：970-975.

［14］石曉偉，張會清.基于BP神經網絡和改進質心算法的室內無線定位技術的研宄.北京工業大學碩士學位論文，2012.6.

［15］Shih-Hau Fang，Tsung-Nan Lin.Indoor location system based on discriminant-adaptive neural network in IEEE 802.11 environ?ments［J］.IEEE Transactions on Neural Networks.2008，19（11）：1973-1978.

［16］蘭雪梅，朱健，，等.BP網絡的MATLAB實現［J］.微電腦應用，2003，19（1）：6-8.

［17］章堅武，張璐.基于ZigBee的RSSI測距研究［J］.傳感技術學報，2009.22（2）：285-288.

［18］陳維克，李文鋒，首珩，等.基于RSSI的無線傳感器網絡加權質心定位算法［J］.武漢理工大學學報，2006，20（12）：2695-2700.

［19］LuthyKA，EGrantD，HendersonTC.Leveraging RSSI for Robotic Repairof Disconnected Wireless Sensor Networks［C］//Proceed?ings of 2007 IEEE International Conference on Roboticsand Auto?mation.Rome，Italy，2007.10-14.