一種基于蒙特卡洛的移動(dòng)傳感網(wǎng)節(jié)點(diǎn)定位的優(yōu)化算法

李坤++何月順

摘要：在無線傳感網(wǎng)中，針對(duì)蒙特卡洛移動(dòng)節(jié)點(diǎn)定位算法中通信半徑無法確定這一缺陷，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的蒙特卡洛定位改進(jìn)算法。該算法首先利用實(shí)際中測得節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，進(jìn)而精化出一個(gè)環(huán)形采樣區(qū)域，提高了采樣效率。仿真結(jié)果表明，優(yōu)化之后的算法能夠顯著地減少定位采樣次數(shù)，能夠有效提高定位的準(zhǔn)確性，并且能改善網(wǎng)絡(luò)中低錨節(jié)點(diǎn)密度時(shí)的性能。

關(guān)鍵詞：無線傳感網(wǎng) 移動(dòng)定位 蒙特卡洛 跳＼距轉(zhuǎn)換模型 采樣優(yōu)化

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0123-02

1 引言

無線傳感技術(shù)在信息科技的各個(gè)領(lǐng)域已經(jīng)得到越來越廣泛的應(yīng)用，傳感器測得的數(shù)據(jù)要和它自身的位置信息相結(jié)合才有意義。如何更高效、更精準(zhǔn)地獲取無線傳感網(wǎng)（wireless sensor network，WSN）中節(jié)點(diǎn)的位置信息是WSN研究的當(dāng)務(wù)之急。大部分的定位算法都是針對(duì)靜態(tài)WSN網(wǎng)絡(luò)的，倘若將靜態(tài)WSN定位算法應(yīng)用于移動(dòng)WSN絡(luò)中，由于節(jié)點(diǎn)的運(yùn)動(dòng)性會(huì)導(dǎo)致定位的精度下降，節(jié)點(diǎn)能量消耗加快等問題，很多針對(duì)移動(dòng)WSN定位的方法應(yīng)運(yùn)而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了節(jié)點(diǎn)的移動(dòng)性，能夠取得較好的定位精度，得到了廣泛的應(yīng)用。以MCL為基礎(chǔ)，很多專家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)通信半徑無法確定，且經(jīng)典MCL采樣過程繁瑣，采樣效率低下，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的MCL優(yōu)化算法，避免直接使用節(jié)點(diǎn)的通信半徑確定采樣區(qū)域，而且能夠取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類數(shù)值計(jì)算方法。它應(yīng)用于移動(dòng)WSN節(jié)點(diǎn)定位中可以描述為：

（1）結(jié)合未知節(jié)點(diǎn)上一時(shí)刻位置和運(yùn)動(dòng)模型，得到一個(gè)圓形的均勻采樣區(qū)域進(jìn)行采樣。（2）利用未知節(jié)點(diǎn)與觀測到的附近錨節(jié)點(diǎn)的距離信息對(duì)樣本進(jìn)行過濾，過濾條件為 ，其中、分別代表一、二跳錨節(jié)點(diǎn)，代表通信半徑，代表采樣坐標(biāo)。（3）過濾掉一部分采樣樣本之后再重復(fù)進(jìn)行上述步驟，直到得到足夠數(shù)量的樣本數(shù)，給每個(gè)樣本賦予權(quán)值，就可以估算出未知節(jié)點(diǎn)的位置。但經(jīng)典MCL在實(shí)際應(yīng)用中并不能得到理想?yún)?shù)值，比如說節(jié)點(diǎn)通信半徑會(huì)隨著高度的變化而發(fā)生較大的改變。為了解決這些問題，我們需要對(duì)原算法進(jìn)行一些改進(jìn)使它能更好的應(yīng)用于實(shí)際中。

3 一種新的蒙特卡洛定位改進(jìn)算法

本文基于MCL提出了一種叫做HDMCL的定位算法，該算法利用節(jié)點(diǎn)間跳數(shù)信息估算未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，再規(guī)劃出一個(gè)精化的采樣區(qū)域，解決了通信半徑波動(dòng)大的困難，且定位精度和采樣效率上都有明顯的提升。

3.1 跳＼距（H＼D）轉(zhuǎn)換模型

H＼D轉(zhuǎn)換模型可利用節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)間的距離信息，描述如下：

（1）網(wǎng)絡(luò)中所有節(jié)點(diǎn)洪泛和接收其他節(jié)點(diǎn)的跳數(shù)信息；（2）錨節(jié)點(diǎn)在洪泛和接收跳數(shù)信息的同時(shí)還要傳播坐標(biāo)值。計(jì)算出與其他錨節(jié)點(diǎn)距離的和值及跳數(shù)的和值，分別記為、。它們的比值即為的平均跳距值，記為。（3）未知節(jié)點(diǎn)從與之跳數(shù)最小的一個(gè)錨節(jié)點(diǎn)獲取平均跳距值，記為，用乘上它與其他錨節(jié)點(diǎn)的跳數(shù)值，即可以獲得它與所有錨節(jié)點(diǎn)的距離。

3.2 環(huán)形采樣區(qū)域確定

將每個(gè)未知節(jié)點(diǎn)與其他錨節(jié)點(diǎn)的距離，記為，表示未知節(jié)點(diǎn)，表示錨節(jié)點(diǎn)。假設(shè)未知節(jié)點(diǎn)的坐標(biāo)為，錨節(jié)點(diǎn)坐標(biāo)為，利用多邊測量法即可計(jì)算出每個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，具體方法流程如下：

（1）未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的歐氏距離表示為：

（2）分別用式1中第2至n個(gè)方程分別減去第1個(gè)方程：

用A表示方程組系數(shù)項(xiàng)

用b表示方程組常數(shù)項(xiàng)

（3）解出未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值：

通過上述方法，得到各個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值，同時(shí)提取出未知節(jié)點(diǎn)周圍錨節(jié)點(diǎn)信息，分別計(jì)算未知節(jié)點(diǎn)與其一、二跳錨節(jié)點(diǎn)的歐氏距離作為環(huán)形區(qū)域的參考半徑，記為，m表示預(yù)估計(jì)坐標(biāo)，n表示一、二跳錨節(jié)點(diǎn)坐標(biāo)。參考半徑分別乘上參數(shù)因子α和β，和分別作為環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)的半徑，考慮到預(yù)估計(jì)坐標(biāo)位置存在誤差，且誤差是在一定范圍內(nèi)服從均勻分布的，所以環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)是參考圓的等比縮小或者擴(kuò)大，所以α和β可以表示為和，，只要選取合適的，就能用最小的代價(jià)換取最大的采樣效率。結(jié)合上述信息可以構(gòu)造出一個(gè)精化的定位采樣環(huán)形區(qū)域，如圖1所示，陰影處即為采樣區(qū)域。

4 仿真與分析

本文使用MATLAB R2013B仿真軟件對(duì)算法進(jìn)行分析，仿真環(huán)境如表1所示。

4.1 定位精度

圖2中兩條曲線分別描述WSN所有節(jié)點(diǎn)分別運(yùn)行MCL算法和HDMCL算法得到的平均定位誤差情況，本方案模擬前10個(gè)時(shí)間步的誤差情況?？梢钥闯鲇捎谠诙ㄎ贿^程中精化了濾波條件，HDMCL算法中節(jié)點(diǎn)的平均定位誤差相比于經(jīng)典的MCL算法的平均定位誤差有所減小，優(yōu)化的比例是3%至8%不等，定位精度平均優(yōu)化了5.01%。

4.2 采樣效率

圖3為HDMCL算法中采樣次數(shù)由100減為50，MCL采樣次數(shù)仍為100，其他定位條件不變的節(jié)點(diǎn)定位誤差對(duì)比圖，可以看出相比于傳統(tǒng)MCL算法，節(jié)點(diǎn)定位精度仍然平均優(yōu)化了3.57%，這是由于在HDMCL算法中，采樣區(qū)域是由若干個(gè)環(huán)形區(qū)域的交集精化而來的，取代了傳統(tǒng)MCL通過通信半徑確定的采樣區(qū)域，所以采樣效率有明顯的改善。

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

錨節(jié)點(diǎn)密度是WSN節(jié)點(diǎn)定位的重要參考指標(biāo)，本文對(duì)網(wǎng)絡(luò)中錨節(jié)點(diǎn)不同個(gè)數(shù)情況下的未知節(jié)點(diǎn)定位情況進(jìn)行分析，錨節(jié)點(diǎn)個(gè)數(shù)分別為7至25個(gè)不等，由圖4可以看出平均定位誤差是隨著錨節(jié)點(diǎn)密度的增加而減小，HDMCL算法中，錨節(jié)點(diǎn)密度越低時(shí)，定位精度相比于經(jīng)典MCL算法優(yōu)化效果更明顯。這說明在低錨節(jié)點(diǎn)密度情況下HDMCL有著更好的定位效果。

5 結(jié)語

本文提出了一種基于蒙特卡洛算法的移動(dòng)WSN定位改進(jìn)算法，該算法利用節(jié)點(diǎn)間相互感知的跳數(shù)信息和錨節(jié)點(diǎn)信息得到一個(gè)精化的環(huán)形采樣區(qū)域，取得了較好的定位效果。仿真表明該算法相比于蒙特卡洛方法有更好的定位精度，此外，在采樣效率方面有了很大的改善，并且在錨節(jié)點(diǎn)密度較低的WSN環(huán)境下有更顯著的優(yōu)化效果。目前該能很好的應(yīng)用于規(guī)則的網(wǎng)絡(luò)環(huán)境，但并不能很好的應(yīng)用于復(fù)雜地形，這一點(diǎn)還有待研究。

參考文獻(xiàn)

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法[J].傳感技術(shù)學(xué)報(bào)，2012.

[5]孫燕.基于采樣優(yōu)化的蒙特卡羅移動(dòng)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù)，2010.endprint

摘要：在無線傳感網(wǎng)中，針對(duì)蒙特卡洛移動(dòng)節(jié)點(diǎn)定位算法中通信半徑無法確定這一缺陷，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的蒙特卡洛定位改進(jìn)算法。該算法首先利用實(shí)際中測得節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，進(jìn)而精化出一個(gè)環(huán)形采樣區(qū)域，提高了采樣效率。仿真結(jié)果表明，優(yōu)化之后的算法能夠顯著地減少定位采樣次數(shù)，能夠有效提高定位的準(zhǔn)確性，并且能改善網(wǎng)絡(luò)中低錨節(jié)點(diǎn)密度時(shí)的性能。

關(guān)鍵詞：無線傳感網(wǎng) 移動(dòng)定位 蒙特卡洛 跳＼距轉(zhuǎn)換模型 采樣優(yōu)化

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0123-02

1 引言

無線傳感技術(shù)在信息科技的各個(gè)領(lǐng)域已經(jīng)得到越來越廣泛的應(yīng)用，傳感器測得的數(shù)據(jù)要和它自身的位置信息相結(jié)合才有意義。如何更高效、更精準(zhǔn)地獲取無線傳感網(wǎng)（wireless sensor network，WSN）中節(jié)點(diǎn)的位置信息是WSN研究的當(dāng)務(wù)之急。大部分的定位算法都是針對(duì)靜態(tài)WSN網(wǎng)絡(luò)的，倘若將靜態(tài)WSN定位算法應(yīng)用于移動(dòng)WSN絡(luò)中，由于節(jié)點(diǎn)的運(yùn)動(dòng)性會(huì)導(dǎo)致定位的精度下降，節(jié)點(diǎn)能量消耗加快等問題，很多針對(duì)移動(dòng)WSN定位的方法應(yīng)運(yùn)而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了節(jié)點(diǎn)的移動(dòng)性，能夠取得較好的定位精度，得到了廣泛的應(yīng)用。以MCL為基礎(chǔ)，很多專家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)通信半徑無法確定，且經(jīng)典MCL采樣過程繁瑣，采樣效率低下，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的MCL優(yōu)化算法，避免直接使用節(jié)點(diǎn)的通信半徑確定采樣區(qū)域，而且能夠取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類數(shù)值計(jì)算方法。它應(yīng)用于移動(dòng)WSN節(jié)點(diǎn)定位中可以描述為：

（1）結(jié)合未知節(jié)點(diǎn)上一時(shí)刻位置和運(yùn)動(dòng)模型，得到一個(gè)圓形的均勻采樣區(qū)域進(jìn)行采樣。（2）利用未知節(jié)點(diǎn)與觀測到的附近錨節(jié)點(diǎn)的距離信息對(duì)樣本進(jìn)行過濾，過濾條件為 ，其中、分別代表一、二跳錨節(jié)點(diǎn)，代表通信半徑，代表采樣坐標(biāo)。（3）過濾掉一部分采樣樣本之后再重復(fù)進(jìn)行上述步驟，直到得到足夠數(shù)量的樣本數(shù)，給每個(gè)樣本賦予權(quán)值，就可以估算出未知節(jié)點(diǎn)的位置。但經(jīng)典MCL在實(shí)際應(yīng)用中并不能得到理想?yún)?shù)值，比如說節(jié)點(diǎn)通信半徑會(huì)隨著高度的變化而發(fā)生較大的改變。為了解決這些問題，我們需要對(duì)原算法進(jìn)行一些改進(jìn)使它能更好的應(yīng)用于實(shí)際中。

3 一種新的蒙特卡洛定位改進(jìn)算法

本文基于MCL提出了一種叫做HDMCL的定位算法，該算法利用節(jié)點(diǎn)間跳數(shù)信息估算未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，再規(guī)劃出一個(gè)精化的采樣區(qū)域，解決了通信半徑波動(dòng)大的困難，且定位精度和采樣效率上都有明顯的提升。

3.1 跳＼距（H＼D）轉(zhuǎn)換模型

H＼D轉(zhuǎn)換模型可利用節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)間的距離信息，描述如下：

（1）網(wǎng)絡(luò)中所有節(jié)點(diǎn)洪泛和接收其他節(jié)點(diǎn)的跳數(shù)信息；（2）錨節(jié)點(diǎn)在洪泛和接收跳數(shù)信息的同時(shí)還要傳播坐標(biāo)值。計(jì)算出與其他錨節(jié)點(diǎn)距離的和值及跳數(shù)的和值，分別記為、。它們的比值即為的平均跳距值，記為。（3）未知節(jié)點(diǎn)從與之跳數(shù)最小的一個(gè)錨節(jié)點(diǎn)獲取平均跳距值，記為，用乘上它與其他錨節(jié)點(diǎn)的跳數(shù)值，即可以獲得它與所有錨節(jié)點(diǎn)的距離。

3.2 環(huán)形采樣區(qū)域確定

將每個(gè)未知節(jié)點(diǎn)與其他錨節(jié)點(diǎn)的距離，記為，表示未知節(jié)點(diǎn)，表示錨節(jié)點(diǎn)。假設(shè)未知節(jié)點(diǎn)的坐標(biāo)為，錨節(jié)點(diǎn)坐標(biāo)為，利用多邊測量法即可計(jì)算出每個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，具體方法流程如下：

（1）未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的歐氏距離表示為：

（2）分別用式1中第2至n個(gè)方程分別減去第1個(gè)方程：

用A表示方程組系數(shù)項(xiàng)

用b表示方程組常數(shù)項(xiàng)

（3）解出未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值：

通過上述方法，得到各個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值，同時(shí)提取出未知節(jié)點(diǎn)周圍錨節(jié)點(diǎn)信息，分別計(jì)算未知節(jié)點(diǎn)與其一、二跳錨節(jié)點(diǎn)的歐氏距離作為環(huán)形區(qū)域的參考半徑，記為，m表示預(yù)估計(jì)坐標(biāo)，n表示一、二跳錨節(jié)點(diǎn)坐標(biāo)。參考半徑分別乘上參數(shù)因子α和β，和分別作為環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)的半徑，考慮到預(yù)估計(jì)坐標(biāo)位置存在誤差，且誤差是在一定范圍內(nèi)服從均勻分布的，所以環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)是參考圓的等比縮小或者擴(kuò)大，所以α和β可以表示為和，，只要選取合適的，就能用最小的代價(jià)換取最大的采樣效率。結(jié)合上述信息可以構(gòu)造出一個(gè)精化的定位采樣環(huán)形區(qū)域，如圖1所示，陰影處即為采樣區(qū)域。

4 仿真與分析

本文使用MATLAB R2013B仿真軟件對(duì)算法進(jìn)行分析，仿真環(huán)境如表1所示。

4.1 定位精度

圖2中兩條曲線分別描述WSN所有節(jié)點(diǎn)分別運(yùn)行MCL算法和HDMCL算法得到的平均定位誤差情況，本方案模擬前10個(gè)時(shí)間步的誤差情況?？梢钥闯鲇捎谠诙ㄎ贿^程中精化了濾波條件，HDMCL算法中節(jié)點(diǎn)的平均定位誤差相比于經(jīng)典的MCL算法的平均定位誤差有所減小，優(yōu)化的比例是3%至8%不等，定位精度平均優(yōu)化了5.01%。

4.2 采樣效率

圖3為HDMCL算法中采樣次數(shù)由100減為50，MCL采樣次數(shù)仍為100，其他定位條件不變的節(jié)點(diǎn)定位誤差對(duì)比圖，可以看出相比于傳統(tǒng)MCL算法，節(jié)點(diǎn)定位精度仍然平均優(yōu)化了3.57%，這是由于在HDMCL算法中，采樣區(qū)域是由若干個(gè)環(huán)形區(qū)域的交集精化而來的，取代了傳統(tǒng)MCL通過通信半徑確定的采樣區(qū)域，所以采樣效率有明顯的改善。

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

錨節(jié)點(diǎn)密度是WSN節(jié)點(diǎn)定位的重要參考指標(biāo)，本文對(duì)網(wǎng)絡(luò)中錨節(jié)點(diǎn)不同個(gè)數(shù)情況下的未知節(jié)點(diǎn)定位情況進(jìn)行分析，錨節(jié)點(diǎn)個(gè)數(shù)分別為7至25個(gè)不等，由圖4可以看出平均定位誤差是隨著錨節(jié)點(diǎn)密度的增加而減小，HDMCL算法中，錨節(jié)點(diǎn)密度越低時(shí)，定位精度相比于經(jīng)典MCL算法優(yōu)化效果更明顯。這說明在低錨節(jié)點(diǎn)密度情況下HDMCL有著更好的定位效果。

5 結(jié)語

本文提出了一種基于蒙特卡洛算法的移動(dòng)WSN定位改進(jìn)算法，該算法利用節(jié)點(diǎn)間相互感知的跳數(shù)信息和錨節(jié)點(diǎn)信息得到一個(gè)精化的環(huán)形采樣區(qū)域，取得了較好的定位效果。仿真表明該算法相比于蒙特卡洛方法有更好的定位精度，此外，在采樣效率方面有了很大的改善，并且在錨節(jié)點(diǎn)密度較低的WSN環(huán)境下有更顯著的優(yōu)化效果。目前該能很好的應(yīng)用于規(guī)則的網(wǎng)絡(luò)環(huán)境，但并不能很好的應(yīng)用于復(fù)雜地形，這一點(diǎn)還有待研究。

參考文獻(xiàn)

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法[J].傳感技術(shù)學(xué)報(bào)，2012.

[5]孫燕.基于采樣優(yōu)化的蒙特卡羅移動(dòng)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù)，2010.endprint

摘要：在無線傳感網(wǎng)中，針對(duì)蒙特卡洛移動(dòng)節(jié)點(diǎn)定位算法中通信半徑無法確定這一缺陷，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的蒙特卡洛定位改進(jìn)算法。該算法首先利用實(shí)際中測得節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，進(jìn)而精化出一個(gè)環(huán)形采樣區(qū)域，提高了采樣效率。仿真結(jié)果表明，優(yōu)化之后的算法能夠顯著地減少定位采樣次數(shù)，能夠有效提高定位的準(zhǔn)確性，并且能改善網(wǎng)絡(luò)中低錨節(jié)點(diǎn)密度時(shí)的性能。

關(guān)鍵詞：無線傳感網(wǎng) 移動(dòng)定位 蒙特卡洛 跳＼距轉(zhuǎn)換模型 采樣優(yōu)化

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0123-02

1 引言

無線傳感技術(shù)在信息科技的各個(gè)領(lǐng)域已經(jīng)得到越來越廣泛的應(yīng)用，傳感器測得的數(shù)據(jù)要和它自身的位置信息相結(jié)合才有意義。如何更高效、更精準(zhǔn)地獲取無線傳感網(wǎng)（wireless sensor network，WSN）中節(jié)點(diǎn)的位置信息是WSN研究的當(dāng)務(wù)之急。大部分的定位算法都是針對(duì)靜態(tài)WSN網(wǎng)絡(luò)的，倘若將靜態(tài)WSN定位算法應(yīng)用于移動(dòng)WSN絡(luò)中，由于節(jié)點(diǎn)的運(yùn)動(dòng)性會(huì)導(dǎo)致定位的精度下降，節(jié)點(diǎn)能量消耗加快等問題，很多針對(duì)移動(dòng)WSN定位的方法應(yīng)運(yùn)而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了節(jié)點(diǎn)的移動(dòng)性，能夠取得較好的定位精度，得到了廣泛的應(yīng)用。以MCL為基礎(chǔ)，很多專家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)通信半徑無法確定，且經(jīng)典MCL采樣過程繁瑣，采樣效率低下，本文提出了一種結(jié)合跳＼距轉(zhuǎn)換模型的MCL優(yōu)化算法，避免直接使用節(jié)點(diǎn)的通信半徑確定采樣區(qū)域，而且能夠取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類數(shù)值計(jì)算方法。它應(yīng)用于移動(dòng)WSN節(jié)點(diǎn)定位中可以描述為：

（1）結(jié)合未知節(jié)點(diǎn)上一時(shí)刻位置和運(yùn)動(dòng)模型，得到一個(gè)圓形的均勻采樣區(qū)域進(jìn)行采樣。（2）利用未知節(jié)點(diǎn)與觀測到的附近錨節(jié)點(diǎn)的距離信息對(duì)樣本進(jìn)行過濾，過濾條件為 ，其中、分別代表一、二跳錨節(jié)點(diǎn)，代表通信半徑，代表采樣坐標(biāo)。（3）過濾掉一部分采樣樣本之后再重復(fù)進(jìn)行上述步驟，直到得到足夠數(shù)量的樣本數(shù)，給每個(gè)樣本賦予權(quán)值，就可以估算出未知節(jié)點(diǎn)的位置。但經(jīng)典MCL在實(shí)際應(yīng)用中并不能得到理想?yún)?shù)值，比如說節(jié)點(diǎn)通信半徑會(huì)隨著高度的變化而發(fā)生較大的改變。為了解決這些問題，我們需要對(duì)原算法進(jìn)行一些改進(jìn)使它能更好的應(yīng)用于實(shí)際中。

3 一種新的蒙特卡洛定位改進(jìn)算法

本文基于MCL提出了一種叫做HDMCL的定位算法，該算法利用節(jié)點(diǎn)間跳數(shù)信息估算未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，再規(guī)劃出一個(gè)精化的采樣區(qū)域，解決了通信半徑波動(dòng)大的困難，且定位精度和采樣效率上都有明顯的提升。

3.1 跳＼距（H＼D）轉(zhuǎn)換模型

H＼D轉(zhuǎn)換模型可利用節(jié)點(diǎn)間的跳數(shù)信息得到節(jié)點(diǎn)間的距離信息，描述如下：

（1）網(wǎng)絡(luò)中所有節(jié)點(diǎn)洪泛和接收其他節(jié)點(diǎn)的跳數(shù)信息；（2）錨節(jié)點(diǎn)在洪泛和接收跳數(shù)信息的同時(shí)還要傳播坐標(biāo)值。計(jì)算出與其他錨節(jié)點(diǎn)距離的和值及跳數(shù)的和值，分別記為、。它們的比值即為的平均跳距值，記為。（3）未知節(jié)點(diǎn)從與之跳數(shù)最小的一個(gè)錨節(jié)點(diǎn)獲取平均跳距值，記為，用乘上它與其他錨節(jié)點(diǎn)的跳數(shù)值，即可以獲得它與所有錨節(jié)點(diǎn)的距離。

3.2 環(huán)形采樣區(qū)域確定

將每個(gè)未知節(jié)點(diǎn)與其他錨節(jié)點(diǎn)的距離，記為，表示未知節(jié)點(diǎn)，表示錨節(jié)點(diǎn)。假設(shè)未知節(jié)點(diǎn)的坐標(biāo)為，錨節(jié)點(diǎn)坐標(biāo)為，利用多邊測量法即可計(jì)算出每個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)，具體方法流程如下：

（1）未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的歐氏距離表示為：

（2）分別用式1中第2至n個(gè)方程分別減去第1個(gè)方程：

用A表示方程組系數(shù)項(xiàng)

用b表示方程組常數(shù)項(xiàng)

（3）解出未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值：

通過上述方法，得到各個(gè)未知節(jié)點(diǎn)的預(yù)估計(jì)坐標(biāo)值，同時(shí)提取出未知節(jié)點(diǎn)周圍錨節(jié)點(diǎn)信息，分別計(jì)算未知節(jié)點(diǎn)與其一、二跳錨節(jié)點(diǎn)的歐氏距離作為環(huán)形區(qū)域的參考半徑，記為，m表示預(yù)估計(jì)坐標(biāo)，n表示一、二跳錨節(jié)點(diǎn)坐標(biāo)。參考半徑分別乘上參數(shù)因子α和β，和分別作為環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)的半徑，考慮到預(yù)估計(jì)坐標(biāo)位置存在誤差，且誤差是在一定范圍內(nèi)服從均勻分布的，所以環(huán)形區(qū)域內(nèi)環(huán)和外環(huán)是參考圓的等比縮小或者擴(kuò)大，所以α和β可以表示為和，，只要選取合適的，就能用最小的代價(jià)換取最大的采樣效率。結(jié)合上述信息可以構(gòu)造出一個(gè)精化的定位采樣環(huán)形區(qū)域，如圖1所示，陰影處即為采樣區(qū)域。

4 仿真與分析

本文使用MATLAB R2013B仿真軟件對(duì)算法進(jìn)行分析，仿真環(huán)境如表1所示。

4.1 定位精度

圖2中兩條曲線分別描述WSN所有節(jié)點(diǎn)分別運(yùn)行MCL算法和HDMCL算法得到的平均定位誤差情況，本方案模擬前10個(gè)時(shí)間步的誤差情況。可以看出由于在定位過程中精化了濾波條件，HDMCL算法中節(jié)點(diǎn)的平均定位誤差相比于經(jīng)典的MCL算法的平均定位誤差有所減小，優(yōu)化的比例是3%至8%不等，定位精度平均優(yōu)化了5.01%。

4.2 采樣效率

圖3為HDMCL算法中采樣次數(shù)由100減為50，MCL采樣次數(shù)仍為100，其他定位條件不變的節(jié)點(diǎn)定位誤差對(duì)比圖，可以看出相比于傳統(tǒng)MCL算法，節(jié)點(diǎn)定位精度仍然平均優(yōu)化了3.57%，這是由于在HDMCL算法中，采樣區(qū)域是由若干個(gè)環(huán)形區(qū)域的交集精化而來的，取代了傳統(tǒng)MCL通過通信半徑確定的采樣區(qū)域，所以采樣效率有明顯的改善。

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

錨節(jié)點(diǎn)密度是WSN節(jié)點(diǎn)定位的重要參考指標(biāo)，本文對(duì)網(wǎng)絡(luò)中錨節(jié)點(diǎn)不同個(gè)數(shù)情況下的未知節(jié)點(diǎn)定位情況進(jìn)行分析，錨節(jié)點(diǎn)個(gè)數(shù)分別為7至25個(gè)不等，由圖4可以看出平均定位誤差是隨著錨節(jié)點(diǎn)密度的增加而減小，HDMCL算法中，錨節(jié)點(diǎn)密度越低時(shí)，定位精度相比于經(jīng)典MCL算法優(yōu)化效果更明顯。這說明在低錨節(jié)點(diǎn)密度情況下HDMCL有著更好的定位效果。

5 結(jié)語

本文提出了一種基于蒙特卡洛算法的移動(dòng)WSN定位改進(jìn)算法，該算法利用節(jié)點(diǎn)間相互感知的跳數(shù)信息和錨節(jié)點(diǎn)信息得到一個(gè)精化的環(huán)形采樣區(qū)域，取得了較好的定位效果。仿真表明該算法相比于蒙特卡洛方法有更好的定位精度，此外，在采樣效率方面有了很大的改善，并且在錨節(jié)點(diǎn)密度較低的WSN環(huán)境下有更顯著的優(yōu)化效果。目前該能很好的應(yīng)用于規(guī)則的網(wǎng)絡(luò)環(huán)境，但并不能很好的應(yīng)用于復(fù)雜地形，這一點(diǎn)還有待研究。

參考文獻(xiàn)

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法[J].傳感技術(shù)學(xué)報(bào)，2012.

[5]孫燕.基于采樣優(yōu)化的蒙特卡羅移動(dòng)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù)，2010.endprint