水剛

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

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

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

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

2.1無參考節(jié)點算法和有參考節(jié)點算法

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

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

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

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

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

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

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

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

5結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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