第5章目標跟蹤技術

5.1目標跟蹤的基本原理及跟蹤策略

設計要考慮的問題5.2點目標跟蹤5.3面目標跟蹤5.4小結

5.1目標跟蹤的基本原理及跟蹤策略設計要考慮的問題

5.1.1無線傳感器網(wǎng)絡中目標跟蹤的基本原理

傳感器網(wǎng)絡由大量體積小、成本低，具有感測、通信、數(shù)據(jù)處理能力的傳感器節(jié)點構成，并將大量的傳感器節(jié)點部署在監(jiān)測區(qū)域內(nèi)。自組織成網(wǎng)絡后，經(jīng)過多條路由將數(shù)據(jù)傳輸?shù)綌?shù)據(jù)中心，供用戶使用。傳感器網(wǎng)絡體系通常包括傳感器節(jié)點、匯聚節(jié)點和管理節(jié)點。在不同的應用中傳感器網(wǎng)絡節(jié)點的組成不同，但傳感器節(jié)點都有傳感器模塊、處理器模塊、無線通信模塊和能量供應模塊，其中處理器大都選用嵌入式CPU，通信模塊采用休眠/喚醒機制。各模塊由一個微型操作系統(tǒng)控制。傳感器網(wǎng)絡由大量部署在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點組成，當有目標進入監(jiān)測區(qū)域時，由于目標的輻射特性(通常是紅外輻射特征)、聲傳播特征和目標運動過程中產(chǎn)生的地面震動特征，傳感器會探測到相應的信號。

我們假定把N個傳感器節(jié)點部署在監(jiān)控區(qū)域為S的區(qū)域內(nèi)，網(wǎng)絡總的延時為T。傳感器最大探測半徑為R。任一時刻t，當有目標以速度u進入傳感器節(jié)點探測半徑內(nèi)時，傳感器檢測為“1”；否則檢測為“0”。當網(wǎng)絡探測到目標后便開始利用特定的跟蹤算法與通信方式進行目標定位跟蹤。下面定性地討論現(xiàn)有的三種跟蹤策略，以比較其跟蹤目標的有效性、節(jié)能性以及網(wǎng)絡壽命。

(1)完全跟蹤策略：網(wǎng)絡內(nèi)所有探測到目標的傳感器節(jié)點均參與跟蹤。顯然，這種策略消耗的能量很大，造成了較大的資源浪費，為數(shù)據(jù)融合與消除冗余信息增加了負擔，但同時這種方法提供了較高的跟蹤精度。

(2)隨機跟蹤策略：網(wǎng)絡內(nèi)每個節(jié)點以其概率參與跟蹤，整個跟蹤以平均概率進行跟蹤。顯然，這種策略由于參與跟蹤的節(jié)點數(shù)目得到了限制，因而可以降低能量消耗，但是不能保證跟蹤精度。

(3)協(xié)作跟蹤策略：網(wǎng)絡通過一定的跟蹤算法來適時啟動相關節(jié)點參與跟蹤。通過節(jié)點間相互協(xié)作進行跟蹤，既能節(jié)約能量又能保證跟蹤精度。顯然，協(xié)作跟蹤策略是跟蹤算法的最好選擇。為了對跟蹤策略有一個基本的理解，首先簡單說明一個目標被跟蹤的情況。假定一個物體進入了事先布置和組織好的無線傳感器網(wǎng)絡監(jiān)測區(qū)域，如果感測信息超出了門限，這時每一個處于偵測狀態(tài)的節(jié)點傳感器都能探測到物體，然后把探測信息數(shù)據(jù)包發(fā)送給匯聚節(jié)點。匯聚節(jié)點從網(wǎng)絡內(nèi)收集到數(shù)據(jù)后對信息進行融合，得出物體是否需要被跟蹤的結論，如果目標的確需要被監(jiān)控，傳感器網(wǎng)絡在監(jiān)測區(qū)域內(nèi)將使用一個跟蹤運動目標的算法，隨著目標的運動，跟蹤算法將及時通知合適的節(jié)點參與跟蹤，簡要過程如下：

(1)網(wǎng)絡內(nèi)節(jié)點以一定的時間間隔從休眠狀態(tài)轉(zhuǎn)換到監(jiān)測狀態(tài)，偵測是否有目標出現(xiàn)。

(2)傳感器節(jié)點檢測到目標進入探測范圍后，通過操作系統(tǒng)喚醒通信模塊并向網(wǎng)絡內(nèi)廣播信息包，記錄下目標進入?yún)^(qū)域所持續(xù)的時間。信息包中含有傳感器節(jié)點身份號碼和傳感器位置坐標以及目標在探測范圍內(nèi)持續(xù)的時間。

(3)當匯聚節(jié)點接收到K個節(jié)點發(fā)送的信息后，由目標跟蹤公式計算出目標位置。

(4)匯聚節(jié)點根據(jù)接收到的信息和融合信息，通過使用跟蹤算法啟動相應的節(jié)點參與跟蹤。

(5)當目標離開監(jiān)測區(qū)域時，節(jié)點向匯聚節(jié)點報告自己的位置信息以及目標在節(jié)點探測范圍內(nèi)所持續(xù)的時間。匯聚節(jié)點綜合歷史數(shù)據(jù)和新信息形成目標的運動趨勢。5.1.2無線傳感器網(wǎng)絡跟蹤策略設計要考慮的問題

傳感器網(wǎng)絡跟蹤目標涉及到目標探測、目標定位、通信、數(shù)據(jù)融合、跟蹤算法的設計等很多方面的問題。在跟蹤過程中，如果選擇不合適的節(jié)點參與跟蹤，不但跟蹤精度較低甚至有可能丟失目標，并且會過多地消耗不必要的能量。同時算法的優(yōu)劣也直接影響著跟蹤的效果。衡量一個跟蹤策略是否具有較好的跟蹤效果，需要考慮以下問題：

(1)跟蹤精度。跟蹤精度是目標跟蹤中首先要考慮的一個問題，當然也并不是跟蹤精度越高就越好，精度越高意味著算法融合的數(shù)據(jù)越多，這樣會增加能量消耗，所以還要結合能量消耗，綜合評價跟蹤算法的優(yōu)劣。

(2)跟蹤能量消耗。由于用無線傳感器網(wǎng)絡跟蹤目標大都應用于實際環(huán)境，節(jié)點的能量消耗是一個非常關鍵的問題。因而要求傳感器節(jié)點最好不但能儲備能量(電池)，而且還要根據(jù)實際情況可以現(xiàn)場蓄能(太陽能)。跟蹤過程中選擇合適的節(jié)點參與跟蹤需要考慮該節(jié)點的通信能量消耗、感測能量消耗和計算能量消耗，其中通信能量消耗是最主要的部分。在設計考慮跟蹤算法時要綜合衡量這幾種能量消耗，找到合適的比重，以滿足較低的能量消耗，從而延長節(jié)點和網(wǎng)絡的壽命。

(3)跟蹤的可靠性。網(wǎng)絡的可靠性對目標跟蹤的質(zhì)量有很大的影響。當前應用于目標跟蹤的方法主要有集中式和分布式，集中式方法要求所有網(wǎng)絡節(jié)點在探測到目標后都要向匯聚節(jié)點發(fā)回探測結果，不但引入的通信開銷大，而且計算開銷也增加很多，這樣網(wǎng)絡的可靠性下降很快。分布式方法是一種較好的選擇，但是也要充分考慮跟蹤算法的魯棒性，能適應環(huán)境的變化，以增強網(wǎng)絡的可靠性。

(4)跟蹤的實時性。在實際應用中跟蹤的實時性是一個很重要的指標，實時性能主要由硬件性能、算法的具體設計以及網(wǎng)絡拓撲等多方面決定，在硬件技術飛速發(fā)展的今天，算法的實時性與網(wǎng)絡拓撲結構的選擇便越發(fā)顯得重要。

5.2點?目?標?跟?蹤

5.2.1雙元檢測協(xié)作跟蹤

傳感器節(jié)點具有體積小和價格低的特點，它的傳感器模塊功能比較弱。下面介紹最簡單的情況，即傳感器節(jié)點只能進行雙元檢測(binary-detection)時的目標跟蹤。

1.雙元檢測

雙元檢測傳感器只有兩種偵測狀態(tài)，即目標處在傳感器偵測距離之內(nèi)或者之外。圖5-1給出了這種雙元傳感器的模型，其中實心點表示傳感器節(jié)點。對于節(jié)點的偵測距離R，當目標距傳感器節(jié)點的距離在(R-e)之內(nèi)時總會被檢測到；當目標距節(jié)點距離在(R?+?e)之外時不會被檢測到；當目標距節(jié)點距離在(R?-?e)和(R?+?e)之間時以一定的概率被檢測到。通常情況下e?=?0.1R。圖5-1雙元檢測傳感器模型

2.基于雙元檢測的協(xié)作跟蹤

雙元檢測傳感器不能檢測它到目標的距離，只能判斷目標是否在偵測范圍內(nèi)。因此檢測到目標的節(jié)點只能確定包含目標的圓形區(qū)域，還需要多個節(jié)點協(xié)作才能確定目標的位置信息。當目標進入偵測區(qū)域后，在節(jié)點足夠密集的情況下，任何時刻都有多個節(jié)點同時偵測到目標的位置區(qū)域。這些節(jié)點偵測范圍的重疊區(qū)域是一個相對較小的區(qū)域，目標就處于這個重疊區(qū)域內(nèi)，這樣，就能相對精確地確定目標位置。由于目標運動具有隨機性，要跟蹤這樣不規(guī)則的運動軌跡十分困難。在不影響跟蹤結果的條件下，假設目標在節(jié)點的偵測范圍內(nèi)勻速運動，從而將目標運動軌跡近似為一條折線。由于單個傳感器節(jié)點的偵測范圍比較小，這樣的假設很接近目標的真實運動軌跡。通過大量節(jié)點的協(xié)作可以進一步提高跟蹤精度。雙元檢測協(xié)作跟蹤的基本過程如下：

(1)當節(jié)點偵測到目標進入偵測區(qū)域時，喚醒自身的通信模塊并向鄰居節(jié)點廣播檢測到目標的消息。消息中包含節(jié)點ID以及自身位置信息。同時該節(jié)點開始記錄目標出現(xiàn)的持續(xù)時間。

(2)如果節(jié)點檢測到目標出現(xiàn)，同時接收到兩個或兩個以上節(jié)點發(fā)送的通告消息，則節(jié)點計算目標位置。計算時采用目標在節(jié)點偵測范圍內(nèi)的持續(xù)時間作為權重。

(3)當目標離開偵測區(qū)域時，節(jié)點向匯聚節(jié)點發(fā)送自己的位置信息以及目標在自己偵測區(qū)域內(nèi)的持續(xù)時間信息。匯聚節(jié)點根據(jù)已有的歷史數(shù)據(jù)和當前獲得的最新數(shù)據(jù)進行線性擬合，計算移動目標的運動軌跡。雙元檢測傳感器雖然不能確定它到目標的距離，卻可確定目標在自己檢測范圍內(nèi)的持續(xù)時間。如圖5-2所示，假設移動目標勻速運動，則目標在監(jiān)測區(qū)域內(nèi)的持續(xù)時間越長，就表明它離節(jié)點越近，該節(jié)點的偵測數(shù)據(jù)也就越精確。因此檢測到目標時間長的節(jié)點，它的數(shù)據(jù)應具有較大的權重。

基于雙元檢測的協(xié)作跟蹤適用于簡單低廉的傳感器節(jié)點，并通過大量密集部署節(jié)點保證跟蹤精度，另外，該協(xié)作跟蹤需要節(jié)點間的時鐘同步，并要求節(jié)點知道自身的位置信息。圖5-2目標持續(xù)時間長度與計算權重的關系5.2.2信息驅(qū)動協(xié)作跟蹤

對移動目標的偵測、分類、跟蹤通常需要在傳感器節(jié)點間進行協(xié)作。對節(jié)點跟蹤數(shù)據(jù)的融合能夠有效地提高跟蹤精度。通過選擇合適的節(jié)點進行協(xié)作能降低節(jié)點間的數(shù)據(jù)通信量，從而節(jié)省節(jié)點能量和通信帶寬。協(xié)作跟蹤的關鍵在于如何通過節(jié)點間交換跟蹤信息實現(xiàn)對目標運動軌跡較為精確的跟蹤，同時盡量減少節(jié)點的能量消耗。協(xié)作跟蹤的關鍵問題包括確定讓哪些節(jié)點進行跟蹤，需要獲取哪些偵測數(shù)據(jù)以及節(jié)點間必須交換哪些信息。根據(jù)綜合考慮節(jié)點獲得的跟蹤信息的有效性和精確度，以及節(jié)點完成跟蹤任務需要的能量代價來決定哪些傳感器節(jié)點應參與跟蹤過程以及跟蹤節(jié)點間的協(xié)作方式。信息驅(qū)動(information-driven)協(xié)作跟蹤的核心思想就是傳感器節(jié)點利用自己偵測到的信息和接收到的其他節(jié)點的偵測信息判斷目標可能的運動軌跡，喚醒合適的傳感器節(jié)點在下一時刻參與跟蹤活動。由于使用了合適的預測機制，信息驅(qū)動的協(xié)作跟蹤能夠有效地減少節(jié)點間的通信量，從而節(jié)省節(jié)點有限的能量資源和通信資源。

1．信息驅(qū)動的協(xié)作跟蹤方法

由于目標運動軌跡沒有規(guī)律，而且目標還可能作加速或減速運動，因此通過預先選定的一些傳感器節(jié)點進行目標跟蹤會產(chǎn)生一些問題。首先是不能保證有效的跟蹤，其次是跟蹤效率較低，有些不在目標運動軌跡附近的節(jié)點也要參與跟蹤。為此，有些學者提出了基于信息驅(qū)動的協(xié)作跟蹤方法，使傳感器節(jié)點能夠通過交換局部信息來選擇合適的節(jié)點檢測目標并傳遞信息。

圖5-3表示了一個信息驅(qū)動的協(xié)作跟蹤實例。網(wǎng)絡中包括兩類傳感器節(jié)點，分別裝有角度傳感器和距離傳感器。圖中的粗線表示目標穿過傳感器網(wǎng)絡的軌跡，虛線邊界圓形區(qū)域為傳感器節(jié)點的偵測范圍，用戶通過匯聚節(jié)點(如圖5-3中節(jié)點Q)查詢目標跟蹤信息，要求傳感器網(wǎng)絡每隔一段時間報告一次目標位置。任何時刻傳感器網(wǎng)絡中至少有一個節(jié)點處于活動狀態(tài)，負責存放當前目標跟蹤狀態(tài)信息，這個節(jié)點稱為跟蹤節(jié)點。隨著目標的移動，當前跟蹤節(jié)點負責喚醒并將現(xiàn)有的跟蹤信息傳遞給下一個跟蹤節(jié)點。目標進入傳感器區(qū)域時，離目標最近的節(jié)點a獲得目標位置的初始估計值，并計算出下一時刻節(jié)點b進行跟蹤時能夠保證偵測數(shù)據(jù)的精度，使自己到節(jié)點b的通信代價在規(guī)定的范圍內(nèi)，則將獲得的目標位置估計值傳給節(jié)點b。b使用相同的標準選擇下一個跟蹤節(jié)點c，這個過程不斷重復直到目標離開傳感器網(wǎng)絡偵測區(qū)域。每隔一段時間節(jié)點就將目標的位置信息返回給匯聚節(jié)點。圖5-3信息驅(qū)動的協(xié)作跟蹤實例

2.跟蹤節(jié)點的選擇

信息驅(qū)動的協(xié)作跟蹤的核心問題是如何選擇下一時刻的跟蹤節(jié)點。如果選擇了不合適的節(jié)點，傳感器網(wǎng)絡可能會丟失跟蹤目標或者產(chǎn)生多余的通信代價。選取下一時刻最優(yōu)跟蹤節(jié)點的策略需要綜合考慮該節(jié)點偵測數(shù)據(jù)對結果的影響以及當前節(jié)點到該節(jié)點的通信代價，如何以較小的能量消耗代價來提高目標位置估計的準確性。

1)偵測精度評估

結合附近傳感器節(jié)點的數(shù)據(jù)，能提高當前目標位置估計結果的精確性。傳感器節(jié)點并不是都能提供可靠的信息，而且有些數(shù)據(jù)信息雖然有效，卻是冗余的。因此就要尋找一個最優(yōu)化的節(jié)點子集，并且確定這些節(jié)點數(shù)據(jù)加入目標位置估計過程的最佳順序。通過計算傳感器節(jié)點到當前目標的有效估測范圍的均值，可以評價節(jié)點數(shù)據(jù)的有效性。假設目標位置的估計服從高斯分布，則可以用不確定性橢圓表示。如圖5-4所示，實線橢圓表示當前目標位置估計，虛線橢圓表示在下一時刻結合了傳感器節(jié)點S1或S2的測量值后的目標位置估計。結合傳感器節(jié)點S1或S2的測量值都可能提高對當前目標狀態(tài)估計的精確性，但由于傳感器節(jié)點S1，S2位置不同，得到的估計結果也不同。雖然分別結合這兩個節(jié)點偵測數(shù)據(jù)后的估計結果都會減少不確定性橢圓的面積，但大小不同，選擇令橢圓面積更小的節(jié)點作為下一個跟蹤節(jié)點。若減少了相同面積，但如果結合節(jié)點S2偵測數(shù)據(jù)后不確定性橢圓仍然有很長的長軸，而結合節(jié)點S1偵測數(shù)據(jù)后橢圓的長軸大大縮短，考慮到高斯分布中不確定性橢圓的長軸越長則表示不確定性越高，因此選取S1作為新的跟蹤節(jié)點能夠得到對目標位置更加精確的估計。圖5-4基于信息增益的傳感器選擇

2)代價評估

選擇下一時刻的跟蹤節(jié)點需要考慮該節(jié)點的通信代價、該節(jié)點獲取目標位置信息的消耗代價以及該節(jié)點結合自身偵測結果和接收到的偵測結果時的能量消耗。這三部分能量消耗分別是通信能量消耗、感應能量消耗和計算能量消耗，其中通信能量消耗是主要部分。一般來說，對于傳感特征相同的節(jié)點，相互距離越近這些代價將越小。因此跟蹤節(jié)點選擇令目標位置估計不確定性橢圓面積減少最多的鄰居節(jié)點作為下一個跟蹤節(jié)點，將能以較小的能量消耗來提高目標位置估計的準確性。基于信息驅(qū)動的目標跟蹤方法在保證跟蹤精度的同時盡量減少由于節(jié)點間不必要的通信帶來的能量消耗。衡量節(jié)點間的不確定性是估計一個節(jié)點是否能增加偵測精度的一種可行方法。而在考慮節(jié)點跟蹤精度的同時也要考慮節(jié)點間能量消耗。如何更好地結合這兩個因素是未來信息驅(qū)動跟蹤中的一個重要問題。由于節(jié)點能夠智能地決定后繼跟蹤節(jié)點，所以信息驅(qū)動的跟蹤方法能夠大幅地減少參加跟蹤活動的節(jié)點數(shù)量，從而減少整個網(wǎng)絡的能量消耗。5.2.3傳送樹跟蹤算法

目前大多數(shù)傳感器網(wǎng)絡跟蹤算法都是集中式的，傳感器節(jié)點需要把跟蹤信息傳送到數(shù)據(jù)中心去進行綜合處理。本節(jié)介紹的基于傳送樹的跟蹤算法是一種分布式算法，節(jié)點只在本地收集數(shù)據(jù)并通過局部節(jié)點交換信息以完成目標跟蹤。

傳送樹(conveytree)是一種由移動目標附近的節(jié)點組成的動態(tài)樹型結構，并且會隨著目標的移動，動態(tài)地添加或者刪除一些節(jié)點。移動目標附近的節(jié)點通過傳送樹結構進行協(xié)作跟蹤，在保證對目標進行高效跟蹤的同時減少節(jié)點間的通信開銷。圖5-5表示通過傳送樹進行目標跟蹤的過程。如圖5-5(a)所示，目標進入偵測區(qū)域時，在探測到目標的傳感器節(jié)點中選出一個根節(jié)點，并構造出初始傳送樹。傳送樹上每個節(jié)點周期性發(fā)出偵測信息，并傳送到根節(jié)點。根節(jié)點收集傳送樹上所有節(jié)點的偵測報告，進行數(shù)據(jù)融合處理，并將處理結果發(fā)送到匯聚節(jié)點。隨著目標的移動，傳送樹刪除那些距離目標越來越遠的節(jié)點，喚醒目標移動方向上的節(jié)點并將其加入傳送樹。當目標與根節(jié)點的距離超過一定閾值時，需要重新選出根節(jié)點并重新構造傳送樹，如圖5-5(b)所示。圖5-5基于動態(tài)傳送樹的目標跟蹤為了節(jié)省傳感器節(jié)點的能量，傳感器網(wǎng)絡采用網(wǎng)格狀的分簇結構。簇內(nèi)節(jié)點周期性地擔任簇頭節(jié)點。當該網(wǎng)格沒有偵測事件發(fā)生時，只有簇頭節(jié)點處于工作狀態(tài)，普通節(jié)點則處于休眠狀態(tài)。當移動目標進入網(wǎng)格時，簇頭節(jié)點負責喚醒單元格中的其他節(jié)點。傳送樹跟蹤算法包括如下3個關鍵問題：當目標第一次出現(xiàn)在監(jiān)視區(qū)域中時，構造一棵初始傳送樹；隨著目標的移動對傳送樹進行調(diào)整；當根節(jié)點距離目標超過閾值時重新選出根節(jié)點并重構傳送樹。

1.初始傳送樹的建造

當目標第一次進入傳感器網(wǎng)絡的偵測區(qū)域時，它附近的簇頭節(jié)點會探測到目標，并且立刻喚醒網(wǎng)格內(nèi)的其他節(jié)點。被喚醒的節(jié)點相互交換自己到目標的距離，并選出當前距離目標最近的節(jié)點作為傳送樹的根節(jié)點。如果幾個節(jié)點到目標的距離相同，就選擇節(jié)點號小的節(jié)點作為根節(jié)點。選舉根節(jié)點的過程分為兩個階段：第一階段中，每個工作節(jié)點都廣播一個選舉消息給所有的鄰居節(jié)點，選舉消息包括本節(jié)點到目標的距離以及節(jié)點號信息。如果某個節(jié)點在所有鄰居節(jié)點中到目標的距離最短，則該節(jié)點成為根節(jié)點的候選者；否則，它就放棄競選根節(jié)點并選擇鄰居中距離目標最近的節(jié)點作為父節(jié)點。第二階段，每個根節(jié)點候選者向整個網(wǎng)絡廣播勝利者消息，勝利者消息仍然包括自己到目標的距離以及節(jié)點號信息。如果某個候選者收到一個勝利者消息，而且該勝利者到目標的距離比自己到目標的距離小，它就放棄競選根節(jié)點并且選擇轉(zhuǎn)發(fā)勝利者消息的節(jié)點作為父節(jié)點。最終選出距離目標最近的節(jié)點成為傳送樹的根節(jié)點，其他能夠偵測到目標的節(jié)點都連接至該傳送樹。

2.傳送樹的調(diào)整

由于目標的移動，傳送樹上有些節(jié)點不再能夠偵測到目標，而另外一些處于目標移動方向上的節(jié)點需要加入傳送樹。當傳送樹上的節(jié)點發(fā)現(xiàn)自己不能偵測到目標時，向父節(jié)點發(fā)出通告，父節(jié)點將其從傳送樹上刪除。為了確定需要加入傳送樹的節(jié)點，目前提出了保守機制和預測機制兩種方法。這兩種方法都由根節(jié)點計算需要增加的節(jié)點。在如圖5-6(a)所示的保守機制中，到當前目標位置的距離小于的節(jié)點都將包含在傳送樹中。其中，vt是目標當前的移動速度，是一個全局參數(shù)，ds是節(jié)點監(jiān)控區(qū)域的半徑。這個方案假設目標以小于的速度向任意方向移動。為了令下一時刻凡偵測到目標的節(jié)點都位于傳送樹上，參數(shù)應該足夠大。但如果過大，傳送樹將包含許多冗余節(jié)點。為減少保守機制中的冗余節(jié)點，有些學者提出了一種預測機制。該機制假設可以通過一定的方向預測技術判斷出目標未來的位置。只有處在預測監(jiān)控范圍內(nèi)的節(jié)點才能加入傳送樹。如圖5-6(b)所示，只有那些到目標預測位置的距離小于ds的節(jié)點才會加入傳送樹。由于目標的移動方向不會頻繁的改變，所以預測機制能夠在大大減少冗余節(jié)點的同時保證對目標的跟蹤。

確定需要加入傳送樹的節(jié)點后，根節(jié)點向這些節(jié)點所在網(wǎng)格的簇頭節(jié)點發(fā)送通告信息，并由簇頭節(jié)點喚醒它們。這些節(jié)點將選擇自己鄰居中到目標距離最近的節(jié)點作為父節(jié)點。圖5-6基于動態(tài)傳送樹的目標跟蹤

3.傳送樹的重構

當目標到根節(jié)點的距離超過一定閾值時，需要重構傳送樹以保證對目標的跟蹤。這個閾值為dm?+?a?+?vt。其中dm表示最小的重構距離，vt為t時刻的目標速度，a為一個小數(shù)。

重構傳送樹仍舊按照上述算法選舉距離目標最近的節(jié)點作為新的根節(jié)點。當新的根節(jié)點選出后，要進行根的遷移。由于當前根節(jié)點只知道新的根節(jié)點離目標較近，所以原先的根節(jié)點先尋找目標當前的單元格，然后向該單元格的頭節(jié)點發(fā)送遷移請求。收到請求后，頭節(jié)點把這個消息發(fā)給新的根節(jié)點。在根節(jié)點改變后，網(wǎng)絡需要重構傳送樹以使收集各節(jié)點數(shù)據(jù)的能量消耗最小。新的根節(jié)點先廣播一個重組消息給它的鄰居。收到重組消息的節(jié)點在重組信息包中加入自身的位置信息和與根節(jié)點通信的代價信息，并繼續(xù)廣播。當其余任何節(jié)點收到重組消息后，都等待一定的時間以便收集所有發(fā)送給自己的重組消息。然后，每個節(jié)點選擇與根節(jié)點的通信代價最小的鄰居節(jié)點作為自己的父節(jié)點。這個過程將持續(xù)到監(jiān)控區(qū)域內(nèi)的所有節(jié)點都加入到樹中為止。傳送樹是傳感器節(jié)點協(xié)作跟蹤的一種可行方案，移動目標附近的節(jié)點通過加入傳送樹將偵測信息匯聚到樹根節(jié)點。通過增加和刪除適當?shù)墓?jié)點以及重構傳送樹，可以保證對目標的有效跟蹤。選擇距離目標最近的節(jié)點作為根節(jié)點，并且每個節(jié)點只將自己的數(shù)據(jù)傳送給父節(jié)點，從而降低了數(shù)據(jù)傳輸?shù)娜哂嘈浴Ｊ褂梅执氐耐負浣Y構也減少了整個網(wǎng)絡的能量消耗。但是根節(jié)點需要進行數(shù)據(jù)融合和新節(jié)點的計算，能量消耗比較大。

5.3面?目?標?跟?蹤

傳感器網(wǎng)絡跟蹤中，很多情況下需要跟蹤面積較大的目標，例如森林火災中火災邊緣的推進軌跡，臺風的行進路線等。在這種情況下僅僅通過局部節(jié)點的協(xié)作無法偵測到完整的目標移動軌跡，為此有些學者提出使用對偶空間轉(zhuǎn)換的方法決定由哪些節(jié)點參與跟蹤，以保證對目標移動軌跡的完整偵測。5.3.1對偶空間轉(zhuǎn)換

考慮初始二維空間的直線，它由和兩個參數(shù)唯一確定，其中表示斜率，表示截距。定義這條直線的兩個參數(shù)在初始空間的對偶空間中用點表示。同樣地，初始空間中的點(a，b)定義了對偶空間中的一條直線Φ?=?aθ?+?b。這是一個一一映射關系，如圖5-7所示。圖5-7初始空間與對偶空間的映射關系假設將面積較大的目標看成一個半平面，則它的邊界就是一條直線。對偶空間變換就是將每個傳感器節(jié)點映射為對偶空間中的一條直線，將目標的邊界映射為對偶空間中的一個點。這樣，在初始空間中無規(guī)律分布的傳感器節(jié)點在對偶空間中便成為許多相交的直線，并將對偶空間劃分為眾多子區(qū)域，而跟蹤目標的邊界映射到對偶空間中則是一個點，并處于某個子區(qū)域中，如圖5-8所示。這個子區(qū)域?qū)膸讞l相交直線就是離目標最近的傳感器節(jié)點，再通過到初始空間的逆變換確定此時需要的跟蹤節(jié)點。圖5-8對偶空間映射通過對偶跟蹤的方法，跟蹤問題轉(zhuǎn)換為在對偶空間中尋找包括目標邊界映射點的子區(qū)域。當目標移動時，映射點會進入其他子區(qū)域，這時需要喚醒新區(qū)域中的節(jié)點進行跟蹤，而讓原有區(qū)域中不再屬于新區(qū)域的節(jié)點轉(zhuǎn)入休眠狀態(tài)。5.3.2對偶空間跟蹤算法

假設傳感器節(jié)點知道自己是否處于跟蹤目標的半平面內(nèi)，并且處于該半平