王 楷，任 靜，熊慶宇，張志強(qiáng)

（重慶大學(xué)自動化學(xué)院，重慶 400030）

0 引言

目標(biāo)跟蹤是無線傳感器網(wǎng)絡(luò)的重要應(yīng)用之一，傳感器節(jié)點(diǎn)具有體積小、價格低、布撒容易等優(yōu)點(diǎn)，但是由于其能量有限［1］，影響到許多應(yīng)用的生命周期，因此，減少節(jié)點(diǎn)能耗是在設(shè)計目標(biāo)跟蹤算法時首要考慮的因素。目前，很多睡眠調(diào)度策略［2］已經(jīng)廣泛地應(yīng)用于無線傳感器網(wǎng)絡(luò)中，可以大大地節(jié)省能耗，然而，現(xiàn)有的睡眠調(diào)度協(xié)議［3，4］沒有考慮到目標(biāo)跟蹤應(yīng)用的實(shí)際要求，直接應(yīng)用到目標(biāo)跟蹤任務(wù)中不僅不能降低能耗［5］，而且還會導(dǎo)致目標(biāo)跟蹤質(zhì)量退化。

為了能在能量有效性和跟蹤質(zhì)量之間做出平衡［6］，本文提出一種面向目標(biāo)跟蹤的傳感器網(wǎng)絡(luò)睡眠調(diào)度協(xié)議（sleep scheduling protocol for target tracking in sensor networks，TTSSP），本算法將所有的傳感器節(jié)點(diǎn)分為偵測、通信、跟蹤、睡眠4個狀態(tài)，針對不同的節(jié)點(diǎn)分配不同的幾種狀態(tài)，各個節(jié)點(diǎn)在不同的狀態(tài)之間進(jìn)行轉(zhuǎn)換。在初始狀態(tài)整個監(jiān)控區(qū)域沒有目標(biāo)時，監(jiān)控區(qū)域節(jié)點(diǎn)按照目標(biāo)跟蹤前的節(jié)點(diǎn)調(diào)度;當(dāng)有目標(biāo)進(jìn)入監(jiān)控區(qū)域時，節(jié)點(diǎn)調(diào)度進(jìn)入跟蹤調(diào)度策略，邊界簇頭節(jié)點(diǎn)轉(zhuǎn)入跟蹤狀態(tài)，其他節(jié)點(diǎn)以一定的周期在睡眠和通信狀態(tài)之間進(jìn)行切換，等待被喚醒;當(dāng)目標(biāo)發(fā)生意外丟失時，則進(jìn)入目標(biāo)丟失時的節(jié)點(diǎn)調(diào)度策略。TTSSP在降低跟蹤能耗的同時能夠很好地保證跟蹤質(zhì)量。

本文首先從能耗入手，更加細(xì)致地劃分了不同節(jié)點(diǎn)各個跟蹤節(jié)點(diǎn)的工作模式，提出能量有效的睡眠調(diào)度機(jī)制，平衡跟蹤質(zhì)量和能耗之間的需求;其次根據(jù)目標(biāo)跟蹤的不同節(jié)點(diǎn)來決定節(jié)點(diǎn)的睡眠機(jī)制，使整個網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)合理地協(xié)同工作;最后Matlab仿真軟件驗(yàn)證了所提出的算法，實(shí)驗(yàn)表明:TTSSP在降低跟蹤能耗的同時能夠很好地保證跟蹤質(zhì)量。

1 網(wǎng)絡(luò)模型

1.1 基本前提條件

監(jiān)控區(qū)域內(nèi)只有一個移動目標(biāo)進(jìn)入，或者是一個接一個，不存在同時有2個目標(biāo)在監(jiān)控區(qū)域內(nèi)的情況［7］;監(jiān)控區(qū)域完全被節(jié)點(diǎn)覆蓋，節(jié)點(diǎn)的感知區(qū)域是以R為半徑的圓形區(qū)域，節(jié)點(diǎn)的感知區(qū)域和通信半徑相等，節(jié)點(diǎn)自身位置是已知的，可以通過GPS或者定位算法計算得到［8］;只要能有節(jié)點(diǎn)能夠感知到目標(biāo)節(jié)點(diǎn)，便可以利用加權(quán)定位算法計算得到目標(biāo)的位置［9］;各個節(jié)點(diǎn)的時鐘同步。

1.2 網(wǎng)絡(luò)體系結(jié)構(gòu)

監(jiān)控區(qū)域被劃分為若干個虛擬單元格，每個節(jié)點(diǎn)根據(jù)其地理位置信息劃入相應(yīng)的單元格，每個虛擬單元格稱為一個簇，處于監(jiān)控區(qū)域邊界的簇稱為邊界簇。如圖1所示，可以將整個監(jiān)控網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)分為三類，即邊界簇頭節(jié)點(diǎn)，負(fù)責(zé)感知監(jiān)控區(qū)域是否有目標(biāo)出現(xiàn);簇頭節(jié)點(diǎn)，目標(biāo)來臨后負(fù)責(zé)目標(biāo)定位和調(diào)度其簇內(nèi)節(jié)點(diǎn);簇內(nèi)節(jié)點(diǎn)，負(fù)責(zé)跟蹤目標(biāo)。

圖1 監(jiān)控網(wǎng)絡(luò)模型Fig 1 Model of monitoring network

在TTSSP，所有節(jié)點(diǎn)的工作狀態(tài)分為偵測、通信、跟蹤、睡眠4個狀態(tài)，偵測狀態(tài)指感知模塊和計算部件處于工作狀態(tài);通信狀態(tài)則是指無線通信模塊和計算部件處于激活狀態(tài);跟蹤狀態(tài)指傳感器節(jié)點(diǎn)所有模塊都工作;睡眠狀態(tài)指節(jié)點(diǎn)所有模塊都關(guān)閉，但是節(jié)點(diǎn)可以通過定時器激活。各個模式之間的轉(zhuǎn)換如圖2所示。

圖2 TTSSP各個狀態(tài)之間轉(zhuǎn)換示意圖Fig 2 Diagram of converting between each state of TTSSP

2 基于睡眠調(diào)度的目標(biāo)跟蹤算法TTSSP

2.1 目標(biāo)跟蹤前的節(jié)點(diǎn)調(diào)度

在整個監(jiān)控網(wǎng)絡(luò)布置完成后，只有邊界簇頭節(jié)點(diǎn)處于偵測狀態(tài)，因此，可以保證整個監(jiān)控區(qū)域的邊界都覆蓋到，當(dāng)沒有檢測到目標(biāo)進(jìn)入時，為了保證整個網(wǎng)絡(luò)的能量均衡性，延長整個網(wǎng)絡(luò)的生命周期，必須保證邊界簇內(nèi)的節(jié)點(diǎn)均衡地成為簇頭節(jié)點(diǎn)，邊界簇內(nèi)的所有節(jié)點(diǎn)通過定時器會周期性地醒來，根據(jù)判斷到剩余的能量來確定邊界簇頭節(jié)點(diǎn)。

當(dāng)目標(biāo)沒有到達(dá)監(jiān)控區(qū)域時，在一個網(wǎng)格內(nèi)所有的簇頭節(jié)點(diǎn)和其簇內(nèi)節(jié)點(diǎn)處于睡眠狀態(tài)，通過自身的定時器固定時間喚醒，轉(zhuǎn)入通信狀態(tài)，若收到跟蹤任務(wù)時，簇頭節(jié)點(diǎn)或者簇內(nèi)節(jié)點(diǎn)立即轉(zhuǎn)入跟蹤狀態(tài)，若沒收到消息則轉(zhuǎn)入睡眠狀態(tài)。要保證一個網(wǎng)格內(nèi)有節(jié)點(diǎn)處于通信狀態(tài)，跟蹤任務(wù)到達(dá)時有節(jié)點(diǎn)加入跟蹤任務(wù)，在設(shè)定節(jié)點(diǎn)定時器時要設(shè)定不同的周期使一簇內(nèi)的節(jié)點(diǎn)交替醒來，而不是統(tǒng)一醒來或者睡眠。

2.2 跟蹤目標(biāo)時的節(jié)點(diǎn)調(diào)度

當(dāng)邊界簇頭節(jié)點(diǎn)檢測到目標(biāo)出現(xiàn)時，首先將自身狀態(tài)轉(zhuǎn)變?yōu)楦櫊顟B(tài)，并不斷廣播喚醒信號至一跳內(nèi)的所有節(jié)點(diǎn)，所有處于偵測狀態(tài)的節(jié)點(diǎn)收到邊界簇頭節(jié)點(diǎn)發(fā)送的信號后，立即將自身狀態(tài)轉(zhuǎn)變?yōu)楦櫊顟B(tài)，并利用基于感知信號強(qiáng)度的加權(quán)定位算法對目標(biāo)的位置進(jìn)行計算，同時鄰居簇頭節(jié)點(diǎn)收到信息后轉(zhuǎn)發(fā)相同信號喚醒其簇內(nèi)的節(jié)點(diǎn)，準(zhǔn)備進(jìn)行目標(biāo)跟蹤。

當(dāng)前簇頭節(jié)點(diǎn)根據(jù)其簇內(nèi)節(jié)點(diǎn)計算得到的目標(biāo)的位置信息對目標(biāo)軌跡進(jìn)行預(yù)測，本文采用基于最小二乘法多項(xiàng)式擬合方法預(yù)測出來目標(biāo)將要進(jìn)入的區(qū)域，當(dāng)前簇頭將此信息發(fā)送給鄰居簇頭，鄰居簇頭計算自己是否在監(jiān)測區(qū)域內(nèi)，若在將自身狀態(tài)轉(zhuǎn)變?yōu)楦櫊顟B(tài)并發(fā)送喚醒信號到其簇內(nèi)節(jié)點(diǎn)。由于目標(biāo)的機(jī)動特性差別很大，當(dāng)目標(biāo)的運(yùn)動速度比較低時，由距離目標(biāo)較近的節(jié)點(diǎn)發(fā)射喚醒信號，目標(biāo)高速運(yùn)動時，由距離較遠(yuǎn)的節(jié)點(diǎn)發(fā)射，以便喚醒更遠(yuǎn)處的節(jié)點(diǎn)。這樣就避免了目標(biāo)已經(jīng)高速通過當(dāng)前簇，丟失目標(biāo)的情況。

當(dāng)目標(biāo)由當(dāng)前簇所在區(qū)域進(jìn)入下一區(qū)域后，當(dāng)前簇內(nèi)節(jié)點(diǎn)感知目標(biāo)信號強(qiáng)度值將會變得很弱，每個傳感器節(jié)點(diǎn)根據(jù)自身感知到的目標(biāo)信號強(qiáng)度值來確定自身是否轉(zhuǎn)入睡眠狀態(tài)，具體感知信號強(qiáng)度模型如公式（1）所示

式中s為目標(biāo)信號源的強(qiáng)度;α為信號強(qiáng)度的衰減指數(shù)（α約等于2）;di（t）為t時刻節(jié)點(diǎn)i與跟蹤目標(biāo)之間的距離;ni～N（0，σ2）為測量噪聲，可近似為高斯白噪聲，具體方法如式（2）、式（3）和式（4）所示

式中temp為節(jié)點(diǎn)i在t+1時刻與t時刻感知信號強(qiáng)度之間的差值，limT為設(shè)定的固定門限值，當(dāng)節(jié)點(diǎn)i在t時刻滿足式（3）和式（4）時，就可以轉(zhuǎn)入睡眠狀態(tài)。

2.3 目標(biāo)丟失時的節(jié)點(diǎn)調(diào)度策略

由于移動目標(biāo)的運(yùn)動速度、方向存在一定程度的誤差，在預(yù)測時間內(nèi)，目標(biāo)的一些運(yùn)動特性可能會突然發(fā)生較大的改變，致使目標(biāo)離開當(dāng)前的監(jiān)控區(qū)域，這種現(xiàn)象稱為目標(biāo)丟失，為了能夠快速地重新跟蹤到目標(biāo)，提出了一種有效的目標(biāo)恢復(fù)機(jī)制。

目標(biāo)丟失檢測:被喚醒的節(jié)點(diǎn)檢測到目標(biāo)時會向前一監(jiān)控節(jié)點(diǎn)發(fā)送確認(rèn)消息，否則，在一周期內(nèi)沒有發(fā)現(xiàn)目標(biāo)則自動進(jìn)入睡眠狀態(tài)，如果前一監(jiān)控節(jié)點(diǎn)在規(guī)定時間內(nèi)沒有收到喚醒節(jié)點(diǎn)發(fā)送的確認(rèn)消息，則表明目標(biāo)丟失，啟動目標(biāo)恢復(fù)機(jī)制。

目標(biāo)恢復(fù):目標(biāo)恢復(fù)分為2個過程，首先當(dāng)前跟蹤簇泛洪命令喚醒簇內(nèi)所有節(jié)點(diǎn)搜索其監(jiān)測范圍內(nèi)的所有目標(biāo)信息，所有當(dāng)前簇內(nèi)節(jié)點(diǎn)在一個周期內(nèi)上傳其檢測信息，若當(dāng)前簇頭節(jié)點(diǎn)監(jiān)測到移動目標(biāo)，則休眠不相關(guān)節(jié)點(diǎn)繼續(xù)進(jìn)行跟蹤;若沒有發(fā)現(xiàn)目標(biāo)說明移動目標(biāo)已經(jīng)離開當(dāng)前簇，當(dāng)前簇頭節(jié)點(diǎn)休眠其簇內(nèi)節(jié)點(diǎn)，并且泛洪消息到一跳范圍的相鄰的簇頭節(jié)點(diǎn)，相鄰簇頭節(jié)點(diǎn)再啟動搜索任務(wù)。

2.4 TTSSP 整體流程

1）網(wǎng)絡(luò)初始化，只有邊界簇頭節(jié)點(diǎn)處于感知狀態(tài)，其他節(jié)點(diǎn)睡眠;

2）當(dāng)目標(biāo)進(jìn)入網(wǎng)絡(luò)，開始目標(biāo)跟蹤;

If{成功跟蹤目標(biāo)}

{目標(biāo)所在邊界簇頭節(jié)點(diǎn)稱為跟簇頭，對目標(biāo)進(jìn)行定位，預(yù)測其軌跡;發(fā)送預(yù)測結(jié)果至鄰居簇，喚醒鄰居簇內(nèi)節(jié)點(diǎn)繼續(xù)跟蹤;前一簇內(nèi)節(jié)點(diǎn)根據(jù)感知信號強(qiáng)度決定是否睡眠;}

else{目標(biāo)丟失，啟動目標(biāo)恢復(fù)機(jī)制}

3 仿真實(shí)驗(yàn)

本節(jié)對TTSSP協(xié)議進(jìn)行仿真實(shí)驗(yàn)。仿真場景的基本設(shè)置為400個節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的二維監(jiān)控平臺，節(jié)點(diǎn)的傳輸半徑R=30m，目標(biāo)信號源強(qiáng)度s=100，信號強(qiáng)度隨距離衰減指數(shù)α=2，噪聲分布ni～N（0，σ2），目標(biāo)做直線運(yùn)動，其中，v=10 m/s，a= ±costm/s2。仿真分別對TTSSP、基于預(yù)測的目標(biāo)跟蹤算法（PT）［10］和基于兩階段睡眠調(diào)度的目標(biāo)跟蹤協(xié)議（TSSTP）［11］進(jìn)行了10次仿真，跟蹤性能對比圖如圖3～圖5所示，圖中的數(shù)據(jù)為對應(yīng)參數(shù)10次仿真所得結(jié)果的平均值。

圖3顯示了感知信號強(qiáng)度檢測閾值和目標(biāo)運(yùn)動速度對目標(biāo)發(fā)現(xiàn)概率的影響。監(jiān)測閾值的大小和平均發(fā)現(xiàn)概率呈反比，即檢測閾值小，就會有更多的感知信號強(qiáng)度節(jié)點(diǎn)被喚醒，然而閾值過小會導(dǎo)致過多的節(jié)點(diǎn)參與跟蹤任務(wù)，網(wǎng)絡(luò)中的冗余信息增加，不利于網(wǎng)絡(luò)的均衡性。發(fā)現(xiàn)概率是和移動目標(biāo)的速度呈反比，從圖3中可以看出:在一定的速率內(nèi)，本文提出的睡眠調(diào)度機(jī)制未對系統(tǒng)性能帶來過多的影響。

圖3 檢測閾值、速度對發(fā)現(xiàn)概率的影響Fig 3 Influence of detection threshold and speed on discovery probability

圖4比較了TTSSP與另外一個比較好的睡眠調(diào)度協(xié)議TSSTP以及一般的基于預(yù)測的跟蹤算法PT的能量消耗情況。圖中可以明顯看到TTSSP算法的優(yōu)越性。TSSTP將節(jié)點(diǎn)的跟蹤調(diào)度分為2個階段，PF算法沒有引入睡眠調(diào)度機(jī)制。實(shí)驗(yàn)結(jié)果表明:本文算法和TSSTP算法相對于PT算法能量消耗大大降低，因?yàn)槎叨家肓溯^好的節(jié)點(diǎn)調(diào)度機(jī)制。但是，TSSTP算法由于在目標(biāo)經(jīng)過后沒有及時地休眠感知信號強(qiáng)度小的節(jié)點(diǎn)，所以，能量消耗稍高于TTSSP算法。

圖4 三種算法能耗比較Fig 4 Energy consumption comparison of three algorithms

圖5比較了PT，TTSSP和TSSTP三種算法的跟蹤成功率。從圖中可以明顯看出:隨著時間的增長，三種算法的跟蹤成功率相差不多，但是，TTSSP和TSSTP在剛開始的時候，由于采用了睡眠調(diào)度機(jī)制，只有少部分或者沒有節(jié)點(diǎn)處于偵測狀態(tài)，跟蹤成功率相對于PT算法來講都比較低，但是由于TSSTP在剛開始的時候所有的節(jié)點(diǎn)都是處于睡眠狀態(tài)，所以，不能成功地檢測到目標(biāo)的出現(xiàn)。本文算法在跟蹤網(wǎng)絡(luò)開始時，邊界簇頭節(jié)點(diǎn)是處于偵測狀態(tài)的，所有的邊界簇頭節(jié)點(diǎn)能夠覆蓋到整個區(qū)域，所以，跟蹤成功率提高了40%，并且TTSSP更加節(jié)省能量。

圖5 三種算法跟蹤成功率比較Fig 5 Successful tracking rate of three algorithms

4 結(jié)論

為了在保證跟蹤質(zhì)量的同時減少系統(tǒng)能耗，本文分別對目標(biāo)跟蹤前和目標(biāo)跟蹤過程中進(jìn)行了節(jié)點(diǎn)睡眠調(diào)度，另外，當(dāng)跟蹤目標(biāo)丟失時能夠動態(tài)地調(diào)度節(jié)點(diǎn)。為了提高協(xié)議的性能，提高能量利用率，進(jìn)一步從休眠特定節(jié)點(diǎn)和節(jié)點(diǎn)預(yù)測角度進(jìn)行了優(yōu)化。

最后在Matlab 7.0實(shí)驗(yàn)仿真平臺上對所提出的協(xié)議進(jìn)行仿真。實(shí)驗(yàn)結(jié)果表明:本文所提出的睡眠調(diào)度機(jī)制能夠在保證跟蹤質(zhì)量的同時大幅度降低能耗，與沒有引入睡眠調(diào)度的跟蹤算法相比，本文算法能降低1倍的能耗。

［1］胡湘華，楊學(xué)軍.傳感網(wǎng)節(jié)點(diǎn)調(diào)度方法綜述［J］.計算機(jī)工程與科學(xué)，2008，30（3）:93 －96.

［2］任倩倩，李建中，李金寶，等.無線傳感器網(wǎng)絡(luò)中一種能源有效的移動對象跟蹤方法［J］.通信學(xué)報，2009，30（4）:50－59.

［3］Huang C F，Lee H W，Kuo S P，et al.Location tracking in a wireless sensor networks by mobile agents and its data fusion strategies［J］.The Computer Journal，2004，47（4）:448 － 460.

［4］Lee W C，Xu Y.On localized prediction for power efficient object tracking in sensor networks［C］//Proceedings of the 23rd International Conference on Distributed Computers Systems Workshops，2003:434－439.

［5］Jiang Bo，Han Kai，Ravindran B.Energy efficient sleep scheduling based on moving directions in target tracking sensor network［J］.IEEE Journal on Selected Areas in Communications，2008，17（8）:1426－1438.

［6］Wang Guojun，Wang Huan，Cao Jiangnong.Energy-efficient dual prediction based data gathering for environmental monitoring applications［C］// IEEE Communication Society Subject Matter Experts for Publication in the WCNC 2007 Proceedings，2007:3516－3521.

［7］孫煥平，周宗錫，何建華，等.一種面向目標(biāo)跟蹤的無線傳感器網(wǎng)絡(luò)分簇算法［J］.傳感器與微系統(tǒng)，2010，29（5）:125－127.

［8］申興發(fā)，李鴻斌，趙 軍，等.面向目標(biāo)跟蹤的傳感網(wǎng)絡(luò)分布式組管理機(jī)制［J］.儀器儀表學(xué)報，2007，28（6）:966 －972.

［9］Lin K W，Hsieh Ming Hua，Tseng V S.A novel prediction-based strategy for object tracking in sensor networks by mining seamless temporal movement patterns［J］.Expert Systems with Applications，2010，37:2799 －2807.

［10］鄧克波，劉 中.基于無線傳感器網(wǎng)絡(luò)動態(tài)簇的目標(biāo)跟蹤［J］.兵工學(xué)報，2008，29（10）:1197－1202.

［11］任倩倩，李建中，高 宏，等.傳感器網(wǎng)絡(luò)中一種基于二級睡眠調(diào)度的目標(biāo)跟蹤協(xié)議［J］.計算機(jī)學(xué)報，2009，32（10）:1971－1979.