產(chǎn)品中心 應(yīng)用方案 技術(shù)文摘質(zhì)量保證產(chǎn)品選型 下載中心業(yè)內(nèi)動(dòng)態(tài) 選型幫助 品牌介紹 產(chǎn)品一覽 聯(lián)系我們
- 無(wú)線傳感器網(wǎng)絡(luò)自身定位算法研究
- 來(lái)源:賽斯維傳感器網(wǎng) 發(fā)表于 2012/2/16
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)用要求。若沒有位置信息,傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)幾乎是沒有應(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開發(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ò)。現(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ù)洌嚯x的測(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)可推出:
令:
利用公式(2),(3)可求得:
最后利用公式:
來(lái)判斷所求的結(jié)果是否有效,當(dāng)residue超過(guò)無(wú)線射程時(shí),結(jié)果是無(wú)效的。
在求精階段,節(jié)點(diǎn)測(cè)量得到所有一跳鄰居的距離并依次更新自己的位置。該算法的所有位置計(jì)算都使用最小二乘法。算法引入了置信度來(lái)提高求精階段的性能,置信度被用來(lái)在三邊定位中加權(quán)。當(dāng)未知節(jié)點(diǎn)更新其位置估計(jì)時(shí)同樣也更新其置信度。這樣,網(wǎng)絡(luò)的平均置信度將隨迭代而增加,提高了覆蓋度和精度。
該算法的定位精度比較高,在網(wǎng)絡(luò)連通度較高的情況下能較好地容忍距離誤差。但由于對(duì)網(wǎng)絡(luò)拓?fù)涞囊蕾,需要較長(zhǎng)的覆蓋時(shí)間。
2.1.2 N-hop multilateration算法
在N-hop multilateration算法中,測(cè)距使用的是超聲波測(cè)距技術(shù),該算法也分為3個(gè)階段,第一階段是生成協(xié)作子樹,根據(jù)判定條件,在網(wǎng)絡(luò)中生成多個(gè)由未知節(jié)點(diǎn)和錨節(jié)點(diǎn)組成的限制條件完整或超限制條件的構(gòu)形,稱為協(xié)作子樹。每個(gè)構(gòu)形包括n個(gè)未知變量(未知節(jié)點(diǎn)的坐標(biāo))和至少n個(gè)非線性方程式,并確保每個(gè)未知變量擁有惟一解。未被協(xié)作子樹包含的節(jié)點(diǎn)在整個(gè)算法的后處理階段進(jìn)行定位。
第二階段是對(duì)未知節(jié)點(diǎn)位置的粗略估計(jì),他通過(guò)粗略未知節(jié)點(diǎn)和錨節(jié)點(diǎn)問(wèn)的距離來(lái)估算未知節(jié)點(diǎn)的位置。如圖2所示,未知節(jié)點(diǎn)C在錨節(jié)點(diǎn)A,B所形成的Boundingbox里面,可推算出節(jié)點(diǎn)所在位置的x坐標(biāo)的取值范圍是(|xA-a|,|xB+(b+c)|)。
第三階段采用了循環(huán)求精,根據(jù)預(yù)設(shè)的定位精度,使用卡爾曼濾波技術(shù)在每個(gè)協(xié)作子樹范圍內(nèi)(每個(gè)節(jié)點(diǎn)位置有惟一解)對(duì)第二階段的結(jié)果進(jìn)行循環(huán)求精。
該算法要求錨節(jié)點(diǎn)要求錨節(jié)點(diǎn)要部署在網(wǎng)絡(luò)的邊緣才能達(dá)到較好的效果,而且循環(huán)求精的次數(shù)無(wú)法預(yù)知。
2.1.3 算法分析
對(duì)于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法,定位精度是個(gè)主要的評(píng)估標(biāo)準(zhǔn),上述兩種算法都采用了求精的步驟,仿真結(jié)果顯示定位精度有了比較大的提高,但各自又有不足之處,在測(cè)距階段,Robust positioning算法采用了DV-hop的算法,DV-hop算法是基于距離矢量交換協(xié)議的,在大型網(wǎng)絡(luò)中需要較長(zhǎng)的覆蓋時(shí)間,而N-hop multilateration算法卻采用了硬件測(cè)距的方法,提高了網(wǎng)絡(luò)的成本。
N-hop muItilateration算法可以根據(jù)配置采用集中式和分布式兩種計(jì)算方式,通信開銷基本相當(dāng),他在定位階段,采用了Bounding box的方法,計(jì)算量要比最小二乘法小很多,是非常值得借鑒的思想。而對(duì)N-hop multi-lateration算法,錨節(jié)點(diǎn)的密度和分布對(duì)算法的定位精度有較大的影響,而Robust positioning算法在這方面的影響較小。總體上講,Robust positioning算法要比N-hopmultilateration算法具有更大的優(yōu)勢(shì),今后主要的工作是如何提高該算法的覆蓋速度,來(lái)適應(yīng)大規(guī)模網(wǎng)絡(luò)的需要。
3 結(jié) 語(yǔ)
近些年來(lái),國(guó)內(nèi)外提出了很多關(guān)于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法,每一種算法都有各自的特點(diǎn)。對(duì)于精度比較高的算法,通信開銷和收斂速度等方面的性能可能就會(huì)有所下降,采用硬件測(cè)距可以提高定位精度,但同時(shí)會(huì)增加傳感器節(jié)點(diǎn)的成本。根據(jù)具體業(yè)務(wù)的需要,定位的條件和要求會(huì)有所不同,因此,要針對(duì)具體的應(yīng)用設(shè)計(jì)和采用適合的定位算法。傳感器網(wǎng)絡(luò)定位技術(shù)還有比較大的研究空間,主要集中在傳感器節(jié)點(diǎn)測(cè)距硬件技術(shù)的研究、傳感器網(wǎng)絡(luò)定位算法仿真平臺(tái)的研究與開發(fā)和基于復(fù)雜地理?xiàng)l件下的定位算法研究等方面。
轉(zhuǎn)載請(qǐng)注明來(lái)源:賽斯維傳感器網(wǎng)(www.jsxlzzp.com)
- 如果本文收錄的圖片文字侵犯了您的權(quán)益,請(qǐng)及時(shí)與我們聯(lián)系,我們將在24內(nèi)核實(shí)刪除,謝謝!