摘 要：節(jié)點定位技術是無線傳感器網絡的關鍵技術之一。文章介紹了無線傳感器移動節(jié)點定位的原理，討論了移動節(jié)點定位算法的分類，對移動節(jié)點定位算法的優(yōu)點、局限、適用情況做了對比，并對未來移動節(jié)點定位算法的發(fā)展進行了展望。

關鍵詞：無線傳感器網絡；移動節(jié)點定位；蒙特卡羅定位算法；

Abstract： Localization technique is one of the key technologies of wireless sensor networks.This paper introduces the principle of wireless sensor node localization in mobile，and discusses the classification of mobile node localization algorithm，and compares the mobile node localization algorithm advantages，disadvantages and applicability，and the future of mobile node localization algorithm development was prospected.

Key words：wireless sensor network ，mobile node localization，Monte Carlo localization algorithm

文章編號：1674-3520（2015）-12-00-02

引言

無線傳感器網絡（WSN）是21世紀最重要的技術之一，它是由一組具有有限計算能力和通訊性能的傳感器構成的分布式自組織的無線網絡。目前它已經廣泛應用在智能家居、醫(yī)療護理、智能交通、環(huán)境監(jiān)測等領域。無線傳感器節(jié)點定位是最關鍵的技術，因為不包含位置信息的節(jié)點是毫無價值的，而且無線傳感器中的諸如數(shù)據(jù)傳輸與傳遞的過程是以節(jié)點的位置信息為基礎的。無線傳感器節(jié)點定位主要分為靜止節(jié)點定位與移動節(jié)點定位。靜止節(jié)點定位也稱傳統(tǒng)節(jié)點定位技術。根據(jù)是否將定位過程建立在距離或角度信息的基礎上主要分為基于測距的定位技術與非測距技術?；跍y距的定位技術主要包括TOA、TDOA、AOA、RSSI等；基于非測距技術主要包括質心定位技術、DV-Hop、Amorphous、APIT等。這些算法可以通過經常刷新位置估計來適用于移動網絡，但是它們沒有考慮到如何可以開發(fā)移動性來完成定位。有關靜止節(jié)點定位技術的綜述現(xiàn)在已有很多，故本文不再贅述，本文主要論述移動節(jié)點定位技術。

一、移動傳感器網絡定位算法分類

根據(jù)移動無線傳感器節(jié)點的運動情況的不同可以分為三類：錨節(jié)點靜止而未知節(jié)點運動、錨節(jié)點運動而未知節(jié)點靜止、錨節(jié)點和未知節(jié)點都運動的情況。錨節(jié)點靜止而未知節(jié)點運動的一個典型例子是未知節(jié)點沿著河漂流，錨節(jié)點固定在河岸中的某一位置。錨節(jié)點運動而未知節(jié)點靜止的典型例子是一個軍事應用，其中未知節(jié)點從飛機上下落到土地，士兵或者動物身上附帶的發(fā)射器被當做移動錨節(jié)點。錨節(jié)點和未知節(jié)點都運動的情形是最通用的，它適用于未知節(jié)點和錨節(jié)點以ad hoc方式分布，或因為他們所處的環(huán)境而移動或因為他們具有促動器而移動的任何應用。在此情況下，主流的定位算法是蒙特卡羅算法及其衍生算法。

（一）蒙特卡羅算法

2005年Lingxuan Hu和David Evans將蒙特卡羅（MCL）定位算法首先應用到了移動傳感器網絡中，而此前MCL方法一直是應用在機器人定位中[2]。MCL算法的流程是先初始化，然后判斷系統(tǒng)是否到達定位時間，如果到達定位時間，就進入預測階段。在預測階段，位置節(jié)點使用轉移方程并根據(jù)前一時刻的樣本分布來預測它可能的位置和運動情況。如果已知節(jié)點的最大運動速度為v，則節(jié)點在當前時間段的位置是以前一時間段位置為圓心，v為半徑的圓內。所以根據(jù)之前位置估計的現(xiàn)有位置的概率以均勻分布的形式給出。接下來進入過濾階段。在這一階段，未知節(jié)點根據(jù)新的觀測值濾除不可能存在的位置。濾波條件是保留所有直接被未知節(jié)點監(jiān)聽到的錨節(jié)點和被未知節(jié)點的鄰居節(jié)點監(jiān)聽到但未被未知節(jié)點直接監(jiān)聽到的錨節(jié)點的集合。過濾之后剩下的節(jié)點數(shù)可能少于要求的數(shù)目，預測和過濾過程重復進行，加入找到的滿足條件的可能節(jié)點，直到達到要求或者采樣次數(shù)達到上限為止。最后將樣本點集合中的平均值作為待定位節(jié)點在t時刻的估計位置。

（二）MCB算法

在MCL方法中如果采樣樣本沒有達到閾值就不再設置樣本集了。在MCL算法基礎上，Baggio等人提出了Monte Carlo Localization Boxed（MCB）算法。在MCB算法中，使用監(jiān)聽到的錨節(jié)點的信息來限制采樣區(qū)域，主要通過構建錨盒和采樣盒子。一個監(jiān)聽到一跳或二跳錨節(jié)點的未知節(jié)點構建一個覆蓋錨節(jié)點廣播范圍重疊區(qū)域的盒子稱為錨盒。錨盒的構建過程是一個未知節(jié)點構建一個以錨節(jié)點位置為中心的邊長為2r的正方形，r是廣播范圍。采樣盒是一個以舊樣本點為中心，2vmax為邊長的正方形。它限制了對于每個舊樣本點，一個未知節(jié)點在一個時間間隔內能移動的最大區(qū)域。盒子的構建保持一個序列化過程，錨盒首先被建立，獨立更新每個舊樣本點，建立采樣盒子，從中每個新樣本點被有效采樣。MCB的濾波和重采樣過程與MCL相同[3]。

（三）MMCL定位算法

傳統(tǒng)的MCL、MCB算法雖然可以減少計算量但是這些算法仍然依賴于一些特定的參數(shù)比如固定的廣播傳輸范圍，而且主要有兩個限制：需要有充分的錨節(jié)點和假定固定廣播傳輸范圍已知。因此Jiyoung Yi等人根據(jù)具有多跳傳播的序列蒙特卡羅方法提出了一種新的定位機制，基于多跳的MCL算法MMCL。

MMCL算法主要由兩部分組成。第一部分像DV-hop一樣給錨節(jié)點提供一個平均跳段距離。每個傳感器節(jié)點從錨節(jié)點處獲得平均每跳距離并計算它的位置。第二部分是在每個傳感器節(jié)點運用MCL算法[2]。

（四）對偶MCL算法與混合MCL算法

對偶蒙特卡羅算法的原理就是將傳統(tǒng)MCL算法中的預測階段和過濾階段進行倒置：以觀測方程獲得樣本點，以轉移方程過濾樣本點。在混合蒙特卡羅算法中，樣本點通過原始MCL算法和對偶MCL算法生成?；旌厦商乜_算法是以概率1-p使用原始MCL采樣算法，以概率p使用對偶MCL算法來生成每個樣本點。

（五）MSL和MSL*算法

它是由加拿大York大學的Rudafshani M和Datta S設計提出的，在 MCL算法基礎上進行改進，依據(jù)樣本集的構建過程和采樣的共同鄰居節(jié)點關系將樣本粒子的權重進行不同的取值。該算法是利用待定位節(jié)點的一階和二階鄰居節(jié)點來改善定位效果。MSL*針對 MCL 算法僅僅依靠信標節(jié)點來實現(xiàn)定位進行了改進，提出了兩種利用未知節(jié)點的鄰居節(jié)點來提高定位精度的方法，但是該算法也會擴大采樣區(qū)間，又降低了采樣的效率。

二、各算法性能比較

以上介紹的每個算法都有其各自的特點，以下分析每個算法的改進之處、優(yōu)點、局限和適用情況。

（一）MCB算法特性

MCB算法的優(yōu)點是不像MCL算法那樣定位精度容易受未知節(jié)點的最大速度的影響。對于一個類似的定位精度，MCB算法比MCL算法定位更快。在MCB定位算法中，把節(jié)點的通信區(qū)域看成是一個正規(guī)的圓形區(qū)域，而在現(xiàn)實的環(huán)境中，節(jié)點間通信的范圍不可能是規(guī)則的圓形區(qū)域。MCB算法適用于對于MCL算法獲得足夠多的樣本點困難的情形，MCB能得到足夠多的樣本點。

（二）MMCL算法特性

MMCL算法的改進之處是結合了MCL和DV-Hop兩個算法的優(yōu)勢。MMCL算法的優(yōu)點是不需要提前知道節(jié)點傳輸范圍，MMCL相對于MCL算法而言，在信標節(jié)點密度較小的時候，由于幾乎能用到所有信標節(jié)點的位置信息而使其定位精度較高。MMCL算法的局限在于隨著信標節(jié)點密度的增大，該算法定位精度的提高卻很有限，遠不及 MCL 算法精度的提高。同時網絡中節(jié)點間的通信量卻迅速增多，浪費了節(jié)點的能量。MMCL算法更常適用于大規(guī)模且低信標節(jié)點密度的網絡應用。

（三）對偶MCL算法特性

對偶MCL算法的改進之處是原始蒙特卡羅算法的邏輯顛倒。對偶MCL算法的優(yōu)點是它克服了依賴樣本總個數(shù)的缺點。對偶MCL算法的局限是需要更多時間從傳感器獲得樣本。對偶MCL算法的計算量比MCL算法多，定位精度不優(yōu)于MCL定位精度。對偶MCL算法的適用情況同MCL一樣。

（四）混合MCL算法特性

混合蒙特卡羅方法的改進之處是它是原始蒙特卡羅算法和對偶蒙特卡羅算法的結合?；旌螹CL算法的優(yōu)點是克服了依賴樣本點總個數(shù)的缺點?；旌螹CL算法在計算時間消耗和定位準確性中找到了平衡?；旌螹CL算法的局限是它的計算量比MCL算法多，定位精度也優(yōu)于MCL定位精度。混合MCL算法的適用情況同MCL一樣。

（五）MSL算法特性

MSL算法的改進之處是通過使用所有鄰居節(jié)點的位置估計（而不僅僅是錨節(jié)點）來提高算法的定位精度。MSL算法的優(yōu)點是具有良好的衰減性和更低的通信開銷。MSL算法的局限是它需要高的未知節(jié)點密度和高的錨節(jié)點密度來收斂。MSL算法適用于那些可以支持額外通信開銷的大型傳感器網絡。在最后時間單元倒置大多數(shù)樣本點的特性使得MSL更適用于具有低運動速度的網絡。

（六）MSL*算法特性

MSL*算法的改進之處是它能在廣播傳輸范圍內處理不均勻性（異質性）。通過使用所有鄰居節(jié)點的位置估計（而不僅僅是錨節(jié)點）來提高算法的定位精度。MSL*算法的優(yōu)點是誤差較小，具有良好的衰減性，采樣步驟較快。MSL*算法在很多場景下表現(xiàn)的比MSL要好，但是這導致了更高的通信開銷，它還具有比MSL更高的計算開銷。MSL*適用于任何數(shù)量的傳感器節(jié)點是靜止的或運動的情況下。適用于那些可以支持額外通信開銷的大型傳感器網絡。在最后時間單元倒置大多數(shù)樣本點的特性使得MSL*更適用于具有低運動速度的網絡。

三、總結與展望

本文主要介紹了蒙特卡羅算法及其衍生算法。基于蒙特卡羅算法的跟蹤方法，用蒙特卡羅算法預測移動節(jié)點定位目標下一時刻的一組狀態(tài)；然后通過計算得到各預測狀態(tài)中與參考目標的狀態(tài)相似度最大的一個，即為移動節(jié)點定位目標跟蹤的結果。研究結果表明：該方法能實時、準確地跟蹤無規(guī)律、非線性運動的目標。不同的算法各有優(yōu)劣與適用情況，在實際科學計算中應按照不同算法各自的特點，選擇合適的算法。研究發(fā)展方向期待有更多的衍生算法誕生，未來的移動節(jié)點定位算法將向著低復雜度、低開銷、低能耗的趨勢進一步發(fā)展，如何進一步優(yōu)化節(jié)點定位算法將成為無線傳感器網絡定位技術研究的重要方向。期待著未來的WSN定位算法向著智能化、便捷化的方向發(fā)展，同時要實現(xiàn)這一目標具有理論上、技術上的難度，需要科研工作者努力研究實現(xiàn)。

參考文獻：

[1]羅雯雯.無線傳感器網絡自主移動節(jié)點定位技術研究.浙江理工大學碩士學位論文.2013.03

[2]宋艷.基于Monte Carlo移動無線傳感器網絡定位算法研究.南京郵電大學碩士學位論文2012.02

[3]王妮.分布式無需測距（range-free）的移動無線傳感器網絡節(jié)點的定位方法.上海交通大學碩士學位論文.2008.11