無(wú)線傳感器移動(dòng)節(jié)點(diǎn)定位技術(shù)綜述

摘 要：節(jié)點(diǎn)定位技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。文章介紹了無(wú)線傳感器移動(dòng)節(jié)點(diǎn)定位的原理，討論了移動(dòng)節(jié)點(diǎn)定位算法的分類，對(duì)移動(dòng)節(jié)點(diǎn)定位算法的優(yōu)點(diǎn)、局限、適用情況做了對(duì)比，并對(duì)未來(lái)移動(dòng)節(jié)點(diǎn)定位算法的發(fā)展進(jìn)行了展望。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；移動(dòng)節(jié)點(diǎn)定位；蒙特卡羅定位算法；

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

文章編號(hào)：1674-3520（2015）-12-00-02

引言

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

一、移動(dòng)傳感器網(wǎng)絡(luò)定位算法分類

根據(jù)移動(dòng)無(wú)線傳感器節(jié)點(diǎn)的運(yùn)動(dòng)情況的不同可以分為三類：錨節(jié)點(diǎn)靜止而未知節(jié)點(diǎn)運(yùn)動(dòng)、錨節(jié)點(diǎn)運(yùn)動(dòng)而未知節(jié)點(diǎn)靜止、錨節(jié)點(diǎn)和未知節(jié)點(diǎn)都運(yùn)動(dòng)的情況。錨節(jié)點(diǎn)靜止而未知節(jié)點(diǎn)運(yùn)動(dòng)的一個(gè)典型例子是未知節(jié)點(diǎn)沿著河漂流，錨節(jié)點(diǎn)固定在河岸中的某一位置。錨節(jié)點(diǎn)運(yùn)動(dòng)而未知節(jié)點(diǎn)靜止的典型例子是一個(gè)軍事應(yīng)用，其中未知節(jié)點(diǎn)從飛機(jī)上下落到土地，士兵或者動(dòng)物身上附帶的發(fā)射器被當(dāng)做移動(dòng)錨節(jié)點(diǎn)。錨節(jié)點(diǎn)和未知節(jié)點(diǎn)都運(yùn)動(dòng)的情形是最通用的，它適用于未知節(jié)點(diǎn)和錨節(jié)點(diǎn)以ad hoc方式分布，或因?yàn)樗麄兯幍沫h(huán)境而移動(dòng)或因?yàn)樗麄兙哂写賱?dòng)器而移動(dòng)的任何應(yīng)用。在此情況下，主流的定位算法是蒙特卡羅算法及其衍生算法。

（一）蒙特卡羅算法

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

（二）MCB算法

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

（三）MMCL定位算法

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

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

（四）對(duì)偶MCL算法與混合MCL算法

對(duì)偶蒙特卡羅算法的原理就是將傳統(tǒng)MCL算法中的預(yù)測(cè)階段和過(guò)濾階段進(jìn)行倒置：以觀測(cè)方程獲得樣本點(diǎn)，以轉(zhuǎn)移方程過(guò)濾樣本點(diǎn)。在混合蒙特卡羅算法中，樣本點(diǎn)通過(guò)原始MCL算法和對(duì)偶MCL算法生成。混合蒙特卡羅算法是以概率1-p使用原始MCL采樣算法，以概率p使用對(duì)偶MCL算法來(lái)生成每個(gè)樣本點(diǎn)。

（五）MSL和MSL*算法

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

二、各算法性能比較

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

（一）MCB算法特性

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

（二）MMCL算法特性

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

（三）對(duì)偶MCL算法特性

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

（四）混合MCL算法特性

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

（五）MSL算法特性

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

（六）MSL*算法特性

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

三、總結(jié)與展望

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

參考文獻(xiàn)：

[1]羅雯雯.無(wú)線傳感器網(wǎng)絡(luò)自主移動(dòng)節(jié)點(diǎn)定位技術(shù)研究.浙江理工大學(xué)碩士學(xué)位論文.2013.03

[2]宋艷.基于Monte Carlo移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)定位算法研究.南京郵電大學(xué)碩士學(xué)位論文2012.02

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