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

趙 明，喬鋼柱，介 婧

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

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

趙 明，喬鋼柱，介 婧

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

1 意義

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）成本低廉、布放簡單，被廣泛應(yīng)用于軍事、醫(yī)療、環(huán)境監(jiān)測、物流運送、空間探測等多個領(lǐng)域。在大多數(shù)的無線傳感器網(wǎng)絡(luò)應(yīng)用中，傳感器網(wǎng)絡(luò)節(jié)點的位置信息是不可或缺的，缺乏了位置數(shù)據(jù)，傳感器網(wǎng)絡(luò)采集到的數(shù)據(jù)將失去意義。傳感器網(wǎng)絡(luò)節(jié)點自身定位技術(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定位方法是用后驗概率模型來進(jìn)行定位的一種方法，有較好的定位精度，有很好的健壯性，且能充分利用巷道空間狹窄的環(huán)境特點來做進(jìn)一步的改進(jìn)。

2 背景

無線傳感網(wǎng)絡(luò)定位按是否基于測距分為基于測距的定位算法和無須測距的定位算法。基于測距的定位通過測量節(jié)點到節(jié)點間的距離、角度信息，然后利用三邊測距、三角測距或最大似然估計的方法進(jìn)行節(jié)點自身定位。典型的基于測距的定位算法有RSSI[1]，TOA[2]，TDOA[3]，AOA[4-5]等。這些算法大部分都需要增加額外的硬件設(shè)備，增加了節(jié)點的成本，同時又增加了節(jié)點的能耗。基于測距技術(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)的定位原理實現(xiàn)過程，文獻(xiàn)[13]介紹了RFID井下人員定位在應(yīng)用上的幾個關(guān)鍵問題，并給出了適當(dāng)?shù)慕鉀Q方法。一類是通過傳感器節(jié)點來實現(xiàn)定位，如文獻(xiàn)[14]介紹了信標(biāo)節(jié)點鏈?zhǔn)讲渴鸬木聼o線傳感器網(wǎng)絡(luò)定位算法，文獻(xiàn)[15]介紹了井下無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)自適應(yīng)的系統(tǒng)。一般來講RFID定位時都是在區(qū)域入口或關(guān)鍵通道設(shè)置讀卡器，來記錄相關(guān)人員進(jìn)出記錄，實時性及精度上不如傳感器節(jié)點。而井下，人員的位置都是在劫態(tài)變化的，因此井下無線傳感器網(wǎng)絡(luò)需要能夠進(jìn)行移動定位。

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

3 MCL和MCB定位原理及過程

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

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

式（1）中i是當(dāng)前節(jié)點第i個一跳鄰居節(jié)點，鄰居節(jié)點的個數(shù)為m個，其中m大于等于0。在抽樣階段，MCB在錨盒當(dāng)中抽取樣本。雖然過濾方法和MCL相同，但無效樣本的數(shù)量因為抽樣區(qū)縮小而大為減少，極大地提高了定位方法的速度。雖然MCB定位方法有較大的改進(jìn)，但在井下環(huán)境當(dāng)中，MCB能夠利用井下環(huá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è)備的實時定位，為精細(xì)的實時管理成為可能。通常的全球定位設(shè)備（Global Positioning System，GPS）成本高，且在礦井里無法使用，無線傳感器網(wǎng)絡(luò)的不斷發(fā)展，又為人員及設(shè)備的實時定位提供了技術(shù)支持。

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

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

4.2 算法提出

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

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

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

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

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

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

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

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

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

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

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

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

整個CMCL定位算法流程如下：

預(yù)測階段：

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

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

更新階段：

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

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

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

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

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

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

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

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

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

圖2 錨盒計算示意圖

圖3 錨節(jié)點按100 m間隔時對比圖

5 實驗驗證

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

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

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

圖4 錨節(jié)點按50 m間隔時對比圖

圖5 錨節(jié)點按25 m間隔時對比圖

圖6 錨節(jié)點按10 m間隔時對比圖

圖7 巷道寬度3 m時對比圖

圖8 巷道寬度5 m時對比圖

圖9 巷道寬度10 m時對比圖

圖10 算法運行時間對比圖

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

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

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

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

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

6 結(jié)論及展望

本文算法實現(xiàn)步驟簡潔，計算量少，很適合于移植到傳感器節(jié)點芯片當(dāng)中。從實驗結(jié)果看，本文算法在模擬巷道環(huán)境當(dāng)中較MCL和MCB定位精度高、定位穩(wěn)定、計算時間較短、不受未知節(jié)點密度的影響。CMCL定位方法更簡單運算量少，且精度更高，更適合于在井下環(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].工礦自動化，2006（2）：4-7.

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

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

[14]喬鋼柱，曾建潮.信標(biāo)節(jié)點鏈?zhǔn)讲渴鸬木聼o線傳感器網(wǎng)絡(luò)定位算法[J].煤炭學(xué)報，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的移動傳感網(wǎng)絡(luò)精確定位算法[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)鍵信息之一。怎樣用最小的代價，使得定位算法更加穩(wěn)定健壯、更精確、更高效，是目前無線傳感網(wǎng)定位算法追求的一個方向。因為無線傳感網(wǎng)絡(luò)有著很強(qiáng)的應(yīng)用相關(guān)性，Monte-Carlo中心定位算法以井下環(huán)境為背景，設(shè)計的一種基于Monte-Carlo算法的改進(jì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í)◎