摘要:節(jié)點定位技術是傳感器網絡關鍵技術之一,具有十分重要的地位。在對常用的節(jié)點定位算法進行分析比較的基礎上,總結了現有定位算法存在成本和錨節(jié)點稀疏問題,并提出了利用移動錨節(jié)點來進行優(yōu)化定位的方法,能夠有效節(jié)約錨節(jié)點成本。
關鍵詞:無線傳感網絡;節(jié)點定位;移動錨節(jié)點
無線傳感器網絡具有低功耗、低成本、自組織的能力, 能夠自動進行配置和適應環(huán)境的變化, 具有動態(tài)可重構性等特點,能廣泛應用于軍事領域、精細農業(yè)、環(huán)境監(jiān)測、智能家居、城市交通等方面。無線傳感器網絡節(jié)點定位技術,是無線傳感器網絡應用領域重要的共性支撐技術之一,對其研究具有非常重要的意義,無線網絡的許多應用都與無線傳感節(jié)點位置息息相關。傳感器自身定位算法主要可以分為兩類:基于測距的定位算法與非基于測距的定位算法。相比前者,后者由于具有成本和功耗等方面的優(yōu)勢,而成為業(yè)界研究熱點。
1 節(jié)點定位算法
目前無線傳感網絡的節(jié)點定位算法有許多不同的分類的原則,如:基于有無錨點可以分為有錨點算法和無錨點算法;基于測距方式可以分為距離相關算法和距離無關算法;基于計算方式可以分為集中式算法和分布式算法;基于計算次數可以分為一次計算算法和循環(huán)求精算法。
1.1集中式算法和分布式算法
集中定位是指節(jié)點把定位所需信息傳送到中心節(jié)點,在中心節(jié)點行節(jié)點位置計算;分布式定位通過節(jié)點問的信息交換和信標節(jié)點輔助的定位方式。分布式算法相對于集中式算法具有以下特點:自我組織能力強,不依賴于全局基施;健壯,能夠容忍節(jié)點失效和測距誤差;節(jié)能,只需要較少的計算和通信開銷。因此分布式算法更適用于大規(guī)模的傳感器網絡。
1.2 距離相關算法和距離無關算法
距離相關算法通過測量節(jié)點之間的距離或角度信息,使用三邊測量、三角測量或最大似然估計等定位算法計算節(jié)點位置。而無需測距定位算法則不需要距離和角度信息,算法根據網絡的連通性等信息實現節(jié)點定位[1]。
1.2.1距離相關算法
此類定位算法分為兩步:第一步測距,運用特定的測距技術測量未知節(jié)點與錨節(jié)點之間的距離;第二步計算,當未知節(jié)點獲得的距離信息到達一個閥值時,使用三邊測量法、三角測量法或最大似然估計法計算未知節(jié)點的位置。在距離無關定位算法中,測距的消耗在定位過程中占據了最大的比例,因此研究的重點是測距技術。
典型的測距方法有6種[2]:
(1)接收信號強度法(RSSI),將信號的傳播損耗轉化為距離;
(2)信號傳輸時間法(TOA),將電波的傳輸時間轉化為距離,需要精確的時鐘同步;
(3)信號往返時間差法(RTOF),通過計算往返時間、扣除處理時間的方法將時間轉換為距離;
(4)信號到達時間差法(TDOA)將兩種不同無線信號到達接收節(jié)點的時間差轉化為距離,無需時鐘同步;
(5)信號到達角法(AOA)通過antenna矩陣或多接收機感知發(fā)射節(jié)點信號的到達方向,計算接收節(jié)點和發(fā)射節(jié)點之間的相對方位或角度;
(6)信號到達相位差法(PDOA)利用傳播往返時間粗估計距離,然后利用相位差精確估計距離。
測距精度和功耗成本是一對相互矛盾的性能指標,追求高精度的同時必然帶來高的功耗和硬件成本。當精度要求高時,TODA和PDOA測距方法較優(yōu);當成本和功耗為主要考慮因素時,RSSI測距方法較優(yōu)。距離相關定位方法能夠實現精確定位,但對無線傳感器節(jié)點的硬件、成本和功耗過要求高,而且在測量距離和角度的準確性方面也需要大量的研究。因此未來距離相關定位算法研究趨勢是低成本、高能效、高精度的距離或角度測量技術。
1.2.2 距離無關定位算法
距離無關定位算法不需要使用測距技術,只利用連通情況來估測自己的位置。絕大多數距離無關定位算法采取分布式計算模式,因為其可擴展性好,每個節(jié)點的計算復雜度與網絡的規(guī)模無關,計算簡單而且容易實現,同時計算在節(jié)點進行,通信量小。
質心定位算法[3]:一個普通節(jié)點所有直接連通錨點組成的多邊形的質心作為該節(jié)點的位置。質心算法的原理首先是確定包含未知節(jié)點的區(qū)域,計算這個區(qū)域的質心,并將其作為未知節(jié)點的位置。在這個算法中,信標節(jié)點周期性地向鄰近節(jié)點廣播信標分組。當未知節(jié)點接收到來自不同信標節(jié)點的信標分組數量超過某一個門限值k或接收一定時間后,就確定自身位置為這些信標節(jié)點所組成的多邊形的質心。與未知節(jié)點處于鄰近關系的所有錨節(jié)點,所組成的多邊形區(qū)域的質心,作為未知節(jié)點的位置估計。
APIT算法[4]:與未知節(jié)點處于鄰近關系的三個錨節(jié)點構成一個三角形,以多個這樣的三角形的交疊區(qū)域的質心作為未知節(jié)點的位置。用該算法定位的具體步驟:(1)收集信息:未知節(jié)點收集鄰近信標節(jié)點的信息,如位置、標識號、接收到的信號強度等,鄰居節(jié)點之間交換各自接收到的信標節(jié)點的信息;(2)APIT測試:測試未知節(jié)點是否在不同的信標節(jié)點組合成的三角形內部;(3)計算重疊區(qū)域:統(tǒng)計包含未知節(jié)點的三角形,計算所有三角形的重疊區(qū)域;(4)計算未知節(jié)點位置:計算重疊區(qū)域的質心位置,作為未知節(jié)點的位置。
DV-Hop算法[5]由三個階段組成。第一階段,使用典型的距離矢量交換協(xié)議,使網絡中所有未知節(jié)點獲得距初始錨節(jié)點的跳數;第二階段,在獲得其他錨節(jié)點位置( , )和相隔跳數后,各錨節(jié)點( , )利用所收集的信息按式(1)計算平均跳距:
(1)
式中 是錨節(jié)點 的平均每跳距離, 為節(jié)點 和節(jié)點j之間的跳數;然后將平均每跳距離作為一個校正值廣播至網絡中,校正值采用可控洪泛法在網絡中傳播。第三階段,在二維空間中,一旦一個未知節(jié)點獲得與3個或更多錨節(jié)點的距離后,執(zhí)行三邊測量法或最大似然估計法計算自身的位置。
Amorphous算法與DV-Hop相似也有三個階段,其中第一、第三階段與DV-Hop算法相同,只是在第二階Amorphous定位算法是假設段網絡中節(jié)點的通信半徑相同,平均每跳距離為節(jié)點的通信半徑,未知節(jié)點計算到每個信標節(jié)點的跳段距離,誤差比較大。該算法需要預知網絡平均連通度,而且需要較高的節(jié)點密度。其相應的改進算法改進方向主要是重新計算平均每跳距離,或利用局部跳數的平均值代替總跳數,但是誤差相較DV-Hop算法仍比較大。
2 移動錨節(jié)點的節(jié)點定位算法
從前面的分析可以看出成本和錨節(jié)點稀疏問題是目前定位算法最需要進一步解決的問題。如何以較少的成本獲得較多的錨節(jié)點位置信息,同時處理錨節(jié)點稀疏問題是定位算法的一個重要的課題,有學者提出利用移動錨節(jié)點來進行定位。在這些方案中,一個移動錨節(jié)點在網絡中移動并周期地發(fā)送含有錨節(jié)點位置信息的信標信號,未知節(jié)點接受這些信標信號并通過特定的算法估算自己的位置。其中利用RSSI測距技術進行定位的算法,信標信號中包含錨節(jié)點的位置信息和信號強度。利用TOA測距進行定位的算法,在發(fā)送信標的時候加入了時間信息,需要有較高的時間同步的要求。利用錨節(jié)點的移動性導致的信號到達時間差進行定位的算法。上述的3個方法都是利用的錨節(jié)點的移動性來節(jié)約錨節(jié)點成本,但是對未知節(jié)點的硬件成本和功耗的要求并未減少,因此低成本、高能效、高精度的距離或角度測量技術仍然是研究的重點。
3 結論
對現有常見的無線傳感網絡定位算法進行了對比分析,目前為止,各種定位算法都存在一定的技術缺陷,既便如此,這些已有的算法已經為無線傳感技術的推廣發(fā)展乃至整個人類社會的科技進步做出了不可磨滅的貢獻。相信隨著科學界對無線傳感技術的更加深入、成熟的研究探索,人們一定會開發(fā)出技術更加全面的節(jié)點定位算法,為更多的行業(yè)發(fā)展帶來活力。
項目基金:渭南師范學院研究生項目(11YKZ025)
參考文獻:
[1] 孫利民,李建中,陳渝等.無線傳感器網絡[M].北京:清華大學出版社,2005.
[2] 王福豹,史龍,任豐原.無線傳感網絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16 (5):858-868.
[3] 陳迅,唐紅雨,涂時亮.無線傳感器網絡主動分布節(jié)點定位算法[J].計算機工程與設計, 2008,29(7):1664-1667.
[4] 劉鋒,張翰,楊驥 一種基于加權處理的無線傳感器網絡平均跳距離估計算法[J].電子與信息學報,2008,35(5):1221-1224
[5] 姚忠孝,俞立,董齊芬.基于移動信標的 DV-hop無線傳感網絡定位算法[J].傳感技術學報, 2009,22(10):1504-1507.
作者簡介:陳煒(1984-),女,河南淮陽人,2010年畢業(yè)于中國礦業(yè)大學(北京),碩士,渭南師范學院物理與電氣工程學院助教,研究方向無線傳感器網絡及應用。電話:18700361080,郵箱:cwei62213891@163.com