水剛

摘要：無(wú)線傳感器網(wǎng)絡(luò)的定位問(wèn)題是組網(wǎng)的重要問(wèn)題，是大多數(shù)應(yīng)用的基礎(chǔ)。首先介紹了節(jié)點(diǎn)定位的相關(guān)概念和定位方法，對(duì)當(dāng)前的定位算法進(jìn)行了分類，接著介紹了幾種典型的節(jié)點(diǎn)定位算法并做了比較分析，最后指出定位算法的應(yīng)用技巧。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；定位算法；節(jié)點(diǎn)定位

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)01-0030-04

Research on Localization Problem in Wireless Sensor Network

SHUI Gang

(71282 PLA Troops，Luoyang 471000,China)

Abstract: In wireless sensor network, Sensor positioning is a crucial issue for operation and management, which is extremly crucial for most of the applications. Firstly，the concepts and methods of node positioning in WSN were introduced.At the same time,the taxonomy for WSN node localization algorithms was mentioned.Secondly,some popular algorithms were introduced.Then,the paper offerd the analy? sis and comparison of popular algorithms.At last,the using method of localization algorithms was put forward.

Key words: wireless sensor network(WSN);localization algorithms; node localization

無(wú)線傳感器網(wǎng)絡(luò)(WSN , Wireless Sensor Network)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量微型傳感器節(jié)點(diǎn)相互協(xié)作構(gòu)成的一個(gè)多跳自組織網(wǎng)絡(luò),其目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被監(jiān)測(cè)對(duì)象的信息,如溫度、濕度、壓力、移動(dòng)物體的速度等,并發(fā)送給觀察者[1]。在醫(yī)療護(hù)理、軍事國(guó)防、工業(yè)控制、智能農(nóng)業(yè)、城市交通、環(huán)境監(jiān)測(cè)、智能家居等領(lǐng)域都有重要科研價(jià)值和廣闊應(yīng)用前景。WSN中節(jié)點(diǎn)的地理位置信息是其應(yīng)用的基礎(chǔ)，用于確定信息來(lái)源的準(zhǔn)確位置，此外，利用節(jié)點(diǎn)位置信息可以設(shè)計(jì)路由算法以提高路由效率等。因此，節(jié)點(diǎn)定位問(wèn)題已成為WSN的一個(gè)重要研究方向。

2傳感器網(wǎng)絡(luò)定位算法分類

2.1無(wú)參考節(jié)點(diǎn)算法和有參考節(jié)點(diǎn)算法

無(wú)參考節(jié)點(diǎn)算法無(wú)預(yù)先位置信息，根據(jù)局部距離值來(lái)定位。已公開的算法有AFL算法和ABC算法；有參考節(jié)點(diǎn)算法依賴于一些位置已知的節(jié)點(diǎn)，需要先定位參考節(jié)點(diǎn)，為減小定位誤差，參考節(jié)點(diǎn)數(shù)目還要盡量多。目前除AFL和ABC兩種無(wú)參考節(jié)點(diǎn)算法外，其余均屬有參考節(jié)點(diǎn)算法，如Terrain算法、Hop Terrain算法、GPS-Free算法[2]等。

2.2集中式算法、增量式算法和分布式算法

集中式計(jì)算是指把所需信息傳送到某一中心節(jié)點(diǎn)，并在那里進(jìn)行節(jié)點(diǎn)定位計(jì)算的方式，典型的集中式算法有凸規(guī)劃、MDS－MAP算法[7]、質(zhì)心定位算法、APIT算法等；增量式算法從3個(gè)或4個(gè)已知坐標(biāo)的中心節(jié)點(diǎn)開始，尋找合適的新節(jié)點(diǎn)，通過(guò)測(cè)距來(lái)迭代求解，再把這些新節(jié)點(diǎn)加入中心節(jié)點(diǎn)組，逐步得到所有節(jié)點(diǎn)的坐標(biāo)，ABC算法、協(xié)作式多邊測(cè)量法和AOA算法屬此類算法[3]；分布式計(jì)算依賴節(jié)點(diǎn)間的信息交換和協(xié)調(diào)，讓節(jié)點(diǎn)自行計(jì)算，除集中式和增量式算法外的其它算法均屬分布式定位算法，比較典型的有Bounding Box、DV－Hop、Robust Position等。

2.5緊密耦合與松散耦合[4]

緊密耦合定位系統(tǒng)是將參考節(jié)點(diǎn)仔細(xì)地部署在固定的位置，并且通過(guò)有線介質(zhì)連接中心控制器。典型的緊密耦合定位系統(tǒng)有AT&T的Active Bat系統(tǒng)和Active Badge、Hiball Tracker等。其特點(diǎn)是適用于室內(nèi)環(huán)境，有較高的精確性和實(shí)時(shí)性，時(shí)間同步和參考節(jié)點(diǎn)間的協(xié)調(diào)問(wèn)題容易解決，但系統(tǒng)的可擴(kuò)展性受到了限制，代價(jià)較大，無(wú)法應(yīng)用于布線工作不可行的室外環(huán)境。

松散型定位系統(tǒng)的節(jié)點(diǎn)采用無(wú)中心控制器的分布式無(wú)線協(xié)調(diào)方式，近年來(lái)提出的許多定位系統(tǒng)和算法，如Cricket和AHLos等都屬于松散耦合型解決方案。其特點(diǎn)是犧牲緊密耦合系統(tǒng)的精確性而獲得部署的靈活性，依賴節(jié)點(diǎn)間的協(xié)調(diào)和信息交換實(shí)現(xiàn)定位。

4幾種典型算法的比較分析

DV-Hop算法需要較少的參考節(jié)點(diǎn)，通信和計(jì)算開銷適中，不要求節(jié)點(diǎn)具備測(cè)距能力，是一個(gè)可擴(kuò)展的算法。對(duì)于各向同性的密集網(wǎng)絡(luò)，可得到合理的平均每跳距離，從而能夠達(dá)到適當(dāng)?shù)亩ㄎ痪?；但?duì)于網(wǎng)絡(luò)拓?fù)洳灰?guī)則的網(wǎng)絡(luò)，定位精度迅速下降。Bounding Box算法是分布式的，也是可擴(kuò)展的，每個(gè)節(jié)點(diǎn)的計(jì)算復(fù)雜度與網(wǎng)絡(luò)的規(guī)模無(wú)關(guān)，算法需要較高的參考節(jié)點(diǎn)密度，否則定位精度和覆蓋度將會(huì)很低，適于節(jié)點(diǎn)計(jì)算能力非常有限的情況。Robust Position算法可達(dá)到較好的精度，節(jié)點(diǎn)主要和其一跳鄰居節(jié)點(diǎn)通信，因而在網(wǎng)絡(luò)連通度較高的情況下可較好地容忍距離誤差，該算法還可擴(kuò)展。但由于迭代的過(guò)程，算法是強(qiáng)計(jì)算的，如果初始位置估計(jì)非常不準(zhǔn)確或誤差是相關(guān)的，算法可能達(dá)不到精確的估計(jì)。由于依賴于網(wǎng)絡(luò)拓?fù)洌撍惴赡苄枰荛L(zhǎng)的覆蓋時(shí)間。Eu? clidean算法與DV-Hop算法不同，依賴于局部幾何拓?fù)?，適用于網(wǎng)絡(luò)拓?fù)洳灰?guī)則的網(wǎng)絡(luò)，由于數(shù)據(jù)包只傳送兩跳，該算法通信開銷較小，此外，算法還具有適當(dāng)?shù)挠?jì)算開銷和定位精度，但算法的覆蓋度受參考節(jié)點(diǎn)密度和局部幾何拓?fù)涞挠绊戄^大。APIT算法的定位精確度高，性能穩(wěn)定，但APIT測(cè)試對(duì)網(wǎng)絡(luò)的連通性提出了較高的要求。另外，雖然節(jié)點(diǎn)密度對(duì)APIT算法影響最小，并且APIT通信量也較小，但它所需參考節(jié)點(diǎn)密度最大。

5結(jié)束語(yǔ)

近年來(lái)WSN定位方法研究取得了豐碩的成果，提出了許多算法和解決辦法。但是，通過(guò)算法比較分析，在特定條件下，一些算法在某些性能指標(biāo)上可能優(yōu)于其他算法，而在其他方面則可能處于劣勢(shì)，實(shí)際應(yīng)用中需根據(jù)對(duì)結(jié)果精確度和能量消耗等方面進(jìn)行綜合考慮，以選擇合適的定位方法。

參考文獻(xiàn)：

[1] Akyildiz I,Su W,Sanakarasubramaniam Y. Wireless Sensor Network :A Survey[J].Computer Networks ,2002 ,38 (4) :393 - 422.

[2]李善倉(cāng),傅鵬,張德運(yùn).無(wú)線傳感器網(wǎng)絡(luò)中的分布式節(jié)點(diǎn)定位方法[J].西安交通大學(xué)學(xué)報(bào),2007(12):418-422.

[3]方紅雨,崔遜學(xué),劉綦.無(wú)線傳感器網(wǎng)絡(luò)的定位問(wèn)題綜述[J].電腦與信息技術(shù),2005(12):4-5.

[4]熊小華,何通能,徐中勝,王槊華,王曉楓.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究綜述[J].機(jī)電工程,2009(2):15.

[5]曹小紅,李穎,豐皇.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)綜述[J].信息技術(shù),2009(7):235.

[6]陳淦.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)研究[J].軟件導(dǎo)報(bào),2009(12):131-132.

[7] Yi Shang , Wheeler Rmnl , Ying Zhang. Localizationfrom mere connectivity[M].Annapolis ,MaryLand ,USA.