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

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

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

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

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

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

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

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

8、加而衰減,表明信號強(qiáng)度變化與傳播距離間存在著某種函數(shù)關(guān)系。無線信道的數(shù)學(xué)模型如式： d是發(fā)射機(jī)和接收機(jī)之間的距離，d0是參考距離；n是信道衰減指數(shù)，一般取值24；X是均值為零、方差的高斯隨機(jī)變量；PL(d0)是距離發(fā)射機(jī)d0處的信號強(qiáng)度。它是一種低功率、廉價(jià)的測距技術(shù)，但是信號強(qiáng)度很容易受到周圍環(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í)間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.1.14.1.2無線傳感器網(wǎng)絡(luò)測距技術(shù)無線傳感器網(wǎng)絡(luò)定位機(jī)制與性能評價(jià)標(biāo)準(zhǔn)現(xiàn)有無線傳感器

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

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

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

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

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

14、位精度，網(wǎng)絡(luò)節(jié)點(diǎn)能量耗盡、物理損傷等自身原因而過早死亡，引起其他節(jié)點(diǎn)的定位過程中斷或者不能實(shí)現(xiàn)等諸多情況。因此，定位系統(tǒng)要有一定的容錯(cuò)性和魯棒性從而減小定位誤差提高定位精度，以更好地適應(yīng)周圍環(huán)境。134.1.2無線傳感器網(wǎng)絡(luò)定位機(jī)制與性能評價(jià)標(biāo)準(zhǔn)課程目錄4.14.2無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)跟蹤技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)4.3無線傳感器網(wǎng)絡(luò)的發(fā)展與安全趨勢課程目錄4.1.14.1.2無線傳感器網(wǎng)絡(luò)測距技術(shù)無線傳感器網(wǎng)絡(luò)定位機(jī)制與性能評價(jià)標(biāo)準(zhǔn)現(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é)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)計(jì)算靜止或者移動(dòng)目標(biāo)在大樓內(nèi)具體房間的哪一區(qū)域，而不是絕對位置。Cricket系統(tǒng)沒有中心管理或者控制系統(tǒng)，而是分布式管理，為了更好地通信，把信標(biāo)節(jié)點(diǎn)和發(fā)射器布置在天花板上。24.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法2質(zhì)心定位算法質(zhì)心定位算法是一種與距離無關(guān)的估計(jì)定位算法，質(zhì)心也即多邊形的幾何中心，多邊形的頂點(diǎn)坐標(biāo)的平均值為質(zhì)心坐標(biāo)。多邊

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

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

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

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

20、的方位角。當(dāng)節(jié)點(diǎn)A的兩個(gè)接收機(jī)收到節(jié)點(diǎn)B的信號后，利用TOA技術(shù)測出x1、x2，然后再根據(jù)幾何關(guān)系可以推導(dǎo)出節(jié)點(diǎn)B相對于節(jié)點(diǎn)A的方位角。74.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法84.1.3現(xiàn)有無線傳感器網(wǎng)絡(luò)定位方法利用上面的方法，分別測得相鄰3個(gè)節(jié)點(diǎn)的相對各自的方位角，如節(jié)點(diǎn)B相對節(jié)點(diǎn)A的方位角為ab，同樣可以測得節(jié)點(diǎn)C相對于節(jié)點(diǎn)A的方位角ac，由此可得：CAB=acab。如果節(jié)點(diǎn)B是已知方向的節(jié)點(diǎn)，它的軸線相對于指南針方向角為b，則可以根據(jù)幾何知識推導(dǎo)出節(jié)點(diǎn)A的軸線相對于指南針的方向角為 。由此可知，該算法還可以實(shí)現(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é)點(diǎn)根據(jù)接收到的信號強(qiáng)度值計(jì)算信號的傳播損耗，按照相應(yīng)的傳播損耗模型將傳播損耗轉(zhuǎn)化為距離，然后再根據(jù)三邊定位法或者多邊極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的位置。SpotON項(xiàng)目，微軟的RADAR系統(tǒng)都利用了RSSI測距技術(shù)。RADAR是一個(gè)基于RSSI測距的室內(nèi)定位系統(tǒng)，用于確定用戶所在樓層的具體位置。它一般使用信號傳播經(jīng)驗(yàn)?zāi)Ｐ秃屠碚撃Ｐ蛢煞N方法進(jìn)行未知節(jié)點(diǎn)的定位?；赗SSI的定位受到周圍環(huán)境的影響很大，定位精度不穩(wěn)定，尤其是在室外，影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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