非測(cè)距移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法.

1、計(jì)算機(jī)科學(xué)2007V01.34N_o .9（專(zhuān)刊）非測(cè)距移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法*）Range FreeLocalizationinMobileWirelessSensorNetworks魏葉華李仁發(fā)陳洪龍（湖南大學(xué)計(jì)算機(jī)與通信學(xué)院長(zhǎng)沙 4 1 0 0 8 2 ）摘要定位在許多無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用中都至關(guān)重要，提出了許多節(jié)點(diǎn)定位算 法，但大部分算法假定網(wǎng)絡(luò)是靜態(tài)的，移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的定位研究相對(duì)較少。 針對(duì)定位節(jié)點(diǎn)和錨節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)的網(wǎng)絡(luò)模型，結(jié)合無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的特點(diǎn)，提出了 一種基于似然的自適應(yīng)采樣蒙特卡羅非測(cè)距定位算法，充分利用節(jié)點(diǎn)移動(dòng)性和多跳 錨節(jié)點(diǎn)信息，減少抽樣次數(shù)，提高采樣效率。仿真

2、結(jié)果表明，提出的算法與其它算 法相比定位精度相當(dāng)，但節(jié)點(diǎn)在不同最大運(yùn)動(dòng)速度下，抽樣次數(shù)相對(duì)平穩(wěn)，同時(shí)抽 樣次數(shù)減少7 0%90%，定位覆蓋率最小提高了 7%，最大提高了11%左 右。關(guān)鍵詞無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，定位，蒙特卡羅，非測(cè)距隨著無(wú)線(xiàn)通信和感器器技術(shù)的發(fā)展，產(chǎn)生了無(wú)線(xiàn)傳感網(wǎng)絡(luò)（wirelesssensornetworks，簡(jiǎn)稱(chēng)WSN），作為一種新興的網(wǎng)絡(luò)技術(shù)，在諸如目標(biāo)跟蹤、入侵檢測(cè)、環(huán)境監(jiān) 控、軍事國(guó)防、災(zāi)難救援、醫(yī)療等許多領(lǐng)域都具有廣泛的應(yīng)用前景，通過(guò)部署大量 傳感器節(jié)點(diǎn)至目標(biāo)區(qū)域，進(jìn)行信息的感知、處理與傳輸，WSN將改變我們與客觀 世界的交互方式1。在WSN的應(yīng)用中，如環(huán)境監(jiān)控、目標(biāo)跟蹤

3、等，節(jié)點(diǎn)位置至關(guān)重要，離開(kāi)位置 信息，感知數(shù)據(jù)是沒(méi)有意義的2,定位技術(shù)是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中關(guān)鍵的基礎(chǔ)支 撐技術(shù)。此外，基于傳感器節(jié)點(diǎn)位置信息的路由協(xié)議可以提高路由效率，節(jié)約能耗3，增強(qiáng)網(wǎng)絡(luò)安全性4及實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞淖耘渲? 1等。而所有網(wǎng)絡(luò)節(jié) 點(diǎn)均安裝GPS接收器或者人工配置節(jié)點(diǎn)位置會(huì)受到成本、效率等問(wèn)題的限制，甚 至在某些場(chǎng)合可能無(wú)法實(shí)現(xiàn)，因此必須采用一定的機(jī)制實(shí)現(xiàn)WSN的自身定位。目前面向不同應(yīng)用，提出了許多測(cè)距、非測(cè)距的定位算法，然而現(xiàn)有算法大多 數(shù)假定節(jié)點(diǎn)靜止的，既靜態(tài)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的定位。對(duì)于錨節(jié)點(diǎn)（已知位置節(jié) 點(diǎn)）、定位節(jié)點(diǎn)（未知位置節(jié)點(diǎn)）均可隨機(jī)移動(dòng)的移動(dòng)WSN定位研究較少L1 6|

4、。由于節(jié)點(diǎn)的移動(dòng)性，增加了節(jié)點(diǎn)定位難度，現(xiàn)有靜態(tài)網(wǎng)絡(luò)的定位算法也無(wú)法 適應(yīng)這一動(dòng)態(tài)需求。本文針對(duì)移動(dòng)WSN，根據(jù)網(wǎng)絡(luò)的連通性，利用多跳錨節(jié)點(diǎn)信 息，提出了基于似然的自適應(yīng)采樣蒙特卡羅非測(cè)距定位算法？使用指數(shù)退避思想對(duì) 不同跳數(shù)的錨節(jié)點(diǎn)集過(guò)濾所得的樣本賦予不同的加權(quán)值，樣本總權(quán)值達(dá)到設(shè)定閾值 停止采樣。仿真表明此算法保持一定定位精度前提下，有效減少了抽樣次數(shù)，從而 可以縮短處理時(shí)間，節(jié)約系統(tǒng)能耗。本文第1節(jié)概括了WSN定位的相關(guān)研究；第2節(jié)闡述蒙特卡羅定位思想；第 3節(jié)提出了改進(jìn)的蒙特卡羅定位算法；第4節(jié)進(jìn)行仿真分析，并與現(xiàn)有算法進(jìn)行比 較；最后總結(jié)和展望。1相關(guān)研究無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位成為了一個(gè)

5、研究熱點(diǎn)問(wèn)題，針對(duì)不同約束，提出了各種定位算法，大體分為基于測(cè)距和非測(cè)距算法兩 類(lèi)。測(cè)距算法7一9 ，定位節(jié)點(diǎn)使用一定的測(cè)距技術(shù)，測(cè)量到錨節(jié)點(diǎn)距離，通 常至少需要三個(gè)測(cè)距信息，利用三邊測(cè)量算法進(jìn)行位置計(jì)算。常用的測(cè)距技術(shù)有信 號(hào)強(qiáng)度（RSSI ）、到達(dá)時(shí)間差（TOA ）等。測(cè)距算法定位精度相對(duì)較高，但 增加了成本和能耗，對(duì)測(cè)距誤差比較敏感，文10提出了減小測(cè)距誤差影響的 優(yōu)化算法。非測(cè)距定位則無(wú)須距離和角度信息，僅根據(jù)網(wǎng)絡(luò)連通性等約束實(shí)現(xiàn)節(jié)點(diǎn)定位 11_13，減少成本，同時(shí)犧牲了定位精度。較為經(jīng)典的算法如Belus u和Heideman n提出的質(zhì)心算法12 根據(jù)接收的錨節(jié)點(diǎn)位置信息進(jìn) 行位置

6、計(jì)算；DV Hop1 1方法基于到錨節(jié)點(diǎn)的跳數(shù)來(lái)計(jì)算距離，進(jìn)行三 邊測(cè)量的位置計(jì)算，文19使用RSSI技術(shù)增加了DVHop定位精度通常非測(cè)距定位需要較多的參考節(jié)點(diǎn)，通信開(kāi)銷(xiāo)也比較大。文14,is中，移動(dòng)的錨節(jié)點(diǎn)周期性廣播自己的當(dāng)前位置，定位節(jié)點(diǎn)接 收到一定錨節(jié)點(diǎn)信息后：進(jìn)行位置估計(jì)。此類(lèi)算法節(jié)約了實(shí)際錨節(jié)點(diǎn)使用數(shù)目，增 加了定位節(jié)點(diǎn)獲取參考信息的概率，如同增加了*）國(guó)家自然科學(xué)基金（N O.60673061 ）:高等學(xué)校博士學(xué)科點(diǎn)專(zhuān) 項(xiàng)科研基金（N O.20060532024）。魏葉華博士生.研究方向?yàn)闊o(wú)線(xiàn) 傳感器網(wǎng)絡(luò).嵌入式計(jì)算：李仁發(fā)教授、博導(dǎo)，研究方向?yàn)闊o(wú)線(xiàn)網(wǎng)絡(luò)、嵌入式計(jì) 算、數(shù)字化試驗(yàn)

7、技術(shù)：陳洪龍博士生.研究方向?yàn)榍度胧街虚g件。虛擬錨節(jié)點(diǎn)，增加了定位精度目前，對(duì)于錨節(jié)點(diǎn)、定位節(jié)點(diǎn)均可移動(dòng)的WSN定位研究相對(duì)較少。由于節(jié)點(diǎn) 的移動(dòng)性，獲取信息容易失效，增加了定位困難，削減了定位精度，提出了新的挑 戰(zhàn)。文E16 通過(guò)對(duì)文17研究，提出了基于序列蒙特卡羅的非測(cè)距WSN 定位算法，網(wǎng)絡(luò)的錨節(jié)點(diǎn)和定位節(jié)點(diǎn)可以無(wú)控制移動(dòng)，取得了較好的定位精度。但 此方法使用固定數(shù)目采樣，采樣周期長(zhǎng)，開(kāi)銷(xiāo)大。為此本文在文1 16,18基 礎(chǔ)之上，提出了基于似然的自適應(yīng)采樣的蒙特卡羅定位算法，仿真表明本文算法在 保證一定定位精度的情況下，減少了抽樣次數(shù)，從而節(jié)約處理時(shí)間，減少了系統(tǒng)能 耗。第2節(jié)給出了蒙特

8、卡羅定位思想的簡(jiǎn)要描述。2蒙特卡羅定位思想對(duì)于動(dòng)態(tài)系統(tǒng)狀態(tài)的遞歸估計(jì)問(wèn)題，貝葉斯濾波給出了一個(gè)概率框架模型，主 要思想就是使用獲取的感知信息遞歸的估計(jì)動(dòng)態(tài)系統(tǒng)狀態(tài)空間的后驗(yàn)概率密度。假 定數(shù)據(jù)由順序的離散時(shí)間索引的觀測(cè)值0。和控制測(cè)量值稅。組成，貝扛時(shí)刻后驗(yàn) 分布即信度Bel （五）表示為2川：Bel（x，） 一聲（五I Ot，Ut 1，Ot 一1，地 一2，00,UO）（1）依據(jù)控制測(cè)量值和觀測(cè)值，遞歸的使用預(yù)測(cè)（公式2）、更新（公式3）兩個(gè) 階段獲取狀態(tài)的后驗(yàn)密度：BeZ (z)? JP(z132f 1， 1)Bel(xf1)dz 一1(3)Bel(xo) 一ap(ooI.22)Be1 一

9、 (zf)其中a是標(biāo)準(zhǔn)化常量，使得在整個(gè)狀態(tài)空間信度之和為1 ,p（x1.27 一，UH）為系統(tǒng)運(yùn)動(dòng)模型，表示輸入控制信息 一后狀態(tài)變化，p（oI z。）為感知模型，表示狀態(tài)五下觀測(cè)到0。的概率。蒙特卡羅定位是基于粒子濾波的一種定位方法，是貝葉斯濾波框架的實(shí)現(xiàn)，粒 子過(guò)濾器與運(yùn)動(dòng)和感知模型的結(jié)合，使用加權(quán)粒子集表示可能位置的后驗(yàn)分布。L。一si = 1，N）表示粒子集，在預(yù)測(cè)階段，使用LH，z 一 1,地 一，對(duì)P（zolz川， 川）進(jìn)行采樣，得到新的粒子集L7。更新階段：根 據(jù)新的觀測(cè)信息0。，使用感知模型對(duì)每個(gè)采樣計(jì)算加權(quán)系數(shù)：謝一P（o。s）,對(duì)加權(quán)粒子集重新采樣得到新集合L。，以此近似

10、表示t時(shí)刻的狀態(tài)的后驗(yàn) 概率分布。3自適應(yīng)采樣蒙特卡羅定位算法此節(jié)首先描述使用的網(wǎng)絡(luò)模型、節(jié)點(diǎn)感知和運(yùn)動(dòng)模型，及相關(guān)假定，接著詳細(xì)描述自適應(yīng)采樣的定位算法。3.1系統(tǒng)模型本文使用的系統(tǒng)模型與相關(guān)的假定：在WSN中，使用全向的、通信半徑為r的理想圓周傳輸模型; 錨節(jié)點(diǎn)、定位節(jié)點(diǎn)遵循Waypointl 91運(yùn)動(dòng)模型，在部署區(qū)域內(nèi) 隨機(jī)運(yùn)動(dòng)，最大運(yùn)動(dòng)速度為Vma,; WSN被構(gòu)建成一個(gè)動(dòng)態(tài)的離散時(shí)間系統(tǒng)，t表示離散時(shí)間，1。表示節(jié)點(diǎn) 在時(shí)間t時(shí)刻的位置分布，0。表示在t一1到t時(shí)刻之間從錨節(jié)點(diǎn)獲取的觀測(cè)信 息； 移動(dòng)模型P（Zo/zH）表示基于上一時(shí)刻位置信息的節(jié)點(diǎn)當(dāng)前位置的預(yù) 測(cè)，感知模型P（oo

11、/z。）表示在節(jié)點(diǎn)位置為Z。時(shí)得到觀測(cè)值0。的似然； L。一 0)then6 .口一口 +Wt7. L。一上吖U(l。，姒；8. endif;9. forj 一l ndo10.m 一 m 7 口 ；/權(quán)值標(biāo)準(zhǔn)化，n為實(shí)際樣本數(shù)1 1.P。： 一 E訕“厶“;/位置估計(jì)圖1自適應(yīng)蒙特卡羅定位算法3.2. 1預(yù)測(cè)階段此過(guò)程是對(duì)上一時(shí)刻的樣本集LH中每個(gè)樣本1H“利用運(yùn)動(dòng)模型聲(z。/o。 ！)進(jìn)行更新。在定位開(kāi)始？粒子集為空，為改善在部署區(qū)域內(nèi)進(jìn)行樣本隨 機(jī)選擇的不精確性？選取一錨節(jié)點(diǎn)作為參考點(diǎn)進(jìn)行初始采樣。其它時(shí)刻中，因已假 定節(jié)點(diǎn)作隨機(jī)運(yùn)動(dòng)，最大運(yùn)動(dòng)速度為 。，則一1時(shí)刻的可能位置川 “在 時(shí)

12、刻時(shí)的可能位置位于以H “為圓心zStv。，為半徑的圓內(nèi).且當(dāng)前可能 位置的概率服從如下均勻分布，其中d(1。，o,)表示兩點(diǎn)的歐幾里德距離，At表示定位時(shí)間間隔：礎(chǔ)/H, LO忑bifd(Z:,Z,l)vAtv otherwise(4)3.2.2過(guò)濾階段過(guò)濾階段！節(jié)點(diǎn)根據(jù)新的觀測(cè)值O。對(duì)上階段預(yù)測(cè)樣本中不可能位置進(jìn)行過(guò)濾。為了改善MCL算法采樣次數(shù)較大，效率不高的不足，并考慮在非理想網(wǎng)絡(luò)環(huán) 境下，可能因障礙物而導(dǎo)致定位節(jié)點(diǎn)與一跳錨節(jié)點(diǎn)無(wú)法直接通信的現(xiàn)象，我們充分 利用多跳錨節(jié)點(diǎn)信息，對(duì)預(yù)測(cè)階段產(chǎn)生的樣本集中的每個(gè)樣本1進(jìn)行過(guò)濾：filter(l) 一VPENi(d(Z，鄉(xiāng))鍬)，1，挖(5)

13、其中N1表示定位節(jié)點(diǎn)的第i跳錨節(jié)點(diǎn)集，1表示跳數(shù)，R為節(jié)點(diǎn)傳輸距離。 以(5)式為過(guò)濾條件進(jìn)行樣本過(guò)濾并計(jì)算相應(yīng)權(quán)值：Wt 一鄉(xiāng)(o/Z?！?，這里借鑒擁塞控制中的二進(jìn)制指數(shù)退避算法思想，當(dāng)滿(mǎn)足第i跳錨節(jié)點(diǎn)過(guò)濾 條件時(shí)W。 “厶1/2卜1,實(shí)際應(yīng)用中最多應(yīng)用四跳錨節(jié)點(diǎn)信息已經(jīng)充足了。跳 數(shù)越大，過(guò)濾得到的樣本表示節(jié)點(diǎn)位置可能性越小，即似然越小，賦予的權(quán)值也越 小，這也是基于似然自適應(yīng)采樣的思想。本質(zhì)上，本文方法是一種松弛加權(quán)采樣的 定位算法。3.2.3位置估計(jì)累計(jì)上步所得權(quán)值，當(dāng)總和a刀為“達(dá)到一個(gè)預(yù)設(shè)閾值丁或者采樣次數(shù)達(dá) 到設(shè)定最大值時(shí)，停止采樣，對(duì)權(quán)值砌。使用(6)式進(jìn)行標(biāo)準(zhǔn)化，使得 BV

14、t一 1。最后使用(7)式估計(jì)節(jié)點(diǎn)可能位置。毗(i): ZUt (1)(6)aP。一口以 1 (7)4仿真實(shí)驗(yàn)在下面的仿真實(shí)驗(yàn)中，使用MCL算法所用模擬器，節(jié)點(diǎn)開(kāi)始隨機(jī)分布在2 5 0mX 2 5 0 m部署區(qū)域內(nèi)，假定定位節(jié)點(diǎn)和錨節(jié)點(diǎn)是半徑為的圓周傳輸模型， r設(shè)為2 5m，所有節(jié)點(diǎn)采用隨機(jī)waypoint移動(dòng)模型191，最大單位 時(shí)間內(nèi)移動(dòng)速度u。設(shè)定為r(25m)，節(jié)點(diǎn)總數(shù)設(shè)為160，錨節(jié)點(diǎn)數(shù)為1 6,并與MCI。算法、USC算法(質(zhì)心算法)12進(jìn)行相關(guān)性能比較，著 重研究加權(quán)閾值與誤差，最大移動(dòng)速度與抽樣次數(shù)、定位誤差關(guān)系，分析定位節(jié)點(diǎn) 覆蓋等。4.1樣本數(shù)/N權(quán)閾值為了研究樣本數(shù)或加

15、權(quán)閾值對(duì)定位誤差的影響？對(duì)MCI。和AM(:I .算 法在Vma0 一0.4r和u。一0.8r兩種情況下分別仿真實(shí)驗(yàn)，考慮無(wú)線(xiàn) 傳感器節(jié)點(diǎn)的計(jì)算能力和能耗約束，這里抽樣最大迭代次數(shù)設(shè)為5 0次，因此與文】6中結(jié)果相比誤差相對(duì)偏大。由圖2可知，AM CI.算法和MCI。算法在兩種速度下閾值與誤差的關(guān)系差別不明顯。因?yàn)閮煞N法樣本中部分由一跳錨節(jié)點(diǎn)過(guò)濾得到樣本是相同的，其它樣本MCI。算法使 用松弛重采樣獲取，AMCI，使用多跳錨節(jié)點(diǎn)信息過(guò)濾獲取，并且加權(quán)值較小， 因此定位精度相近。當(dāng)樣本數(shù)/閾值為2、3、5時(shí)，參考節(jié)點(diǎn)數(shù)目較少，定位誤 差較大，隨著閾值增大誤差下降顯著，當(dāng)達(dá)到3 0已經(jīng)相對(duì)穩(wěn)定。為

16、此以下實(shí)驗(yàn)選 擇40作為閾值較有代表性。圖2樣本數(shù)/加權(quán)閾值與誤差關(guān)系4.2誤差與抽樣次數(shù)本節(jié)對(duì)最大運(yùn)動(dòng)速度、算法性能與定位精度之間關(guān)系進(jìn)行仿真分析。這里不考 慮節(jié)點(diǎn)間通信開(kāi)銷(xiāo)，使用抽樣次數(shù)表示定位處理所需時(shí)間。抽樣次數(shù)越多，耗時(shí)越 大，算法性能越差。反之，算法性能越好。選擇6 4個(gè)隨機(jī)運(yùn)動(dòng)的定位節(jié)點(diǎn)，執(zhí)行 5 0步定位，迭代1O次，統(tǒng)計(jì)平均誤差和平均抽樣次數(shù)，并分析它們之間關(guān)系。圖3表示了 USC、MCL和AMCI。算法在 o。從0 .2r增加到2r 時(shí)對(duì)誤差的影響。MCL、AMCI。定位精度明顯優(yōu)于USC算法，同樣MCL 與AMCL定位精度差別不明顯。表1是與圖3同一實(shí)驗(yàn)下的各算法在不同最

17、大速 度下平均抽樣次數(shù)統(tǒng)計(jì)。為了更加直觀比較，給出了其曲線(xiàn)圖，見(jiàn)圖4。由圖可知MCI .算法的抽樣次數(shù)對(duì)勘。變化比較敏感，。值從0 .2r增加到2r時(shí)，MCI，平均抽樣次數(shù)從2 5 0左右增加到了77 0左右j而AMCI。算法的抽樣次數(shù)相對(duì)平穩(wěn)，75次左右，減少了7 0%9 0%。圖5對(duì)7dma。一0.4r和0 .8r兩種情況下迭代中的每步運(yùn)算的抽樣 次數(shù)進(jìn)行統(tǒng)計(jì)（前2 0步作為穩(wěn)定步數(shù)），同樣可以觀察到，AMCI，算法對(duì) 。變化的穩(wěn)定性。因?yàn)樵诳凇Ｖ翟黾訒r(shí)，節(jié)點(diǎn)單位時(shí)間內(nèi)移動(dòng)距離增大，也增加了獲 取錨節(jié)點(diǎn)信，皂、的可能性？ MCI。算法中使用負(fù)信息進(jìn)行過(guò)濾，新樣本失效的 概?7 5?率大，進(jìn)

18、行重新采樣的次數(shù)增加，而AMCI。算法使用多跳錨節(jié)點(diǎn)信息，使 用松弛的加權(quán)采樣算法，增加了新樣本的有效性，從而減少了抽樣次數(shù)。由此可以 得出，與MCI。算法相比，本文算法在保持一定定位精度的同時(shí)，有效的減少了 抽樣次數(shù)，提高了采樣效率，減少了定位處理時(shí)間，提高了算法的性能。圖3 %。與誤差關(guān)系表1不同v。，下平均抽樣次數(shù)市00. 511.52MaxSpeed(rdistancepertimeunit)，與抽樣次數(shù)關(guān)系4.3定位節(jié)點(diǎn)覆蓋表2給出了對(duì)三種算法在不同。值下平均未定位節(jié)點(diǎn)數(shù)目統(tǒng)計(jì)？這里未定位節(jié)點(diǎn)是指定位最大抽樣次數(shù)結(jié)束，樣本集合仍 然為空的節(jié)點(diǎn)。把能夠定位的節(jié)點(diǎn)占總定位節(jié)點(diǎn)的比率稱(chēng)為覆

19、蓋率。實(shí)驗(yàn)?7 6?中選擇的定位節(jié)點(diǎn)為6 4,在每個(gè)u。值下運(yùn)行50步，迭代10次，表2 給出了平均未定位節(jié)點(diǎn)數(shù)，由表2可計(jì)算出，MCI 算法的定位平均覆蓋率在8 8%92%，由于AMCI。使用了多跳錨節(jié)點(diǎn)信息，有效減少了未定位節(jié)點(diǎn) 數(shù)，與USC相近，平均覆蓋率幾乎達(dá)到了 9 9%，并且。增加，獲取錨節(jié)點(diǎn)信息的概率增加，USC與AMCI。未定位節(jié)點(diǎn)都相應(yīng)有所減少。魯苗高三2巖E3呂go之圖5每步平均抽樣次數(shù)比較表2不同v。下平均未定位節(jié)點(diǎn)數(shù)結(jié)論與展望針對(duì)移動(dòng)WSN，本文在MCI。算法的基礎(chǔ)之上，提出了一種基于似然的蒙特卡羅非測(cè)距定位算法，充分利用節(jié) 點(diǎn)移動(dòng)性和多跳錨節(jié)點(diǎn)信息，使用不同跳數(shù)錨節(jié)點(diǎn)

20、信息得到的樣本賦予不同加權(quán) 值，設(shè)定一個(gè)閾值，在迭代處理過(guò)程中自適應(yīng)調(diào)節(jié)采樣尺寸，減少計(jì)算復(fù)雜度。通 過(guò)仿真分析，此算法保持一定精度的情況下，有效減少了抽樣次數(shù)，提高了采樣效 率，縮減了處理時(shí)間，間接縮減了網(wǎng)絡(luò)能耗，延長(zhǎng)整個(gè)網(wǎng)絡(luò)壽命。然而移動(dòng)WSN 由于其獨(dú)特的特點(diǎn)，精確有效的定位仍然面臨巨大的挑戰(zhàn)，怎樣有效的利用移動(dòng)信 息，增加定位精度，是我們下一步工作研究的重點(diǎn)。參考文獻(xiàn)1AkyildizIF.elal.WirelessSensorNelworks:asurveyJComputerNetworks.2002.38 (4):393 422（下轉(zhuǎn)第8 4頁(yè)）O0 0 0xxc加IoJaDE3z

21、算法。分析原因：在信標(biāo)節(jié)點(diǎn)密度很低時(shí)，DV Hop算法中一些節(jié)點(diǎn)由于 不能獲得至少三個(gè)信標(biāo)節(jié)點(diǎn)信息，從而不能用三邊測(cè)量方法計(jì)算出其位置。而CE SI.算法由于采用了兩點(diǎn)定位法及正負(fù)約束限制方法，使節(jié)點(diǎn)能在少于三個(gè)信標(biāo) 節(jié)點(diǎn)情況下進(jìn)行定位，從而提高了定位覆蓋率。總結(jié)針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位技術(shù)的特點(diǎn)，本文提出了一種基于簇的傳感器網(wǎng)絡(luò)定位算法一CESL定位算法。該算法的 主要特點(diǎn)在于：（1）基于簇的分層機(jī)制，將網(wǎng)絡(luò)中可以定位的節(jié)點(diǎn)以最大精度定 位出來(lái)；（2）不可定位節(jié)點(diǎn)的識(shí)別與處理，本文引入了兩點(diǎn)定位法及正負(fù)約束限 制定位，在信標(biāo)節(jié)點(diǎn)密度很低時(shí)，通過(guò)對(duì)一些本質(zhì)上不能定位節(jié)點(diǎn)進(jìn)行定位，進(jìn)而提高網(wǎng)絡(luò)的定

22、 位覆蓋率；（3）當(dāng)網(wǎng)絡(luò)中少數(shù)節(jié)點(diǎn)位置改變時(shí)，待定位節(jié)點(diǎn)只需發(fā)送請(qǐng)求定位申請(qǐng)，即可根據(jù)其鄰居節(jié) 點(diǎn)信息重新定位，以降低網(wǎng)絡(luò)能耗。仿真實(shí)驗(yàn)結(jié)果同樣表明，CESI。算法具有良好的定位精度及定位覆蓋率，在大規(guī)模無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中具有較好的應(yīng)用前景1234567參考文獻(xiàn)孫利民李建中，陳渝，朱紅松無(wú)線(xiàn)傳感器網(wǎng)絡(luò)清華大學(xué)出版社，2005Bu1usun,etal.Density adaptive beaconplacementalgorithmsfor localizationinAdhocwireless networks.IEEEInfocom 2002,NewYork:USA,2002Nico

23、lescuD,NathB.AdHocpositioningsystems(APS).In:Proc.ofthe2 0 0 1IEEEGlobalTelecorrmmnicationsConf.VOl.5.SanAntonio:IEEECommunicationsSoc iety,2001.2926 2931MeguerdichianSoSlijepcevicS,Ka rayanV,Potkonjak 眥Lo calizedalgorithm sinwirelessad hocnetworks:Locationdi scov cryandsensorexposure.In:Proc.ofthe2

24、ndACMInt Symp.onMobileAdHoeNetworking 敬Compu ting.LongBeach:ACMPress,2001.106 116 FallettiE.PrestiI.L,SelloneF.SAMIoOSTsmartantennas basedmovablelocalizationsystemVehi cularTechnology,IEEETransactionson.2006,55 (l):25 42馬祖長(zhǎng)，孫怡寧無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法計(jì)算機(jī)工程，2004,30 (7):13 14LangendoenKoReijersN.INstributedlO c

25、alizationinwirelesssensornetworks:a quantitativecomparison.ComputerNetw orks,2003,43:49 9518(上接第7 6頁(yè))2RabacyJJ,AmmerMJ,daSilvaJr.JL,PatelD,RoundyS.Pi corodiosupportsadhocultralowpowerwirelessnetworkingJ.Computer,2000,33 (7):42 48CapkunS,HamdiM,HubauxJp.GPS Freep ositioninginmobileadhocnetworksJ.Clus

26、terComputing,2002, 5(2):157 16 74KarlofCoWagnernSecureRoutinginSensorNetworks:At tacksandCountermeasuresC.In:FirstIEEEInt emationalWorkshoponSensorNetworkProtocolsandApplications,An chorage,Alaska,May2 0 0 35CerpaA,EstrinD.AscentzAdaptiveself configuringsensornet worktopologiesJ.ACMSIGCOMMComputerCo

27、mmunicationReview,2002,32 (l):62 626王福豹，史龍，任豐原.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法J.軟件學(xué)報(bào)，2005,16 (5):857 8687PengR,SichitiuMLRobustprobabilisticcon straint basedlo calizationforwirelesss ensonetworksC.In:SecondAnnualIEEECommunicationsSocietyConference onSensorandAdHol20CommunicationsandNetworks(SECON5),SantaClara,CA

28、,USA,Sept.2OO58NiculescuD,NathB.AdHoepositioningsystem(APS)usingAOAA.ProceedingsofIEEEINFOCOMc.Piscataway,USA:IEEE.2003.1734 1743陳維克，李文鋒等基于RSSI的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法J 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與程版)，2 0 0 6,0 2 ( 3 0 ):2 6 5 2 6 8lOEversL.Dulman S.HavingaP.Adistributed precision basedlO calizationalgorithmforad hocnetw

29、orksC.In:PervasiveCom puting:SecondInternationalConferen ce(PERVASIVE2094).ViennaAustria.April2 0 0 4llNiculescuD.NathB.DVbasedpositioninginadhocnetworksJl.JournalofTelecommunicationSystems,2003,224 (l):2672 8 012EulusuN,HeidernannJ,EstrinD.GP孓less10weostoutdoor10 calizationforverysmalldevicesJ.IEEEWirelessCommunications,2000,7:28 3413HuangQ,selvakennedyS.ARangeFreeLocalizationAlgorithmforWirelessSensorNetworksC.In:Proc.of63rdIEEEVe hicularTechnology Conf