一種高效可靠的無線傳感器網(wǎng)絡(luò)定位算法

陳 翔 ，羅守山

（1.杭州師范大學 杭州國際服務工程學院，浙江 杭州310036；2.北京郵電大學 信息工程學院，北京100876）

無線傳感器網(wǎng)絡(luò)作為一種新興技術(shù)，在工農(nóng)業(yè)、城市管理、搶險救災等許多領(lǐng)域都有重要的科研價值和應用前景，是目前學術(shù)界研究的熱點問題之一。其中，傳感器節(jié)點的定位問題是無線傳感器網(wǎng)絡(luò)中的一個基本和關(guān)鍵問題[1]。在傳感器網(wǎng)絡(luò)中，傳感器節(jié)點自身的正確定位是提供監(jiān)測事件位置信息的前提。只有在節(jié)點自身正確定位之后，才能確定傳感器節(jié)點監(jiān)測到的事件的具體位置，這需要監(jiān)測到該事件的多個傳感器節(jié)點之間相互協(xié)作，并利用他們自身的定位機制確定事件發(fā)生的位置。

近年來國內(nèi)外研究人員提出了一些定位算法。在DV-Hop定位算法[2-3]中，將節(jié)點的無線射程R作為平均每跳的距離，這對于節(jié)點分布密集且均勻的網(wǎng)絡(luò)比較適合。但當節(jié)點分布不均勻或節(jié)點密度較低時，非鄰居節(jié)點間的估計距離會比實際距離偏大，只有在各向同性的密集網(wǎng)絡(luò)中才能合理估算出每跳的平均距離。SPA算法[4]選擇網(wǎng)絡(luò)中連通度最大的節(jié)點作為坐標原點，建立全局相對坐標系。其余每個節(jié)點分別通過測距獲得鄰居節(jié)點間的距離，在各個節(jié)點建立局部坐標系統(tǒng)，通過節(jié)點間的信息交換與協(xié)調(diào)，以參考點為基準通過坐標變換(旋轉(zhuǎn)與平移)建立全局坐標系統(tǒng)。由于每個節(jié)點都要參與多次坐標變換，因此計算量和定位誤差都非常大。

本文針對目前定位算法距離值誤差較大以及低效的問題，考慮把固定錨節(jié)點之間的距離和信號強度兩種信息同時作為參考來校正每個固定錨節(jié)點的權(quán)值，彌補了DV-Hop算法和SPA算法的不足。在本文算法中，每個節(jié)點收集自身到其一跳鄰節(jié)點的RSSI值，當收集數(shù)量達到要求時，對數(shù)據(jù)進行濾波并求平均值處理。仿真結(jié)果表明，本文提出的定位算法可以降低定位誤差，具有高可用性，能夠應用于實際的無線傳感器網(wǎng)絡(luò)中。

1 ERL定位算法

在無線傳感器網(wǎng)絡(luò)中，RSSI受環(huán)境影響的程度較大，相同的節(jié)點在不同的相對位置下的RSSI值有可能相差非常大。此外，在同一環(huán)境下，不同區(qū)域或不同方向的節(jié)點，盡管距離相同，RSSI值也可能不相同。這就意味著同一個RSSI值，在同一網(wǎng)絡(luò)拓撲分布中的不同節(jié)點對間代表的距離是不同的，相應的權(quán)值也應當是不同的。如果未知節(jié)點的位置計算僅僅考慮未知節(jié)點到某個固定錨節(jié)點的RSSI值而沒有加入其他修正方法，那么由于RSSI值受環(huán)境的影響可能導致算法的誤差較大。所以，考慮把固定錨節(jié)點之間的距離和信號強度信息兩種信息同時作為參考來校正每個固定錨節(jié)點的權(quán)值，進而彌補了DV-Hop和SPA算法的不足。

在基于接收信號強度指示（RSSI）的定位算法中，己知發(fā)射節(jié)點的發(fā)射信號強度，接收節(jié)點根據(jù)收到的信號強度計算出信號的傳播損耗，利用理論和經(jīng)驗模型將傳輸損耗轉(zhuǎn)換為節(jié)點的位置。ERL定位算法的理論依據(jù)是RSSI可以標示信號的強度，進而可以判斷出節(jié)點間的距離信息，通過理論推導，得出未知節(jié)點到固定節(jié)點的距離，進而達到高效定位的目的。

本文提出的ERL定位算法總體上分為兩個階段：測距階段和定位計算階段。在測距階段的整個網(wǎng)絡(luò)自組織過程中，每個節(jié)點收集自身到其一跳鄰節(jié)點的RSSI值，當收集數(shù)量達到要求時對數(shù)據(jù)進行濾波并求平均值處理，保存最終結(jié)果。當組網(wǎng)成功后，由信標節(jié)點廣播發(fā)送定位數(shù)據(jù)幀，其中含有信標節(jié)點的ID、坐標信息、數(shù)據(jù)幀生命期、跳計數(shù)和RSSI累加值，跳計數(shù)和 RSSI累加值初始化為0。在定位計算階段中，當未知節(jié)點接收到3個或3個以上信標節(jié)點的坐標時，可以采用下面的推理方法從而提高定位的網(wǎng)絡(luò)覆蓋率，達到高效定位的目的。主要推導過程如下：

RSSIi表示未知節(jié)點M接收到固定錨節(jié)點Bi信號的RSSI平均值(單位dbm)，Pi表示未知節(jié)點 M接收到固定錨節(jié)點Bi的信號強度平均值(單位 mW)，則兩者的轉(zhuǎn)換關(guān)系如式(1)所示：

在計算未知節(jié)點與固定錨節(jié)點的距離時，以固定錨節(jié)點對之間的距離和測量的RSSI值作為參考，將固定錨節(jié)點之間的距離和信號強度信息考慮進來校正固定錨節(jié)點的權(quán)值，從而提高算法的精度。RSSIij表示固定錨節(jié)點B。接收到固定錨節(jié)點Bj信號RSSI平均值(單位dbm)，Pij表示固定錨節(jié)點 Bi接收到固定錨節(jié)點 Bj的信號強度平均值(單位mW)，則同理有:

因此未知節(jié)點到固定錨節(jié)點Bi的距離可以表示為對于所有j的可能值的平均值。

2 底層傳輸模型

為了準確評價ERL算法，需要選擇一種適合無線傳感器網(wǎng)絡(luò)底層傳輸模型，這里選擇Shadowing模型。該模型由pass loss和接收到的能量變化兩部分組成。第一部分是pass loss模型，它能夠預測出當距離為d時接收到的平均能量，表示為Pr(d)。它使用了一個接近中心的距離 d0作為參考，Pr(d)相對于 Pr(d0)的計算如下：

β是pass loss指數(shù)，它通常是由場地測量得來的經(jīng)驗值。Pass loss通常由dB作為計量單位，因此從式(4)中可以得到:

Shadowing模型的第二部分反映了當距離一定時接收到的能量的變化。它是一個對數(shù)正態(tài)隨機變量，即如果以as作為計量單位則滿足高斯分布。完整的Shadowing模型如下：

XdB是一個沒有任何意義的高斯隨機變量。式（6）也被稱為對數(shù)正態(tài)shadowing模型。根據(jù)Shadowing模型對理想環(huán)境模型進行了擴展，變成了一個富有統(tǒng)計學的模型:當節(jié)點接近通信范圍邊緣時，能否通信只能是一個隨機事件。

通過以上分析可以看出，在仿真實驗中，為了模擬現(xiàn)實的無線傳感器網(wǎng)絡(luò)的通信特性，可以使用shadowing物理通信模型，本文所提出的定位算法同樣基于該模型，為該算法的實際應用提供了較強的說服力。

3 仿真試驗及性能評估

本節(jié)利用NS2仿真工具分析上文提出的算法性能，設(shè)計實驗場景如下：在一個500 m×500 m的區(qū)域內(nèi)按均勻分布隨機放置400個無線傳感器節(jié)點，設(shè)定錨節(jié)點和普通節(jié)點的通信半徑R都為10 m，網(wǎng)絡(luò)節(jié)點連接度為8.28，每次定位需要的成功樣本數(shù)N為100。以所有待定位節(jié)點的估計位置與真實位置的平均誤差作為性能評估的標準，平均誤差對通信半徑R進行歸一化。每個仿真結(jié)果在同一環(huán)境下運行10次取平均值。

為了對本文所提出的聯(lián)合優(yōu)化方法ERL做出性能評價，需要選擇一種路由協(xié)議作為評價的“載體”?？紤]到Direct Diffusion協(xié)議[5]是一種按需路由協(xié)議，協(xié)議的設(shè)計適合于無線傳感器網(wǎng)絡(luò)的應用，便于性能的比較，這里做出如下的標記：將原始基于HOP算法的命名為HOP-DD，將基于SPA算法命名為SPA-DD，將基于本文提出的ERL算法命名為ERL-DD。

圖1所示為定位誤差隨錨節(jié)點比例的變化情況?？梢钥闯觯贖OP的抽樣效果要好基于SPA的抽樣，因為基于HOP的抽樣對樣本點的過濾更加嚴格，得到的樣本點的值也更加接近真實值。理論上說越嚴格的過濾條件得到的樣本點也會越好，但是相應地會使需要抽樣的次數(shù)增加，才能滿足樣本數(shù)量的要求。ERL-DD則使用了本文提出的定位算法，考慮了固定錨節(jié)點之間的距離，其效果優(yōu)于HOP-DD和SPA-DD。

圖2所示為不同個數(shù)節(jié)點下的定位誤差分布圖，DV-Hop由于使用兩次洪泛而使其節(jié)點間通信量過大，并且利用跳段距離代替直線距離存在一定的誤差。從圖中可以看到，基于本文所提出的ERL算法在相同節(jié)點個數(shù)下，優(yōu)于基于SPA和HOP的定位算法。主要原因在于DV-HOP算法在節(jié)點間消耗大量的能量，而且定位誤差大，SPA算法隨著網(wǎng)絡(luò)壽命的變短及其不穩(wěn)定，定位誤差大。本文所提出的算法基于RSSI定位，可以節(jié)省定位能耗，提高定位精確度。

本文分析了定位算法的研究現(xiàn)狀，針對無線傳感器網(wǎng)絡(luò)的通信鏈路存在著高丟失率、非對稱性等特點，設(shè)計了一個高效可靠的定位算法，并將此算法應用于Direct Diffusion協(xié)議中，仿真結(jié)果表明本文提出的定位算法可以節(jié)省定位能耗，提高定位精度，具有高可用性，對無線傳感器網(wǎng)絡(luò)的實際應用具有一定的參考價值。

[1]屈斌，胡訪宇.高效節(jié)能的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].計算機仿真，2008，25(5)：113-116.

[2]SON D，KRISHNAMACHARI B，HEIDEMANN J.Experimental study of the effects of transmission power control and blacklisting in wireless sensor networks.In IEEE SECON，2004：289-298.

[3]YANG S W，YI J Y，CHA H J.HCRL：a hop count-ratio based localization in wireless sensor networks sensor[A].Proceedings of the 4th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks[C].TEEE Publish House.2007：31-40.

[4]ELEONORA S，EMILIE H，MANFRED N.Study of the behaviour of a catalytic ceramic candle filter in a lab-scale unit at high temperatures[J].International Journal of Chemical Reactor Engineering，2010：135-142.

[5]KHAN S A，MULVANEY R L，HOEFT R G.Direct-diffusion methods for inorganic-nitrogen analysis of soil.Soil Science Society of America Journal[J].2000，64(3)：1083-1089.