基于通用相關(guān)的無線傳感網(wǎng)絡(luò)節(jié)點快速定位算法*

陳佳媛，楊 丹

（常州工學(xué)院計算機(jī)信息工程學(xué)院，江蘇 常州 213032）

0 引 言

無線傳感器網(wǎng)絡(luò)中，許多的應(yīng)用場合都需要有節(jié)點自身的位置信息，以便向用戶提供有價值的服務(wù)，沒有節(jié)點自身位置信息的監(jiān)測數(shù)據(jù)是沒有什么實際意義的[1]。例如，在倉儲式超市中，對商品進(jìn)行分類存放，根據(jù)存放類別再劃分區(qū)域，同時在購物車上安置一個無線收發(fā)器，配置WSN每一個貨架節(jié)點位置信息，顧客在購物時，就可以根據(jù)所需要的貨物與自己的購物車的位置信息，快速準(zhǔn)確找到所需要的貨物。再如，對于天然氣管道監(jiān)測的應(yīng)用，如果在某一處有漏氣點，人們最關(guān)心的首要問題是漏氣點的位置信息，以便進(jìn)行處置。因此，節(jié)點的位置信息對于很多場景是至關(guān)重要的。

1 研究背景和意義

隨著信息技術(shù)向物聯(lián)智能化網(wǎng)絡(luò)方向的發(fā)展，現(xiàn)實的物理世界和以計算機(jī)控制技術(shù)為核心的物聯(lián)網(wǎng)融合需求越來越迫切，定位則成為連接物理世界和計算機(jī)網(wǎng)絡(luò)技術(shù)的橋梁紐帶[2]。

定位是利用電磁波信號確定目標(biāo)的位置信息，位置信息是確定被監(jiān)測目標(biāo)與場景位置，方向等信息的最直接方法，是移動計算、物聯(lián)網(wǎng)技術(shù)、普適計算等基于地理位置信息服務(wù)的基礎(chǔ)。位置信息對物聯(lián)網(wǎng)技術(shù)應(yīng)用和基于位置信息服務(wù)的移動計算領(lǐng)域有著非常重要意義。因此，無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)也就成為學(xué)術(shù)界研究的熱點之一[3]。

無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)主要分成基于測距的定位技術(shù)和非測距的定位技術(shù)二大類?；跍y距定位技術(shù)主要包括：信號強(qiáng)度定位（Received Signal Strength Indication，RSSI）算法，時間差定位（TIme difference of Arrival，TDOA）算法，到達(dá)時間定位（TIme of Arrival，TOA）算法，以及到達(dá)角度定位（Arrival Of Angle，AOA）算法。這一類算法主要是通過傳感器節(jié)點配備的測量電路硬件以及算法，精確測量目標(biāo)距離及方位來實現(xiàn)節(jié)點定位，定位精度高。非測距定位主要包括：基于網(wǎng)絡(luò)中跳數(shù)的 DV-HOP（Distance Vector，HOP）定位算法，基于網(wǎng)絡(luò)連通性質(zhì)心的Amorphous算法，以及基于區(qū)域劃分的（Approximare Point In Triangulation Test）APIT定位算法。這些算法是利用節(jié)點連通性和路由交換信息等技術(shù)，估算未知節(jié)點與信標(biāo)節(jié)點間的距離，從而實現(xiàn)定位。該類算法無需依托硬件支持。因此，可以減少開支和功耗，但估算節(jié)點間距離時會產(chǎn)生較大誤差，定位精度較低[3-5]。

2 微弱信號檢測

在野外惡劣環(huán)境下，定位信號往往被淹沒在噪聲中。此時，便需要有從噪聲中檢測定位信號的方法和技術(shù)。根據(jù)定位信號自身具有周期性和噪聲信號隨機(jī)性這些特點，通過自相關(guān)或互相關(guān)檢測算法，應(yīng)用于微弱定位信號的相關(guān)檢測中，從而實現(xiàn)從噪聲中提取周期性定位信號，得到精確的定位數(shù)據(jù)，達(dá)到定位目的[6-7]。

2.1 互相關(guān)算法的工作原理

互相關(guān)測距是一種實時動態(tài)測量方式?；竟ぷ髟硎牵杭す獍l(fā)射器向探測目標(biāo)發(fā)射一周期性測量信號（可根據(jù)探測距離確定測量信號波長），測量信號碰到目標(biāo)后，被反射回來形成回波信號，然后將這二路信號進(jìn)行互相關(guān)分析處理，將距離的測量轉(zhuǎn)化成對這二路信號時間間隔（て）的測量。圖1所示為激光互相關(guān)測距示意圖。圖1中：S是被測目標(biāo)與激光發(fā)射器和接收器的距離。て為激光傳播的延時。

圖1 激光互相關(guān)測距示意圖

激光從發(fā)射器發(fā)射周期性探測波信號并以一定的波速傳播。當(dāng)探測波遇到目標(biāo)物后，探測波將會發(fā)生反射現(xiàn)象，部分探測波從原路返回至接收器。因此，根據(jù)激光從發(fā)射探測波起到接收反射回來探測波的時間差。再加上已知環(huán)境中探測波的傳播速度，就可以計算出激光傳播的距離。從而計算出目標(biāo)的距離。

2.2 通用互相關(guān)法計算延時

互相關(guān)法計算延時て，可以通過求二路信號的互相關(guān)值來估算。設(shè)S1（t）為發(fā)射器的發(fā)射信號。S2（t）為接收器接收到的信號。D是經(jīng)過傳播后的延時，n（t）是均值為0，方差為1的高斯白噪聲。則：

其中，α為S1（t）經(jīng)傳播后的衰減，為計算方便，不妨設(shè)α=1。

由于噪聲與信號互不相關(guān)，所以式（3）中RS1n（τ）=0。

由式（3）可知，S1（t），S2（t）互相關(guān)函數(shù)取得最大值時，RS1S1（τ-D）也取得最大值。而 RS1S1（τ-D）≤RS1S1（0），所有取得最大值時的て，即為延時D，即：τ=D 時 RS1S1（τ）取得最大值。

當(dāng) S1（t），S2（t）是緊密相關(guān)的信號時，RS1S2（τ）將會有一個很突出的相關(guān)峰出現(xiàn)，圖 2為S1（t）與 S2（t）相關(guān)函數(shù)仿真波形。

圖2 為 S1（t）與 S2（t）相關(guān)函數(shù)仿真波形

3 快速互相關(guān)峰值搜索算法

通過D/A對采集的信號數(shù)字化，其互相關(guān)函數(shù)的表達(dá)式為：

式中，N為積分區(qū)間上的采樣數(shù)據(jù)總數(shù)，τj為τ的取值序列，τj的取值間隔與數(shù)據(jù)采樣間隔相同。

若采集數(shù)字信號經(jīng)相關(guān)處理得到τ0后，傳播延時可由式（5）求出：

式中，fs為采樣頻率，C為信號傳播速度。

式（4）中，j每變化一次，RS1S2（τj）就需要重新計算一次，故RS1S2（τj）的計算工作量是非常大的。

實際計算時，由于求 S1（t），S2（t）相關(guān)函數(shù)的過程是乘和加的運(yùn)算。若不進(jìn)行算法改進(jìn)，則計算工作量很大。例如：在采樣點數(shù)為512時，做一次延時計算則需要1 024×1 024次乘和加的運(yùn)算。由于計算工作量大，造成定位的實時性受到影響，因而不實用。雖然可以采用降低采樣率，減少計算次數(shù)的方法來提高運(yùn)算速度，但這會造成延時的估計誤差，達(dá)不到預(yù)期精度。通過對相關(guān)函數(shù)波形（見圖2）分析可以看出，互相關(guān)法求延時的過程，實際上就是找互相關(guān)函數(shù)最大值的過程。而在互相關(guān)結(jié)果附近存在明顯的最大峰特性，因而采用一定步長點數(shù)找互相關(guān)峰是一種快速有效的方法。其原理是：對采集的信號求互相關(guān)時，點數(shù)不是逐點的變化，而是一次進(jìn)行多個點的跳躍計算，如每次進(jìn)行n個點的跳躍計算，找出相關(guān)峰值存在的一個小區(qū)間，然后在該小區(qū)間再找出最大峰值位置。再以已經(jīng)找到的最大點為中心，左右各掃描n-1個點，和已經(jīng)求得的最大值比較，以確定下一個搜索中心。這樣既可以減少計算點數(shù)，加快計算速度，又可以保證測量精度。

具體實現(xiàn)方法：在對采樣得到的信號序列求相關(guān)時。采用“不定步長峰值搜索”進(jìn)行互相關(guān)函數(shù)最大峰值確定，也就是求互相關(guān)峰值時，點數(shù)不是逐點的變化，而是一次進(jìn)行多個點的跳躍式計算。例如：第1次進(jìn)行n個點的跳躍式計算，找到相關(guān)峰值存在的一個區(qū)間，第二次進(jìn)行n/2個點的跳躍式計算，找到相關(guān)峰值存在的一個較小的區(qū)間。依次數(shù)推，直到步長為1。最終求出相關(guān)峰值的值及位量。改進(jìn)的算法表達(dá)式為：

具體實現(xiàn)步驟如下：

第 1 步：取步長為 n（n=2k），以 n 步長在 Rxy（n）中取出對應(yīng)元素，組成新的序列RxyN（n），在新序列RxyN（n）中找出最大值MN及其位置LMN。

11xy再以LMN為中心，以n1為新的步長，取出對應(yīng)元素，組成新序列 RxyN1（n），再在新序列 RxyN1（n）中，再次找出最大值MN1及位置LMN1。

22xy中再次以LMN1為中心，以n2為新的步長，取出對應(yīng)元素，組成新序列RxyN2（n），再次在序列RxyN2（n）中，再一次找出最大值MN2及其位置LMN2。

以此類推，直至步長為1的序列搜索到最大值為止。便可確定互相關(guān)函數(shù)的最大值及對應(yīng)位置，這樣的算法可以使互相關(guān)的計算量減少到原

算法流程圖如圖3所示，其中Max_Value為記錄最大值的變量，Max_P為記錄最大值所在的位置，max_P_tem為找到的最大值點位置的臨時變量，step_k為搜索步長變量，step_k_tem為步長的臨時變量。

圖3 算法流程

4 實驗及仿真結(jié)果分析

利用Matlab進(jìn)行算法仿真，仿真中，用調(diào)頻（Frequency Modulation，F(xiàn)M）信號疊加上均值為“0”，方差為“1”的高斯白噪聲，且信噪比（Signal-noiseRatio，SNR）為2的條件下進(jìn)行仿真，仿真程序如下：

圖4為延時d=30的仿真圖。通過對改進(jìn)算法仿真可以看出，理論上的延時與仿真得到的延時完全吻合，取得了非常好的效果。經(jīng)實驗，在采樣點為512的情況下，一次通常的互相關(guān)計算時間為2 s，而改進(jìn)算法，若K=2時，計算時間為0.25 s。若K=3時，計算時間為31.3 ms，與理論值很吻合。同時證明，采用此種快速計算方法具有很實用的價值。

圖4 延時d=30的仿真圖

5 結(jié) 語

本文針對通用互相關(guān)求延時計算量大的問題，提出了“不定長峰值搜索”改進(jìn)算法，并進(jìn)行了MatLab仿真和實驗。仿真和實驗結(jié)果表明，改進(jìn)后的算法明顯優(yōu)于改進(jìn)前的通用互相關(guān)算法。改進(jìn)后的算法性能優(yōu)越，在保證計算精度的情況下，極大地提高了計算速度，具有很好的實用性及廣闊的市場應(yīng)用前景。