摘要：節(jié)點定位技術(shù)是傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)之一，具有十分重要的地位。在對常用的節(jié)點定位算法進行分析比較的基礎(chǔ)上，總結(jié)了現(xiàn)有定位算法存在成本和錨節(jié)點稀疏問題，并提出了利用移動錨節(jié)點來進行優(yōu)化定位的方法，能夠有效節(jié)約錨節(jié)點成本。

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

無線傳感器網(wǎng)絡(luò)具有低功耗、低成本、自組織的能力， 能夠自動進行配置和適應(yīng)環(huán)境的變化， 具有動態(tài)可重構(gòu)性等特點，能廣泛應(yīng)用于軍事領(lǐng)域、精細農(nóng)業(yè)、環(huán)境監(jiān)測、智能家居、城市交通等方面。無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)，是無線傳感器網(wǎng)絡(luò)應(yīng)用領(lǐng)域重要的共性支撐技術(shù)之一，對其研究具有非常重要的意義，無線網(wǎng)絡(luò)的許多應(yīng)用都與無線傳感節(jié)點位置息息相關(guān)。傳感器自身定位算法主要可以分為兩類：基于測距的定位算法與非基于測距的定位算法。相比前者，后者由于具有成本和功耗等方面的優(yōu)勢，而成為業(yè)界研究熱點。

1 節(jié)點定位算法

目前無線傳感網(wǎng)絡(luò)的節(jié)點定位算法有許多不同的分類的原則，如：基于有無錨點可以分為有錨點算法和無錨點算法；基于測距方式可以分為距離相關(guān)算法和距離無關(guān)算法；基于計算方式可以分為集中式算法和分布式算法；基于計算次數(shù)可以分為一次計算算法和循環(huán)求精算法。

1.1集中式算法和分布式算法

集中定位是指節(jié)點把定位所需信息傳送到中心節(jié)點，在中心節(jié)點行節(jié)點位置計算；分布式定位通過節(jié)點問的信息交換和信標節(jié)點輔助的定位方式。分布式算法相對于集中式算法具有以下特點：自我組織能力強，不依賴于全局基施；健壯，能夠容忍節(jié)點失效和測距誤差；節(jié)能，只需要較少的計算和通信開銷。因此分布式算法更適用于大規(guī)模的傳感器網(wǎng)絡(luò)。

1.2 距離相關(guān)算法和距離無關(guān)算法

距離相關(guān)算法通過測量節(jié)點之間的距離或角度信息，使用三邊測量、三角測量或最大似然估計等定位算法計算節(jié)點位置。而無需測距定位算法則不需要距離和角度信息，算法根據(jù)網(wǎng)絡(luò)的連通性等信息實現(xiàn)節(jié)點定位[1]。

1.2.1距離相關(guān)算法

此類定位算法分為兩步：第一步測距，運用特定的測距技術(shù)測量未知節(jié)點與錨節(jié)點之間的距離；第二步計算，當未知節(jié)點獲得的距離信息到達一個閥值時，使用三邊測量法、三角測量法或最大似然估計法計算未知節(jié)點的位置。在距離無關(guān)定位算法中，測距的消耗在定位過程中占據(jù)了最大的比例，因此研究的重點是測距技術(shù)。

典型的測距方法有6種[2]：

（1）接收信號強度法（RSSI），將信號的傳播損耗轉(zhuǎn)化為距離；

（2）信號傳輸時間法（TOA），將電波的傳輸時間轉(zhuǎn)化為距離，需要精確的時鐘同步；

（3）信號往返時間差法（RTOF），通過計算往返時間、扣除處理時間的方法將時間轉(zhuǎn)換為距離；

（4）信號到達時間差法（TDOA）將兩種不同無線信號到達接收節(jié)點的時間差轉(zhuǎn)化為距離，無需時鐘同步；

（5）信號到達角法（AOA）通過antenna矩陣或多接收機感知發(fā)射節(jié)點信號的到達方向，計算接收節(jié)點和發(fā)射節(jié)點之間的相對方位或角度；

（6）信號到達相位差法（PDOA）利用傳播往返時間粗估計距離，然后利用相位差精確估計距離。

測距精度和功耗成本是一對相互矛盾的性能指標，追求高精度的同時必然帶來高的功耗和硬件成本。當精度要求高時，TODA和PDOA測距方法較優(yōu)；當成本和功耗為主要考慮因素時，RSSI測距方法較優(yōu)。距離相關(guān)定位方法能夠?qū)崿F(xiàn)精確定位，但對無線傳感器節(jié)點的硬件、成本和功耗過要求高，而且在測量距離和角度的準確性方面也需要大量的研究。因此未來距離相關(guān)定位算法研究趨勢是低成本、高能效、高精度的距離或角度測量技術(shù)。

1.2.2 距離無關(guān)定位算法

距離無關(guān)定位算法不需要使用測距技術(shù)，只利用連通情況來估測自己的位置。絕大多數(shù)距離無關(guān)定位算法采取分布式計算模式，因為其可擴展性好，每個節(jié)點的計算復(fù)雜度與網(wǎng)絡(luò)的規(guī)模無關(guān)，計算簡單而且容易實現(xiàn)，同時計算在節(jié)點進行，通信量小。

質(zhì)心定位算法[3]：一個普通節(jié)點所有直接連通錨點組成的多邊形的質(zhì)心作為該節(jié)點的位置。質(zhì)心算法的原理首先是確定包含未知節(jié)點的區(qū)域，計算這個區(qū)域的質(zhì)心，并將其作為未知節(jié)點的位置。在這個算法中，信標節(jié)點周期性地向鄰近節(jié)點廣播信標分組。當未知節(jié)點接收到來自不同信標節(jié)點的信標分組數(shù)量超過某一個門限值k或接收一定時間后，就確定自身位置為這些信標節(jié)點所組成的多邊形的質(zhì)心。與未知節(jié)點處于鄰近關(guān)系的所有錨節(jié)點，所組成的多邊形區(qū)域的質(zhì)心，作為未知節(jié)點的位置估計。

APIT算法[4]：與未知節(jié)點處于鄰近關(guān)系的三個錨節(jié)點構(gòu)成一個三角形，以多個這樣的三角形的交疊區(qū)域的質(zhì)心作為未知節(jié)點的位置。用該算法定位的具體步驟：（1）收集信息：未知節(jié)點收集鄰近信標節(jié)點的信息，如位置、標識號、接收到的信號強度等，鄰居節(jié)點之間交換各自接收到的信標節(jié)點的信息；（2）APIT測試：測試未知節(jié)點是否在不同的信標節(jié)點組合成的三角形內(nèi)部；（3）計算重疊區(qū)域：統(tǒng)計包含未知節(jié)點的三角形，計算所有三角形的重疊區(qū)域；（4）計算未知節(jié)點位置：計算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點的位置。

DV-Hop算法[5]由三個階段組成。第一階段，使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有未知節(jié)點獲得距初始錨節(jié)點的跳數(shù)；第二階段，在獲得其他錨節(jié)點位置（ ， ）和相隔跳數(shù)后，各錨節(jié)點（ ， ）利用所收集的信息按式（1）計算平均跳距：

（1）

式中 是錨節(jié)點 的平均每跳距離， 為節(jié)點 和節(jié)點j之間的跳數(shù)；然后將平均每跳距離作為一個校正值廣播至網(wǎng)絡(luò)中，校正值采用可控洪泛法在網(wǎng)絡(luò)中傳播。第三階段，在二維空間中，一旦一個未知節(jié)點獲得與3個或更多錨節(jié)點的距離后，執(zhí)行三邊測量法或最大似然估計法計算自身的位置。

Amorphous算法與DV-Hop相似也有三個階段，其中第一、第三階段與DV-Hop算法相同，只是在第二階Amorphous定位算法是假設(shè)段網(wǎng)絡(luò)中節(jié)點的通信半徑相同，平均每跳距離為節(jié)點的通信半徑，未知節(jié)點計算到每個信標節(jié)點的跳段距離，誤差比較大。該算法需要預(yù)知網(wǎng)絡(luò)平均連通度，而且需要較高的節(jié)點密度。其相應(yīng)的改進算法改進方向主要是重新計算平均每跳距離，或利用局部跳數(shù)的平均值代替總跳數(shù)，但是誤差相較DV-Hop算法仍比較大。

2 移動錨節(jié)點的節(jié)點定位算法

從前面的分析可以看出成本和錨節(jié)點稀疏問題是目前定位算法最需要進一步解決的問題。如何以較少的成本獲得較多的錨節(jié)點位置信息，同時處理錨節(jié)點稀疏問題是定位算法的一個重要的課題，有學者提出利用移動錨節(jié)點來進行定位。在這些方案中，一個移動錨節(jié)點在網(wǎng)絡(luò)中移動并周期地發(fā)送含有錨節(jié)點位置信息的信標信號，未知節(jié)點接受這些信標信號并通過特定的算法估算自己的位置。其中利用RSSI測距技術(shù)進行定位的算法，信標信號中包含錨節(jié)點的位置信息和信號強度。利用TOA測距進行定位的算法，在發(fā)送信標的時候加入了時間信息，需要有較高的時間同步的要求。利用錨節(jié)點的移動性導致的信號到達時間差進行定位的算法。上述的3個方法都是利用的錨節(jié)點的移動性來節(jié)約錨節(jié)點成本，但是對未知節(jié)點的硬件成本和功耗的要求并未減少，因此低成本、高能效、高精度的距離或角度測量技術(shù)仍然是研究的重點。

3 結(jié)論

對現(xiàn)有常見的無線傳感網(wǎng)絡(luò)定位算法進行了對比分析，目前為止，各種定位算法都存在一定的技術(shù)缺陷，既便如此，這些已有的算法已經(jīng)為無線傳感技術(shù)的推廣發(fā)展乃至整個人類社會的科技進步做出了不可磨滅的貢獻。相信隨著科學界對無線傳感技術(shù)的更加深入、成熟的研究探索，人們一定會開發(fā)出技術(shù)更加全面的節(jié)點定位算法，為更多的行業(yè)發(fā)展帶來活力。

項目基金：渭南師范學院研究生項目（11YKZ025）

參考文獻：

[1] 孫利民，李建中，陳渝等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學出版社，2005.

[2] 王福豹，史龍，任豐原.無線傳感網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學報，2005，16 （5）：858-868.

[3] 陳迅，唐紅雨，涂時亮.無線傳感器網(wǎng)絡(luò)主動分布節(jié)點定位算法[J].計算機工程與設(shè)計， 2008，29（7）：1664-1667.

[4] 劉鋒，張翰，楊驥 一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計算法[J].電子與信息學報，2008，35（5）：1221-1224

[5] 姚忠孝，俞立，董齊芬.基于移動信標的 DV-hop無線傳感網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學報， 2009，22（10）：1504-1507.

作者簡介：陳煒（1984-），女，河南淮陽人，2010年畢業(yè)于中國礦業(yè)大學（北京），碩士，渭南師范學院物理與電氣工程學院助教，研究方向無線傳感器網(wǎng)絡(luò)及應(yīng)用。電話：18700361080，郵箱：cwei62213891@163.com