1．2 位置預(yù)測(cè)

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

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

　　1．3 位置濾波

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

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

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

　　如果濾波條件為假，那么節(jié)點(diǎn)位置的概率分布p(lt|Ot)值為零，否則p(lt Ot)將符合均勻分布，這樣．就可以從節(jié)點(diǎn)的所有可能位置集合中去除那些與觀測(cè)值不一致的位置。經(jīng)濾波后，節(jié)點(diǎn)剩余的可能位置也許會(huì)少于N個(gè)。預(yù)測(cè)過(guò)程和濾波過(guò)程將不斷重復(fù)進(jìn)行，并結(jié)合已經(jīng)發(fā)現(xiàn)的節(jié)點(diǎn)可能位置,直至獲得節(jié)點(diǎn)的至少N個(gè)可能位置。

　　1．4 重要性采樣

　　算法的最終目標(biāo)是估計(jì)節(jié)點(diǎn)可能位置的后驗(yàn)概率分布p(lt|O0,O1，…Ot)。首先，通過(guò)一個(gè)標(biāo)準(zhǔn)化重要性采樣函數(shù)π獲得一系列相互獨(dú)立的節(jié)點(diǎn)位置采樣值；然后，對(duì)每個(gè)采樣值的權(quán)重值進(jìn)行調(diào)整并且使用這些權(quán)重值對(duì)節(jié)點(diǎn)所在可能位置的后驗(yàn)概率分布作出估計(jì)。算法采用了下列遞歸式重要性函數(shù)。

　　式(3)表示節(jié)點(diǎn)的位置預(yù)測(cè)，節(jié)點(diǎn)借助先前所在的可能位置預(yù)測(cè)其當(dāng)前的可能位置。式(4)表示節(jié)點(diǎn)的位置更新，節(jié)點(diǎn)根據(jù)獲得的觀測(cè)值對(duì)新的采樣值不斷進(jìn)行權(quán)重值更新與調(diào)整。然后。通過(guò)式(5)對(duì)權(quán)重值Wit；進(jìn)行歸一化處理得到Wit用權(quán)重值序列(lit,wit)對(duì)節(jié)點(diǎn)位置的后驗(yàn)概率分布作出估計(jì)。通過(guò)式(3)和式(4)的反復(fù)計(jì)算，很容易地確定概率值p(lk|lk-1)和p(l1|Ot)的大小。