第2講 定位技術(shù)

1、1WSN: Theory and Applications一、WSN概述二、定位技術(shù)三、目標(biāo)跟蹤四、拓?fù)淇刂莆濉r(shí)間同步 六、路由協(xié)議七、安全技術(shù)八、課程考核本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 基于測(cè)距的定位技術(shù) 無(wú)需測(cè)距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 1. WSN定位技術(shù)的概述基本含義重要意義性能指標(biāo)算法特點(diǎn)位置計(jì)算算法分類1. WSN定位技術(shù)的概述-基本含義 定位就是確定位置。定位的兩種意義：一種是確定自己在系統(tǒng)中的位置；一種是確定目標(biāo)在系統(tǒng)中的位置。位置信息的類型：物理位置指目標(biāo)在特定坐標(biāo)系下的位置數(shù)值，表示目標(biāo)的相對(duì)或者絕對(duì)位置；符號(hào)位置指在目標(biāo)與一個(gè)基站或者多個(gè)基站接近程度的信

2、息，表示目標(biāo)與基站之間的連通關(guān)系，提供目標(biāo)大致的所在范圍。1. WSN定位技術(shù)的概述-重要意義 定位機(jī)制是定位機(jī)制是WSN的基本機(jī)制的基本機(jī)制 沒(méi)有位置信息的檢測(cè)消息是沒(méi)有意義的； 應(yīng)用：戰(zhàn)場(chǎng)偵查、目標(biāo)跟蹤、入侵檢測(cè)、災(zāi)難預(yù)報(bào)等。 節(jié)點(diǎn)定位是基本的定位機(jī)制節(jié)點(diǎn)定位是基本的定位機(jī)制 隨機(jī)部署的網(wǎng)絡(luò)，需要確定節(jié)點(diǎn)位置； 只有節(jié)點(diǎn)定位以后，才能確定節(jié)點(diǎn)檢測(cè)事件的位置。1. WSN定位技術(shù)概述-性能指標(biāo) 最重要的指標(biāo)，指定位系統(tǒng)提供的位置信息的精確程度。 絕對(duì)精度，指以長(zhǎng)度為單位度量的精度；相對(duì)精度，通常以節(jié)點(diǎn)之間距離的百分比來(lái)定義。覆蓋范圍是另一個(gè)重要指標(biāo)，它和精度是一對(duì)矛盾。1. WSN定位技術(shù)的

3、概述-算法特點(diǎn) 自組織性：節(jié)點(diǎn)隨機(jī)分布，不能依靠全局的基礎(chǔ)設(shè)施協(xié)助定位； 健 壯 性：節(jié)點(diǎn)測(cè)量數(shù)據(jù)時(shí)有誤差，算法需具有良好的容錯(cuò)性； 能量高效：算法計(jì)算復(fù)雜度要小，減少通信開(kāi)銷，延長(zhǎng)網(wǎng)絡(luò)的生命周期； 分布計(jì)算：節(jié)點(diǎn)計(jì)算自身的位置，不能將信息集中到某個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算。 已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)，以及它們到節(jié)點(diǎn)D的距離，確定節(jié)點(diǎn)D的坐標(biāo)。三邊測(cè)量算法1. WSN定位技術(shù)的概述-節(jié)點(diǎn)位置計(jì)算方法1. WSN定位技術(shù)的概述-節(jié)點(diǎn)位置計(jì)算方法 已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)，節(jié)點(diǎn)D相對(duì)于節(jié)點(diǎn)A、B、C的角度，確定節(jié)點(diǎn)D的坐標(biāo)； 轉(zhuǎn)換為三邊測(cè)量法。三角測(cè)量算法1. WSN定位技術(shù)的概述-節(jié)點(diǎn)位置計(jì)算方法

4、知1、2、3等n個(gè)節(jié)點(diǎn)的坐標(biāo)，及它們到節(jié)點(diǎn)D到距離，確定節(jié)點(diǎn)D的坐標(biāo)； 最小均方差估計(jì)算法。極大似然估計(jì)法1. WSN定位技術(shù)的概述-定位算法分類（1） 根據(jù)定位過(guò)程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，把定位算法分為： 基于距離的（range-based）定位 利用測(cè)量節(jié)點(diǎn)間實(shí)際距離或方位計(jì)算未知節(jié)點(diǎn)位置； 距離無(wú)關(guān)的（range-free）定位 利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算未知節(jié)點(diǎn)位置 。1. WSN定位技術(shù)的概述-定位算法分類（2） 根據(jù)定位過(guò)程中節(jié)點(diǎn)定位先后次序的不同，把定位算法分為： 遞增式的（Incremental）定位 信標(biāo)節(jié)點(diǎn)附近的節(jié)點(diǎn)首先開(kāi)始定位，依次向外延伸，各節(jié)點(diǎn)逐次進(jìn)行定位 ； 并發(fā)

5、式的（Concurrent）定位 所有的節(jié)點(diǎn)同時(shí)進(jìn)行位置計(jì)算 。1. WSN定位技術(shù)的概述-定位算法分類（3） 根據(jù)定位過(guò)程中是否使用信標(biāo)節(jié)點(diǎn)的位置信息 ，把定位算法分為： 基于信標(biāo)節(jié)點(diǎn)（beacon-based）定位 以信標(biāo)節(jié)點(diǎn)作為定位中的參考點(diǎn)，各節(jié)點(diǎn)定位后產(chǎn)生整體絕對(duì)坐標(biāo)系統(tǒng) ； 無(wú)信標(biāo)節(jié)點(diǎn)的(beacon-free)定位 各節(jié)點(diǎn)先以自身作為參考點(diǎn)，將鄰近節(jié)點(diǎn)納入自己定義的坐標(biāo)系中，相鄰的坐標(biāo)系統(tǒng)依次轉(zhuǎn)換合并，最后產(chǎn)生整體相對(duì)坐標(biāo)系統(tǒng) 。本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 基于測(cè)距的定位技術(shù) 無(wú)需測(cè)距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 2. 基于測(cè)距的定位技術(shù) 基本思想：通過(guò)測(cè)量相鄰節(jié)

6、點(diǎn)間的實(shí)際距離或方位進(jìn)行定位。 三個(gè)階段： 測(cè)距階段：未知節(jié)點(diǎn)首先測(cè)量到鄰居節(jié)點(diǎn)的距離或角度，然后進(jìn)一步計(jì)算到鄰近信標(biāo)節(jié)點(diǎn)的距離或方位； 定位階段：未知節(jié)點(diǎn)在計(jì)算出到達(dá)三個(gè)或三個(gè)以上信標(biāo)節(jié)點(diǎn)的距離或角度后，利用三邊測(cè)量法、三角測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)； 修正階段：對(duì)求得的節(jié)點(diǎn)的坐標(biāo)進(jìn)行求精，提高定位精度，減少誤差。2. 基于測(cè)距的定位技術(shù) 基于信號(hào)傳播時(shí)間的定位（TOA）基于信號(hào)傳播時(shí)間差定位（TDOA）基于接收信號(hào)強(qiáng)度的定位（RSSI） 基于接收信號(hào)角度的定位 (AOA) 2. 基于測(cè)距的定位技術(shù)-TOA 發(fā)射機(jī)接收機(jī)T0T1T2T33021()()2TTTT Vd 基本思想

7、： 已知信號(hào)的傳播速度，根據(jù)信號(hào)的傳播時(shí)間來(lái)計(jì)算節(jié)點(diǎn)間的距離，然后利用三邊或極大似然估計(jì)法等計(jì)算出節(jié)點(diǎn)的位置。2. 基于測(cè)距的定位技術(shù)-TOA 定位過(guò)程： 發(fā)送節(jié)點(diǎn)的揚(yáng)聲器模塊在發(fā)送偽噪聲序列信號(hào)的同時(shí)，無(wú)線電模塊通過(guò)無(wú)線電同步消息通知接收節(jié)點(diǎn)偽噪聲序列信號(hào)發(fā)送的時(shí)間，接收節(jié)點(diǎn)的麥克風(fēng)模塊在檢測(cè)到偽噪聲序列信號(hào)后，根據(jù)傳播時(shí)間和速度計(jì)算發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離；利用三邊測(cè)量算法或極大似然估計(jì)算法計(jì)算出自身位置；2. 基于測(cè)距的定位技術(shù)-TDOA122112()*c cdTTcc 基本思想： 發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種不同傳播速度的無(wú)線信號(hào)，接收節(jié)點(diǎn)根據(jù)兩種信號(hào)到達(dá)的時(shí)間差以及已知這兩種信號(hào)的傳播

8、速度，計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離，然后利用三邊或極大似然估計(jì)法等計(jì)算出節(jié)點(diǎn)的位置。2. 基于測(cè)距的定位技術(shù)- RSSI,0,0( )() 10 logr dBr dBdBdPdPdXd 基本思想：通過(guò)信號(hào)在傳播中的衰減來(lái)估計(jì)節(jié)點(diǎn)之間的距離； 根據(jù)信道模型求解距離：2. 基于測(cè)距的定位技術(shù)-AOA 基本思想： 接收節(jié)點(diǎn)通過(guò)天線陣列或多個(gè)超聲波接收機(jī)感知發(fā)射節(jié)點(diǎn)信號(hào)的到達(dá)方向，計(jì)算接收節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)之間的相對(duì)方位或角度，再通過(guò)三角測(cè)量法計(jì)算出節(jié)點(diǎn)的位置 。2. 基于測(cè)距的定位技術(shù)-AOA 第一步：相鄰節(jié)點(diǎn)之間方位角的測(cè)定 節(jié)點(diǎn)A的兩個(gè)接收機(jī)R1、R2間距離是L，接收機(jī)連線中點(diǎn)的位置代表節(jié)點(diǎn)A位置；將兩

9、個(gè)接收機(jī)連線的中垂線作為節(jié)點(diǎn)A的軸線，作為確定鄰居節(jié)點(diǎn)方位角度基準(zhǔn)線 ；2. 基于測(cè)距的定位技術(shù)-AOA 第二步：相對(duì)信標(biāo)節(jié)點(diǎn)的方位角測(cè)量 目標(biāo)：計(jì)算與信標(biāo)節(jié)點(diǎn)不相鄰的未知節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)之間的方位； L節(jié)點(diǎn)是信標(biāo)節(jié)點(diǎn)，A、B、C節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)； ABC、LBC的內(nèi)部角度已經(jīng)計(jì)算，從而能夠計(jì)算出四邊形ACLB的角度信息，進(jìn)而計(jì)算出信標(biāo)節(jié)點(diǎn)L相對(duì)于節(jié)點(diǎn)A的方位 ；2. 基于測(cè)距的定位技術(shù)-AOA 第三步：利用方位信息計(jì)算節(jié)點(diǎn)的位置 從n個(gè)信標(biāo)節(jié)點(diǎn)中任選三個(gè)信標(biāo)節(jié)點(diǎn)A、B、C ；利用三角測(cè)量算法或極大似然估計(jì)算法計(jì)算節(jié)點(diǎn)D坐標(biāo) 。本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 基于測(cè)距的定位技術(shù) 無(wú)需測(cè)

10、距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 3. 無(wú)需測(cè)距的定位技術(shù)質(zhì)心定位算法 DV-Hop算法 APIT算法 不定形定位算法 3. 無(wú)需測(cè)距的定位技術(shù)-質(zhì)心定位算法 多邊形的幾何中心，稱為質(zhì)心，多邊形頂點(diǎn)坐標(biāo)的平均值就是質(zhì)心節(jié)點(diǎn)的坐標(biāo)。 質(zhì)心定位算法首先確定包含未知節(jié)點(diǎn)的區(qū)域，計(jì)算這個(gè)區(qū)域的質(zhì)心，并將其作為未知節(jié)點(diǎn)的位置。3. 無(wú)需測(cè)距的定位技術(shù)-質(zhì)心定位算法 基本過(guò)程： 信標(biāo)節(jié)點(diǎn)周期性向鄰近節(jié)點(diǎn)廣播信標(biāo)分組，信標(biāo)分組中包含信標(biāo)節(jié)點(diǎn)的標(biāo)識(shí)號(hào)和位置信息； 當(dāng)未知節(jié)點(diǎn)接收到來(lái)自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)分組數(shù)量超過(guò)某一個(gè)門限k或接收一定時(shí)間后，就確定自身位置為這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心。3. 無(wú)需測(cè)距的

11、定位技術(shù)- DV-Hop算法 基本思想： 首先：計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)； 然后：估算平均每跳的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離； 最后：利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。3. 無(wú)需測(cè)距的定位技術(shù)- DV-Hop算法 計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù) 信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組，其中包括跳數(shù)字段，初始化為0； 接收節(jié)點(diǎn)記錄具有到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來(lái)自同一個(gè)信標(biāo)節(jié)點(diǎn)的較大跳數(shù)的分組。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)； 網(wǎng)絡(luò)中所有節(jié)點(diǎn)能夠記錄下到每個(gè)信標(biāo)節(jié)點(diǎn)最小跳數(shù)3. 無(wú)需測(cè)距的定位技術(shù)- DV-H

12、op算法 計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離 每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)記錄的其它信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，估算平均每跳的實(shí)際距離 ； 然后，信標(biāo)節(jié)點(diǎn)將計(jì)算的每跳平均距離用帶有生存期字段的分組廣播至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的第一個(gè)每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn) ； 未知節(jié)點(diǎn)接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，計(jì)算到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離；3. 無(wú)需測(cè)距的定位技術(shù)- DV-Hop算法 利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身位置 未知節(jié)點(diǎn)利用第二階段中記錄的到各個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離，利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)3. 無(wú)需測(cè)距的定位技術(shù)- DV-Hop算法 例子 信標(biāo)節(jié)點(diǎn)L2計(jì)算的每

13、跳平均距離為(40+75)/(2+5) A從L2獲得每跳平均距離，則節(jié)點(diǎn)A與三個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為L(zhǎng)1：316.42，L2：216.42，L3：316.42； L3AL1L23. 無(wú)需測(cè)距的定位技術(shù)- APIT算法 近似三角形內(nèi)點(diǎn)測(cè)試法（APIT, Approximate Point-In-Triangulation test）找到若干個(gè)由參考節(jié)點(diǎn)構(gòu)成的三角形，則節(jié)點(diǎn)必然在這些三角形的交集內(nèi)。使用這個(gè)交集的重心估計(jì)節(jié)點(diǎn)的位置。 APIT算法分四步：（1）信標(biāo)交換，（2）三角形內(nèi)點(diǎn)測(cè)試（PIT, Point-In-Triangulation testing），（3） 交集運(yùn)算計(jì)算三角形的重

14、合區(qū)域，（4）重心（COG, Center of Gravity）計(jì)算求節(jié)點(diǎn)的位置。 3. 無(wú)需測(cè)距的定位技術(shù)-APIT算法 基本過(guò)程 未知節(jié)點(diǎn)首先收集其鄰近信標(biāo)節(jié)點(diǎn)的位置信息； 從這些信標(biāo)節(jié)點(diǎn)組成的集合中任意選取三個(gè)節(jié)點(diǎn)，假設(shè)集合中有n個(gè)元素，那么共有Cn3種不同選取方法，確定Cn3個(gè)不同三角形，逐一測(cè)試未知節(jié)點(diǎn)是否位于每個(gè)三角形內(nèi)部，直到窮盡所有Cn3種組合或達(dá)到定位所需精度； 計(jì)算包含目標(biāo)節(jié)點(diǎn)所有三角形的重疊區(qū)域，并求質(zhì)心；3. 無(wú)需測(cè)距的定位技術(shù)- APIT算法 PIT：最佳三角形內(nèi)點(diǎn)測(cè)試法 PIT原理 假如存在一個(gè)方向，節(jié)點(diǎn)M沿著這個(gè)方向移動(dòng)會(huì)同時(shí)遠(yuǎn)離或接近頂點(diǎn)A、B、C，那么節(jié)點(diǎn)M

15、位于ABC外；否則，節(jié)點(diǎn)M位于ABC內(nèi)。3. 無(wú)需測(cè)距的定位技術(shù)-APIT算法 收集信息 未知節(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)的信息 ； APIT 測(cè)試 測(cè)試未知節(jié)點(diǎn)是否在不同信標(biāo)節(jié)點(diǎn)組合成三角形內(nèi)部 ； 計(jì)算重疊區(qū)域 統(tǒng)計(jì)包含未知節(jié)點(diǎn)三角形，計(jì)算所有三角形的重疊區(qū)域； 計(jì)算未知節(jié)點(diǎn)位置 計(jì)算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點(diǎn)的位置3. 無(wú)需測(cè)距的定位技術(shù)-不定形定位算法 在不定形計(jì)算機(jī)（Amorphous Computer）上實(shí)現(xiàn)的定位算法。 不定形計(jì)算機(jī)是一種并行計(jì)算結(jié)構(gòu)，和智能群（蟻群、鳥(niǎo)群、粒子群等）很相似。本質(zhì)上，不定

16、形算法是DV-Hop算法的增強(qiáng)，引入了多參考點(diǎn)測(cè)量進(jìn)行估計(jì)求精的步驟。兩個(gè)重要的參數(shù)修正：不定形算法通過(guò)平滑（smoothing）修正節(jié)點(diǎn)到參考節(jié)點(diǎn)的梯度跳數(shù)。采用通信半徑作為每跳距離，使得節(jié)點(diǎn)到參考節(jié)點(diǎn)的最終估計(jì)距離偏大。不定形算法采用下面的公式來(lái)修正每跳距離： 本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 基于測(cè)距的定位技術(shù) 無(wú)需測(cè)距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 4.一篇文獻(xiàn)-大家都在關(guān)注什么？4.一篇文獻(xiàn)-科技論文創(chuàng)作的方法老方法研究老問(wèn)題沒(méi)有創(chuàng)新新方法研究老問(wèn)題說(shuō)明新方法的優(yōu)越性老方法研究新問(wèn)題說(shuō)明新問(wèn)題的必要性新方法研究新問(wèn)題很大創(chuàng)新提取凝練出新概念最大創(chuàng)新4.一篇文獻(xiàn)標(biāo)題：簡(jiǎn)明扼要標(biāo)題：簡(jiǎn)明扼要 編輯：審稿周期編輯：審稿周期4.一篇文獻(xiàn)研究什么問(wèn)題研究什么問(wèn)題Consider 使用什么方法、得到什么結(jié)果使用什么方法、得到什么結(jié)果First, Then, By applying 仿真驗(yàn)證理論仿真驗(yàn)證理論Simulations 關(guān)鍵詞：研究對(duì)象、研究方法關(guān)鍵詞：研究對(duì)象、研究方法