無線傳感網(wǎng)定位技術(shù)

1、無線傳感網(wǎng)無線傳感網(wǎng) 定位技術(shù)定位技術(shù) n一、 引言 n二、 節(jié)點定位技術(shù)基本概念 n三、 基于距離的定位算法 n四、 與距離無關(guān)的定位算法 n五、 總結(jié) 引言引言 n無線傳感器節(jié)點的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置信息的無線傳感器節(jié)點的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置信息的 監(jiān)測數(shù)據(jù)往往毫無意義。監(jiān)測數(shù)據(jù)往往毫無意義。 n在傳感網(wǎng)的各種應用中，監(jiān)測到事件后關(guān)心的一個重要問題就是該事件在傳感網(wǎng)的各種應用中，監(jiān)測到事件后關(guān)心的一個重要問題就是該事件 發(fā)生的位置。發(fā)生的位置。 q如在環(huán)境監(jiān)測應用中需要知道采集的環(huán)境信息所對應的具體區(qū)域位置； q對于突發(fā)事件，需要知道森林火災現(xiàn)場位置

2、，戰(zhàn)場上敵方車輛運動的區(qū)域， 天然氣管道泄漏的具體地點等。 n傳感器節(jié)點自身定位就是根據(jù)傳感器節(jié)點自身定位就是根據(jù)少數(shù)已知位置的節(jié)點少數(shù)已知位置的節(jié)點，按照某種定位機制，按照某種定位機制 確定自身位置。只有在傳感器節(jié)點自身正確定位之后，才能確定傳感器確定自身位置。只有在傳感器節(jié)點自身正確定位之后，才能確定傳感器 節(jié)點監(jiān)測到的事件發(fā)生的具體位置，這需要監(jiān)測到該事件的多個傳感器節(jié)點監(jiān)測到的事件發(fā)生的具體位置，這需要監(jiān)測到該事件的多個傳感器 節(jié)點之間的相互協(xié)作，并利用它們自身的位置信息，使用特定定位機制節(jié)點之間的相互協(xié)作，并利用它們自身的位置信息，使用特定定位機制 確定事件發(fā)生的位置。確定事件發(fā)生的

3、位置。 引言引言 n全球定位系統(tǒng)全球定位系統(tǒng)GPS(Global Position System)是目前應用最廣泛最成熟是目前應用最廣泛最成熟 的定位系統(tǒng)，通過衛(wèi)星的授時和測距對用戶節(jié)點進行定位，具有定位精的定位系統(tǒng)，通過衛(wèi)星的授時和測距對用戶節(jié)點進行定位，具有定位精 度高、實時性好、抗干擾能力強等優(yōu)點，但是度高、實時性好、抗干擾能力強等優(yōu)點，但是GPS定位適應于無遮擋的定位適應于無遮擋的 室外環(huán)境，用戶節(jié)點通常能耗高體積大，成本也比較高，需要固定的基室外環(huán)境，用戶節(jié)點通常能耗高體積大，成本也比較高，需要固定的基 礎設施等礎設施等，這使得不適用于低成本自組織的傳感網(wǎng)。，這使得不適用于低成本自組

4、織的傳感網(wǎng)。 n在機器人領(lǐng)域中，機器人節(jié)點的移動性和自組織等特性，其定位技術(shù)與在機器人領(lǐng)域中，機器人節(jié)點的移動性和自組織等特性，其定位技術(shù)與 傳感網(wǎng)的定位技術(shù)具有一定的相似性，但是機器人節(jié)點通常攜帶充足的傳感網(wǎng)的定位技術(shù)具有一定的相似性，但是機器人節(jié)點通常攜帶充足的 能量供應和精確的測距設備，系統(tǒng)中機器人的數(shù)量很少，所以這些機器能量供應和精確的測距設備，系統(tǒng)中機器人的數(shù)量很少，所以這些機器 人定位算法也不適用于傳感網(wǎng)。人定位算法也不適用于傳感網(wǎng)。 n受到成本、功耗、擴展性等問題的限制，為每個傳感器安裝受到成本、功耗、擴展性等問題的限制，為每個傳感器安裝GPS模塊等模塊等 這些傳統(tǒng)定位手段并不實

5、際，甚至在某些場合可能根本無法實現(xiàn)，因此這些傳統(tǒng)定位手段并不實際，甚至在某些場合可能根本無法實現(xiàn)，因此 必須采用一定的機制與算法實現(xiàn)傳感器節(jié)點的自身定位必須采用一定的機制與算法實現(xiàn)傳感器節(jié)點的自身定位 返回 節(jié)點定位技術(shù)基本概念 n1定位的含義定位的含義 n無線傳感網(wǎng)定位問題是指網(wǎng)絡通過特定方法提供節(jié)點的位置信息。無線傳感網(wǎng)定位問題是指網(wǎng)絡通過特定方法提供節(jié)點的位置信息。 n其定位方式可分為節(jié)點其定位方式可分為節(jié)點自身定位自身定位和和目標定位目標定位。 q自身定位：是確定網(wǎng)絡節(jié)點的坐標位置的過程。節(jié)點自身定位是網(wǎng)絡自身 屬性的確定過程，可以通過人工標定或者各種節(jié)點的自定位算法完成。 q目標定位

6、：是確定網(wǎng)絡覆蓋區(qū)域內(nèi)一個事件或者一個目標的坐標位置。目 標定位是以位置已知的網(wǎng)絡節(jié)點作為參考，確定事件或者目標在網(wǎng)絡覆蓋 范圍內(nèi)所在的位置。 n位置信息有多種分類方法。通常有位置信息有多種分類方法。通常有物理位置物理位置和和符號位置符號位置兩大類。兩大類。 q物理位置指目標在特定坐標系下的位置數(shù)值，表示目標的相對或者絕對位 置。 q符號位置指目標與一個基站或者多個基站接近程度的信息，表示目標與基 站之間的連通關(guān)系，提供目標大致的所在范圍。 n在很多傳感網(wǎng)應用場合中，必須知道各節(jié)點物理位置的坐標信息。通過在很多傳感網(wǎng)應用場合中，必須知道各節(jié)點物理位置的坐標信息。通過 人工測量或配置來獲得節(jié)點坐

7、標的方法往往不可行。通常傳感網(wǎng)能夠通人工測量或配置來獲得節(jié)點坐標的方法往往不可行。通常傳感網(wǎng)能夠通 過網(wǎng)絡內(nèi)部節(jié)點之間的相互測距和信息交換，形成一套全網(wǎng)節(jié)點的坐標。過網(wǎng)絡內(nèi)部節(jié)點之間的相互測距和信息交換，形成一套全網(wǎng)節(jié)點的坐標。 這才是經(jīng)濟和可行的定位方案。這才是經(jīng)濟和可行的定位方案。 n從廣義上來講，無線傳感網(wǎng)的定位問題包括傳感器節(jié)點的自身定位和對從廣義上來講，無線傳感網(wǎng)的定位問題包括傳感器節(jié)點的自身定位和對 監(jiān)控目標的定位。目標定位側(cè)重于傳感網(wǎng)在目標跟蹤方面的應用，是對監(jiān)控目標的定位。目標定位側(cè)重于傳感網(wǎng)在目標跟蹤方面的應用，是對 監(jiān)控目標的位置估計，它以先期的節(jié)點自身定位為基礎。從不同的

8、角度監(jiān)控目標的位置估計，它以先期的節(jié)點自身定位為基礎。從不同的角度 出發(fā)，無線傳感網(wǎng)的定位方法可以進行如下分類。出發(fā)，無線傳感網(wǎng)的定位方法可以進行如下分類。 n（1）根據(jù)是否依靠測量距離，分為）根據(jù)是否依靠測量距離，分為基于測距的定位基于測距的定位和和不需要測距的定位。不需要測距的定位。 n（2）根據(jù)部署的場合不同，分為室內(nèi)定位和室外定位。）根據(jù)部署的場合不同，分為室內(nèi)定位和室外定位。 n（3）根據(jù)信息收集的方式，網(wǎng)絡收集傳感器數(shù)據(jù)用于節(jié)點定位被稱為被）根據(jù)信息收集的方式，網(wǎng)絡收集傳感器數(shù)據(jù)用于節(jié)點定位被稱為被 動定位，節(jié)點主動發(fā)出信息用于定位被稱為主動定位。動定位，節(jié)點主動發(fā)出信息用于定位被

9、稱為主動定位。 2基本術(shù)語基本術(shù)語 n（1）信標節(jié)點：指預先獲得位置坐標的節(jié)點，也被稱作錨點。其余節(jié)點被稱為非錨點。）信標節(jié)點：指預先獲得位置坐標的節(jié)點，也被稱作錨點。其余節(jié)點被稱為非錨點。 n（2）測距：指兩個相互通信的節(jié)點通過測量的方式來估計出彼此之間的距離或角度。）測距：指兩個相互通信的節(jié)點通過測量的方式來估計出彼此之間的距離或角度。 n（3）連接度：包括節(jié)點連接度和網(wǎng)絡連接度兩種含義。）連接度：包括節(jié)點連接度和網(wǎng)絡連接度兩種含義。 q節(jié)點連接度是指節(jié)點可探測發(fā)現(xiàn)的鄰居節(jié)點個數(shù)。 q網(wǎng)絡連接度是所有節(jié)點的鄰居節(jié)點數(shù)目的平均值，它反映了傳感網(wǎng)節(jié)點配置的密集程度。 n（4）鄰居節(jié)點：傳感節(jié)點

10、通信半徑以內(nèi)的所有其他節(jié)點，被稱為該節(jié)點的鄰居節(jié)點。）鄰居節(jié)點：傳感節(jié)點通信半徑以內(nèi)的所有其他節(jié)點，被稱為該節(jié)點的鄰居節(jié)點。 n（5）接收信號強度指示（）接收信號強度指示（Received signal Strength Indicator，RSSI）：節(jié)點接收到無）：節(jié)點接收到無 線信號的強度大小，被稱為接收信號的強度指示。線信號的強度大小，被稱為接收信號的強度指示。 n（6）到達角度（）到達角度（Angle of Arrival，AoA）：節(jié)點接收到的信號相對于自身軸線的角度，被）：節(jié)點接收到的信號相對于自身軸線的角度，被 稱為信號相對接收節(jié)點的到達角度。稱為信號相對接收節(jié)點的到達角度。

11、n（7）視線關(guān)系（）視線關(guān)系（Line of sight，LoS）:如果兩個節(jié)點之間沒有障礙物，能夠?qū)崿F(xiàn)直接通信，如果兩個節(jié)點之間沒有障礙物，能夠?qū)崿F(xiàn)直接通信， 則稱這兩個節(jié)點間存在視線關(guān)系。則稱這兩個節(jié)點間存在視線關(guān)系。 n（8）非視線關(guān)系（）非視線關(guān)系（None Line of sight，NLoS）：兩個節(jié)點之間存在障礙物，影響了它們）：兩個節(jié)點之間存在障礙物，影響了它們 直接的無線通信。直接的無線通信。 3定位性能的評價指標定位性能的評價指標 n（1）定位精度：）定位精度： q定位精度指提供的位置信息的精確程度，它分為相對精度和絕對精度。 n絕對精度指以長度為單位度量的精度。例如，GP

12、S的精度為110m，現(xiàn)在使用GPS導航系統(tǒng)的 精度約5m。一些商業(yè)的室內(nèi)定位系統(tǒng)提供30cm的精度，可以用于工業(yè)環(huán)境、物流倉儲等場合。 n相對精度通常以節(jié)點之間距離的百分比來定義。例如，若兩個節(jié)點之間距離是20m，定位精度為 2m，則相對定位精度為10。由于有些定位方法的絕對精度會隨著距離的變化而變化，因而使用 相對精度可以很好地表示精度指標。設節(jié)點的估計坐標與真實坐標在二維情況下的距離差值為， 則個未知位置節(jié)點的網(wǎng)絡平均定位誤差為。 n（2）覆蓋范圍：）覆蓋范圍： q覆蓋范圍和定位精度是一對矛盾性的指標。例如超聲波可以達到分米級精度，但是 它的覆蓋范圍只有10多米；Wi-Fi和藍牙的定位精度

13、為3米左右，覆蓋范圍可以達到 100米左右；GSM系統(tǒng)能覆蓋千米級的范圍，但是精度只能達到100米。由此可見， 覆蓋范圍越大，提供的精度就越低。提供大范圍內(nèi)的高精度通常是難以實現(xiàn)的。 3定位性能的評價指標定位性能的評價指標 n（3）刷新速度：）刷新速度： q刷新速度是指提供位置信息的頻率。例如，如果GPS每秒刷新1次，則這種頻率對 于車輛導航已經(jīng)足夠了，能讓人體驗到實時服務的感覺。對于移動的物體，如果位 置信息刷新較慢，就會出現(xiàn)嚴重的位置信息滯后，直觀上感覺已經(jīng)前進了很長距離， 提供的位置還是以前的位置。因此，刷新速度會影響定位系統(tǒng)實際工作提供的精度， 它還會影響位置控制者的現(xiàn)場操作。如果刷新

14、速度太低，可能會使得操作者無法實 施實時控制。 n（4）功耗：）功耗： q功耗作為傳感網(wǎng)設計的一項重要指標，對于定位這項服務功能，需要計算為此所消 耗的能量。采用的定位方法不同，功耗的差別會很大，主要原因是定位算法的復雜 度不同，需要為定位提供的計算和通信開銷方面存在數(shù)量上的差別，導致完成定位 服務的功耗有所不同。 n（5）代價：）代價： q定位系統(tǒng)或算法的代價可從幾個不同方面來評價。 n時間代價包括一個系統(tǒng)的安裝時間、配置時間、定位所需時間。 n空間代價包括一個定位系統(tǒng)或算法所需的基礎設施和網(wǎng)絡節(jié)點的數(shù)量、硬件尺寸等。 n資金代價則包括實現(xiàn)一種定位系統(tǒng)或算法的基礎設施、節(jié)點設備的總費用。返回

15、 基于距離的定位算法 n基于測距的定位技術(shù)是通過測量節(jié)點之間的距離，根據(jù)幾何關(guān)系計算基于測距的定位技術(shù)是通過測量節(jié)點之間的距離，根據(jù)幾何關(guān)系計算 出網(wǎng)絡節(jié)點的位置。解析幾何里有多種方法可以確定一個點的位置。出網(wǎng)絡節(jié)點的位置。解析幾何里有多種方法可以確定一個點的位置。 n比較常用的方法是比較常用的方法是多邊定位多邊定位和和角度定位角度定位。這里重點介紹通過距離測量。這里重點介紹通過距離測量 的方式，它可以用來計算傳感網(wǎng)中某一未知位置的節(jié)點坐標。的方式，它可以用來計算傳感網(wǎng)中某一未知位置的節(jié)點坐標。 測距方法 n1接收信號強度指示（接收信號強度指示（RSSI） n2到達時間（到達時間（ToA） n

16、3到達時間差（到達時間差（TDoA） n4到達角（到達角（AoA） 1接收信號強度指示（接收信號強度指示（RSSI） n基于基于RSSI定位算法，是通過測量發(fā)送功率與接收功率，計算傳定位算法，是通過測量發(fā)送功率與接收功率，計算傳 播損耗。播損耗。 n利用理論和經(jīng)驗模型，將傳播損耗轉(zhuǎn)化為發(fā)送器與接收器的距離。利用理論和經(jīng)驗模型，將傳播損耗轉(zhuǎn)化為發(fā)送器與接收器的距離。 n該方法易于實現(xiàn)，無需在節(jié)點上安裝輔助定位設備。當遇到非均該方法易于實現(xiàn)，無需在節(jié)點上安裝輔助定位設備。當遇到非均 勻傳播環(huán)境，有障礙物造成多徑反射或信號傳播模型過于粗糙時，勻傳播環(huán)境，有障礙物造成多徑反射或信號傳播模型過于粗糙時，

17、 RSSI測距精度和可靠性降低，有時測距誤差可達到測距精度和可靠性降低，有時測距誤差可達到50%。一般。一般 將將RSSI和其他測量方法綜合運用來進行定位。和其他測量方法綜合運用來進行定位。 2到達時間（到達時間（ToA） n這類方法通過測量傳輸時間來估算兩節(jié)點之間距離。精度較好。但由于這類方法通過測量傳輸時間來估算兩節(jié)點之間距離。精度較好。但由于 無線信號的傳輸速度快，時間測量上的很小誤差就會導致很大的誤差值，無線信號的傳輸速度快，時間測量上的很小誤差就會導致很大的誤差值， 所以要求傳感器節(jié)點有較強的計算能力。這兩種基于時間的測距方法適所以要求傳感器節(jié)點有較強的計算能力。這兩種基于時間的測距

18、方法適 用于多種信號，如射頻、聲學、紅外和超聲波信號等。用于多種信號，如射頻、聲學、紅外和超聲波信號等。 nToA機制是已知信號的傳播速度，根據(jù)信號的傳播時間來計算節(jié)點間的機制是已知信號的傳播速度，根據(jù)信號的傳播時間來計算節(jié)點間的 距離。如圖距離。如圖6-1所示為某于所示為某于ToA測距的簡單實現(xiàn)過程示例，采均偽噪聲序測距的簡單實現(xiàn)過程示例，采均偽噪聲序 列信號作為聲波信號，根據(jù)聲波的傳播時間來測量節(jié)點之間的距離。列信號作為聲波信號，根據(jù)聲波的傳播時間來測量節(jié)點之間的距離。 2到達時間（到達時間（ToA）(2) n假設兩個節(jié)點預先變現(xiàn)了時間同步，在發(fā)送節(jié)點發(fā)送偽噪聲序列假設兩個節(jié)點預先變現(xiàn)了時

19、間同步，在發(fā)送節(jié)點發(fā)送偽噪聲序列 信號的同時，無線傳輸模塊通過無線電同步消息通知接收節(jié)點偽信號的同時，無線傳輸模塊通過無線電同步消息通知接收節(jié)點偽 噪聲序列信號發(fā)送的時間，接收節(jié)點的麥克風模塊檢測到偽噪聲噪聲序列信號發(fā)送的時間，接收節(jié)點的麥克風模塊檢測到偽噪聲 序列信號后，根據(jù)聲波信號的傳播時間和速度來計算節(jié)點間的距序列信號后，根據(jù)聲波信號的傳播時間和速度來計算節(jié)點間的距 離。離。 n節(jié)點在計算出多個鄰近的信標節(jié)點后，利用多邊測量算法和極大節(jié)點在計算出多個鄰近的信標節(jié)點后，利用多邊測量算法和極大 似然估計算法算出自身的位置。似然估計算法算出自身的位置。 nToA采用的聲波信號進行到達時間測量。

20、由于聲波頻率低，速度采用的聲波信號進行到達時間測量。由于聲波頻率低，速度 低。對節(jié)點硬件的成本和復雜度的要求很低，但聲波的傳播速度低。對節(jié)點硬件的成本和復雜度的要求很低，但聲波的傳播速度 易受大氣條件的影響。易受大氣條件的影響。 nToA算法的定位精度高，但要求節(jié)點間保持精確的時間同步，對算法的定位精度高，但要求節(jié)點間保持精確的時間同步，對 傳感器節(jié)點的硬件和功耗提出了較高的要求。傳感器節(jié)點的硬件和功耗提出了較高的要求。 3到達時間差（到達時間差（TDoA） n在基于在基于TDoA的定位機制中，發(fā)射節(jié)點同時發(fā)射兩種不同傳播速度的無線信號，的定位機制中，發(fā)射節(jié)點同時發(fā)射兩種不同傳播速度的無線信號

21、， 接收節(jié)點根據(jù)兩種信號到達的時間差以及這兩種信號的傳播速度計算兩個節(jié)點之接收節(jié)點根據(jù)兩種信號到達的時間差以及這兩種信號的傳播速度計算兩個節(jié)點之 間的距離。間的距離。 n如圖如圖6-2所示，發(fā)射節(jié)點同時發(fā)射無線射頻信號和超聲波信號，接收節(jié)點記錄下這所示，發(fā)射節(jié)點同時發(fā)射無線射頻信號和超聲波信號，接收節(jié)點記錄下這 兩種信號的到達時間兩種信號的到達時間T1、T2，巳知無線射頻信號和超聲波的傳播速度為，巳知無線射頻信號和超聲波的傳播速度為c1、c2， 那么兩點之間的距離為那么兩點之間的距離為(T2-T1)S，其中，其中S=c1c2/(c2-c1)。 3到達時間差（到達時間差（TDoA）(2) n由于

22、無線射頻信號的傳播速度要遠大于超聲波的傳播速度，因而由于無線射頻信號的傳播速度要遠大于超聲波的傳播速度，因而 未知節(jié)點在收到無線射頻信號時，會同時打開超聲波信號接收機。未知節(jié)點在收到無線射頻信號時，會同時打開超聲波信號接收機。 根據(jù)兩種信號的到達時間間隔和各自的傳播速度，未知節(jié)點算出根據(jù)兩種信號的到達時間間隔和各自的傳播速度，未知節(jié)點算出 和該信標節(jié)點之間的距離，然后通過比較到各個鄰近信標節(jié)點的和該信標節(jié)點之間的距離，然后通過比較到各個鄰近信標節(jié)點的 距離，選擇出離自身最近的信標節(jié)點，從該信標節(jié)點廣播的信息距離，選擇出離自身最近的信標節(jié)點，從該信標節(jié)點廣播的信息 中取得自身的位置。中取得自身的

23、位置。 nTDoA技術(shù)對節(jié)點硬件的要求高，其對成本和功耗的要求使得該技技術(shù)對節(jié)點硬件的要求高，其對成本和功耗的要求使得該技 術(shù)對低成本、低功耗的傳感網(wǎng)設計提出了挑戰(zhàn)。當然術(shù)對低成本、低功耗的傳感網(wǎng)設計提出了挑戰(zhàn)。當然TDoA技術(shù)的技術(shù)的 測距誤差小，具有較高精度。測距誤差小，具有較高精度。 4到達角（到達角（AoA） n該方法通過配備特殊天線來估測其他節(jié)點發(fā)射的無線信號的到達角度。它的硬件要求較高，該方法通過配備特殊天線來估測其他節(jié)點發(fā)射的無線信號的到達角度。它的硬件要求較高， 每個節(jié)點要安裝昂貴的天線陣列和超聲波接收器。每個節(jié)點要安裝昂貴的天線陣列和超聲波接收器。 n在基于在基于AoA的定位

24、機制中，接收節(jié)點通過天線陣列或多個超聲波接收機，來感知發(fā)射節(jié)點信的定位機制中，接收節(jié)點通過天線陣列或多個超聲波接收機，來感知發(fā)射節(jié)點信 號的到達方向，計算接收節(jié)點和發(fā)射節(jié)點之間的相對方位和角度，再通過三角測量法計算節(jié)號的到達方向，計算接收節(jié)點和發(fā)射節(jié)點之間的相對方位和角度，再通過三角測量法計算節(jié) 點的位置。點的位置。 n如圖如圖6-3所示，接收節(jié)點通過麥克風陣列，探測發(fā)射節(jié)點信號的到達方向。所示，接收節(jié)點通過麥克風陣列，探測發(fā)射節(jié)點信號的到達方向。 nAoA定位不僅能夠確定節(jié)點的坐標，還能夠確定節(jié)點的方位信息。但是定位不僅能夠確定節(jié)點的坐標，還能夠確定節(jié)點的方位信息。但是AoA測距技術(shù)易受外測

25、距技術(shù)易受外 界環(huán)境影響，且需要額外硬件，因此它的硬件尺寸和功耗指標并不適用于大規(guī)模的傳感網(wǎng)。界環(huán)境影響，且需要額外硬件，因此它的硬件尺寸和功耗指標并不適用于大規(guī)模的傳感網(wǎng)。 節(jié)點定位計算方法 n在傳感器節(jié)點定位過程中，未知節(jié)點在獲得對于鄰近信標節(jié)點的距離，在傳感器節(jié)點定位過程中，未知節(jié)點在獲得對于鄰近信標節(jié)點的距離， 或獲得鄰近的信標節(jié)點與未知節(jié)點之間的相對角度后，通常使用下列或獲得鄰近的信標節(jié)點與未知節(jié)點之間的相對角度后，通常使用下列 方法計算自己的坐標。方法計算自己的坐標。 q（1）三邊測量法 q（2）三角測量法 q（3）極大似然估計法 （1）三邊測量法）三邊測量法 n三邊測量法（三邊測

26、量法（trilateration）如圖）如圖6-4所示，已知所示，已知A、B、C三個節(jié)點的三個節(jié)點的 坐標分別為坐標分別為(xa,ya)、(xb,yb)、(xc,yc)，以及它們到未知節(jié)點，以及它們到未知節(jié)點D的距的距 離分別為離分別為da、db、dc，假設節(jié)點，假設節(jié)點D的坐標為的坐標為(x,y)。那么存在下列公。那么存在下列公 式：式： ccc bbb aaa dyyxx dyyxx dyyxx 22 22 22 )()( )()( )()( 222222 222222 1 )(2)(2 )(2)(2 bccbcb accaca cbcb caca ddyyxx ddyyxx yyxx y

27、yxx y x 可以得到節(jié)點D的坐標為 （2）三角測量法）三角測量法 n三角測量法三角測量法(triangulation)原理如圖原理如圖6-5所示，已知所示，已知A、B、C三個節(jié)點的坐標三個節(jié)點的坐標 分別為分別為(xa,ya)、(xb,yb)、(xc,yc) ，節(jié)點，節(jié)點D相對于節(jié)點相對于節(jié)點A、B、C的角度分別為的角度分別為 ADBADB、 ADCADC 、 BDCBDC ，假設節(jié)點，假設節(jié)點D的坐標為的坐標為(x,y)。 n對于節(jié)點對于節(jié)點A、C和角和角ADCADC ，如果弧段，如果弧段AC在在ABC內(nèi)，那么能夠惟一確定一個內(nèi)，那么能夠惟一確定一個 圓，設圓心為圓，設圓心為O1(xo1

28、,yo1)，半徑為，半徑為r1，那么角，那么角= AO1C=2= AO1C=2-2 ADC-2 ADC， 并存在下列公式：并存在下列公式： cos22)()( )()( )()( 2 1 2 1 22 1 2 1 2 1 1 2 1 2 1 rryyxx ryyxx ryyxx caca bObO aOaO 由式（6.3）能夠確定圓心點的坐標和半徑。同理對A、B、 ADB和B、C、 BDC分別確定相應的圓心、半徑。最后利用三邊測量法，由三個圓心點及 其半徑確定D點坐標。 （3）極大似然估計法）極大似然估計法 n極大似然估計法極大似然估計法(maximum likelihood estimati

29、on，MLE)如圖如圖2.4所示，己知所示，己知1、 2、3等個節(jié)點的坐標分別為等個節(jié)點的坐標分別為(x1,y1)、(x2,y2)、(xn,yn)，它們到未知節(jié)點的，它們到未知節(jié)點的 距離分別為距離分別為d1、d2、dn，假設未知節(jié)點的坐標為，假設未知節(jié)點的坐標為(x,y)。 222 2 2 2 2 2 2 2 1 2 1 2 1 )()( )()( )()( nnn dyyxx dyyxx dyyxx 有公式： bAAAX TT1 )( 解方程得： 其中： )(2)(2 )(2)(2 11 11 nnnn nn yyxx yyxx A 2 1 222 1 22 1 2 1 222 1 22

30、1 nnnnnn nnn ddyyxx ddyyxx b y x X 返回 與距離無關(guān)的定位算法 n與距離無關(guān)的定位技術(shù)不需要直接測量距離和角度信息。它不是通過測量節(jié)點之的定位技術(shù)不需要直接測量距離和角度信息。它不是通過測量節(jié)點之 間的距離來定位的，而是僅根據(jù)間的距離來定位的，而是僅根據(jù)網(wǎng)絡的連通性網(wǎng)絡的連通性確定網(wǎng)絡中節(jié)點之間的確定網(wǎng)絡中節(jié)點之間的跳數(shù)跳數(shù)，同時，同時 根據(jù)已知位置的參考節(jié)點的坐標等信息估計出每一跳的大致距離，然后估計出節(jié)根據(jù)已知位置的參考節(jié)點的坐標等信息估計出每一跳的大致距離，然后估計出節(jié) 點在網(wǎng)絡中的位置。點在網(wǎng)絡中的位置。 n與距離無關(guān)的定位算法無須測量節(jié)點間的絕對距離

31、或方位，降低了對節(jié)點硬件的與距離無關(guān)的定位算法無須測量節(jié)點間的絕對距離或方位，降低了對節(jié)點硬件的 要求。要求。 n目前主要有兩類距離無關(guān)的定位方法：目前主要有兩類距離無關(guān)的定位方法： q一類是先對未知節(jié)點和信標節(jié)點之間的距離進行估計，然后利用多邊定位等方法完 成對其他節(jié)點的定位； q另一類是通過鄰居節(jié)點和信標節(jié)點來確定包含未知節(jié)點的區(qū)域，然后將這個區(qū)域的 質(zhì)心作為未知節(jié)點的坐標。 n距離無關(guān)的定位方法精度低，但能滿足大多數(shù)應用的要求。距離無關(guān)的定位方法精度低，但能滿足大多數(shù)應用的要求。 n距離無關(guān)的定位算法主要有質(zhì)心算法、距離無關(guān)的定位算法主要有質(zhì)心算法、DV-Hop算法、算法、Amorpho

32、us算法、算法、APIT算算 法等。法等。 1質(zhì)心算法質(zhì)心算法 n在計算幾何學里，多邊形的幾何中心被稱為質(zhì)心，多邊形頂點坐在計算幾何學里，多邊形的幾何中心被稱為質(zhì)心，多邊形頂點坐 標的平均值就是質(zhì)心節(jié)點的坐標。假設多邊形頂點位置的坐標向標的平均值就是質(zhì)心節(jié)點的坐標。假設多邊形頂點位置的坐標向 量表示為量表示為 ，則這個多邊形的質(zhì)心坐標計算方法如下。，則這個多邊形的質(zhì)心坐標計算方法如下。 T iii yxp),( n i i n i i y n x n yx 11 1 , 1 ),( 這種方法的計算與實現(xiàn)都非常簡單，可以根據(jù)網(wǎng)絡的連通性確定信標節(jié)點周 圍的信標參考節(jié)點，直接求解信標參考節(jié)點構(gòu)成的

33、多邊形的質(zhì)心。 在傳感網(wǎng)的質(zhì)心定位系統(tǒng)的實現(xiàn)中，信標節(jié)點周期性地向鄰近節(jié)點廣播分組 信息，該信息包含了信標節(jié)點的標識和位置。 在未知節(jié)點接收到來自不同信標節(jié)點的分組信息數(shù)量超過某一門限或在接收 了一定時間之后，就可以計算這些信標節(jié)點所組成的多邊形的質(zhì)心，并以此 確定自身位置。 質(zhì)心定位算法雖然實現(xiàn)簡單、通信開銷小，但僅能實現(xiàn)粗精度定位，并且需 要信標節(jié)點具有較高的密度，各信標節(jié)點部署的位置也對定位效果有影響。 2DV-Hop算法算法 n距離向量距離向量-跳數(shù)（跳數(shù)（distance vector-hop，DV-Hop）算法定位機制非常類）算法定位機制非常類 似于傳統(tǒng)網(wǎng)絡中的距離向量路由機制。似

34、于傳統(tǒng)網(wǎng)絡中的距離向量路由機制。 n在距離向量定位機制中，未知節(jié)點首先計算與信標節(jié)點的最小跳數(shù)，然在距離向量定位機制中，未知節(jié)點首先計算與信標節(jié)點的最小跳數(shù)，然 后估算平均跳數(shù)的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié)后估算平均跳數(shù)的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié) 點與信標節(jié)點之間的估計距離，再利用三邊測量法或極大似然估計法計點與信標節(jié)點之間的估計距離，再利用三邊測量法或極大似然估計法計 算未知節(jié)點的坐標。算未知節(jié)點的坐標。DV-Hop算法的定位過程分為以下三個階段：算法的定位過程分為以下三個階段： n（1）計算未知節(jié)點與信標節(jié)點的最小跳數(shù)）計算未知節(jié)點與信標節(jié)點的最小跳

35、數(shù) q信標節(jié)點向鄰居節(jié)點廣播自身的位置信息的分組，其中包括跳數(shù)字段，初 始化為0。接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數(shù)，忽略來自同一 個信標節(jié)點的最大跳數(shù)的分組。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點。 通過這種方法，網(wǎng)絡中的所有節(jié)點能夠記錄下到每個信標節(jié)點的最小跳數(shù)。 如圖6-7所示，信標節(jié)點A廣播的分組以近似于同心圓的方式在網(wǎng)絡中逐次 傳播，圖中的數(shù)字代表距離信標節(jié)點A的跳數(shù)。 圖6-7 信標節(jié)點廣播分組傳播過程圖示 n（2）計算未知節(jié)點與信標節(jié)點的實際跳數(shù)距離）計算未知節(jié)點與信標節(jié)點的實際跳數(shù)距離 q每個信標節(jié)點根據(jù)第一個階段記錄的其他信標節(jié)點的位置信息和相距跳數(shù)， 利用式 估算平均跳數(shù)

36、的實際平均距離值。 n （6.8） n n其中（其中（xi,yi)，(xj,yj)是信標節(jié)點是信標節(jié)點I,j的坐標，的坐標，hij是信標節(jié)點是信標節(jié)點I,j與之間的跳數(shù)。與之間的跳數(shù)。 n然后，信標節(jié)點將計算的每跳平均距離用帶有生存期字段的分組廣播到然后，信標節(jié)點將計算的每跳平均距離用帶有生存期字段的分組廣播到 網(wǎng)絡中，未知節(jié)點僅記錄接收到的每一跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。網(wǎng)絡中，未知節(jié)點僅記錄接收到的每一跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。 n這個策略確保了絕大多數(shù)節(jié)點從最近的信標節(jié)點接收每跳平均距離值。這個策略確保了絕大多數(shù)節(jié)點從最近的信標節(jié)點接收每跳平均距離值。 未知節(jié)點接收到平均值每跳距離

37、后，根據(jù)記錄的跳數(shù)，計算到每個信標未知節(jié)點接收到平均值每跳距離后，根據(jù)記錄的跳數(shù)，計算到每個信標 節(jié)點的跳段距離。節(jié)點的跳段距離。 ij j ij jiji i h yyxx 22 )()( HopSize i HopSizehops i D n（3）利用三邊測量法或極大似然估計法計算自身位置）利用三邊測量法或極大似然估計法計算自身位置 q未知節(jié)點利用第二階段中記錄的每個信標節(jié)點的跳段距離，利用三邊測量 法或極大似然估計法計算自身坐標。 q如圖6-8給出了DV-Hop算法示例。經(jīng)過第一階段和第二階段，能夠計算出 信標節(jié)點L1、L2、L3間的實際距離和跳數(shù)，那么信標節(jié)點L2計算的每跳 平均距離為

38、d=(40+75)/(2+5)=16.42m。假設未知節(jié)點A從L2獲得每跳平均 距離，則節(jié)點與三個信標節(jié)點之間的距離分別為：3d，2d，3d，最后利 用三邊測量法計算出節(jié)點的坐標。 3. DV-Distance算法算法 nDV-Distance算法類似于算法類似于DV-Hop算法，它們之間的區(qū)別就在于算法，它們之間的區(qū)別就在于 DV-Hop算法是通過節(jié)點的平均每跳距離和跳數(shù)算出節(jié)點間的距離，算法是通過節(jié)點的平均每跳距離和跳數(shù)算出節(jié)點間的距離， 而而DV-Distance算法是通過節(jié)點間使用射頻通信來測量出節(jié)點間算法是通過節(jié)點間使用射頻通信來測量出節(jié)點間 的距離，即利用的距離，即利用RSSI來測

39、量節(jié)點間的距離，然后再應用三角測量來測量節(jié)點間的距離，然后再應用三角測量 法計算出節(jié)點的位置。法計算出節(jié)點的位置。 n與與DV-Hop算法相比較，算法相比較，DV-Distance算法對傳感器節(jié)點的功能要算法對傳感器節(jié)點的功能要 求比較低，不要求節(jié)點能夠儲存網(wǎng)絡中各個節(jié)點的位置信息，同求比較低，不要求節(jié)點能夠儲存網(wǎng)絡中各個節(jié)點的位置信息，同 時還較大幅度地減少了節(jié)點間的通信量，也就降低了節(jié)點工作的時還較大幅度地減少了節(jié)點間的通信量，也就降低了節(jié)點工作的 能源消耗。不足之處在于，因為它直接測量節(jié)點間的距離，這樣能源消耗。不足之處在于，因為它直接測量節(jié)點間的距離，這樣 對距離的敏感性要求較高，尤其

40、對測距的誤差很敏感，因此算法對距離的敏感性要求較高，尤其對測距的誤差很敏感，因此算法 的誤差較大。的誤差較大。 4.APIT算法算法 n近似三角形內(nèi)點測試法（近似三角形內(nèi)點測試法（approximate point-in triangulation test，APIT），）， n首先確定多個包含未知節(jié)點的三角形區(qū)域，這些三角形區(qū)域的交集是一個多邊形，首先確定多個包含未知節(jié)點的三角形區(qū)域，這些三角形區(qū)域的交集是一個多邊形， 它確定了更小的包含未知節(jié)點的區(qū)域；然后計算這個多邊形區(qū)域的質(zhì)心，并將質(zhì)它確定了更小的包含未知節(jié)點的區(qū)域；然后計算這個多邊形區(qū)域的質(zhì)心，并將質(zhì) 心作為未知節(jié)點的位置。心作為未知

41、節(jié)點的位置。 n未知節(jié)點首先收集其鄰近信標節(jié)點的信息，然后從這些信標節(jié)點組成的集合中任未知節(jié)點首先收集其鄰近信標節(jié)點的信息，然后從這些信標節(jié)點組成的集合中任 意選取三個信標節(jié)點。假設集合中有個元素，那么共有種不同的選取方法，確定意選取三個信標節(jié)點。假設集合中有個元素，那么共有種不同的選取方法，確定 個不同的三角形，逐一測試未知節(jié)點是否位于每個三角形內(nèi)部，直到窮盡所有種個不同的三角形，逐一測試未知節(jié)點是否位于每個三角形內(nèi)部，直到窮盡所有種 組合或達到定位所需精度；最后計算包含目標節(jié)點所有三角形的重疊區(qū)域，將重組合或達到定位所需精度；最后計算包含目標節(jié)點所有三角形的重疊區(qū)域，將重 疊區(qū)域的質(zhì)心作為

42、未知節(jié)點的位置。如圖疊區(qū)域的質(zhì)心作為未知節(jié)點的位置。如圖6-9所示，陰影部分區(qū)域是包含未知節(jié)點所示，陰影部分區(qū)域是包含未知節(jié)點 的所有三角形的重疊區(qū)域，黑點指示的質(zhì)心位置作為未知節(jié)點的位置。的所有三角形的重疊區(qū)域，黑點指示的質(zhì)心位置作為未知節(jié)點的位置。 4.APIT算法算法(2) nAPIT算法的理論基礎是最佳三角形內(nèi)點測試法（算法的理論基礎是最佳三角形內(nèi)點測試法（perfect point-in triangulation test， PIT），），PIT測試原理如圖測試原理如圖6-10所示，假如存在一個方間。節(jié)點沿著這個方向移動會同所示，假如存在一個方間。節(jié)點沿著這個方向移動會同 時遠離或

43、接近頂點時遠離或接近頂點A、B、C，那么節(jié)點，那么節(jié)點M位于位于ABC外；否則，節(jié)點外；否則，節(jié)點M位三角形位三角形ABC內(nèi)。內(nèi)。 n在傳感網(wǎng)中，信標節(jié)點通常是靜止的。為了在靜態(tài)的環(huán)境中觀察三角形內(nèi)點測試，提在傳感網(wǎng)中，信標節(jié)點通常是靜止的。為了在靜態(tài)的環(huán)境中觀察三角形內(nèi)點測試，提 出了近似的三角形內(nèi)點測試法：假如在節(jié)點的所有鄰居節(jié)點里，相對于節(jié)點沒有同時出了近似的三角形內(nèi)點測試法：假如在節(jié)點的所有鄰居節(jié)點里，相對于節(jié)點沒有同時 遠離或靠近三個信標節(jié)點遠離或靠近三個信標節(jié)點A、B、C，那么節(jié)點，那么節(jié)點M在三角形在三角形ABC內(nèi)；否則，節(jié)點內(nèi)；否則，節(jié)點M在三在三 角形角形ABC外。外。 n近似的三角形內(nèi)點測試利用網(wǎng)絡中相對較高的節(jié)點密度來模擬節(jié)點移動，利用無線信近似的三角形內(nèi)點測試利用網(wǎng)絡中相對較高的節(jié)點密度來模擬節(jié)點移動，利用無線信 號的傳播特性來判斷是否遠離或靠