，

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

視頻傳感器網(wǎng)絡(luò)中移動(dòng)目標(biāo)k覆蓋優(yōu)化算法

蔣一波，盛尚浩

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

k覆蓋問(wèn)題作為視頻傳感器網(wǎng)絡(luò)中的一個(gè)研究熱點(diǎn)，引起了許多研究者的關(guān)注.針對(duì)視頻傳感器網(wǎng)絡(luò)中的移動(dòng)目標(biāo)k級(jí)覆蓋問(wèn)題，結(jié)合概率預(yù)測(cè)思想，充分考慮非勻速移動(dòng)目標(biāo)的運(yùn)動(dòng)特性和下一時(shí)刻目標(biāo)有可能達(dá)到的位置，建立了一種移動(dòng)目標(biāo)覆蓋概率評(píng)估模型，提高了k覆蓋的概率.同時(shí)，提出了新的基于預(yù)測(cè)的分布式k覆蓋優(yōu)化算法，傳感器節(jié)點(diǎn)在通信范圍內(nèi)交換覆蓋信息并進(jìn)行決策.最后通過(guò)一系列仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法和模型的有效性和可行性.

視頻傳感器網(wǎng)絡(luò)；移動(dòng)目標(biāo)；k覆蓋；概率模型

近年來(lái)隨著圖像和計(jì)算處理能力的迅猛發(fā)展，視頻傳感器網(wǎng)絡(luò)(VSNs, Visual sensor networks)因其部署便捷、高精度、高可靠性和易擴(kuò)展性等性能優(yōu)勢(shì)，在監(jiān)控、安防等領(lǐng)域得到廣泛的關(guān)注和應(yīng)用，例如監(jiān)控系統(tǒng)、交通管制和醫(yī)療監(jiān)護(hù)等[1-2].視頻傳感器網(wǎng)絡(luò)由許多智能視頻傳感器節(jié)點(diǎn)構(gòu)成，相較于傳統(tǒng)的傳感器網(wǎng)絡(luò)，最大的區(qū)別在于節(jié)點(diǎn)，視頻傳感器的節(jié)點(diǎn)可以通過(guò)調(diào)整自己的視域(FoVs, Field-of-views)優(yōu)化覆蓋目標(biāo)，監(jiān)測(cè)入侵物或者需要重點(diǎn)監(jiān)控的區(qū)域[1,3].視頻傳感器網(wǎng)絡(luò)作為一個(gè)前沿的研究領(lǐng)域，結(jié)合了傳感器、視頻、通信和分布式處理等眾多技術(shù)，其顯著的優(yōu)勢(shì)主要體現(xiàn)在：網(wǎng)絡(luò)能力增強(qiáng)、媒體信息豐富和處理復(fù)雜任務(wù)等.

覆蓋問(wèn)題作為傳感器網(wǎng)絡(luò)中的一個(gè)重要研究問(wèn)題，大致可劃分為三大類：目標(biāo)覆蓋(Target coverage)、區(qū)域覆蓋(Area coverage)和柵欄覆蓋(Barrier coverage)[4-7].目標(biāo)覆蓋主要研究的問(wèn)題：如何調(diào)度和分配有限的傳感器節(jié)點(diǎn)覆蓋監(jiān)測(cè)區(qū)域內(nèi)的目標(biāo)，其中每個(gè)目標(biāo)至少被k(k≥1)個(gè)不同的傳感器節(jié)點(diǎn)同時(shí)覆蓋的問(wèn)題被歸納為k覆蓋[8-9].近些年來(lái)有許多國(guó)內(nèi)外學(xué)者對(duì)目標(biāo)覆蓋問(wèn)題進(jìn)行了研究，Liu等[10]提出DKC(Directionalk-coverage)的概念，通過(guò)概率論方法構(gòu)建覆蓋質(zhì)量和傳感器節(jié)點(diǎn)數(shù)量之間的關(guān)系模型.Maleks等[11]設(shè)計(jì)了一種集中式貪心k覆蓋算法(CGkCA)，解決了在節(jié)點(diǎn)數(shù)量不足的情況下進(jìn)行k覆蓋所產(chǎn)生的不平衡的問(wèn)題.為了解決無(wú)線傳感器網(wǎng)絡(luò)中目標(biāo)跟蹤的能耗問(wèn)題，任靜等[12]提出了一種基于預(yù)測(cè)策略的目標(biāo)跟蹤算法，兼顧能耗的同時(shí)降低了目標(biāo)丟失率，保證了精度.張美燕等[13]設(shè)計(jì)了一種簡(jiǎn)單的分布式啟發(fā)算法，調(diào)度在一跳鄰居范圍內(nèi)的傳感器節(jié)點(diǎn)的感知方向，使得更多的目標(biāo)被k覆蓋延長(zhǎng)k覆蓋時(shí)間.蔣麗萍[14]等考慮了實(shí)際應(yīng)用中環(huán)境因素對(duì)節(jié)點(diǎn)感知能力的影響，提出了一種分布式k重覆蓋算法KCAPSM，采用了感知概率模型保證監(jiān)測(cè)區(qū)域中每一點(diǎn)被k重覆蓋.由于視頻傳感器節(jié)點(diǎn)計(jì)算處理能有限，大量精準(zhǔn)的預(yù)測(cè)方法會(huì)加重節(jié)點(diǎn)的能耗負(fù)擔(dān)，需要尋求一種平衡能耗和k覆蓋概率的策略.筆者針對(duì)非勻速的移動(dòng)目標(biāo)，提出了基于預(yù)測(cè)的移動(dòng)目標(biāo)覆蓋k覆蓋算法，分析移動(dòng)目標(biāo)的運(yùn)動(dòng)特性，充分考慮下一個(gè)時(shí)刻目標(biāo)有可能到達(dá)的位置，建立一個(gè)覆蓋概率評(píng)估模型，進(jìn)而設(shè)計(jì)了一種分布式k覆蓋優(yōu)化算法.算法在提高目標(biāo)k覆蓋概率的同時(shí)降低了傳感器節(jié)點(diǎn)的能耗，延長(zhǎng)整個(gè)視頻傳感器網(wǎng)絡(luò)的使用壽命.

1 移動(dòng)目標(biāo)k覆蓋問(wèn)題

為了更好地闡述非勻速移動(dòng)目標(biāo)k覆蓋問(wèn)題，在給出數(shù)學(xué)模型之前先提出如下假設(shè):

1)視頻傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)都是同構(gòu)的，即節(jié)點(diǎn)的各項(xiàng)參數(shù)都是相同的.

2)監(jiān)測(cè)區(qū)域內(nèi)的所有傳感器節(jié)點(diǎn)都是隨機(jī)投放，且投放之后位置固定.

3)傳感器節(jié)點(diǎn)可以有效地識(shí)別各個(gè)目標(biāo)并獲取目標(biāo)的運(yùn)動(dòng)信息，且目標(biāo)自身帶有編號(hào).

4)移動(dòng)目標(biāo)在整個(gè)運(yùn)動(dòng)過(guò)程中做變速運(yùn)動(dòng)，且移動(dòng)目標(biāo)之間不會(huì)相互干擾.

1.1 視頻傳感器模型

視頻傳感器的感知范圍取決于其視域(FoV， Filed of view)，現(xiàn)有的視頻傳感器節(jié)點(diǎn)可以通過(guò)三種方式調(diào)節(jié)其感知范圍：水平方向調(diào)整感知方向，垂直方向轉(zhuǎn)動(dòng)感知方向，改變感知半徑.研究使用的視頻傳感器節(jié)點(diǎn)限定只能在二維平面內(nèi)進(jìn)行轉(zhuǎn)動(dòng)，傳感器節(jié)點(diǎn)的感知區(qū)域是一個(gè)圓心為節(jié)點(diǎn)Ps，感知半徑為Rs，夾角為α的扇形區(qū)域.任意傳感器節(jié)點(diǎn)可以用一個(gè)四元組〈Ps,Rs,α,θ〉來(lái)表示，其中Ps代表節(jié)點(diǎn)在笛卡爾坐標(biāo)系中的位置；Rs表示節(jié)點(diǎn)的最大感知半徑，任何與節(jié)點(diǎn)坐標(biāo)Ps的歐式距離大于Rs的目標(biāo)都無(wú)法被精準(zhǔn)感知；α表示節(jié)點(diǎn)的最大感知夾角，夾角越大則感知范圍越大；θ表示節(jié)點(diǎn)的感知方向角，節(jié)點(diǎn)可以通過(guò)調(diào)整自身的感知方向角來(lái)優(yōu)化覆蓋效果.

圖1 視頻傳感器節(jié)點(diǎn)感知模型Fig.1 Perception model of visual sensor node

1.2 問(wèn)題分析與定義

目前用于目標(biāo)跟蹤的預(yù)測(cè)方法主要有粒子群濾波、卡爾曼濾波等[11,15]，但是這些方法需要大量的數(shù)據(jù)迭代計(jì)算，且對(duì)節(jié)點(diǎn)的處理能力要求高.雖然這些技術(shù)更加精確，但是這些方法不適合應(yīng)用于計(jì)算能力和資源有限的視頻傳感器節(jié)點(diǎn).針對(duì)上述問(wèn)題，采用概率預(yù)測(cè)思想來(lái)進(jìn)行優(yōu)化，在移動(dòng)目標(biāo)運(yùn)動(dòng)過(guò)程中提前分析其運(yùn)動(dòng)到下一個(gè)時(shí)刻有可能到達(dá)的位置，并給出覆蓋概率分布.

時(shí)刻移動(dòng)目標(biāo)最有可能到達(dá)的位置是繼續(xù)以at經(jīng)過(guò)Δt時(shí)間運(yùn)動(dòng)到的坐標(biāo)位置.當(dāng)然下一個(gè)時(shí)刻目標(biāo)的加速度會(huì)隨機(jī)變化，但不會(huì)發(fā)生劇烈的變化，將目標(biāo)的加速度大小與方向作為兩個(gè)隨機(jī)變量，分別用X表示大小變量，Y表示方向偏角，且x∈[amin,amax]，y∈[-π,π]，因此覆蓋概率密度函數(shù)γ(x,y)滿足：

(1)

為了更加直觀的展示下一個(gè)時(shí)刻移動(dòng)目標(biāo)落點(diǎn)的概率分布，圖2為相同初始條件但加速度不同的情況下概率分布熱力對(duì)比圖.

圖2 移動(dòng)目標(biāo)落點(diǎn)概率分布對(duì)比圖Fig.2 Probability distribution of moving target positions

假設(shè)當(dāng)前時(shí)刻為t，圖2(a)為移動(dòng)目標(biāo)在t時(shí)刻從原點(diǎn)(0,0)出發(fā)，以初速度v0=40,延x軸正方向運(yùn)動(dòng)，且加速度大小a0=20，加速度方向與y軸正方向一致；圖2(b)為移動(dòng)目標(biāo)在t時(shí)刻同樣從原點(diǎn)(0,0)出發(fā)，以初速度v0=40,延x軸正方向，且加速度大小a0=20，但加速度方向與y軸正方向呈30°夾角，經(jīng)過(guò)Δt時(shí)間間隔后有可能到達(dá)的位置的概率分布.圖2中黑色水滴形區(qū)域?yàn)榭赡苄暂^大的落點(diǎn)區(qū)域，即t+1時(shí)刻目標(biāo)到達(dá)該區(qū)域的可能性更大，而周圍白色區(qū)域則表示t+1時(shí)刻目標(biāo)到達(dá)該區(qū)域的可能性較小.

每個(gè)時(shí)刻，根據(jù)監(jiān)測(cè)要求和容錯(cuò)需求，移動(dòng)目標(biāo)至少被k個(gè)不同的視頻傳感器節(jié)點(diǎn)所覆蓋，結(jié)合上述覆蓋概率分布函數(shù)，筆者的研究目標(biāo)旨在完成對(duì)所有目標(biāo)的k覆蓋同時(shí)降低旋轉(zhuǎn)可能帶來(lái)的能耗損失.通過(guò)分析下一時(shí)刻移動(dòng)目標(biāo)有可能的運(yùn)動(dòng)軌跡，根據(jù)最優(yōu)覆蓋效果調(diào)整節(jié)點(diǎn)的感知方向，可以盡可能地提高k覆蓋的質(zhì)量，用盡可能小地旋轉(zhuǎn)能耗代價(jià)換取高質(zhì)量的移動(dòng)目標(biāo)k覆蓋.

由此建立非線性優(yōu)化模型為

Δθi,t∈[-ωΔt,ωΔt]?i=1,2,…,n?j=1,2,…,m

(2)

(3)

在判斷是否達(dá)到k覆蓋要求時(shí)，采用四舍五入取整的計(jì)算方式，可以在一定程度上避免多個(gè)覆蓋概率較小的節(jié)點(diǎn)被選中.

2 基于預(yù)測(cè)的分布式覆蓋算法

針對(duì)上節(jié)所述的移動(dòng)目標(biāo)k覆蓋問(wèn)題，由于該問(wèn)題屬于NP完全問(wèn)題，難以在多項(xiàng)式時(shí)間內(nèi)解決.同時(shí)在監(jiān)測(cè)區(qū)內(nèi)采集全局信息存在一定困難，因此需要尋求一種分布式次優(yōu)解算法[16-19].本節(jié)提出了一種基于預(yù)測(cè)的移動(dòng)目標(biāo)k覆蓋動(dòng)態(tài)優(yōu)化算法KPNMOA，充分考慮非勻速移動(dòng)目標(biāo)每一個(gè)時(shí)刻所有可能到達(dá)的位置，模擬了所有落點(diǎn)的概率值，在通信范圍內(nèi)與鄰居節(jié)點(diǎn)交換覆蓋信息，依次作出決策.

KPNMOA算法描述：從移動(dòng)目標(biāo)進(jìn)入?yún)^(qū)域開始，每個(gè)時(shí)刻，傳感器節(jié)點(diǎn)Si以當(dāng)前感知方向角為基準(zhǔn)，計(jì)算出在可旋轉(zhuǎn)范圍內(nèi)的最優(yōu)覆蓋效果，即能夠達(dá)到的最大覆蓋概率預(yù)測(cè)值Pmax為

(4)

式中：M為覆蓋區(qū)域內(nèi)未滿足k覆蓋的移動(dòng)目標(biāo)個(gè)數(shù)總和；fij為在覆蓋最大的條件下，節(jié)點(diǎn)Si對(duì)目標(biāo)Tj分別進(jìn)行覆蓋的概率.在通信范圍內(nèi)廣播并接受鄰居節(jié)點(diǎn)的覆蓋信息數(shù)據(jù)包，包含節(jié)點(diǎn)編號(hào)ID，最大覆蓋概率Pmax，感知方向偏移角度Δθi，目標(biāo)Tj的覆蓋概率fij.算法首先選取覆蓋效果最佳的傳感器節(jié)點(diǎn)先進(jìn)行決策，然后按照覆蓋效果值從大到小依次選取節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，算法終止條件為所有節(jié)點(diǎn)都已經(jīng)調(diào)整自身的感知視角或者所有移動(dòng)目標(biāo)都滿足k級(jí)覆蓋.若某一個(gè)移動(dòng)目標(biāo)的累積覆蓋概率之和大于k時(shí)，則判定該目標(biāo)達(dá)到k覆蓋要求，下一輪循環(huán)無(wú)需考慮覆蓋.KPNMOA算法流程如下：

Input：每個(gè)節(jié)點(diǎn)的坐標(biāo)位置和各自的感知方向

Output：每個(gè)節(jié)點(diǎn)的感知方向角

1)t←0;

2) 獲取節(jié)點(diǎn)位置P;

3) 獲取通信范圍內(nèi)鄰居節(jié)點(diǎn)集合φ;

4) Status←false;//標(biāo)志位

5) while(true)

6)t←t+1;

7) 計(jì)算節(jié)點(diǎn)Si可以覆蓋且未被k覆蓋的目標(biāo)集合φj

8) 計(jì)算移動(dòng)目標(biāo)落點(diǎn)分布概率

9) sumj=0;

10) while(Status==false &&φj!=null)

11) 計(jì)算節(jié)點(diǎn)Si達(dá)到最大覆蓋效果值時(shí)的Δθi和Pmax;

12) 廣播并接受覆蓋消息數(shù)據(jù)包

13) 按照f(shuō)ij值大小降序排序，如果一致按|Δθi|值從小到大排序;

14) 選擇覆蓋效果最好的節(jié)點(diǎn)Sa;

15) sumj+=fij;//累加覆蓋值

16) if([0.5+sumj]≥k)

目標(biāo)Tj達(dá)到k覆蓋;

17) if(Sa==Si){

18) Status=true;

19)θ+=Δθi;//旋轉(zhuǎn)節(jié)點(diǎn)

}

20) sleep(Δt);

21) end while;

22) end while;

在保證數(shù)據(jù)可靠傳輸?shù)那闆r下，KPNMOA算法就能在有限時(shí)間內(nèi)終止.算法將覆蓋概率函數(shù)作為指導(dǎo)，并將加速度納入函數(shù)可以確保大概率評(píng)估更加合理，提前作出合理的旋轉(zhuǎn)決策，更好地實(shí)現(xiàn)了實(shí)時(shí)移動(dòng)目標(biāo)k覆蓋.

3 算法仿真

為了更好地驗(yàn)證KPNMOA算法的可行性和有效性,基于Net Framework開發(fā)了仿真平臺(tái)進(jìn)行模擬實(shí)驗(yàn)研究，給出不同體系下的各種性能對(duì)比.在500×500的監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)投放下N個(gè)視頻傳感器節(jié)點(diǎn)進(jìn)行覆蓋工作，每個(gè)視頻傳感器節(jié)點(diǎn)規(guī)格相同，仿真參數(shù)值如表1所示.

表1 傳感器節(jié)點(diǎn)參數(shù)Table 1 Parameters of sensor node

圖3展示了當(dāng)監(jiān)測(cè)區(qū)域內(nèi)出現(xiàn)5個(gè)移動(dòng)目標(biāo)時(shí)的仿真實(shí)驗(yàn)過(guò)程，每個(gè)移動(dòng)目標(biāo)的初始速度為10 m/s，且加速度a∈[-5,5].圖3記錄了KPNMOA算法運(yùn)行不同時(shí)間步長(zhǎng)后視頻傳感器網(wǎng)絡(luò)中移動(dòng)目標(biāo)覆蓋情況以及每個(gè)移動(dòng)目標(biāo)的運(yùn)動(dòng)軌跡.

將KPNMOA算法與其他三種算法Continue(節(jié)點(diǎn)持續(xù)旋轉(zhuǎn))，DPGKCA[9]算法,MPKCDA[15]算法進(jìn)行比較，考察了在傳感器節(jié)點(diǎn)數(shù)量，感知半徑發(fā)生等關(guān)鍵參數(shù)變化時(shí)對(duì)覆蓋質(zhì)量產(chǎn)生的影響.首先給出覆蓋質(zhì)量函數(shù)為

(5)

式中：t為時(shí)間步長(zhǎng)；k為實(shí)際k覆蓋大小,k覆蓋持續(xù)時(shí)間是評(píng)價(jià)覆蓋質(zhì)量的重要因素，并采用平均值來(lái)進(jìn)行比較.圖4比較了不同傳感器節(jié)點(diǎn)規(guī)模時(shí)各算法的覆蓋質(zhì)量，其中節(jié)點(diǎn)數(shù)量從50～250依次遞增20.由圖4可知：覆蓋質(zhì)量Q隨著節(jié)點(diǎn)數(shù)量N的增大而增大，顯然網(wǎng)絡(luò)中部署更多節(jié)點(diǎn)可以延長(zhǎng)k覆蓋的時(shí)間，同時(shí)當(dāng)節(jié)點(diǎn)數(shù)量相同時(shí)，Continue的效果是最不理想的，KPNMOA隨著傳感器節(jié)點(diǎn)數(shù)量增加性能提高優(yōu)于MPKCDA和DPGKCA.

圖4 不同網(wǎng)絡(luò)規(guī)模對(duì)覆蓋質(zhì)量的影響Fig.4 Effect of networks size on the coverage quality

圖5為不同傳感器節(jié)點(diǎn)感知半徑時(shí)四種算法的覆蓋質(zhì)量的對(duì)比情況，半徑以10為步長(zhǎng)從10～90依次遞增.覆蓋質(zhì)量Q隨節(jié)點(diǎn)感知半徑R的增加呈現(xiàn)指數(shù)級(jí)增長(zhǎng)，因?yàn)榘殡S感知半徑的增加,節(jié)點(diǎn)的感知范圍快速變大，k覆蓋的概率也隨之提高.較其他三種算法,隨著半徑的增加KPNMOA的優(yōu)勢(shì)越來(lái)越明顯.

圖6顯示了四種算法在感知角度大小變化時(shí)的覆蓋質(zhì)量.當(dāng)感知角度增大時(shí)，可覆蓋到的目標(biāo)數(shù)量也會(huì)增多，因此覆蓋質(zhì)量Q隨節(jié)點(diǎn)感知角度α的增長(zhǎng)呈線性增長(zhǎng)，KPNMOA的增長(zhǎng)幅度明顯高于其他三種算法.

圖5 傳感器節(jié)點(diǎn)感知半徑對(duì)覆蓋質(zhì)量的影響Fig.5 Effect of sensor node perception radius on the coverage quality

圖7給出了四種算法在不同k覆蓋要求的情況下的性能比較.Maxk代表了監(jiān)測(cè)區(qū)域的安全需求等級(jí)，Maxk值越大則每個(gè)時(shí)刻需要更多的視頻傳感器節(jié)點(diǎn)來(lái)跟蹤移動(dòng)目標(biāo)，該監(jiān)測(cè)區(qū)域的安全需求越高.由圖7可知：Continue和DPGKCA的覆蓋質(zhì)量不斷下降，而MPKCDA和KPNMOA呈先增加后下降變化，其中KPNMOA對(duì)k值變化的適應(yīng)性更強(qiáng).

圖6 傳感器節(jié)點(diǎn)感知角度對(duì)覆蓋質(zhì)量的影響Fig.6 Effect of sensor node perception angle on the coverage quality

圖7 不同覆蓋要求對(duì)覆蓋質(zhì)量的影響Fig.7 Effect of Maxk on the coverage quality

4 結(jié) 論

針對(duì)視頻傳感器網(wǎng)絡(luò)中的移動(dòng)目標(biāo)k覆蓋問(wèn)題，首先建立一個(gè)覆蓋概率評(píng)估模型，分析非勻速移動(dòng)目標(biāo)的運(yùn)動(dòng)軌跡，將加速度納入概率模型使計(jì)算下一個(gè)時(shí)刻的覆蓋概率更加合理，然后設(shè)計(jì)了一種基于預(yù)測(cè)的分布式k覆蓋優(yōu)化算法，提高了移動(dòng)目標(biāo)的k覆蓋概率和覆蓋時(shí)長(zhǎng).仿真結(jié)果顯示在不同網(wǎng)絡(luò)規(guī)模、感知半徑、感知角度和覆蓋要求時(shí)KPNMOA均具有更好的性能表現(xiàn).在下一步工作中，將根據(jù)實(shí)際環(huán)境考慮加入障礙物后的移動(dòng)目標(biāo)k覆蓋優(yōu)化問(wèn)題，并對(duì)算法進(jìn)行改進(jìn)降低時(shí)間復(fù)雜度.

[1] MUNISHWAR V P, ABU-GHAZALEH N B. Coverage algorithms for visual sensor networks[J]. ACM transactions on sensor

networks,2013,9(9):1-36.

[2] 周曉,李杰,邊裕挺.基于無(wú)線傳感網(wǎng)絡(luò)的環(huán)境溫度監(jiān)測(cè)系統(tǒng)設(shè)計(jì)[J].浙江工業(yè)大學(xué)學(xué)報(bào),2013,41(4):440-443

[3] 劉唐，彭艦，楊進(jìn).異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J].軟件學(xué)報(bào)，2013(2):215-229.

[4] GUVENSAN M A, YAVUZ A G. On coverage issues in directional sensor networks: a survey[J].Ad Hoc networks,2011,9(7):1238-1255.

[5] CARDEI M, DU D Z. Improving wireless sensor network lifetime through power aware organization[J]. Wireless networks,2005,11(3):333-340.

[6] YANG Y, AMBROSE A, CARDEI M. Coverage for composite event detection in wireless sensor network[J]. Wirelesscommunications and mobile computing,2011,11(8):1168-1181.

[7] SUNG T W, YANG C S. Voronoi-based coverage improvement approach for wireless directional sensor networks[J].Journal of network and computer applications，2014，39(1):202-213.

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

[9] 蔣一波,陳瓊,王萬(wàn)良，等.視頻傳感器網(wǎng)絡(luò)中基于移動(dòng)目標(biāo)軌跡預(yù)測(cè)的k級(jí)覆蓋增強(qiáng)算法[J].傳感技術(shù)學(xué)報(bào),2014(7):956-963.

[10] LIU L, MA H D, ZHANG X. On directionalk-coverage analysis of randomly deployed camera sensor networks[C]//IEEE International Conference on Communications. New York: IEEE Press,2008:2707-2711.

[11] MALEKS M B, SADIK M M, RAHMAN A. On balancedk-coverage in visual sensor networks[J]. Journal of network &computer applications,2015,72:72-86.

[12] 任靜,熊慶宇,石為人.一種基于預(yù)測(cè)策略的目標(biāo)跟蹤算法研究[J].傳感技術(shù)學(xué)報(bào),2011,24(10):1496-1500.

[13] 張美燕,蔡文郁.無(wú)線視頻傳感器網(wǎng)絡(luò)有向感知k覆蓋控制算法研究[J].傳感技術(shù)學(xué)報(bào),2013,26(5):728-733.

[14] 蔣麗萍,王良民,熊書明,等.基于感知概率的無(wú)線傳感器網(wǎng)絡(luò)k重覆蓋算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(9):3484-3489.

[15] 俞立,王銘,董齊芬，等.基于無(wú)線傳感網(wǎng)的目標(biāo)跟蹤算法及實(shí)驗(yàn)系統(tǒng)設(shè)計(jì)[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(6):649-652

[16] 蔣一波,陳瓊,王萬(wàn)良,等.視頻傳感器網(wǎng)絡(luò)中多路徑k級(jí)覆蓋動(dòng)態(tài)優(yōu)化算法[J].儀器儀表學(xué)報(bào),2015,36(4):830-840.

[17] ISLAM M M, AHASANUZZAMAN M, RAZZAQUE M A, et al. Target coverage through distributed clustering in directional sensor networks[J]. Eurasip journal on wireless communications and networking,2015(1):167.

[18] JING A, ABOUZEID A A. Coverage by directional sensors in randomly deployed wireless sensor networks[J]. Journal of combinatorial optimization,2006,11(1):21-41.

[19] 張文安,薛東國(guó),俞立.面向節(jié)能的無(wú)線多傳感器H∞融合估計(jì)[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,43(3):237-242.

Optimizedmovingtargetsk-coveragealgorithmforvisualsensornetworks

JIANG Yibo, SHENG Shanghao

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

As a research hotspot in Visual Sensor Networks(VSNs),k-coverage problem has aroused general attention of many researchers. Aiming at the problem of moving targetsk-coverage problem in visual sensor networks, we propose a new target coverage probability evaluation model for non-uniform motion, which consider all the possible locations of every target at the next moment and the motion behavior of non-uniform motion objects by using probabilistic prediction theory. This method can increase the probability ofk-coverage. A new predictive distributedk-covering optimization algorithm is proposed. Sensor nodes exchange coverage information and make decisions in communication range. Finally, through a series of simulation experiments, the experimental results verify the effectiveness and feasibility of the algorithm and model.

visual sensor networks; moving targets;k-coverage; probability mode

2017-02-15

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402415)

蔣一波(1982—)，男，浙江杭州人，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)控制與管理、無(wú)線傳感網(wǎng)絡(luò)監(jiān)控系統(tǒng)等，E-mail：jyb106@zjut.edu.cn.

TP393

A

1006-4303(2017)06-0615-06

(責(zé)任編輯：陳石平)