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

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

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

1 節(jié)點(diǎn)定位算法

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

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

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

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

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

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

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

典型的測(cè)距方法有6種[2]：

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

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

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

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

（5）信號(hào)到達(dá)角法（AOA）通過antenna矩陣或多接收機(jī)感知發(fā)射節(jié)點(diǎn)信號(hào)的到達(dá)方向，計(jì)算接收節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)之間的相對(duì)方位或角度；

（6）信號(hào)到達(dá)相位差法（PDOA）利用傳播往返時(shí)間粗估計(jì)距離，然后利用相位差精確估計(jì)距離。

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

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

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

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

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

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

（1）

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

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

2 移動(dòng)錨節(jié)點(diǎn)的節(jié)點(diǎn)定位算法

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

3 結(jié)論

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

項(xiàng)目基金：渭南師范學(xué)院研究生項(xiàng)目（11YKZ025）

參考文獻(xiàn)：

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

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

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

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

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

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