無線傳感器網(wǎng)絡(luò)技術(shù)概論課件：無線傳感器網(wǎng)絡(luò)其他關(guān)鍵技術(shù)

無線傳感器網(wǎng)絡(luò)其他關(guān)鍵技術(shù)9.1時間同步機制9.2無線傳感器網(wǎng)絡(luò)定位技術(shù)9.3數(shù)據(jù)融合技術(shù)9.4無線傳感器網(wǎng)絡(luò)目標跟蹤技術(shù)思考題

9.1時間同步機制

9.1.1時間同步面臨的問題

在無線傳感器網(wǎng)絡(luò)中，單個節(jié)點的能力非常有限，整個系統(tǒng)所有功能的實現(xiàn)需要網(wǎng)絡(luò)內(nèi)所有節(jié)點相互配合共同完成，時間同步在無線傳感器網(wǎng)絡(luò)中起著非常重要的作用。在分布式系統(tǒng)中，時間可分為“邏輯時間”和“物理時間”?！斑壿嫊r間”的概念是建立在Lamport提出的超前關(guān)系上，體現(xiàn)了系統(tǒng)內(nèi)時間發(fā)生的邏輯順序。

而“物理時間”是用來描述在分布式系統(tǒng)中所傳遞的一定意義上的人類時間。對于直接觀測物理世界現(xiàn)象的無線傳感器網(wǎng)絡(luò)系統(tǒng)來說，物理時間更為重要，因為現(xiàn)象發(fā)生的時間本身就是一個非常重要的信息。此外，節(jié)點間的協(xié)同信號處理、節(jié)點間通信的調(diào)度算法等都對系統(tǒng)提出了不同精度的物理時間同步要求。

如果將時鐘偏移定義為某個時間段內(nèi)兩個時鐘之間因為漂移而產(chǎn)生的時間差，那么分布式系統(tǒng)物理時鐘服務(wù)就定義了一個系統(tǒng)中所允許的時鐘偏移的最大值。只要兩個時鐘之間的差值小于所定義的最大時鐘偏移量，就可以認為這兩個時鐘保持了同步。

在無線傳感器網(wǎng)絡(luò)中完成節(jié)點間的時間同步面臨以下幾個問題：

(1)??GPS可以將本地時鐘與世界時鐘同步，但體積、成本、能耗等方面的限制使得無線傳感器網(wǎng)絡(luò)中的絕大部分節(jié)點不具備GPS功能。

(2)節(jié)點間通過無線多跳的方式進行數(shù)據(jù)交換，在低速低帶寬的條件下，同步信號傳輸過程中的延遲具有很大不確定性。

(3)底層協(xié)議的節(jié)能操作使得節(jié)點在大部分時間都處于“睡眠狀態(tài)”，不能在系統(tǒng)運行期間持續(xù)地保持時間同步。

(4)由于環(huán)境、能量等因素的影響，節(jié)點易損壞，無線傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)頻繁變化，不可能對時間基準的獲取路徑進行靜態(tài)配置。

(5)在網(wǎng)絡(luò)規(guī)模較大的情況下，實現(xiàn)全局時鐘同步很難保證全局同步，精度具有確定的上限限制。

9.1.2時鐘模型

為了分析不同的時間同步方法，有必要在闡述時間同步問題之前為其建立一個模型，用以描述無線傳感器網(wǎng)絡(luò)時間同步過程中涉及的各種問題。一般地，理想的時鐘以固定的時間間隔計數(shù)來測量時間。

假設(shè)：

(1)?t時刻時鐘代表的時間為h(t)，它是一個真實時間的函數(shù)。

(2)時鐘頻率為f，它是h(t)的一階導(dǎo)數(shù)，即f(t)?=?dh(t)/dt。

如果有一塊秒表，使用者從秒表讀出的時間為h(t)，它是一個連續(xù)函數(shù)。顯然，只要秒表還在運轉(zhuǎn)，讀出的時間就會不斷增加。因此，h(t)是單調(diào)增函數(shù)。因為秒表的讀數(shù)每秒增加1，所以秒表的頻率f為1。對于一般的時鐘來說，h(t)是單調(diào)增函數(shù)，必然有f(t)＞0。理想的時鐘頻率應(yīng)該始終為常數(shù)1，但實際上真實的時鐘頻率總會受到電壓、溫度等因

素的影響而隨時間變化。根據(jù)時鐘頻率漂移的不同假設(shè)，可以用不同的模型來描述時鐘的特性。

(1)常速率模型：當需要的時鐘精度與時鐘頻率的波動相比較小的時候，可以假設(shè)時鐘頻率是常數(shù)。

(2)有界漂移模型：假設(shè)時鐘頻率相對于理想時鐘頻率的偏移是有界的。由于理想的時鐘頻率為1，可以定義時鐘漂移為

(9-1)

且

(9-2)

這種假設(shè)限制了r?(t)在上界和下界之間跳變。如果時鐘的漂移僅僅受到溫度、電壓等漸變環(huán)境因素的影響，這樣的假設(shè)顯然是合理的。

傳感器網(wǎng)絡(luò)時間同步算法是由單跳同步策略和多跳同步策略組成，其設(shè)計參數(shù)包括單跳和多跳的同步精度、再次同步的時間間隔以及同步開銷等。在接收者和接收者之間，同步算法主要可以分為以下三類：

①交互同步算法。

②雙向同步算法。

③單向同步算法。

9.1.3接收者和接收者交互時間同步機制

在接收者和接收者之間采用的交互時間同步機制，就是第三方節(jié)點廣播若干次同步信令，廣播域內(nèi)各節(jié)點利用本地時鐘記錄信令的到達時刻，然后各接收節(jié)點之間交互時間記錄，進而兩兩校準時鐘。其代表性算法有RBS(ReferenceBroadcastSynchronization)算法。

RBS機制可以用來構(gòu)造局部時間，對于需要時間同步但不需要絕對時間的傳感器網(wǎng)絡(luò)應(yīng)用非常有用。RBS算法是利用不同廣播域相交區(qū)域內(nèi)，節(jié)點起時間轉(zhuǎn)換作用實現(xiàn)多跳時鐘同步的。對于兩個接收節(jié)點，RBS機制需要發(fā)送3個消息和接收4個消息。對于單個廣播域內(nèi)的n個節(jié)點和m個廣播消息，RBS機制的復(fù)雜度是O(mn)。

在實際傳感器網(wǎng)絡(luò)中，發(fā)送節(jié)點往往也需要同步，因此需要另一個節(jié)點同樣成為發(fā)送節(jié)點來發(fā)送廣播消息。用于多跳網(wǎng)絡(luò)的RBS機制需要依賴有效的分簇方法，保證簇之間具有共同節(jié)點以便簇間進行時間同步，但在多跳網(wǎng)絡(luò)中的誤差隨跳數(shù)增加而增加。

RBS算法的主要優(yōu)點：

①通過廣播信道來同步接收節(jié)點之間的局部時鐘，消除了關(guān)鍵路徑中的許多不確定性延時，提高了同步精度。

②RBS允許節(jié)點建立本地時間表，這對于僅需要局部時間同步的無線傳感器網(wǎng)絡(luò)應(yīng)用較為高效。

RBS算法的主要缺點：

①RBS協(xié)議不適用于點對點網(wǎng)絡(luò)，且無法應(yīng)用于需要與世界時鐘同步的場景。

②對于擁有n個節(jié)點的單跳網(wǎng)絡(luò)，RBS算法需要O(n2)次的消息交換，這對于大規(guī)模網(wǎng)絡(luò)來說計算代價較高。

③由于信息交換量大，實現(xiàn)整網(wǎng)同步的收斂時間較長。

9.1.4發(fā)送者和接收者的雙向時間同步機制

發(fā)送者和接收者雙向同步機制首先由待同步節(jié)點向基準節(jié)點發(fā)送同步請求包，然后基準節(jié)點回饋包含當前時間的同步包，最后待同步節(jié)點估算時延，并校準時鐘。這類同步機制的代表性算法有TPSN(TimesyncProtocolforSensorNetwork)算法，LTS(LightweightTree-basedSynchronization)算法，Tiny-sync與Mini-sync算法。

1．TPSN算法

TPSN算法采用在發(fā)送者與接收者之間雙向交換消息的方法，達到兩節(jié)點間的時間同步，并將其擴展到全網(wǎng)域的時間同步。TPSN算法采用鏈路層打時間戳技術(shù)，減少了發(fā)送方產(chǎn)生的不確定因素的影響，并通過構(gòu)造分層網(wǎng)絡(luò)實現(xiàn)多跳同步，其同步過程如圖9-1所示。

在TPSN算法中，待同步客戶機A向同步服務(wù)器B發(fā)送同步請求并記錄此時的本地時間T1，B收到該包后記錄本地時間T2，經(jīng)過一段時間后發(fā)送同步回應(yīng)包，附帶此時此刻的T3以及T2，A收到后記錄本地時間T4。通過同步信令的交互，估計往返時延d和時間偏差σ，可實現(xiàn)1～50ms精度計算機校時。

圖9-1TPSN算法的同步過程

在相同的硬件條件下，TPSN算法的同步精度能達到RBS算法精度的兩倍。該算法的關(guān)鍵是在發(fā)送方底層打時間戳，消除了大多數(shù)不確定性影響因素，使得同步結(jié)果更為準確。因此，在傳感器網(wǎng)絡(luò)中，雙向同步機制比經(jīng)典同步機制更為有效。

TSPN算法的主要優(yōu)點：

①TSPN算法的雙向同步精度不會隨著傳感器網(wǎng)絡(luò)規(guī)模的擴大而明顯惡化。

②達到全網(wǎng)范圍的時間同步所花費的代價比NTP協(xié)議花費的代價要小。

TPSN算法的主要缺點：

①TPSN算法沒有對時鐘的頻差進行估計，這使得它需要頻繁同步，開銷較大。

②因為該協(xié)議需要分級的基礎(chǔ)結(jié)構(gòu)，所以它不適用于感知節(jié)點移動速度較快的應(yīng)用場景。

③TPSN算法不支持多跳的信息交互。

2．LTS算法

LTS時間同步算法的基本思想是通過犧牲一定精度來減少能量開銷，它基于以下考慮：一般場景下，傳感器網(wǎng)絡(luò)對時間精度的要求并不是很高(幾分之一秒以內(nèi))，而對能量消耗卻限制嚴格。因此，在傳感器網(wǎng)絡(luò)中，應(yīng)用一個輕量級的同步機制就能夠滿足應(yīng)用的需求。

LTS算法主要用于全局時間同步，算法首先構(gòu)造一個低深度生成樹T，參考節(jié)點為樹T的根，它肩負著在有需要時發(fā)起“再同步”的責(zé)任，然后沿著樹T的邊進行成對同步，參考節(jié)點通過與它的所有直接子節(jié)點繼續(xù)成對同步來初始化整個同步過程。

通過假設(shè)時鐘漂移被限定和需要的精確度已給出，參考節(jié)點計算單個同步操作有效的時間周期，假如需要可以進行“再同步”。參考節(jié)點的子節(jié)點又與它們自己的子節(jié)點進行成對同步，整個過程直到T的葉子節(jié)點被同步時終止。生成樹的深度影響著整個網(wǎng)絡(luò)達成同步所需的時間以及樹葉節(jié)點的精確度誤差，因此根節(jié)點可以根據(jù)反饋得到的生成樹的數(shù)來調(diào)整“再同步”的精度。因為LTS算法只沿生成樹的邊進行成對同步，所以成對同步次數(shù)是生成樹邊數(shù)的線性函數(shù)，這與簡單地將成對同步擴展到多跳同步的方法相比(要求n2次成對同步)，極大地減少了成對同步的系統(tǒng)開銷，但也在一定程度上降低了同步的精確度。

LTS算法的主要優(yōu)點是犧牲精度換取簡單的復(fù)雜度，因此算法能耗較少，延長了整個網(wǎng)絡(luò)的生存周期。

LTS算法的主要缺點：

①它主要應(yīng)用于全局時間同步，當部分節(jié)點需要頻繁同步時，效率較低。

②LTS算法精度較低，難以滿足所有場景要求。

3．Tiny-sync與Mini-sync算法

一般方法中，計算節(jié)點間時鐘的頻偏和相偏通常采用收集大量數(shù)據(jù)采集點信息，然后通過擬合的方法處理，這樣就需要較大的通信量、存儲空間和計算量，為此出現(xiàn)了Tiny-sync與Mini-sync算法。它們是針對傳感器網(wǎng)絡(luò)提出的兩個輕量級的同步算法。

Tiny-sync的基本原理如下：假設(shè)每個時鐘能夠與固定頻率的振蕩器近似，采用傳統(tǒng)的雙向消息交換來估計節(jié)點時鐘間的相對漂移和相對偏移，并建立偏移和漂移的上下限。在每次獲得新的數(shù)據(jù)點時，首先與以前的數(shù)據(jù)點比較，若新的數(shù)據(jù)點計算出的誤差大于以前數(shù)據(jù)點計算的誤差，則拋棄新的數(shù)據(jù)點，采用舊的數(shù)據(jù)點；反之采用新的數(shù)據(jù)點，拋棄舊的數(shù)據(jù)點。

iny-sync算法建立的根本原則是并非所有的數(shù)據(jù)點都是有用的，因此Tiny-sync算法僅需存儲三四個數(shù)據(jù)點的信息，就可以實現(xiàn)一定精度的時間同步，有效降低存儲需求和計算量。Tiny-sync同步算法利用了所有的數(shù)據(jù)信息，只是通過實時處理使得保留的數(shù)據(jù)總是很少，但是在某些情況下可能丟失即將用到的且更為有用的數(shù)據(jù)采集點。

Mini-sync算法是為了克服Tiny-sync算法丟失有用數(shù)據(jù)點的缺點而提出的，通過建立更有效的約束條件來確保僅丟掉將來不會用到的數(shù)據(jù)點，并且每次獲取新的數(shù)據(jù)點后都更新約束條件，但這樣也增加了Mini-sync算法的復(fù)雜度。

Tiny-sync和Mini-sync算法的主要優(yōu)點：

①Tiny-sync和Mini-sync為輕量級算法，通過交換少量的信息就能夠提供具有確定誤差上界的頻偏和相偏估計，能量利用率較高。

②它們所占用的網(wǎng)絡(luò)通信帶寬、存儲容量和處理能力等資源較少，能較好地滿足無線傳感器網(wǎng)絡(luò)的需求。

9.1.5發(fā)送者和接收者的單向時間同步機制

在單向時間同步機制模型中，首先選擇某節(jié)點充當時間基準點，發(fā)送包含當前時鐘讀數(shù)的同步信令，其他節(jié)點接收到該同步信令后，估算時延等參數(shù)并調(diào)整自己的時鐘，以與基準點達成同步。周圍節(jié)點在和基準點同步后作為新的基準點，一環(huán)環(huán)向外同步，直至覆蓋整個網(wǎng)絡(luò)。這種同步機制的代表性算法有基于時延測量的DMTS(DelayMeasurementTimeSynchronization)算法和基于泛洪的FTSP(FloodingTimeSynchronizationProtocol)算法，而這均基于MicaMote硬件平臺。

1．DMTS算法

無線傳感器網(wǎng)絡(luò)的一個突出特點是其自組織性及動態(tài)特性，自組織性意味著網(wǎng)絡(luò)拓撲可能隨著時間的推移而發(fā)生變化。DMTS算法實現(xiàn)策略是犧牲部分時鐘同步精度換取較低的計算復(fù)雜度和能耗，其重點在于可測量性以及自適應(yīng)性。這就意味著DMTS算法對網(wǎng)絡(luò)拓撲的變化不敏感，具有可適應(yīng)性。

DMTS算法的具體同步過程如下：首先選擇一個基準節(jié)點用以廣播自己本地時鐘，基準節(jié)點先發(fā)送前導(dǎo)碼和同步碼，而后才發(fā)送數(shù)據(jù)。鏈路層在發(fā)送前導(dǎo)碼和同步碼時，給同步信令包打上時間戳T。接收節(jié)點收到前導(dǎo)碼和同步碼后，記錄此時自己的本地時間T1。在開始處理接收到的數(shù)據(jù)包時，記錄此時的本地時間T2。若電磁波的傳播時延忽略不計，則全部的時延為發(fā)送前導(dǎo)碼和同步碼時延加上T2和T1的差，設(shè)前導(dǎo)碼和同步碼共有n位，發(fā)送一位所需時間為τ，則接收節(jié)點的時鐘應(yīng)調(diào)整為

Tr

=

T

+

nt

+

(T2-T1)

(9-6)

根據(jù)式(9-6)，周圍的接收節(jié)點即可同步到基準節(jié)點。DMTS算法的最低精度是無線電設(shè)備的同步精度，最高的精度是本地時鐘的精度。因為DMTS算法在單跳范圍內(nèi)只需要一次消息傳送就可以實現(xiàn)所有節(jié)點的時間同步，所以DMTS是能量有效的算法。又因為在整個過程中沒有復(fù)雜的執(zhí)行過程，因此DMTS也是一個輕量級的算法。

DMTS算法的主要優(yōu)點為計算復(fù)雜度較低、能量利用率較高；但其主要缺點也比較明顯，它只能應(yīng)用于低分辨率、低外部時鐘交換頻率的場景，是用精度換取低計算復(fù)雜度的算法。

2．FTSP算法

FTSP算法的目標是通過多跳同步實現(xiàn)全網(wǎng)范圍內(nèi)的時間同步，并綜合考慮了能量效率、可擴展性、健壯性、適應(yīng)動態(tài)拓撲和及時性等多種因素，精度可達微秒級。FTSP算法通過一個在發(fā)送端和接收端都打上時間戳的簡單無線電信息，實現(xiàn)讓盡可能多的接收節(jié)點與發(fā)送節(jié)點時間同步的目的。FTSP算法假設(shè)每個節(jié)點均有唯一的身份識別碼(ID)，可以在無線信道中發(fā)送廣播信息。作為發(fā)送端的節(jié)點周期性發(fā)送多個廣播信息，其廣播域內(nèi)鄰近節(jié)點利用時間同步數(shù)據(jù)構(gòu)造最佳回歸直線，估算時鐘漂移和偏移，并建立線性回歸表。

FTSP算法的多跳同步也采用層次樹形結(jié)構(gòu)逐級同步，使所有節(jié)點都同步到根節(jié)點。層次網(wǎng)絡(luò)的根節(jié)點由動態(tài)選舉產(chǎn)生，保證其他所有節(jié)點都與根節(jié)點保持時間同步。此外，F(xiàn)TSP算法將分組交換的傳輸延遲進一步細化分解，仔細分析各種延遲的產(chǎn)生原因并盡力減小不確定性延遲的影響，提高同步精度。

FTSP算法的主要優(yōu)點：

①通過對收發(fā)過程的分析，把時延細分為發(fā)送中斷處理時延、編碼時延、傳播時延、解碼時延、字節(jié)對齊時延、接收中斷處理時延，進一步降低時延的不確定度。

②采用節(jié)點選舉機制，針對節(jié)點失效、新節(jié)點加入、拓撲變化等情況進行優(yōu)化，這使得它具有較高的魯棒性，精度達到了微秒級。

FTSP算法的主要缺點：

①通過對多個樣本數(shù)據(jù)進行線性回歸處理來估計漂移量，對應(yīng)算法的空間復(fù)雜度相對較大。

②需要對傳輸過程中的時延進行仔細地分析，并建立合適的分布模型，這就需要對傳感器節(jié)點的硬件有深入了解，因此FTSP協(xié)議對硬件的依賴性比較強。

9.1.6時間同步機制的誤差來源及性能指標

從前文的描述中可以知道，無線傳感器網(wǎng)絡(luò)中時間同步過程主要面臨以下兩個問題：一是由于傳感器節(jié)點使用的時鐘受自身特點以及溫度、電壓等外部環(huán)境因素的影響，其準確性會隨時間不斷惡化，甚至發(fā)生跳變，導(dǎo)致不同節(jié)點的時鐘之間出現(xiàn)偏差，從而失去共同的時間基準；二是為了補償節(jié)點間的時間偏差，節(jié)點之間需要交換彼此的時間信息，而消息時延的隨機性又增加了時間信息交換過程中的不確定性。

傳感器節(jié)點時鐘漂移和時間消息交換過程中時延的不確定性對時間同步的影響可以分開研究。在某些情況下時鐘漂移的影響更明顯。例如，在很多傳感器網(wǎng)絡(luò)中節(jié)點間的通信并不頻繁，節(jié)點本地時鐘漂移造成的累積偏差會隨著時間的增加越來越大，而節(jié)點間的通信時延卻可以認為是基本不變的。假設(shè)消息傳遞的時延的不確定性為1?μs，而時鐘漂移為10×10-6；50?s以后時鐘造成的誤差就和時延不確定性相等；1?h以后時鐘誤差已經(jīng)是時延不確定性的72倍。因此，在這種情況下忽略時延的不確定性是完全可以接受的。

所有網(wǎng)絡(luò)的時間同步機制均依靠節(jié)點間的某種消息交換。傳輸時間或物理信道接入時間等網(wǎng)絡(luò)的動態(tài)不確定性會使很多系統(tǒng)中的同步任務(wù)具有挑戰(zhàn)性。當網(wǎng)絡(luò)中的節(jié)點產(chǎn)生時間戳并發(fā)送給另一個節(jié)點時，攜帶時間戳的包在到達它的目的接收者和解碼之前將面臨著各種延遲。這些延遲破壞了節(jié)點間本地時鐘的比較，進而破壞了節(jié)點間的時間同步。

一般把網(wǎng)絡(luò)時間同步的誤差來源分解成以下四個部分：

①發(fā)送時間。發(fā)送者創(chuàng)建消息的時間，包括操作系統(tǒng)的能耗和傳輸消息到網(wǎng)絡(luò)接口的時間。

②接入時間。每個包發(fā)送之前在MAC層面臨著很多延遲，如等待空閑信道或者TDMA中的時隙，它主要來自于MAC層的調(diào)度。

③傳輸時間。發(fā)送者和接收者的網(wǎng)絡(luò)接口之間傳輸信息所消耗的時間。

④接收時間。接收者的網(wǎng)絡(luò)接口接收消息并傳送給主機所消耗的時間。

目前已經(jīng)有多種適用于無線傳感器網(wǎng)絡(luò)環(huán)境的時間同步協(xié)議，這些協(xié)議可以有效地實現(xiàn)傳感器節(jié)點點對點的時間同步或傳感器節(jié)點的全局時間同步。傳感器節(jié)點點對點的時間同步是指鄰居節(jié)點間獲得高精度的相互時間同步。而傳感器節(jié)點的全局時間同步是指整個無線傳感器網(wǎng)絡(luò)中所有節(jié)點共享一個全局時鐘。

無線傳感器網(wǎng)絡(luò)時間同步算法的性能一般包括同步精確度、可擴展性、穩(wěn)定性、效率、健壯性、同步期限、同步有效范圍、成本和體積等指標。

(1)同步精確度。同步精確度是指同步誤差的大小，即一組傳感器節(jié)點之間的最大時間差量，或相對外部標準時間的最大時間差量。精確度的需求依賴于時間同步的目的和應(yīng)用。對于某些應(yīng)用，只需要知道時間和消息的先后順序就可以了，而有的應(yīng)用則要求同步精度到微秒。

(2)可擴展性。無線傳感器網(wǎng)絡(luò)需要部署大量的傳感器節(jié)點，時間同步機制應(yīng)該能夠適應(yīng)這種網(wǎng)絡(luò)部署范圍或節(jié)點密度的變化。

(3)穩(wěn)定性。無線傳感器網(wǎng)絡(luò)因環(huán)境因素以及節(jié)點自身的變化導(dǎo)致網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)變化，時間同步機制能夠在網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)變化中保持同步的連續(xù)性和精度的穩(wěn)

定性。

(4)效率。它是指達到時間同步精度所經(jīng)歷的時間和消耗的能量。需要交換的同步消息越多，經(jīng)歷的時間越長，網(wǎng)絡(luò)消耗的能量就越大，同步的效率則相對越低。

(5)健壯性。無線傳感器網(wǎng)絡(luò)可能在復(fù)雜監(jiān)測區(qū)域內(nèi)長時間無人管理，一旦某些節(jié)點損毀或失效，在整個無線傳感器網(wǎng)絡(luò)中，時間同步機制應(yīng)該繼續(xù)保持有效且功能健全。

(6)同步期限。節(jié)點需要一直保持時間同步的時間長度。無線傳感器網(wǎng)絡(luò)需要在各種時間長度內(nèi)保持時間同步，包括瞬間同步以及伴隨網(wǎng)絡(luò)存在的永久同步。

(7)同步有效范圍。時間同步機制可以給網(wǎng)絡(luò)內(nèi)所有的節(jié)點提供時間，也可以給局部區(qū)域內(nèi)的部分節(jié)點提供時間。對于面積較大的無線傳感器網(wǎng)絡(luò)，由于可擴展性的原因，能量和帶寬的利用是昂貴的，全面的時間同步有很大難度。另外，大量節(jié)點在同一時間需要收集來自遙遠節(jié)點的用于全面同步的數(shù)據(jù)，這對于大規(guī)模的無線傳感器網(wǎng)絡(luò)是難以實現(xiàn)的，而且直接影響同步的精確度。

(8)成本和體積。時間同步可能需要特定的硬件，在無線傳感器網(wǎng)絡(luò)中需要考慮部件的成本和體積，采用低成本、微型化的時間同步硬件是傳感器網(wǎng)絡(luò)系統(tǒng)構(gòu)成的重要要求。

9.1.7時間同步機制的主要應(yīng)用

時間同步時無線傳感器網(wǎng)絡(luò)的基本中間件對其他中間件以及各種應(yīng)用都起著基礎(chǔ)性作用，一些常見的應(yīng)用如下：

(1)低功耗MAC協(xié)議。主動發(fā)送分組與被動偵聽無線信道消耗的能量是相當?shù)?，因此盡可能地關(guān)閉無線通信模塊是無線傳感器網(wǎng)絡(luò)MAC層協(xié)議設(shè)計的一個基本原則。為了節(jié)省能量，節(jié)點只有在交換無線信息時短暫蘇醒，在快速完成通信后再次進入睡眠狀態(tài)。如果MAC協(xié)議采用最直接的時分多路復(fù)用方法，那么達到上述目標可以利用占空比進行調(diào)節(jié)。但參與通信的雙方首先要實現(xiàn)時間同步，而且同步精度越高，防護頻帶越小，對應(yīng)消耗的能量也越少。所以低功耗MAC協(xié)議的技術(shù)基礎(chǔ)是高精度的時間同步。

(2)測距定位。如果無線傳感器網(wǎng)絡(luò)中的節(jié)點保持時間同步，那么很容易確定時間節(jié)點間的信號傳輸時間。由于信號在介質(zhì)中的傳播速度是一定的，距離很容易根據(jù)信息傳輸時間得到。因此，時間同步直接決定了測距的精度。

(3)協(xié)作傳輸?shù)囊蟆Ｒ话闱闆r下，由于無線傳感器網(wǎng)絡(luò)節(jié)點的傳輸功率的局限性，節(jié)點無法和遠方基站直接通信。因此，通過網(wǎng)絡(luò)內(nèi)多個節(jié)點同時發(fā)送相同的信息，利用電磁波的能量疊加效應(yīng)，遠方基站將會在瞬間感應(yīng)到一個功率很強的信號，以此實現(xiàn)直接向遠處節(jié)點傳輸信息的目的。同時，實現(xiàn)協(xié)作傳輸?shù)幕厩疤崾蔷_的時間同步，而且需要新型的調(diào)制解調(diào)的方式。

(4)多傳感器數(shù)據(jù)壓縮與融合。當傳感器節(jié)點的分布相對集中時，多個傳感器節(jié)點將會接收到同一事件。如果基站節(jié)點直接對發(fā)給它的所有事件進行處理，將浪費很多的網(wǎng)絡(luò)帶寬。另外，因為計算開銷遠低于通信開銷，所以正確識別一組鄰近節(jié)點所偵測到的相同事件，然后對重復(fù)的信息進行整理壓縮后再傳輸將會節(jié)省大量的電能。為了能夠正確判斷重復(fù)信息，可以為每個事件標記一個時間戳，通過該時間戳就可以識別重復(fù)事件。精確的時間同步能更有效地識別重復(fù)事件。

不同的應(yīng)用場合對無線傳感器網(wǎng)絡(luò)時間同步會有不同的指標要求，包括同步持續(xù)期、同步范圍、同步精度和節(jié)能效率等。對于目標/事件檢測類應(yīng)用，由于只有目標或事件發(fā)生點附近的節(jié)點需要進行協(xié)同檢測，同步只需要在小范圍進行，同步的有效期也不需要很長。

但是對于目標跟蹤類的應(yīng)用，由于目標運動軌跡附近的節(jié)點都需要同步，同步的范圍較大，同步的有效期可能較長，一些目標的定位所需要信號處理技術(shù)也對時間同步精度提出較高要求。因此，針對不同的應(yīng)用需求，無線傳感器網(wǎng)絡(luò)應(yīng)采用多種時間同步機制。

對于大規(guī)模無線傳感器網(wǎng)絡(luò)來說，時間同步要解決三個方面問題：

①盡量減少“關(guān)鍵路徑”中引起時間不確定性的環(huán)節(jié)。

②在跨多個廣播域范圍內(nèi)進行同步時，需要解決時間基準的傳遞問題。

③如何減少時間同步的通信開銷是一個要綜合考慮的問題。

9.2無線傳感器網(wǎng)絡(luò)定位技術(shù)

9.2.1無線傳感器網(wǎng)絡(luò)節(jié)點定位的基本原理

無線傳感器網(wǎng)絡(luò)節(jié)點定位的目的是獲取各傳感器節(jié)點在平面或空間中的絕對或相對位置信息，因為在傳感器網(wǎng)絡(luò)的許多應(yīng)用中，用戶關(guān)心的一個重要問題就是在什么位置或區(qū)域發(fā)生了什么事件。例如，在目標跟蹤、入侵檢測、環(huán)境安全檢測等應(yīng)用中，感知數(shù)據(jù)的位置信息是至關(guān)重要的。若無法獲得傳感器節(jié)點自身的位置，感知的數(shù)據(jù)就沒有意義。

傳感器節(jié)點為用戶提供其所在環(huán)境的上下文相關(guān)信息，其中80%的信息與位置信息有關(guān)，甚至在有些應(yīng)用中只需發(fā)回單純的位置信息即可。因此，傳感器網(wǎng)絡(luò)節(jié)點感知、采集的數(shù)據(jù)必須綁定其位置信息，從而實現(xiàn)對感知、采集的數(shù)據(jù)的有效應(yīng)用。

節(jié)點定位機制是指依靠有限的位置已知的節(jié)點，確定布設(shè)區(qū)中其他節(jié)點的位置，在傳感器節(jié)點間建立起空間關(guān)系的機制。與傳統(tǒng)計算機網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)在計算機軟硬件所組成的計算世界與實際物理世界之間建立了更為緊密的聯(lián)系，高密度的傳感器節(jié)點通過近距離觀測物理現(xiàn)象極大地提高了信息的“保真度”。

全球定位系統(tǒng)已經(jīng)在許多領(lǐng)域得到了應(yīng)用，但為每個節(jié)點配備GPS接收裝置是不現(xiàn)實的。其原因主要有兩點：一是GPS接收裝置費用較高，二是GPS對于使用環(huán)境有一定限制，如在水下、建筑物內(nèi)等地方不能直接使用。與全球定位系統(tǒng)原理一致，即在三位空間中，若某一節(jié)點獲得了到另外四個或四個以上的參考節(jié)點的距離，便可以確定該節(jié)點的位置信息。同理，在二維空間中，若某一節(jié)點獲得了到另外三個以上(包括三個)參考節(jié)點的距離，便可以確定該節(jié)點的位置坐標。目前，經(jīng)常采用的計算節(jié)點坐標的方法有三邊測量法、多邊測量法(極大似然估計法)、Min-max法及三角測量法等。圖9-2所示為三邊測量法及其變換形式多邊測量法的原理示意圖。

圖9-2三邊測量法及其變換形式多邊測量法的原理示意圖

由圖9-2可知，三邊測量法的基本原理是利用以三個信標節(jié)點為圓心，以三個信標節(jié)點分別到該未知節(jié)點的距離為半徑的三個圓在平面中的交點來推算出未知節(jié)點的位置坐標。但是，在實際定位過程中，由于節(jié)點間測距存在誤差，圖中的三個圓可能無法交于一點，所以常常使用最小二乘法來估算未知節(jié)點的坐標。

假設(shè)某一未知節(jié)點u測得了到n個信標節(jié)點的距離(n≥3)，其中第i個信標節(jié)點的位置坐標為(xi，yi)，且到節(jié)點u的距離為di，則可以得到如下方程組

(9-7)

式中(x，y)為節(jié)點u的坐標。為了使得問題線性化，分別用前(n-1)個方程減去最后一個方程，上述二元二次方程組轉(zhuǎn)換為AX?=?b形式，其中

(9-8)

方程組AX?=?b可用最小二乘法解得

(9-9)

從而，解得位置的估計值

。

9.2.2無線傳感器網(wǎng)絡(luò)節(jié)點定位算法

測量節(jié)點間的物理距離是很多定位系統(tǒng)及定位算法的基礎(chǔ)，但物理測距需要采用復(fù)雜的硬件設(shè)備與信號處理算法。目前也有許多研究不采用物理測距技術(shù)實現(xiàn)節(jié)點定位的算法。以是否需要節(jié)點具有物理測距能力為標準，可將現(xiàn)有的傳感器網(wǎng)絡(luò)節(jié)點定位機制分為兩大類，即基于測距的節(jié)點定位機制和無需測距的節(jié)點定位機制。

1．基于測距的節(jié)點定位機制

基于測距的定位方法通過給節(jié)點配備額外測量設(shè)備，測量節(jié)點間點到點的距離或角度信息，然后利用三邊測量法、三角測量法或極大似然估計法計算出未知節(jié)點的位置信息?；跍y距的定位技術(shù)常用的測距方法有RSSI(ReceivedSignalStrengthIndicator)、TOA(TimeOfArrival)、TDOA(TimeDifferenceOnArrival)及AOA(AngleOfArrival)等。

1)?RSSI定位算法

RSSI定位技術(shù)是將無線信號的傳輸損耗轉(zhuǎn)換成距離，通過檢測傳輸損耗而推算出節(jié)點間距離。常用的傳播路徑損耗模型有自由空間傳播模型、對數(shù)距離路徑損耗模型、哈它模型以及對數(shù)-常態(tài)分布模型等?，F(xiàn)有傳感器節(jié)點的通信控制芯片通常已提供測量信號強度的方法，可以在接收數(shù)據(jù)的同時完成RSSI的測量，無需配置額外硬件。RSSI測距的主要誤差來自射頻信號的多徑衰落、反射以及不規(guī)則傳播特性，其測距準確度依賴于信號的強度、傳播模型和信號衰落模型。RSSI通常被視為一種粗糙的測距技術(shù)，有±50%的測距誤差。

2)?TOA定位算法

TOA定位算法將發(fā)送器發(fā)出信號的時間與接收器收到信號的時間之間的差值，乘以無線電波在介質(zhì)中的傳播速度，從而得到兩者間的距離。與RSSI技術(shù)相比，TOA具有對環(huán)境依賴小、測距精度高等優(yōu)點，但它需要節(jié)點間精確的時間同步，因此無法應(yīng)用于松散耦合型定位。GPS是使用TOA技術(shù)的典型定位系統(tǒng)。因受節(jié)點性能的限制，實際使用TOA技術(shù)的傳感器網(wǎng)絡(luò)定位系統(tǒng)較少。但隨著UWB技術(shù)的成熟與發(fā)展，TOA測距在傳感器網(wǎng)絡(luò)定位領(lǐng)域具有了廣闊的應(yīng)用前景。

3)?TDOA定位算法

TDOA定位算法通過記錄信號的到達時間差來測量距離，被廣泛應(yīng)用于傳感器網(wǎng)絡(luò)定位系統(tǒng)。一般采用在發(fā)送節(jié)點和接收節(jié)點上安裝超聲波和RF兩種收發(fā)器來實現(xiàn)，該算法利用聲波和電磁波在空氣中傳播速度的差異來測距，它將兩種信號的到達時間差乘以聲速得到節(jié)點間距離。TDOA測距不是采用到達的絕對時間來測距的，因此降低了對時間同步的要求，但仍然需要較精確的計時功能。TDOA的測距精度可達到厘米級，但受超聲波的短距離傳播和非視距傳播效應(yīng)等問題的限制。

4)?AOA定位算法

AOA定位算法是接收機通過天線陣列測出電磁波的入射角度，形成一根從接收機到發(fā)射機的方向線，即測位線，由兩個信標節(jié)點得到的兩條測位線的交點就是未知節(jié)點的位置。因此，AOA定位法只需要兩個基站就可以定位，而兩條直線只有一個交點，不會出現(xiàn)軌跡有多個交點的現(xiàn)象，即定位的模糊性。但為了測量電磁波的入射角度，接收機的天線需要改進，必須配備方向性強的天線陣列。

AOA定位算法的原理如圖9-3所示。假定未知節(jié)點分別測得與信標節(jié)點N1和N2所構(gòu)成的角度θ1和θ2，且N1、N2分別位于(x1，y1)和(x2，y2)，則

(9-10)

其中，i?=?1，2。通過求解該非線性方程，可得到未知節(jié)點的位置(x0，y0)。

從圖9-3可知，AOA定位算法首先獲取發(fā)送節(jié)點的無線電波信號的角度信息，然后通過交匯法估計終端的位置。但是，AOA算法受外界環(huán)境影響較大，而且需要額外硬件，也會受到硬件尺寸和功耗的限制。AOA算法用于傳感器節(jié)點時需要根據(jù)實際情況而定。

圖9-3AOA定位算法的原理

2．無需測距的節(jié)點定位機制

無需測距的節(jié)點定位機制就是無需配備額外的設(shè)備來獲取節(jié)點間點到點的距離或角度，僅根據(jù)網(wǎng)絡(luò)的連通性和信標節(jié)點的位置信息實現(xiàn)相對精確的定位功能。無需測距的定位技術(shù)典型的方法有質(zhì)心法、DV-Hop定位算法、APIT(ApproximatePITTest)算法、凸規(guī)則定位法和MDS-MAP定位算法等。

1)質(zhì)心法

質(zhì)心法是一種僅基于網(wǎng)絡(luò)連通性的室外定位算法，其主要優(yōu)點是方法簡單，具有很好的可擴展性，但是定位精度較差，且定位精度依賴于信標的數(shù)量和分布情況。通過收到的位置廣播信息，未知節(jié)點將連接度超過90%的信標節(jié)點加為連通信標節(jié)點集合，并將自身位置確定為我所有，而后與連通的信標節(jié)點組成多邊形的質(zhì)心。

設(shè)未知節(jié)點有k個連通信標節(jié)點，且其中第i節(jié)點的坐標為(xi，yi)，則未知節(jié)點的物理位置估計值

可采用式(9-11)計算：

(9-11)

由于該算法僅用到鄰居信標節(jié)點的信息，計算和通信的復(fù)雜度隨著信標節(jié)點的密度增大呈線性增加，不會隨系統(tǒng)大小的變化而變化，因此該算法具有廣泛的可擴展性。

2)?DV-Hop定位算法

DV-Hop定位算法是一種典型的基于多跳信標節(jié)點信息的定位策略，包括三個階段：第一階段，采用典型的距離矢量交換方法，使所有未知節(jié)點獲得到信標節(jié)點的跳數(shù)；第二階段，在獲得其他信標節(jié)點的位置和相隔跳數(shù)后，信標節(jié)點采用式(9-12)估算網(wǎng)絡(luò)平均每跳的距離：

(9-12)

其中，(xi，yi)、(xj，yj)分別是信標節(jié)點i和j的坐標，hij是i和j之間的跳數(shù)。然后，將平均每跳的距離作為一個校正值廣播至網(wǎng)絡(luò)中，未知節(jié)點僅記錄接收到的第一個平均單跳距離，并轉(zhuǎn)發(fā)給其鄰節(jié)點。未知節(jié)點接收到校正值之后，根據(jù)記錄的跳數(shù)計算到每個信標節(jié)點的距離，并在第三階段執(zhí)行多邊測量定位過程。

DV-Hop定位算法確保了大多數(shù)節(jié)點從最近的信標節(jié)點接收到平均單跳距離值，其優(yōu)勢為不依賴于測距精度，方法簡單。其缺點是僅在各向同性的密集網(wǎng)絡(luò)中，校正值才能合理地估算平均每跳距離。這種假設(shè)不盡合理，因此具有較大的應(yīng)用局限性。

3)?APIT定位算法

APIT是一種基于區(qū)域估算的定位策略，其主要思想是未知節(jié)點從所有鄰居信標節(jié)點中任選三個構(gòu)成一個三角形，并判斷自身是否處于該三角形中，然后對不同信標節(jié)點組合進行重復(fù)測試，直到測試完成所有組合或者精度滿足要求為止。最后，計算所有包括未知節(jié)點的三角形交集的質(zhì)心，從而確定未知節(jié)點的大致位置。APIT的定位算法原理如圖9-4所示，其中每個三角形的頂點均為信標節(jié)點。

圖9-4APIT的定位算法原理

APIT把定位問題轉(zhuǎn)化為判斷未知節(jié)點處于信標三角形區(qū)域內(nèi)部或外部的問題。各個信標節(jié)點將探測區(qū)域分成很多小三角形區(qū)域，獲得越多的三角形就能獲得越精確的定位，測試未知節(jié)點是否處于目標三角形內(nèi)的理論基礎(chǔ)是三角形的點測試法PIT，如圖9-5所示。

圖9-5PIT三角形的點測試法

假如存在一個方向，沿著這個方向M點會同時遠離或者同時接近A、B、C三個點，那么M位于ΔABC外；否則M位于ΔABC內(nèi)。在靜態(tài)網(wǎng)絡(luò)中，M是固定的，無法執(zhí)行PIT測試，為此定義了APIT測試：加入節(jié)點M的鄰居節(jié)點中沒有同時遠離或同時接近3個信標節(jié)點A、B、C的節(jié)點，則M就在ΔABC之內(nèi)；否則M就在ΔABC外。APIT測試的基本思想就是利用M節(jié)點的鄰節(jié)點與信標節(jié)點之間交換信息來效仿PIT測試中的節(jié)點移動。由于APIT要求信標節(jié)點的密集度高，只適合信標節(jié)點密集的傳感器網(wǎng)絡(luò)。

4)凸規(guī)則定位算法

凸規(guī)則定位算法將節(jié)點間的通信連接視為節(jié)點位置的幾何約束，把整個網(wǎng)絡(luò)模型化為一個凸集，從而將節(jié)點定位問題轉(zhuǎn)化為凸約束優(yōu)化問題，然后使用半定規(guī)劃和線性規(guī)劃方法得到一個全局優(yōu)化的解決方案，從而確定節(jié)點位置。同時，該算法也給出了一種計算未知節(jié)點有可能存在的矩形區(qū)域的方法，如圖9-6所示。圖9-6凸規(guī)則定位算法原理

根據(jù)位置節(jié)點與信標節(jié)點之間的通信連接和節(jié)點無線射程，可以計算出未知節(jié)點可能存在的區(qū)域(圖9-6中的交匯部分)，并得到相應(yīng)矩形區(qū)域，然后以矩形的質(zhì)心作為未知節(jié)點的位置。凸規(guī)劃是一種集中式定位算法，在信標節(jié)點比例為?10%的條件下，定位精度接近?100%。為了提高效率，信標節(jié)點必須部署在網(wǎng)絡(luò)邊緣，否則節(jié)點的位置估算會向網(wǎng)絡(luò)中心偏移。

5)?MDS-MAP定位算法

MDS-MAP定位算法是以MDS算法為基礎(chǔ)的傳感器網(wǎng)絡(luò)節(jié)點定位算法，屬于集中式算法，可在基于測距和無需測距兩種情況下運行，并且可以根據(jù)情況實現(xiàn)相對定位和絕對定位。MDS-MAP定位算法采用了一種源自心理測量和精神物理學(xué)的多維定標數(shù)據(jù)分析技術(shù)，常用于探索數(shù)據(jù)分析或信息可視化。MDS-MAP算法由以下三個步驟組成：

(1)從全局角度生成網(wǎng)絡(luò)拓撲連通圖，并為圖中每條邊賦予距離值，當節(jié)點具有測距能力時，該值就是測距結(jié)果；當節(jié)點僅擁有連通性信息時，所有邊賦值為1；然后使用最短路徑算法，如Dijkstra或Floyd算法，生成節(jié)點間距矩陣。

(2)對節(jié)點間距應(yīng)用MDS技術(shù)，生成整個網(wǎng)絡(luò)的二維或三維相對坐標系統(tǒng)。

(3)當擁有足夠的信標節(jié)點時(二維最少3個，三維最少4個)，將相對坐標系統(tǒng)轉(zhuǎn)化為絕對坐標系統(tǒng)。

當網(wǎng)絡(luò)的節(jié)點密度減小時，定位誤差增大，并且無法定位的節(jié)點數(shù)量增加。當網(wǎng)絡(luò)連通度達到12.2時，幾乎全部節(jié)點都可實現(xiàn)定位。在擁有200個節(jié)點(其中4個信標節(jié)點)，平均連通度為12.1的網(wǎng)絡(luò)中，在無需測距條件下，定位誤差約為30%；而在測距條件下，定位誤差為16%(測距誤差為5%)。

基于測距的定位方法精度相對較高，但對節(jié)點的硬件要求也很高，并且通常需要多次測量，循環(huán)定位求精度，從而增加了大量的計算開銷和通信開銷，所以這種方法雖然定位精度較高，但不適合低成本、低功耗的無線傳感器網(wǎng)絡(luò)。雖然無需測距的定位精度一般不如基于測距的定位精度，但無需配備額外的設(shè)備，在精度允許的情況下，更適合低成本、低功耗的無線傳感器網(wǎng)絡(luò)，這也是無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)發(fā)展與研究的趨勢。

9.2.3定位算法的應(yīng)用案例

在傳感器網(wǎng)絡(luò)節(jié)點定位系統(tǒng)的應(yīng)用領(lǐng)域，如環(huán)境監(jiān)測、交通管理、現(xiàn)代物流、目標跟蹤等應(yīng)用中，節(jié)點的地理位置信息是非常重要的，直接影響整個網(wǎng)絡(luò)系統(tǒng)的有效性。在無線傳感器網(wǎng)絡(luò)中不但有很多特定應(yīng)用都依賴于傳感器節(jié)點或者目標物體的地理位置信息，而且很多網(wǎng)絡(luò)運行和管理也需要節(jié)點位置信息的輔助，如基于地理信息的路由、資源的有效配置、對外部目標的定位和跟蹤、計算網(wǎng)絡(luò)覆蓋范圍、控制網(wǎng)絡(luò)的負載均衡等。近年來，在許多領(lǐng)域有傳感器網(wǎng)絡(luò)節(jié)點定位的應(yīng)用案例。

1)森林防火應(yīng)急監(jiān)控

目前，很多森林防火應(yīng)急監(jiān)控都是利用無線傳感器網(wǎng)絡(luò)來實現(xiàn)的。將傳感器網(wǎng)絡(luò)節(jié)點部署在監(jiān)控區(qū)域，通過傳感器網(wǎng)絡(luò)回傳至控制中心的數(shù)據(jù)一旦發(fā)現(xiàn)有異常情況，便可以通過該節(jié)點的相關(guān)地理位置信息判斷是哪塊區(qū)域發(fā)生了異常，以便工作人員采取相應(yīng)的措施，開展火災(zāi)救防任務(wù)。

2)動物活動追蹤

野外動物學(xué)家為了能夠更加了解動物的生活習(xí)性，有時需要跟蹤某些動物的活動路徑，比如一些鳥類的遷徙路徑。通過將傳感器節(jié)點固定或者植入該動物身體的某個部位，并通過該節(jié)點周期性地把相關(guān)信息回傳到基站或者控制中心，便可以得到其活動的路徑信息。

3)貴重文物的實時監(jiān)控

在一些重要的文物保護單位，一些特別珍貴的文物就利用傳感器網(wǎng)絡(luò)節(jié)點來實時監(jiān)控，利用節(jié)點的位置信息來判斷該文物是否在原來的位置，一旦節(jié)點位置信息有變動就有被盜的嫌疑。在網(wǎng)絡(luò)節(jié)點回傳的信息中還有可能包括該文物所處環(huán)境的濕度、溫度、光照度指標等，這些信息可以方便工作人員判斷環(huán)境是否對該文物有較大的影響。

4)礦井定位系統(tǒng)

礦井的安全問題一直都是礦工人身安全的最大威脅，在礦井下部署無線傳感器網(wǎng)絡(luò)節(jié)點來監(jiān)控其周圍的環(huán)境，比如一氧化碳的濃度，一旦發(fā)現(xiàn)某個網(wǎng)絡(luò)節(jié)點回傳的數(shù)據(jù)有異常，監(jiān)控系統(tǒng)便可以從該節(jié)點的位置信息來通知相關(guān)礦工，以便采取后續(xù)救援措施。

5)目標跟蹤的應(yīng)用

節(jié)點定位技術(shù)的應(yīng)用在目標跟蹤的過程中為系統(tǒng)提供了重要的目標位置信息參照，比如目標節(jié)點在無線AP(AccessPoint)間切換的時候，目標的位置信息對其在各?AP?中的無縫接入有著重要作用。

6)智能交通系統(tǒng)的應(yīng)用

節(jié)點定位技術(shù)是提供車輛所處位置信息的基礎(chǔ)，也是智能交通系統(tǒng)的信息基礎(chǔ)，獲取車輛位置信息可以為道路車輛提供信息反饋、精確導(dǎo)航、目標跟蹤等服務(wù)。

7)水下無線傳感器網(wǎng)絡(luò)應(yīng)用

隨著無線傳感器網(wǎng)絡(luò)在陸地上應(yīng)用的成熟，目前其應(yīng)用也拓展到了水下世界，但無論是陸地還是水下，其應(yīng)用大多數(shù)都離不開節(jié)點的地理位置信息。隨著水下無線傳感器網(wǎng)絡(luò)技術(shù)的成熟，傳感器網(wǎng)絡(luò)技術(shù)逐漸轉(zhuǎn)向民用，如用于海洋環(huán)境和海洋生物檢測，海底科學(xué)試驗等。由于水下無線傳感器網(wǎng)絡(luò)的巨大應(yīng)用價值，它已經(jīng)引起了世界許多國家軍事部門的極大關(guān)注，因為其發(fā)展甚至影響到海軍軍事戰(zhàn)略的變革。

目前，基于無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)的應(yīng)用領(lǐng)域已經(jīng)非常廣闊，比如定位技術(shù)在物流系統(tǒng)、緊急救援、軍事中的應(yīng)用等，還有很多應(yīng)用就不一一舉例了，細心的讀者一定可以發(fā)現(xiàn)它的很多應(yīng)用，甚至發(fā)現(xiàn)一些潛在的新應(yīng)用領(lǐng)域。

9.3數(shù)據(jù)融合技術(shù)

9.3.1數(shù)據(jù)融合概述

無線傳感器網(wǎng)絡(luò)大規(guī)模密集部署的特點導(dǎo)致大部分數(shù)據(jù)是冗余的，而且傳感器節(jié)點的絕大部分能量消耗在無線通信模塊，傳輸信息時要比執(zhí)行計算時更消耗電能，傳輸1?bit信息100m的距離需要的能量大約相當于執(zhí)行3000條計算指令消耗的能量。因此，為了盡量延長資源受限的無線傳感器網(wǎng)絡(luò)的生命周期，可在傳感器網(wǎng)絡(luò)中采用數(shù)據(jù)融合(DataAggregation)技術(shù)，即可以采取用計算量的增加換取通信量的降低的方法，在傳送過程中對數(shù)據(jù)包進行處理，減少無效數(shù)據(jù)。

1．數(shù)據(jù)融合技術(shù)的作用

傳感器網(wǎng)絡(luò)數(shù)據(jù)融合的主要思想是刪除冗余、無效和可信度較差的數(shù)據(jù)，同時將來自不同節(jié)點的信息結(jié)合起來進行融合處理，達到減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量的目的。這與傳統(tǒng)的多傳感器數(shù)據(jù)融合技術(shù)有所不同，傳統(tǒng)的多傳感器數(shù)據(jù)融合是對不同的知識源和傳感器采集的數(shù)據(jù)進行融合，以更好地描述觀測對象的信息。而傳感器網(wǎng)絡(luò)數(shù)據(jù)融合主要是指單種傳感器為了減少網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)傳輸量，達到減少能源消耗、延長網(wǎng)絡(luò)生命周期的目的。

一般地，傳感器網(wǎng)絡(luò)中的傳感器節(jié)點是密集分布的，這些節(jié)點所發(fā)送的數(shù)據(jù)很多具有語義相關(guān)性。如果能將網(wǎng)絡(luò)中具有語義相關(guān)性的數(shù)據(jù)合并成一條更有效的數(shù)據(jù)，就能降低在網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量，從而達到節(jié)約功耗的目的。另外，傳感器節(jié)點由于受到干擾，可能會采集到一些錯誤數(shù)據(jù)。如果在中間節(jié)點采用數(shù)據(jù)融合技術(shù)將錯誤的信息刪除掉，必將會減少能量的浪費，延長網(wǎng)絡(luò)壽命。總之，數(shù)據(jù)融合技術(shù)在傳感器網(wǎng)絡(luò)中起著十分重要的作用，主要表現(xiàn)在以下三個方面。

1)節(jié)省能量

傳感器網(wǎng)絡(luò)中部署著大量的傳感器節(jié)點，單個傳感器節(jié)點的檢測范圍和可靠性有限。在部署網(wǎng)絡(luò)時需要使傳感器節(jié)點達到一定的密度，以增強整個網(wǎng)絡(luò)的魯棒性和檢測信息的準確性，有時甚至需要使多個節(jié)點的檢測范圍互相交疊，這就導(dǎo)致相鄰節(jié)點報告的信息存在一定程度的冗余。在冗余程度很高的情況下，把這些節(jié)點報告的數(shù)據(jù)全部發(fā)送給匯聚

節(jié)點，與僅發(fā)送一份數(shù)據(jù)相比，除了使網(wǎng)絡(luò)消耗更多的能量外，匯聚節(jié)點并未獲得更多的信息。

數(shù)據(jù)融合就是針對上述情況對數(shù)據(jù)進行網(wǎng)內(nèi)處理的，即中間節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)之前，首先對數(shù)據(jù)進行融合，去掉冗余信息，在滿足應(yīng)用需求的前提下將需要傳輸?shù)臄?shù)據(jù)量最小化。網(wǎng)內(nèi)處理利用的是節(jié)點的計算資源和存儲資源，它的能量消耗與傳輸數(shù)據(jù)相比要少很多。因此，在一定程度上盡量進行網(wǎng)內(nèi)處理，減少數(shù)據(jù)傳輸量，可以有效地節(jié)省能量。在理想的融合情形下，中間節(jié)點可以把n個長度相等的輸入數(shù)據(jù)分組合并成1個等長的輸出分組，這樣只需要消耗不進行融合所消耗能量的1/n即可完成數(shù)據(jù)傳輸；最差的情況下融合操作并未減少數(shù)據(jù)量，但通過減少分組個數(shù)，可以減少信道的協(xié)商或競爭過程造成的能量開銷。

2)提高所獲得信息的精度

無線傳感器網(wǎng)絡(luò)要部署在各種各樣的環(huán)境中，因此傳感器節(jié)點獲得的信息存在著很高的不可靠性。導(dǎo)致信息不可靠的因素主要來自以下三個方面：

①受到成本及體積的限制，節(jié)點配置的傳感器精度一般較低。

②無線通信的機制使得傳送的數(shù)據(jù)更容易因為受到干擾而遭破壞。

③惡劣的工作環(huán)境除了影響數(shù)據(jù)傳輸外，還會破壞節(jié)點的功能部件，令工作異常，報告錯誤的數(shù)據(jù)。

因此，僅收集少數(shù)幾個分散性的傳感器節(jié)點的數(shù)據(jù)很難得到正確的信息，需要通過對監(jiān)測同一對象的多個傳感器所采集的數(shù)據(jù)進行融合來有效地提高所獲得信息的精度。另外，由于鄰近的傳感器節(jié)點監(jiān)測同一區(qū)域，獲得的信息之間差異很小，如果個別節(jié)點報告了錯誤的或誤差比較大的信息，很容易在本地處理中通過簡單的比較算法排除。

3)提高數(shù)據(jù)收集效率

采用數(shù)據(jù)融合技術(shù)可以在一定程度上提高網(wǎng)絡(luò)收集數(shù)據(jù)的整體效率，減少需要傳輸?shù)臄?shù)據(jù)量，減輕網(wǎng)絡(luò)的傳輸擁塞，降低數(shù)據(jù)的傳輸延遲。即使有效數(shù)據(jù)量并未減少，但通過對多個數(shù)據(jù)分組合并，可以減少數(shù)據(jù)分組個數(shù)以及傳輸中的沖突碰撞現(xiàn)象，提高無線信道的利用率。

無線傳感器網(wǎng)絡(luò)需要傳輸?shù)臄?shù)據(jù)與傳統(tǒng)無線網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)不同。對無線傳感器網(wǎng)絡(luò)而言，終端用戶并不需要網(wǎng)絡(luò)節(jié)點發(fā)送所有采集到的傳感數(shù)據(jù)，這是因為相鄰節(jié)點的傳感數(shù)據(jù)具有高度相關(guān)性，造成了大量的數(shù)據(jù)冗余。圖9-7所示是無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合處理示意圖。

圖9-7無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合處理示意圖

2．數(shù)據(jù)融合方法和分類

現(xiàn)有傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合技術(shù)存在多種不同的分類方式，可以根據(jù)融合前后的數(shù)據(jù)信息含量、融合級別和網(wǎng)內(nèi)數(shù)據(jù)融合技術(shù)所依賴的網(wǎng)絡(luò)拓撲路由劃分。

1)按照數(shù)據(jù)信息含量分類

傳感器網(wǎng)絡(luò)數(shù)據(jù)融合從數(shù)據(jù)信息含量上分為無損融合和有損融合兩種方法。在無損融合中，所有有效的信息將會被保留，在各個結(jié)果之間相關(guān)性非常大的情況下，會存在許多冗余數(shù)據(jù)。數(shù)據(jù)融合的基本原則就是減少這些冗余信息。與無損融合不同，有損融合是以減少信息的詳細內(nèi)容或降低信息質(zhì)量的方法來減少更多的數(shù)據(jù)傳輸量，從而達到節(jié)省能源的目的。如圖9-8和圖9-9所示，圖中所有的信息都被保留了下來。

圖9-9傳感器網(wǎng)絡(luò)的有損數(shù)據(jù)融合圖9-8傳感器網(wǎng)絡(luò)的無損數(shù)據(jù)融合

2)按照融合級別分類

根據(jù)信息的抽象程度，信息融合主要在三個層次上展開：數(shù)據(jù)級融合、特征級融合和決策級融合。

數(shù)據(jù)級融合是最低層次的融合，它是對傳感器獲得的原始數(shù)據(jù)在不經(jīng)處理或者經(jīng)過很少處理的基礎(chǔ)上進行的融合，能提供其他層次上所不具有的細節(jié)信息，主要針對目標檢測、濾波、定位和跟蹤等底層數(shù)據(jù)融合。但是融合數(shù)據(jù)的穩(wěn)定性和實時性差，有很大的局限性。

特征級融合屬于中間層次的融合，是對從原始信息中提取的特征信息進行的融合，能夠增加某些重要特征的準確性，也可以產(chǎn)生新的組合特征，具有較大的靈活性。

決策級融合是一種高層次的融合，它直接對完全不同類型的傳感器或來自不同環(huán)境區(qū)域的感知信息形成的局部決策進行最后分析，以得出最終的決策。決策級融合抽象層次高，適用范圍最廣。

總之，數(shù)據(jù)級融合信息準確性最高，但對資源的要求比較嚴格。決策級融合處理速度最快，但是要以一定的信息損失為代價。特征級融合既保留了足夠的重要信息，又實現(xiàn)了客觀的信息壓縮，是介于數(shù)據(jù)級融和決策級融合之間的一種中間級處理。

3)按照網(wǎng)絡(luò)拓撲路由分類

與網(wǎng)絡(luò)拓撲路由相關(guān)的數(shù)據(jù)融合方法跟網(wǎng)絡(luò)結(jié)構(gòu)密切相關(guān)，這也是由傳感器網(wǎng)絡(luò)所特有的性質(zhì)決定的。根據(jù)傳感器網(wǎng)絡(luò)拓撲路由，數(shù)據(jù)融合方式分為分簇型數(shù)據(jù)融合、反向樹型數(shù)據(jù)融合以及簇樹混合型數(shù)據(jù)融合。

圖9-10給出了分簇型數(shù)據(jù)融合方式。這種方式可應(yīng)用于分級的簇型網(wǎng)絡(luò)中，它將整個網(wǎng)絡(luò)自組織成若干個簇區(qū)域，每個區(qū)域選舉出自己的簇頭，感知節(jié)點感測到數(shù)據(jù)后將數(shù)據(jù)直接發(fā)送到它所在簇的簇頭節(jié)點，簇頭節(jié)點對簇內(nèi)數(shù)據(jù)進行融合處理后，直接轉(zhuǎn)發(fā)給匯聚節(jié)點。

圖9-10分簇型數(shù)據(jù)融合方式

與這種數(shù)據(jù)融合方式相關(guān)的路由協(xié)議主要有：低功耗自適應(yīng)分簇路由算法(LowEnergyAdaptiveClusteringHierarchy，LEACH)及其改進算法HEED等，以及基于安全模式的能量有效數(shù)據(jù)融合協(xié)議(Energy-efficientandSecurePatternbasedDataAggregationforWirelessSensorNetworks，ESPDA)等。

反向樹型傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)融合如圖9-11所示，它建立在樹型網(wǎng)絡(luò)拓撲結(jié)構(gòu)基礎(chǔ)之上，感知節(jié)點感測到數(shù)據(jù)后，經(jīng)過反向多播融合樹，通過多跳的方式轉(zhuǎn)發(fā)給匯聚節(jié)點，樹上各中間節(jié)點都對接收到的數(shù)據(jù)進行融合處理。

圖9-11反向樹型傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)融合

關(guān)于反向數(shù)據(jù)融合樹的構(gòu)造，有以下三種實用的方案：

①近源匯聚(CenteratNearestSource，CNS)：距離匯聚節(jié)點最近的源節(jié)點充當數(shù)據(jù)的融合節(jié)點，所有其他的數(shù)據(jù)源都將數(shù)據(jù)發(fā)送給這個節(jié)點，最后由這個節(jié)點將融合后的數(shù)據(jù)發(fā)送給匯聚節(jié)點。此種方案中融合節(jié)點一旦確定，便形成了融合樹模型。

②最短路徑樹(ShortestPathsTree，SPT)：每個數(shù)據(jù)源都各自沿著到達匯聚節(jié)點的最短路徑傳送數(shù)據(jù)，這些最短路徑會產(chǎn)生交疊，從而形成融合樹。交疊部分的每個中間節(jié)點都進行數(shù)據(jù)融合。此種方案中，當所有源節(jié)點確定各自的最短傳輸路徑時，便確定了融合樹的形態(tài)。

③貪心樹(GreedyIncrementalTree，GIT)：此種方案中融合樹是逐步建立的，先確定樹的主干，再逐步添加枝葉。最初，貪心增長樹只有匯聚節(jié)點與距離它最近的源節(jié)點之間的一條最短路徑，然后每一步都從剩下的源節(jié)點中選出距離貪心增長樹最近的節(jié)點連接到樹上，直到所有的源節(jié)點都連接到樹上為止。

與這種數(shù)據(jù)融合方式相關(guān)的路由協(xié)議主要有：信息協(xié)商的傳感器協(xié)議(SensorProtocolforInformationviaNegotiation，SPIN)，高效的能量感知的分布啟發(fā)式融合樹(EfficientEnergy-awareDistributedHeuristictoGeneratetheAggregationTree，EADAT)、平衡融合樹路由(BalancedAggregationTreerouting，BATR)等。

簇樹混合型網(wǎng)內(nèi)數(shù)據(jù)融合技術(shù)面向復(fù)雜、高效的簇樹混合型網(wǎng)絡(luò)，如圖9-12所示。無線傳感器網(wǎng)絡(luò)首先自組織大量的簇，在簇頭節(jié)點之間形成反向多播融合樹。數(shù)據(jù)源節(jié)點感測到數(shù)據(jù)后將數(shù)據(jù)直接發(fā)送至它所在簇的簇頭節(jié)點，在簇頭節(jié)點進行融合處理后，再經(jīng)過反向多播融合樹的融合處理轉(zhuǎn)發(fā)給匯聚節(jié)點。

圖9-12簇樹混合型傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)數(shù)據(jù)融合

9.3.2主要數(shù)據(jù)融合方法分析

本節(jié)將針對前文所述的反向樹型數(shù)據(jù)融合方法，分簇型數(shù)據(jù)融合方法中的靜態(tài)分簇方法和動態(tài)分簇方法分別進行詳細分析。

1．反向樹型數(shù)據(jù)融合方法分析

在傳感器網(wǎng)絡(luò)中，匯聚節(jié)點是通過反向多播樹的形式從分散的傳感器節(jié)點逐步將監(jiān)測數(shù)據(jù)匯集起來的。如果傳輸數(shù)據(jù)的路徑形成一棵反向多播樹，樹上的每個中間節(jié)點都對收到的數(shù)據(jù)進行融合處理，那么數(shù)據(jù)便得到了及時地、且最大限度地融合。

需要注意的是，同一個事件引起的多個源節(jié)點的數(shù)據(jù)包在向匯聚節(jié)點傳輸?shù)倪^程中可能經(jīng)過完全不相交的路徑，因此根本不會產(chǎn)生數(shù)據(jù)融合。圖9-13描述了三種可能的數(shù)據(jù)融合場景。采用不用的路由拓撲和目標的位置會影響數(shù)據(jù)融合的性能。

圖9-13樹型融合方法的各種數(shù)據(jù)融合過程

圖9-13表明，在第一種情況下，事件T1產(chǎn)生的數(shù)據(jù)包在節(jié)點B處匯合，但是節(jié)點B距離目標監(jiān)測區(qū)域很遠。在第二種情況下，事件T2產(chǎn)生的數(shù)據(jù)包在不同路徑轉(zhuǎn)發(fā)過程中沒有經(jīng)過融合。在第三種情況下，事件T3產(chǎn)生的數(shù)據(jù)包在距離目標節(jié)點比較近的C節(jié)點處進行了數(shù)據(jù)融合。

2．靜態(tài)分簇型數(shù)據(jù)融合方法

前文所述的LEACH和TEEN都是基于層次的路由，它們的核心思想是采用分簇的方法使得數(shù)據(jù)融合的地位突顯出來，它包括周期性的循環(huán)過程。LEACH的操作分成“輪”來進行，每一輪具有兩個運行階段，包括簇建立階段和數(shù)據(jù)通信階段。為了減少協(xié)議的開銷，數(shù)據(jù)通信階段的持續(xù)時間要長于簇建立階段。

在簇建立階段，相鄰節(jié)點動態(tài)地自動形成簇，隨機產(chǎn)生簇頭。隨機性可確保簇頭與匯聚節(jié)點之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹偟剿械膫鞲衅鞴?jié)點。簇頭的具體產(chǎn)生機制如下：一個傳感器節(jié)點生成0～1的隨機數(shù)，如果大于閾值T，就選擇這個節(jié)點為簇頭。T的計算方法為

式中，p為節(jié)點中成為簇頭的百分數(shù)；r為當前的輪數(shù)。

(9-13)

一旦簇頭節(jié)點被選定，它們便主動向所有節(jié)點廣播這個消息。根據(jù)接收信號的強度，節(jié)點選擇它所要加入的簇，并告知相應(yīng)的簇頭節(jié)點。

在數(shù)據(jù)通信階段，節(jié)點把數(shù)據(jù)發(fā)送給簇頭，簇頭進行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點。由于簇頭承擔(dān)了很多耗能的工作，如數(shù)據(jù)融合、與匯聚節(jié)點通信等。各節(jié)點需要等概率地輪流擔(dān)任簇頭，以達到網(wǎng)絡(luò)能量消耗的平衡。LEACH協(xié)議的特點是分簇和數(shù)據(jù)融合，分簇有利于網(wǎng)絡(luò)的擴展性，數(shù)據(jù)融合可以節(jié)約功耗。

LEACH協(xié)議對于節(jié)點分布較密的情況有較高的效率，因為節(jié)點密度大會導(dǎo)致在小范圍內(nèi)冗余數(shù)據(jù)較多，LEACH協(xié)議可以有效地消除數(shù)據(jù)的冗余性。然而，LEACH算法僅僅強調(diào)了數(shù)據(jù)融合的重要性，并沒有給出具體的融合方法。TEEN是LEACH的一種改進算法，可應(yīng)用于事件驅(qū)動的傳感器網(wǎng)絡(luò)。TEEN與定向擴散路由一樣通過緩存機制抑制不需要轉(zhuǎn)發(fā)的數(shù)據(jù)，但是它利用閾值的設(shè)置使抑制操作更加靈活，對于前一次監(jiān)測結(jié)果差值較小的數(shù)據(jù)也進行了抑制。

靜態(tài)分簇型數(shù)據(jù)融合方法的關(guān)鍵思想是把網(wǎng)絡(luò)主動分為一些小的簇，每個簇都有一個簇頭和多個傳感器成員節(jié)點組成，簇頭負責(zé)數(shù)據(jù)融合，其他節(jié)點負責(zé)監(jiān)測和事件報告。當成員節(jié)點監(jiān)測到一個事件，它們就把事件數(shù)據(jù)包傳送給各自的簇頭，然后由簇頭進行數(shù)據(jù)融合操作，這取決于融合因子α，最終把融合后的ρ個數(shù)據(jù)包傳送給匯聚節(jié)點。因為簇頭是提前創(chuàng)建的，并不受位置或事件規(guī)律的影響，因此把這樣的融合稱為靜態(tài)融合方案。

理想情況下，監(jiān)測到同一事件的所有傳感器網(wǎng)絡(luò)節(jié)點均屬于同一個簇，這種情況下數(shù)據(jù)包的傳輸量將會最小。然而，很可能出現(xiàn)監(jiān)測到同一目標的傳感器節(jié)點屬于不同的簇。圖9-14所示為采用Voronoi圖的靜態(tài)分簇型數(shù)據(jù)融合方案，一個目標被簇2、5、6中的成員節(jié)點監(jiān)測到。在這種情況下，多個簇頭將會發(fā)送同一事件的信息，這在一定程度上降低了數(shù)據(jù)融合帶來的優(yōu)點。

圖9-14采用Voronoi圖的靜態(tài)分簇型數(shù)據(jù)融合方案

這里設(shè)計了一個算法來執(zhí)行靜態(tài)分簇型數(shù)據(jù)融合方案，算法由網(wǎng)絡(luò)建立階段和運行階段組成。在建立階段，網(wǎng)絡(luò)中的一小部分節(jié)點被推選為簇頭節(jié)點來負責(zé)數(shù)據(jù)融合，在運行階段節(jié)點涉及感應(yīng)、事件監(jiān)測、事件報告和數(shù)據(jù)融合。由于簇頭比其他成員節(jié)點更容易耗盡能量，因此循環(huán)進行建立階段和運行階段，每次使不同的節(jié)點被推舉為簇頭。這將使系統(tǒng)中節(jié)點的能量平衡，從而延長傳感器網(wǎng)絡(luò)系統(tǒng)的壽命。靜態(tài)分簇算法的運行如圖9-15所示。

圖9-15靜態(tài)分簇算法的運行

1)建立階段

靜態(tài)分簇融合算法的網(wǎng)絡(luò)建立階段包括時間同步、鄰居發(fā)現(xiàn)、分簇等操作。

(1)時間同步階段：系統(tǒng)中的節(jié)點需要維持時間同步，這樣才能分簇和按順序重新分簇。采用簡單的時間同步方案，只需要本地時間同步。

(2)鄰居發(fā)現(xiàn)階段：在此階段，節(jié)點周期性廣播鄰居發(fā)現(xiàn)信標。收到信標信息的節(jié)點根據(jù)其內(nèi)容產(chǎn)生與鄰居節(jié)點的鏈路質(zhì)量估計。這個信息在后來的分簇階段很重要，成員節(jié)點用來決定簇頭。

(3)分簇階段：在本階段，網(wǎng)絡(luò)中的一小部分節(jié)點被選為簇頭。鄰近簇頭的非簇頭節(jié)點加入簇，成為一個簇的成員節(jié)點。

其中，分簇階段算法按照如下循環(huán)進行：

①選擇簇頭候選者。在每一輪，覆蓋到的節(jié)點在前一輪或者成為簇頭或者成為成員節(jié)點。在第i輪的開始，網(wǎng)絡(luò)中未覆蓋到的節(jié)點成為簇頭候選者的概率是kip0。其中p0是第0輪節(jié)點成為簇頭的初始概率，并且p0的值必須足夠小，這樣在圓形的無線電范圍內(nèi)，即簇區(qū)域內(nèi)只有一個節(jié)點能夠成為簇頭候選者。參數(shù)k和p0決定整個網(wǎng)絡(luò)完成分簇需要的輪數(shù)，也決定網(wǎng)絡(luò)中成為簇頭的節(jié)點的數(shù)目。

②簇頭廣播。如果一個節(jié)點變成簇頭候選者，就啟動一個定時器。定時器的長短與節(jié)點的剩余能量成反比，如果節(jié)點的剩余能量越多，定時器就會越早終止。當定時器終止，節(jié)點成為簇頭，并廣播一個簇頭廣告信息(CHA)。該信息包含節(jié)點的ID和節(jié)點的剩余能量。采用定時器可以使具有更多剩余能量的節(jié)點被推選為簇頭。一旦一個節(jié)點在第i輪成為簇頭，它將在隨后的三輪中繼續(xù)轉(zhuǎn)發(fā)CHA信息，從而增加在有損的環(huán)境中鄰居節(jié)點接收到CHA信息的可能性。

③簇頭廣告信息接收。當一個未被覆蓋過的節(jié)點接收到其他節(jié)點的CHA信息后，它成為一個成員節(jié)點。當一個簇頭候選者收到另一個節(jié)點的CHA信息后，它把自己的剩余能量與CHA信息中的剩余能量的值相比較，如果發(fā)送者的剩余能量比自己的剩余能量多，該節(jié)點成為一個成員節(jié)點并終止定時器。如果在一輪的最后，節(jié)點既不是簇頭也不是成員節(jié)點，它就開始新的一輪并重復(fù)以上操作。

④簇頭抉擇。經(jīng)過有限輪后，所有的節(jié)點都被會被覆蓋到。從簇頭CH1，CH2，…，CHn收到多個簇頭廣告信息的成員節(jié)點決定只能成為n個簇中的一個簇的成員節(jié)點。這個決定基于在鄰居發(fā)現(xiàn)階段它獲得的n個簇頭的鏈路質(zhì)量估計。

2)運行階段

靜態(tài)分簇融合算法的網(wǎng)絡(luò)運行階段就是一個數(shù)據(jù)融合的

過程：

①當節(jié)點監(jiān)測到目標時，報告監(jiān)測信息給它的簇頭。

②簇頭沿著路由路徑傳輸融合后的數(shù)據(jù)包到匯聚節(jié)點。

3．動態(tài)分簇型數(shù)據(jù)融合方法

在動態(tài)分簇型數(shù)據(jù)融合方法中，簇信息是由目標監(jiān)測觸發(fā)的，同時簇圍著目標而創(chuàng)建。多個感應(yīng)節(jié)點相互協(xié)作推舉出一個簇頭，該簇頭把融合后的數(shù)據(jù)包發(fā)送到匯聚節(jié)點。動態(tài)分簇融合包括兩個重要特征：

①當事件發(fā)生時，只有空間上很近的節(jié)點能加入到簇的構(gòu)造中，網(wǎng)絡(luò)中的其他節(jié)點不需要進行耗能的簇建立和保持操作。

②當一個節(jié)點無線發(fā)射的范圍大于它的監(jiān)測范圍的2倍時，監(jiān)測到事件的傳感器節(jié)點都在相互的無線電范圍內(nèi)，因此可以達成一致，選一個簇頭來進行數(shù)據(jù)融合。這就是動態(tài)分簇融合跟靜態(tài)分簇融合的區(qū)別，靜態(tài)分簇融合中多個簇可能傳送同一事件的信息。

在動態(tài)選擇融合節(jié)點來進行數(shù)據(jù)融合的機制中，目標導(dǎo)向的動態(tài)融合算法(TargetOrientedDynamicAggregationAlgorithm)是一個典型算法。當傳感器節(jié)點監(jiān)測到目標時，節(jié)點就開始交換監(jiān)測信息，其中具有更高剩余能量的監(jiān)測節(jié)點，或收到更多監(jiān)測報告的節(jié)點有更大的可能性成為簇頭。目標導(dǎo)向的動態(tài)融合算法的具體過程如下：

(1)報告監(jiān)測信息。當傳感器節(jié)點監(jiān)測到目標時，它廣播一個監(jiān)測報告(SensingReport)信息給它的鄰居。這個信息包含節(jié)點的ID、剩余能量和關(guān)于目標的信息。

(2)簇頭候選者競選。如果一個監(jiān)測節(jié)點從鄰居節(jié)點收到SR信息，且該監(jiān)測節(jié)點的剩余能量大于監(jiān)測節(jié)點的平均剩余能量，節(jié)點就成為簇頭候選者，并開啟用來發(fā)送CHA消息的CHA定時器。定時器的終止時間有以下兩個值：

①一個與接收到的SR信息的數(shù)目成反比的值。

②一個比第1個值更小的隨機值。

第2個值用來打斷收到相同數(shù)目SR信息節(jié)點的聯(lián)系。從而，收到更多SR信息的節(jié)點和有更多剩余能量的節(jié)點趨于成為簇頭候選者。收到更多SR信息的節(jié)點就能夠產(chǎn)生更充沛的和多維的目標信息。

(3)簇頭廣告。當一個簇頭候選者的CHA定時器終止時，它就成為簇頭并廣播一個CHA信息給它的鄰居節(jié)點。該信息包含節(jié)點的ID和CHA定時器延遲的值。

(4)簇頭廣告信息接收。當簇頭候選者收到一個CHA信息后，它把自己的CHA定時器的延遲的值與收到的信息里CHA定時器延遲的值進行比較，如果發(fā)送者的值比它自己的值小，這個節(jié)點就取消它的CHA定時器。

(5)多簇頭的解決。由于無線鏈路的不可靠和信息碰撞，對于同一個事件很可能有多個簇頭被選舉出來。為了降低這種情況發(fā)生的可能性，被推選的簇頭啟動一個多簇頭解決定時器，用來延遲發(fā)往匯聚節(jié)點的融合數(shù)據(jù)包。如果簇頭在這個多簇頭解決延遲定時器終止之前接收到另一個CHA信息，它就發(fā)送一個終止信息給發(fā)送者。

(6)數(shù)據(jù)包傳輸。當多簇頭解決定時器終止了，簇頭進行數(shù)據(jù)融合操作，并把融合后的數(shù)據(jù)發(fā)送到匯聚節(jié)點。

9.4無線傳感器網(wǎng)絡(luò)目標跟蹤技術(shù)

9.4.1目標跟蹤概述1．目標跟蹤的必要性

無線傳感器網(wǎng)絡(luò)一個非常重要的應(yīng)用就是目標跟蹤，用無線傳感器網(wǎng)絡(luò)探測、識別并追蹤進入監(jiān)視區(qū)域的移動目標，實現(xiàn)對區(qū)域環(huán)境進行實時測控。獲取移動目標的位置和速度信息是實現(xiàn)追蹤的前提和基礎(chǔ)，涉及的傳感器主要有雷達波傳感器、聲波傳感器、磁傳感器等。

以雷達波傳感器和聲波傳感器為例來說明目標追蹤問題。兩者均可以定位移動目標，區(qū)別在于利用聲波傳感器測量時，要求被測物體必須距離傳感器節(jié)點很近，而利用雷達波傳感器測量卻無此限制。單個傳感器節(jié)點是無法確定被測物體的位置的，只能確定目標到其自身的距離。利用雷達波傳感器測量物體時，至少需要三個傳感器節(jié)點采集信號，由這三個信號構(gòu)成三角形計算物體的位置。利用聲波傳感器測量時，至少需要四個傳感器節(jié)點采集信號，并采用其中一個節(jié)點作為基準，計算出其他三個節(jié)點到目標的距離，然后再根據(jù)三角形算法計算出移動目標的位置。

從獲取移動目標的位置和速度的過程來看，多個傳感器節(jié)點必須協(xié)同工作才能完成任務(wù)。為了提高追蹤精度，傳感器節(jié)點必須盡量減小測量數(shù)據(jù)的時間差，保持協(xié)同信息的同步。不考慮資源約束，理想的追蹤方法就是讓所有傳感器節(jié)點以最快的采樣頻率參與目標追蹤，但實際上這是不可能的。此外，由于目標不斷移動，且速度和方向都不確定，所以要求系統(tǒng)具有極強的實時性，這增加了無線傳感器網(wǎng)絡(luò)分配資源的難度。隨著時間的推移，傳感器節(jié)點會出現(xiàn)不穩(wěn)定的情況，有的甚至損壞，所以要求系統(tǒng)具有極強的魯棒性。

2．目標跟蹤過程分析

一般地，目標的跟蹤過程可以分為探測目標、目標分類、目標定位、建立目標運動方程與預(yù)測結(jié)果等五個階段。

1)探測目標

探測階段的目的是發(fā)現(xiàn)目標，此階段需要大量的信號處理計算。為了進行信號處理，需要劃定時間窗，在時間窗內(nèi)連續(xù)采樣信號進行處理。一般情況下，由于環(huán)境噪聲及測量噪聲的影響，要設(shè)立探測閾值，只有能量大于閾值的信號才能表示探測到目標。由于噪聲是不斷變化的，探測閾值要隨著噪聲的變化而不斷調(diào)整，其調(diào)整的準則是保證恒定的誤報率。所謂誤報，是指環(huán)境中沒有任何目標，而系統(tǒng)卻出現(xiàn)“探測到目標”的情況。