無線傳感器網絡定位算法的研究

摘要：節(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