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

陳 翔 ，羅守山

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

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

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

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

1 ERL定位算法

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

在基于接收信號強(qiáng)度指示（RSSI）的定位算法中，己知發(fā)射節(jié)點(diǎn)的發(fā)射信號強(qiáng)度，接收節(jié)點(diǎn)根據(jù)收到的信號強(qiáng)度計(jì)算出信號的傳播損耗，利用理論和經(jīng)驗(yàn)?zāi)Ｐ蛯鬏敁p耗轉(zhuǎn)換為節(jié)點(diǎn)的位置。ERL定位算法的理論依據(jù)是RSSI可以標(biāo)示信號的強(qiáng)度，進(jìn)而可以判斷出節(jié)點(diǎn)間的距離信息，通過理論推導(dǎo)，得出未知節(jié)點(diǎn)到固定節(jié)點(diǎn)的距離，進(jìn)而達(dá)到高效定位的目的。

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

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

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

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

2 底層傳輸模型

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

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

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

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

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

3 仿真試驗(yàn)及性能評估

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

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

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

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

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

[1]屈斌，胡訪宇.高效節(jié)能的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].計(jì)算機(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.