趙 明，喬鋼柱，介 婧

太原科技大學(xué) 復(fù)雜系統(tǒng)與智能計(jì)算研究所，太原 030024

基于Monte-Carlo方法的井下無線傳感網(wǎng)絡(luò)定位算法

趙 明，喬鋼柱，介 婧

太原科技大學(xué) 復(fù)雜系統(tǒng)與智能計(jì)算研究所，太原 030024

1 意義

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）成本低廉、布放簡單，被廣泛應(yīng)用于軍事、醫(yī)療、環(huán)境監(jiān)測、物流運(yùn)送、空間探測等多個(gè)領(lǐng)域。在大多數(shù)的無線傳感器網(wǎng)絡(luò)應(yīng)用中，傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息是不可或缺的，缺乏了位置數(shù)據(jù)，傳感器網(wǎng)絡(luò)采集到的數(shù)據(jù)將失去意義。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位技術(shù)是WSN應(yīng)用中的重要組成部分，也是無線傳感器網(wǎng)絡(luò)研究領(lǐng)域中的關(guān)鍵性支撐技術(shù)之一。

在井下，環(huán)境條件總是在不斷地變化，在這樣的環(huán)境里面定位需要穩(wěn)定、精確、且能長期有效。井下定位主要面臨如下問題，首先區(qū)域空間狹窄，巷道環(huán)境差異大，在地面上的一些定位方法在這里容易受限制。其次，井下可見度低，濕度大，并伴有煙霧及粉塵，無線通信易受影響。無線傳感器網(wǎng)絡(luò)的Monte-Carlo定位方法是用后驗(yàn)概率模型來進(jìn)行定位的一種方法，有較好的定位精度，有很好的健壯性，且能充分利用巷道空間狹窄的環(huán)境特點(diǎn)來做進(jìn)一步的改進(jìn)。

2 背景

無線傳感網(wǎng)絡(luò)定位按是否基于測距分為基于測距的定位算法和無須測距的定位算法?；跍y距的定位通過測量節(jié)點(diǎn)到節(jié)點(diǎn)間的距離、角度信息，然后利用三邊測距、三角測距或最大似然估計(jì)的方法進(jìn)行節(jié)點(diǎn)自身定位。典型的基于測距的定位算法有RSSI[1]，TOA[2]，TDOA[3]，AOA[4-5]等。這些算法大部分都需要增加額外的硬件設(shè)備，增加了節(jié)點(diǎn)的成本，同時(shí)又增加了節(jié)點(diǎn)的能耗。基于測距技術(shù)的定位在定位精度上有一定的優(yōu)勢，但在低功耗、低成本的應(yīng)用中還存在一些問題。無須測距技術(shù)的定位則不需要測量距離和角度，而是依據(jù)網(wǎng)絡(luò)的連通性來進(jìn)行定位，典型算法的有DV-Hop[6-7]、凸規(guī)劃[8-9]、MDS-MAP[10]等。而對于井下環(huán)境，無需測距的定位方法更有優(yōu)勢。

在井下，無線定位目前主要分為兩類，一類是基于射頻識別（Radio Frequency Identification，RFID）技術(shù)，如文獻(xiàn)[11]介紹了一種井下RFID讀卡器防碰撞算法，文獻(xiàn)[12]介紹了一種礦山井下RFID人員定位系統(tǒng)的定位原理實(shí)現(xiàn)過程，文獻(xiàn)[13]介紹了RFID井下人員定位在應(yīng)用上的幾個(gè)關(guān)鍵問題，并給出了適當(dāng)?shù)慕鉀Q方法。一類是通過傳感器節(jié)點(diǎn)來實(shí)現(xiàn)定位，如文獻(xiàn)[14]介紹了信標(biāo)節(jié)點(diǎn)鏈?zhǔn)讲渴鸬木聼o線傳感器網(wǎng)絡(luò)定位算法，文獻(xiàn)[15]介紹了井下無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)自適應(yīng)的系統(tǒng)。一般來講RFID定位時(shí)都是在區(qū)域入口或關(guān)鍵通道設(shè)置讀卡器，來記錄相關(guān)人員進(jìn)出記錄，實(shí)時(shí)性及精度上不如傳感器節(jié)點(diǎn)。而井下，人員的位置都是在劫態(tài)變化的，因此井下無線傳感器網(wǎng)絡(luò)需要能夠進(jìn)行移動(dòng)定位。

移動(dòng)無線傳感網(wǎng)定位無須測距的MCL（Monte-Carlo Location）定位算法最早由文獻(xiàn)[16]提出，其定位精度較好，能利用節(jié)點(diǎn)的移動(dòng)性提高算法的精度。本文便是結(jié)合井下環(huán)境的特點(diǎn)對MCL進(jìn)行了改進(jìn)提出了中心蒙特卡洛（Center Monte-Carlo Location，CMCL）算法。

3 MCL和MCB定位原理及過程

Hu和Evans提出的MCL（Monte-Carlo Location）定位算法[16]是用后驗(yàn)概率模型來進(jìn)行定位的一種方法，定位精度和效率很出色。MCL定位方法當(dāng)中分為初始化，采樣和過濾三部分，而把時(shí)間分為一個(gè)個(gè)時(shí)間片，對每個(gè)節(jié)點(diǎn)反復(fù)執(zhí)行進(jìn)行采樣和過濾來不斷地更新所在的位置。具體方法如下：把時(shí)間分成離散的時(shí)間片，用t表示其中某一個(gè)單獨(dú)的時(shí)間片，用lt表示當(dāng)前未知節(jié)點(diǎn)在時(shí)間片t時(shí)所在的位置，用Ot表示錨節(jié)點(diǎn)在時(shí)間t和時(shí)間t-1之間所觀測到的當(dāng)前未知節(jié)點(diǎn)的坐標(biāo)值。公式 p(lt/lt-1)表示當(dāng)前未知節(jié)點(diǎn)的通過在t-1時(shí)間片所在的位置來預(yù)測在時(shí)間t時(shí)所在的位置，公式 p(lt/ot-1)表示當(dāng)前未知節(jié)點(diǎn)的通過在t-1時(shí)間片觀測的位置來預(yù)測在時(shí)間t時(shí)所在的位置。用Lt表示一組樣本位置的集合，即樣本集合中每一個(gè)樣本的位置lt在一起組成了Lt。每一個(gè)時(shí)間片開始第一步，算法都會遞歸地運(yùn)算出樣本集，Lt-1表示時(shí)間t-1時(shí)的位置，那么借助于Ot和lt-1可以計(jì)算出lt來。每個(gè)樣本是從當(dāng)前節(jié)點(diǎn)的第一個(gè)鄰居錨節(jié)點(diǎn)的通信范圍當(dāng)中抽取的，但是對于每個(gè)時(shí)間片中的樣本集Lt，算法最多可能要經(jīng)過2次過濾，即若第一次抽取的樣本經(jīng)過過濾個(gè)數(shù)不足時(shí)，便進(jìn)行第二次樣本抽取過濾。而每個(gè)樣本的過濾則是要經(jīng)過兩次遍歷，第一次遍歷所有的一跳鄰居錨節(jié)點(diǎn)，第二次遍歷所有的二跳鄰居錨節(jié)點(diǎn)。即檢查該樣本是否是在當(dāng)前這個(gè)鄰居錨節(jié)點(diǎn)的通訊范圍之內(nèi)，如果是兩次遍歷所有的鄰居錨節(jié)點(diǎn)通訊范圍內(nèi)都有該樣本節(jié)點(diǎn)，那么這個(gè)樣本節(jié)點(diǎn)是合格的，如果這個(gè)過程中有一個(gè)鄰居錨節(jié)點(diǎn)通訊范圍內(nèi)沒有該樣本節(jié)點(diǎn)，那么這個(gè)樣本節(jié)點(diǎn)不合格。要重新抽取樣本。整個(gè)過程中過濾是MCL定位方法中耗時(shí)較多的部分。

隨后Baggio，A和K.Langendoen提出了一種改進(jìn)的MCB（Monte-Carlo Boxed Location）定位方法[17]，定位精度有了進(jìn)一步的提升，計(jì)算量進(jìn)一步下降，且充分利用了二跳鄰居節(jié)點(diǎn)，但在井下環(huán)境當(dāng)中其過濾方法效果不明顯，且計(jì)算量也不小。MCB定位方法改進(jìn)了MCL抽取樣本的區(qū)域，即是從所有鄰居錨節(jié)點(diǎn)通信重疊區(qū)域當(dāng)中抽取樣本。多加了創(chuàng)建或更新錨盒的部分，錨盒的邊界如下：

式（1）中i是當(dāng)前節(jié)點(diǎn)第i個(gè)一跳鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)的個(gè)數(shù)為m個(gè)，其中m大于等于0。在抽樣階段，MCB在錨盒當(dāng)中抽取樣本。雖然過濾方法和MCL相同，但無效樣本的數(shù)量因?yàn)槌闃訁^(qū)縮小而大為減少，極大地提高了定位方法的速度。雖然MCB定位方法有較大的改進(jìn)，但在井下環(huán)境當(dāng)中，MCB能夠利用井下環(huán)境的特點(diǎn)進(jìn)一步做改進(jìn)。

4 MCL和MCB定位在井下的問題及改進(jìn)算法方法

本文針對于礦井這種特定的環(huán)境條件，結(jié)合以上兩種方法提出蒙特卡洛中心定位算法CMCL，充分利用Monte-Carlo方法精度高且定位方法簡單的優(yōu)勢，去除了在井下定位當(dāng)效果不明顯和沒有效果的部分。

4.1 MCL和MCB定位在井下的問題

在礦井當(dāng)中，安全問題首當(dāng)其沖。為了能減少安全事故，就需要加強(qiáng)人員和設(shè)備的管理。人員及設(shè)備的實(shí)時(shí)定位，為精細(xì)的實(shí)時(shí)管理成為可能。通常的全球定位設(shè)備（Global Positioning System，GPS）成本高，且在礦井里無法使用，無線傳感器網(wǎng)絡(luò)的不斷發(fā)展，又為人員及設(shè)備的實(shí)時(shí)定位提供了技術(shù)支持。

無線傳感器網(wǎng)絡(luò)在煤礦井下的定位是通過在巷道中布放已知自身位置的節(jié)點(diǎn)（錨節(jié)點(diǎn)，anchor node），在人員和設(shè)備上配帶上未知當(dāng)前位置的節(jié)點(diǎn)（未知節(jié)點(diǎn)，unknown node），當(dāng)未知節(jié)點(diǎn)在布有錨節(jié)點(diǎn)的巷道里時(shí)，通過錨節(jié)點(diǎn)的位置來計(jì)算出自身的位置，并將位置數(shù)據(jù)實(shí)時(shí)傳給管理中心從而實(shí)現(xiàn)礦井中人員和設(shè)備的實(shí)時(shí)定位跟蹤。礦井環(huán)境下的無傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題是無線傳感器網(wǎng)絡(luò)在礦井環(huán)境中應(yīng)用需要解決的關(guān)鍵技術(shù)問題，為礦井安全生產(chǎn)提供技術(shù)支持，為無線傳感器網(wǎng)絡(luò)的定位技術(shù)提供理論驗(yàn)證。礦井巷道狹長，一般巷道的寬度遠(yuǎn)遠(yuǎn)小于巷道的長度，巷道的寬度一般為2～10 m，如神華寧煤集團(tuán)石炭井二礦21053工作面回風(fēng)巷道全長692 m，寬度3 m[18]。錨節(jié)點(diǎn)在巷道當(dāng)中均勻部署，固定在礦井巷道的一側(cè)。人員及設(shè)備上可配帶未知節(jié)點(diǎn)，當(dāng)人員或設(shè)備在巷道當(dāng)中移動(dòng)時(shí)，通過對人員（設(shè)備）所攜帶未知節(jié)點(diǎn)的定位，實(shí)現(xiàn)對人員的實(shí)時(shí)定位及跟蹤。傳感器網(wǎng)絡(luò)定位算法與應(yīng)用環(huán)境極為相關(guān)，每種定位算法都有各自的特點(diǎn)和應(yīng)用范圍，沒有哪種算法能夠保證在各種條件下都是最好的[19]，同一種的定位算法在不同應(yīng)用環(huán)境下其定位性能相差可能會很大。因此，需結(jié)合應(yīng)用實(shí)際情況進(jìn)行無線傳感器網(wǎng)絡(luò)定位算法的設(shè)計(jì)。

在礦井環(huán)境條件當(dāng)中，MCL和MCB定位方法計(jì)算量都較大，不利于節(jié)點(diǎn)在井下長期使用，且定位過程相對復(fù)雜?？梢猿浞掷玫V井巷道狹長的特點(diǎn)，將抽樣區(qū)域都建立在一跳鄰居錨節(jié)點(diǎn)的信號重疊區(qū)中，這樣所有樣本都將是合格的樣本，就可以省去耗時(shí)的過濾部分。其中，MCL和MCB未知節(jié)點(diǎn)移動(dòng)模型都是隨機(jī)移動(dòng)模型，節(jié)點(diǎn)可能會向各個(gè)方向移動(dòng)，文獻(xiàn)[20]是根據(jù)節(jié)點(diǎn)前幾個(gè)點(diǎn)的位置預(yù)測節(jié)點(diǎn)的運(yùn)動(dòng)來定位，而礦井巷道只有兩個(gè)方向，節(jié)點(diǎn)只能沿兩個(gè)方向中的一個(gè)方向移動(dòng)，這樣隨機(jī)沿兩個(gè)方向進(jìn)行定位比MCL、MCB和文獻(xiàn)[20]定位方法更簡單。每種基于MCL的定位算法取得節(jié)點(diǎn)位置都需要先抽樣，然后過濾掉樣本坐標(biāo)不在錨節(jié)點(diǎn)信號重疊覆蓋區(qū)的點(diǎn)，再看是否有足夠了的樣本點(diǎn)，如果樣本點(diǎn)不夠則重復(fù)抽樣并擴(kuò)大抽樣區(qū)域，最后再根據(jù)樣本點(diǎn)的權(quán)值算出節(jié)點(diǎn)的位置。這些方法具體到礦井當(dāng)中單個(gè)節(jié)點(diǎn)的計(jì)算量有點(diǎn)大，不利于節(jié)點(diǎn)的長期使用。巷道采樣區(qū)域本身很小，本文省去了對樣本過濾這一步，在實(shí)際應(yīng)用當(dāng)中可能會更有效。

4.2 算法提出

MCB定位算法比MCL定位精度更好時(shí)間更短，得益于MCB限定了采樣區(qū)域，有著比MCL更小的采樣區(qū)，這樣MCB定位算法的采樣和過濾的效率更高，之所以還要過濾采樣點(diǎn)是因?yàn)椴⒉荒芡耆ＷC所有的樣本都能落在信號的重疊區(qū)當(dāng)中。MCB定位方法使用錨盒將它的抽樣效率變得更高，那么能不能進(jìn)一步提高抽樣的效率，讓所抽取的樣本都是合格的樣本，進(jìn)而能夠省去過濾的部分。本文就是本著這樣的思考，結(jié)合井下的壞境條件進(jìn)一步的抽樣區(qū)域縮小，使得在這個(gè)區(qū)域當(dāng)中抽取的樣本都是合格的樣本，就可以完全省去過濾和重復(fù)抽樣，定位的效率會大大提高。本文算法以此為出發(fā)點(diǎn)，作如下分析。

如圖1在礦井當(dāng)中，巷道狹長，巷道寬度為w；A、B兩點(diǎn)為錨節(jié)點(diǎn)，節(jié)點(diǎn)通訊半徑為r，錨節(jié)點(diǎn)相隔d布放在巷道的一側(cè)，d小于2r即任意兩個(gè)錨節(jié)點(diǎn)間通訊半徑有重疊；將錨盒寬度限定為巷道寬度，長度也限定為巷道寬度。當(dāng)節(jié)點(diǎn)在這兩個(gè)錨節(jié)間移動(dòng)，根據(jù)位置不同會在三個(gè)位置上形成錨盒（以當(dāng)前節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)為參照，計(jì)算出這些節(jié)點(diǎn)的中心，以中心坐標(biāo)為原點(diǎn)上下左右各向外加巷道的寬度的一半，形成錨盒的邊界），即在錨節(jié)點(diǎn)附近時(shí)會以錨節(jié)點(diǎn)為中心形成錨盒，在靠近兩個(gè)錨節(jié)點(diǎn)中心點(diǎn)時(shí)會以中心點(diǎn)坐標(biāo)為中心形成一個(gè)錨盒。如果把能形成錨盒的區(qū)域稱為錨盒區(qū)的話，當(dāng)未知節(jié)點(diǎn)位于兩個(gè)錨盒區(qū)的中間時(shí)誤差最大，這個(gè)未知節(jié)點(diǎn)最大可能誤差為d/4+w/2。

例如r=50 m，寬w=5 m，巷道內(nèi)每隔d=25 m布放一個(gè)錨節(jié)點(diǎn)，100 m內(nèi)可以布放4個(gè)錨節(jié)點(diǎn)，未知節(jié)點(diǎn)在這100 m內(nèi)移動(dòng)時(shí)會在七個(gè)位置上形成錨盒，這樣未知節(jié)點(diǎn)的理論最大可能誤差為25/4+5/2=8.75 m，即移動(dòng)節(jié)點(diǎn)的定位精度小于等于8.75 m，在實(shí)際定位中會比這個(gè)小。

誤差公式為：錨節(jié)點(diǎn)的間隔d/4+巷道寬度/2。

錨盒個(gè)數(shù)：（巷道長度/錨節(jié)點(diǎn)的間隔+1）+（巷道長度/錨節(jié)點(diǎn)的間隔+1）/2。

圖1 錨盒個(gè)數(shù)示意圖

通過分析可知，100 m內(nèi)通訊半徑為50 m時(shí)，錨節(jié)點(diǎn)密度為1、2、4時(shí)能形成的錨盒個(gè)數(shù)如表1。

表1 未知節(jié)點(diǎn)100 m內(nèi)所能生成錨盒個(gè)數(shù)

形成錨盒后，在錨盒當(dāng)中進(jìn)行樣本點(diǎn)的抽取，若當(dāng)前鄰居節(jié)點(diǎn)列表為空，則看上次抽樣的樣本點(diǎn)數(shù)是否為零，如果不為零，則以上次估計(jì)位置作為未知節(jié)點(diǎn)的位置；如果上次抽樣的樣本點(diǎn)數(shù)也是零，就說明上次未知節(jié)點(diǎn)通訊范圍內(nèi)也沒有錨節(jié)點(diǎn)，則以區(qū)域的幾何中心作為未知節(jié)點(diǎn)的位置。

鄰居節(jié)點(diǎn)為空的情況只有在錨節(jié)點(diǎn)以相隔100 m布放于巷道一側(cè)時(shí)會產(chǎn)生，即未知節(jié)點(diǎn)在兩錨節(jié)點(diǎn)間的中點(diǎn)且在巷道的另一側(cè)，此時(shí)未知節(jié)點(diǎn)離兩個(gè)錨節(jié)點(diǎn)的距離都會超過50 m的通訊距離而收不到信號。而當(dāng)錨節(jié)點(diǎn)以小于100 m布放時(shí)，未知節(jié)點(diǎn)的鄰居列表中至少會有一個(gè)錨節(jié)點(diǎn)。

相比于MCL和MCB這個(gè)方法對采集好的樣本不進(jìn)行過濾，也就是說只要能生成錨盒，那么這個(gè)未知節(jié)點(diǎn)的坐標(biāo)就能確定下來，進(jìn)而加快了定位的速度，節(jié)省了運(yùn)算量。

未知節(jié)點(diǎn)在移動(dòng)中位置不停地改變，反復(fù)運(yùn)行這個(gè)定位方法便能不停地取得變更的位置?？剂康膮⒄斟^節(jié)點(diǎn)只是這個(gè)未知節(jié)點(diǎn)能夠接受到信號的一跳鄰居錨節(jié)點(diǎn)。

整個(gè)CMCL定位算法流程如下：

預(yù)測階段：

（1）首先，更新鄰居列表，計(jì)算出一跳鄰居列表的中心坐標(biāo)，如果一跳鄰居中有節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離小于四分之一的錨節(jié)點(diǎn)間距，以這個(gè)鄰居節(jié)點(diǎn)的坐標(biāo)為中心坐標(biāo)，以中心坐標(biāo)為原點(diǎn)左右各向外加巷道的寬度的一半，以巷道的寬度為錨盒的寬，形成錨盒的邊界。

（2）從錨盒當(dāng)中抽取出50個(gè)樣本點(diǎn)。

更新階段：

（3）如果當(dāng)前樣本點(diǎn)數(shù)不為零，執(zhí)行（6）；點(diǎn)數(shù)為0則看前次樣本數(shù)是否為0如果是執(zhí)行（4）否則執(zhí)行（5）。

（4）取區(qū)域的幾何中心作為未知節(jié)點(diǎn)的當(dāng)前位置；執(zhí)行（1）。

（5）以上次估計(jì)位置作為未知節(jié)點(diǎn)的當(dāng)前位置；執(zhí)行（1）。

（6）取所有樣本點(diǎn)的幾何中心作為未知節(jié)點(diǎn)的當(dāng)前位置。執(zhí)行（1）。

圖2中A、B和C都是錨節(jié)點(diǎn)，按50 m相隔布放在巷道的一側(cè)，節(jié)點(diǎn)的通訊半徑為50 m，其中，生成錨盒過程如下（如圖2）：

（1）利用當(dāng)前未知節(jié)點(diǎn)的一跳領(lǐng)居錨節(jié)點(diǎn)（指當(dāng)前節(jié)點(diǎn)通訊范圍內(nèi)的錨節(jié)點(diǎn)，圖2中未知節(jié)點(diǎn)的一跳鄰居錨節(jié)點(diǎn)有A和B）計(jì)算出中這些錨節(jié)點(diǎn)的幾何中心。

（2）以幾何中心為中點(diǎn)左右各加巷道寬度的一半，上下以巷道寬度為邊界；幾何中心的坐標(biāo)為（centX，centY）：

式（2）中n為當(dāng)前未知節(jié)點(diǎn)一跳鄰居錨節(jié)點(diǎn)的個(gè)數(shù)，第i個(gè)（i從1到n）錨節(jié)點(diǎn)的x坐標(biāo)是Axi，y坐標(biāo)是Ayi。

式（3）中tunnelwidth是當(dāng)前巷道的寬度。

圖2 錨盒計(jì)算示意圖

圖3 錨節(jié)點(diǎn)按100 m間隔時(shí)對比圖

5 實(shí)驗(yàn)驗(yàn)證

為了對CMCL定位算法的性能進(jìn)行評價(jià)，采用了文獻(xiàn)[16]中開發(fā)的用于基于Monte Carlo方法的傳感器網(wǎng)絡(luò)定位算法仿真工具M(jìn)CL-simulator對CMCL算法進(jìn)行了仿真，并在相同的條件下與MCL和MCB算法的性能進(jìn)行了比較。

實(shí)驗(yàn)?zāi)M礦井環(huán)境，巷道的長度設(shè)為1 000 m，巷道的寬度分別設(shè)為3 m、5 m和10 m。錨節(jié)點(diǎn)固定在巷道的一邊，在巷道中分別相隔10 m、20 m、25 m、40 m、50 m和100 m布設(shè)。未知節(jié)點(diǎn)在巷道中隨機(jī)沿一個(gè)方向移動(dòng)，當(dāng)未知節(jié)點(diǎn)到達(dá)巷道的兩個(gè)端點(diǎn)時(shí)，改變方向向另一個(gè)方向移動(dòng)，移動(dòng)的速度從0/每個(gè)時(shí)間片開始到2倍的通訊半徑/每個(gè)時(shí)間片。每個(gè)節(jié)點(diǎn)的通訊半徑為50 m，MCL、MCB和CMCL的采樣數(shù)都設(shè)定為50個(gè)樣本點(diǎn)。

不同錨節(jié)點(diǎn)密度時(shí)定位精度比較，以巷道為1 000 m長5 m寬，錨節(jié)點(diǎn)間隔分別為100 m、50 m、25 m和10 m，結(jié)果如圖3～6。

圖4 錨節(jié)點(diǎn)按50 m間隔時(shí)對比圖

圖5 錨節(jié)點(diǎn)按25 m間隔時(shí)對比圖

圖6 錨節(jié)點(diǎn)按10 m間隔時(shí)對比圖

圖7 巷道寬度3 m時(shí)對比圖

圖8 巷道寬度5 m時(shí)對比圖

圖9 巷道寬度10 m時(shí)對比圖

圖10 算法運(yùn)行時(shí)間對比圖

從上邊錨節(jié)點(diǎn)間隔分別為100 m、50 m、25 m和10 m時(shí)的對比圖看節(jié)點(diǎn)移動(dòng)速度從0 m到100 m的精度變化，CMCL的定位精度是最好的，可以看到在100 m時(shí)的定位精度大約是在50%左右，50 m時(shí)精度在30%以下，25 m時(shí)精度完全在17%以下，10米在10%以下。

不同巷道寬度條件下定位精度比較，巷道長度固定為1 000 m，巷道寬度分別設(shè)置為3 m、5 m和10 m，錨節(jié)點(diǎn)間隔固定為25 m。

如圖7～9所示，在巷道寬度為3 m、5 m、10 m條件下，精度仍然是CMCL精度最好?？梢钥吹皆诟采w面積遠(yuǎn)遠(yuǎn)大于巷道寬度，隨著巷道寬度的變小，所有的定位方法的定位精度都有所提高精度都在10%左右。

定位時(shí)間比較，比較三種定位算法在巷道長度固定為1 000 m，巷道寬度設(shè)置為5 m，錨節(jié)點(diǎn)間隔固定為25 m，未知節(jié)點(diǎn)數(shù)為10，30，50時(shí)的定位時(shí)間。

從圖10中可以看出，紅色為MCL的定位運(yùn)行時(shí)間，綠色為MCB的定位運(yùn)行時(shí)間，藍(lán)色為CMCL的定位運(yùn)行時(shí)間。從中可以看出，CMCL遠(yuǎn)遠(yuǎn)小于另外兩種定位方法。MCL從一個(gè)一跳鄰居錨節(jié)點(diǎn)的通訊區(qū)域當(dāng)中抽取樣本，每抽取一個(gè)樣本都要用一跳和二跳錨節(jié)點(diǎn)來對這個(gè)樣本進(jìn)行過濾，最差情況下抽取20 000次，并且不能保證取到足夠的樣本，這就使MCL定位較慢。MCB對抽樣的區(qū)域進(jìn)行了縮小，這使得它的抽樣效率更高，它有著MCL同樣的過濾方式，它比MCL快了不少，但是比CMCL還是要慢很多。CMCL抽樣是從固定大小的區(qū)域中抽取樣本，并且抽取的樣本不進(jìn)行過濾，這使得CMCL的抽樣只要運(yùn)行一遍，計(jì)算量遠(yuǎn)遠(yuǎn)小于上兩種定位方法。這樣更簡單，且精度更高，更能適應(yīng)于低功耗的要求。

6 結(jié)論及展望

本文算法實(shí)現(xiàn)步驟簡潔，計(jì)算量少，很適合于移植到傳感器節(jié)點(diǎn)芯片當(dāng)中。從實(shí)驗(yàn)結(jié)果看，本文算法在模擬巷道環(huán)境當(dāng)中較MCL和MCB定位精度高、定位穩(wěn)定、計(jì)算時(shí)間較短、不受未知節(jié)點(diǎn)密度的影響。CMCL定位方法更簡單運(yùn)算量少，且精度更高，更適合于在井下環(huán)境中應(yīng)用。

[1]Girod L，Bychkovskiy V，Elson J，et al.Locating tiny sensors in time and space：a case study[C]//IEEE International Conference on Computer Design：VLSI in Computers and Pocessors，2002：214-219.

[2]Harter A，Hopper A，Steggles P，et al.The anatomy of a contextaware application[C]//MobiCom’99，1999：59-68.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multimodalsensing[C]//IEEE/RSJ InternationalConference on Intelligent Robots and Systems，2001：1312-1320.

[4]Priyantha N B，Miu A K L，Balakrishnan H，et al.The cricket compass for context-aware mobile applications[C]//Mobi-Com’01，2001：1-14.

[5]Niculescu D，Nath B.Ad hoc Positioning System（APS）using AOA[C]//INFOCOM，2003：1734-1743.

[6]Niculescu D，Nath B.Ad hoc Positioning System（APS）[C]// GLOBECOM’01，2001：2926-2931.

[7]Niculescu D，Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems，2003，22：267-280.

[8]Doherty L.Algorithmsforposition and datarecovery in wireless sensornetworks[M].Berkeley，CA：University of California Press，2000.

[9]Doherty L，El Ghaoui L.Convex position estimation in wireless sensor networks[C]//INFOCOM，2001：1655-1663.

[10]Shang Y，Ruml W，Zhang Y，et al.Localization from mere connectivity[C]//MobiHoc’03，2003：201-212.

[11]胡圣波，鄭志平.一種井下RFID定位系統(tǒng)的讀卡器防碰撞算法[J].工礦自動(dòng)化，2006（2）：4-7.

[12]傅智河.基于RFID的礦山井下人員定位系統(tǒng)設(shè)計(jì)[J].龍巖學(xué)院學(xué)報(bào)，2007，25（6）：50-52.

[13]任曉強(qiáng)，賈瑞生.井下RFID定位系統(tǒng)的實(shí)用技術(shù)研究[J].山東輕工業(yè)學(xué)院學(xué)報(bào)，2008，22（3）：84-85.

[14]喬鋼柱，曾建潮.信標(biāo)節(jié)點(diǎn)鏈?zhǔn)讲渴鸬木聼o線傳感器網(wǎng)絡(luò)定位算法[J].煤炭學(xué)報(bào)，2010（7）.

[15]Li M，Liu Y.Underground structure monitoring with wireless sensor networks[C]//IPSN，2007：69-78.

[16]Hu L，Evans D.Localization for mobile sensor networks[C]// Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，2004：45-57.

[17]Baggio A，Langendoen K.Monte Carlo localization for mobile wireless sensor networks[J].Ad Hoc Networks，2008，6（5）：718-733.

[18]奚家米，毛久海，楊更社，等.沿空掘巷合理煤柱寬度綜合分析與確定[J].煤田地質(zhì)與勘探，2008，36（4）：42-45.

[19]Wang F B，Shi L，Ren F Y.Self-localization systems and algorithms for wireless sensor networks[J].Chinese Journal of Software，2005，16（5）：857-868.

[20]汪煬，黃劉生，吳俊敏，等.一種基于Monte Carlo的移動(dòng)傳感網(wǎng)絡(luò)精確定位算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2008，29（9）.

ZHAO Ming,QIAO Gangzhu,JIE Jing

Laboratory of Complex System and Computational Intelligence,Taiyuan University of Science and Technology,Taiyuan 030024,China

For most wireless sensor network applications,position data is one of key information.How to make the positioning algorithm more stable and robust,more accurate,more efficient with the minimum cost is a direction which wireless sensor network localization algorithm to pursue.Applications of wireless sensor network are attached great relevence to application.It takes tunnel environment as the background,designs an improved localization algorithm based on the Monte-Carlo localization（Center Monte-Carlo Location,CMCL）,CMCL method is simple and uses bitty computation.Compared and analyzed the CMCL and Monte-Carlo localization though the experiment of simulation,the result reveals that the CMCL has strong stability and better accuracy.

wireless sensor network;Monte-Carlo;localization algorithm

在無線傳感器網(wǎng)絡(luò)應(yīng)用當(dāng)中，位置數(shù)據(jù)向來是關(guān)鍵信息之一。怎樣用最小的代價(jià)，使得定位算法更加穩(wěn)定健壯、更精確、更高效，是目前無線傳感網(wǎng)定位算法追求的一個(gè)方向。因?yàn)闊o線傳感網(wǎng)絡(luò)有著很強(qiáng)的應(yīng)用相關(guān)性，Monte-Carlo中心定位算法以井下環(huán)境為背景，設(shè)計(jì)的一種基于Monte-Carlo算法的改進(jìn)的定位算法，定位方法簡單，定位計(jì)算量小。最后通過實(shí)驗(yàn)將該算法和Monte-Carlo算法進(jìn)行了仿真，結(jié)果顯示在井下環(huán)境條件下，該算法有很強(qiáng)的穩(wěn)定性和更好的精度。

無線傳感網(wǎng)；Monte-Carlo；定位算法

A

TP393

10.3778/j.issn.1002-8331.1202-0217

ZHAO Ming,QIAO Gangzhu,JIE Jing.Monte-Carlo method based localization algorithm for underground wireless sensor network.Computer Engineering and Applications,2013,49（23）：81-85.

國家自然科學(xué)基金（No.60975074）。

趙明（1979—），男，碩士研究生，主研方向：無線傳感器網(wǎng)絡(luò)；喬鋼柱，副教授；介婧，博士后，副教授。E-mail：zmovocs@gmail.com

2012-02-13

2012-07-25

1002-8331（2013）23-0081-05

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎