曹樹(shù)林，單志龍，武曉琳，曹楚裙

（華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州 510631）

基于拓?fù)浣Y(jié)構(gòu)變化趨勢(shì)的MCL優(yōu)化算法*

曹樹(shù)林，單志龍*，武曉琳，曹楚裙

（華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州 510631）

該文提出一種高精度的移動(dòng)傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)定位跟蹤的方法，該方法利用未知節(jié)點(diǎn)在運(yùn)動(dòng)過(guò)程中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的信息提高錨節(jié)點(diǎn)利用率，并改善樣本采集效率。在無(wú)拓?fù)浣Y(jié)構(gòu)變化的情況下采用牛頓插值方法對(duì)節(jié)點(diǎn)當(dāng)前位置進(jìn)行預(yù)測(cè)，當(dāng)拓?fù)浣Y(jié)構(gòu)有變化時(shí)，采用拓?fù)浣Y(jié)構(gòu)變化構(gòu)建適應(yīng)值函數(shù)，并用粒子群算法優(yōu)化樣本點(diǎn)的質(zhì)量。仿真實(shí)驗(yàn)結(jié)果表明，該文算法與傳統(tǒng)算法相比加快了收斂速度，提高了定位精度，改善了在低錨節(jié)點(diǎn)密度時(shí)的性能。

無(wú)線傳感網(wǎng)；拓?fù)浣Y(jié)構(gòu)；蒙特卡羅算法；粒子群算法；牛頓插值

無(wú)線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Networks）是由大量附有通信模塊的傳感器節(jié)點(diǎn)按照協(xié)議自組成的分布式網(wǎng)絡(luò)。無(wú)線傳感網(wǎng)絡(luò)多用于軍事偵察，目標(biāo)跟蹤等位置服務(wù)。然而當(dāng)這些位置服務(wù)信息沒(méi)有節(jié)點(diǎn)的位置作為參考位置時(shí)，這一位置服務(wù)也就失去了意義。因此傳感器節(jié)點(diǎn)確定自身位置在整個(gè)應(yīng)用中非常重要。目前常見(jiàn)的WSN定位算法有：DV-HOP定位算法［1］，凸規(guī)劃定位算法［2］，APIT定位算法［3］，質(zhì)心定位算法以及新穎的MDS-MAP定位算法［4］，然而這些定位算法一般適合節(jié)點(diǎn)靜止的網(wǎng)絡(luò)，即靜態(tài)網(wǎng)絡(luò)。

當(dāng)然，針對(duì)網(wǎng)絡(luò)行為復(fù)雜的動(dòng)態(tài)網(wǎng)絡(luò)，也有一系列動(dòng)態(tài)傳感器網(wǎng)絡(luò)定位算法，Hu［5］等首先提出了一種常用的基于蒙特卡羅MCL（Monte Carlo Localization）的WSN定位算法，該算法用運(yùn)動(dòng)模型采樣，然后使用約束信息來(lái)過(guò)濾，算法存在周期長(zhǎng)，采樣次數(shù)大，粒子退化等問(wèn)題。匡興紅［6］提出一種測(cè)距技術(shù)與信標(biāo)點(diǎn)相結(jié)合的分布式節(jié)點(diǎn)定位方法。Baggio［7］，曾凡仔［8］等提出了一種蒙特卡羅箱（MCB）方法，該方法是對(duì)MCL算法采樣區(qū)域的改進(jìn)，減少計(jì)算的同時(shí)提高了采樣的成功率。朱海平［9］等人提出一種動(dòng)態(tài)無(wú)線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法：該算法構(gòu)建接收信號(hào)強(qiáng)度指示測(cè)距模型來(lái)限制樣本區(qū)域以求提高采樣效，并最終獲得一個(gè)更好的精度。Rudafshani［10］，Stevens［11］等人則對(duì)MCL算法的結(jié)構(gòu)做改進(jìn)從而一定程度上提高了定位效果。李牧東［12］等人將粒子群優(yōu)化算法應(yīng)用到無(wú)線傳感器定位中，顯著的提高了定位精度。黃梅根［13］等人則通過(guò)構(gòu)建節(jié)點(diǎn)運(yùn)動(dòng)模型，提出了一種基于信標(biāo)節(jié)點(diǎn)靜止、定位節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)的WSN定位方法。JiyongYi［14］，Wang［15］，Bram［16］等人提出一種基于測(cè)距的動(dòng)態(tài)定位方法。通過(guò)對(duì)這些算法的研究，本文利用未知節(jié)點(diǎn)運(yùn)動(dòng)過(guò)程中周?chē)負(fù)浣Y(jié)構(gòu)的變化信息，提出了TMCL（Topological Monte Carlo Localization）算法。算法首先收集節(jié)點(diǎn)移動(dòng)中的拓?fù)浣Y(jié)構(gòu)變化，然后用這些信息構(gòu)建粒子群優(yōu)化模型來(lái)優(yōu)化所采得的樣本粒子，從而使節(jié)點(diǎn)定位達(dá)到較高精度。對(duì)未知節(jié)點(diǎn)的最大移動(dòng)速度，移動(dòng)步長(zhǎng)和錨節(jié)點(diǎn)數(shù)量定位仿真，并在相同條件下將傳統(tǒng)MCL和TMCL算法進(jìn)行了對(duì)比。

1 蒙特卡洛定位算法

MCL算法最早被定義在文獻(xiàn)［5］中，其充分利用無(wú)線網(wǎng)絡(luò)的節(jié)點(diǎn)特性，算法受貝葉斯濾波啟發(fā)，用若干個(gè)帶有權(quán)重的離散樣本來(lái)估計(jì)后驗(yàn)概率密度，并利用重要性采樣來(lái)迭代更新它們。算法有初始化，預(yù)測(cè)，濾波以及定位4個(gè)階段。

初始化完成后，然后重復(fù)預(yù)測(cè)階段和濾波階段來(lái)實(shí)現(xiàn)節(jié)點(diǎn)定位。

圖1 采樣區(qū)域和過(guò)濾條件示意圖

式中：方程p（mt|mt-1）描述由t-1時(shí)刻的節(jié)點(diǎn)位置所預(yù)測(cè)t時(shí)刻的位置分布。

在濾波階段，算法會(huì)通過(guò)當(dāng)前周?chē)芙邮盏降男艠?biāo)節(jié)點(diǎn)的跳數(shù)信息，然后對(duì)節(jié)點(diǎn)可能存在的位置做一個(gè)約束，丟棄那些不可能存在的預(yù)測(cè)位置。具體來(lái)說(shuō)，在當(dāng)前時(shí)刻t每個(gè)預(yù)測(cè)位置都應(yīng)該在待定位節(jié)點(diǎn)能接收到的信標(biāo)節(jié)點(diǎn)的公共廣播范圍內(nèi)，如果預(yù)測(cè)位置不在該范圍內(nèi)，則表明該位置為真實(shí)位置的可能性很小，因此應(yīng)該丟棄。具體算法根據(jù)當(dāng)前時(shí)刻接收到的二跳以內(nèi)的錨節(jié)點(diǎn)的位置信息把不符合條件的樣本過(guò)濾掉。如圖1所示，如果S1t和S2t分別為未知節(jié)點(diǎn)在t時(shí)刻一跳和兩跳錨節(jié)點(diǎn)的集合，r是節(jié)點(diǎn)通信半徑，則過(guò)濾條件為：

在過(guò)濾階段后，由于可能會(huì)出現(xiàn)樣本被過(guò)濾掉，采集不到足夠的樣本，當(dāng)樣本不足時(shí)，算法則需要重復(fù)預(yù)測(cè)與過(guò)濾階段，直到采集到足夠的樣本。

2TMCL算法

TMCL算法通過(guò)計(jì)算并保存節(jié)點(diǎn)跟蹤過(guò)程中未知節(jié)點(diǎn)周?chē)負(fù)浣Y(jié)構(gòu)變化，然后利用這些拓?fù)浣Y(jié)構(gòu)的變化通過(guò)粒子群優(yōu)化算法來(lái)優(yōu)化所采得的樣本粒子。當(dāng)拓?fù)浣Y(jié)構(gòu)發(fā)生明顯的變化時(shí)，粒子群優(yōu)化過(guò)程中，定位過(guò)程中的樣本粒子的分布會(huì)呈現(xiàn)一個(gè)向未知節(jié)點(diǎn)真實(shí)位置靠近的趨勢(shì)，經(jīng)過(guò)加權(quán)最終得到未知節(jié)點(diǎn)的估計(jì)位置。當(dāng)拓?fù)浣Y(jié)構(gòu)無(wú)變化時(shí)，則通過(guò)前面時(shí)刻的估計(jì)位置用二次牛頓插值法來(lái)預(yù)測(cè)當(dāng)前時(shí)刻未知節(jié)點(diǎn)的位置，整個(gè)算法有效的提高了定位精度和定位率。

2.1 移動(dòng)模型

目前常用的移動(dòng)模型有：

①隨機(jī)移動(dòng)模型RWM（Random Walk Model）：在該移動(dòng)模型中，移動(dòng)節(jié)點(diǎn)每次運(yùn)動(dòng)到當(dāng)前位置后都會(huì)為接下來(lái)的運(yùn)動(dòng)隨機(jī)選擇一個(gè)速率。這使得其前后時(shí)刻的速率缺少關(guān)聯(lián)，該模型實(shí)際上是一種無(wú)規(guī)律性且不太接近現(xiàn)實(shí)的節(jié)點(diǎn)移動(dòng)模型，故較少使用。

②隨機(jī)路點(diǎn)移動(dòng)模型RWPM（Random Way Point Model）：RWPM在移動(dòng)過(guò)程中采用停留Ts的方式，在停留后在網(wǎng)絡(luò)中隨機(jī)產(chǎn)生一個(gè)目的地，然后節(jié)點(diǎn)再以一個(gè)有下限和上限的任意速度向目的地移動(dòng)，并不表示下一時(shí)刻會(huì)到達(dá)該目的地。隨機(jī)路點(diǎn)移動(dòng)模型中加入的時(shí)間停留可以避免RWM中突發(fā)情況的發(fā)生。

③高斯馬爾可夫移動(dòng)模型 GMM（Gaussian Markov Model）：該模型與RWM移動(dòng)模型不同的是當(dāng)前時(shí)刻的速率和方向分別是在上一時(shí)刻的基礎(chǔ)上增加一個(gè)高斯擾動(dòng)值，這種變化使得移動(dòng)模型比較接近于實(shí)際的運(yùn)動(dòng)。

由于高斯馬爾可夫移動(dòng)模型比較切合實(shí)際且其可調(diào)參數(shù)多，靈活性很大，本文最終采用其作為移動(dòng)模型，高斯馬爾科夫移動(dòng)模型公式定義如下：

式中：vk，dk分為別第k個(gè)時(shí)間間隔t開(kāi)始時(shí)的速度和方向，vmean，dmean是速度和運(yùn)動(dòng)的均值，α是信標(biāo)移動(dòng)中的一個(gè)隨機(jī)度調(diào)節(jié)參數(shù)，決定了節(jié)點(diǎn)移動(dòng)的隨機(jī)性。當(dāng)α=1時(shí)，節(jié)點(diǎn)做線性運(yùn)動(dòng)，當(dāng)α=0時(shí)，節(jié)點(diǎn)則是完全隨機(jī)的運(yùn)動(dòng)。γv，γd均為代表高斯分布的隨機(jī)變量。

節(jié)點(diǎn)在k個(gè)時(shí)間間隔開(kāi)始時(shí)的位置定義如下：

式中：（xk，yk）代表信標(biāo)運(yùn)動(dòng)到第k個(gè)時(shí)間間隔開(kāi)始時(shí)的坐標(biāo)。

2.2 拓?fù)浣Y(jié)構(gòu)變化趨勢(shì)構(gòu)建

用Tn2和T2n分別表示未知節(jié)點(diǎn)在t時(shí)刻從無(wú)法接收到未知節(jié)點(diǎn)信息變成2跳和從2跳變成無(wú)法接收到未知節(jié)點(diǎn)信息的錨節(jié)點(diǎn)集合，用T21和T12分別表示未知節(jié)點(diǎn)在t時(shí)刻從2跳變成1跳和從1跳變成2跳的錨節(jié)點(diǎn)集合。未知節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)變化如圖2所示。

圖2 未知節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)變化圖

當(dāng)前時(shí)刻的拓?fù)浣Y(jié)構(gòu)變化列表將按式（8）構(gòu)建：

假如未知節(jié)點(diǎn)相對(duì)某一錨節(jié)點(diǎn)的跳數(shù)由一跳變?yōu)閮商?，此時(shí)未知節(jié)點(diǎn)的位置將在一跳與兩跳范圍之間，其他變化規(guī)則一致。因此有了這些拓?fù)浣Y(jié)構(gòu)變化信息，拓?fù)浣Y(jié)構(gòu)變化將對(duì)未知節(jié)點(diǎn)位置的估計(jì)有個(gè)更好的限制作用，因此可以利用這些拓?fù)浣Y(jié)構(gòu)變化信息來(lái)采集更優(yōu)的樣本點(diǎn)。

2.3 粒子群優(yōu)化算法

粒子群優(yōu)化算法PSO（Particle Swarm Optimization）是一種模擬鳥(niǎo)群捕食行為研究的群體智能優(yōu)化算法。在結(jié)果優(yōu)化的模型中，其關(guān)鍵在于怎么定義一個(gè)優(yōu)化解的約束集。如果約束處理的不好，其優(yōu)化的結(jié)果往往會(huì)出現(xiàn)不能夠收斂和結(jié)果是空集的狀況?；赑SO算法的約束優(yōu)化工作主要分為兩類(lèi)：①罰函數(shù)法。罰函數(shù)的目的是將約束優(yōu)化問(wèn)題轉(zhuǎn)化成無(wú)約束優(yōu)化問(wèn)題。②將粒子群的搜索范圍都限制在條件約束簇內(nèi)，即在可行解范圍內(nèi)尋優(yōu)。

在MCL算法中，樣本點(diǎn)的分布可以用來(lái)估計(jì)未知節(jié)點(diǎn)的位置。為了使樣本點(diǎn)更加接近未知節(jié)點(diǎn)的真實(shí)位置，需要充分利用節(jié)點(diǎn)運(yùn)動(dòng)中拓?fù)渥兓男畔?，得到一些位置相?duì)準(zhǔn)確的樣本點(diǎn)。粒子群算法特別適合這種約束性優(yōu)化問(wèn)題，因此本文方法將采用粒子群算法對(duì)其進(jìn)行優(yōu)化。粒子群算法的適應(yīng)性函數(shù)fitness（p）將根據(jù)式（10）構(gòu)造，樣本例子p滿足式（10）則表示該樣本有更高的適應(yīng)度，其也將更接近真實(shí)位置。

式中：r為節(jié)點(diǎn)的通信半徑，Ve為未知節(jié)點(diǎn)前3個(gè)時(shí)刻的平均速度，p是樣本粒子，d（p，Sxy［i］）為粒子p 到Sxy［i］號(hào)錨節(jié)點(diǎn)的歐式距離。

設(shè)Lt=｛l1，l2，…，lN｝為所采到的N個(gè)樣本點(diǎn)，vi（t）為第i個(gè)樣本例子在t時(shí)刻的優(yōu)化速度，那么粒子群優(yōu)化算法的進(jìn)化方程如下：

圖3 未知節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)變化圖

式中：t表示迭代次數(shù)，Pt（t）表示樣本例子i迄今為止經(jīng)過(guò)的歷史最好位置；Pg（t）為當(dāng)前粒子群搜索到的最好位置（全局最好位置）；c1，c2為學(xué)習(xí)因子，c1主要調(diào)節(jié)樣本例子向自身最好位置優(yōu)化的速度，c2調(diào)節(jié)樣本例子向全局優(yōu)化的速度；rand1，rand2為［0，1］上的兩個(gè)相互獨(dú)立的隨機(jī)數(shù)。

2.4 樣本優(yōu)化

當(dāng)時(shí)刻t發(fā)生拓?fù)渥兓瘯r(shí)，即Tn2，T2n，T12，T21不為空。此時(shí)可用粒子群優(yōu)化算法對(duì)已經(jīng)采到的N個(gè)樣本點(diǎn)進(jìn)行優(yōu)化。當(dāng)時(shí)刻t無(wú)任何拓?fù)渥兓瘯r(shí)，如圖4所示，未知節(jié)點(diǎn)當(dāng)前與上一時(shí)刻的鄰近錨節(jié)點(diǎn)列表無(wú)變化，即Tn2，T2n，T12，T21均為空。此時(shí)如果再使用粒子群來(lái)優(yōu)化將沒(méi)有任何意義。由于節(jié)點(diǎn)通常是保持平滑的移動(dòng)，因此這種情況下當(dāng)前時(shí)刻的位置與前面幾個(gè)時(shí)刻的位置相關(guān)。采用牛頓二次插值算法可以預(yù)測(cè)節(jié)點(diǎn)位置，同時(shí)避免多次過(guò)濾和預(yù)測(cè)，減少算法定位所需時(shí)間。

圖4 拓?fù)浣Y(jié)構(gòu)無(wú)變化時(shí)

假設(shè)前3個(gè)連續(xù)時(shí)刻的坐標(biāo)分別為（xt-3，yt-3），（xt-2，yt-2），（xt-1，yt-1），此時(shí)可分別對(duì)x和y方向的數(shù)據(jù)采用二次牛頓插值：

式中：（xt，yt）即為未知節(jié)點(diǎn)在t時(shí)刻的估計(jì)位置。

2.5 樣本過(guò)濾階段

算法根據(jù)k跳范圍內(nèi)的錨節(jié)點(diǎn)以及優(yōu)于自身的一跳鄰居節(jié)點(diǎn)信息實(shí)現(xiàn)濾波加權(quán)。第i個(gè)粒子的加權(quán)值wi等于上述各個(gè)節(jié)點(diǎn)加權(quán)因子的乘積。

對(duì)于錨節(jié)點(diǎn)，加權(quán)因子定義如下：

式中：d代表樣本與錨節(jié)點(diǎn)的歐式空間距離，h為兩者間的跳數(shù)。

2.6 位置確定及誤差計(jì)算

最后統(tǒng)計(jì)的樣本數(shù)目如果還是不足N，就需要重復(fù)從預(yù)測(cè)階段開(kāi)始，將采樣半徑增加δ即為vmax+δ擴(kuò)大一倍在新區(qū)域重新采樣并執(zhí)行后續(xù)操作，反復(fù)直至達(dá)到樣本點(diǎn)的數(shù)目。此時(shí)，可計(jì)算出移動(dòng)節(jié)點(diǎn)在t時(shí)刻的位置：

定位誤差是指節(jié)點(diǎn)實(shí)際位置和估算位置之間的距離差。節(jié)點(diǎn)定位誤差計(jì)算公式為：

3 仿真及分析

算法的實(shí)驗(yàn)仿真在MATLAB平臺(tái)下進(jìn)行，仿真區(qū)域?yàn)殚L(zhǎng)度250 m，寬度250 m的矩形，節(jié)點(diǎn)速度在［0，vmax］內(nèi)隨機(jī)選取，節(jié)點(diǎn)的通信半徑為r，節(jié)點(diǎn)移動(dòng)模型采用高斯馬爾可夫移動(dòng)模型。節(jié)點(diǎn)均沒(méi)有測(cè)距能力，但可以判斷某個(gè)節(jié)點(diǎn)是否在其一跳或者二跳通信范圍內(nèi)。默認(rèn)條件的仿真參數(shù)為：節(jié)點(diǎn)總數(shù)CN=51，其中錨節(jié)點(diǎn)數(shù)目CA=50，未知節(jié)點(diǎn)數(shù)目UN=1，通信半徑r=25 m，未知節(jié)點(diǎn)最大速度Vmax= 0.2r。為了使比較結(jié)果更具有平等而有說(shuō)服力，MCL和TMCL算法在同一場(chǎng)景和條件下運(yùn)行，且節(jié)點(diǎn)采用統(tǒng)一的運(yùn)動(dòng)步調(diào)。由于此算法為基于MCL算法的改進(jìn)，故實(shí)驗(yàn)將對(duì)二者進(jìn)行比較分析。

3.1 定位誤差

待定位節(jié)點(diǎn)的真實(shí)位置和估算位置之間的差值稱為定位誤差。在靜態(tài)網(wǎng)絡(luò)中，定位誤差不會(huì)與時(shí)間有關(guān)；然而在動(dòng)態(tài)網(wǎng)絡(luò)中，節(jié)點(diǎn)的運(yùn)動(dòng)特性會(huì)直接影響定位，因此不同時(shí)刻定位誤差不同。

圖5對(duì)未知節(jié)點(diǎn)在20個(gè)時(shí)間周期內(nèi)的定位誤差進(jìn)行了對(duì)比。由于MCL算法是跟前面時(shí)刻的位置有著密切關(guān)系的算法，因此在初始定位時(shí)，由于缺少先驗(yàn)值，前面的估計(jì)位置對(duì)后面的定位沒(méi)有幫助，兩種算法定位誤差都比較大。隨著節(jié)點(diǎn)移動(dòng)，兩者算法都達(dá)到一個(gè)穩(wěn)定的定位階段，但TMCL算法保持了一個(gè)較高的精度，這是因?yàn)槠涑浞掷霉?jié)點(diǎn)運(yùn)動(dòng)過(guò)程中的拓?fù)浣Y(jié)構(gòu)的變化，提高了樣本質(zhì)量。此外因?yàn)槔鄯e誤差的影響，在后續(xù)定位中會(huì)使定位誤差小幅度上升。TMCL算法的定位精度要比MCL算法高15%～25%，平均提高18%。

圖5 步長(zhǎng)與定位誤差關(guān)系

3.2 最大運(yùn)行速度

圖6描述了移動(dòng)速度對(duì)定位誤差的影響。仿真結(jié)果顯示，MCL和TMCL算法隨著速度的增大精度都有個(gè)先降后升的趨勢(shì)，因?yàn)楣?jié)點(diǎn)速度增大首先會(huì)直接使得下一時(shí)刻的采樣區(qū)域的變大，從而使定位誤差增大；同時(shí)節(jié)點(diǎn)會(huì)收到更多的信標(biāo)節(jié)點(diǎn)位置信息，它有利于過(guò)濾掉不可能的位置，從而使定位誤差減少。從圖6中可以看出，當(dāng)速度趨近0.4 r時(shí)定位誤差最小，當(dāng)速度繼續(xù)增大時(shí)，由于采樣接收概率也增大，過(guò)濾失效可能性加大。導(dǎo)致定位誤差也隨之增大。但是此過(guò)程中TMCL的精度始終高于MCL算法。

圖6 最大速度與定位誤差關(guān)系

3.3 錨節(jié)點(diǎn)密度

錨節(jié)點(diǎn)密度取決于當(dāng)前場(chǎng)景范圍內(nèi)的錨節(jié)點(diǎn)數(shù)目的多少，對(duì)定位算法的好壞影響很大。當(dāng)錨節(jié)點(diǎn)密度增加時(shí)，錨節(jié)點(diǎn)的多少在蒙特卡洛算法中會(huì)影響濾波環(huán)節(jié)得到的采樣粒子的好壞程度，定位精度也會(huì)隨之提高?？紤]到錨節(jié)點(diǎn)成本較高，所以定位算法在錨節(jié)點(diǎn)密度低時(shí)也應(yīng)該有一定的定位精度。

如圖7所示，MCL和TMCL算法隨著錨節(jié)點(diǎn)密度的增大，定位誤差會(huì)呈現(xiàn)明顯的下降趨勢(shì)。當(dāng)錨節(jié)點(diǎn)數(shù)目較少時(shí)，MCL算法和TMCL算法的定位誤差相差不大，MCL算法提高精度幅度不大，這是因?yàn)殄^節(jié)點(diǎn)太少時(shí)導(dǎo)致未知節(jié)點(diǎn)能獲得的觀測(cè)信息會(huì)減少，其相應(yīng)的拓?fù)浣Y(jié)構(gòu)變化就會(huì)明顯減少，這時(shí)使用牛頓插值算法對(duì)精度沒(méi)有任何提高，一旦錨節(jié)點(diǎn)數(shù)量超過(guò)30，大量的拓?fù)浣Y(jié)構(gòu)變化對(duì)精度有著明顯的提高。TMCL算法的定位誤差比MCL算法低16%～22%，平均低19%。

圖7 錨節(jié)點(diǎn)數(shù)量與定位誤差關(guān)系

3.4 定位時(shí)間

定位時(shí)間是指整個(gè)定位算法完成一次定位所需要的時(shí)間，是定位算法需要考慮的一個(gè)重要指標(biāo)之一。TMCL算法在拓?fù)浣Y(jié)構(gòu)變化趨勢(shì)構(gòu)建階段所需時(shí)間不多，但在粒子群算法優(yōu)化樣本點(diǎn)時(shí)，需要進(jìn)行多次迭代，在一定程度上增加了定位算法的計(jì)算量。在樣本優(yōu)化時(shí)，由于利用了牛頓插值算法，因此可以避免反復(fù)預(yù)測(cè)和過(guò)濾，達(dá)到減少算法計(jì)算量的目的。如圖8所示，TMCL算法的定位時(shí)間會(huì)比MCL算法多，說(shuō)明粒子群算法比牛頓插值算法所需要的時(shí)間復(fù)雜度更高。但MCL和TMCL算法兩者之間定位時(shí)間差距并不是很明顯，因此TMCL算法在時(shí)間復(fù)雜度上還是可以接受的。

圖8 錨節(jié)點(diǎn)數(shù)量與定位時(shí)間關(guān)系

4 結(jié)語(yǔ)

位置服務(wù)作為無(wú)線傳感網(wǎng)絡(luò)常用的服務(wù)之一，移動(dòng)傳感器網(wǎng)絡(luò)中位置信息的缺乏讓多數(shù)定位算法很難有個(gè)很好的精度。本文根據(jù)移動(dòng)傳感網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)導(dǎo)致拓?fù)浣Y(jié)構(gòu)的變化和原始的蒙特卡洛算法，提出了一種基于拓?fù)浣Y(jié)構(gòu)變化的TMCL算法。該方法能夠?qū)⑼負(fù)浣Y(jié)構(gòu)的變化保存下來(lái)，拓?fù)浣Y(jié)構(gòu)的變化可用來(lái)提高采樣效率，同時(shí)粒子群優(yōu)化算法優(yōu)化當(dāng)前已經(jīng)采到的樣本。仿真結(jié)果表明，該算法有較高的定位精度。該算法可廣泛應(yīng)用于室內(nèi)人員定位跟蹤、野生動(dòng)物保護(hù)、病人監(jiān)護(hù)等行業(yè)領(lǐng)域。

［1］ Chen H，Sezaki K，Deng P，et al.AnImprovedDV-Hop Localization Algorithm for Wireless Sensor Networks［C］// Industrial Electronics and Applications，2008.ICIEA 2008.3rd IEEE Conference on.IEEE，2008：1557-1561.

［2］ Doherty L，Pister K S J.Convex Position Estimation in Wireless Sensor Networks［C］//Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，Anchorage，2001，3：1655-1663.

［3］ Cheng W H，Li J，Li H.An Improved APIT Location Algorithm for Wireless Sensor Networks［M］.Advances in Electrical Engineering and Automation.Springer Berlin Heidelberg，2012：113-119.

［4］ Yj S，Rmnl W，Zhang Y.et al.Localization from Mere Connectivity ［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoe Networking and Computing，Maryland，2003：201-212.

［5］ Hu Lingxuan，Evans D.Localization for Mobile Sensor Networks ［C］//Proceedings of MobiCom 2004，Philadelphia，Pennsylvania，USA，2004：45-57.

［6］ 匡興紅，邵惠鶴.一種新的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，2008，21（1）：174-177.

［7］ Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Networks［J］.Ad Hoc Networks，2008，6（5）：718-733.

［8］ 曾凡仔，孫正章，羅娟，等.無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位方法［J］.通信學(xué)報(bào)，2009，29（11）：62-66.

［9］ 朱海平，于紅丞，鐘小勇，等.動(dòng)態(tài)無(wú)線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，25（9）：1284-1288.

［10］Rudafshani Mand Datta S.Localization in Wireless Sensor Networks ［C］//6th International Symposium on IPSN.Cambridge，MA，USA，Apr.25-27，2007：51-60.

［11］ Stevens-navarro E，Vivekanandan V，WONG V W S.Dual and Mixture Monte Carlo Localization Algorithms for Mobile Wireless Sensor Networks［C］//IEEE Wireless Communications and Networking Conference，Hong Kong，China，Mar 11-15，2007：4027-4031.

［12］李牧東，熊偉，梁青.基于人工蜂群改進(jìn)算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（2）：241-245.

［13］黃梅根，常新峰.一種基于蒙特卡羅法的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23（4）：562-566.

［14］Yi J，Yang S，Cha H.Multi-Hop-Based Monte Carlo Localization for Mobile Sensor Networks［C］//Proceedings of IEEE SECON 2007，San Diego，California，USA，June 18-21，2007：162-171.

［15］Wang W D，Zhu Q X.RSS-Based Monte Carlo Localization for Mobile Sensor Networks［J］.IET Communications，2008，2（5）：673-681.

［16］DIL B，DULMAN S，HAVINGA P.Range-Based Localization in Mobile Sensor Networks［C］//Proceedings of EWSN 2006，Zurich，Switzerland，F(xiàn)eb.13-15，2006：164-179.

曹樹(shù)林（1991-），男，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，caosl158 @gmail.com；

單志龍（1976-），男，博士，教授，碩士生導(dǎo)師，主要研究方向?yàn)槲锫?lián)網(wǎng)、無(wú)線傳感器網(wǎng)絡(luò)、無(wú)線通信網(wǎng)絡(luò)等，zhilongshan@gmail.com。

A MCL Optimization Algorithm Based on The Changes of Topological Structure for Mobile WSN*

CAO Shulin，SHAN Zhilong*，WU Xiaolin，CAO Chuqun
（School of Computer Science，South China Normal University，Guangzhou 510631，China）

The paper presents a high precision of localization algorithm in mobile sensor networks.The algorithm utilizes topological change of unknown nodes during the process of node motion to improve utilization of anchor node and the efficiency of sampling.In the case of no topological change，Newton interpolation will be adopted to calculate the current position of the node and when the topology changes，the fitness function will be created with the changes，then the particle swarm optimization will be applied to optimize the sample quality.Simulation result show that the algorithm outperforms the tranditional algorithm in convergence speed，localiization accuracy，and requirement of node density.

WSN；changes of topological；monte carlo localization；particle swarm optimization；newton interpolation EEACC：7230

TP309

A

1004-1699（2015）04-0537-07

10.3969/j.issn.1004-1699.2015.04.015

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61102065，61370003）；廣東省科技計(jì)劃項(xiàng)目（2013B040401014）；廣東省自然科學(xué)基金項(xiàng)目（S2012040010974）

2014-09-28 修改日期：2015-01-14