第3課 定位技術(shù)

1、1WSN: Theory and Applications一、I o T概述二、WSN概述三、路由協(xié)議四、拓?fù)淇刂莆?、定位技術(shù)六、目標(biāo)跟蹤七、時間同步八、信息融合 九、安全技術(shù)2第三課、定位技術(shù)物聯(lián)網(wǎng)工程學(xué)院吳治海Email: Phoneddress:C4232011-9-22本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 定位算法的幾種分類基于測距的定位技術(shù) 無需測距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 1. WSN定位技術(shù)的概述-基本含義 定位就是確定位置。定位的兩種意義：一種是確定自己在系統(tǒng)中的位置；一種是確定目標(biāo)在系統(tǒng)中的位置。位置信息的類型：物理位置指目標(biāo)在特定坐標(biāo)系下

2、的位置數(shù)值，表示目標(biāo)的相對或者絕對位置；符號位置指在目標(biāo)與一個基站或者多個基站接近程度的信息，表示目標(biāo)與基站之間的連通關(guān)系，提供目標(biāo)大致的所在范圍。1. WSN定位技術(shù)的概述-基本含義 定位機(jī)制是定位機(jī)制是WSN的基本機(jī)制的基本機(jī)制 沒有位置信息的檢測消息是沒有意義的； 應(yīng)用：戰(zhàn)場偵查、目標(biāo)跟蹤、入侵檢測、災(zāi)難預(yù)報等。 節(jié)點(diǎn)定位是基本的定位機(jī)制節(jié)點(diǎn)定位是基本的定位機(jī)制 隨機(jī)部署的網(wǎng)絡(luò)，需要確定節(jié)點(diǎn)位置； 只有節(jié)點(diǎn)定位以后，才能確定節(jié)點(diǎn)檢測事件的位置。1. WSN定位技術(shù)概述-技術(shù)指標(biāo) 最重要的指標(biāo)，指定位系統(tǒng)提供的位置信息的精確程度。 絕對精度指以長度為單位度量的精度；相對精度，通常以節(jié)點(diǎn)之間

3、距離的百分比來定義。覆蓋范圍是另一個重要指標(biāo)，它和精度是一對矛盾。刷新速度是提供位置信息的頻率。比如GPS每秒鐘刷新1次。 精度覆蓋范圍超聲波分米級十多米Wi-Fi和藍(lán)牙3米100米GSMC系統(tǒng)100米公里級1. WSN定位技術(shù)的概述-算法特點(diǎn) 自組織性：節(jié)點(diǎn)隨機(jī)分布，不能依靠全局的基礎(chǔ)設(shè)施協(xié)助定位； 健壯性：節(jié)點(diǎn)測量數(shù)據(jù)時有誤差，算法需具有良好的容錯性； 能量高效：算法計算復(fù)雜度要小，減少通信開銷，延長網(wǎng)絡(luò)的生命周期； 分布計算：節(jié)點(diǎn)計算自身的位置，不能將信息集中到某個節(jié)點(diǎn)進(jìn)行計算。本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 定位算法的幾種分類基于測距的定位技術(shù) 無需測距的定位技術(shù) 一篇WSN定

4、位的文獻(xiàn) 2.定位算法的幾種分類節(jié)點(diǎn)位置計算方法定位算法分類（1）定位算法分類（2）定位算法分類（3）2.定位算法的幾種分類：節(jié)點(diǎn)位置計算方法 已知A、B、C三個節(jié)點(diǎn)的坐標(biāo)，以及它們到節(jié)點(diǎn)D的距離，確定節(jié)點(diǎn)D的坐標(biāo)。三邊測量算法2.定位算法的幾種分類：節(jié)點(diǎn)位置計算方法 已知A、B、C三個節(jié)點(diǎn)的坐標(biāo)，節(jié)點(diǎn)D相對于節(jié)點(diǎn)A、B、C的角度，確定節(jié)點(diǎn)D的坐標(biāo)； 轉(zhuǎn)換為三邊測量法。三角測量算法2.定位算法的幾種分類：節(jié)點(diǎn)位置計算方法 知1、2、3等n個節(jié)點(diǎn)的坐標(biāo)，及它們到節(jié)點(diǎn)D到距離，確定節(jié)點(diǎn)D的坐標(biāo)； 最小均方差估計算法。極大似然估計法2.定位算法的幾種分類（1） 根據(jù)定位過程中是否測量實(shí)際節(jié)點(diǎn)間的距離

5、，把定位算法分為： 基于距離的（range-based）定位 利用測量節(jié)點(diǎn)間實(shí)際距離或方位計算未知節(jié)點(diǎn)位置； 距離無關(guān)的（range-free）定位 利用節(jié)點(diǎn)間的估計距離計算未知節(jié)點(diǎn)位置 。2.定位算法的幾種分類（2） 根據(jù)定位過程中節(jié)點(diǎn)定位先后次序的不同，把定位算法分為： 遞增式的（Incremental）定位 信標(biāo)節(jié)點(diǎn)附近的節(jié)點(diǎn)首先開始定位，依次向外延伸，各節(jié)點(diǎn)逐次進(jìn)行定位 ； 并發(fā)式的（Concurrent）定位 所有的節(jié)點(diǎn)同時進(jìn)行位置計算 。2.定位算法的幾種分類（3） 根據(jù)定位過程中是否使用信標(biāo)節(jié)點(diǎn)的位置信息 ，把定位算法分為： 基于信標(biāo)節(jié)點(diǎn)（beacon-based）定位 以信標(biāo)節(jié)

6、點(diǎn)作為定位中的參考點(diǎn)，各節(jié)點(diǎn)定位后產(chǎn)生整體絕對坐標(biāo)系統(tǒng) ； 無信標(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)生整體相對坐標(biāo)系統(tǒng) 。本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 定位算法的幾種分類基于測距的定位技術(shù) 無需測距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 3. 基于測距的定位技術(shù) 基本思想：通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位進(jìn)行定位。 三個階段： 測距階段：未知節(jié)點(diǎn)首先測量到鄰居節(jié)點(diǎn)的距離或角度，然后進(jìn)一步計算到鄰近信標(biāo)節(jié)點(diǎn)的距離或方位； 定位階段：未知節(jié)點(diǎn)在計算出到達(dá)三個或三個以上信標(biāo)節(jié)點(diǎn)的距離或角度后，利用

7、三邊測量法、三角測量法或極大似然估計法計算未知節(jié)點(diǎn)的坐標(biāo)； 修正階段：對求得的節(jié)點(diǎn)的坐標(biāo)進(jìn)行求精，提高定位精度，減少誤差。3. 基于測距的定位技術(shù) 基于信號傳播時間的定位（TOA）基于信號傳播時間差定位（TDOA）基于接收信號強(qiáng)度的定位（RSSI） 基于接收信號角度的定位 (AOA) 3. 基于測距的定位技術(shù)-TOA 發(fā)射機(jī)接收機(jī)T0T1T2T32*)()(1203VTTTTd 基本思想： 已知信號的傳播速度，根據(jù)信號的傳播時間來計算節(jié)點(diǎn)間的距離，然后利用三邊或極大似然估計法等計算出節(jié)點(diǎn)的位置。3. 基于測距的定位技術(shù)-TOA 定位過程： 發(fā)送節(jié)點(diǎn)的揚(yáng)聲器模塊在發(fā)送偽噪聲序列信號的同時，無線電

8、模塊通過無線電同步消息通知接收節(jié)點(diǎn)偽噪聲序列信號發(fā)送的時間，接收節(jié)點(diǎn)的麥克風(fēng)模塊在檢測到偽噪聲序列信號后，根據(jù)傳播時間和速度計算發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離；利用三邊測量算法或極大似然估計算法計算出自身位置；3. 基于測距的定位技術(shù)-TDOA122112()*c cdTTcc 基本思想： 發(fā)射節(jié)點(diǎn)同時發(fā)射兩種不同傳播速度的無線信號，接收節(jié)點(diǎn)根據(jù)兩種信號到達(dá)的時間差以及已知這兩種信號的傳播速度，計算兩個節(jié)點(diǎn)之間的距離，然后利用三邊或極大似然估計法等計算出節(jié)點(diǎn)的位置。3. 基于測距的定位技術(shù)- RSSI,0,0( )() 10 logr dBr dBdBdPdPdXd 基本思想：通過信號在傳播中的

9、衰減來估計節(jié)點(diǎn)之間的距離； 根據(jù)信道模型求解距離：3. 基于測距的定位技術(shù)-AOA 基本思想： 接收節(jié)點(diǎn)通過天線陣列或多個超聲波接收機(jī)感知發(fā)射節(jié)點(diǎn)信號的到達(dá)方向，計算接收節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)之間的相對方位或角度，再通過三角測量法計算出節(jié)點(diǎn)的位置 。3. 基于測距的定位技術(shù)-AOA 第一步：相鄰節(jié)點(diǎn)之間方位角的測定 節(jié)點(diǎn)A的兩個接收機(jī)R1、R2間距離是L，接收機(jī)連線中點(diǎn)的位置代表節(jié)點(diǎn)A位置；將兩個接收機(jī)連線的中垂線作為節(jié)點(diǎn)A的軸線，作為確定鄰居節(jié)點(diǎn)方位角度基準(zhǔn)線 ；3. 基于測距的定位技術(shù)-AOA 第二步：相對信標(biāo)節(jié)點(diǎn)的方位角測量 目標(biāo)：計算與信標(biāo)節(jié)點(diǎn)不相鄰的未知節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)之間的方位； L節(jié)點(diǎn)是

10、信標(biāo)節(jié)點(diǎn)，A、B、C節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)； ABC、LBC的內(nèi)部角度已經(jīng)計算，從而能夠計算出四邊形ACLB的角度信息，進(jìn)而計算出信標(biāo)節(jié)點(diǎn)L相對于節(jié)點(diǎn)A的方位 ；3. 基于測距的定位技術(shù)-AOA 第三步：利用方位信息計算節(jié)點(diǎn)的位置 從n個信標(biāo)節(jié)點(diǎn)中任選三個信標(biāo)節(jié)點(diǎn)A、B、C ；利用三角測量算法或極大似然估計算法計算節(jié)點(diǎn)D坐標(biāo) 。本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 定位算法的幾種分類基于測距的定位技術(shù) 無需測距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 4. 無需測距的定位技術(shù)質(zhì)心定位算法 DV-Hop算法 APIT算法 不定形定位算法 4. 無需測距的定位技術(shù)-質(zhì)心定位算法 多邊形的幾何中心，稱為質(zhì)心，多

11、邊形頂點(diǎn)坐標(biāo)的平均值就是質(zhì)心節(jié)點(diǎn)的坐標(biāo)。 質(zhì)心定位算法首先確定包含未知節(jié)點(diǎn)的區(qū)域，計算這個區(qū)域的質(zhì)心，并將其作為未知節(jié)點(diǎn)的位置。4. 無需測距的定位技術(shù)-質(zhì)心定位算法 基本過程： 信標(biāo)節(jié)點(diǎn)周期性向鄰近節(jié)點(diǎn)廣播信標(biāo)分組，信標(biāo)分組中包含信標(biāo)節(jié)點(diǎn)的標(biāo)識號和位置信息； 當(dāng)未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)分組數(shù)量超過某一個門限k或接收一定時間后，就確定自身位置為這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心。4. 無需測距的定位技術(shù)- DV-Hop算法 基本思想： 首先：計算未知節(jié)點(diǎn)與每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù)； 然后：估算平均每跳的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計距離； 最后：利

12、用三邊測量法或極大似然估計法計算未知節(jié)點(diǎn)的坐標(biāo)。4. 無需測距的定位技術(shù)- DV-Hop算法 計算未知節(jié)點(diǎn)與每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù) 信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組，其中包括跳數(shù)字段，初始化為0； 接收節(jié)點(diǎn)記錄具有到每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一個信標(biāo)節(jié)點(diǎn)的較大跳數(shù)的分組。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)； 網(wǎng)絡(luò)中所有節(jié)點(diǎn)能夠記錄下到每個信標(biāo)節(jié)點(diǎn)最小跳數(shù)4. 無需測距的定位技術(shù)- DV-Hop算法 計算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離 每個信標(biāo)節(jié)點(diǎn)根據(jù)記錄的其它信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，估算平均每跳的實(shí)際距離 ； 然后，信標(biāo)節(jié)點(diǎn)將計算的每跳平均距離用帶有生存期字段的分組廣播

13、至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的第一個每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn) ； 未知節(jié)點(diǎn)接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，計算到每個信標(biāo)節(jié)點(diǎn)的跳段距離；4. 無需測距的定位技術(shù)- DV-Hop算法 利用三邊測量法或極大似然估計法計算自身位置 未知節(jié)點(diǎn)利用第二階段中記錄的到各個信標(biāo)節(jié)點(diǎn)的跳段距離，利用三邊測量法或極大似然估計法計算自身坐標(biāo)4. 無需測距的定位技術(shù)- DV-Hop算法 例子 信標(biāo)節(jié)點(diǎn)L2計算的每跳平均距離為(40+75)/(2+5) A從L2獲得每跳平均距離，則節(jié)點(diǎn)A與三個信標(biāo)節(jié)點(diǎn)之間的距離分別為L1：316.42，L2：216.42，L3：316.42； L3AL1L24. 無需測

14、距的定位技術(shù)- APIT算法 近似三角形內(nèi)點(diǎn)測試法（APIT, Approximate Point-In-Triangulation test）找到若干個由參考節(jié)點(diǎn)構(gòu)成的三角形，則節(jié)點(diǎn)必然在這些三角形的交集內(nèi)。使用這個交集的重心估計節(jié)點(diǎn)的位置。 APIT算法分四步：（1）信標(biāo)交換，（2）三角形內(nèi)點(diǎn)測試（PIT, Point-In-Triangulation testing），（3） 交集運(yùn)算計算三角形的重合區(qū)域，（4）重心（COG, Center of Gravity）計算求節(jié)點(diǎn)的位置。 4. 無需測距的定位技術(shù)-APIT算法 基本過程 未知節(jié)點(diǎn)首先收集其鄰近信標(biāo)節(jié)點(diǎn)的位置信息； 從這些信標(biāo)節(jié)

15、點(diǎn)組成的集合中任意選取三個節(jié)點(diǎn)，假設(shè)集合中有n個元素，那么共有Cn3種不同選取方法，確定Cn3個不同三角形，逐一測試未知節(jié)點(diǎn)是否位于每個三角形內(nèi)部，直到窮盡所有Cn3種組合或達(dá)到定位所需精度； 計算包含目標(biāo)節(jié)點(diǎn)所有三角形的重疊區(qū)域，并求質(zhì)心；4. 無需測距的定位技術(shù)- APIT算法 PIT：最佳三角形內(nèi)點(diǎn)測試法 PIT原理 假如存在一個方向，節(jié)點(diǎn)M沿著這個方向移動會同時遠(yuǎn)離或接近頂點(diǎn)A、B、C，那么節(jié)點(diǎn)M位于ABC外；否則，節(jié)點(diǎn)M位于ABC內(nèi)。4. 無需測距的定位技術(shù)-APIT算法 收集信息 未知節(jié)點(diǎn)收集鄰近信標(biāo)節(jié)點(diǎn)的信息，如位置、標(biāo)識號、接收到的信號強(qiáng)度等；鄰居節(jié)點(diǎn)之間交換各自接收到的信標(biāo)節(jié)

16、點(diǎn)的信息 ； APIT 測試 測試未知節(jié)點(diǎn)是否在不同信標(biāo)節(jié)點(diǎn)組合成三角形內(nèi)部 ； 計算重疊區(qū)域 統(tǒng)計包含未知節(jié)點(diǎn)三角形，計算所有三角形的重疊區(qū)域； 計算未知節(jié)點(diǎn)位置 計算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點(diǎn)的位置3. 無需測距的定位技術(shù)-不定形定位算法 在不定形計算機(jī)（Amorphous Computer）上實(shí)現(xiàn)的定位算法。 不定形計算機(jī)是一種并行計算結(jié)構(gòu)，和智能群（蟻群、鳥群、粒子群等）很相似。本質(zhì)上，不定形算法是DV-Hop算法的增強(qiáng)，引入了多參考點(diǎn)測量進(jìn)行估計求精的步驟。兩個重要的參數(shù)修正：不定形算法通過平滑（smoothing）修正節(jié)點(diǎn)到參考節(jié)點(diǎn)的梯度跳數(shù)。采用通信半徑作為每跳距離，使得節(jié)點(diǎn)到參考節(jié)點(diǎn)的最終估計距離偏大。不定形算法采用下面的公式來修正每跳距離： 本節(jié)課主要內(nèi)容提綱WSN定位技術(shù)的概述 定位算法的幾種分類基于測距的定位技術(shù) 無需測距的定位技術(shù) 一篇WSN定位的文獻(xiàn) 6.一篇文獻(xiàn)標(biāo)題：簡明扼要標(biāo)題：簡明扼要 編輯：審稿周期編輯：審稿周期6.一篇文獻(xiàn)研究什么問題研究什么問題Consider 使用什么方法、得到什么結(jié)果使用什么方法、得到什么結(jié)果First, Then, By applying 仿真驗(yàn)證理論仿真驗(yàn)證理論Simulations 關(guān)鍵詞：研究對象、研究方法關(guān)鍵詞：研究對