一種基于Monte Carlo的移動(dòng)傳感網(wǎng)絡(luò)精確定位算法 汪煬12黃劉生12吳 ...

1、一種基于Monte Carlo的移動(dòng)傳感網(wǎng)絡(luò)精確定位算法 汪煬1,2,黃劉生1,2,吳 .摘要： 汪煬 - 相關(guān)文章關(guān)鍵詞：算法類別：專題技術(shù)來(lái)源：牛檔搜索（Niudown ）本文系牛檔搜索（Niudown ）根據(jù)用戶的指令自動(dòng)搜索的結(jié)果，文中內(nèi)涉及到的資料均來(lái)自互聯(lián)網(wǎng)，用于學(xué)習(xí)交流經(jīng)驗(yàn)，作品其著作權(quán)歸原作者所有。不代表牛檔搜索（Niudown ）贊成本文的內(nèi)容或立場(chǎng)，牛檔搜索（Niudown ）不對(duì)其付相應(yīng)的法律責(zé)任！一種基于Monte Carlo的移動(dòng)傳感網(wǎng)絡(luò)精確定位算法汪煬1,2,黃劉生1,2,吳俊敏1,2,徐宏力1,21 （中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系，安徽，合肥，230027）2 （蘇州

2、市下一代Web服務(wù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，江蘇，蘇州，215123）E-mail: 摘 要：無(wú)線傳感器網(wǎng)絡(luò)作為一種全新的信息獲取和處理技術(shù)，可以在廣泛的應(yīng)用領(lǐng)域內(nèi)實(shí)現(xiàn)復(fù)雜的大規(guī)模監(jiān)測(cè)和追蹤任務(wù)。在傳感器網(wǎng)絡(luò)中，確定事件發(fā)生的位置或獲取消息的節(jié)點(diǎn)位置是傳感器最基本的功能和支撐技術(shù)。本文針對(duì)特定的應(yīng)用場(chǎng)景，設(shè)計(jì)了適用于錨節(jié)點(diǎn)固定，節(jié)點(diǎn)自由移動(dòng)的移動(dòng)傳感器網(wǎng)絡(luò)的基于Monte Carlo方法的精確定位算法，并描述了其節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)和位置選取模型，最后通過(guò)實(shí)驗(yàn)將本算法與以往研究成果中的代表性的移動(dòng)傳感器網(wǎng)絡(luò)定位算法進(jìn)行了模擬比較和分析。關(guān)鍵詞：移動(dòng)傳感器網(wǎng)絡(luò)定位；Mont

3、e Carlo；牛頓插值中圖分類號(hào)：TP 文獻(xiàn)標(biāo)示碼：A 文章編號(hào):1000-1220（2005）02An Accurate Localization Algorithm Based on MCL for Mobile Sensor NetworksWANG yang1,2, HUANG Liusheng1,2, WU Junmin1,2, XU Hongli1,21 （Department of Computer & Technology, University of Science & Technology of China，Anhui，Hefei，230027,China）2 （Suzh

4、ou Key Lab of Next Generation Web Services Computing，Jiangsu，Suzhou，215123,China）Abstract: As a new technology of data-gathering, Wireless sensor networks can be widely used so as to realize massive monitoring and tracking. It is the most basic support function of WSNs to ensure the location of the

5、information. In this paper, an accurate localization algorithm based on MCL for mobile sensor networks is designed for special application scenes, Which include the movement prediction model and the location selection model. Finally, a simulation is processed to compare this algorithm with some othe

6、r typical methods.Key words: Mobile Sensor Networks, Monte Carlo, Newtown interpolation1 引言定位問(wèn)題對(duì)于無(wú)線傳感器而言是非常有意義的，因?yàn)槠渲饕獞?yīng)用于布線和電源供給困難的區(qū)域、人員不能到達(dá)的區(qū)域、移動(dòng)目標(biāo)的跟蹤和一些臨時(shí)場(chǎng)合1。無(wú)線傳感器網(wǎng)絡(luò)要在這些特殊行業(yè)領(lǐng)域展開(kāi)應(yīng)用，首先要實(shí)現(xiàn)的就是節(jié)點(diǎn)自定位。此外，基于定位的路由協(xié)議能夠顯著的減小能耗2,3,4，系統(tǒng)安全性也會(huì)因此而得到提高5,6。現(xiàn)有的對(duì)于無(wú)線傳感器網(wǎng)絡(luò)定位問(wèn)題的研究主要分為基于距離的定位算法和距離無(wú)關(guān)的定位算法7，基于信標(biāo)節(jié)點(diǎn)的定位算法和無(wú)信標(biāo)節(jié)

7、點(diǎn)的定位算法8等，但是他們都被如下的某些問(wèn)題困擾著：依賴于特殊的硬件：基于信號(hào)強(qiáng)弱來(lái)測(cè)量距離的RSSI算法，例如RADAR9系統(tǒng)；基于到達(dá)時(shí)間TOA10算法，到達(dá)時(shí)間差的TDOA11,12算法和基于到達(dá)角度的AOA13算法都需要在無(wú)線傳感器節(jié)點(diǎn)上增加額外的硬件，這對(duì)于節(jié)點(diǎn)來(lái)說(shuō)，既增加成本又增加了節(jié)點(diǎn)的體積。需要明確的網(wǎng)絡(luò)拓?fù)洌捍蟛糠脂F(xiàn)有的算法都需要數(shù)量眾多的信標(biāo)節(jié)點(diǎn)并且被有效的撒布來(lái)覆蓋整個(gè)網(wǎng)絡(luò)。但是在很多無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中，信標(biāo)節(jié)點(diǎn)的預(yù)先撒布都是不可能的。雖然基于跳數(shù)的定位技術(shù)14,15不需要大量的信標(biāo)節(jié)點(diǎn)，但是它們要求節(jié)點(diǎn)的分布是密集統(tǒng)一的。我們著重研究了如何在更加普遍的網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)

8、節(jié)點(diǎn)的自定位。在我們研究的環(huán)境中，信標(biāo)節(jié)點(diǎn)的預(yù)先分布是未知的，信標(biāo)節(jié)點(diǎn)的密度較低，節(jié)點(diǎn)分布是不規(guī)則的并且節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)都是可以自由移動(dòng)的。本人針對(duì)這樣的環(huán)境展開(kāi)了研究，并提出了一種有效的針對(duì)移動(dòng)傳感器網(wǎng)絡(luò)的定位算法，并與以往的研究成果相比，討論了其精確性，最后總結(jié)全文并展望了移動(dòng)傳感器網(wǎng)絡(luò)的精確定位算法的研究工作。2 移動(dòng)傳感器網(wǎng)絡(luò)定位算法研究現(xiàn)狀正如前文中所提到的，無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)方面已有了不少類型的算法出現(xiàn)，他們其中包含了一些典型的具有代表性的算法，例如：Cricket系統(tǒng)、質(zhì)心定位算法、SPA相對(duì)定位算法16、凸規(guī)劃定位算法17,18、DV-Hop定位算法、DV-Distance

9、定位算法、Euclidean定位算法19以及MDS-MAP定位算法20等等，綜合分析以上的定位算法，我們發(fā)現(xiàn)，每種系統(tǒng)和算法都有各自的特點(diǎn)和適用范圍,沒(méi)有哪一種是絕對(duì)最優(yōu)的；但是，上面提及的以往的研究成果中的方法，雖然對(duì)于移動(dòng)傳感器網(wǎng)絡(luò)它們可以不斷的間隔性的獲取節(jié)點(diǎn)的位置信息，但是沒(méi)有一項(xiàng)是特別針對(duì)節(jié)點(diǎn)移動(dòng)或是信標(biāo)節(jié)點(diǎn)移動(dòng)的情形而設(shè)計(jì)的，唯一的考慮到移動(dòng)節(jié)點(diǎn)的情形的是2002年由Bergamo和Mazzini21提出的研究成果，但是他們的研究成果也并不是真正意義上的考慮移動(dòng)節(jié)點(diǎn)的情形。另一方面，在機(jī)器人研究的領(lǐng)域里，移動(dòng)定位的問(wèn)題已經(jīng)有了顯著的成果。機(jī)器人定位問(wèn)題一般假設(shè)地圖已知并且試圖通過(guò)其

10、運(yùn)動(dòng)和收集的數(shù)據(jù)來(lái)確定其位置。如果運(yùn)動(dòng)和測(cè)量模型都可以用高斯密度來(lái)描述并且初始數(shù)據(jù)同樣吻合，那么可以用經(jīng)典的卡爾曼濾波22來(lái)完成定位；相反的，如果模型是多模型的非高斯密度的，則可以使用基于網(wǎng)格的馬爾科夫23,24定位方法。以往的研究中，有使用移動(dòng)機(jī)器人定位的方法通過(guò)測(cè)定信號(hào)強(qiáng)弱值來(lái)改進(jìn)傳感器定位的精確程度的成果25,26。他們這一成果在確定的室內(nèi)環(huán)境中工作的非常出色，但是這一成果需要假設(shè)固定的信標(biāo)節(jié)點(diǎn)的位置且需要一個(gè)學(xué)習(xí)階段，所以此成果在對(duì)于移動(dòng)傳感器網(wǎng)絡(luò)的定位問(wèn)題并不適用。蒙特卡羅定位（MCL）27,28也經(jīng)常用于機(jī)器人定位或移動(dòng)傳感器網(wǎng)絡(luò)應(yīng)用。MCL是與機(jī)器人運(yùn)動(dòng)的概率模型有關(guān)的粒子濾波。

11、它的主要思想是用一組帶權(quán)的采樣值表示先驗(yàn)概率密度。每一個(gè)步驟又分為預(yù)測(cè)階段和更新階段。在預(yù)測(cè)階段，機(jī)器人的運(yùn)動(dòng)使得位置的不確定性增加。在更新階段，新的測(cè)量數(shù)據(jù)被融合及濾波，數(shù)據(jù)得到更新。這個(gè)過(guò)程不斷重復(fù)，機(jī)器人持續(xù)地更新它的位置。在我們的工作中采用了有序的蒙特卡羅方法29來(lái)實(shí)現(xiàn)定位，然后在機(jī)器人定位和無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方面有著非常大的差別。然而，在機(jī)器人定位和傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位之間有著本質(zhì)的不同。首先，機(jī)器人定位是在預(yù)先定義的地圖上定位，而傳感器網(wǎng)絡(luò)是在自由空間或未標(biāo)明的區(qū)域上定位。第二，機(jī)器人對(duì)在預(yù)定義地圖上的運(yùn)動(dòng)有著相對(duì)好的控制和了解。傳感器節(jié)點(diǎn)很少或無(wú)法控制它的運(yùn)動(dòng)，而且對(duì)速度和方向

12、也不了解。第三，機(jī)器人可以從路標(biāo)獲得精確的范圍信息，但傳感器節(jié)點(diǎn)只能知道它是否在通信范圍內(nèi)。傳感器節(jié)點(diǎn)的約束和范圍的精確度決定了移動(dòng)傳感器節(jié)點(diǎn)的定位是比機(jī)器人定位更困難的問(wèn)題。3 基于Monte Carlo方法的精準(zhǔn)定位算法我們?cè)诒竟?jié)提出了一種新的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法，關(guān)注了在更普遍的網(wǎng)絡(luò)環(huán)境下實(shí)施的節(jié)點(diǎn)定位。在這種環(huán)境下，不需要特殊的測(cè)距硬件，錨節(jié)點(diǎn)分布密度較低，普通節(jié)點(diǎn)的分布沒(méi)有規(guī)律，傳感器節(jié)點(diǎn)可以不受控制的自由移動(dòng)。雖然移動(dòng)性令其他定位技術(shù)變得不精確，我們的方法利用了節(jié)點(diǎn)的移動(dòng)性提高了精確度和減少了錨節(jié)點(diǎn)的數(shù)目。這里考慮的是錨節(jié)點(diǎn)靜止，未知節(jié)點(diǎn)移動(dòng)的情況。錨節(jié)點(diǎn)預(yù)先配置在固定位置，或

13、者通過(guò)GPS 確定位置。其他節(jié)點(diǎn)隨機(jī)分布，位置未知。我們假設(shè)時(shí)間分為離散的時(shí)隙。因?yàn)橐粋€(gè)節(jié)點(diǎn)可能離開(kāi)它原來(lái)的位置，它需要在每個(gè)時(shí)隙進(jìn)行重定位。我們更關(guān)心的是獲得一個(gè)節(jié)點(diǎn)可能位置的概率分布。因?yàn)楣?jié)點(diǎn)保持在網(wǎng)絡(luò)中移動(dòng)，前一個(gè)位置信息也變得不精確。且由于節(jié)點(diǎn)與錨節(jié)點(diǎn)之間通訊，以及節(jié)點(diǎn)和錨節(jié)點(diǎn)的計(jì)算都要花費(fèi)一定的時(shí)間，每次確定當(dāng)前時(shí)刻節(jié)點(diǎn)的位置時(shí)，該節(jié)點(diǎn)已經(jīng)在下一個(gè)位置了。我們永遠(yuǎn)無(wú)法通過(guò)傳統(tǒng)定位方法獲得當(dāng)前時(shí)刻節(jié)點(diǎn)的實(shí)際位置。因此盡量準(zhǔn)確地預(yù)測(cè)下一個(gè)或幾個(gè)時(shí)刻節(jié)點(diǎn)的位置就顯得至關(guān)重要。在以往對(duì)Ad hoc網(wǎng)絡(luò)和無(wú)線傳感器網(wǎng)絡(luò)中的研究中，通常的研究模型都是使用隨機(jī)運(yùn)動(dòng)模型。他們認(rèn)為在一段時(shí)間間隔內(nèi)，節(jié)

14、點(diǎn)是以一定的速度朝一定的方向運(yùn)動(dòng)的，而不同的時(shí)間間隔的運(yùn)動(dòng)之間都是相互獨(dú)立的。換而言之，這樣的模型會(huì)生成一些不切實(shí)際的運(yùn)動(dòng)行為，例如急速轉(zhuǎn)彎或者突然停止等。另一些成果利用了改進(jìn)的隨機(jī)運(yùn)動(dòng)模型，例如文獻(xiàn)30就是一種對(duì)隨機(jī)運(yùn)動(dòng)模型的拓展，在這一研究中，節(jié)點(diǎn)在某一時(shí)刻處于某一位置，并在下一時(shí)刻以任意選擇的方向和0到MaxSpeed的區(qū)間內(nèi)均勻分布的速度來(lái)運(yùn)動(dòng)。文獻(xiàn)31中的馬爾科夫過(guò)程模型也是另一種對(duì)隨機(jī)運(yùn)動(dòng)模型的延伸。還有許多其他的研究也都涉及到這方面，但是所有的這些研究都只是試圖生成一個(gè)節(jié)點(diǎn)的運(yùn)動(dòng)的軌跡來(lái)進(jìn)行模擬，沒(méi)有一個(gè)在其中包含了真正的節(jié)點(diǎn)位置預(yù)測(cè)，進(jìn)而預(yù)先估計(jì)無(wú)線傳感網(wǎng)絡(luò)的拓?fù)渥兓?。在本文?/p>

15、算法中，我們利用對(duì)節(jié)點(diǎn)前幾個(gè)點(diǎn)的位置進(jìn)行插值得到大致的運(yùn)動(dòng)軌跡來(lái)預(yù)測(cè)節(jié)點(diǎn)的運(yùn)動(dòng)方向。這樣可以大大地減小節(jié)點(diǎn)可能的范圍和預(yù)測(cè)的工作量；并且因?yàn)榇蟛糠值墓?jié)點(diǎn)跟蹤定位需求都還是連續(xù)近似平滑的運(yùn)動(dòng)，所以定位的精度也有可能大大的提高。3.1 節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè)假設(shè)在一個(gè)二維平面上，有一個(gè)移動(dòng)節(jié)點(diǎn)Nmobile。我們已知該節(jié)點(diǎn)時(shí)刻0，時(shí)刻1，時(shí)刻2時(shí)刻k-1的位置：, ，現(xiàn)在要通過(guò)前k-1個(gè)點(diǎn)的運(yùn)動(dòng)軌跡預(yù)測(cè)該節(jié)點(diǎn)在時(shí)刻k的位置和運(yùn)動(dòng)方向。已知前k個(gè)時(shí)刻的位置，可以利用三維插值的方法預(yù)測(cè)出k時(shí)刻的位置，但考慮節(jié)點(diǎn)的運(yùn)算能力和節(jié)能，可以利用兩次二維牛頓插值來(lái)代替。分別對(duì)前k+1個(gè)時(shí)刻的和做插值(0ik)。我們假設(shè)函

16、數(shù)f(t)在k1個(gè)相異的時(shí)刻上的函數(shù)值分別為：即，那么根據(jù)牛頓插值多項(xiàng)式，我們可以利用前k1個(gè)時(shí)刻的即來(lái)預(yù)測(cè)第k+2個(gè)時(shí)刻的，其公式如下： 公式1 公式2 公式3同樣： 公式4由公式1和公式4 ，我們可以預(yù)測(cè)得到在第K+1時(shí)刻，節(jié)點(diǎn)在x方向和y方向的速度和分別是： 公式5 公式6由插值預(yù)測(cè)得出的節(jié)點(diǎn)在x方向和y方向的運(yùn)動(dòng)速度，我們可以在假設(shè)在t=k的時(shí)刻節(jié)點(diǎn)的位置為原點(diǎn)的前提下得到節(jié)點(diǎn)的運(yùn)動(dòng)方向，用直線方程表述為： 公式7節(jié)點(diǎn)的運(yùn)動(dòng)速度為： 公式8其中在插值點(diǎn)的選取方面，即f(t)在前K+1個(gè)相異時(shí)刻的函數(shù)值，我們應(yīng)該遵循以下的原則：1. 始終維持一個(gè)包括K+1個(gè)樣本點(diǎn)的采樣窗口，用來(lái)對(duì)節(jié)點(diǎn)的

17、運(yùn)動(dòng)軌跡進(jìn)行插值。2. 這K+1個(gè)采樣點(diǎn)可以是節(jié)點(diǎn)前K+1個(gè)時(shí)刻的預(yù)測(cè)位置的修正值。時(shí)間間隔可以任取，而不一定是連續(xù)的時(shí)間間隔。原則上，越靠近當(dāng)前時(shí)刻所取得時(shí)間間隔應(yīng)密集。3. 采用時(shí)間和準(zhǔn)確度兩個(gè)標(biāo)準(zhǔn)對(duì)窗口中的樣本點(diǎn)進(jìn)行維護(hù)。判斷方法如下：l 得到濾波后的修正值之后，比較修正值和插值所得點(diǎn)的位置，如果兩者方向不同（運(yùn)動(dòng)趨勢(shì)偏移較大），則舍棄前K+1個(gè)采樣點(diǎn)，從此刻開(kāi)始插值。l 如果兩者方向一致，距離相差不大（小于一定閾值），則無(wú)需更新采樣窗口。減小計(jì)算量。l 否則，更新采樣窗口。將當(dāng)前時(shí)刻的修正值加入，在窗口中選擇插值點(diǎn)和修正值差別最小的點(diǎn)來(lái)替換。l 每隔一段時(shí)間強(qiáng)制更新一次。3.2 節(jié)點(diǎn)位

18、置預(yù)測(cè)我們?cè)谇拔闹性?jīng)就以往的節(jié)點(diǎn)運(yùn)動(dòng)模型進(jìn)行了詳細(xì)的分析歸類，我們發(fā)現(xiàn)，原有的運(yùn)動(dòng)模型并不能對(duì)現(xiàn)實(shí)應(yīng)用中的絕大部分運(yùn)動(dòng)軌跡實(shí)現(xiàn)很好的擬合。因?yàn)樵诂F(xiàn)實(shí)應(yīng)用環(huán)境中，跟蹤的目標(biāo)或節(jié)點(diǎn)的移動(dòng)軌跡總是相對(duì)平滑的，因?yàn)橥ǔ５倪\(yùn)動(dòng)物體的運(yùn)動(dòng)軌跡都還是比較規(guī)則的。通過(guò)我們對(duì)本文的應(yīng)用背景的礦山井下定位的節(jié)點(diǎn)運(yùn)動(dòng)軌跡進(jìn)行統(tǒng)計(jì)分析，我們可以發(fā)現(xiàn)對(duì)于本文應(yīng)用背景中涉及到的運(yùn)動(dòng)軌跡，所有的運(yùn)動(dòng)都是沿巷道做運(yùn)動(dòng)的，而井下的巷道中95%以上都是平滑的，換而言之，95%的巷道都可以用二次曲線來(lái)描述其形狀，所以95%以上的運(yùn)動(dòng)軌跡都可以用二次曲線來(lái)擬合。所以我們?cè)谶x擇預(yù)測(cè)的節(jié)點(diǎn)位置是可以采取以下的方式：1. 取以為半徑，節(jié)

19、點(diǎn)運(yùn)動(dòng)方向順時(shí)針與逆時(shí)針各展開(kāi)角（045）的一個(gè)扇型；2. 以節(jié)點(diǎn)的運(yùn)動(dòng)方向?yàn)榍芯€，隨機(jī)生成d條二次曲線；3. 在此d條二次曲線上在扇形內(nèi)的線段上任意隨機(jī)選取N個(gè)點(diǎn)做預(yù)測(cè)值；4. 如果濾波后符合要求的點(diǎn)個(gè)數(shù)不夠N?？梢詫⑸刃蔚慕嵌燃颖逗笥?相同方法重新進(jìn)行選點(diǎn)和濾波(隨機(jī)選取的點(diǎn)數(shù)變?yōu)橹夭蓸訑?shù))，直到找到滿足要求的點(diǎn)。所以可以描述滿足上述情況節(jié)點(diǎn)集合為： 公式93.3 濾波算法在預(yù)測(cè)階段我們獲得第k+2時(shí)刻的N個(gè)預(yù)測(cè)值，它們的集合為S,我們對(duì)以后的算法做出如下定義：定義0鄰節(jié)點(diǎn)：在Nmobile通信半徑內(nèi)的未知節(jié)點(diǎn)，稱為Nmobile的鄰節(jié)點(diǎn)定義1內(nèi)錨點(diǎn)(Innor,D)：當(dāng)前時(shí)刻在Nmobi

20、le通訊半徑內(nèi)的錨點(diǎn)，則在當(dāng)前時(shí)刻這些錨點(diǎn)稱為Nmobile內(nèi)錨點(diǎn)定義2鄰錨點(diǎn)(Neighboor,I)：當(dāng)前時(shí)刻在NNmobile的鄰居節(jié)點(diǎn)通訊半徑內(nèi)的錨點(diǎn)，則在當(dāng)前時(shí)刻這些錨點(diǎn)稱為Nmobile的鄰錨點(diǎn)。在k到k+1時(shí)刻N(yùn)mobile接受到以下廣播信息：l 錨點(diǎn)向通訊半徑內(nèi)廣播當(dāng)前時(shí)刻位置坐標(biāo)l 普通節(jié)點(diǎn)向通訊半徑內(nèi)廣播其所偵聽(tīng)到的錨節(jié)點(diǎn)位置將根據(jù)在時(shí)刻k到k+1觀測(cè)到的廣播信息，把Nmobile的在時(shí)刻k到k+1的內(nèi)錨點(diǎn)集合記為IS，鄰錨點(diǎn)集合記為NS，用代表N個(gè)預(yù)測(cè)值中的某一點(diǎn)，很顯然，我們可以總結(jié)Nmobile在時(shí)刻k+1的位置到它的內(nèi)錨點(diǎn)s的距離小于等于R，到鄰錨點(diǎn)的距離大于R小于

21、等于2R，所以我們可以描述下列濾波公式：公式10根據(jù)公式10的濾波公式，濾掉不滿足要求的預(yù)測(cè)值后，保留滿足要求的預(yù)測(cè)值。我們假設(shè)滿足濾波公式的預(yù)測(cè)值的權(quán)值為1，否則為0，設(shè)預(yù)測(cè)值的權(quán)值為，那么我們需要重新預(yù)測(cè)采樣的數(shù)目N為： 公式11根據(jù)上文所述的節(jié)點(diǎn)預(yù)測(cè)采樣規(guī)則，重新采樣的N個(gè)節(jié)點(diǎn)，然后重復(fù)上述過(guò)程直到找到N個(gè)滿足要求的值為止。因?yàn)檎业矫總€(gè)節(jié)點(diǎn)的權(quán)重都是一致的，所以對(duì)找到的N個(gè)節(jié)點(diǎn)進(jìn)行平均，得到Nmobile在時(shí)刻k+1也就是第k+2個(gè)時(shí)刻的預(yù)測(cè)修正值： 公式12 公式134 實(shí)驗(yàn)?zāi)M類似本文的工作包括文獻(xiàn)32中提出的一種基于MCL的定位方法和文獻(xiàn)33中提出的CDL方法，因?yàn)楸疚牟捎玫亩ㄎ环?/p>

22、法和上述兩篇文章中提出的定位算法都是非測(cè)距的定位方法。其中文獻(xiàn)32中提出的方法只是一個(gè)基本的MCL方法，并沒(méi)有針對(duì)真實(shí)應(yīng)用中可能出現(xiàn)的運(yùn)動(dòng)模型進(jìn)行進(jìn)一步分析。我們?cè)谙挛闹袑⒎Q文獻(xiàn)32中提出的方法為“傳統(tǒng)MCL”，稱文獻(xiàn)33中提出的方法為“CDL”，而將本文中提出的算法稱為“精準(zhǔn)MCL”。本文的研究背景是基于煤礦井下的移動(dòng)定位提出的，所以模擬實(shí)驗(yàn)的環(huán)境也應(yīng)該盡量的類似的煤礦井下的井筒的形態(tài)。在此我們利用本文作者的辦公樓中交錯(cuò)的走廊來(lái)模擬井筒，具體的實(shí)驗(yàn)場(chǎng)地見(jiàn)圖1和圖2：圖1 實(shí)驗(yàn)場(chǎng)地示意圖Fig1. Sketch map of experiment filed圖2 實(shí)驗(yàn)場(chǎng)地實(shí)景圖Fig2. Sn

23、apshot of experiment field其中圖中灰色描出的部分為辦公樓的走廊，我們將利用這些部分來(lái)做為我們實(shí)驗(yàn)?zāi)M的場(chǎng)地。圖中所示走廊寬度為3米，長(zhǎng)度分別為38米，19米，4米和8米，總實(shí)驗(yàn)面積為207米2。由于節(jié)點(diǎn)的移動(dòng)即煤礦井下的節(jié)點(diǎn)和人員的移動(dòng)，所以我們?cè)趯?shí)驗(yàn)中采用了多人攜帶傳感器在走廊自由走動(dòng)的方式來(lái)模擬井下節(jié)點(diǎn)的移動(dòng)，也就是說(shuō)節(jié)點(diǎn)的移動(dòng)帶上了人的主觀行為，不會(huì)頻繁的出現(xiàn)突然急停和快速轉(zhuǎn)彎的過(guò)程，我們假設(shè)人員移動(dòng)的最大速度為最小運(yùn)動(dòng)速度為。下面是我們給出的一些實(shí)驗(yàn)相關(guān)參數(shù)的定義：l 錨節(jié)點(diǎn)密度（）：在一跳傳輸半徑內(nèi)的平均錨節(jié)點(diǎn)的個(gè)數(shù)；l 時(shí)間間隔（t）：移動(dòng)定位算法的定位周

24、期；l 節(jié)點(diǎn)密度（）：在一跳傳輸半徑內(nèi)的平均節(jié)點(diǎn)個(gè)數(shù)；l 精度評(píng)價(jià)指標(biāo)：實(shí)際位置與算法結(jié)果位置之間的距離除以通訊半徑R得出的商。由此我們可以得出實(shí)驗(yàn)相關(guān)的參數(shù)如下表：表1 模擬實(shí)驗(yàn)相關(guān)參數(shù)表Table1. Parameters of simulations參數(shù)值范圍區(qū)域面積207m2移動(dòng)節(jié)點(diǎn)速度,節(jié)點(diǎn)傳輸半徑2米MCL相關(guān)算法樣本數(shù)50算法執(zhí)行時(shí)間50t定位時(shí)間間隔t圖3所示的是三種算法在錨節(jié)點(diǎn)密度；以及節(jié)點(diǎn)密度的情況下算法精度評(píng)價(jià)指標(biāo)和算法執(zhí)行時(shí)間之間的關(guān)系，圖中橫坐標(biāo)為算法執(zhí)行的時(shí)間，用時(shí)間片的個(gè)數(shù)來(lái)衡量；圖的縱坐標(biāo)表示算法的定位精度評(píng)價(jià)指標(biāo)。由于兩項(xiàng)和MCL方法相關(guān)的算法能夠利用過(guò)去的位

25、置信息，所以其精度隨著時(shí)間變化有著明顯的變化而CDL方法不能利用過(guò)去的相關(guān)信息，所以時(shí)間變化對(duì)其結(jié)果影響不明顯。所以我們可以發(fā)現(xiàn)，雖然在算法執(zhí)行的早期，CDL算法明顯好于本文提出的算法，但是隨著算法的執(zhí)行，本文的算法由于充分的利用的歷史信息并透徹的分析了節(jié)點(diǎn)的運(yùn)動(dòng)模型，所以本文提出的算法很快的在精度上趕超了CDL算法，而同傳統(tǒng)MCL算法相比較，雖然在算法早期兩者的精度類似，但是當(dāng)算法執(zhí)行到一定程度，由于本文提出的算法在節(jié)點(diǎn)運(yùn)動(dòng)和位置預(yù)測(cè)階段明顯的由于傳統(tǒng)的MCL方法，所以算法在執(zhí)行后期精度提高的非常迅速。圖3 算法精度比較Fig3. Accuracy comparison圖4表示了錨節(jié)點(diǎn)的密度

26、對(duì)參加評(píng)價(jià)比較的三個(gè)算法的定位精度的影響情況，該項(xiàng)實(shí)驗(yàn)在固定且節(jié)點(diǎn)密度的情形下進(jìn)行。我們可以發(fā)現(xiàn)，由于CDL算法是從所有的錨節(jié)點(diǎn)那里收集信息的而基于MCL算法只是收集其通訊半徑內(nèi)和其鄰居通訊半徑內(nèi)錨節(jié)點(diǎn)的信息，所以兩項(xiàng)基于MCL的算法的精度受錨節(jié)點(diǎn)密度的變化影響都較大。圖中的橫坐標(biāo)表示為錨節(jié)點(diǎn)密度的值，縱坐標(biāo)描述了算法精度的衡量指標(biāo)。圖4 錨節(jié)點(diǎn)密度對(duì)算法精度的影響Fig4. Impact of seed density節(jié)點(diǎn)的密度在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中扮演著非常重要的角色，由于在算法的濾波部分中，需要節(jié)點(diǎn)的鄰居節(jié)點(diǎn)提供錨節(jié)點(diǎn)的相關(guān)信息，所以當(dāng)節(jié)點(diǎn)密度越高時(shí)，算法的精度也就同樣會(huì)越高。同時(shí)，

27、由節(jié)點(diǎn)分布不均勻所造成的算法精度差的可能性將隨節(jié)點(diǎn)密度的提高而大大的降低。該實(shí)驗(yàn)是在固定且的情況下進(jìn)行的，我們可以發(fā)現(xiàn)三種算法的精度都會(huì)隨著節(jié)點(diǎn)密度的增加而明顯增加，但是我們可以發(fā)現(xiàn)，在節(jié)點(diǎn)密度相同的情況下，三種算法的優(yōu)劣性總是保持一致，這說(shuō)明雖然節(jié)點(diǎn)密度對(duì)于三種算法的精度來(lái)說(shuō)都有提高的作用，但是節(jié)點(diǎn)密度并不能影響到算法的優(yōu)劣。 圖5 節(jié)點(diǎn)密度對(duì)算法精度的影響Fig5. Impact of node density5 結(jié)論本文綜合分析了無(wú)線傳感器網(wǎng)絡(luò)定位算法和其某些應(yīng)用場(chǎng)景中的運(yùn)動(dòng)模型的定義，給出了一種基于MCL方法的適用于煤礦井下定位等運(yùn)動(dòng)規(guī)模帶有明顯人為特征的精準(zhǔn)的移動(dòng)傳感器網(wǎng)絡(luò)定位算法，

28、利用了牛頓插值分析來(lái)進(jìn)行運(yùn)動(dòng)軌跡的分析預(yù)測(cè)，最后還針對(duì)以往成果中的移動(dòng)傳感器網(wǎng)絡(luò)定位算法，包括一些同樣利用MCL方法來(lái)進(jìn)行定位的算法，展開(kāi)了全面的模擬實(shí)驗(yàn)比較。最終實(shí)驗(yàn)結(jié)果表明，本文提出的方法在某些應(yīng)用場(chǎng)景下，其實(shí)用性要好于以往的算法。6 參考文獻(xiàn)1 Sohrabi K, Gao J, Ailawadhi V, et al. Protocols for Self-organization of a Wireless Sensor Network. IEEE Personal Communications, 2000,7 (5): 16-272 Brad Karp and H. T. Kung.

29、 Greedy Perimeter Stateless Routing. MobiCom 2000.3 Young-Bae Ko and Nitin H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. MobiCom 1998.4 Martin Mauve, Jrg Widmer,et al. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network Magazine. 2001.5 Yih-Chun Hu, Adrian

30、 Perrig ,et al. Packet Leashes: A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. IEEE InfoCom 2003. April 2003.6 Chris Karlof and David Wagner. Secure Routing in Sensor Networks: Attacks and Countermeasures. First IEEE International Workshop on Sensor Network Protocols and Application

31、s, May, 2003.7 He T, Huang C, Blum B M,et al. Range-free localization schemes for large scale sensor networks. In: proc 9th Annual Intl Conf on Mobile Computing and Networking (MobiCom), San Diego, CA., 2003. 81958 Priyantha N B, Balakrishnma H,et al. Anchor-free distributed localization in sensor n

32、etworks. Technical Report MIT-LCS-Tr-892, MIT Lab for computer Science, April 20039 Bahl P, Padmanabhan V N. RADAR: An in-building RF-based user location and tracking system. In: Proc of INFOCOM 2000, Tel Aviv, Israel. 2000, Vol.2：77578410 Griod L, Estrin D. Robust Range Estimation using Acoustic an

33、d Multimodal SensingC.In:Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS01),Maui,Hawaii,USA:IEEE Computer Society,2001;3:1312132011 Priyantha N，Chakraborty A ,et al. The cricket location-support systemACMConference Oil Mobiil Computing and Networking J1MA，2000

34、(6)12 Andreas Savvides, Chih-Chieh Han ,et al. Dynamic Fine-Grained Localization in Ad-Hoc Networks of. Sensors. Networked and Embedded Systems Lab. Department of Electrical Engineering. University of Calfornia, Los Angeles13 Niculescu D,Nath B.Ad Hoc Positioning System (APS)Using AOA,IEEE INFOCOM 2

35、003,San Francisco,CA,USA,2003.14 Radhika Nagpal, Howard Shrobe,et al. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. 2nd International Workshop on Information Processing in Sensor Networks (IPSN). April 2003.15 Dragos Niculescu and Badri Nath. DV Based Posi

36、tioning in Ad hoc Networks. Kluwer Journal of Telecommunication Systems. 2003.16 Capkun S, Hamdi M, et al. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002,5(2):157.167.17 Doherty L, Pister KSJ,et al. Convex position estimation in wireless sensor networks. In: Proc. of the IEE

37、E INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 1655.1663. 18 Doherty L. Algorithms for position and data recovery in wireless sensor networks. Berkeley: University of California, 2000.19 Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001

38、 IEEE Global Telecommunications Conf. Vol.5, San Antonio: IEEE Communications Society, 2001. 2926.2931. 20 Shang Y, Ruml W,et al.Localization from mere connectivity. In: Proc. of the 4th ACM Intl Symp. on Mobile Ad Hoc Networking & Computing. Annapolis: ACM Press, 2003. 201.212. 21 P. Bergamo and G.

39、 Mazzini. Localization in Sensor Networks with Fading and Mobility. IEEE PIMRC. September 2002.22 Peter Maybeck. Stochastic Models. Estimation and Control, Volume 1. Academic Press, New York, 1979.23 Wolfram Burgard, Dieter Fox,et al. Estimating the Absolute Position of a Mobile Robot Using Position

40、 Probability Grids. 14th National Conference on Artificial Intelligence (AAAI). 1996.24 Wolfram Burgard, Andreas Derr,et al. Integrating Global Position Estimation and Position Tracking for Mobile Robots: The Dynamic Markov Localization Approach. IEEE/RSI International Conference on Intelligence Robots and Systems (IROS). 1998.25 Andrew M. Ladd, Kostas E.,et al. Robotics-Based Location