視頻傳感器網絡中基于移動目標軌跡預測的K級覆蓋增強算法*

蔣一波,陳 瓊,王萬良,樓 弘

(浙江工業大學計算機科學與技術學院,杭州 310023)

?

視頻傳感器網絡中基于移動目標軌跡預測的K級覆蓋增強算法*

蔣一波*,陳 瓊,王萬良,樓 弘

(浙江工業大學計算機科學與技術學院,杭州 310023)

從視頻傳感器節點的有向感知模型出發,深入研究了移動目標K級覆蓋問題。首先擴展了可旋轉的視頻傳感器節點有向感知模型,分析了監控區域內移動目標可能的行為,定義了最小旋轉角度的移動目標K級覆蓋問題并給出了對應的數學描述。然后設計了一種目標軌跡點預測方法,提出了基于預測的分布式貪心K級覆蓋算法。最后引入了優化的覆蓋質量評價指標,通過一系列仿真實驗驗證了算法的有效性。

視頻傳感器網絡;移動目標覆蓋;K級覆蓋;分布式算法

視頻傳感器網絡具備數據、圖像和視頻等多媒體信息感知、采集、處理和傳輸能力,是一種有效的狀態感知、信息采集和目標跟蹤手段,在工農業、軍事、環境監測等領域展現出廣泛的應用前景[1]。其中目標覆蓋控制是視頻傳感器網絡中的一個基本研究問題,有些監測應用對熱點區域及目標的覆蓋服務質量具有較高的要求,此時需要區域中每個目標點至少被K個不同傳感節點同時覆蓋,此類問題也稱為K覆蓋問題[2]。盡管無線視頻傳感器網絡日趨成熟,但從現有研究成果來看,絕大多數目標覆蓋問題是針對靜態目標展開的,對于具備隨機性特征的移動目標持續性覆蓋問題以及移動目標K級覆蓋問題的研究還非常少,這直接影響到了監控系統的實時監測質量。

視頻傳感器與傳統傳感器不同,對環境數據的感知受“視域FoV(Field of View)”的限制,具有方向性,其感知范圍是一個以節點為圓心,半徑為感知距離的扇形區域,是有向感知模型。由于監測區域普遍地勢復雜,因此視頻傳感器初始部署大都采用隨機部署策略。視頻傳感器的感知有向性和部署隨機性給研究移動目標K級覆蓋問題帶來了難度和挑戰,需要旋轉視頻傳感器的感知方向角來實時覆蓋隨機性移動的監測目標,因此,迫切需要設計出針對該問題的新方法來滿足其覆蓋要求。

目前,有向傳感器網絡覆蓋理論從覆蓋對象的角度可分為區域覆蓋[3-4]和目標覆蓋;從目標出現形式看,目標覆蓋問題分為靜態目標覆蓋與移動目標覆蓋兩類;從覆蓋質量看,有向K覆蓋是目前的研究熱點。

移動目標覆蓋是保證任意移動的目標在穿越監控區域過程中能夠被持續跟蹤的問題。Boulanouar等人[5]將移動目標跟蹤劃分為兩個階段:檢測目標出現和持續定位目標,并提出了協同跟蹤算法CTA,利用異構的移動傳感器和視頻傳感器降低了跟蹤能量消耗并提高了跟蹤覆蓋率。Wang等人[6]針對有向傳感器網絡提出了一個新的、實時的分布式目標跟蹤算法。在國內,李石堅等人[7]以目標跟蹤為背景,將移動目標、熱點區域與障礙物引入虛擬力方法,提出一種涉及目標的虛擬力算法TIVFA。陶丹[8]和肖甫[9]等在目標運動軌跡點提前獲知的情況下研究了基于虛擬勢場的路徑覆蓋增強算法PFPCE,并針對可能出現的局部極小問題設計了改進的算法IPFPCA,實現網絡路徑的高效覆蓋。任靜等人[10]針對現有無線傳感器網絡目標跟蹤算法不能兼顧精度和能耗的問題,提出了一種基于預測策略的目標跟蹤算法。

在有向傳感器網絡中,K覆蓋問題亦引起了研究學者們的關注。Liu等人[11]率先提出有向K覆蓋DKC(Directional K-Coverage)的概念,基于概率論方法設計數學模型,預測網絡DKC性能與隨機部署的有向節點數目(或密度)之間的函數關系。Wu等人[12]則基于概率模型研究最小K覆蓋集MKS(Minimal K-Coverage Set)問題。Fusco等人[13]設計了一種簡單的貪心算法,通過選取最少數目的有向節點并調節其初始感知方向,達到給定區域及目標點的K覆蓋。在國內,張美燕等人[14]設計了一種簡單的分布式啟發算法,在一跳鄰居范圍內對傳感器節點的感知方向進行協同調度,使得目標集被有向K覆蓋的時間最長。蔣麗萍等人[15]考慮了實際應用中環境因素對節點感知能力的影響,提出了一種分布式K重覆蓋算法KCAPSM,采用了感知概率模型保證監測區域中每一點被K重覆蓋。李明[16]提出了一種基于多重覆蓋算法的異構節點調度機制,滿足區域覆蓋要求和重點區域中監測目標多重覆蓋的要求。

以上文獻均是單方面地考慮移動目標覆蓋問題和靜態目標多重覆蓋問題,本文同時考慮了這兩方面的情況,并針對目標移動隨機性的特點,設計了一種目標軌跡點預測方法,達到移動目標實時K級覆蓋的要求。

本文將基本的有向感知模型擴展為方向可旋轉的有向感知模型,提出了最小旋轉角度的移動目標K級覆蓋問題MAKLC(Minimum Rotation Angle of Moving Target withKLevel Coverage),并且研究了MAKLC問題的分布式解決方案,然后設計了一種目標軌跡點預測方法,提出了基于預測的分布式貪心K級覆蓋算法DPGKCA(Distributed Prediction-Based GreedyKLevel Coverage Algorithm)提高網絡的實時監測性能。最后,通過一系列仿真實驗中各項統計指標的比較,驗證了DPGKCA算法的有效性。

1 最小旋轉角度的移動目標K級覆蓋問題MAKLC

本節主要分析和定義最小旋轉角度的移動目標K級覆蓋問題MAKLC。首先描述了方向可旋轉的視頻傳感器節點有向感知模型,然后分析了監控區域內移動目標可能的行為,最后形式化定義了MAKLC問題并給出了準確的數學描述。

1.1 視頻傳感器節點有向感知模型

視頻傳感器節點不同于全向感知模型,有感知視角的限制,但其可以通過旋轉感知方向角來改變監測區域。但是,節點旋轉具有角速度ω,在Δt時間范圍內節點最大可以旋轉Δt*ω角度,假設節點旋轉順時針方向為正方向,節點感知方向角是以x軸正方向為起點順時針轉到扇形區域中心線的角度。因此,節點可以在[-Δt*ω,Δt*ω]范圍內旋轉其感知方向來覆蓋監測目標。我們得到視頻傳感器節點方向可旋轉感知模型,如圖1所示。

圖1 方向可旋轉感知模型

定義1在任一離散時刻t,視頻傳感器節點的感知范圍是一個以節點P為圓心、半徑R為其感知距離、夾角為α的扇形區域,扇形區域的中心線Vp角度為θ,節點旋轉角速度為ω。因此,方向可旋轉的視頻傳感器節點有向感知模型可以用一個五元組來表示,分別表示每個視頻傳感器節點的中心位置坐標,感知半徑,感知視角FoV(Field of View),感知方向角及旋轉角速度。

特別地,當α=2π時,即FoV=2π時,全向感知模型是有向感知模型的一個特例。

1.2 移動目標K級覆蓋

移動目標覆蓋是網絡檢測入侵目標和跟蹤目標軌跡的一類問題。當目標沒有進入監測區域時,網絡節點工作在監視模式,可以監測到目標的進入;當目標出現時,節點被喚醒,為目標提供高質量的感知覆蓋;當目標離開網絡時,節點又進入低能耗的監視模式。移動目標K級覆蓋的工作過程可以劃分為目標監測、目標覆蓋和目標離開3個工作階段。

目標M監測:假設目標從監測區域的邊界進入。當沒有目標出現時,所有邊界附近的節點工作在監視模式,其余節點休眠以節省能耗。有節點發現目標后需要周圍節點協助感知目標以獲得目標的狀態信息。發現目標的節點向鄰居節點廣播喚醒消息,被喚醒的鄰居節點協作獲得目標的當前的坐標位置、移動方向及移動速度,把它們分別作為該目標的初始位置、初始移動方向及移動速度,移動速度保持不變。

目標M覆蓋:在監測到目標M后,傳感器網絡需要通知該目標附近的傳感器節點加入到目標監測過程中來。根據目標移動的軌跡點及時調整節點的感知方向角,按旋轉角速度ω旋轉節點,滿足該軌跡點被K覆蓋。當目標移動到傳感器節點無法覆蓋到的位置后,該傳感器節點恢復到休眠狀態。

目標M離開:當移動目標從監測區域的邊界離開的時候,認為該目標消失,邊界附近的節點再次進入監視模式,其余節點休眠。

1.3MAKLC問題的分析與定義

在研究本文內容之前,我們需要作以下假設:①視頻傳感器網絡中所有節點同構,即所有節點的感知半徑(R)、感知視角(α)、旋轉角速度(ω)的參數規格分別相同。②視頻傳感器網絡所有節點一經部署,位置固定不變,但其感知方向可旋轉。③視頻傳感器網絡中各個節點都了解自身位置及感知方向角信息,且各節點對自身感知方向可控。④采用雷達波/聲波傳感器可獲得移動目標的實時位置信息。⑤目標從出現到消失,在移動過程中保持速度V不變,方向會發生變化,但目標在較小的時間間隔Δt內做勻速直線運動。

設給定監測區域中視頻傳感器節點集合N={Ni|i=1,2,…,n},T={Tw|w=0,1,2,…}表示監測的各個時刻。Trw表示Tw時刻目標M的當前位置信息。根據當前位置Trw,附近的視頻傳感器節點調整感知方向以達到目標的K覆蓋,但是并不是Trw附近的所有節點都有資格參與軌跡點覆蓋,有限定條件:所有距離Trw不大于節點感知半徑R的點所構成的圓形區域,稱為可覆蓋區。位于可覆蓋區內的節點稱為跟蹤節點TN,其構成的集合稱為跟蹤節點集合{TN}。因此只要考慮Trw的跟蹤節點集合{TN}中的節點即可。

每個跟蹤節點可以順時針或逆時針旋轉,如果第i個視頻傳感器是跟蹤節點,則設θi,w+1表示第i個視頻傳感器在Tw+1時刻的感知方向角,Di,w表示第i個視頻傳感器在Tw+1時刻的感知方向角θi,w+1與此時Tw時刻的感知方向角θi,w之間的夾角,得到

(1)

但是每個傳感器節點旋轉有一定的角速度ω,因此在Δt內節點的旋轉角度范圍是[0,Δt*ω]。假設xi,w為布爾決策變量,表示第i個視頻傳感器在Tw時刻是否旋轉:

(2)

假設ew,i為布爾決策變量,表示在Tw時刻目標的實際位置Sw是否被第i個視頻傳感器覆蓋:

(3)

定義2最小旋轉角度的移動目標K級覆蓋問題MAKLC:要求在監測區域出現的移動目標每個時刻至少被K個不同傳感器節點同時覆蓋。調節節點感知方向按旋轉角速度ω旋轉節點,滿足移動目標被K覆蓋的前提下使可覆蓋區內的跟蹤節點旋轉角度之和最小。

由此可以得到以下的非線性優化模型:

(4)

其中,目標函數表示在移動目標從監測區域的邊界進入到離開的過程中,各個時刻的實際位置Sw在滿足K覆蓋的前提下使傳感器節點旋轉角度之和最小。約束條件表示在Tw時刻,目標的實際位置Sw至少被K個視頻傳感器所覆蓋。

2 基于預測的分布式貪心K級覆蓋算法DPGKCA

本文研究的MAKLC問題屬于NP完全問題,所以上節的非線性優化問題無法在多項式時間內解決,而且大規模的視頻傳感器網絡全局信息很難采集完全,因此,需要尋求分布式次優算法使視頻傳感器節點能夠獨立決策,減少通信開銷。本節設計了一種目標軌跡點預測方法,提出了基于預測的分布式貪心K級覆蓋算法DPGKCA。傳感器節點根據預測位置進行旋轉決策,避免了決策時延。

2.1 移動目標位置預測方法

假設移動目標M在Tw時刻監測到的實際坐標位置由Sw,w=0,1,2,…,表示,預測下一時刻即Tw+1時刻M的坐標位置是Aw+1,w=0,1,2,…。預測位置Aw+1可能與實際位置Sw+1不一致。

定義3目標M從出現到消失的移動路徑Tr可以用一個四元組序列,w=0,1,2,…,來表示,分別表示目標在Tw時刻的實際位置,Tw時刻的移動方向,移動速度及時間間隔。目標在移動過程中保持速度V不變。當w=0時,為該目標初始時刻的位置坐標;T0為初始時刻;V0為目標初始移動方向。

根據移動路徑Tr,移動目標M在時刻Tw的實際坐標是Sw,速度為V,方向向量為Vw,時間間隔為Δt,在通常情況下取一極小時間間隔。假設在時間區間[Tw,Tw+1]內M從點Sw到Aw+1以速度V做勻速直線運動。已知

Vw=(Xw-Xw-1,Yw-Yw-1)w=1,2,…

(5)

Δt=Tw+1-Tw

(6)

(7)

根據Vw和Sw計算得到SwAw+1所在的直線方程:

(8)

根據式(7)和(8)計算得到

其中

(9)

根據式(6)得到

Tw+1=Tw+Δt

(10)

因此由式(9)和(10)得到了M下一時刻即Tw+1時刻的預測位置Aw+1。

2.2 DPGKCA算法描述

DPGKCA算法的核心思想是:利用目標的前兩個軌跡點來預測目標下一刻可能的位置,按照預測位置進行旋轉決策。根據預測位置確定可覆蓋區和跟蹤節點集合,每個跟蹤節點根據自身的有向感知模型計算出覆蓋到預測位置需要旋轉的角度,并根據可旋轉范圍決策是否旋轉。每個跟蹤節點都能接收到其他跟蹤節點所需旋轉角度和是否旋轉的決策變量信息,每個跟蹤節點對收集到的可以旋轉的節點按旋轉角度從小到大排序,選擇前K個節點進行旋轉。

基于上述分析,本文提出DPGKCA算法,從第2個時刻開始先預測目標下個時刻的位置,按預測位置確定跟蹤節點集合。每個時刻DPGKCA算法在跟蹤節點集合中并發執行。DPGKCA算法描述如下:

輸入:節點i的位置和感知方向角θi,w信息和是否啟動預測功能P。

輸出:節點i的感知方向角θi,w+1信息。

1.w←0;//初始化時間步長計數器

2. 計算節點i一個時間步長內最大可旋轉角度Δt*ω;

3. while(true)

3.1.w←w+1;xi,w←0;

3.2. if(P) then//啟動預測函數

3.2.1. 計算出預測位置Aw+1;

3.2.2. 決策位置L=Aw+1;//賦值

3.3. else//關閉預測函數

3.3.1. 決策位置L=目標位置Trw;//賦值

3.4. ifL在節點i的感知范圍內then

3.4.1.k←k-1;

3.4.2. continue;

3.6. 計算節點的感知方向角θi,w與di的逆時針夾角angle;

3.7. if(angle≤180)then

3.7.1. 計算旋轉后節點i的感知方向角θi,w+1=θi,w-angle+α/2;

3.7.2. 計算為覆蓋L,節點i需要旋轉的角度Di,w=angle-α/2;

3.8. else if(angle>180)then

3.8.1. 計算旋轉后節點i的感知方向角θi,w+1=θi,w-angle-α/2;

3.8.2. 計算為覆蓋L,節點i需要旋轉的角度Di,w=360-angle-α/2;

3.9. if(Di,w≤Δt*ω)then

3.9.1.xi,w←1;

3.9.2. broadcast(Di,w);//廣播包含需要旋轉角度的消息給所有其余跟蹤節點

3.10. 節點i收到其余跟蹤節點的需要旋轉角度的消息;

3.11. sort();//對旋轉角度按照從小到大排序

3.12. if序列前k個節點中包含節點ithen

3.12.1. 旋轉i的感知方向至θi,w+1;

3.13. sleep(Δt);

4. end;

很顯然,只要跟蹤節點間旋轉角度信息能夠可靠傳輸,算法DPGKCA就能在有限時間內終止。該算法加入了是否啟動預測功能P的可選項,啟動預測函數可以避免決策的時延,更好地實現實時覆蓋移動目標的要求;若P為false即關閉預測計算,可以適應某些工況中路徑點測量偏差較大的情況。

3 覆蓋質量評價指標

移動目標的覆蓋質量不僅與被多少個活躍節點感知有關,而且與感知的持續時間有關。覆蓋目標的節點數越多、被持續覆蓋的時間越長,則覆蓋質量越高。目標在各個時刻被節點覆蓋的個數可能不是K,需要根據實際要求來量化未達到K級覆蓋、達到K級覆蓋和超過K級覆蓋的權重值,并且也要考慮目標被K覆蓋的時間長度。例如3個時刻達到1重覆蓋應該比1個時刻達到3重覆蓋性能好。另外,節點旋轉會消耗自身的能量,節能低耗可以延長視頻傳感器網絡的工作時間,最小化節點旋轉角度之和也是我們追求的目標。因此,目標覆蓋質量評價指標關系到比較各個算法性能的優劣,本節根據實際監測需求引入了一個目標覆蓋質量評價指標和優化了一種目標覆蓋質量評價函數。

3.1 節點旋轉角度之和

節點旋轉角度之和Angle可以對同一移動目標從一方面來反映各個算法的能耗。統計方法:每個跟蹤節點對收集到的可以旋轉的節點按旋轉角度從小到大排序,選擇前K個節點統計它們的旋轉角度之和。

3.2 覆蓋質量函數

4 算法仿真與性能分析

4.1 仿真環境與實驗實例

本文基于Microsoft.Net Framework開發了仿真軟件來進行模擬實驗研究,仿真環境是隨機在500×500的監測區域內散布N=150個視頻傳感器節點進行移動目標跟蹤覆蓋,節點感知半徑R為50 m,感知視角α為60°,主感知方向向量θ滿足[0,2π]內服從均勻分布,視頻傳感器節點的最大角速度ω為30°/s,目標覆蓋最大K為4,移動目標以速度V為10 m/s做勻速運動,按時間間隔Δt為1 s進行仿真實驗,比較4種移動目標K級覆蓋算法的覆蓋質量指標,通過改變各個參數值來分析參數對移動目標K級覆蓋策略的影響。

本節我們通過一個具體實例說明DPGKCA算法對視頻傳感器網絡移動目標K級覆蓋的過程。按照上述仿真環境配置參數值,記錄下DPGKCA算法運行不同時間步長時網絡的目標覆蓋情況,如圖2所示。并對此例中移動目標達到K覆蓋的時間進行步長統計,如表1所示。

圖2 DPGKCA算法實現移動目標K級覆蓋

表1 移動目標K級覆蓋的時間步長統計

由表1的統計結果可以直觀地看出,此例中移動目標的整個運動過程中沒有被視頻節點感知到的時間只有兩個時間步長。達到maxK=4要求的時間有47個時間步長,超過整個時間的一半。由此可見DPGKCA算法可以解決移動目標K級覆蓋問題。

4.2 性能比較

本節實驗比較4種分布式算法Random,Continue[17],DPGKCA(P=0)和DPGKCA(P=1)的覆蓋質量f值和比較DPGKCA(P=0)與DPGKCA(P=1)的旋轉角度之和Angle。所有結果都是2 000次模擬實驗的平均值。Random算法是隨機部署視頻傳感器節點,即網絡初始覆蓋情況。Continue算法是基于持續旋轉感知模型,在監測過程中所有節點按照固定的角速度ω持續旋轉。DPGKCA(P=0)是不帶預測功能的分布式貪心K級覆蓋算法,DPGKCA(P=1)是基于預測功能的分布式貪心K級覆蓋算法。

首先設定maxK=4,R=50 m,α=60°,ω=30°/s,V=10 m/s,圖3給出了4種算法在不同節點規模下的性能比較。隨著傳感器數目的增加,覆蓋質量f和旋轉角度之和Angle幾乎呈線性增長,很顯然,對于覆蓋質量f,Random和Continue很接近,DPGKCA(P=0)優于Random和Continue,而DPGKCA(P=1)比其余3種好很多;對于旋轉角度之和Angle,DPGKCA(P=1)略多于DPGKCA(P=0),但非常接近。正如我們所期望的,DPGKCA(P=1)算法性能是最好的,這是因為根據預測位置做出旋轉決策可以減少延遲,隨著節點數目增多,K覆蓋的持續時間增長,性能提高尤其顯著。例如,當傳感器數目是250時,算法DPGKCA(P=1)的覆蓋質量為4 171,而DPGKCA(P=0)、Continue和Random只有2 708、2 341和2 334。這是因為節點冗余的網絡中有更多的區域通過旋轉方向可以達到K覆蓋的要求,隨機部署的傳感器越密集,覆蓋質量越高,所以4種算法都隨網絡規模的增大,覆蓋質量越高。

圖4是設定傳感器數目為150時4種算法在不同節點感知半徑下的性能比較。覆蓋質量f隨節點感知半徑R的增加呈現指數級增長。DPGKCA(P=0)和DPGKCA(P=1)算法的旋轉角度之和Angle隨著感知半徑R的增加先增大后減少,但兩者值仍十分接近。

圖3 傳感器數目對覆蓋質量和旋轉角度之和的影響

圖4 節點感知半徑對覆蓋質量和旋轉角度之和的影響

設定傳感器數目為150,感知半徑為50 m時,圖5給出了4種算法在不同節點感知視角下的性能比較。覆蓋質量f隨節點感知視角α的增加呈現線性增長,旋轉角度之和Angle呈現線性減少。這是因為感知視角越大,節點能夠感知的范圍就越大,只要旋轉很小的角度甚至不旋轉就能容易地覆蓋到目標。

圖6顯示了4種算法在不同節點角速度下對覆蓋質量和旋轉角度之和的影響。可以看出,Random和Continue在不同的節點角速度下覆蓋質量變化不大,幾乎不受角速度影響。DPGKCA(P=0)和DPGKCA(P=1)算法呈現線性增長的趨勢,但DPGKCA(P=1)增長的速度明顯要快于DPGKCA(P=0),旋轉角度之和Angle呈現線性增加的趨勢。這是因為隨著角速度增大,DPGKCA(P=1)可以把更多的跟蹤節點旋轉到預測位置,滿足K覆蓋的要求。

不同K覆蓋體現了監測系統的特殊要求,圖7給出了4種算法在不同要求的K覆蓋下的性能比較。隨著K的不斷增加,覆蓋質量f明顯下降,但同樣的K值,DPGKCA(P=1)算法要好于其余3種方法。通過旋轉角度之和的圖示可以看出,在需要旋轉的角度幾乎一致的情況下,DPGKCA(P=1)要好于DPGKCA(P=0)。

目標移動的速度越快,單位時間步長內移動的距離就越大,由于目標的方向是可以隨時改變的,所以預測位置的準確性越低。圖8給出了4種算法在不同移動目標速度下的性能比較。和預期一致,隨著速度的增加,覆蓋質量f急劇下降,最后都趨向于Random初始部署。

圖5 節點感知視角對覆蓋質量和旋轉角度之和的影響

圖6 節點角速度對覆蓋質量和旋轉角度之和的影響

圖7 不同K覆蓋對覆蓋質量和旋轉角度之和的影響

圖8 目標移動速度對覆蓋質量和旋轉角度之和的影響

5 結束語

目標覆蓋是傳感器網絡的重要研究內容。本文從視頻傳感器節點的有向感知模型出發,深入研究了移動目標K級覆蓋問題。首先擴展了可旋轉的視頻傳感器節點有向感知模型,分析了監控區域內移動目標可能的行為,定義了MAKLC問題并給出了相應的數學描述。然后提出一種基于預測的分布式貪心算法DPGKCA,傳感器節點根據預測位置按需旋轉角度從小到大排序,選擇前K個節點進行旋轉,得到MAKLC問題的一個次優解。接下來根據實際監測需求優化一個目標覆蓋質量評價指標和一個目標覆蓋質量評價函數。最后通過一系列仿真實驗結果表明,算法DPGKCA提高了移動目標的覆蓋質量。因此,DPGKCA算法對移動目標K級覆蓋問題有效。在后期工作中,我們將研究如何提高預測位置的準確性,減少覆蓋移動目標延遲的算法。

[1] 李建中,高宏.無線傳感器網絡的研究進展[J].計算機研究與發展,2008,45(1):1-15.

[2]陶丹,馬華東.有向傳感器網絡覆蓋控制算法[J].軟件學報,2011,22(10):2317-2334.

[3]程衛芳,廖湘科,沈昌祥.有向傳感器網絡最大覆蓋調度算法[J].軟件學報,2009,20(4):975-984.

[4]蔣一波,王萬良,陳偉杰,等.視頻傳感器網絡中無盲區覆蓋優化算法[J].軟件學報,2012,23(2):310-322.

[5]Boulanouar I,Lohier S,Rachedi A,et al.CTA:a Collaborative Tracking Algorithm in Wireless Sensor Networks[C]//Proc.of the 2013 Int’l Conf.on Computing,Networking and Communications.2013:529-534.

[6]Wang Z,Bulut E,Szymanski B K.Distributed Target Tracking with Directional Binary Sensor Networks[C]//Global Telecommunica-tions Conference,2009.GLOBECOM 2009.IEEE.IEEE,2009.1-6.[7]李石堅,徐從富,吳朝暉,等.面向目標跟蹤的傳感器網絡布局優化及保護策略[J].電子學報,2006,34(1):71-76.

[8]陶丹,馬華東,劉亮.視頻傳感器網絡中路徑覆蓋增強算法研究[J].電子學報,2008,36(7):1291-1296.

[9]肖甫,王汝傳,葉曉國,等.基于改進勢場的有向傳感器網絡路徑覆蓋增強算法[J].計算機研究與發展,2009,46(12):2126-2133. [10]任靜,熊慶宇,石為人.一種基于預測策略的目標跟蹤算法研究[J].傳感技術學報,2011,24(10):1496-1500.

[11]Liu L,Ma HD,Zhang X.On Directional k-Coverage Analysis of Randomly Deployed Camera Sensor Networks[C]//Proc of the IEEE ICC 2008.New York:IEEE Press,2008:2707-2711.

[12]Wu Y A,Yin J P,Li M,et al.Efficient Algorithms for Probabilistic k-Coverage in Directional Sensor Networks[C]//Proc of the Int’l Conf on Intelligent Sensors,Sensor Networks and Information Processing.2008:587-592.

[13]Fusco G,Gupta H.Selection and Orientation of Directional Sensors for Coverage Maximization[C]//Proc of the 6th Annual IEEE Conf on Sensor,Mesh and Ad Hoc Communications and Networks.New York:IEEE Press,2009:1-9.

[14]張美燕,蔡文郁.無線視頻傳感器網絡有向感知K覆蓋控制算法研究[J].傳感技術學報,2013,26(5):728-733.

[15]蔣麗萍,王良民,熊書明,等.基于感知概率的無線傳感器網絡K重覆蓋算法[J].計算機應用研究,2009,26(9):3484-3489.[16]李明.基于差分算法的異構無線傳感器網絡多重覆蓋節點調度方案[J].傳感技術學報,2012,25(6):826-830.

[17]Fusco G,Gupta H.Placement and Orientation of Rotating Directional Sensors[C]//Proc.of the 7th Annual IEEE Communications Society Conf on Sensor Mesh and Ad Hoc Communications and Networks.New York:IEEE Press,2010:1-9.

蔣一波(1982-),男,工學博士,副教授,研究方向為計算機網絡控制與管理、無線傳感網絡監控系統等;

陳瓊(1990-),女,碩士生,研究方向為無線傳感器網絡;

王萬良(1957-),男,工學博士,教授,博士研究生導師,主要從事計算機控制與智能自動化、計算機網絡控制與管理等方面的研究;

樓弘(1991-),男,碩士生,研究方向為計算機網絡與電力系統。

AKlevelCoverageEnhancementAlgorithmBasedonMovingTargetTrajectoryPredictionforVideoSensorNetworks*

JIANGYibo*,CHENQiong,WANGWanliang,LOUHong

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

This paper starts from the directional perception model of video sensor nodes,further studies the moving target withKlevel coverage problem.First,the directional perception model of rotatable video sensor nodes is extended,the possible behaviors of moving target in the monitoring area are analyzed,the problem of minimum rotation angle of moving target withKlevel coverage is defined and the corresponding mathematical description is given.Then,we put forward a distributed prediction-based greedyKlevel coverage algorithm,which introduces a target trajectory prediction method.Finally,by comparing the optimized coverage quality evaluation indicators,a set of simulation results is performed to demonstrate the effectiveness of the proposed algorithm.

video sensor networks;moving target coverage;Klevel coverage;distributed algorithm

項目來源:“十二五”國家科技支撐計劃項目(2012BAD10B01);國家自然科學基金項目(61379123);國家自然科學基金項目(61070043);國家自然科學基金項目(61102067)

2014-04-08修改日期:2014-05-29

10.3969/j.issn.1004-1699.2014.07.018

TP393

:A

:1004-1699(2014)07-0956-08