視頻傳感器網絡中移動目標k覆蓋優化算法

，

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

視頻傳感器網絡中移動目標k覆蓋優化算法

蔣一波，盛尚浩

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

k覆蓋問題作為視頻傳感器網絡中的一個研究熱點，引起了許多研究者的關注.針對視頻傳感器網絡中的移動目標k級覆蓋問題，結合概率預測思想，充分考慮非勻速移動目標的運動特性和下一時刻目標有可能達到的位置，建立了一種移動目標覆蓋概率評估模型，提高了k覆蓋的概率.同時，提出了新的基于預測的分布式k覆蓋優化算法，傳感器節點在通信范圍內交換覆蓋信息并進行決策.最后通過一系列仿真實驗，實驗結果驗證了該算法和模型的有效性和可行性.

視頻傳感器網絡；移動目標；k覆蓋；概率模型

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

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

1 移動目標k覆蓋問題

為了更好地闡述非勻速移動目標k覆蓋問題，在給出數學模型之前先提出如下假設:

1)視頻傳感器網絡中的傳感器節點都是同構的，即節點的各項參數都是相同的.

2)監測區域內的所有傳感器節點都是隨機投放，且投放之后位置固定.

3)傳感器節點可以有效地識別各個目標并獲取目標的運動信息，且目標自身帶有編號.

4)移動目標在整個運動過程中做變速運動，且移動目標之間不會相互干擾.

1.1 視頻傳感器模型

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

圖1 視頻傳感器節點感知模型Fig.1 Perception model of visual sensor node

1.2 問題分析與定義

目前用于目標跟蹤的預測方法主要有粒子群濾波、卡爾曼濾波等[11,15]，但是這些方法需要大量的數據迭代計算，且對節點的處理能力要求高.雖然這些技術更加精確，但是這些方法不適合應用于計算能力和資源有限的視頻傳感器節點.針對上述問題，采用概率預測思想來進行優化，在移動目標運動過程中提前分析其運動到下一個時刻有可能到達的位置，并給出覆蓋概率分布.

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

(1)

為了更加直觀的展示下一個時刻移動目標落點的概率分布，圖2為相同初始條件但加速度不同的情況下概率分布熱力對比圖.

圖2 移動目標落點概率分布對比圖Fig.2 Probability distribution of moving target positions

假設當前時刻為t，圖2(a)為移動目標在t時刻從原點(0,0)出發，以初速度v0=40,延x軸正方向運動，且加速度大小a0=20，加速度方向與y軸正方向一致；圖2(b)為移動目標在t時刻同樣從原點(0,0)出發，以初速度v0=40,延x軸正方向，且加速度大小a0=20，但加速度方向與y軸正方向呈30°夾角，經過Δt時間間隔后有可能到達的位置的概率分布.圖2中黑色水滴形區域為可能性較大的落點區域，即t+1時刻目標到達該區域的可能性更大，而周圍白色區域則表示t+1時刻目標到達該區域的可能性較小.

每個時刻，根據監測要求和容錯需求，移動目標至少被k個不同的視頻傳感器節點所覆蓋，結合上述覆蓋概率分布函數，筆者的研究目標旨在完成對所有目標的k覆蓋同時降低旋轉可能帶來的能耗損失.通過分析下一時刻移動目標有可能的運動軌跡，根據最優覆蓋效果調整節點的感知方向，可以盡可能地提高k覆蓋的質量，用盡可能小地旋轉能耗代價換取高質量的移動目標k覆蓋.

由此建立非線性優化模型為

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

(2)

(3)

在判斷是否達到k覆蓋要求時，采用四舍五入取整的計算方式，可以在一定程度上避免多個覆蓋概率較小的節點被選中.

2 基于預測的分布式覆蓋算法

針對上節所述的移動目標k覆蓋問題，由于該問題屬于NP完全問題，難以在多項式時間內解決.同時在監測區內采集全局信息存在一定困難，因此需要尋求一種分布式次優解算法[16-19].本節提出了一種基于預測的移動目標k覆蓋動態優化算法KPNMOA，充分考慮非勻速移動目標每一個時刻所有可能到達的位置，模擬了所有落點的概率值，在通信范圍內與鄰居節點交換覆蓋信息，依次作出決策.

KPNMOA算法描述：從移動目標進入區域開始，每個時刻，傳感器節點Si以當前感知方向角為基準，計算出在可旋轉范圍內的最優覆蓋效果，即能夠達到的最大覆蓋概率預測值Pmax為

(4)

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

Input：每個節點的坐標位置和各自的感知方向

Output：每個節點的感知方向角

1)t←0;

2) 獲取節點位置P;

3) 獲取通信范圍內鄰居節點集合φ;

4) Status←false;//標志位

5) while(true)

6)t←t+1;

7) 計算節點Si可以覆蓋且未被k覆蓋的目標集合φj

8) 計算移動目標落點分布概率

9) sumj=0;

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

11) 計算節點Si達到最大覆蓋效果值時的Δθi和Pmax;

12) 廣播并接受覆蓋消息數據包

13) 按照fij值大小降序排序，如果一致按|Δθi|值從小到大排序;

14) 選擇覆蓋效果最好的節點Sa;

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

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

目標Tj達到k覆蓋;

17) if(Sa==Si){

18) Status=true;

19)θ+=Δθi;//旋轉節點

}

20) sleep(Δt);

21) end while;

22) end while;

在保證數據可靠傳輸的情況下，KPNMOA算法就能在有限時間內終止.算法將覆蓋概率函數作為指導，并將加速度納入函數可以確保大概率評估更加合理，提前作出合理的旋轉決策，更好地實現了實時移動目標k覆蓋.

3 算法仿真

為了更好地驗證KPNMOA算法的可行性和有效性,基于Net Framework開發了仿真平臺進行模擬實驗研究，給出不同體系下的各種性能對比.在500×500的監測區域內隨機投放下N個視頻傳感器節點進行覆蓋工作，每個視頻傳感器節點規格相同，仿真參數值如表1所示.

表1 傳感器節點參數Table 1 Parameters of sensor node

圖3展示了當監測區域內出現5個移動目標時的仿真實驗過程，每個移動目標的初始速度為10 m/s，且加速度a∈[-5,5].圖3記錄了KPNMOA算法運行不同時間步長后視頻傳感器網絡中移動目標覆蓋情況以及每個移動目標的運動軌跡.

將KPNMOA算法與其他三種算法Continue(節點持續旋轉)，DPGKCA[9]算法,MPKCDA[15]算法進行比較，考察了在傳感器節點數量，感知半徑發生等關鍵參數變化時對覆蓋質量產生的影響.首先給出覆蓋質量函數為

(5)

式中：t為時間步長；k為實際k覆蓋大小,k覆蓋持續時間是評價覆蓋質量的重要因素，并采用平均值來進行比較.圖4比較了不同傳感器節點規模時各算法的覆蓋質量，其中節點數量從50～250依次遞增20.由圖4可知：覆蓋質量Q隨著節點數量N的增大而增大，顯然網絡中部署更多節點可以延長k覆蓋的時間，同時當節點數量相同時，Continue的效果是最不理想的，KPNMOA隨著傳感器節點數量增加性能提高優于MPKCDA和DPGKCA.

圖4 不同網絡規模對覆蓋質量的影響Fig.4 Effect of networks size on the coverage quality

圖5為不同傳感器節點感知半徑時四種算法的覆蓋質量的對比情況，半徑以10為步長從10～90依次遞增.覆蓋質量Q隨節點感知半徑R的增加呈現指數級增長，因為伴隨感知半徑的增加,節點的感知范圍快速變大，k覆蓋的概率也隨之提高.較其他三種算法,隨著半徑的增加KPNMOA的優勢越來越明顯.

圖6顯示了四種算法在感知角度大小變化時的覆蓋質量.當感知角度增大時，可覆蓋到的目標數量也會增多，因此覆蓋質量Q隨節點感知角度α的增長呈線性增長，KPNMOA的增長幅度明顯高于其他三種算法.

圖5 傳感器節點感知半徑對覆蓋質量的影響Fig.5 Effect of sensor node perception radius on the coverage quality

圖7給出了四種算法在不同k覆蓋要求的情況下的性能比較.Maxk代表了監測區域的安全需求等級，Maxk值越大則每個時刻需要更多的視頻傳感器節點來跟蹤移動目標，該監測區域的安全需求越高.由圖7可知：Continue和DPGKCA的覆蓋質量不斷下降，而MPKCDA和KPNMOA呈先增加后下降變化，其中KPNMOA對k值變化的適應性更強.

圖6 傳感器節點感知角度對覆蓋質量的影響Fig.6 Effect of sensor node perception angle on the coverage quality

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

4 結 論

針對視頻傳感器網絡中的移動目標k覆蓋問題，首先建立一個覆蓋概率評估模型，分析非勻速移動目標的運動軌跡，將加速度納入概率模型使計算下一個時刻的覆蓋概率更加合理，然后設計了一種基于預測的分布式k覆蓋優化算法，提高了移動目標的k覆蓋概率和覆蓋時長.仿真結果顯示在不同網絡規模、感知半徑、感知角度和覆蓋要求時KPNMOA均具有更好的性能表現.在下一步工作中，將根據實際環境考慮加入障礙物后的移動目標k覆蓋優化問題，并對算法進行改進降低時間復雜度.

[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] 周曉,李杰,邊裕挺.基于無線傳感網絡的環境溫度監測系統設計[J].浙江工業大學學報,2013,41(4):440-443

[3] 劉唐，彭艦，楊進.異構延遲容忍移動傳感器網絡中基于轉發概率的數據傳輸[J].軟件學報，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] 陶丹，馬華東.有向傳感器網絡覆蓋控制算法[J].軟件學報，2011，22(10):2317-2334.

[9] 蔣一波,陳瓊,王萬良，等.視頻傳感器網絡中基于移動目標軌跡預測的k級覆蓋增強算法[J].傳感技術學報,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] 任靜,熊慶宇,石為人.一種基于預測策略的目標跟蹤算法研究[J].傳感技術學報,2011,24(10):1496-1500.

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

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

[15] 俞立,王銘,董齊芬，等.基于無線傳感網的目標跟蹤算法及實驗系統設計[J].浙江工業大學學報,2012,40(6):649-652

[16] 蔣一波,陳瓊,王萬良,等.視頻傳感器網絡中多路徑k級覆蓋動態優化算法[J].儀器儀表學報,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] 張文安,薛東國,俞立.面向節能的無線多傳感器H∞融合估計[J].浙江工業大學學報,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

國家自然科學基金資助項目(61402415)

蔣一波(1982—)，男，浙江杭州人，副教授，研究方向為計算機網絡控制與管理、無線傳感網絡監控系統等，E-mail：jyb106@zjut.edu.cn.

TP393

A

1006-4303(2017)06-0615-06

(責任編輯：陳石平)