視頻傳感器網(wǎng)絡(luò)中基于移動(dòng)目標(biāo)軌跡預(yù)測的K級(jí)覆蓋增強(qiáng)算法*

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

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

?

視頻傳感器網(wǎng)絡(luò)中基于移動(dòng)目標(biāo)軌跡預(yù)測的K級(jí)覆蓋增強(qiáng)算法*

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

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

從視頻傳感器節(jié)點(diǎn)的有向感知模型出發(fā),深入研究了移動(dòng)目標(biāo)K級(jí)覆蓋問題。首先擴(kuò)展了可旋轉(zhuǎn)的視頻傳感器節(jié)點(diǎn)有向感知模型,分析了監(jiān)控區(qū)域內(nèi)移動(dòng)目標(biāo)可能的行為,定義了最小旋轉(zhuǎn)角度的移動(dòng)目標(biāo)K級(jí)覆蓋問題并給出了對應(yīng)的數(shù)學(xué)描述。然后設(shè)計(jì)了一種目標(biāo)軌跡點(diǎn)預(yù)測方法,提出了基于預(yù)測的分布式貪心K級(jí)覆蓋算法。最后引入了優(yōu)化的覆蓋質(zhì)量評(píng)價(jià)指標(biāo),通過一系列仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

視頻傳感器網(wǎng)絡(luò);移動(dòng)目標(biāo)覆蓋;K級(jí)覆蓋;分布式算法

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

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

目前,有向傳感器網(wǎng)絡(luò)覆蓋理論從覆蓋對象的角度可分為區(qū)域覆蓋[3-4]和目標(biāo)覆蓋;從目標(biāo)出現(xiàn)形式看,目標(biāo)覆蓋問題分為靜態(tài)目標(biāo)覆蓋與移動(dòng)目標(biāo)覆蓋兩類;從覆蓋質(zhì)量看,有向K覆蓋是目前的研究熱點(diǎn)。

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

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

以上文獻(xiàn)均是單方面地考慮移動(dòng)目標(biāo)覆蓋問題和靜態(tài)目標(biāo)多重覆蓋問題,本文同時(shí)考慮了這兩方面的情況,并針對目標(biāo)移動(dòng)隨機(jī)性的特點(diǎn),設(shè)計(jì)了一種目標(biāo)軌跡點(diǎn)預(yù)測方法,達(dá)到移動(dòng)目標(biāo)實(shí)時(shí)K級(jí)覆蓋的要求。

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

1 最小旋轉(zhuǎn)角度的移動(dòng)目標(biāo)K級(jí)覆蓋問題MAKLC

本節(jié)主要分析和定義最小旋轉(zhuǎn)角度的移動(dòng)目標(biāo)K級(jí)覆蓋問題MAKLC。首先描述了方向可旋轉(zhuǎn)的視頻傳感器節(jié)點(diǎn)有向感知模型,然后分析了監(jiān)控區(qū)域內(nèi)移動(dòng)目標(biāo)可能的行為,最后形式化定義了MAKLC問題并給出了準(zhǔn)確的數(shù)學(xué)描述。

1.1 視頻傳感器節(jié)點(diǎn)有向感知模型

視頻傳感器節(jié)點(diǎn)不同于全向感知模型,有感知視角的限制,但其可以通過旋轉(zhuǎn)感知方向角來改變監(jiān)測區(qū)域。但是,節(jié)點(diǎn)旋轉(zhuǎn)具有角速度ω,在Δt時(shí)間范圍內(nèi)節(jié)點(diǎn)最大可以旋轉(zhuǎn)Δt*ω角度,假設(shè)節(jié)點(diǎn)旋轉(zhuǎn)順時(shí)針方向?yàn)檎较?節(jié)點(diǎn)感知方向角是以x軸正方向?yàn)槠瘘c(diǎn)順時(shí)針轉(zhuǎn)到扇形區(qū)域中心線的角度。因此,節(jié)點(diǎn)可以在[-Δt*ω,Δt*ω]范圍內(nèi)旋轉(zhuǎn)其感知方向來覆蓋監(jiān)測目標(biāo)。我們得到視頻傳感器節(jié)點(diǎn)方向可旋轉(zhuǎn)感知模型,如圖1所示。

圖1 方向可旋轉(zhuǎn)感知模型

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

特別地,當(dāng)α=2π時(shí),即FoV=2π時(shí),全向感知模型是有向感知模型的一個(gè)特例。

1.2 移動(dòng)目標(biāo)K級(jí)覆蓋

移動(dòng)目標(biāo)覆蓋是網(wǎng)絡(luò)檢測入侵目標(biāo)和跟蹤目標(biāo)軌跡的一類問題。當(dāng)目標(biāo)沒有進(jìn)入監(jiān)測區(qū)域時(shí),網(wǎng)絡(luò)節(jié)點(diǎn)工作在監(jiān)視模式,可以監(jiān)測到目標(biāo)的進(jìn)入;當(dāng)目標(biāo)出現(xiàn)時(shí),節(jié)點(diǎn)被喚醒,為目標(biāo)提供高質(zhì)量的感知覆蓋;當(dāng)目標(biāo)離開網(wǎng)絡(luò)時(shí),節(jié)點(diǎn)又進(jìn)入低能耗的監(jiān)視模式。移動(dòng)目標(biāo)K級(jí)覆蓋的工作過程可以劃分為目標(biāo)監(jiān)測、目標(biāo)覆蓋和目標(biāo)離開3個(gè)工作階段。

目標(biāo)M監(jiān)測:假設(shè)目標(biāo)從監(jiān)測區(qū)域的邊界進(jìn)入。當(dāng)沒有目標(biāo)出現(xiàn)時(shí),所有邊界附近的節(jié)點(diǎn)工作在監(jiān)視模式,其余節(jié)點(diǎn)休眠以節(jié)省能耗。有節(jié)點(diǎn)發(fā)現(xiàn)目標(biāo)后需要周圍節(jié)點(diǎn)協(xié)助感知目標(biāo)以獲得目標(biāo)的狀態(tài)信息。發(fā)現(xiàn)目標(biāo)的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播喚醒消息,被喚醒的鄰居節(jié)點(diǎn)協(xié)作獲得目標(biāo)的當(dāng)前的坐標(biāo)位置、移動(dòng)方向及移動(dòng)速度,把它們分別作為該目標(biāo)的初始位置、初始移動(dòng)方向及移動(dòng)速度,移動(dòng)速度保持不變。

目標(biāo)M覆蓋:在監(jiān)測到目標(biāo)M后,傳感器網(wǎng)絡(luò)需要通知該目標(biāo)附近的傳感器節(jié)點(diǎn)加入到目標(biāo)監(jiān)測過程中來。根據(jù)目標(biāo)移動(dòng)的軌跡點(diǎn)及時(shí)調(diào)整節(jié)點(diǎn)的感知方向角,按旋轉(zhuǎn)角速度ω旋轉(zhuǎn)節(jié)點(diǎn),滿足該軌跡點(diǎn)被K覆蓋。當(dāng)目標(biāo)移動(dòng)到傳感器節(jié)點(diǎn)無法覆蓋到的位置后,該傳感器節(jié)點(diǎn)恢復(fù)到休眠狀態(tài)。

目標(biāo)M離開:當(dāng)移動(dòng)目標(biāo)從監(jiān)測區(qū)域的邊界離開的時(shí)候,認(rèn)為該目標(biāo)消失,邊界附近的節(jié)點(diǎn)再次進(jìn)入監(jiān)視模式,其余節(jié)點(diǎn)休眠。

1.3MAKLC問題的分析與定義

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

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

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

(1)

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

(2)

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

(3)

定義2最小旋轉(zhuǎn)角度的移動(dòng)目標(biāo)K級(jí)覆蓋問題MAKLC:要求在監(jiān)測區(qū)域出現(xiàn)的移動(dòng)目標(biāo)每個(gè)時(shí)刻至少被K個(gè)不同傳感器節(jié)點(diǎn)同時(shí)覆蓋。調(diào)節(jié)節(jié)點(diǎn)感知方向按旋轉(zhuǎn)角速度ω旋轉(zhuǎn)節(jié)點(diǎn),滿足移動(dòng)目標(biāo)被K覆蓋的前提下使可覆蓋區(qū)內(nèi)的跟蹤節(jié)點(diǎn)旋轉(zhuǎn)角度之和最小。

由此可以得到以下的非線性優(yōu)化模型:

(4)

其中,目標(biāo)函數(shù)表示在移動(dòng)目標(biāo)從監(jiān)測區(qū)域的邊界進(jìn)入到離開的過程中,各個(gè)時(shí)刻的實(shí)際位置Sw在滿足K覆蓋的前提下使傳感器節(jié)點(diǎn)旋轉(zhuǎn)角度之和最小。約束條件表示在Tw時(shí)刻,目標(biāo)的實(shí)際位置Sw至少被K個(gè)視頻傳感器所覆蓋。

2 基于預(yù)測的分布式貪心K級(jí)覆蓋算法DPGKCA

本文研究的MAKLC問題屬于NP完全問題,所以上節(jié)的非線性優(yōu)化問題無法在多項(xiàng)式時(shí)間內(nèi)解決,而且大規(guī)模的視頻傳感器網(wǎng)絡(luò)全局信息很難采集完全,因此,需要尋求分布式次優(yōu)算法使視頻傳感器節(jié)點(diǎn)能夠獨(dú)立決策,減少通信開銷。本節(jié)設(shè)計(jì)了一種目標(biāo)軌跡點(diǎn)預(yù)測方法,提出了基于預(yù)測的分布式貪心K級(jí)覆蓋算法DPGKCA。傳感器節(jié)點(diǎn)根據(jù)預(yù)測位置進(jìn)行旋轉(zhuǎn)決策,避免了決策時(shí)延。

2.1 移動(dòng)目標(biāo)位置預(yù)測方法

假設(shè)移動(dòng)目標(biāo)M在Tw時(shí)刻監(jiān)測到的實(shí)際坐標(biāo)位置由Sw,w=0,1,2,…,表示,預(yù)測下一時(shí)刻即Tw+1時(shí)刻M的坐標(biāo)位置是Aw+1,w=0,1,2,…。預(yù)測位置Aw+1可能與實(shí)際位置Sw+1不一致。

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

根據(jù)移動(dòng)路徑Tr,移動(dòng)目標(biāo)M在時(shí)刻Tw的實(shí)際坐標(biāo)是Sw,速度為V,方向向量為Vw,時(shí)間間隔為Δt,在通常情況下取一極小時(shí)間間隔。假設(shè)在時(shí)間區(qū)間[Tw,Tw+1]內(nèi)M從點(diǎn)Sw到Aw+1以速度V做勻速直線運(yùn)動(dòng)。已知

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

(5)

Δt=Tw+1-Tw

(6)

(7)

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

(8)

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

其中

(9)

根據(jù)式(6)得到

Tw+1=Tw+Δt

(10)

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

2.2 DPGKCA算法描述

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

基于上述分析,本文提出DPGKCA算法,從第2個(gè)時(shí)刻開始先預(yù)測目標(biāo)下個(gè)時(shí)刻的位置,按預(yù)測位置確定跟蹤節(jié)點(diǎn)集合。每個(gè)時(shí)刻DPGKCA算法在跟蹤節(jié)點(diǎn)集合中并發(fā)執(zhí)行。DPGKCA算法描述如下:

輸入:節(jié)點(diǎn)i的位置和感知方向角θi,w信息和是否啟動(dòng)預(yù)測功能P。

輸出:節(jié)點(diǎn)i的感知方向角θi,w+1信息。

1.w←0;//初始化時(shí)間步長計(jì)數(shù)器

2. 計(jì)算節(jié)點(diǎn)i一個(gè)時(shí)間步長內(nèi)最大可旋轉(zhuǎn)角度Δt*ω;

3. while(true)

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

3.2. if(P) then//啟動(dòng)預(yù)測函數(shù)

3.2.1. 計(jì)算出預(yù)測位置Aw+1;

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

3.3. else//關(guān)閉預(yù)測函數(shù)

3.3.1. 決策位置L=目標(biāo)位置Trw;//賦值

3.4. ifL在節(jié)點(diǎn)i的感知范圍內(nèi)then

3.4.1.k←k-1;

3.4.2. continue;

3.6. 計(jì)算節(jié)點(diǎn)的感知方向角θi,w與di的逆時(shí)針夾角angle;

3.7. if(angle≤180)then

3.7.1. 計(jì)算旋轉(zhuǎn)后節(jié)點(diǎn)i的感知方向角θi,w+1=θi,w-angle+α/2;

3.7.2. 計(jì)算為覆蓋L,節(jié)點(diǎn)i需要旋轉(zhuǎn)的角度Di,w=angle-α/2;

3.8. else if(angle>180)then

3.8.1. 計(jì)算旋轉(zhuǎn)后節(jié)點(diǎn)i的感知方向角θi,w+1=θi,w-angle-α/2;

3.8.2. 計(jì)算為覆蓋L,節(jié)點(diǎn)i需要旋轉(zhuǎn)的角度Di,w=360-angle-α/2;

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

3.9.1.xi,w←1;

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

3.10. 節(jié)點(diǎn)i收到其余跟蹤節(jié)點(diǎn)的需要旋轉(zhuǎn)角度的消息;

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

3.12. if序列前k個(gè)節(jié)點(diǎn)中包含節(jié)點(diǎn)ithen

3.12.1. 旋轉(zhuǎn)i的感知方向至θi,w+1;

3.13. sleep(Δt);

4. end;

很顯然,只要跟蹤節(jié)點(diǎn)間旋轉(zhuǎn)角度信息能夠可靠傳輸,算法DPGKCA就能在有限時(shí)間內(nèi)終止。該算法加入了是否啟動(dòng)預(yù)測功能P的可選項(xiàng),啟動(dòng)預(yù)測函數(shù)可以避免決策的時(shí)延,更好地實(shí)現(xiàn)實(shí)時(shí)覆蓋移動(dòng)目標(biāo)的要求;若P為false即關(guān)閉預(yù)測計(jì)算,可以適應(yīng)某些工況中路徑點(diǎn)測量偏差較大的情況。

3 覆蓋質(zhì)量評(píng)價(jià)指標(biāo)

移動(dòng)目標(biāo)的覆蓋質(zhì)量不僅與被多少個(gè)活躍節(jié)點(diǎn)感知有關(guān),而且與感知的持續(xù)時(shí)間有關(guān)。覆蓋目標(biāo)的節(jié)點(diǎn)數(shù)越多、被持續(xù)覆蓋的時(shí)間越長,則覆蓋質(zhì)量越高。目標(biāo)在各個(gè)時(shí)刻被節(jié)點(diǎn)覆蓋的個(gè)數(shù)可能不是K,需要根據(jù)實(shí)際要求來量化未達(dá)到K級(jí)覆蓋、達(dá)到K級(jí)覆蓋和超過K級(jí)覆蓋的權(quán)重值,并且也要考慮目標(biāo)被K覆蓋的時(shí)間長度。例如3個(gè)時(shí)刻達(dá)到1重覆蓋應(yīng)該比1個(gè)時(shí)刻達(dá)到3重覆蓋性能好。另外,節(jié)點(diǎn)旋轉(zhuǎn)會(huì)消耗自身的能量,節(jié)能低耗可以延長視頻傳感器網(wǎng)絡(luò)的工作時(shí)間,最小化節(jié)點(diǎn)旋轉(zhuǎn)角度之和也是我們追求的目標(biāo)。因此,目標(biāo)覆蓋質(zhì)量評(píng)價(jià)指標(biāo)關(guān)系到比較各個(gè)算法性能的優(yōu)劣,本節(jié)根據(jù)實(shí)際監(jiān)測需求引入了一個(gè)目標(biāo)覆蓋質(zhì)量評(píng)價(jià)指標(biāo)和優(yōu)化了一種目標(biāo)覆蓋質(zhì)量評(píng)價(jià)函數(shù)。

3.1 節(jié)點(diǎn)旋轉(zhuǎn)角度之和

節(jié)點(diǎn)旋轉(zhuǎn)角度之和Angle可以對同一移動(dòng)目標(biāo)從一方面來反映各個(gè)算法的能耗。統(tǒng)計(jì)方法:每個(gè)跟蹤節(jié)點(diǎn)對收集到的可以旋轉(zhuǎn)的節(jié)點(diǎn)按旋轉(zhuǎn)角度從小到大排序,選擇前K個(gè)節(jié)點(diǎn)統(tǒng)計(jì)它們的旋轉(zhuǎn)角度之和。

3.2 覆蓋質(zhì)量函數(shù)

4 算法仿真與性能分析

4.1 仿真環(huán)境與實(shí)驗(yàn)實(shí)例

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

本節(jié)我們通過一個(gè)具體實(shí)例說明DPGKCA算法對視頻傳感器網(wǎng)絡(luò)移動(dòng)目標(biāo)K級(jí)覆蓋的過程。按照上述仿真環(huán)境配置參數(shù)值,記錄下DPGKCA算法運(yùn)行不同時(shí)間步長時(shí)網(wǎng)絡(luò)的目標(biāo)覆蓋情況,如圖2所示。并對此例中移動(dòng)目標(biāo)達(dá)到K覆蓋的時(shí)間進(jìn)行步長統(tǒng)計(jì),如表1所示。

圖2 DPGKCA算法實(shí)現(xiàn)移動(dòng)目標(biāo)K級(jí)覆蓋

表1 移動(dòng)目標(biāo)K級(jí)覆蓋的時(shí)間步長統(tǒng)計(jì)

由表1的統(tǒng)計(jì)結(jié)果可以直觀地看出,此例中移動(dòng)目標(biāo)的整個(gè)運(yùn)動(dòng)過程中沒有被視頻節(jié)點(diǎn)感知到的時(shí)間只有兩個(gè)時(shí)間步長。達(dá)到maxK=4要求的時(shí)間有47個(gè)時(shí)間步長,超過整個(gè)時(shí)間的一半。由此可見DPGKCA算法可以解決移動(dòng)目標(biāo)K級(jí)覆蓋問題。

4.2 性能比較

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

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

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

圖3 傳感器數(shù)目對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

圖4 節(jié)點(diǎn)感知半徑對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

設(shè)定傳感器數(shù)目為150,感知半徑為50 m時(shí),圖5給出了4種算法在不同節(jié)點(diǎn)感知視角下的性能比較。覆蓋質(zhì)量f隨節(jié)點(diǎn)感知視角α的增加呈現(xiàn)線性增長,旋轉(zhuǎn)角度之和Angle呈現(xiàn)線性減少。這是因?yàn)楦兄暯窃酱?節(jié)點(diǎn)能夠感知的范圍就越大,只要旋轉(zhuǎn)很小的角度甚至不旋轉(zhuǎn)就能容易地覆蓋到目標(biāo)。

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

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

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

圖5 節(jié)點(diǎn)感知視角對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

圖6 節(jié)點(diǎn)角速度對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

圖7 不同K覆蓋對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

圖8 目標(biāo)移動(dòng)速度對覆蓋質(zhì)量和旋轉(zhuǎn)角度之和的影響

5 結(jié)束語

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

[1] 李建中,高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展,2008,45(1):1-15.

[2]陶丹,馬華東.有向傳感器網(wǎng)絡(luò)覆蓋控制算法[J].軟件學(xué)報(bào),2011,22(10):2317-2334.

[3]程衛(wèi)芳,廖湘科,沈昌祥.有向傳感器網(wǎng)絡(luò)最大覆蓋調(diào)度算法[J].軟件學(xué)報(bào),2009,20(4):975-984.

[4]蔣一波,王萬良,陳偉杰,等.視頻傳感器網(wǎng)絡(luò)中無盲區(qū)覆蓋優(yōu)化算法[J].軟件學(xué)報(bào),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]李石堅(jiān),徐從富,吳朝暉,等.面向目標(biāo)跟蹤的傳感器網(wǎng)絡(luò)布局優(yōu)化及保護(hù)策略[J].電子學(xué)報(bào),2006,34(1):71-76.

[8]陶丹,馬華東,劉亮.視頻傳感器網(wǎng)絡(luò)中路徑覆蓋增強(qiáng)算法研究[J].電子學(xué)報(bào),2008,36(7):1291-1296.

[9]肖甫,王汝傳,葉曉國,等.基于改進(jìn)勢場的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強(qiáng)算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(12):2126-2133. [10]任靜,熊慶宇,石為人.一種基于預(yù)測策略的目標(biāo)跟蹤算法研究[J].傳感技術(shù)學(xué)報(bào),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]張美燕,蔡文郁.無線視頻傳感器網(wǎng)絡(luò)有向感知K覆蓋控制算法研究[J].傳感技術(shù)學(xué)報(bào),2013,26(5):728-733.

[15]蔣麗萍,王良民,熊書明,等.基于感知概率的無線傳感器網(wǎng)絡(luò)K重覆蓋算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(9):3484-3489.[16]李明.基于差分算法的異構(gòu)無線傳感器網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度方案[J].傳感技術(shù)學(xué)報(bào),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-),男,工學(xué)博士,副教授,研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)控制與管理、無線傳感網(wǎng)絡(luò)監(jiān)控系統(tǒng)等;

陳瓊(1990-),女,碩士生,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò);

王萬良(1957-),男,工學(xué)博士,教授,博士研究生導(dǎo)師,主要從事計(jì)算機(jī)控制與智能自動(dòng)化、計(jì)算機(jī)網(wǎng)絡(luò)控制與管理等方面的研究;

樓弘(1991-),男,碩士生,研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與電力系統(tǒng)。

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

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

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

10.3969/j.issn.1004-1699.2014.07.018

TP393

:A

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