無線傳感器網(wǎng)絡(luò)定位跟蹤與時間同步技術(shù)

1、無線傳感器網(wǎng)絡(luò)技術(shù)及其應用第四章 無線傳感器網(wǎng)絡(luò)定位、跟蹤與時間同步技術(shù)課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢4.1無線傳感器網(wǎng)絡(luò)定位技術(shù)定位是無線傳感器網(wǎng)絡(luò)重要的支撐技術(shù)，定位就是確定位置。無線傳感器網(wǎng)絡(luò)的定位是指自組織的網(wǎng)絡(luò)通過特定方法提供節(jié)點位置信息。這種自組織網(wǎng)絡(luò)定位分為節(jié)點自身定位和目標定位。節(jié)點自身定位是確定網(wǎng)絡(luò)中節(jié)點為坐標位置的過程。目標定位是確定網(wǎng)絡(luò)覆蓋范圍內(nèi)目標的坐標位置。14.1無線傳感器網(wǎng)絡(luò)定位技術(shù)在傳感器網(wǎng)絡(luò)中，沒有統(tǒng)一的最優(yōu)的定位算法，只有針對特定環(huán)境比較適合的定位算法。按照下面的

2、標準對定位算法進行分類：1基于測距的定位和無需測距的定位2絕對定位與相對定位3集中式計算、分布式計算與遞增式計算24.1無線傳感器網(wǎng)絡(luò)定位技術(shù)1基于測距的定位和無需測距的定位前者需要測量相鄰節(jié)點之間的絕對距離或者方位，并利用節(jié)點間的實際距離或者方位來計算未知節(jié)點的位置，常用的測距技術(shù)有RSSI（到達信號強度測量法）、TOA（到達時間測量法）、TDOA（到達時間差測量法）等。雖然在定位精度上有一定可取之處，但是并不適用于低功耗、低成本的領(lǐng)域?；跓o需測距的定位算法無需測量節(jié)點之間的絕對距離或方位，而是利用節(jié)點間的估計距離計算節(jié)點的位置，如典型的DV-Hop定位、凸規(guī)劃定位。雖然在精確度方面有待進

3、一步改進，但是具有可擴展性、規(guī)模性以及代價小等優(yōu)點。34.1無線傳感器網(wǎng)絡(luò)定位技術(shù)2絕對定位與相對定位絕對定位的定位結(jié)果是一個標準的坐標位置，如經(jīng)緯度；而相對定位通常是以網(wǎng)絡(luò)中部分節(jié)點為參考，建立整個網(wǎng)絡(luò)的相對坐標系統(tǒng)。絕對定位可為網(wǎng)絡(luò)提供唯一的命名空間，受網(wǎng)絡(luò)變動影響較小，有非常廣泛的應用領(lǐng)域。大多數(shù)定位系統(tǒng)都可以實現(xiàn)絕對定位，只有部分定位系統(tǒng)和算法能實現(xiàn)相對定位。44.1無線傳感器網(wǎng)絡(luò)定位技術(shù)3集中式計算、分布式計算與遞增式計算集中式計算是指把所需要的定位信息集中傳送到某個中心節(jié)點（如匯聚節(jié)點），由該節(jié)點進行集中計算未知節(jié)點的位置。分布式計算是指由節(jié)點間進行信息交換，未知節(jié)點根據(jù)自身獲取足

4、夠的信息進行自身位置計算的計算方式。集中式計算的優(yōu)點是可以從全局角度出發(fā)更好地進行規(guī)劃，從而獲得相對精確的定位。缺點是中心節(jié)點以及它周圍的節(jié)點通信開銷過大、能耗過快，易造成個別節(jié)點過早死亡，從而影響其它節(jié)點的定位。分布式計算可使網(wǎng)絡(luò)中所有節(jié)點同時進行位置計算。遞增式計算通常是從信標節(jié)點開始，信標節(jié)點周圍的節(jié)點首先開始定位，依次向外延伸，逐步實現(xiàn)整個網(wǎng)絡(luò)的定位。遞增式算法的缺點是在定位過程中誤差容易被積累和放大。5課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.1.14.1.2無線傳感器網(wǎng)絡(luò)測距技術(shù)無線傳感

5、器網(wǎng)絡(luò)定位機制與性能評價標準現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法4.1.3無線傳感器網(wǎng)絡(luò)定位技術(shù)4.14.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)測距即測量兩個節(jié)點之間的距離，一般常采用物理信號測量方式，如無線電、聲波和磁場等。根據(jù)各種物理信號的優(yōu)缺點，常用的方法有到達時間測量法（TOA）、到達時間差測量法（TDOA）、到達信號強度測量法（RSS）等。1測距中用到的基本術(shù)語: 接收新信號強度指示（Received Signal Strength Indicator，RSSI）：節(jié)點接收到無線信號的強度的大小，稱為接收信號的強度指示。 到達角度（Angle of Arrival，AOA）：節(jié)點接收到的信號相對于自身軸

6、線的角度，稱為信號相對接收節(jié)點的到達角度。 視線關(guān)系（Line of Sight，LOS）：兩個節(jié)點間沒有障礙物間隔，能夠直接通信，稱為兩個節(jié)點間存在視線關(guān)系。 非視線關(guān)系（NLOS，no LOS）：兩個節(jié)點之間存在障礙物。24.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)一些測距方法:1到達時間測量法（Time of Arrival，TOA）2到達時間差測量法（Time Difference of Arrival，TDOA）3到達信號強度測量法（RSSI）34.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)1到達時間測量法（Time of Arrival，TOA）已知物理信號的傳播速度v，根據(jù)信號的傳播時間t來計算節(jié)點間的距

7、離，即距離d=vt。此方法要求進行通信的兩個節(jié)點時間必須高度同步。44.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)2到達時間差測量法（Time Difference of Arrival，TDOA）發(fā)送節(jié)點同時發(fā)射兩種不同速率的無線信號，接收節(jié)點根據(jù)兩種信號的時間到達差和速率，計算這兩個節(jié)點之間的距離。節(jié)點A在T0時刻同時發(fā)射無線射頻信號和超聲波信號，節(jié)點B分別記錄這兩種物理信號的到達時間T1和T2，已知無線射頻信號和超聲波的速率分別為v1，v2，設(shè)兩節(jié)點之間的距離為d，由 可得：54.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)64.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)3到達信號強度測量法（RSSI）信號強度會隨著其傳播距離的增

8、加而衰減,表明信號強度變化與傳播距離間存在著某種函數(shù)關(guān)系。無線信道的數(shù)學模型如式： d是發(fā)射機和接收機之間的距離，d0是參考距離；n是信道衰減指數(shù)，一般取值24；X是均值為零、方差的高斯隨機變量；PL(d0)是距離發(fā)射機d0處的信號強度。它是一種低功率、廉價的測距技術(shù)，但是信號強度很容易受到周圍環(huán)境的影響，通常將其看做一種粗糙的測距技術(shù)。74.1.1無線傳感器網(wǎng)絡(luò)測距技術(shù)課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.1.14.1.2無線傳感器網(wǎng)絡(luò)測距技術(shù)無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準現(xiàn)有無線傳感器

9、網(wǎng)絡(luò)定位方法4.1.3無線傳感器網(wǎng)絡(luò)定位技術(shù)4.11定位機制解析幾何中的任何可以確定某一點位置的幾何學方法，只要傳感器網(wǎng)絡(luò)能夠提供足夠的信息，都可以成為定位的方法。比較常用的是三邊定位法、多邊極大似然估計法以及角度測量法。定義： 信標節(jié)點：已知節(jié)點坐標或者位置信息的節(jié)點，有的書籍也稱為錨節(jié)點。 未知節(jié)點：坐標或者位置信息未知的節(jié)點。14.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（1）三邊定位法已知3個信標節(jié)點的坐標和其中1個未知節(jié)點到3個信標節(jié)點的距離，求該未知節(jié)點的坐標。24.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準設(shè)未知節(jié)點D的坐標為（x，y），信標節(jié)點的A、B、C的坐標分別為（xA，

10、yA）、（xB，yB）、（xA，yC），未知節(jié)點到3個信標節(jié)點的距離分別為dA、dB、dC，則從而可以推出未知節(jié)點的坐標為34.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（2）多邊極大似然估計法多邊極大似然估計法是指已知3個以上的信標節(jié)點的坐標和它們到未知節(jié)點的距離，求解該未知節(jié)點的坐標。設(shè)節(jié)點1，2，3，4，n個節(jié)點的坐標分別為 、 、 、 ，它們到節(jié)點D的距離分別為d1、d2、d3、dn，節(jié)點D的坐標為（x，y），則44.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準54.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準從第一個方程開始分別減去最后一個方程可得如下線性方程：64.1.2無線傳感器網(wǎng)絡(luò)

11、定位機制與性能評價標準簡化為矩陣相乘的方式：AX=b使用標準的最小均方差估計方法可以得到節(jié)點D的坐標為：74.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（3）角度測量法原理如圖4-4所示，已知信標節(jié)點A、B、C的坐標分別為 ， ， 和3個內(nèi)角 、 、 。設(shè)未知節(jié)點D的坐標為 ，則對于節(jié)點A、C和角 ，如果弧段AC在 中，那么能夠唯一確定一個圓，設(shè)圓心 ，半徑為r1，則 ，并存在下列公式：能夠確定圓心O1點的坐標和半徑r1。同理對A、B，ADB和B、C，BDC分別能夠確定相應的圓心 、半徑r2、圓心 、半徑r3。84.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準最后，利用三邊定位法，由點 ， ，

12、確定節(jié)點D的坐標。94.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準2定位性能評價標準無線傳感器網(wǎng)絡(luò)自身定位系統(tǒng)和算法有很多，它們的性能直接影響其可用性。幾個常用的評價標準：（1）定位精度定位精度是指定位系統(tǒng)提供的位置信息的精確程度，是評價指標中的首要標準。定位精度有相對精度和絕對精度。精度越高，技術(shù)要求越高，成本也相應越高。絕對精度是指以長度為量度的精度。相對精度通常以誤差值與節(jié)點的無線射程的比例表示。104.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（2）覆蓋范圍覆蓋范圍是指節(jié)點的射程范圍，覆蓋范圍越大，精度越高的定位機制是最佳的選擇。覆蓋范圍和定位精度是一對矛盾。覆蓋范圍越大，提供的精度越

13、低。在實際應用中可以根據(jù)具體情況在覆蓋范圍和定位精度之間做出折中，以達到較好的定位效果。114.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（3）信標節(jié)點密度不同的定位方案對信標節(jié)點的數(shù)量要求不同，如三邊定位算法要求3個信標節(jié)點、多邊極大似然估計法需要至少3個信標節(jié)點。信標節(jié)點一般都是通過人工部署或者全球定位系統(tǒng)（GPS）獲取其地址的。信標節(jié)點的密度越小越好。124.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準（4）容錯性和魯棒性定位算法通常是在比較理想的通信環(huán)境和一些測量指標比較準確的情況下才能達到精確定位。在實際網(wǎng)絡(luò)環(huán)境定位過程中，通常存在因為周圍環(huán)境的影響而產(chǎn)生的測離和角度誤差太大從而影響定

14、位精度，網(wǎng)絡(luò)節(jié)點能量耗盡、物理損傷等自身原因而過早死亡，引起其他節(jié)點的定位過程中斷或者不能實現(xiàn)等諸多情況。因此，定位系統(tǒng)要有一定的容錯性和魯棒性從而減小定位誤差提高定位精度，以更好地適應周圍環(huán)境。134.1.2無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.1.14.1.2無線傳感器網(wǎng)絡(luò)測距技術(shù)無線傳感器網(wǎng)絡(luò)定位機制與性能評價標準現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法4.1.3無線傳感器網(wǎng)絡(luò)定位技術(shù)4.11Cricket定位系統(tǒng)2質(zhì)心定位算法3TOA和TDOA定位方法4AOA定位算

15、法5RSSI定位方法6DV-HOP定位方法7Amorphous定位方法8APIT定位方法14.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法1Cricket定位系統(tǒng)Cricket是一種基于TDOA測距技術(shù)的室內(nèi)定位系統(tǒng)，與其他定位系統(tǒng)不同的是，它通過測量到未知節(jié)點最近的信標節(jié)點計算靜止或者移動目標在大樓內(nèi)具體房間的哪一區(qū)域，而不是絕對位置。Cricket系統(tǒng)沒有中心管理或者控制系統(tǒng)，而是分布式管理，為了更好地通信，把信標節(jié)點和發(fā)射器布置在天花板上。24.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法2質(zhì)心定位算法質(zhì)心定位算法是一種與距離無關(guān)的估計定位算法，質(zhì)心也即多邊形的幾何中心，多邊形的頂點坐標的平均值為質(zhì)心坐標。多邊

16、形ABCD的頂點是 ， ， ， ，則質(zhì)心坐標為 在質(zhì)心算法中首先確定未知節(jié)點的所在區(qū)域，計算這個區(qū)域的質(zhì)心坐標，并將該質(zhì)心坐標作為此未知節(jié)點的坐標。它不需要信標節(jié)點和未知節(jié)點之間的協(xié)調(diào)，因此實現(xiàn)起來比較簡單，算法復雜度比較低。34.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法3TOA和TDOA定位方法Girod L等利用TOA測距技術(shù)實現(xiàn)了網(wǎng)絡(luò)定位。該系統(tǒng)中假設(shè)發(fā)送節(jié)點和接收節(jié)點時間同步并且每個節(jié)點均包含一個發(fā)射機和一個接收機，發(fā)射機發(fā)射一種命名為chirp的聲波，并且同時在該聲波中包含了發(fā)送時間。當接收機收到chirp聲波后從中提取發(fā)送時間，利用聲波在大氣中的傳播模型計算發(fā)送節(jié)點和接收節(jié)點之間的距離。節(jié)

17、點在計算出與多個臨近信標節(jié)點之間的距離后，可以利用三邊定位法或者極大似然估計法計算自身位置?；赥OA的定位實現(xiàn)簡單，定位精度高，但是要求節(jié)點間保持精確的時間同步，這樣對傳感器網(wǎng)絡(luò)的節(jié)點的硬件和功耗提出了較高的要求。44.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法基于TDOA測距定位的應用已經(jīng)不再陌生，前面講述的Cricket系統(tǒng)就是一個很好的應用，下面重點介紹另一個基于TDOA測距定位的應用AHLos（Ad-Hoc Localization System）系統(tǒng)。AHLos系統(tǒng)在初始階段已經(jīng)通過人工配置或者使用GPS定位技術(shù)使一小部分節(jié)點成為信標節(jié)點，它實現(xiàn)全網(wǎng)未知節(jié)點的定位是一個逐步迭代的過程。首先信

18、標節(jié)點向周圍鄰近節(jié)點廣播自己的位置信息，未知節(jié)點通過TDOA方法測得與周圍臨近節(jié)點的距離和接收到的位置信息使用相應的定位算法計算自身的位置，轉(zhuǎn)化成為信標節(jié)點并向周圍鄰近節(jié)點廣播自己的位置信息，這樣依次迭代直到網(wǎng)絡(luò)中所有未知節(jié)點均計算出自己的位置。54.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法在具體迭代過程中，未知節(jié)點會根據(jù)周圍信標節(jié)點的不同分布選擇相應的多變定位算法計算自身位置。（1）原子多邊算法（Atomic Multilateration）（2）迭代多邊算法（Iterative Multilateration）（3）協(xié)作多邊算法（Collaborative Multilateration）總體來講

19、，AHLos算法在迭代過程中存在誤差積累問題，對網(wǎng)絡(luò)節(jié)點密度要求高，不適合大規(guī)模無線傳感器網(wǎng)絡(luò)?；赥DOA的測距技術(shù)對硬件要求高，具有測距誤差小，精度高的優(yōu)點。64.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法4AOA定位算法基于到達角度的AOA定位算法，未知節(jié)點通過天線陣列和多個超聲波接收器感知信標節(jié)點的發(fā)送信號的方向，計算未知節(jié)點和信標節(jié)點之間的方位角等，再通過角度測量法計算未知節(jié)點的位置。每個節(jié)點配有兩個超聲波接收機為例，節(jié)點A為未知節(jié)點，節(jié)點B為信標節(jié)點，兩個接收機R1和R2之間的距離為L，兩個接收機的連線的中垂線為節(jié)點A的軸線，x1、x2分別為R1和R2到信標節(jié)點的距離，角為節(jié)點B相對于節(jié)點A

20、的方位角。當節(jié)點A的兩個接收機收到節(jié)點B的信號后，利用TOA技術(shù)測出x1、x2，然后再根據(jù)幾何關(guān)系可以推導出節(jié)點B相對于節(jié)點A的方位角。74.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法84.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法利用上面的方法，分別測得相鄰3個節(jié)點的相對各自的方位角，如節(jié)點B相對節(jié)點A的方位角為ab，同樣可以測得節(jié)點C相對于節(jié)點A的方位角ac，由此可得：CAB=acab。如果節(jié)點B是已知方向的節(jié)點，它的軸線相對于指南針方向角為b，則可以根據(jù)幾何知識推導出節(jié)點A的軸線相對于指南針的方向角為 。由此可知，該算法還可以實現(xiàn)定向功能。由于基于AOA的定位算法需要額外硬件的支持，而且測距過程容易受到外界

21、環(huán)境的影響，因此不適合在大規(guī)模網(wǎng)絡(luò)中使用。94.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法104.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法5RSSI定位方法在RSSI定位過程中，未知節(jié)點根據(jù)接收到的信號強度值計算信號的傳播損耗，按照相應的傳播損耗模型將傳播損耗轉(zhuǎn)化為距離，然后再根據(jù)三邊定位法或者多邊極大似然估計法計算未知節(jié)點的位置。SpotON項目，微軟的RADAR系統(tǒng)都利用了RSSI測距技術(shù)。RADAR是一個基于RSSI測距的室內(nèi)定位系統(tǒng)，用于確定用戶所在樓層的具體位置。它一般使用信號傳播經(jīng)驗模型和理論模型兩種方法進行未知節(jié)點的定位?；赗SSI的定位受到周圍環(huán)境的影響很大，定位精度不穩(wěn)定，尤其是在室外，影響

22、因素會更多，該技術(shù)離實際應用還有一段距離。114.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法6DV-HOP定位方法DV-HOP（Distance Vector-HOP）定位機制包括3個不同的階段，首先計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)，其次計算未知節(jié)點與信標節(jié)點之間的距離，最后計算未知節(jié)點的坐標。124.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法（1）第一階段：計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)這個階段使用經(jīng)典的距離矢量交換協(xié)議，每個節(jié)點維護一個表 ，其中xi、yi、hi分別代表信標節(jié)點的坐標和到該信標節(jié)點的跳數(shù)。每個信標節(jié)點發(fā)送一個廣播分組，該分組包含自身的位置信息和跳段個數(shù)，跳段個數(shù)初始化為0。節(jié)點收到信

23、標節(jié)點的廣播分組后檢驗該分組跳段數(shù)是否小于本節(jié)點表內(nèi)的存儲值，如果是則更新該表，然后跳段數(shù)加1并廣播該分組，否則丟棄該分組。最終所有的未知節(jié)點均能獲得到所有信標節(jié)點的最小跳數(shù)。134.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法（2）第二階段：計算未知節(jié)點與信標節(jié)點的距離每個信標節(jié)點根據(jù)自身表中記錄的其他信標節(jié)點的坐標信息和跳數(shù)，按照式（4-12）計算平均跳段距離ci。然后把計算出來的平均跳段距離利用可控洪泛法進行廣播，每個節(jié)點均接收第一個跳段距離，忽略后來到達的，這樣確保了絕大多數(shù)節(jié)點可從最近的信標節(jié)點接收平均跳段距離。最后未知節(jié)點便可計算自己到達相應的信標節(jié)點的距離。其中 、 分別為信標節(jié)點i、j的坐

24、標，hi為節(jié)點i到節(jié)點j的跳段數(shù)。144.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法（3）第三階段：計算未知節(jié)點的坐標 當未知節(jié)點收到3個或者更多信標節(jié)點的距離時，則可以根據(jù)三邊定位或多邊定位算法進行自身位置的計算。接下來舉例說明具體計算過程，如圖4-11所示，經(jīng)過前兩個階段，現(xiàn)在已知信標節(jié)點L1、L2與L3之間的距離和跳數(shù)，假設(shè)L2計算得到平均跳段距離為（40+75）/（2+5）=16.42。假設(shè)節(jié)點A從節(jié)點L2獲得平均跳段距離，則它與信標節(jié)點L1、L2、L3的距離為分別為316.42、216.42、316.42。DV-HOP定位算法使用平均跳段距離估算兩點之間的實際距離，存在一定誤差，同時在定位過程

25、中兩次洪泛，能量開銷大，但是該算法對硬件要求低，實現(xiàn)簡單。154.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法164.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法7Amorphous定位方法假定傳感器節(jié)點隨機分布在一個二維面板上，傳感器節(jié)點的物理通信半徑為r，r遠小于該面板的尺寸，在節(jié)點本身距離r以內(nèi)的節(jié)點為通信鄰居，每個節(jié)點都可以和通信鄰居內(nèi)的節(jié)點進行通信。同時，該算法首先假定每個節(jié)點擁有相同的通信距離，并且不使用RSS測距來確定未知節(jié)點的位置，因此Amorphous定位算法是無需測距的定位算法。174.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法Amorphous定位算法為以下面兩個階段：第一階段：使用經(jīng)典的距離矢量交換協(xié)議

26、計算未知節(jié)點和信標節(jié)點之間的最小跳數(shù)，該過程在DV-HOP定位算法中已經(jīng)介紹，這里不再重復。第二階段：使用節(jié)點的通信半徑r作為節(jié)點間的平均每跳通信距離，從而估算未知節(jié)點和信標節(jié)點之間的距離，當未知節(jié)點得出至少到3個信標節(jié)點距離后，估算自己的坐標位置。直到該節(jié)點到信標節(jié)點的計算距離與估算距離之間的方差最小為止。Amorphous算法需要較高的節(jié)點密度，并且要求在網(wǎng)絡(luò)部署前離線計算平均每跳距離，網(wǎng)絡(luò)擴展性差。184.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法8APIT定位方法近似三角形內(nèi)點測試法APIT（Approximate Point-in-triangulation Test）是一種無需測距的定位技術(shù)

27、，它包括四個步驟。1.收集信息。未知節(jié)點收集周圍臨近信標節(jié)點的位置、標識號、接收信號強度等信息，鄰居節(jié)點之間交換并共享各自接收到的信標節(jié)點的信息。2.PIT測試。未知節(jié)點收集到的信標節(jié)點組合成不同的三角形，假設(shè)信標節(jié)點有n個，則可以組合成 個不同的三角形，測試該未知節(jié)點是否在三角形內(nèi)部，直到窮盡所有三角形或者達到預定的定位精度為止。將所有的包含未知節(jié)點的三角形存儲在Inside集合中。194.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法3.計算重疊區(qū)域。計算Inside集合中所有三角形的重疊區(qū)域，該區(qū)域為一個多邊形。 4.計算未知節(jié)點的位置。計算重疊區(qū)域的質(zhì)心坐標作為未知節(jié)點的坐標。204.1.3現(xiàn)有無線

28、傳感器網(wǎng)絡(luò)定位方法接下來重點介紹PIT測試原理，如圖4-13所示，存在一個方向，當節(jié)點M沿著這個方向移動時，如果它同時遠離或者接近節(jié)點A、B、C時，則節(jié)點M在三角形ABC的外部，否則節(jié)點M在三角形ABC的內(nèi)部。214.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法但是無線傳感器網(wǎng)絡(luò)節(jié)點是靜止的，如何辨別節(jié)點M是靠近還是遠離某一信標節(jié)點。為了模擬節(jié)點的移動，利用節(jié)點的接收信號強度來進行測試，通常未知節(jié)點離信標節(jié)點越遠，它的接收信號強度越弱，節(jié)點M通過與鄰居節(jié)點交換信息并對比接收信號強度值，從而可以判斷是靠近還是遠離某一信標節(jié)點。為了窮盡所有可能的方向測試節(jié)點M會同時靠近或者遠離了個信標節(jié)點，提出近似三角形內(nèi)點

29、測試法，PIT測試的準確性與網(wǎng)絡(luò)場景和網(wǎng)絡(luò)節(jié)點密度有關(guān)。在網(wǎng)絡(luò)無線信號傳播模式不規(guī)則和傳感器節(jié)點隨機部署的情況下，APIT算法的定位精度高，性能穩(wěn)定，但是APIT測試需要較高的網(wǎng)絡(luò)連通性，通常連通度大于6。相對于質(zhì)心算法而言，APIT定位算法對信標節(jié)點密度要求低，定位精度高。214.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法214.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.2.14.2.2無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)概述無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)4.2在無

30、線傳感器網(wǎng)絡(luò)的許多實際應用中，跟蹤運動目標是一項基本功能。由于傳感器節(jié)點體積小、價格低廉、采用無線通信方式，以及傳感器網(wǎng)絡(luò)部署隨機，具有自組織性、魯棒性和隱藏性等特點，無線傳感器網(wǎng)絡(luò)非常適合于移動目標的定位和跟蹤。傳感器網(wǎng)絡(luò)的跟蹤算法必須能夠盡可能利用局部信息進行目標位置和運動軌跡的計算，具備移動的魯棒性以適應網(wǎng)絡(luò)拓撲的動態(tài)變化，能夠?qū)崟r傳輸跟蹤數(shù)據(jù)和計算結(jié)果，同時具備較低通信開銷。14.2.1無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)概述在無線傳感器網(wǎng)絡(luò)跟蹤過程中，首先需要節(jié)點進行監(jiān)測，如果監(jiān)測到目標出現(xiàn)，需要在一定時間內(nèi)選擇適合的算法判斷出目標的運動軌跡，并對目標進行一些狀態(tài)探測，這就要求傳感器節(jié)點不僅具有一

31、定的數(shù)據(jù)處理能力，而且能夠根據(jù)不同的任務和有限的資源選擇適合的算法計算目標的狀態(tài)。按照跟蹤對象數(shù)量的不同，傳感器網(wǎng)絡(luò)的目標跟蹤可以分為單目標跟蹤和多目標跟蹤；按照目標形狀的不同，可以分為點目標跟蹤和面目標跟蹤；按照傳感器節(jié)點運動方式的不同，可以分為靜態(tài)目標的偵測和移動目標的跟蹤。24.2.1無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)概述課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.2.14.2.2無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)概述無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)4.2跟蹤與定位不同，主要目的不是追求定位的精度

32、，而是需要對移動的目標或者時間進行動態(tài)的監(jiān)測。基于無線傳感器網(wǎng)絡(luò)的目標跟蹤過程大致包括3個階段：檢測、定位和通告，每個階段需要不同的技術(shù)來實現(xiàn)。14.2.2無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程在檢測階段，主要任務是通過各種檢測手段檢測跟蹤目標是否出現(xiàn)，常用的技術(shù)有超聲波檢測、震動技術(shù)檢測、紅外線技術(shù)檢測以及多媒體基礎(chǔ)檢測等；定位階段，定位是跟蹤的技術(shù)基礎(chǔ)，在前面部分敘述了多種無線傳感器網(wǎng)絡(luò)定位技術(shù)，可以根據(jù)不同的場景和用戶需求來選擇適合的定位技術(shù)來確定當前目標的位置和狀態(tài)，比較常用的方法有雙元檢測、三角測量以及基于流行學習算法等，然后記錄當前目標的軌跡和狀態(tài)，用于以后目標跟蹤查看或者預測；通告階段

33、，是節(jié)點之間交互信息的過程，在這個過程中節(jié)點向周圍其他節(jié)點發(fā)出協(xié)作定位求助或者通告其他節(jié)點自己對目標的監(jiān)測狀態(tài)。24.2.2無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程1檢測階段無線傳感器網(wǎng)絡(luò)中的節(jié)點周期性地通過傳感器模塊檢測是否有目標出現(xiàn)。節(jié)點通過一些技術(shù)測試目標的真實性，如果確實目標到達了本節(jié)點的監(jiān)測區(qū)域，則節(jié)點首先計算自己到目標的距離，然后向整個網(wǎng)絡(luò)廣播目標偵測消息。鄰居節(jié)點收到該目標偵測消息后保存到本地信息表中并加上時間戳。節(jié)點動態(tài)維護本地信息表，如果表中的信息表項在預定的時間內(nèi)得不到更新將會被刪除。34.2.2無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程2定位階段為了節(jié)省能量，只有距離跟蹤目標比較近的節(jié)點才

34、會對目標進行定位，如果節(jié)點收到另外兩個或者兩個以上的節(jié)點到跟蹤目標的距離，則可選用三邊定位法或者多邊極大似然估計法計算跟蹤目標的位置。確定跟蹤目標的位置后，還要進一步預測其運動趨勢，以便通知目標將要達到區(qū)域的網(wǎng)絡(luò)節(jié)點。44.2.2無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程3通告階段計算出跟蹤目標的運動軌跡后，傳感器網(wǎng)絡(luò)要通知跟蹤目標周圍的節(jié)點啟動進入跟蹤狀態(tài)。所有利用3個位置估算出的跟蹤目標的軌跡節(jié)點均廣播一個通告消息，該消息包含了本節(jié)點的位置信息和跟蹤目標的軌跡。收到消息的節(jié)點計算本身到跟蹤目標預測軌跡的距離，如果該距離小于預定的閾值d，則節(jié)點啟動進入跟蹤狀態(tài)，同時轉(zhuǎn)發(fā)該通告消息。否則節(jié)點保持原狀態(tài)并

35、丟棄該消息。54.2.2無線傳感器網(wǎng)絡(luò)目標跟蹤的基本過程課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.3.14.3.2時間同步模型時間同步協(xié)議無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.31時鐘模型2通信模型3時鐘同步的誤差來源14.3.1時間同步模型1時鐘模型傳感器網(wǎng)絡(luò)中節(jié)點的本地時鐘依靠對自身晶振中斷計數(shù)實現(xiàn)。晶振的頻率誤差和初始計時時刻不同，使得節(jié)點之間本地時鐘不同步。如果能估算出本地時鐘與物理時鐘的關(guān)系或本地時鐘之間的關(guān)系，就可以構(gòu)造對應的邏輯時鐘以達成同步。目前的邏輯時鐘同步算法，如下文提到的有些同步算法同

36、步精度已達到1s，可以滿足傳感器網(wǎng)絡(luò)中絕大部分應用的需求。如果要達到納秒級精度，則要采用鎖相環(huán)等硬件實現(xiàn)物理時鐘同步。24.3.1時間同步模型（1）節(jié)點本地時鐘模型在計算機系統(tǒng)中，時鐘通常用晶體振蕩器脈沖來度量:在工程實踐中，因為溫度、壓力、電源電壓等外界環(huán)境的變化，往往會導致晶振頻率產(chǎn)生波動。因此，構(gòu)造理想時鐘比較困難。在一般情況下，晶振頻率的波動幅度并是非任意的，而是局限在一定的范圍之內(nèi)，為了方便描述和分析，定義如下3種時鐘模型:34.3.1時間同步模型 速率恒定模型。速率恒定模型假定時鐘速率是恒定的，即晶振頻率沒有波動發(fā)生。當要求的時鐘精度遠低于頻率波動導致的偏差時，該模型的假定應該是合

37、理的。 漂移有界模型。定義時鐘速率 相對于理想速率1的偏差為時鐘漂移(drift) ，即 。漂移有界模型在工程實踐中非常有用，常用來確定時鐘的精度或誤差的上下界。 漂移變化有界模型。該模型假定時鐘漂移的變化 是有界的時鐘漂移的變化主要是溫度和電源電壓等因素發(fā)生變化所引起的，一般變化速率相對緩慢，可以通過適當?shù)难a償算法加以修正。44.3.1時間同步模型（2）節(jié)點邏輯時鐘模型任一節(jié)點i在物理時刻t的邏輯時鐘讀數(shù)可以表示為其中， 為當前本地時鐘讀數(shù)， 為頻率修正系數(shù)， 為初相位修正系數(shù)。采用邏輯時鐘的目的是對本地時鐘進行一定的換算以達成同步。為了同步任意兩個節(jié)點i和j，構(gòu)造邏輯時鐘有兩種途徑：一是根

38、據(jù)本地時鐘與物理時鐘等全局事件基準的關(guān)系進行變換,另一種是根據(jù)兩個節(jié)點本地時鐘的關(guān)系進行對應換算。兩種方法都估計了頻率修正系數(shù)和初相位修正系數(shù)，精度較高。對于低精度類應用，還可以簡單地根據(jù)本地時鐘和物理時鐘的差值以及本地時鐘兩兩之間的差值進行修正。54.3.1時間同步模型2通信模型節(jié)點時間校正技術(shù)是無線傳感器網(wǎng)絡(luò)時間同步的核心和基礎(chǔ)。目前主要的時間校正技術(shù)有單向報文傳遞、雙向報文交換、廣播參考報文和參數(shù)擬合技術(shù)。64.3.1時間同步模型（1）單向報文傳遞節(jié)點i在本地時間 時刻向節(jié)點j發(fā)送一個報文，包含時間戳 。假設(shè)節(jié)點j在本地時間 時刻收到上述報文。節(jié)點j不知道報文的傳遞時延d，所以只能對d進

39、行估計，如果知道d的上界和下界，則可以得到進而估計節(jié)點i和節(jié)點j之間的時間偏差公式為這種時間校正技術(shù)的精度最低，因為它假設(shè)報文傳遞過程中只有傳播延時，忽略了無線信道的許多不確定因素的影響。74.3.1時間同步模型（2）雙向報文交換雙向報文交換的時間校正技術(shù)要復雜很多。節(jié)點i在本地時鐘 時刻向節(jié)點j發(fā)送同步報文，節(jié)點j在本地時鐘時刻 接收到該報文，之后立即向節(jié)點i發(fā)送應答報文，節(jié)點i在本地時鐘時刻 接收到該應答報文。則報文的往返時間為D，大小為 ，報文的傳遞時延d在0D之間。如果知道d的上界和下界，節(jié)點j可以確定d在 和 之間。由此可以確定節(jié)點i、j之間的時間偏差為 假設(shè)上行報文和下行報文的時間

40、延遲相等，即 雙向報文交換是應用很廣泛的一種時間校正技術(shù)，精度比較高。但是網(wǎng)絡(luò)負載比較大，耗能較高，而且需要周期性地執(zhí)行同步過程。84.3.1時間同步模型（3）廣播參考報文它是利用第三個節(jié)點k作為參考節(jié)點，發(fā)送時間同步的參考廣播報文給相鄰的節(jié)點i和節(jié)點j。假設(shè)這個參考廣播報文到達節(jié)點i和節(jié)點j的時間延遲相等 。節(jié)點j收到參考廣播報文后，立即發(fā)送包含有 信息的報文給節(jié)點i，于是節(jié)點i就可以計算收到兩條報文的時間間隔D為廣播參考報文的方法只能使節(jié)點間的時鐘保持相對同步。94.3.1時間同步模型（4）參數(shù)擬合技術(shù)參數(shù)擬合技術(shù)可以同時計算出節(jié)點時鐘之間的頻率偏移和相位偏移。假設(shè)兩時鐘的時間之間滿足式其

41、中，和分別是兩個時鐘時間之間的相對頻率偏移和相位偏移。采用上述3種方法測量節(jié)點間時間偏差，在測量得到多組數(shù)據(jù)樣本后，就可以利用參數(shù)擬合技術(shù)計算時間的頻偏和相偏。參數(shù)擬合技術(shù)有線性回歸、鎖相環(huán)兩種實現(xiàn)方法。104.3.1時間同步模型3時鐘同步的誤差來源正確地估算本地時鐘與物理時鐘或本地時鐘之間的頻率偏差和相位偏差，是構(gòu)造邏輯時鐘的關(guān)鍵。節(jié)點通過交互同步信令估算相應的參數(shù)，然而同步信令在網(wǎng)絡(luò)上傳輸會產(chǎn)生不確定的時延，該時延的不確定性是影響同步精度的關(guān)鍵因素。正確估計同步信息的時延對提高同步精度意義重大，同步信息的時延包括以下幾部分：協(xié)議發(fā)送時延、接入時延、發(fā)送時延、傳播時延、接收時延、接收處理時延

42、114.3.1時間同步模型124.3.1時間同步模型課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.3.14.3.2時間同步模型時間同步協(xié)議無線傳感器網(wǎng)絡(luò)時間同步技術(shù)4.31時間同步的類別時間同步一般理解為使許多節(jié)點的時鐘顯示相同的時間，實際上有很多種不同類型的同步。下面對各種同步方法進行整體的介紹。在為給定的應用選擇同步算法時，要在最大程度滿足應用的同時盡可能將計算、存儲，尤其是能量開銷降到最低。14.3.2時間同步協(xié)議（1）時鐘速率同步與偏移同步速率同步是指各個傳感器節(jié)點測量所得的時間間隔相等，如公式

43、（4-35）所示： 在目標跟蹤、定位等應用中，節(jié)點時鐘速率同步是最低的同步要求。偏移同步是指傳感器節(jié)點在當前時刻t的時鐘時間顯示相等，即在時刻t傳感器節(jié)點的時鐘讀出時間同為T，而不管時鐘速率是否同步，如式（4-36）所示： 偏移同步對傳感器網(wǎng)絡(luò)中不同節(jié)點間的時戳結(jié)合是必須的。24.3.2時間同步協(xié)議（2）同步期限：長期同步與按需同步時間同步的同步期限是指同步要保持的時間長短。在長期同步的情況下，維持同步的代價是很大的，隨著時間的推移，節(jié)點間誤差逐漸增加，可能還需要周期性地再同步。按需同步是指傳感器節(jié)點的時間在相關(guān)事件發(fā)生前后進行同步，它不需要大量的維護同步的通信開銷，節(jié)省了通信帶寬和節(jié)點能量。

44、對一些傳感器網(wǎng)絡(luò)的應用，按需同步效率更高。34.3.2時間同步協(xié)議（3）同步范圍：全網(wǎng)同步與局部同步同步范圍是定義網(wǎng)絡(luò)中哪些節(jié)點式需要同步的。在有些情況下，范圍可能純粹是地理上的距離。而在其他情況下，邏輯距離更有用，如網(wǎng)絡(luò)中的跳數(shù)。根據(jù)不同的應用，范圍可能是網(wǎng)絡(luò)中所有節(jié)點或者部分節(jié)點。44.3.2時間同步協(xié)議（4）內(nèi)同步和外同步時間同步簡單的意思就是得到正確的時間，一般這個正確時間就是UTC。然而，一些應用只需要記錄事件發(fā)生的先后順序以及時間間隔，并不需要事件發(fā)生的絕對時間。這種情況下，只需要內(nèi)同步（相對同步），網(wǎng)絡(luò)必須內(nèi)部一致，不需要它們與外界標準時間保持一致性。另一類應用要求外同步（絕對同

45、步），即每個節(jié)點都要與外部時間標度（如UTC）保持同步。通常的環(huán)境監(jiān)控或者需要數(shù)據(jù)存檔的應用中，比較需要外同步，而且要求的同步期限比較長。54.3.2時間同步協(xié)議（5）發(fā)送者接收者同步與接收者接收者同步在進行發(fā)送者接收者同步時，發(fā)送者在報文中嵌入報文發(fā)送時間，而接收者在接收到報文后記錄下接收時間，并利用這些時間信息計算出收發(fā)雙方的時鐘偏移，進而達到收發(fā)雙方的時間同步。接收者接收者同步時，發(fā)送者發(fā)送一個同步報文到多個接收者，這些接收者通過對同一個報文時間的比較，計算出它們之間的時鐘偏移，從而達到接收者一接收者同步。64.3.2時間同步協(xié)議2典型的時間同步協(xié)議（1）LTS協(xié)議（2）RBS協(xié)議（3）

46、TPSN協(xié)議（4）DMTS協(xié)議（5）FTSP協(xié)議（6）幾種協(xié)議的比較74.3.2時間同步協(xié)議（1）LTS協(xié)議LTS（Lightweight Tree-based Synchronization）同步算法的設(shè)計目標就是適用于低成本、低復雜度的傳感器節(jié)點時間同步，側(cè)重最小化同步的能量開銷，同時具有魯棒性和自配置的特點。Anceaume和Puaut把時間同步模塊劃分為3個組成部件：重同步監(jiān)測、遠程時鐘估計和時鐘修正。重同步時間監(jiān)測用來確定節(jié)點進行時間同步的時刻。兩種方式確定重同步時刻：一種是基于初始同步的時間，以kR固定周期進行重同步，R是單個時間同步周期的長度，k是大于1的實數(shù)，用來防止兩個同步周

47、期的重疊；另一種是一個特定節(jié)點在kR時間后發(fā)送初始同步消息給其他節(jié)點，節(jié)點在收到消息后啟動時間同步。遠程時鐘估計部件用來決定網(wǎng)絡(luò)中另一個節(jié)點的本地時鐘。84.3.2時間同步協(xié)議（2）RBS協(xié)議2002年12月，Jeremy Elson等提出參考廣播同步機制（Reference Broadcast Synchronization，RBS），該機制利用了無線數(shù)據(jù)鏈路層的廣播信道特性，一個節(jié)點發(fā)送廣播消息，接收到廣播消息的一組節(jié)點通過比較各自接收到廣播消息的同步時刻，來實現(xiàn)它們之間的時間同步。RBS算法通過接收節(jié)點對時抵消發(fā)送時間和訪問時間，發(fā)送節(jié)點廣播一個信標分組，廣播域中兩個節(jié)點都能接收到這個分組，交換接收時間，兩個接收時間的差值相當于兩個接收節(jié)點間的時間差值，其中一個節(jié)點可以根據(jù)這個時間差值更改它的本地時間，從而實現(xiàn)兩個節(jié)點的時間同步。94.3.2時間同步協(xié)議104.3.2時間同步協(xié)議（3）TPSN協(xié)議2003年11月，Saurabh Ganer