基于不可靠節點序列和面感知路由的目標跟蹤*

曾國定，李超良，2，王國軍*

(1.中南大學信息科學與工程學院，長沙 410083;2.湖南商學院計算機與電子工程系，長沙 410205)

隨著傳感器技術、微機電系統、無線通信和現代網絡等技術的飛速發展，無線傳感器網絡(wireless sensor net works，WSN)應運而生。無線傳感器網絡是由大量的集成了傳感、數據收集、處理和無線通信能力的小體積、低成本的傳感器節點構成的無線自組織網絡，其目的是協作地感知、采集和處理網絡覆蓋的地理區域內感知對象的信息，并傳送給需要這些信息的用戶［1］。由于無線傳感器網絡具有低成本、自組織、體積小和布撒靈活等特性，因此在軍事偵察、環境信息檢測、空間探索、農業生產、醫療健康監護、建筑與家居、工業生產控制、交通控制以及商業等領域有著廣闊的應用前景［2－3］。

基于無線傳感器網絡的目標跟蹤是無線傳感器網絡中應用研究的重點和熱點之一。目標跟蹤在軍事和民用上都有著廣泛的應用，這些應用小到娛樂，大到關系人的生命安全，如機器人足球、犯罪分子的跟蹤、消防中的救援、生物學上的動物跟蹤、軍事上的作戰等。目標跟蹤需要傳感器網絡根據結點的偵測信息判斷目標是否出現;如果目標出現，需要在一定時間內判斷出目標的運動軌跡，這就要求傳感器結點對偵測數據進行處理，根據不同的任務需求和有限資源選擇合適的算法來對目標進行定位，并且通過網絡中的多個結點協同工作、交換偵測信息共同確定目標的運動軌跡，并將跟蹤結果發送給網絡用戶。目前國內外在這方面的研究非常多，已有的目標跟蹤算法都存在各自的優點和不足，如何以最低的能量代價實現高質量的目標跟蹤一直是各種算法追求的核心問題，然而這個目標卻很難實現，因為若要提高目標跟蹤精度，必然要融合更多節點的數據，這就會帶來較高的能量開銷;而若要節省能量，就只能在有限范圍內進行通信和計算，那么跟蹤精度就會受到影響。

文獻［4］提出了一個比較新穎的想法，即基于節點序列的跟蹤模式，根據節點監測到目標的時間長短形成節點序列，并把該節點序列同事先劃分網絡形成的節點序列表進行匹配，從而把求解跟蹤路徑問題轉化為求圖中最短路徑問題，每條最短路徑匹配一個節點序列。該方法有效減少了節點間傳送數據量，從而大大降低了通信能量損耗，但方法中提取的節點序列是不可靠的，而且在節點數目達到一定數量后算法復雜度會顯著提高。本文在文獻［4］的基礎上結合文獻［5］做進一步改進，在面感知路由的基礎上利用基于節點序列的定位算法來跟蹤目標，既達到了減少網絡中數據傳輸量的目的，同時也保證把算法的復雜度控制在一定范圍內。

在無線傳感器的目標跟蹤中，最早提出的跟蹤算法為Nai’ve［6］。該算法使感應區域內的所有傳感器節點一直處于激活狀態，保持對區域的監視。文獻［7］提出的跟蹤算法則是基于預測的思想，對目標下一可能位置進行線性預測，并且激活相應的信標節點，同時目標離開感應區則自動進入睡眠狀態。文獻［8］研究了層次型WSN目標跟蹤的特點，首先加入了雙層預測機制。文獻［9］提出了DCTC算法，使用一個護衛樹來跟蹤目標，其中護衛樹由一個根節點和其他的圍繞在目標周圍的節點組成。文獻［10］提出了一種自適應的目標跟蹤算法，通過設置一定的權值來控制節點的狀態。文獻［11］則提出了一種被動紅外目標跟蹤技術算法，采用紅外線來定位和跟蹤目標。文獻［12］提出了基于監視節點和后備節點的目標跟蹤協議，能對移動目標進行高效的跟蹤和提高目標跟蹤協議的容錯性。

1 相關定義及網絡模型

1.1 節點狀態定義及轉換

本文中傳感器節點設定三個狀態:活動狀態、睡眠狀態、蘇醒狀態。圖1為節點狀態轉換圖。當節點處于睡眠狀態時，將關閉所有功能;當節點處于活動狀態時，它可以偵測目標、接收和傳輸數據;當節點在蘇醒狀態下，節點將開啟偵測、接收功能，可以接收其他節點發過來的請求和喚醒信息。網絡中所有節點都周期性處于睡眠和蘇醒狀態。如果某個節點在蘇醒狀態下偵測到其周圍有目標出現，它將自身狀態轉換為活躍同時向其周圍節點發送喚醒信息，鄰居節點收到喚醒信息后將也進入活動狀態，參與跟蹤;如果蘇醒周期內沒有偵測到目標，則在蘇醒周期結束后自動進入睡眠狀態。在活躍狀態的節點如果發現目標丟失或者目標已經離開自己的偵測區域，節點將轉入睡眠狀態。

圖1 節點狀態轉換圖

1.2 網絡模型

假定在歐幾里德平面上存在一個由n個節點組成的集合V，網絡模型給出如下假設:①被跟蹤的對象，即目標，位于傳感器網絡中，可能是入侵者、運動中的野生動物、蔓延的火情或運動車輛等;②節點要時間同步，隨機地分布在一個二維的平面上，且節點能量有限，具有全向的監測及通訊能力;③節點能發送廣播信號，其他節點收到該廣播信號后會發送確認信號;④傳感器布撒以后，所有節點都能與其鄰居節點通訊，在GPS定位系統和其直接鄰居的合作下，節點能知道其所有的鄰居節點;⑤傳感器網絡同構、能量有限，對于所有的節點來說，監測時的能量消耗是一樣的;⑥目標如果被一個節點監測到，一段時間后又被另一個節點監測到，則認為是同一個目標。

1.3 面感知路由

為了避免節點序列劃分時節點數目過多的問題，采用結合面感知路由的方法，即一種基于地理信息的平面路由策略，這是第一個不需要包副本，也不需要存儲過去的路由信息的路由策略，同時還可以有效避免無線傳感器網絡中容易形成的“黑洞”和“關鍵路徑”問題。面感知路由需要首先將網絡平面化，傳感器網絡可以通過兩個著名的分布式平面化協議Gabriel Graph(GG)和Relative Neighborhood Graph(RNG)來平面化。如果G=(V，E)表示一個圖，u和v是屬于集合V的傳感器節點，如果這兩個節點處于兩者的通訊范圍內，則在節點u和v之間有一條邊uv，如果以uv為直徑的圓內沒有其他節點，則把邊uv稱為Gabriel edge，如果一個圖G中只包含Gabriel edges，則該圖為 Gabriel Graph(GG)，如圖2(a)所示。反之，如圖2(b)所示，以uv為直徑的圓內有其他節點w，則邊uv將在平面化的過程中被刪除。在GG和RNG圖中，我們可以得到一個連接的且具有較少邊的平面子圖G'=(V，E')。

圖2 Gabriel Graph

圖3為一個平面網絡的例子，在平面網絡圖中，沒有交叉邊。如果一個圖中任何兩條邊都沒有交叉邊，并且是無向的，就可以稱這樣的圖為平面圖。平面圖由面構成，面是由多邊構成的一個封閉的區間，如式(1)所示:

一般來說，在多維的空間中，GG連接空間中球的直徑的兩個端點，如式(2)所示:

圖3 平面網絡圖

1.4 基于不可靠節點序列的網絡劃分

如圖4(a)所示，對于一個給定的且知道地理位置節點1和節點2，整個區域將被兩個節點連線的垂直平分線Div(1，2)劃分為兩個部分，位于Div(1，2)下的灰色區域中的點到節點1的距離都比到節點2的距離近，而位于Div(1，2)上的白色區域中的點到節點2的距離則更近。通過這樣的劃分，整個區域中的每一個點可以通過到節點1和2的距離的遠近排列的節點序列來表示，如圖中灰色區域就可以用節點序列(1，2)來表示。相應的整個區域被劃分為兩個面，分別對應兩個節點序列f1:Sf1=(1，2)和f2:Sf2=(2，1)。圖4(b)中列舉了三個節點時的劃分情況，可以看到每一個區域都對應一個唯一的由三個節點形成的節點序列。如果在一個區域內有n個節點，采用節點序列劃分方法，該區域將被劃分成2n個小區域，每一個區域都可以對應一個唯一的由這n個節點形成的節點序列。因此網絡中節點數目增加時，這種劃分方法所形成的節點序列的復雜度也會明顯的增長，所以必須把劃分區域的節點數量控制在一定范圍內。

圖4 網絡劃分

對于給定的節點序列S1和S2，定義節點序列距離SD(S1，S2)為S1和S2中置換的節點對數。如圖2(b)所示，f1和f2兩個區域對應的節點序列分別為Sf1=(1，2，3)和Sf2=(2，1，3)，在Sf1和Sf2中，有一對節點置換過來，即(1，2)?(2，1)，因此SD(Sf1，Sf2)=1。依此類推，Sf1和Sf3有兩對節點置換，因此SD(Sf1，Sf3)=2。具體節點序列間距離的計算算法采用EKT［4］算法進行匹配，找出節點序列距離最小的匹配序列進行定位。

當目標進入偵測區域后，節點根據偵測到目標的時間長短形成一個偵測節點序列，隨著目標的不斷移動時，會形成一系列偵測節點序列，監測目標的節點把這些偵測信息發送到基站，基站把這些偵測節點序列與劃分網絡時形成的節點序列進行匹配，找到序列距離最小的匹配序列，即可把目標該時刻的位置定位于匹配序列所對應區域的幾何中心。通過這一系列的匹配，這一系列偵測節點序列可以一一對應一個幾何中心，這些幾何中心就可以構成跟蹤目標路徑。

本文將不可靠節點序列和面感知路由結合在一起，不僅繼承了節點序列劃分的優點，同時有效控制節點序列劃分中節點的數目。如圖5所示，將圖3中的平面網絡圖采用節點序列劃分方法進行進一步劃分。由于平面網絡圖中構成每一個面的節點數目是有限的，因此可以對平面網絡圖中的每一個面都分別采取節點序列劃分的方法進行劃分，由于構成每一個面的節點數目是有限的，因此劃分時候節點序列長度都控制在了一定范圍內，基于節點序列劃分的算法復雜度也得到了有效控制。劃分完成后，采用不規則多邊形的質心算法將每一個區域的質心計算出來，形成一個全網絡的節點序列表，與跟蹤目標得到的節點序列進行匹配，達到定位的目的。

圖5 平面網絡劃分圖

2 目標跟蹤

無線傳感器網絡部署成功后，網絡中的節點周期性處于睡眠和蘇醒狀態，當某個節點ni在蘇醒狀態下偵測到有目標進入其偵測區域時，它把自身的狀態轉變為活躍狀態，并發出喚醒包喚醒所偵測目標所在面Fi中其他節點參與跟蹤。Fi中節點根據收到信號的時間長短形成一個節點序列，將形成的節點序列與劃分網絡時的節點序列匹配，根據匹配結果找到對應的多邊形的質心作為目標該時刻所在位置。

發現和定位目標之后，還需要跟蹤目標。考慮到無線傳感器網絡能量有限，算法采用基于預測的方案。根據當前偵測到的目標的運動方向和速度，對目標的下一步運動進行預判，我們需要提前喚醒它即將進入的下一個面中的節點，做好跟蹤準備。圖6顯示了一次跟蹤過程。假設在T時刻有目標在F1中。節點n1是所有能偵測到目標的節點中離目標最近并最先發現目標的節點，節點n1發現目標后會將目標所在面F1中的所有節點喚醒參與跟蹤。如圖6(a)所示，節點n1在偵測狀態下發現目標進入跟蹤區域，n1轉變自身為活躍狀態并發送喚醒信息給所在面F1中的其他節點n2、n3、n4，這些節點收到喚醒信息后也將轉入活躍狀態參與跟蹤。而在T+1 時刻，目標有可能會進入 F2、F3、F4、F5中，距離目標最近的節點n1根據收集到的目標運動方向和速度對目標下一步運動進行預測，提前喚醒目標即將進入的面中的節點。如圖3－7(b)所示，假設目標在T+1時刻進入的是F4，節點n1就給離自己最近的F4中節點n4發送消息，讓其提前喚醒F4中的節點n5、n6來參與跟蹤。目標離開F1后，F1中節點將其收到的偵測到目標所需時間發送給離基站最近節點，該節點收集到所有信息后，根據時間長短形成一個節點序列發送到基站，基站采用節點序列匹配算法EKT對目標進行定位。基于不可靠節點序列和面感知路由的跟蹤Target tracking based on Node Sequences and Face Strategy(NSFS)算法如算法1所示。

圖6 跟蹤示意圖

算法1:NSFS

圖7則為一個采用該算法計算出來的相對完整的跟蹤實例。根據圖中所示的跟蹤路徑來看，雖然和目標的實際運動路徑存在一定的誤差，但還是具有一定的跟蹤精度。

圖7 跟蹤移動目標

3 模擬分析

能量問題是目標跟蹤中考慮得最多的問題。為了有效計算節點的能耗，下面將對本章中所采用的耗能模型進行介紹。節點的能量消耗主要為通信能量消耗，因此主要設計節點的通信能量模型，如公式

1所示，ET表示節點每發送一個包的數據所消耗的能量，這部分能量消耗主要包括發射電路損耗和功率放大損耗。

其中，ET-elec表示發射電路損耗的能量，d為兩個節點間的距離。考慮到無線網絡通信時信號隨著距離增加而衰減，給節點的距離設置一個閾值d0，當傳輸距離小于閾值時，采用自由空間模型，當傳輸距離大于等于閾值時，采用多路徑衰減模型。而節點每接收一個包的數據消耗能量為

ER-elec包含是傳輸電路和接收電路消耗的能量。

模擬實驗中，傳感器節點隨機部署，建立了一個200 m×200 m的基本網絡。所有節點的初始能量為50 J。依據目標運動模型，目標節點速度為2 m/s～20 m/s。時間建模為一個離散變量，所有的傳感器節點時間同步。從每個傳感器節點的能量消耗以及目標跟蹤時整個時間的角度來研究算法的性能。設計多個實驗評價不同參數對該協議的性能影響，這些參數包括目標速度、距離、方向和節點的數目。具體參數如表1所示。

模擬實驗采取引入目標移動方向的概率模型來對目標的移動速度和方向的變動進行考慮。根據圖8所示，NSFS協議和不可靠節點序列的在節點數目比較小時，平均能耗相差無幾，但隨著節點數目增加，NSFS協議明顯比不可靠節點序列的平均能耗明顯要低。由于不可靠節點序列算法在節點數目較多時算法復雜度太高，對運行實驗的硬件要求很高，因此在實驗中只節點數目最高只設置到了90個。如圖9所示。在模擬實驗中，將目標移動速度從5 m/s提高至20 m/s，可以看出，NSFS協議的能耗比DOT和基于泛洪的跟蹤算法節點的平均能耗明顯要少，主要是因為在NSFS算法中，由于網絡中通信數據量大大減少，因此通信所消耗的能量也大大減少。為了能對算法中包開銷的總數進行對比，通過計算路由維護，目標跟蹤以及信息交換包，如請求信息和響應信息，得到包開銷的數目。結果如圖10所示。從實驗結果來看，在目標速度比較小的時候，TF比DOT，甚至是NSFS協議的包開銷都要少。但當目標的移動速度增大時，它的包開銷就會急劇增大。在目標速度很大時，NSFS的性能比其他的都要好。當目標的速度增大時，與DOT協議相比，NSFS協議的包開銷逐漸增大。在目標丟失率上，平均丟失率由總的丟失率估算得到，總的丟失率產生在實驗的不同階段，基于目標跟蹤節點的感應半徑，定義為節點沒有探測到移動目標的百分率。如圖11所示，相比移動目標的移動方式是隨機的DOT協議，NSFS算法具有較小的丟失率，因為NSFS算法中傳感器節點是在較小的感應范圍內相互協作探測目標。

表1 模擬參數表

圖8 不同節點數目時的平均能量消耗

圖9 節點平均能量消耗

圖10 不同目標速度下的包開銷

圖11 目標丟失率

4 結束語

本文提出一種基于不可靠節點序列和面感知路由的目標跟蹤算法，該算法同其他跟蹤算法相比，由于減少了網絡中數據的傳輸量，因此在能量節約方面具有較大優勢。但是犧牲了一定的跟蹤精度，未來還需要在這方面提出改進，同時可以考慮把該算法擴展至三維空間。

［1］韓紅彥，張西紅，張曉.無線傳感器網絡研究［J］.科學技術與工程，2007，7(8):1701－1706.

［2］馬祖長，孫怡寧，梅濤，無限傳感器網絡綜述［J］.通信學報，2004，25(4):114－123.

［3］孫利民，李建中.無線傳感器網絡［M］.北京:清華大學出版社.

［4］Ziguo Zhong，Ting Zhu，Dan Wang，et al.Tracking with Unreliable Node Sequences［C］//IEEE INFOCOM 2009:1215－1223.

［5］H-W Tsai，C-P Chu，T-S Chen.Mobile Object Tracking in Wireless Sensor Networks［J］.Computer Communications(Elsevier)，2007，30:1811－1825.

［6］D Mc Erlean，S Narayanan.Distributed Detection and Tracking in Sensor Networks［C］//Signals，Systems and Computers，2002.Conference Record of the Thirty-Sixth Asilomar Conference on，2002，2:1174－1178.

［7］He Tian，Huang Chengdu，Blum BM.Range-Free Localization Schemes in Large Scale Sensor Networks［C］//MobiCom，2003:81－95.

［8］黃侖，徐昌慶.無線傳感器網絡目標跟蹤機制的研究與改進［J］.計算機工程與應用，2006，42(16):140－142，149.

［9］Wensheng Zhang，Guohong Cao，DCTC:Dynamic Convey Tree-Based Collaboration for Target Tracking in Sensor Networks［J］.IEEE Transactions on Wireless Communications，2004，11(5):1689－1701.

［10］彭勇，王國軍，邢蕭飛.無線傳感器網絡中一種自適應目標跟蹤協議［J］.傳感技術學報，2009，22(3):427－432.

［11］王森，陳穎文，徐明，等.無線傳感器網絡被動紅外目標跟蹤技術研究［J］.傳感技術學報，2008，21(11):1929－1934.

［12］Md.Zakirul Alam Bhuiyan，Guojun Wang，Jie Wu.Target Tracking with Monitor and Backup Sensors in Wireless Sensor Networks［C］//ICCCN，2009，8:1－6.