基于PMCL方法的大規模無線傳感器網絡移動定位機制*

呂春峰， 朱建平， 陶正蘇

(1.上海海洋大學 工程學院，上海 201306； 2.上海交通大學 電子信息與電氣工程學院，上海 200240)

0 引 言

目前，對移動節點定位的方法基本都是基于序列蒙特卡洛(sequential Monte Carlo,SMC)機制[1,2]，即利用帶權重的樣本集描述狀態量的概率分布，用MC方法來實現遞推是一種魯棒、有效的非線性次優預估方法，近十年來受到了廣泛關注。而大量的樣本優化更新運算導致算法運行效率低是SMC機制主要的不足。

本文將針對傳統的SMC定位機制迭代次數較多、樣本數量易衰減、觀測值多樣性差等缺點，首先，結合隱藏終端耦合(hidden terminal coupling,HTC)傳輸機制，提出了群蒙特卡洛定位(population Monte Carlo localization,PMCL)方法：1)采用兩重限制手段降低迭代次數；2)采用蒙特卡洛群對重采樣進行精確匹配。基于節點密度λ、錨節點分布比例γ、樣本數量N、最大移動速度vmax等參數，對PMCL機制進行理論分析和實驗仿真。PMCL機制與其他的基于SMC機制的移動定位機制進行性能比較。

1 SMC定位機制缺點

基于SMC機制的移動定位機制，普遍存在幾個問題：1)初始樣本隨機選取，沒有任何限制，需要更多次的迭代以獲取足夠數量的有效樣本，效率低；2)通過一重權重迭代，大幅降低樣本的多樣性，降低了目標位置的準確性；3)樣本或者觀測值在經過多次迭代之后，過濾后的樣本數量不足，導致樣本退化。

2 PMCL機制

PMCL機制的核心思想是采用一組權重樣本描述目標的后驗概率分布，并采用重采樣機制(兩重)保證樣本的多樣性和降低樣本衰減，將其用于定位，有其顯著的優點。

1)初始化階段

在初始化階段，時間分成離散的時隙。所有錨節點通過全球定位系統(global positioning system,GPS)獲取其位置信息，并執行HTC機制[3]，通過發送HTC請求包傳遞位置信息和其所有的隱藏終端鏈(hidden terminal link,HTL)上的節點，包括其他錨節點和普通節點。所有節點包括錨節點都獲取其HTLs和HTCs，作為候選樣本。1-hop,2-hop節點(包括錨節點)的鄰居S1-hop和S2-hop分別表示為

(1)

式中l為未知節點與其HTL上的錨節點之間的距離，未知節點的初始位置在候選樣本中選取。

2)采樣與預測階段(一重限制)

(2)

圖1 PMCL機制選取樣本初始化(第一重限制)

(3)

(4)

先驗概率p0(lt)為

(5)

圖2 采樣和預測階段(第二重限制)

(6)

3)權重計算與重采樣階段

(7)

采樣迭代計算產生樣本均可用于構造目標全局預測

(8)

通過對這N個獨立的自適應參數進行重采樣機制為

(9)

(10)

(11)

4)位置計算

節點通過其新的可能位置和新的觀測量，可以計算其下一時刻的位置

(12)

3 實驗驗證

3.1 性能驗證

通過NS-2仿真軟件來驗證PMCL機制的性能。搭建仿真平臺：所有節點包含錨節點均分布在同一個邊長1 km的正方形區域內；假設所有在傳輸距離內的傳輸節點都能偵聽到其他節點的傳送；沒有信號衰減。設定HTC機制參數為：重傳次數為2，最大退避次數為4，數據包長為5個時隙單位。由式(12)可知，位置的誤差取決于錨節點的密度γ、樣本數量N、節點密度λ，移動速度vmax等參數，基于這幾個參數驗證PMCL的性能,如圖3所示。

圖3 定位誤差與節點密度關系

可以看出，節點定位誤差隨著節點密度的增加而減小，且隨著錨節點數量的增加，誤差也會減小。隨著樣本數量增加，其重采樣重要性權重會更加精確，多樣性也增加，但其迭代次數會增加，導致定位延時增加。

同理，定位延時性能也跟γ、樣本數量N、節點密度λ等參數有較大關系，如圖4所示。隨著節點數量的增加，延時先平穩降低，直到λ>0.04，節點數量較多，傳遞數據包發生沖突的概率增加，傳輸定位延時增加。

圖4 定位時延與節點密度關系

3.2 性能比較

PMCL機制與基于SMC機制的定位算法的蒙特卡洛定位(MCL)機制[4]、移動WSNs的MCL(MCB)機制[5]、WMCL機制[6]、基于約束規則的MCL(COMCL)機制[8]、USML[8]等進行性能比較。

PMCL機制是提高定位響應速度的機制，在初始階段就限定了采樣的區域，并在重采樣階段再一次限定觀測區域，提高了迭代效率，因此，定位延時性能要優于其他機制；而其采樣及觀測的區域都選定在信號包低沖突率的區域，提高了定位的精度，特別是節點規模較大、錨節點密度較小的情況，如圖5。

圖5 幾種定位機制的錨節點密度性能影響

節點移動速度對性能也有較大影響，從圖6中看出，PMCL機制對移動速度的響應不理想，只有在低速情況下，其定位誤差和實時性有優勢。

圖6 幾種定位機制的節點移動速度性能影響

4 結束語

提出了精度高、時延小的PMCL方法。從實驗結果表明：PMCL機制在移動速度小、大規模分布的無線傳感器網絡中，提高了定位精度，改善了時延性能，為實時在線監控系統應用提供了保證。