第2講 定位技術(shù).

1、1WSN: Theory and Applications一、WSN概述二、定位技術(shù)三、目標跟蹤四、拓撲控制五、時間同步 六、路由協(xié)議七、安全技術(shù)八、課程考核本節(jié)課主要內(nèi)容提綱1.WSN定位技術(shù)的概述 2.基于測距的定位技術(shù) 3.無需測距的定位技術(shù) 4.一篇WSN定位的文獻 1. WSN定位技術(shù)的概述基本含義重要意義性能指標算法特點位置計算算法分類1. WSN定位技術(shù)的概述-基本含義 定位就是確定位置。定位的兩種意義：一種是確定自己在系統(tǒng)中的位置；一種是確定目標在系統(tǒng)中的位置。位置信息的類型：物理位置指目標在特定坐標系下的位置數(shù)值，表示目標的相對或者絕對位置；符號位置指在目標與一個基站或者多個

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

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

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

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

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

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

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

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

10、術(shù)的概述 2.基于測距的定位技術(shù) 3.無需測距的定位技術(shù) 4.一篇WSN定位的文獻 3. 無需測距的定位技術(shù)質(zhì)心定位算法 DV-Hop算法 APIT算法 不定形定位算法 3. 無需測距的定位技術(shù)-質(zhì)心定位算法 多邊形的幾何中心，稱為質(zhì)心，多邊形頂點坐標的平均值就是質(zhì)心節(jié)點的坐標。 質(zhì)心定位算法首先確定包含未知節(jié)點的區(qū)域，計算這個區(qū)域的質(zhì)心，并將其作為未知節(jié)點的位置。3. 無需測距的定位技術(shù)-質(zhì)心定位算法 基本過程： 信標節(jié)點周期性向鄰近節(jié)點廣播信標分組，信標分組中包含信標節(jié)點的標識號和位置信息； 當未知節(jié)點接收到來自不同信標節(jié)點的信標分組數(shù)量超過某一個門限k或接收一定時間后，就確定自身位置為這

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

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

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

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

15、向移動會同時遠離或接近頂點A、B、C，那么節(jié)點M位于ABC外；否則，節(jié)點M位于ABC內(nèi)。3. 無需測距的定位技術(shù)-APIT算法 收集信息 未知節(jié)點收集鄰近信標節(jié)點的信息，如位置、標識號、接收到的信號強度等；鄰居節(jié)點之間交換各自接收到的信標節(jié)點的信息 ； APIT 測試 測試未知節(jié)點是否在不同信標節(jié)點組合成三角形內(nèi)部 ； 計算重疊區(qū)域 統(tǒng)計包含未知節(jié)點三角形，計算所有三角形的重疊區(qū)域； 計算未知節(jié)點位置 計算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點的位置3. 無需測距的定位技術(shù)-不定形定位算法 在不定形計算機（Amorphous Computer）上實現(xiàn)的定位算法。 不定形計算機是一種并行計算結(jié)構(gòu)，和智

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