一種高跟蹤質(zhì)量保證的預(yù)先節(jié)點選擇策略

李慶華 ，桂衛(wèi)華

LI Qinghua1，2,GUI Weihua2

1.麗水學(xué)院 工學(xué)院，浙江 麗水 323000

2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

1.Institute of Technology,Lishui University,Lishui,Zhejiang 323000,China

2.School of Information Science and Engineering,Central South University,Changsha 410083,China

1 相關(guān)工作

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）的發(fā)展改變了人與自然的交流方式，移動目標(biāo)跟蹤是無線傳感器網(wǎng)絡(luò)的一個重要的應(yīng)用之一，主要的應(yīng)用場景有：在戰(zhàn)場中對入侵目標(biāo)的跟蹤；在珍稀動物的保護(hù)中，以實現(xiàn)對珍稀動物的無人實時跟蹤與監(jiān)測；其他如災(zāi)難預(yù)報和智能交通等領(lǐng)域具有廣泛的應(yīng)用[1-2]。在這些應(yīng)用中，傳感器節(jié)點協(xié)作監(jiān)測一個或多個特定的目標(biāo)，并將感知數(shù)據(jù)發(fā)送到Sink節(jié)點以作決策或進(jìn)一步處理，從而使用戶能夠?qū)崟r、連續(xù)跟蹤目標(biāo)，感知目標(biāo)的移動與狀態(tài)，以實現(xiàn)感知世界的目標(biāo)[3-4]。

無線傳感器網(wǎng)絡(luò)的節(jié)點是由電池供電，能量非常有限[3-4]，而且不能被替換與更新，因而傳感器節(jié)點的能量一旦消耗盡，則完全失去功能而死亡[5-6]。為了節(jié)省節(jié)點的能量消耗，傳感器節(jié)點一般采用周期性的睡眠與活躍（sleep and active）的工作方式[5]。如果多個節(jié)點監(jiān)測到目標(biāo)后都向Sink報告目標(biāo)的話，那么，網(wǎng)絡(luò)將會承擔(dān)很多報告數(shù)據(jù)。而實際上，同一監(jiān)測目標(biāo)的這些報告數(shù)據(jù)存在冗余[7-8]，如果將同一目標(biāo)監(jiān)測到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再發(fā)向Sink，則會大大減少網(wǎng)絡(luò)的能量消耗。因而，有研究提出將依據(jù)目標(biāo)所在的區(qū)域劃分為簇[9]。當(dāng)關(guān)注的目標(biāo)出現(xiàn)發(fā)生后，位于目標(biāo)周圍的處于active狀態(tài)的傳感器節(jié)點產(chǎn)生感知數(shù)據(jù)并向簇頭節(jié)點報告感知的數(shù)據(jù)。簇頭節(jié)點將選定參考節(jié)點的信息進(jìn)行數(shù)據(jù)融合向Sink節(jié)點匯報，由于同一目標(biāo)只出現(xiàn)在網(wǎng)絡(luò)的某一個局部區(qū)域內(nèi)，同一時刻參與目標(biāo)監(jiān)測的節(jié)點數(shù)目有限，而同一目標(biāo)在進(jìn)行數(shù)據(jù)融合后再發(fā)往Sink，因此能夠大大減少數(shù)據(jù)的傳送量，是一種較好的策略，在本文中稱這種策略為基于簇的目標(biāo)監(jiān)測策略。

本文的策略從總體上來說達(dá)到了如下的目標(biāo)：（1）充分利用了非hotspots區(qū)域高達(dá)90%的剩余能量，從而可以依據(jù)目標(biāo)的移動位置預(yù)先選擇一些節(jié)點進(jìn)行目標(biāo)跟蹤，因而大大提高了連續(xù)跟蹤目標(biāo)的能力，并使得目標(biāo)跟蹤的質(zhì)量也得到很大提高。（2）策略采用節(jié)點狀態(tài)監(jiān)測與更新的方法，適時使監(jiān)測較小的節(jié)點轉(zhuǎn)為sleep狀態(tài)以節(jié)省能量。同時，由于本文的預(yù)先選擇策略使得目標(biāo)處于高質(zhì)量監(jiān)測節(jié)點的概率增大，因而及時將低質(zhì)量監(jiān)測節(jié)點轉(zhuǎn)為sleep既不影響監(jiān)測質(zhì)量，也可降低系統(tǒng)的能量消耗。

2 系統(tǒng)模型與問題定義

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

為方便起見，作如下假設(shè)：

（1）同質(zhì)的傳感器網(wǎng)絡(luò)，即所有傳感器節(jié)點是同質(zhì)的，具有相同的通信與處理能力，初始能量相等。

（2）與大多數(shù)研究相同，設(shè)傳感器節(jié)點可以通過某種方法獲得自己的位置坐標(biāo)，節(jié)點vi的坐標(biāo)用(xi，yi)表示。

（3）傳感器節(jié)點采用周期性sleep與active輪換的方式工作以節(jié)省能量。設(shè)節(jié)點的工作周期時間長度為Γ，在時間Γ內(nèi)，節(jié)點處于sleep的時間為τs，處于active的時間長度為τa，根據(jù)文獻(xiàn)[10]的定義：節(jié)點的占空比定義如下：

2.2 能量消耗模型

本文的能量消耗模型與其他文獻(xiàn)采用的模型是一樣的[2-4]，發(fā)送l比特數(shù)據(jù)的能量消耗見公式（2），接收l比特數(shù)據(jù)的能量消耗見公式（3）。

2.3 問題描述

本文的目標(biāo)是：在網(wǎng)絡(luò)監(jiān)測中，需要保證有足夠多的監(jiān)測節(jié)點連續(xù)地監(jiān)測到目標(biāo)，而且目標(biāo)跟蹤質(zhì)量要盡量高。對于目標(biāo)跟蹤質(zhì)量，提出如下的幾個性能指標(biāo)。

（1）連續(xù)跟蹤的質(zhì)量：連續(xù)跟蹤質(zhì)量指：設(shè)目標(biāo)進(jìn)入監(jiān)測區(qū)域的總時間為T，目標(biāo)被監(jiān)測的質(zhì)量超過一定閾值?的時間為t，則定義連續(xù)跟蹤質(zhì)量。

（2）跟蹤質(zhì)量：為簡單起見，定義跟蹤質(zhì)量為一段時間內(nèi)跟蹤到目標(biāo)的節(jié)點個數(shù)，監(jiān)測到目標(biāo)的節(jié)點個數(shù)越多，則監(jiān)測的質(zhì)量越高。

3 高跟蹤質(zhì)量的預(yù)先節(jié)點選擇策略

3.1 策略描述

本節(jié)詳細(xì)給出本文策略的詳細(xì)實現(xiàn)方法。如前面所述，本文策略的前面階段與已有的研究是相同的，不相同的是提前對目標(biāo)可能移動的區(qū)域進(jìn)行預(yù)測，提前選擇一些節(jié)點進(jìn)行監(jiān)測。因此，策略的形成分為如下幾個階段：

（1）工作簇的形成階段：當(dāng)目標(biāo)進(jìn)入監(jiān)測區(qū)域后，由于節(jié)點周期性的sleep與active輪換，一旦目標(biāo)被處于active的節(jié)點感知到，則所有感知到目標(biāo)的節(jié)點將自己感知目標(biāo)信號的強度信息，以及自己的剩余能量情況進(jìn)行廣播，類似于簇的形成過程，以下面的公式競爭簇頭。

（2）預(yù)測區(qū)域節(jié)點加入簇的過程

簇頭節(jié)點通過目標(biāo)周圍節(jié)點感知的信息，通過常用的三點定位法[7]確定目標(biāo)的位置，然后將目標(biāo)的位置，預(yù)測的目標(biāo)移動方向，β與rx的值廣播。所有收到廣播值的節(jié)點計算自己是否落在節(jié)點的預(yù)測區(qū)域內(nèi)，如果節(jié)點落到預(yù)測區(qū)域內(nèi)，則向簇頭節(jié)點發(fā)送請求加入簇的信息而加入簇。

（3）簇的穩(wěn)定運行階段

簇的穩(wěn)定運行階段比較簡單，感知目標(biāo)的節(jié)點將自己感知的信息發(fā)往簇頭，簇頭進(jìn)行信息融合采用比如最短路由（shortest routing）策略發(fā)往Sink。

（4）簇頭的輪換

簇頭節(jié)點不斷計算目標(biāo)的位置，如果計算出的目標(biāo)位置距離簇頭的距離大于一定的閾值σ后，則簇頭節(jié)點重新指定新的簇頭，新的簇頭節(jié)點重新廣播簇半徑rb，然后，舊的簇頭廣播自己不當(dāng)簇頭的信息，那些收到新簇頭節(jié)點消息并且在簇半徑rb的節(jié)點成新簇的簇內(nèi)節(jié)點，那些只收到舊簇頭撤銷簇頭消息的節(jié)點恢復(fù)正常的sleep與active輪換的工作方式。

（5）新的簇頭重復(fù)第（2）到第（4）個階段。

下面給出本文策略的算法描述。

3.2 策略的參數(shù)優(yōu)化

設(shè)節(jié)點距離sink的距離為l，l=hr+x，則此節(jié)點承擔(dān)的數(shù)據(jù)包個數(shù)為：

其中z為使l+zr剛好小于R的整數(shù)。

依據(jù)能量消耗公式（2）和公式（3），設(shè)節(jié)點承擔(dān)一個數(shù)據(jù)包的能量消耗為ep，則可以得到距離Sink為l處遠(yuǎn)的節(jié)點，其轉(zhuǎn)發(fā)數(shù)據(jù)的能量消耗為：

設(shè)距離Sink最近節(jié)點的距離為 y，其能量消耗最大，其他節(jié)點相對于能量消耗最大節(jié)點剩余的能量為：

那么現(xiàn)在要確定的是在剩余能量為E0時，能夠支撐多大的預(yù)測區(qū)域。當(dāng)β和rx確定時，其所圈定的圓弧面積為：

而預(yù)測區(qū)域僅是S1區(qū)域的一部分。設(shè)目標(biāo)距離簇的邊界距離為w，則預(yù)測區(qū)域的面積：

設(shè)w在(0,rb)間的圓上取值，因此，其平均取值可以計算得到為，因此：

設(shè)數(shù)據(jù)收集周期為Γ，因而在單位時間內(nèi)，節(jié)點被選擇后其能量消耗比未選擇前增加的能量消耗速率為Δ，因而在時間周期Γ內(nèi)，增加的能量消耗為：ΔΓ。整個預(yù)選擇區(qū)域的增加的能量消耗為：npΔΓ。距離Sink為l處遠(yuǎn)的節(jié)點剩余的能量為，因而，將所有剩余的能量用于預(yù)測節(jié)點的選擇，建立等式：

在上式中，只有β和rx是未知數(shù)，因而可以選擇合適的β和rx，在不影響網(wǎng)絡(luò)壽命的情況下，提高目標(biāo)監(jiān)測的質(zhì)量。

4 實驗結(jié)果

4.1 仿真參數(shù)設(shè)置

采用OMNET++4.0作為仿真工具，仿真的WSN覆蓋區(qū)域為圓形，其半徑R=500 m。用來監(jiān)測的傳感器節(jié)點數(shù)為500，節(jié)點的發(fā)送半徑可以隨時間變化，采用r=50，r=70，rb=0.6r。節(jié)點隨機分布且所有節(jié)點初始能量都相同。能量仿真參數(shù)如表1所示。

如無特別說明，實驗結(jié)果是20次實驗結(jié)果的平均。

圖1給出了當(dāng)固定β=100°的情況下，距離Sink不同距離處rx的平均長度情況，可見在離Sink預(yù)測區(qū)域越來越大，意味著連續(xù)目標(biāo)跟蹤的能力增強，消耗了更多能量，但這些能量都是網(wǎng)絡(luò)本身剩余的能量，因而不影響網(wǎng)絡(luò)壽命。圖2給出的是在rx固定的情況下，β的變化情況，從圖2也可得到同樣的規(guī)律，即隨著遠(yuǎn)離Sink，由于剩余能量的增多，因而β越大，也就是目標(biāo)跟蹤能力增強。

表1 仿真參數(shù)

圖1 網(wǎng)絡(luò)不同區(qū)域rx的變化情況

圖2 β的變化情況

4.2 仿真結(jié)果與分析

在本文的實驗中，性能對比的參照實驗是類似于文獻(xiàn)[11]動態(tài)簇的目標(biāo)跟蹤策略。在這樣的策略中，如果目標(biāo)出現(xiàn)后，在目標(biāo)附近動態(tài)形成簇，在本文中這種策略稱為基本版（baseline version）的策略，其存在的不足是當(dāng)目標(biāo)移動到新的地方時，簇的形成與建立跟不上目標(biāo)的移動，因而影響監(jiān)測的質(zhì)量。而本文的策略是在其基礎(chǔ)上提前在目標(biāo)可能移去的區(qū)域選擇一些節(jié)點進(jìn)行監(jiān)測，以提高目標(biāo)監(jiān)測質(zhì)量。下面給出這兩種策略的性能實驗結(jié)果。

圖3的實驗結(jié)果是目標(biāo)在網(wǎng)絡(luò)任意位置出現(xiàn)后，以不同速度移動時，不同策略選擇監(jiān)測節(jié)點個數(shù)的情況。在實驗中，設(shè)置簇頭節(jié)點在當(dāng)目標(biāo)距離簇頭節(jié)點30 m時就輪換一次。從圖3的實驗可以看出，當(dāng)目標(biāo)的移動速度較慢時，不同的策略選擇的節(jié)點個數(shù)差不多，但是，隨著目標(biāo)移動速度加快，本文策略選擇的節(jié)點個數(shù)增大。

圖3 不同策略下選擇的節(jié)點個數(shù)

圖4給出的是同時監(jiān)測到目標(biāo)的節(jié)點個數(shù)的對比情況（同時，是單位時間內(nèi)監(jiān)測到目標(biāo)的節(jié)點個數(shù)）。在目標(biāo)移動速度較小時，目標(biāo)完全被節(jié)點覆蓋，因而不同策略同時監(jiān)測到節(jié)點的個數(shù)相差不大。而目標(biāo)移動速度較大時，目標(biāo)往往移出簇，因而以往研究下會存在監(jiān)測的盲區(qū)，導(dǎo)致同時監(jiān)測到目標(biāo)的節(jié)點個數(shù)降低。而本文的策略還是維持在一個較高的水平，因而跟蹤質(zhì)量得到提高。

圖4 監(jiān)測目標(biāo)的節(jié)點個數(shù)

圖5給出的是不同策略下監(jiān)測目標(biāo)錯失率的對比情況（是指目標(biāo)沒有被監(jiān)測到的時間與總時間的比值）。很顯然，如果目標(biāo)移動速度越快，選擇節(jié)點的速度遠(yuǎn)跟不上目標(biāo)移動速度的話，那么目標(biāo)錯失率就高。反之，目標(biāo)移動速度低，則目標(biāo)錯失率低。圖5給出了不同策略的錯失率的對比，從實驗結(jié)果可以看出，本文的策略雖然在目標(biāo)移動速度增大時，錯失率也上升，但是還是遠(yuǎn)遠(yuǎn)小于以往策略，說明本文的策略具有較好的性能。

圖5 錯失監(jiān)測目標(biāo)的概率

圖6給出的是不同策略下的網(wǎng)絡(luò)壽命情況。從總體上來說不同策略的網(wǎng)絡(luò)壽命相近。但是，還是有此細(xì)小的差別：當(dāng)目標(biāo)移動速度增大時，以往的策略由于有目標(biāo)錯失，因而有部分時間與節(jié)點沒有感知到目標(biāo)。因而目標(biāo)移動速度增大時，其數(shù)據(jù)量反而減少，因而其網(wǎng)絡(luò)壽命向上增長。而本文策略不同，目標(biāo)錯失率較小，同時由于目標(biāo)移動快時，預(yù)測區(qū)域變化較快，節(jié)點的選擇動態(tài)變化大，能量消耗反而多，因而網(wǎng)絡(luò)壽命反而有所下降。

圖6 網(wǎng)絡(luò)壽命的對比

5 結(jié)論

目標(biāo)跟蹤中的節(jié)點選擇仍然是一個值得研究的重要課題[12]。很少有研究考慮到節(jié)點這種sleep與active狀態(tài)輪換工作而對目標(biāo)跟蹤造成錯失的影響。本文研究了這一問題。提出了預(yù)先在目標(biāo)移動的區(qū)域選擇一部分節(jié)點，從而能夠較好地提高網(wǎng)絡(luò)監(jiān)測的質(zhì)量，同時，在網(wǎng)絡(luò)壽命方面與以往的研究性能基本相同。達(dá)到這樣效果的重要原因是：本文創(chuàng)新性地依據(jù)網(wǎng)絡(luò)節(jié)點的能量消耗情況，對節(jié)點能量有剩余的區(qū)域預(yù)測區(qū)域較大，而在能量消耗緊張的區(qū)域預(yù)測區(qū)域較小，或者甚至沒有。從而既有效利用了網(wǎng)絡(luò)能量，又提高了網(wǎng)絡(luò)的監(jiān)測質(zhì)量。對于設(shè)計高跟蹤質(zhì)量的網(wǎng)絡(luò)具有較好的指導(dǎo)作用。

[1]Wei W，Ting H，Bisdikian C，et al.Impact of in-network aggregation on target tracking quality under network delays[J].IEEE Journal on Selected Areas in Communications，2013，31（4）：808-818.

[2]Youngwon Kim A，Seong-Moo Y，Changhyuk A，et al.Doppler effect on target tracking in wireless sensor networks[J].Computer Communications，2013，36（7）：834-848.

[3]Anfeng L，Xin J，Guohua C，et al.Deployment guidelines for achieving maximal lifetime and avoiding energy holes in sensor network[J].Information Sciences，2013，230（5）：197-226.

[4]Anfeng L，Zhongming Z，Chao Z，et al.Secure and energy efficient disjoint multi-path routing for WSNs[J].IEEE Transactions on Vehicular Technology，2012，61（7）：3255-3265.

[5]Zhou F，Trajcevski G，Ghica O，et al.Deflection aware tracking principals selection in active wireless sensor networks[J].IEEE Transactions on Vehicular Technology，2012，61（7）：3240-3254.

[6]林曉輝，于潔瓊，陳彬.基于博弈論的無線傳感器網(wǎng)絡(luò)能耗均衡[J].廣西大學(xué)學(xué)報：自然科學(xué)版，2012，37（6）：1150-1157.

[7]Benazir F，Govindarasu M.Energy minimization by exploiting data redundancy in real-time wireless sensor networks[J].Ad Hoc Networks，2013，11（6）：1715-1731.

[8]趙明，陳志剛，葛志輝，等.QS-Sift：一種基于服務(wù)質(zhì)量和空間相關(guān)性的無線傳感器網(wǎng)絡(luò)MAC協(xié)議[J].小型微型計算機系統(tǒng)，2006，27（11）：2007-2011.

[9]周賢偉，林亮，覃伯平.一種無線傳感器網(wǎng)絡(luò)分簇規(guī)模約束算法[J].傳感技術(shù)學(xué)報，2007，20（4）：908-911.

[10]胡倩，陳新.分簇?zé)o線傳感器網(wǎng)絡(luò)中密度感知的自適應(yīng)占空比機制的研究[J].傳感技術(shù)學(xué)報，2013，26（1）：105-109.

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

[12]任倩倩，李建中，王宇.無線傳感器網(wǎng)絡(luò)具有跟蹤質(zhì)量保證的節(jié)點選擇算法[J].計算機學(xué)報，2012，35（10）：2007-2015.