無(wú)線傳感器網(wǎng)絡(luò)自身定位算法研究

發(fā)布時(shí)間:2008/5/29 0:00:00 訪問(wèn)次數(shù):338

1 引言

無(wú)線傳感器網(wǎng)絡(luò)(wsns)是由許多傳感器節(jié)點(diǎn)通過(guò)自組織的形式組成的一種特殊的ad-hoc網(wǎng)絡(luò)，每一個(gè)傳感器節(jié)點(diǎn)由數(shù)據(jù)采集模塊、數(shù)據(jù)處理和控制模塊、通信模塊和供電模塊等組成，此外還可能包括與應(yīng)用相關(guān)的其他部分，比如定位系統(tǒng)、動(dòng)力系統(tǒng)等。借助于內(nèi)置多樣的傳感器，可以測(cè)量溫度、濕度、氣壓、化學(xué)等我們感興趣的物理現(xiàn)象。由于無(wú)線傳感器網(wǎng)絡(luò)在軍事、醫(yī)學(xué)、環(huán)境保護(hù)等領(lǐng)域有著非常廣闊的應(yīng)用前景，受到眾多國(guó)家科研機(jī)構(gòu)的重視。

傳感器節(jié)點(diǎn)的自身定位是傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。例如目標(biāo)監(jiān)測(cè)與跟蹤、基于位置信息的路由、智能交通、物流管理等許多應(yīng)用都要求網(wǎng)絡(luò)節(jié)點(diǎn)預(yù)先知道自身的位置，并在通信和協(xié)作過(guò)程中利用位置信息完成應(yīng)用要求。若沒(méi)有位置信息，傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)幾乎是沒(méi)有應(yīng)用價(jià)值的。所以，在無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中，節(jié)點(diǎn)的定位成為關(guān)鍵的問(wèn)題。采用gps(全球定位系統(tǒng))是獲得位置信息的一種方法，應(yīng)用是非常廣泛的。但他不適用于傳感器網(wǎng)絡(luò)，首先，無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目比較多，因此單個(gè)節(jié)點(diǎn)的成本不能太高，為每一個(gè)節(jié)點(diǎn)配備gps的方案太昂貴了；其次，由于傳感器網(wǎng)絡(luò)的布設(shè)特點(diǎn)，能源不易更換，要求網(wǎng)絡(luò)有較長(zhǎng)的生命周期，而gps定位系統(tǒng)對(duì)能源的消耗過(guò)大，同時(shí)還會(huì)增加傳感器節(jié)點(diǎn)的體積，也不適宜；最后，gps不適于在屋內(nèi)、水下和嚴(yán)重信號(hào)阻礙等環(huán)境下的應(yīng)用。因?yàn)閭鞲衅骶W(wǎng)絡(luò)的定位技術(shù)要適應(yīng)傳感器微型化、低成本和低能耗的要求，盡量延長(zhǎng)傳感器網(wǎng)絡(luò)的生命期，只有通過(guò)網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)之間的相互測(cè)距和信息交換，形成一套全網(wǎng)節(jié)點(diǎn)的坐標(biāo)，才是經(jīng)濟(jì)可行的定位方案。

2 現(xiàn)有定位算法研究

最早期的基于無(wú)線網(wǎng)絡(luò)的室內(nèi)定位系統(tǒng)，都采用了額外的硬件和設(shè)備，如at&t cambridge的active bat系統(tǒng)，采用了超聲波測(cè)距技術(shù)，定位的物體攜帶由控制邏輯、無(wú)線收發(fā)器和超聲波換能器組成的稱為bat的設(shè)備，發(fā)出的信號(hào)由安裝在房間天花板上的超聲波接收器接收，所有接收器通過(guò)有線網(wǎng)絡(luò)連接；在微軟的radar系統(tǒng)中，定位目標(biāo)要攜帶具有測(cè)量rf信號(hào)強(qiáng)度的傳感器，還要有基站定期發(fā)送rf信號(hào)，在事先實(shí)現(xiàn)的rf信號(hào)的數(shù)據(jù)庫(kù)中查詢實(shí)現(xiàn)定位；mit開(kāi)發(fā)了最早的松散耦合定位系統(tǒng)cricket，錨節(jié)點(diǎn)(預(yù)先部署位置的節(jié)點(diǎn))隨機(jī)地同時(shí)發(fā)射rf和超聲波信號(hào)，rf信號(hào)中包括該錨節(jié)點(diǎn)的位置，未知節(jié)點(diǎn)接收這些信號(hào)，然后使用tdoa技術(shù)測(cè)量與錨節(jié)點(diǎn)的距離來(lái)實(shí)現(xiàn)定位。

以上系統(tǒng)都需要事先的網(wǎng)絡(luò)部署或數(shù)據(jù)生成工作，無(wú)法適用于ad-hoc網(wǎng)絡(luò)�，F(xiàn)階段研究較多的是不基于測(cè)距(range-free)的定位算法，這樣就無(wú)需增加額外的硬件，還可以減小傳感器節(jié)點(diǎn)的體積。除此之外，較好的算法還要具備以下幾點(diǎn)特性：

(1) 較小的能耗

傳感器節(jié)點(diǎn)所攜帶能源有限和不易更換的特點(diǎn)要求定位算法應(yīng)該是低能耗的。

(2) 較高的定位精度

這是衡量定位算法的一個(gè)重要指標(biāo)，一般以誤差與無(wú)線射程的比值來(lái)計(jì)算，20％表示定位誤差相當(dāng)于節(jié)點(diǎn)無(wú)線射程的20％。

(3) 計(jì)算方式是分布式的

分布式的定位算法，即計(jì)算節(jié)點(diǎn)位置的工作在節(jié)點(diǎn)本地完成，分布式算法可以應(yīng)用于大規(guī)模的傳感器網(wǎng)絡(luò)。

(4) 較低的錨節(jié)點(diǎn)密度

錨節(jié)點(diǎn)定位通常依賴人工部署或gps實(shí)現(xiàn)。大量的人工部署不適合ad-hoc網(wǎng)絡(luò)，而且錨節(jié)點(diǎn)的成本比普通節(jié)點(diǎn)要高兩個(gè)數(shù)量級(jí)。

(5) 較短的覆蓋時(shí)間。

2.1 算法分析

近些年提出很多典型的算法，但都有各自比較明顯的優(yōu)點(diǎn)和缺點(diǎn)。早期提出的質(zhì)心算法和apit算法要求有較高的錨節(jié)點(diǎn)密度，凸規(guī)劃算法和mds-map算法需要集中式的計(jì)算；euclidean算法基于圍繞在錨節(jié)點(diǎn)周圍的節(jié)點(diǎn)的局部幾何拓?fù)�，但距離的測(cè)量較為復(fù)雜。在所有算法中savarese等提出的robust positioning算法和sav-vides等提出的n-hop multilateration算法是典型的求精算法，與其他算法相比，是較為優(yōu)秀的算法。

2.1.1 robust positioning算法

robust positioning算法分為測(cè)距、定位和求精三階段，在測(cè)距階段，算法采用了dv-hop算法的思想，首先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距錨節(jié)點(diǎn)的跳數(shù)(distance in hops)。第二階段，在獲得其他錨節(jié)點(diǎn)位置和相隔跳距后，錨節(jié)點(diǎn)計(jì)算網(wǎng)絡(luò)平均每跳距離，然后將其作為一個(gè)校正值(correction)廣播至網(wǎng)絡(luò)中。當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與錨節(jié)點(diǎn)距離。如圖1所示，錨節(jié)點(diǎn)l2計(jì)算出他的網(wǎng)絡(luò)平均每跳距離為(40+75)／(2+5)=16.4 m。

在定位階段，采用了最小二乘法(lateration)進(jìn)行計(jì)算，當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或3個(gè)以上錨節(jié)點(diǎn)(xi，yi)的距離di時(shí)，根據(jù)以下式子，可推出計(jì)算公式：

由式(1)可推出：