基于連通度和加權(quán)校正的移動節(jié)點定位算法

侯 華，施朝興

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

無線傳感器網(wǎng)絡(luò)在家居、救災(zāi)、環(huán)境、醫(yī)療等諸多領(lǐng)域中有著非常廣闊的應(yīng)用前景和巨大的研究價值［1］，研究內(nèi)容涉及多個方面，包括節(jié)點定位算法、路由算法、數(shù)據(jù)融合、拓?fù)淇刂啤⒕W(wǎng)絡(luò)安全等，其中節(jié)點定位問題是近年來無線傳感器網(wǎng)絡(luò)中的研究難點和熱點［2］。

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

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

1 基于連通度和加權(quán)校正的移動節(jié)點定位算法

1.1 基于連通度的信標(biāo)選擇

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

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

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

1.2 自校正測距算法

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

1.2.1 RSSI 測距模型

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

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

在實際環(huán)境中，常采用對數(shù)－常態(tài)分布模型，即

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

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

1.2.2 距離自校正模型

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

圖1 RSSI 與距離曲線圖

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

式中:(xi，yi)為信標(biāo)節(jié)點Bi坐標(biāo);(xj，yj)為Bi通信范圍內(nèi)信標(biāo)Bj坐標(biāo)。

同樣可以得到測量距離dij，定義信標(biāo)節(jié)點Bi的加權(quán)校正系數(shù)λ 為

式中:ρj為加權(quán)因子;n 為信標(biāo)節(jié)點Bj的個數(shù);dij為Bi與Bj的測量距離。

在未知節(jié)點定位時，得到未知節(jié)點與某信標(biāo)節(jié)點間測量距離為d'，距未知節(jié)點最近的信標(biāo)節(jié)點的校正系數(shù)為λ，則該信標(biāo)節(jié)點與未知節(jié)點間校正距離d0為

1.3 定位計算

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

其估計結(jié)果為

其中

2 仿真結(jié)果與分析

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

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

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

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

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

圖3 信標(biāo)個數(shù)對定位誤差的影響

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

3 總結(jié)

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

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

［2］韓毅剛，王大鵬，李琪，等.物聯(lián)網(wǎng)概論［M］.北京:機械工業(yè)出版社，2012:128－129.

［3］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，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，F(xiàn)ANG 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］孫燕，尚軍亮，劉三陽.基于采樣優(yōu)化的蒙特卡羅移動節(jié)點定位算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32(9):2001－2004.

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

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

［11］朱曉娟，孟祥瑞.基于加權(quán)質(zhì)心的無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法［J］.計算機工程與科學(xué)，2011，33(11):15－19.

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

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

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

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

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