基于MCL算法的無線傳感網(wǎng)絡節(jié)點定位技術

引言

無線傳感器網(wǎng)絡的應用中，位置信息是節(jié)點采集數(shù)據(jù)時不可缺少的部分，沒有位置信息的監(jiān)測信息通常是毫無意義的。確定事件發(fā)生的位置或采集數(shù)據(jù)的節(jié)點位置是無線傳感器網(wǎng)絡最基本的功能之一。為了能夠提供有效的位置信息，隨機布置的傳感器節(jié)點在網(wǎng)絡部署完成后必須能夠確定自身所在的位置。一般的定位算法分類為基于距離定位算法和距離無關定位算法�；�于距離的定位能夠?qū)崿F(xiàn)節(jié)點的精確定位，但往往對節(jié)點的硬件要求較高。出于硬件成本、能耗等方面的考慮，使用距離無關(Range-free)的節(jié)點定位技術可不需要測量節(jié)點之間的絕對距離或者方位，降低了對節(jié)點的硬件要求，但定位誤差相應有所增加。

無線傳感器網(wǎng)絡的節(jié)點定位策略通常使用少量位置已知的信標節(jié)點．其它位置未知的普通節(jié)點從它們接收到的信息估計自己所處的位置�，F(xiàn)有節(jié)點定位方法大多采用上述策略，典型的Range-free定位算法主要包括：質(zhì)心定位、A-morphous、SPA(self-positioning algorithm)、凸規(guī)劃、APS(adhoc positioning system、APIT等。然而這些方法都沒有考慮節(jié)點(包括普通節(jié)點和信標節(jié)點)具有位置移動性的網(wǎng)絡情形。節(jié)點的移動性會導致定位過程變得更加困難而且復雜。本文使用Monte Carlo定位(MCL)算法來解決節(jié)點具有移動性的無線傳感器網(wǎng)絡的節(jié)點定位問題，并針對MCL算法的一些應用限制進行了改進。

l MCL定位算法

MCL算法的核心思想是利用一系列加權采樣值表示可能位置的后驗概率分布，目的在于確定節(jié)點所在可能位置的后驗概率分布。算法每一步都包括位置預測和位置更新兩個階段。位置預測階段是利用m個加權采樣值對后驗概率分布進行描述的過程，位置更新階段則是通過重要性采樣操作對其進行及時不斷更新，采樣值的權重值從O和l中取值。

MCL，定位算法的基本步驟：

1．1 位置估計

無線傳感器網(wǎng)絡節(jié)點的移動定位問題可以在如下狀態(tài)空間內(nèi)描述。以￡表示離散時間，lt表示f時刻節(jié)點的位置分布，Dt表示節(jié)點在t-1t時刻到t時刻之間接收到的來自信標節(jié)點的觀測值。轉(zhuǎn)換方程p(lt|lt-1)表示基于節(jié)點先前位置對其當前所在位置的估計。觀測方程p(lt，Ot，)表示在給定觀測值的情況下節(jié)點位于位置lt的概率。算法的目標是對節(jié)點位置的濾波分布p(lt|O0,O1,…，Ot)隨時間進行反復估計。用一組采樣值Lt(N個)表示節(jié)點的位置分布lt，而且每一時間段內(nèi)算法要對采樣序列進行反復計算，由于Lt-1是對先前所有觀測值的一個集中反映，因此僅使用Lt-1和Ot就可以計算出lt。

位置估計算法的實現(xiàn)流程：

(1)初始化。節(jié)點最初不具備任何關于其自身所在N個位置的先驗知識，需要對其進行初始化操作(N表示算法執(zhí)行過程中所要維持的采樣數(shù))。

L0=[節(jié)點部署區(qū)域內(nèi)隨機選擇的N個可能位置]

(2)循環(huán)計算。根據(jù)Lt-1、上一時間段內(nèi)節(jié)點的可能位置序列以及新的觀測值Ot計算出節(jié)點新的可能位置Lt。

預測：

在算法起始階段節(jié)點對其所在的位置沒有任何先驗知識。因此可由質(zhì)心算法估計初始位置。質(zhì)心算法的核心思想是：普通節(jié)點以所有在其通信范圍內(nèi)的信標節(jié)點的幾何質(zhì)心作為自己的估計位置。其實現(xiàn)過程非常簡單：信標節(jié)點向鄰居節(jié)點廣播一個信標信號，信號中包含有信標節(jié)點自身的ID和位置信息。當位置未知的普通節(jié)點接收到來自信標節(jié)點的信標信號數(shù)量超過某一個預設的門限值后，該節(jié)點認為與此信標節(jié)點連通，并將自身位置確定為所有與之連通的信標節(jié)點所組成的多邊形的質(zhì)心。

初始位置確定后的每一時間段內(nèi)．位置序列都會根據(jù)節(jié)點的運動和新的觀測信息進行更新。節(jié)點位置的估計可以通過計算集合L內(nèi)節(jié)點的所有可能位置的平均值獲得。

1．2 位置預測

在MCL算法位置預測階段，節(jié)點從前一階段計算出的一組可能位置Lt-1開始，對每個采樣值應用節(jié)點移動模型從而獲得一組新的采樣值Lt。假設節(jié)點的移動速度和方向未知，而只知道其速度值小于Vmax那么，如果lit-1是節(jié)點的一個可能位置，那么節(jié)點所在的當前可能位置則位于以lit-1為圓心、半徑為Vmax的圓形區(qū)域內(nèi)。如果用d(l1,l2)表示兩點l1和l2之間的歐幾里德幾何距離．而且節(jié)點的移動速度在區(qū)間[0，Vmax]上服從均勻分布，那么節(jié)點基于先前位置的當前位置估計的概率分布可以通過以下均勻分布的形式給出。

因此，在預測階段計算出的節(jié)點可能位置序列R就是以點集Lt-1中的任意一點為圓心且半徑為Vmax的圓形區(qū)域。

1．3 位置濾波

在濾波階段，節(jié)點需要根據(jù)所獲得的新觀測值濾除不可能的位置信息。為了便于描述和分析，假設在t時刻每個位于信標節(jié)點無線射程范圍內(nèi)的節(jié)點都可以偵聽到來自信標節(jié)點的位置信息廣播。在實際的網(wǎng)絡部署情況下，需要考慮網(wǎng)絡沖突并解決消息丟失的問題。

如圖l，節(jié)點在t0時刻由位置l0開始移動，并在t1時刻到達位置l1，節(jié)點離開區(qū)域I并到達區(qū)域Ⅱ，但始終在區(qū)域Ⅲ內(nèi)。到達節(jié)點和離開節(jié)點都為節(jié)點的位置估計提供信息，節(jié)點知道在t0時刻位于以如為圓心且半徑為r的圓形區(qū)域內(nèi)的信標節(jié)點，在t1時刻并不在l1為圓心且半徑為r的圓形區(qū)域內(nèi)。

圖2描述了節(jié)點的位置濾波條件。圖中。S表示節(jié)點N能偵聽到的所有信標節(jié)點分組。T表示節(jié)點N的鄰居節(jié)點可以偵聽到而節(jié)點N本身無法偵聽到的全部信標節(jié)點。因此，節(jié)點位置l的濾波條件可以由式(2)表示。