基于連通度和加權校正的移動節點定位算法

侯 華，施朝興

(河北工程大學a.裝備制造學院;b.信息與電氣工程學院，河北 邯鄲056038)

無線傳感器網絡在家居、救災、環境、醫療等諸多領域中有著非常廣闊的應用前景和巨大的研究價值［1］，研究內容涉及多個方面，包括節點定位算法、路由算法、數據融合、拓撲控制、網絡安全等，其中節點定位問題是近年來無線傳感器網絡中的研究難點和熱點［2］。

無線傳感器網絡定位算法依據在定位時是否依賴節點間距離可以分為測距算法和非測距算法［3］。測距算法需要額外的硬件測量節點間的距離，定位精度相對較高，常見測距算法有接收信號強度指示(RSSI)［4］、信號到達時間(TOA)［5］、信號到達角度(AOA)［6］等;非測距算法利用節點間的連通性估計節點位置，如距離向量－跳段算法、質心算法等，不需要額外添加硬件，定位成本低，但定位精度也相對較低，所以在精度要求不高的應用中具有優勢。

跟蹤定位等動態網絡應用中未知節點一般具有一定的移動特性，上述靜態傳感器網絡定位算法不滿足精度要求，需要設計出更有效的移動節點定位算法。Hu Ling－xuan 等人基于蒙特卡羅隨機化采樣提出了適用于移動節點定位跟蹤的MCL 算法［7］，提供了一種很好的研究思路。在此算法的基礎上，研究人員對MCL 算法進行了改進。孫燕等人利用曲線擬合求出后驗密度分布取值相對較大區域，并改進了樣本節點的權值，減少了定位所需的樣本數［8］。李偉等人提出一種基于RSSI 的改進蒙特卡羅定位算法，提升了預測的準確率和定位速度，降低了節點能耗［9］。闊永紅等人提出利用鄰居節點廣播信息進行定位的算法，提升了節點的利用效率［10］。本文提出了一種基于連通度和加權校正的移動節點定位算法，定位精度與蒙特卡羅算法相比有明顯的提升，并且在一定參數條件下與改進的蒙特卡羅算法具有同等精度。

1 基于連通度和加權校正的移動節點定位算法

1.1 基于連通度的信標選擇

無線傳感器網絡中，固定信標節點周期性地向周圍廣播自身位置信息和身份信息。未知節點移動過程中，會收到來自多個信標節點的廣播，通信范圍內的信標也在時刻變化，所以將時間劃分為若干時隙，在一個時隙T 內，未知節點監聽并記錄信標節點的廣播信息，時隙結束時利用連通度公式計算各信標節點與未知節點間的連通度，連通度［11］定義為

式中:Ci表示信標Bi與未知節點間連通度;nr表示一個時隙T 內，未知節點接收到來自信標Bi的廣播信息數目;ns表示一個時隙T 內，信標Bi發送的位置信息數目。連通度表示一個時隙T 內，各信標節點與未知節點之間的連通性。連通度為0，表示信標Bi與未知節點不連通;連通度為1，表示信標Bi在T 內一直與未知節點連通。

依據連通度值的大小，選取連通性最好的a 個信標節點。這里不采用固定連通度閾值選取信標的方法，而是采用信標個數的選取方法，這是為了保證在連通性不好或信標密度小時也有足夠的信標數來進行定位計算。

1.2 自校正測距算法

RSSI 測距算法由于硬件設備簡單、通信開銷小、成本低、易實現而受到廣泛關注，但是它易受外界環境影響，比如會因為反射、多經、非視距等問題產生較大傳播損耗，使RSSI 測距精度降低，最終使得定位精度降低。所以如何提高RSSI 精度是一個關鍵問題。

1.2.1 RSSI 測距模型

文獻［12］中，詳細介紹了無線電的傳播特性。理想狀況下，無線電自由空間傳播損耗模型為

式中:PL(d)為信號經過距離d 后的路徑損耗，單位為dB;d為發射節點到接收節點的直線距離，單位為km;f 為發射頻率，單位為MHz;n 為路徑損耗因子，范圍為2～4。

在實際環境中，常采用對數－常態分布模型，即

式中:P 為發射功率;G 為天線增益;d0=1 m;X 是均值為0、標準差為4～10 的高斯隨機變量。

結合式(2)～(4)，即可計算出測量距離d。并且，由此可以得出接收信號強度與距離曲線圖，如圖1 所示。從圖中可以分析出，隨著距離的增加，同等大小的RSSI 偏差產生的距離誤差也在增大，所以應當盡量選取距未知節點較近的信標參與定位計算。在計算時，較遠信標比較近信標包含更大RSSI 誤差，為此，引入文獻［13－14］中RSSI 自校正的思想，修正測量距離的同時，降低距離較遠的信標的作用程度。

1.2.2 距離自校正模型

受實際環境中障礙物等因素影響，RSSI 并不能滿足分布模型，需要對RSSI 值修正才能降低定位誤差。距未知節點最近的信標節點與它有著相似的環境，可以利用對該信標測距時產生的誤差來修正對未知節點進行測距時產生的誤差。

圖1 RSSI 與距離曲線圖

首先，求出各信標的校正系數。當信標節點廣播自身信息后，信標節點Bi即可獲得通信范圍內信標Bj的位置和兩點間的RSSI。信標節點的位置是已知的，根據式(5)兩點間距離公式可求出它與通信范圍內各信標間實際距離。

式中:(xi，yi)為信標節點Bi坐標;(xj，yj)為Bi通信范圍內信標Bj坐標。

同樣可以得到測量距離dij，定義信標節點Bi的加權校正系數λ 為

式中:ρj為加權因子;n 為信標節點Bj的個數;dij為Bi與Bj的測量距離。

在未知節點定位時，得到未知節點與某信標節點間測量距離為d'，距未知節點最近的信標節點的校正系數為λ，則該信標節點與未知節點間校正距離d0為

1.3 定位計算

移動節點在某一位置獲得3 個或3 個以上的與其通信的信標節點，利用最小二乘法［15］可估計出未知節點坐標。假設未知節點坐標為(x，y)，通過連通度選擇后得到的定位信標m 個，未知節點到第i 個信標(xi，yi)的校正距離為d0i，可得方程組估計為

其估計結果為

其中

2 仿真結果與分析

本文在MATLAB 環境下進行仿真，并同MCL 和改進的MCL 算法［16］進行了比較，并且將差分校正和加權校正方法進行了比較。無線傳感器區域設置為100 m×100 m，固定信標節點在區域中分布均勻，移動節點以1 m/s 的速度做勻速運動。默認的仿真參數為:信標節點個數為36，通信半徑為65 m，衰減因子為2.45，載波頻率為2 400 MHz，高斯隨機變量X 的標準差為5，天線增益為1 dB。定位過程重復進行100次，仿真結果取平均值。節點位置誤差計算采用絕對誤差計算公式，即

式中:N 為仿真次數;r 為節點通信半徑;(xi，yi)為未知節點的估計位置;(x，y)為未知節點的真實位置。

節點通信半徑的大小對定位誤差的高低起到比較大的作用。如圖2 所示，隨著通信半徑的增大，4 種定位算法的定位誤差都在減小。對于蒙特卡羅算法，這是由于通信半徑的增大使得觀測信息隨之增多，排除了部分無效粒子，但是當r 增大到一定程度后，兩種蒙特卡羅算法的誤差變化趨于穩定，并且改進的MCL 算法明顯好于傳統MCL。基于連通度的差分校正和加權校正算法，隨著r 的增大，誤差先是減小，這是由于r 的增大使得未知節點通信范圍內的信標節點逐漸增多，得到了更多的有用位置信息使得定位精度增大。之后，隨著r 的增大，誤差不再減小，反而有了增大的趨勢，這是由于r 的增大包含進了更多離未知節點較遠的信標節點。由圖1 可知，遠距離節點包含了更大的RSSI 誤差，此時RSSI 誤差增大作用超過了位置信息增加的作用。從圖2 中可以看出加權校正優于差分校正，而且在r ＞65 m 后的誤差增大趨勢小于差分校正，這是因為加權校正降低了遠距離信標節點的權重，減小了RSSI 誤差增大對定位精度的影響。整體來看，基于連通度和加權校正的移動節點定位算法與改進的蒙特卡羅算法在r 為55～75 m 間有著相近的精度，但是前者的算法計算量小于后者，有更好的應用性。

在信標節點密度對定位誤差的影響實驗中，依次改變信標節點個數，得到如圖3 所示的仿真結果。隨著信標節點的增多，未知節點獲得了更多的位置信息，4 種定位算法的誤差穩定減小，并趨于平緩。而且，基于連通度和加權校正的移動節點定位算法相比傳統MCL、基于差分校正的移動節點定位算法有更小的定位誤差，能夠達到與改進的MCL 算法相近的精度。

圖2 通信半徑對定位誤差的影響

圖3 信標個數對定位誤差的影響

另外，由上述信標選擇、RSSI 測距誤差校正和定位計算的過程可以看出:假設n 為傳感器節點的平均鄰居節點個數，對于基于連通度和加權校正的移動節點定位算法，算法的時間頻度是關于n 的一次函數，那么很容易得出該定位算法的算法復雜度為O(n)，計算量小于蒙特卡洛算法，這是因為蒙特卡羅算法的精度依賴于大量的采樣樣本和多次的迭代計算，使得計算量增加，定位速度變慢。

3 總結

本文提出了一種基于連通度和加權校正的移動節點定位算法。通過保障信標節點與未知節點間的連通性，校正RSSI測距誤差，降低遠距離信標RSSI 大誤差的影響，實現定位精度的提升。仿真實驗表明，該算法相比蒙特卡羅算法，相對平均定位誤差減小了約10%～30%;隨著節點通信半徑的增大，定位誤差逐漸減小，當r 在60～70 m 范圍內，定位誤差達到最小;隨著信標密度的增加，定位誤差也隨之減小，當信標密度達到一定數值后，定位誤差變化趨勢趨于平緩。

［1］張浩，呂真，連衛民，等.采用入侵雜草優化算法的WSN 定位精度提高方法［J］. 電視技術，2014，38(3):146－149.

［2］韓毅剛，王大鵬，李琪，等.物聯網概論［M］.北京:機械工業出版社，2012:128－129.

［3］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005:142－157.

［4］KALTIOKALLIO O，BOCCA M. Real－time intrusion detection and tracking in indoor environment through distributed RSSI processing［C］//Proc.IEEE 17th International Conference on Embedded and Real－Time Computing Systems and Applications. Toyama:IEEE Press，2011:61－70.

［5］XU Enyang，DING Zhi，DASGUPTA S. Target tracking and mobile sensor navigation in wireless sensor networks［J］.IEEE Trans.Mobile Computing，2013，12(1):177－186.

［6］CHANG D C，FANG Mengwei. Bearing－only maneuvering mobile tracking with nonlinear filtering algorithms in wireless sensor networks［J］.IEEE Systems Journal，2014，8(1):160－170.

［7］HU Lingxuan，EVANS D. Localization for mobile sensor networks［C］//Proc. the 10th Annual International Conference on Mobile Computing and Networking. Philadelphia:IEEE Press，2004:45－57.

［8］孫燕，尚軍亮，劉三陽.基于采樣優化的蒙特卡羅移動節點定位算法［J］.系統工程與電子技術，2010，32(9):2001－2004.

［9］李偉，丁勇，于春娣，等.一種基于RSSI 的改進蒙特卡羅定位算法［J］.計算機應用與軟件，2013，30(12):280－283.

［10］闊永紅，周文文，陳健. 避免非視距影響的蒙特卡羅移動節點定位方法［J］.西安電子科技大學學報:自然科學版，2014，41(1):6－12.

［11］朱曉娟，孟祥瑞.基于加權質心的無線傳感器網絡移動節點定位算法［J］.計算機工程與科學，2011，33(11):15－19.

［12］李建東，郭梯云，鄔國揚.移動通信［M］.西安:西安電子科技大學出版社，2006.

［13］王新芳，張冰，馮友兵.基于粒子群優化的改進加權質心定位算法［J］.計算機工程，2012，38(1):90－95.

［14］程秀芝，朱達榮，張申，等. 基于RSSI 差分校正的最小二乘－擬牛頓定位算法［J］.傳感技術學報，2014，27(1):123－127.

［15］朱敏，劉昊霖，張志宏，等.一種基于DV－HOP 改進的無線傳感器網絡定位算法［J］.四川大學學報:工程科學版，2012，44(1):93－98.

［16］單志龍，劉蘭輝，張迎勝，等.一種使用灰度預測模型的強自適應性移動節點定位算法［J］.電子與信息學報，2014，36(6):1492－1497.