摘要:文章對(duì)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位機(jī)制與算法進(jìn)行了介紹,，并對(duì)基于測(cè)距的和不基于測(cè)距的兩大類方法進(jìn)行了分析對(duì)比。文章認(rèn)為節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù),，對(duì)于無線傳感器網(wǎng)絡(luò)的許多應(yīng)用來說節(jié)點(diǎn)位置信息都是必須的基本信息,，雖然目前已有不少節(jié)點(diǎn)定位技術(shù),，但僅僅是一些初步的研究成果,，距離無線傳感器網(wǎng)絡(luò)的整體優(yōu)化目標(biāo)還很不夠,，需要繼續(xù)深入研究開發(fā),，提出更多的高效算法，促進(jìn)無線傳感器網(wǎng)絡(luò)進(jìn)一步的普及應(yīng)用,。

關(guān)鍵字:無線傳感器網(wǎng)絡(luò),；自組織網(wǎng)絡(luò)；定位算法

英文摘要:The paper introduces the self-localization mechanism and some algorithms for Wireless Sensor Network (WSN). Moreover, it analyzes and compares the range-based and range-free localization algorithms. It thinks that node location is a key technology for WSN and the information about node location is indispensable to many applications of WSM. Existing node location technologies are the primary research achievements, which are far from the goal of the whole WSN optimization. Therefore, further research and development of more high-efficient algorithms is necessary for popularization of WSN applications.

英文關(guān)鍵字:wireless sensor network; Ad hoc network; localization algorithm

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(60372097)

    人類進(jìn)入信息社會(huì)的一個(gè)主要標(biāo)志就是因特網(wǎng)的迅速普及應(yīng)用,。因特網(wǎng)是信息傳輸網(wǎng)絡(luò)與信息處理計(jì)算機(jī)相互融合的產(chǎn)物,。當(dāng)前的因特網(wǎng)使人類社會(huì)進(jìn)入了“網(wǎng)絡(luò)即計(jì)算機(jī)”的網(wǎng)絡(luò)時(shí)代，人們可以在網(wǎng)上找到資源,，進(jìn)行網(wǎng)絡(luò)計(jì)算和存儲(chǔ)資料,。而傳感器網(wǎng)絡(luò)將是信息獲取(傳感)、信息傳輸與信息處理三大子領(lǐng)域技術(shù)又一次相互融合的產(chǎn)物,，人們可以通過傳感網(wǎng)絡(luò)直接感知真實(shí)客觀世界的一切,，從而極大地?cái)U(kuò)展網(wǎng)絡(luò)的功能和人類認(rèn)識(shí)世界的能力，必將極大地推動(dòng)相關(guān)學(xué)科的發(fā)展，并帶來社會(huì)的深刻變革,。因此,、傳感器網(wǎng)絡(luò)將逐漸引領(lǐng)人類步入“網(wǎng)絡(luò)即傳感器”的傳感時(shí)代,。

    無線傳感器網(wǎng)絡(luò)典型的網(wǎng)絡(luò)結(jié)構(gòu)和工作方式如下：
    將大量傳感器節(jié)點(diǎn)布置或拋灑到感興趣的區(qū)域,，節(jié)點(diǎn)通過自組織快速形成一個(gè)無線網(wǎng)絡(luò),。每個(gè)節(jié)點(diǎn)都有自己控制的一個(gè)區(qū)域，通過感知設(shè)備,，如溫度,、濕度,、聲音或光學(xué)設(shè)備，化學(xué)分析裝置,，電磁感應(yīng)裝置等,，來對(duì)周圍的物理環(huán)境進(jìn)行監(jiān)控，也可以通過配置一些專用的功能單元來實(shí)現(xiàn)與特定環(huán)境交互的功能,。節(jié)點(diǎn)的通信距離一般較短,，只能與自己通信范圍內(nèi)的其他傳感器節(jié)點(diǎn)(稱作鄰居節(jié)點(diǎn)或鄰居)交換數(shù)據(jù)。要訪問通信范圍以外的節(jié)點(diǎn),，必須使用多跳路由,。因此，節(jié)點(diǎn)既是信息的采集和發(fā)出者,，也是信息的轉(zhuǎn)發(fā)傳輸者,，采集的數(shù)據(jù)通過多跳路由到達(dá)匯聚節(jié)點(diǎn)(一些文獻(xiàn)也稱作網(wǎng)關(guān))，匯聚節(jié)點(diǎn)是一個(gè)特殊的節(jié)點(diǎn),，可以通過Internet,、移動(dòng)通信網(wǎng)絡(luò)、衛(wèi)星等與監(jiān)控中心通信,。也可以利用飛機(jī)飛越網(wǎng)絡(luò)上空,，通過無線通信采集網(wǎng)關(guān)數(shù)據(jù)。為了保證網(wǎng)絡(luò)內(nèi)大多數(shù)節(jié)點(diǎn)都可以與網(wǎng)關(guān)建立無線鏈路,，并且保證傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域有很好的覆蓋,，節(jié)點(diǎn)的分布要相當(dāng)?shù)拿芗８呙芏确植歼€可以在某些傳感器節(jié)點(diǎn)能量耗盡或者出現(xiàn)故障時(shí)不影響網(wǎng)絡(luò)的連通性和整體的工作,。無線傳感器網(wǎng)絡(luò)典型的體系結(jié)構(gòu)如圖1所示,。節(jié)點(diǎn)具有傳感、信號(hào)處理和無線通信功能,。

    與傳統(tǒng)的無線網(wǎng)絡(luò)相比,，無線傳感器網(wǎng)絡(luò)具有以下特點(diǎn)：
    (1)電源容量有限。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)一般由電池供電,，而且在使用過程中也不能給電池充電或更換電池,。因此無線傳感器網(wǎng)絡(luò)設(shè)計(jì)的基本原則就是都要以節(jié)能為前提。

    (2)傳感器節(jié)點(diǎn)由于受到低成本,、小體積和低功耗的限制,，其硬件、軟件資源非常有限,。

    (3)無中心,。無線傳感器網(wǎng)絡(luò)一般是一個(gè)對(duì)等式的網(wǎng)絡(luò)。

    (4)自組織,。無線傳感器網(wǎng)絡(luò)的布設(shè)和展開無需依賴于任何預(yù)設(shè)的基礎(chǔ)設(shè)施,。

    (5)多跳路由。網(wǎng)絡(luò)中節(jié)點(diǎn)通信距離有限,，如果希望與較遠(yuǎn)的節(jié)點(diǎn)進(jìn)行通信,，則需要通過中間節(jié)點(diǎn)多跳路由來實(shí)現(xiàn)。

    (6)動(dòng)態(tài)拓?fù)?。無線傳感器網(wǎng)絡(luò)是一個(gè)動(dòng)態(tài)的網(wǎng)絡(luò),，節(jié)點(diǎn)可以隨處移動(dòng)；網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會(huì)隨時(shí)發(fā)生變化,，因此網(wǎng)絡(luò)應(yīng)該具有動(dòng)態(tài)拓?fù)浣M織功能,。

    (7)節(jié)點(diǎn)數(shù)量眾多，分布密集,。為了對(duì)一個(gè)區(qū)域執(zhí)行監(jiān)測(cè)任務(wù),，傳感器節(jié)點(diǎn)往往分布得非常密集，利用節(jié)點(diǎn)之間高度連接性來保證系統(tǒng)的容錯(cuò)性和抗毀性,。

    無線傳感器網(wǎng)絡(luò)屬于一種特殊的Ad hoc網(wǎng)絡(luò)[1—5],，它雖然與傳統(tǒng)的Ad hoc網(wǎng)絡(luò)有很多相似的地方，但是與傳統(tǒng)的Ad hoc網(wǎng)絡(luò)相比,，無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)分布更加密集,，能量更加有限，無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)在大多數(shù)情況下是靜止的,。在無線傳感器網(wǎng)絡(luò)中,，數(shù)據(jù)是被分散處理的，系統(tǒng)會(huì)根據(jù)需要盡早對(duì)數(shù)據(jù)進(jìn)行處理,，這樣可以減少網(wǎng)絡(luò)的流量,，降低功耗并提高系統(tǒng)利用率。由于成本和功耗的限制,，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的硬件設(shè)備資源十分有限,，數(shù)據(jù)的處理能力和存儲(chǔ)能力都比較弱。這就決定了在設(shè)計(jì)無線傳感器網(wǎng)絡(luò)各層技術(shù)標(biāo)準(zhǔn)的時(shí)候都要以簡(jiǎn)單和節(jié)能為最重要的前提條件,。

    無線傳感器網(wǎng)絡(luò)的協(xié)議分層結(jié)構(gòu)基本采用傳統(tǒng)網(wǎng)絡(luò)的分層結(jié)構(gòu),，即包括物理層、數(shù)據(jù)鏈路層,、網(wǎng)絡(luò)層,、傳輸層和應(yīng)用層。另外,，能量,、移動(dòng)、任務(wù)等管理平臺(tái)用于監(jiān)控網(wǎng)絡(luò)中的能量利用、節(jié)點(diǎn)移動(dòng)和任務(wù)分配,。這些平臺(tái)能夠幫助傳感器節(jié)點(diǎn)在較低能耗下協(xié)作完成某些監(jiān)控任務(wù),。圖2所示為無線傳感器網(wǎng)絡(luò)的協(xié)議棧結(jié)構(gòu)。

    能量管理平臺(tái)用來管理一個(gè)節(jié)點(diǎn)如何使用它的能量,。例如,，當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)鄰居節(jié)點(diǎn)發(fā)來的消息之后，它可以將它的接收機(jī)關(guān)閉,，避免接收到重復(fù)的消息,。同樣，當(dāng)一個(gè)節(jié)點(diǎn)的能量極低時(shí),，它會(huì)向鄰節(jié)點(diǎn)廣播一條消息,，告訴鄰節(jié)點(diǎn)自己已經(jīng)沒有多少能量，不能再用來對(duì)消息進(jìn)行傳遞了,，這樣它就可以不再接收鄰節(jié)點(diǎn)發(fā)來的需要傳遞的消息,，將能量都留給自己的消息發(fā)送。移動(dòng)管理平臺(tái)能夠監(jiān)測(cè)并記錄節(jié)點(diǎn)的移動(dòng),。任務(wù)管理平臺(tái)用來平衡和規(guī)劃某個(gè)區(qū)域的感知任務(wù),，安排哪些節(jié)點(diǎn)執(zhí)行哪些感知任務(wù)，能量高的節(jié)點(diǎn)可以比那些能量低的節(jié)點(diǎn)多承擔(dān)一些任務(wù),。有了這些管理平臺(tái),，節(jié)點(diǎn)能夠低能耗地協(xié)調(diào)工作，能夠在移動(dòng)的情況下傳遞數(shù)據(jù),，能夠在節(jié)點(diǎn)之間共享資源,。

    無線傳感器網(wǎng)絡(luò)自身的特點(diǎn)決定了它不能使用目前已經(jīng)存在的一些標(biāo)準(zhǔn)協(xié)議，國外的研究工作者為無線傳感器網(wǎng)絡(luò)的各個(gè)層次都提出了一些解決方案,，但是總的來說,，到目前為止還沒有形成可被廣泛認(rèn)同的標(biāo)準(zhǔn)。

1 無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位機(jī)制
    關(guān)于無線傳感器網(wǎng)絡(luò)的定位問題分為兩類,，一類是無線傳感器網(wǎng)絡(luò)對(duì)自身傳感器節(jié)點(diǎn)的定位,，另一類是無線傳感器網(wǎng)絡(luò)對(duì)外部目標(biāo)的定位。本文主要討論前者,。

    節(jié)點(diǎn)準(zhǔn)確地進(jìn)行自身定位是無線傳感器網(wǎng)絡(luò)應(yīng)用的重要條件,。由于節(jié)點(diǎn)工作區(qū)域或者是人類不適合進(jìn)入的區(qū)域，或者是敵對(duì)區(qū)域,，傳感器節(jié)點(diǎn)有時(shí)甚至需要通過飛行器拋撒于工作區(qū)域,，因此節(jié)點(diǎn)的位置都是隨機(jī)并且未知的。然而在許多應(yīng)用中,，節(jié)點(diǎn)所采集到的數(shù)據(jù)必須結(jié)合其在測(cè)量坐標(biāo)系內(nèi)的位置信息才有意義,，否則,，如果不知道數(shù)據(jù)所對(duì)應(yīng)的地理位置，數(shù)據(jù)就失去意義,。除此之外,，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身的定位還可以在外部目標(biāo)的定位和追蹤以及提高路由效率等方面發(fā)揮作用。因此,，實(shí)現(xiàn)節(jié)點(diǎn)的自身定位對(duì)無線傳感器網(wǎng)絡(luò)有重要的意義,。

    獲得節(jié)點(diǎn)位置的一個(gè)直接想法是利用全球定位系統(tǒng)(GPS)來實(shí)現(xiàn)。但是,，在無線傳感器網(wǎng)絡(luò)中使用GPS來獲得所有節(jié)點(diǎn)的位置受到價(jià)格、體積,、功耗以及可擴(kuò)展性等因素限制,，存在著一些困難。因此目前主要的研究工作是利用傳感器網(wǎng)絡(luò)中少量已知位置的節(jié)點(diǎn)來獲得其他未知位置節(jié)點(diǎn)的位置信息,。已知位置的節(jié)點(diǎn)稱作錨節(jié)點(diǎn),，它們可能是被預(yù)先放置好的，或者采用GPS或其他方法得知自己的位置,。未知位置的節(jié)點(diǎn)稱作未知節(jié)點(diǎn),，它們需要被定位。錨節(jié)點(diǎn)根據(jù)自身位置建立本地坐標(biāo)系,，未知節(jié)點(diǎn)根據(jù)錨節(jié)點(diǎn)計(jì)算出自己在本地坐標(biāo)系里的相對(duì)位置,。

    根據(jù)具體的定位機(jī)制，可以將現(xiàn)有的無線傳感器網(wǎng)絡(luò)自身定位方法分為兩類：基于測(cè)距的(Range-based)方法和不基于測(cè)距的(Range-free)方法[6],?；跍y(cè)距的定位機(jī)制需要測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離或者角度信息，然后使用三邊測(cè)量法,、三角測(cè)量法或最大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的位置,。而不基于測(cè)距的定位機(jī)制無需距離或角度信息，或者不用直接測(cè)量這些信息,，僅根據(jù)網(wǎng)絡(luò)的連通性等信息實(shí)現(xiàn)節(jié)點(diǎn)的定位,。

1.1  基于測(cè)距的定位方法
    常用的定位方法是基于測(cè)距定位方法，在這種定位機(jī)制中需要先得到兩個(gè)節(jié)點(diǎn)之間的距離或者角度信息,，通常采用以下方法,。

1.1.1  信號(hào)強(qiáng)度測(cè)距法
    已知發(fā)射功率，在接收節(jié)點(diǎn)測(cè)量接收功率,，計(jì)算傳播損耗,，使用理論或經(jīng)驗(yàn)的信號(hào)傳播模型將傳播損耗轉(zhuǎn)化為距離。例如,，在自由空間中,，距發(fā)射機(jī)d 處的天線接收到的信號(hào)強(qiáng)度由下面的公式給出：
Pr(d )=PtGtGrλ2/(4π)2d 2L      (1)

    其中，Pt為發(fā)射機(jī)功率；Pr(d )是在距離d 處的接收功率,；Gt,、Gr分別是發(fā)射天線和接收天線的增益；d 是距離,，單位為米,；L為與傳播無關(guān)的系統(tǒng)損耗因子；λ是波長(zhǎng),，單位為米,。由公式可知，在自由空間中,，接收機(jī)功率隨發(fā)射機(jī)與接收機(jī)距離的平方衰減,。這樣，通過測(cè)量接收信號(hào)的強(qiáng)度,，再利用式(1)就能計(jì)算出收發(fā)節(jié)點(diǎn)間的大概距離,。

    得到錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離信息后，采用三邊測(cè)量法或最大似然估計(jì)法可計(jì)算出未知節(jié)點(diǎn)的位置,。三邊計(jì)算的理論依據(jù)是,，在三維空間中，知道了一個(gè)未知節(jié)點(diǎn)到三個(gè)以上錨節(jié)點(diǎn)的距離,，就可以確定該點(diǎn)的坐標(biāo),。

    三邊測(cè)量法在二維平面上用幾何圖形表示出來的意義是：當(dāng)?shù)玫轿粗?jié)點(diǎn)到一個(gè)錨節(jié)點(diǎn)的距離時(shí)，就可以確定此未知節(jié)點(diǎn)在以此錨節(jié)點(diǎn)為圓心,、以距離為半徑的圓上,；得到未知節(jié)點(diǎn)到3個(gè)錨節(jié)點(diǎn)的距離時(shí)，3個(gè)圓的交點(diǎn)就是未知節(jié)點(diǎn)的位置,。如圖3所示,。

    然而，公式(1)只是電磁波在理想的自由空間中傳播的數(shù)學(xué)模型,，實(shí)際應(yīng)用中的情況要復(fù)雜的多,，尤其是在分布密集的無線傳感器網(wǎng)絡(luò)中。反射,、多徑傳播,、非視距(NLOS)、天線增益等問題都會(huì)對(duì)相同距離產(chǎn)生顯著不同的傳播損耗,。因此這種方法的主要誤差來源是環(huán)境影響所造成的信號(hào)傳播模型的復(fù)雜性,。信號(hào)強(qiáng)度測(cè)距法通常屬于一種粗糙的測(cè)距技術(shù)。

    還有一些其他算法：如文獻(xiàn)[7]提出了一種節(jié)點(diǎn)位置推測(cè)算法,，該算法通過一種判決節(jié)點(diǎn),，利用收集到的錨節(jié)點(diǎn)的位置信息和節(jié)點(diǎn)間的距離信息,，執(zhí)行節(jié)點(diǎn)位置推測(cè)算法，推測(cè)出所有位置可確定的待測(cè)節(jié)點(diǎn)的位置,。

1.1.2  到達(dá)時(shí)間及時(shí)間差測(cè)距法
    到達(dá)時(shí)間(TOA)技術(shù)通過測(cè)量信號(hào)傳播時(shí)間來測(cè)量距離,。在TOA方法中，若電波從錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的傳播時(shí)間為t,，電波傳播速度為c,，則錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離為t×c。TOA要求接收信號(hào)的錨節(jié)點(diǎn)或未知節(jié)點(diǎn)知道信號(hào)開始傳輸?shù)臅r(shí)刻,，并要求節(jié)點(diǎn)有非常精確的時(shí)鐘,。

    使用TOA技術(shù)比較典型的定位系統(tǒng)是GPS，GPS系統(tǒng)需要昂貴高能耗的電子設(shè)備來精確同步衛(wèi)星時(shí)鐘,。在無線傳感器網(wǎng)絡(luò)中,，節(jié)點(diǎn)間的距離較小，采用TOA測(cè)距難度較大,，同時(shí)節(jié)點(diǎn)硬件尺寸、價(jià)格和功耗的限制也決定了TOA技術(shù)對(duì)無線傳感器網(wǎng)絡(luò)是不可行的,。

    時(shí)間差(TDOA)測(cè)距技術(shù)在無線傳感器網(wǎng)絡(luò)定位方案中得到了較多的應(yīng)用[8]。通過記錄兩種不同信號(hào)(常使用無線電信號(hào)和超聲波信號(hào))的到達(dá)時(shí)間差異,，根據(jù)已知的兩種信號(hào)的傳播速度，直接把時(shí)間差轉(zhuǎn)化為距離,。該技術(shù)受到超聲波傳播距離的限制和非視距問題對(duì)超聲波信號(hào)傳播的影響,，不僅需要精確的時(shí)鐘記錄兩種信號(hào)的到達(dá)時(shí)間差異，還需要傳感器節(jié)點(diǎn)同時(shí)具備感知兩種不同信號(hào)的能力,。

1.1.3  時(shí)間差定位法
    TDOA測(cè)距是通過計(jì)算兩種不同無線信號(hào)到達(dá)未知節(jié)點(diǎn)的時(shí)間差,，再根據(jù)兩種信號(hào)傳播速度來計(jì)算得到未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離。TDOA定位與TDOA測(cè)距不同,，TDOA定位計(jì)算兩個(gè)錨節(jié)點(diǎn)信號(hào)到達(dá)未知節(jié)點(diǎn)的時(shí)間差,，將其轉(zhuǎn)換成到兩個(gè)錨節(jié)點(diǎn)的距離之差，未知節(jié)點(diǎn)通過到多組錨節(jié)點(diǎn)的距離之差得出自身的位置,。

    在二維平面上的,，雙曲線的幾何意義是到兩個(gè)定點(diǎn)的距離之差為一個(gè)常數(shù)的所有點(diǎn)的集合，兩個(gè)定點(diǎn)稱作焦點(diǎn),。因此TDOA定位在二維平面上的幾何意義為：得到未知節(jié)點(diǎn)與兩個(gè)錨節(jié)點(diǎn)的距離之差,，即可知未知節(jié)點(diǎn)定位于以兩個(gè)錨節(jié)點(diǎn)為焦點(diǎn)的雙曲線方程上，通過測(cè)量得到未知節(jié)點(diǎn)所屬的兩個(gè)以上雙曲線方程時(shí),，這些雙曲線唯一的交點(diǎn)即為未知節(jié)點(diǎn)的位置,。由于這種方法不是采用到達(dá)的絕對(duì)時(shí)間來確定節(jié)點(diǎn)的位置,，降低了對(duì)時(shí)間同步的要求，但是仍然需要較精確的計(jì)時(shí)功能,，同時(shí)由于無線傳感器網(wǎng)絡(luò)具有分布密集和無線通信范圍小的特點(diǎn),，這種方法實(shí)現(xiàn)起來難度較大。

1.1.4  到達(dá)角定位法
    到達(dá)角(AOA)定位法通過陣列天線或多個(gè)接收器結(jié)合來得到相鄰節(jié)點(diǎn)發(fā)送信號(hào)的方向,，從而構(gòu)成一根從接收機(jī)到發(fā)射機(jī)的方位線,。兩根方位線的交點(diǎn)即為未知節(jié)點(diǎn)的位置。

    圖4所示為基本的AOA定位法,，未知節(jié)點(diǎn)得到與錨節(jié)點(diǎn)N1和N2所構(gòu)成的角度之后就可以確定自身位置,。另外，AOA信息還可以與TOA,、TDOA信息一起使用成為混合定位法,。采用混合定位法或者可以實(shí)現(xiàn)更高的精確度，減小誤差,，或者可以降低對(duì)某一種測(cè)量參數(shù)數(shù)量的需求,。AOA定位法的硬件系統(tǒng)設(shè)備復(fù)雜，并且需要兩節(jié)點(diǎn)之間存在視距(LOS)傳輸,，因此不適合用于無線傳感器網(wǎng)絡(luò)的定位。

1.2  不基于測(cè)距的定位算法
    基于測(cè)量距離和角度的算法的缺點(diǎn)是使傳感器節(jié)點(diǎn)造價(jià)增高,，消耗了有限的電池資源，而且在測(cè)量距離和角度的準(zhǔn)確性方面需要大量的研究,。下面介紹不基于測(cè)距的定位算法。不基于測(cè)距的算法不需要知道未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離或者不需要直接測(cè)量此距離,，在成本和功耗方面比基于測(cè)距的方法具有優(yōu)勢(shì),。

    下面先介紹4種重要的分布式不基于測(cè)距的算法，它們分別為質(zhì)心法,、基于距離矢量計(jì)算跳數(shù)的算法(DV-Hop),、無定形的(Amorphous)算法和以三角形內(nèi)的點(diǎn)近似定位(APIT)算法，然后對(duì)這4種算法進(jìn)行分析對(duì)比,。

1.2.1  質(zhì)心法
    質(zhì)心法[9]是南加州大學(xué)Nirupama Bulusu等學(xué)者提出的一種僅基于網(wǎng)絡(luò)連通性的室外定位算法,。該算法的中心思想是：未知節(jié)點(diǎn)以所有在其通信范圍內(nèi)的錨節(jié)點(diǎn)的幾何質(zhì)心作為自己的估計(jì)位置。具體過程為：錨節(jié)點(diǎn)每隔一段時(shí)間向鄰居節(jié)點(diǎn)廣播一個(gè)信標(biāo)信號(hào),，信號(hào)中包含有錨節(jié)點(diǎn)自身的ID和位置信息,。當(dāng)未知節(jié)點(diǎn)在一段偵聽時(shí)間內(nèi)接收到來自錨節(jié)點(diǎn)的信標(biāo)信號(hào)數(shù)量超過某一個(gè)預(yù)設(shè)的門限后，該節(jié)點(diǎn)認(rèn)為與此錨節(jié)點(diǎn)連通,，并將自身位置確定為所有與之連通的錨節(jié)點(diǎn)所組成的多邊形的質(zhì)心,。

    質(zhì)心定位算法的最大優(yōu)點(diǎn)是它非常簡(jiǎn)單,，計(jì)算量小，完全基于網(wǎng)絡(luò)的連通性,，但是需要較多的錨節(jié)點(diǎn)。

1.2.2  DV-Hop算法
    DV-Hop算法[10]是由D.Niculescu和B.Nath等人提出的,。DV-Hop定位算法的原理與經(jīng)典的距離矢量路由算法比較相似。在DV-Hop算法中,，錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播一個(gè)信標(biāo),，信標(biāo)中包含有此錨節(jié)點(diǎn)的位置信息和一個(gè)初始值為1的表示跳數(shù)的參數(shù),。此信標(biāo)在網(wǎng)絡(luò)中被以泛洪的方式傳播出去，信標(biāo)每次被轉(zhuǎn)發(fā)時(shí)跳數(shù)都增加1,。接收節(jié)點(diǎn)在它收到的關(guān)于某一個(gè)錨節(jié)點(diǎn)的所有信標(biāo)中保存具有最小跳數(shù)值的信標(biāo),，丟棄具有較大跳數(shù)值的同一錨節(jié)點(diǎn)的信標(biāo)。通過這一機(jī)制,，網(wǎng)絡(luò)中所有節(jié)點(diǎn)(包括其他錨節(jié)點(diǎn))都獲得了到每一個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值,。圖5為一個(gè)示意圖[6]，表示了網(wǎng)絡(luò)中的節(jié)點(diǎn)到錨節(jié)點(diǎn)A的跳數(shù)值,。

    為了將跳數(shù)值轉(zhuǎn)換成物理距離，系統(tǒng)需要估計(jì)網(wǎng)絡(luò)中平均每跳的距離,。錨節(jié)點(diǎn)具有到網(wǎng)絡(luò)內(nèi)部其他錨節(jié)點(diǎn)的跳數(shù)值以及這些錨節(jié)點(diǎn)的位置信息,，因此錨節(jié)點(diǎn)可以通過計(jì)算得到距其他錨節(jié)點(diǎn)的實(shí)際距離。經(jīng)過計(jì)算,，一個(gè)錨節(jié)點(diǎn)得到網(wǎng)絡(luò)的平均每跳距離,，并將此估計(jì)值廣播到網(wǎng)絡(luò)中，稱作校正值,，任何節(jié)點(diǎn)一旦接收到此校正值,，就可以估計(jì)自己到這個(gè)錨節(jié)點(diǎn)的距離。

    如果一個(gè)節(jié)點(diǎn)能夠獲得到3個(gè)以上錨節(jié)點(diǎn)的估計(jì)距離,，它就可以利用三邊法估計(jì)其自身的位置,。

    DV-Hop算法與基于測(cè)距算法具有相似之處，就是都需要獲得未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離,，但是DV-Hop獲得距離的方法是通過網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)信息的計(jì)算而不是通過無線電波信號(hào)的測(cè)量,。

    在基于測(cè)距的方法中，未知節(jié)點(diǎn)只能獲得到自己射頻覆蓋范圍內(nèi)的錨節(jié)點(diǎn)的距離,，而DV-Hop算法可以獲得到未知節(jié)點(diǎn)無線射程以外的錨節(jié)點(diǎn)的距離,，這樣就可以獲得更多的有用數(shù)據(jù),，提高定位精度。

1.2.3  Amorphous算法
    Amorphous定位算法[11]與DV-Hop算法類似,。首先,，采用與DV-Hop算法類似的方法獲得距錨節(jié)點(diǎn)的跳數(shù)，稱為梯度值,。未知節(jié)點(diǎn)收集鄰居節(jié)點(diǎn)的梯度值,，計(jì)算關(guān)于某個(gè)錨節(jié)點(diǎn)的局部梯度平均值。與DV-Hop算法不同的是：Amorphous算法假定預(yù)先知道網(wǎng)絡(luò)的密度,，然后離線計(jì)算網(wǎng)絡(luò)的平均每跳距離,，最后當(dāng)獲得3個(gè)或更多錨節(jié)點(diǎn)的梯度值后，未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)的距離,，并使用三邊測(cè)量法和最大似然估計(jì)法估算自身位置,。

1.2.4  APIT算法
    在APIT算法[6]中，一個(gè)未知節(jié)點(diǎn)從它所有能夠與之通信的錨節(jié)點(diǎn)中選擇3個(gè)節(jié)點(diǎn),，測(cè)試它自身是在這3個(gè)錨節(jié)點(diǎn)所組成的三角形內(nèi)部還是在其外部,；然后再選擇另外3個(gè)錨節(jié)點(diǎn)進(jìn)行同樣的測(cè)試，直到窮盡所有的組合或者達(dá)到所需的精度,。如果未知節(jié)點(diǎn)在某三角形內(nèi)部,，稱此三角形包含未知節(jié)點(diǎn)；最后,，未知節(jié)點(diǎn)將包含自己的所有三角形的相交區(qū)域的質(zhì)心作為自己的估計(jì)位置,。

    APIT算法最關(guān)鍵的步驟是測(cè)試未知節(jié)點(diǎn)是在3個(gè)錨節(jié)點(diǎn)所組成的三角形內(nèi)部還是外部，這一測(cè)試的理論基礎(chǔ)是三角形內(nèi)的點(diǎn)(PIT)測(cè)試,。PIT測(cè)試用來測(cè)試一個(gè)節(jié)點(diǎn)是在其他3個(gè)節(jié)點(diǎn)所組成的三角形內(nèi)部還是在其外部,，其原理如圖6所示：假如存在一個(gè)方向，沿著這個(gè)方向M點(diǎn)會(huì)同時(shí)遠(yuǎn)離或者同時(shí)接近A,、B,、C 3個(gè)點(diǎn)，那么M位于△ABC外,；否則,，M位于△ABC內(nèi)。這就是PIT測(cè)試的原理,，其證明可以在文獻(xiàn)[6]中找到,。

    在靜態(tài)網(wǎng)絡(luò)中，M點(diǎn)固定,，不能朝著不同的方向移動(dòng),，此時(shí)無法執(zhí)行PIT測(cè)試，為此定義APIT測(cè)試(Approximate PIT)：假如節(jié)點(diǎn)M的鄰居節(jié)點(diǎn)中沒有同時(shí)遠(yuǎn)離或同時(shí)靠近3個(gè)錨節(jié)點(diǎn)A,、B,、C的節(jié)點(diǎn),，那么M就在△ABC之內(nèi)；否則M就在△ABC外,，如圖7所示,。

    這種方法是利用網(wǎng)絡(luò)較高的節(jié)點(diǎn)密度來模擬節(jié)點(diǎn)移動(dòng)，根據(jù)給定方向上一個(gè)節(jié)點(diǎn)距離錨節(jié)點(diǎn)越遠(yuǎn)接收信號(hào)強(qiáng)度越弱的無線傳播特性來判斷距錨節(jié)點(diǎn)的遠(yuǎn)近,。在無線傳感器網(wǎng)絡(luò)中,，鄰居節(jié)點(diǎn)間互相交換信息，仿效PIT測(cè)試的節(jié)點(diǎn)移動(dòng),。如圖7中左圖所示,，節(jié)點(diǎn)M通過與鄰居節(jié)點(diǎn)1交換信息，得知自身如果運(yùn)動(dòng)至節(jié)點(diǎn)1,，將遠(yuǎn)離錨節(jié)點(diǎn)B和C,，但會(huì)接近錨節(jié)點(diǎn)A，與鄰居節(jié)點(diǎn)2,、3,、4的通信和判斷過程類似，最終確定自身位于△ABC內(nèi),，而在圖7的右圖中,，節(jié)點(diǎn)M可知假如自身運(yùn)動(dòng)至鄰居節(jié)點(diǎn)2處，將同時(shí)遠(yuǎn)離錨節(jié)點(diǎn)A,、B,、C，故判斷自身不在△ABC中,。

    當(dāng)節(jié)點(diǎn)M比較靠近△ABC的一條邊,，或者M(jìn)周圍的鄰居節(jié)點(diǎn)分布不均勻時(shí)，APIT的判斷可能會(huì)發(fā)生錯(cuò)誤,，當(dāng)未知節(jié)點(diǎn)密度較大時(shí)，APIT判斷發(fā)生錯(cuò)誤的概率較小,。

1.2.5  幾種不基于測(cè)距的定位算法的比較
    節(jié)點(diǎn)之間的無線通信所消耗的電能比其他部件所消耗的電能要大很多,，所以應(yīng)盡量減少節(jié)點(diǎn)之間的無線通信量。由于每個(gè)節(jié)點(diǎn)的能量十分有限,，也不宜將大量的通信和計(jì)算固定于某個(gè)或者某些節(jié)點(diǎn),，否則，這些節(jié)點(diǎn)的電能會(huì)很快耗盡,，出現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)不均衡的情況,。因此，在無線傳感器網(wǎng)絡(luò)中,，要求盡量采用分布式的節(jié)點(diǎn)定位算法,，即定位的計(jì)算過程分散在每個(gè)未知節(jié)點(diǎn)上而不是依賴于在某個(gè)中心節(jié)點(diǎn)進(jìn)行集中計(jì)算,。前邊介紹的4種不基于測(cè)距的定位算法都屬于分布式算法，此外,，還有很少的幾種集中式不基于測(cè)距的定位算法,，它們的定位精度與分布式算法沒有明顯區(qū)別，并且需要進(jìn)行集中計(jì)算,。

    質(zhì)心,、DV-Hop、Amorphous和APIT算法是完全分布式的,，僅需要少量通信和簡(jiǎn)單計(jì)算,，具有良好的擴(kuò)展性。無線傳感器網(wǎng)絡(luò)自身定位算法的性能對(duì)其可用性有直接的影響,，如何評(píng)價(jià)定位算法是一個(gè)需要研究的問題,。目前已有幾個(gè)常用的標(biāo)準(zhǔn)，如定位精度,、錨節(jié)點(diǎn)密度,、未知節(jié)點(diǎn)密度、計(jì)算量,、節(jié)點(diǎn)之間的通信量等,，但這些標(biāo)準(zhǔn)還沒有達(dá)到完善和統(tǒng)一的程度，需要進(jìn)一步地模型化和量化,。文獻(xiàn)[6]中經(jīng)過大量實(shí)驗(yàn)對(duì)比了4種分布式不基于測(cè)距的定位算法,，其結(jié)果見表1。表1可以幫助加強(qiáng)對(duì)不基于測(cè)距的定位算法的理解以及促進(jìn)完整評(píng)估體系的建立,。

    不規(guī)則性的程度(DOI)表示節(jié)點(diǎn)無線傳播模型的不規(guī)則性,。當(dāng)它為0時(shí)，無線傳播模型為球型,，DOI值越大表示節(jié)點(diǎn)無線傳播模型越不規(guī)則,。

    總的來說，不基于測(cè)距的定位機(jī)制屬于粗精度的定位機(jī)制,，然而粗精度定位對(duì)大多數(shù)無線傳感器網(wǎng)絡(luò)的應(yīng)用已經(jīng)足夠,，研究表明，當(dāng)定位誤差小于傳感器節(jié)點(diǎn)無線通信半徑的40%時(shí),，定位誤差對(duì)路由性能和目標(biāo)追蹤精確度的影響不會(huì)很大,。

2 結(jié)束語
    與傳統(tǒng)的無線網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)電源容量有限,，傳感器節(jié)點(diǎn)由于受到低成本,、小體積和低功耗的限制，其硬件軟件資源非常有限。無線傳感器網(wǎng)絡(luò)一般是一個(gè)對(duì)等的,、自組織,、多跳路由的、動(dòng)態(tài)的網(wǎng)絡(luò),。而且節(jié)點(diǎn)數(shù)量眾多,，分布密集，利用節(jié)點(diǎn)之間高度連接性來保證系統(tǒng)的容錯(cuò)性和抗毀性,。因此,、對(duì)于無線傳感器網(wǎng)絡(luò)這種資源極度受限的特殊系統(tǒng)而言，如果仍然依據(jù)原有的網(wǎng)絡(luò)通信7層協(xié)議的模型來進(jìn)行設(shè)計(jì),，將是很不適合的,，需要做較大的變革。需要采用一種整體優(yōu)化的方法,，即是要跨越物理層,、網(wǎng)絡(luò)層、應(yīng)用層,，以及跨越嵌入式操作系統(tǒng),、網(wǎng)絡(luò)節(jié)點(diǎn)的業(yè)務(wù)類型、網(wǎng)絡(luò)節(jié)點(diǎn)的協(xié)同處理和特殊應(yīng)用需求等多個(gè)層次,，進(jìn)行系統(tǒng)整體的優(yōu)化設(shè)計(jì),，才能滿足無線傳感器網(wǎng)絡(luò)的特殊要求。

    節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù),，對(duì)于無線傳感器網(wǎng)絡(luò)的許多應(yīng)用來說節(jié)點(diǎn)位置信息都是必須的基本信息,；而且節(jié)點(diǎn)定位的一些算法也從一定程度上反映了無線傳感器網(wǎng)絡(luò)的特殊性。目前已有的節(jié)點(diǎn)定位技術(shù)還僅僅是一些初步的研究成果,，距離無線傳感器網(wǎng)絡(luò)的整體優(yōu)化目標(biāo)還有很多工作要做,；相信隨著研究開發(fā)的繼續(xù)深入，還會(huì)有更多的高效算法出現(xiàn),，從而促進(jìn)無線傳感器網(wǎng)絡(luò)進(jìn)一步的普及應(yīng)用,。

3 參考文獻(xiàn)
[1] Zhao Feng, Guibas L J. Wireless Sensor Networks: An Information Processing Approach [M]. Amsterdam (Netherlands): Morgan Kaufmann Publishers, 2004.
[2]Callaway E H J. Wireless Sensor Networks: Architectures and Protocols [M]. Boca Raton (FL, USA): CRC Press, 2003.
[3] Raghavendra C S, Sivalingam K M, Znati T. Wireless Sensor Networks [M]. Boston (MA, USA): Kluwer Acadenic Publishers, 2004.
[4] 朱近康. 無線傳感器網(wǎng)絡(luò)技術(shù) [J]. 中興通訊技術(shù), 2004,10(S0):14—15.
[5] 朱林, 袁曉, 葛利嘉, 等. 超寬帶無線傳感器網(wǎng)絡(luò)綜述 [J]. 測(cè)控技術(shù), 2004,23(12): 1—4.
[6] He Tian, Huang Chengdu, Blum B M, et al. Range-free Localization Schemes in Large Scale Sensor Networks [A]. Proceedings of the 9th Annual International Conference on Mobile Computing and Networking,MOBICOM′ 2003 [C]. San Diego (CA, USA), 2003. New York (NY, USA): ACM Press, 2003.81—95.
[7] 孫學(xué)斌, 王匯源, 周正. 自組網(wǎng)中節(jié)點(diǎn)位置推測(cè)算法的研究 [J]. 山東大學(xué)學(xué)報(bào) (工學(xué)版), 2003,34(3):55—59.
[8] 史龍, 王福豹, 段渭軍, 等. 無線傳感器網(wǎng)絡(luò)Range-Free自身定位機(jī)制與算法 [J]. 計(jì)算機(jī)工程與應(yīng)用, 2004,40(23):127—130,151.
[9] Bulusu N, Heidemann J, Estrin D. GPS-less Low- cost Outdoor Localization for Very Small Devices [J]. IEEE Personal Communications, 2000,7(5):28—34.
[10] Niculescu D, Nath B. Ad hoc Positioning System [A]. Conference Record of IEEE Global Telecommunications Conference, GLOBECOM′2001, Vol 5 [C]. San Antonio (TX, USA), 2001. Piscataway (NJ, USA): IEEE, 2001.2926—2931.
[11] Priyantha N B, Miu A K L, Balakrishnan H, et al. The Cricket Compass for Context-aware Mobile Applications [A]. Proceedings of 7th ACM International Conference on Mobile Computing and Networking, MOBICOM′ 2001 [C]. Rome (Italy), 2001.New York (NY,USA): ACM Press, 2001.1—14.

收稿日期：2005-05-15

 

周正，北京郵電大學(xué)工學(xué)博士,。北京郵電大學(xué)教授,、博士生導(dǎo)師。長(zhǎng)期從事通信電路與系統(tǒng),、信號(hào)處理的教學(xué)與科研工作。近年來主持和參加了多項(xiàng)國家教育部博士點(diǎn)基金,、國家自然科學(xué)基金,、國家“863”計(jì)劃及原郵電部重點(diǎn)科研項(xiàng)目的研究。在國內(nèi)外學(xué)術(shù)會(huì)議及學(xué)術(shù)刊物上已發(fā)表論文80多篇，出版譯著3部?，F(xiàn)從事寬帶無線通信,、短距離無線通信、智能信號(hào)處理及通信網(wǎng)絡(luò)優(yōu)化等方面的研究,。