郭新明，蔡軍偉

1.咸陽師范學院 計算機學院，陜西 咸陽 712000

2.寧波工程學院 理學院，浙江 寧波 315211

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSN）是由具有感知、存儲、處理和傳輸信息功能的大量無線傳感器節(jié)點構(gòu)成的自組織網(wǎng)絡(luò)，是物聯(lián)網(wǎng)技術(shù)的核心與基礎(chǔ)。覆蓋問題對WSN 至關(guān)重要，它將直接影響網(wǎng)絡(luò)對敏感區(qū)域的感知質(zhì)量[1]。WSN 覆蓋問題大致可分為兩個研究方向：一是覆蓋優(yōu)化，即用盡可能少的傳感器實現(xiàn)WSN 監(jiān)測區(qū)域的覆蓋要求，同時延長了網(wǎng)絡(luò)的生命周期[2-5]；二是漏洞修補，當WSN監(jiān)測區(qū)域的覆蓋質(zhì)量不滿足要求時，調(diào)配傳感器節(jié)點使網(wǎng)絡(luò)的覆蓋質(zhì)量達標[6-8]。隨著攝像技術(shù)的不斷進步，將攝像裝置作為無線節(jié)點的數(shù)據(jù)采集端形成的無線視覺傳感器網(wǎng)絡(luò)（wireless visual sensor networks，WVSN）能顯著提高WSN數(shù)據(jù)感知的種類和質(zhì)量，因此WVSN 常常被應用到野外監(jiān)控、安保等有圖像需求的監(jiān)測環(huán)境中[9]。在一些特殊應用環(huán)境，如車輛違章甄別、嫌疑人追蹤等場景下，監(jiān)測者更關(guān)注移動對象的正面圖像。針對這一問題，Wang 等人首次給出了WVSN 全視角覆蓋的定義，并提出了一種WVSN全視角覆蓋的判定方法以及隨機均勻部署條件下WVSN全視角覆蓋的充分條件[10]。柵欄覆蓋是WSN覆蓋技術(shù)的重要組成部分，主要用于監(jiān)測穿越WSN覆蓋區(qū)域的入侵行為[11]。Wang 等人又將強、弱柵欄覆蓋技術(shù)引入到WVSN 中，為WVSN 的非法入侵行為檢測提供了一種更加高效的技術(shù)手段[12]。

在WVSN 中，多個視覺傳感器聯(lián)合構(gòu)成的全視角覆蓋區(qū)域是一個不規(guī)則的凸多邊形[10]，這大大增加了WVSN 全視角柵欄覆蓋的研究難度。為了減小WVSN 全視角柵欄覆蓋的構(gòu)建難度，一些學者使用網(wǎng)格劃分方法將WVSN覆蓋區(qū)域劃分為等大小的規(guī)則網(wǎng)格，進而實現(xiàn)WVSN 全視角柵欄的構(gòu)建[13-15]；還有一些學者將WVSN 覆蓋區(qū)進行離散化處理，形成若干不相交的子區(qū)域，然后將這些不相交的子區(qū)域轉(zhuǎn)換為加權(quán)有向圖，并在此基礎(chǔ)上實現(xiàn)WVSN 全視角柵欄覆蓋問題的求解[16]。針對WVSN 入侵檢測圖像捕獲柵欄的改進問題，Gao 等人首次提出了構(gòu)建WVSN全視角弱柵欄的W-GraProj算法，該算法大大減少了構(gòu)建柵欄的傳感器數(shù)量，延長了網(wǎng)絡(luò)的生命周期，卻未考慮圖像寬度的因素，因此柵欄仍存在入侵檢測失效的可能[17]。Cheng 等人為了提高WVSN的監(jiān)測質(zhì)量，要求構(gòu)建的WVSN柵欄必須具有β寬度的圖像質(zhì)量要求（βquality of monitoring，β-QoM），確保入侵者的關(guān)鍵圖像能被清晰捕獲[18-19]，然而構(gòu)建的WVSN柵欄均是強柵欄，沒有涉及弱柵欄覆蓋，因此節(jié)點消耗較大，網(wǎng)絡(luò)生命周期縮短。

在一些特殊的場景中，移動目標的軌跡為直線或近似直線，如公路上行駛的汽車、沿筆直通道移動的人群等，WVSN 只需構(gòu)建具有β-QoM 的全視角弱柵欄覆蓋即可有效捕獲入侵者的關(guān)鍵圖像。針對WVSN 捕獲直線軌跡入侵者圖像精準度不足的問題，本文提出了一種覆蓋面積優(yōu)先的全視角弱柵欄β-QoM 增強構(gòu)建算法（coverage priority full-view weak barrierβ-QoM enhancement construction algorithm，CPFWBβEC），用以構(gòu)建具有β-QoM 的全視角弱柵欄，從而提高WVSN 捕獲直線入侵者關(guān)鍵圖像的質(zhì)量。具體來說，本文主要貢獻如下：

（1）對視覺傳感器的感知模型按照弱柵欄和β-QoM 的要求進行改造，并將其縮放成一個規(guī)則的矩形模型；

（2）證明了WVSN 最優(yōu)全視角弱柵欄β-QoM 增強覆蓋問題是NP-hard的；

（3）基于傳感器覆蓋面積優(yōu)先的貪心思想，提出了一個WVSN入侵檢測全視角弱柵欄β-QoM增強構(gòu)建的啟發(fā)式算法。

1 問題描述及網(wǎng)絡(luò)模型

1.1 問題描述

傳統(tǒng)的WVSN主要用來捕獲非法穿越其覆蓋區(qū)域的入侵者的圖像信息，但對獲取圖像的寬度沒有任何要求，這可能導致WVSN 的入侵檢測結(jié)果失效。如圖1所示，非法入侵者沿虛線所示直線通道穿越WVSN 的覆蓋區(qū)，粗實線箭頭表示入侵者的正面朝向（即關(guān)鍵圖像朝向），（a）圖中每個傳感器對入侵者的覆蓋寬度均大于β，因此正面圖像捕獲成功，而（b）圖中傳感器s1對入侵者的覆蓋寬度w1＜β，導致正面圖像捕獲失敗。

圖1 WVSN中直線入侵行為檢測示意圖Fig.1 Linear intrusion behavior detection in WVSN

研究發(fā)現(xiàn)，穿越WVSN 覆蓋區(qū)域的入侵者在不了解視覺傳感器部署細節(jié)的情況下，為了快速通過監(jiān)測區(qū)，一般會沿直線路徑進行穿越；另外在一些特殊場景中，入侵者只能沿直線路徑移動。本文假設(shè)入侵者的移動軌跡均是垂直于監(jiān)測區(qū)域邊界的直線路徑，主要研究如何使用盡可能少的視覺傳感器構(gòu)建入侵者正面圖像的捕獲柵欄。

定義1（WVSN全視角弱柵欄覆蓋） 在覆蓋區(qū)域為帶狀矩形的WVSN 中，如果入侵者以固定的正面朝向沿任意垂直于矩形監(jiān)測區(qū)長邊的直線路徑穿越WVSN 時，至少有一個視覺傳感器能捕獲到入侵者清晰的正面圖像，則稱該WVSN 是全視角弱柵欄覆蓋的。

1.2 WVSN網(wǎng)絡(luò)模型

為了便于研究WVSN 全視角弱柵欄覆蓋問題，本文給出WVSN的網(wǎng)絡(luò)模型。假設(shè)WVSN的覆蓋區(qū)是一個L×W的帶狀矩形區(qū)域（L?W），該區(qū)域內(nèi)隨機均勻部署若干同構(gòu)的視覺傳感器，且一旦部署，所有傳感器的位置和朝向均不發(fā)生改變。傳感器的視覺感知區(qū)域是一個夾角為γ感知半徑為r的扇形區(qū)域，其通信半徑R≥2r，每個傳感器S可以通過其內(nèi)置定位裝置獲得自己的位置坐標(x,y)和視覺采樣方向，如圖2所示。

圖2 無線視覺傳感器感知模型Fig.2 Sensing model of wireless visual sensor

定義2（有效捕獲） 為了保證視覺傳感器能夠捕獲到監(jiān)測對象的正面圖像，要求監(jiān)測對象P進入視覺傳感器S的覆蓋范圍后其正面朝向和P到S的連線方向的夾角α應該不大于一個閾值θ（θ稱為有效視角，θ∈[0,π/2)），則稱監(jiān)測對象P被視覺傳感器S有效捕獲[12]，如圖3所示。

圖3 視覺傳感器全視角覆蓋示意圖Fig.3 Full-view coverage diagram of visual sensor

定義3（有效朝向集） 在移動目標沿某穿越路徑穿越一個視覺傳感器感知區(qū)域的過程中，該視覺傳感器能有效捕獲到移動目標所有可能出現(xiàn)的正面朝向的集合，稱為該視覺傳感器在這個穿越路徑上的有效朝向集。

由圖4可知，穿越同一視覺傳感器的不同路徑的有效朝向集也不同，除非它們都穿越了視覺傳感器扇形感知區(qū)域的兩條邊。

定義4（β-QoM有效捕獲區(qū)） 一個視覺傳感器的扇形感知區(qū)在所有和其相交線段長度大于等于β且垂直于WVSN監(jiān)測區(qū)域長邊的直線穿越路徑上的有效朝向集拼接而成的連續(xù)區(qū)域，稱為該視覺傳感器的β-QoM有效捕獲區(qū)，其中β稱為有效圖像寬度。

從視覺傳感器扇形感知區(qū)與穿越路徑相交的幾何關(guān)系上看，其β-QoM有效捕獲區(qū)可分為四種類型，如圖5 所示。其中X軸與WVSN 監(jiān)測區(qū)域長邊平行，X軸和其上方Y(jié)軸構(gòu)成的直角坐標系用來描述傳感器的大小和方位；X軸和其下方Y(jié)軸構(gòu)成的直角坐標系用來描述對應傳感器的β-QoM有效捕獲區(qū)（粗實線圍成的封閉區(qū)域）。圖5（d）表示的傳感器β-QoM 有效捕獲區(qū)仍是一個封閉區(qū)域，只是由于有效朝向集的取值必須在[0,2π)內(nèi)，導致從圖像上看是兩個獨立區(qū)域。

圖5 視覺傳感器β-QoM有效捕獲區(qū)Fig.5 β-QoM effective capture area of visual sensor

2 WVSN全視角弱柵欄β-QoM增強覆蓋理論

2.1 WVSN 全視角弱柵欄β-QoM 增強覆蓋模型

由定義1可知，入侵者在穿越WVSN覆蓋區(qū)域時的正面朝向為[0,2π)內(nèi)的某一確定值，若要在WVSN中實現(xiàn)WVSN 全視角弱柵欄的β-QoM 增強覆蓋，則WVSN 中與任一垂直穿越路徑相交線段長度大于β的所有傳感器在該穿越路徑上的有效朝向集必須覆蓋[0,2π)。

如圖6所示，入侵者沿路徑I以某固定朝向穿越了WVSN 中的三個視覺傳感器S1、S2和S3，路徑I與三個視覺傳感器的相交線段長度均大于β，由于S1、S2和S3在路徑I上的有效朝向集能完全覆蓋[0,2π)，那么入侵者的正面圖像就一定能被S1、S2和S3中至少一個有效捕獲。因此，穿越路徑上的全視角弱柵欄β-QoM增強覆蓋并不要求柵欄上視覺傳感器的感知區(qū)域在幾何上彼此相交，只要它們在穿越路徑上的有效朝向集的并集為[0,2π)即可。

圖6 穿越路徑上的全視角弱柵欄β-QoM增強覆蓋Fig.6 Full-view weak barrier β-QoM enhanced coverage on crossing path

WVSN的全視角弱柵欄β-QoM增強覆蓋要求在任一條垂直于監(jiān)測區(qū)長邊的直線穿越路徑上的有效朝向集完全覆蓋[0,2π)，但由于WVSN 監(jiān)測區(qū)中的穿越路徑有無窮多條，逐一判斷顯然是不現(xiàn)實的，因此需要對WVSN帶狀矩形監(jiān)測區(qū)域中的全視角弱柵欄β-QoM增強覆蓋問題進行等價轉(zhuǎn)換?，F(xiàn)將監(jiān)測區(qū)域轉(zhuǎn)換為長為L寬為2π 的矩形區(qū)域R，視覺傳感器的β-QoM 有效捕獲區(qū)轉(zhuǎn)換為圖5 中粗實線圍成的封閉區(qū)域，如果WVSN 中所有傳感器的β-QoM 有效捕獲區(qū)能完全覆蓋R，那么該WVSN 一定是全視角弱柵欄β-QoM 增強覆蓋的。由于視覺傳感器的β-QoM有效捕獲區(qū)都是不規(guī)則的封閉圖形，WVSN 全視角弱柵欄β-QoM增強覆蓋的判定也非易事。

定義5（最大捕獲矩形） 將視覺傳感器β-QoM有效捕獲區(qū)最大內(nèi)嵌矩形以外的區(qū)域剪除，剩余的矩形區(qū)域稱為該視覺傳感器的最大捕獲矩形。圖5 中的陰影矩形分別表示相應視覺傳感器的最大捕獲矩形。

定理1如果一個WVSN監(jiān)測區(qū)域中所有視覺傳感器的最大捕獲矩形能夠完全覆蓋監(jiān)測區(qū)域R，那么該監(jiān)測區(qū)域是全視角弱柵欄β-QoM增強覆蓋的。

證明WVSN 監(jiān)控區(qū)域R中的無線視覺傳感器集合為S={S1,S2,…,Sn}，與S對應的視覺傳感器β-QoM有效捕獲區(qū)的集合A={A1,A2,…,An}，A對應的最大捕獲矩形集合為C={C1,C2,…,Cn}。

若WVSN 是全視角弱柵欄β-QoM 增強覆蓋的，那么將WVSN中所有視覺傳感器的β-QoM有效捕獲區(qū)收縮為最大捕獲矩形的網(wǎng)絡(luò)模型如圖7所示，其中粗線框表示R，所有陰影矩形框表示視覺傳感器的最大捕獲矩形。

圖7 WVSN全視角弱柵欄β-QoM增強覆蓋示意圖Fig.7 Full-view weak barrier β-QoM enhanced coverage of WVSN

2.2 WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋問題分析

定義6（WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋） 若WVSN視覺傳感器集合S的一個子集Z形成了覆蓋區(qū)域的一個全視角弱柵欄β-QoM 增強覆蓋，且不存在S的其他全視角弱柵欄β-QoM增強覆蓋子集Z′，使得|Z′|＜|Z|，則稱集合Z是WVSN的一個最優(yōu)全視角弱柵欄β-QoM增強覆蓋。

為充分研究WVSN的最優(yōu)全視角弱柵欄β-QoM增強覆蓋問題，現(xiàn)將WVSN 模型作如下離散化處理。如圖8所示，將WVSN中每個視覺傳感器表示成其最大捕獲矩形（虛線陰影矩形），將WVSN 的監(jiān)測區(qū)域R（粗實線外框）劃分成p行q列的m(m=p×q)個網(wǎng)格（細實線網(wǎng)格），即G={g1,g2,…,gm}，每個網(wǎng)格的長為L/q，寬為2π/p，WVSN中部署了n個視覺傳感器，即S={S1,S2,…,Sn}。

圖8 WVSN覆蓋區(qū)域網(wǎng)格劃分示意圖Fig.8 Grid division of WVSN coverage area

定義7（覆蓋網(wǎng)格集） 在WVSN 的監(jiān)測區(qū)域R中，視覺傳感器最大捕獲矩形能完整覆蓋的所有網(wǎng)格，稱為該視覺傳感器的覆蓋網(wǎng)格集。如圖9 所示，該視覺傳感器的覆蓋網(wǎng)格集C={g1,g2,g3,g5,g6,g7}。

圖9 視覺傳感器覆蓋網(wǎng)格集Fig.9 Coverage grid set of visual sensor

定理2WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋問題是NP-hard的。

證明令全集U={g1,g2,…,gm}，由定義7 可知WVSN中任一個視覺傳感器si的覆蓋網(wǎng)格集是U的一個子集。

根據(jù)定義6可知，如果WVSN傳感器集合S的一個子集S′是監(jiān)測區(qū)域的最優(yōu)全視角弱柵欄β-QoM增強覆蓋，那么，其中z=|S′|，sk∈S′。由此可見，WVSN 最優(yōu)全視角弱柵欄β-QoM 增強覆蓋問題其實是一個集合覆蓋問題，由于集合覆蓋問題是NPhard的[20]，WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋問題也是NP-hard的，證畢。

3 全視角弱柵欄β-QoM增強構(gòu)建算法設(shè)計

WVSN的最優(yōu)全視角弱柵欄β-QoM增強覆蓋是個NP難問題，因而可給該問題設(shè)計多項式時間的啟發(fā)式算法，從而獲得其次優(yōu)解。在一些特殊應用環(huán)境中，人工部署WVSN 是不現(xiàn)實的，如敵情監(jiān)測、野生動物保護等，因此常采用飛機播撒或其他方式隨機部署WVSN，且視覺傳感器部署后既不移動也不旋轉(zhuǎn)[21]。由于WVSN 節(jié)點部署的隨機性特征，只有節(jié)點部署到一定數(shù)量，方可在WVSN 中實現(xiàn)全視角弱柵欄β-QoM 增強覆蓋，因此本文假設(shè)WVSN 中節(jié)點數(shù)量應滿足全視角弱柵欄β-QoM 增強覆蓋的要求。然而這種工作方式網(wǎng)絡(luò)能耗大，且容易造成通信擁塞。較為理想的方案是休眠部分冗余節(jié)點，使構(gòu)建全視角弱柵欄β-QoM增強覆蓋的無線視覺傳感器盡可能少，并根據(jù)需要進行節(jié)點輪換，使網(wǎng)絡(luò)的生命周期盡可能延長。

基于上述分析，本章提出覆蓋面積優(yōu)先的貪心算法，以構(gòu)建WVSN 的β-QoM 增強型全視角弱柵欄覆蓋。

3.1 CPFWBβEC算法的設(shè)計思想

定義8（有效覆蓋網(wǎng)格） 視覺傳感器最大捕獲矩形能完整覆蓋狀態(tài)為false 的所有網(wǎng)格，稱為該視覺傳感器的有效覆蓋網(wǎng)格（網(wǎng)格狀態(tài)為true，表示該網(wǎng)格已被弱柵欄上其他視覺傳感器最大捕獲矩形覆蓋，反之沒有覆蓋），這里用effective coverage grids的縮寫形式ECG(Si) 表示傳感器Si的有效覆蓋網(wǎng)格集。如圖10 所示，視覺傳感器Sj的有效覆蓋網(wǎng)格數(shù)|ECG(Sj)|=4。

圖10 視覺傳感器的有效覆蓋網(wǎng)格Fig.10 Effective coverage grids of visual sensor

覆蓋面積優(yōu)先的全視角弱柵欄β-QoM增強構(gòu)建算法應使用盡可能少的無線視覺傳感器實現(xiàn)WVSN的全視角弱柵欄β-QoM增強覆蓋。CPFWBβEC每輪次選用覆蓋面積最大的視覺傳感器，這里用有效覆蓋網(wǎng)格數(shù)近似表示視覺傳感器有效覆蓋面積的大小，一旦被選用的傳感器集合滿足全視角弱柵欄覆蓋的要求，則其余節(jié)點進入休眠狀態(tài)。在監(jiān)測區(qū)域不變的情況下，視覺傳感器的有效覆蓋面積越大，則完全覆蓋監(jiān)測區(qū)域R的傳感器的數(shù)量就越少，這便是CPFWBβEC算法的思想來源。

CPFWBβEC算法用傳感器有效覆蓋網(wǎng)格數(shù)代替其有效覆蓋面積，因此面積優(yōu)先就等同于有效覆蓋網(wǎng)格優(yōu)先。該算法構(gòu)建的覆蓋WVSN的β-QoM增強型全視角弱柵欄節(jié)點集最多包含k(ln(m/k)+1)個節(jié)點（m表示網(wǎng)格數(shù)，k為WVSN 全視角弱柵欄β-QoM增強覆蓋最優(yōu)解中傳感器節(jié)點的個數(shù)）[22]，且CPFWBβEC算法的近似比是O(lnB)(B=max(|ECG(Si)|，i=1,2,…,n))[22]?？梢?，本文提出的CPFWBβEC 算法能在WVSN中有效構(gòu)建β-QoM增強型全視角弱柵欄覆蓋。

3.2 CPFWBβEC算法描述

根據(jù)覆蓋面積優(yōu)先的貪心思想，本文設(shè)計了求解WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋的啟發(fā)式算法CPFWBβEC，算法的偽代碼如下所示。

3.3 算法的時間復雜度

CPFWBβEC算法的時耗主要發(fā)生在搜索最大有效覆蓋網(wǎng)格的視覺傳感器環(huán)節(jié)（偽代碼中第19～29行），主要包含遍歷視覺傳感器節(jié)點和遍歷視覺傳感器有效覆蓋網(wǎng)格兩重循環(huán)。遍歷視覺傳感器的循環(huán)次數(shù)為節(jié)點個數(shù)n，遍歷視覺傳感器有效覆蓋網(wǎng)格的循環(huán)次數(shù)則為|ECG(Si)|，而|ECG(Si)|擁有上限max(|ECG(Si)|)。這里令ncg=max(|ECG(Si)|)，因此算法CPFWBβEC 的時間復雜度為O(ncgn)，由于ncg?n，算法CPFWBβEC 的時間復雜度遠小于W-GraProj 的時間復雜度O(n2)，但與算法D-eTriB 的時間復雜度O(n′n)相當，其中n′表示所有傳感器的鄰居傳感器的平均數(shù)。這點在仿真實驗中也得到了印證，因此在節(jié)點部署密集且實時性較高的環(huán)境中，若要實現(xiàn)高質(zhì)量的全視角弱柵欄覆蓋，算法CPFWBβEC 顯然要優(yōu)于W-GraProj和D-eTriB。

4 仿真實驗與分析

4.1 仿真實驗說明

本文使用Matlab2012a 對算法CPFWBβEC 進行仿真實驗，WVSN 監(jiān)測區(qū)內(nèi)的無線視覺傳感器采用隨機均勻部署，實驗數(shù)據(jù)是運行算法100次得到的平均值，并分別與文獻[17]中的W-GraProj 算法和文獻[19]中的D-eTriB算法進行了對比分析。實驗平臺的有關(guān)參數(shù)如表1所示。

表1 仿真實驗平臺的參數(shù)設(shè)置Table 1 Parameter setting of simulation platform

4.2 算法性能分析

由實驗數(shù)據(jù)可知，算法CPFWBβEC 的柵欄構(gòu)建成功率較高，分別比W-GraProj 和D-eTriB 大約高0.116 和0.340，且CPFWBβEC 比W-GraProj 和DeTriB 的適應性更強，同等條件下在W-GraProj 和DeTriB尚不能成功構(gòu)建柵欄時，CPFWBβEC能以較大概率成功構(gòu)建弱柵欄。在100%成功構(gòu)建柵欄的臨界點上，算法CPFWBβEC的覆蓋密度大約是W-GraProj的69.0%，是D-eTriB 的42.7%，可見在隨機部署的條件下，算法CPFWBβEC 構(gòu)建柵欄的可靠性更高，如圖11所示。

圖11 三種算法柵欄構(gòu)建成功率的比較Fig.11 Comparison of barrier construction success rate for three algorithms

在成功構(gòu)建WVSN 全視角弱柵欄的情況下，CPFWBβEC 構(gòu)建柵欄的節(jié)點數(shù)比W-GraProj 和DeTriB分別節(jié)省了大約35.5%和56.1%，且構(gòu)建全視角弱柵欄的平均節(jié)點數(shù)隨節(jié)點覆蓋密度的增加而逐漸下降，如圖12所示。針對不同的傳感半徑，實驗數(shù)據(jù)顯示CPFWBβEC算法全視角弱柵欄構(gòu)建的成功率隨視覺傳感器傳感半徑的增長而增高，構(gòu)建弱柵欄的平均節(jié)點數(shù)則隨之下降。由于視覺傳感器半徑的增大，其傳感范圍也會隨之擴大，若WVSN覆蓋區(qū)域面積不變，則在其上構(gòu)建全視角弱柵欄的可能性理應有所提高。

圖12 三種算法的柵欄構(gòu)建平均節(jié)點數(shù)比較Fig.12 Comparison of average node number of barrier construction for three algorithms

三種算法的性能對比如表2所示。

表2 算法性能對比Table 2 Comparison of algorithm performance

對于不同的有效圖像寬度β，CPFWBβEC算法的實驗效果如圖13和圖14所示。隨著有效圖像寬度β值的增加，全視角弱柵欄的平均構(gòu)建節(jié)點數(shù)也隨之增加，而構(gòu)建全視角弱柵欄的成功率反而下降，其主要原因是有效圖像寬度β值的增大，導致滿足構(gòu)建全視角弱柵欄的節(jié)點間距縮短，因此形成柵欄的平均節(jié)點數(shù)增加。而β值的增長，致使?jié)M足構(gòu)建全視角弱柵欄的節(jié)點序列減少，自然構(gòu)建的成功率會下降。

圖13 不同β值下CPFWBβEC算法弱柵欄構(gòu)建節(jié)點數(shù)Fig.13 Node number of weak barrier constructed by CPFWBβEC with different β

圖14 不同β值下CPFWBβEC算法弱柵欄構(gòu)建成功率Fig.14 Success rate of weak barrier constructed by CPFWBβEC with different β

5 結(jié)束語

為了進一步提高WVSN入侵檢測圖像的捕獲質(zhì)量，針對WVSN 中直線軌跡入侵者圖像捕獲柵欄的增強構(gòu)建問題，本文提出了一個覆蓋面積優(yōu)先的全視角弱柵欄β-QoM增強構(gòu)建算法CPFWBβEC。該算法將不規(guī)則的視覺傳感器有效捕獲區(qū)進行了規(guī)則化處理，降低了弱柵欄構(gòu)建的難度；在傳統(tǒng)弱柵欄覆蓋模型上增加了β寬度的圖像質(zhì)量要求，顯著提高了入侵檢測的效率；覆蓋面積優(yōu)先的貪心算法思想可以較快求得WVSN最優(yōu)全視角弱柵欄β-QoM增強覆蓋的近似解。大量仿真實驗顯示，算法CPFWBβEC 可以在隨機部署的WVSN中較為快速地構(gòu)建β-QoM增強型全視角弱柵欄，其全視角弱柵欄構(gòu)建的成功率比算法W-GraProj 和D-eTriB 分別高約0.116 和0.340，且構(gòu)建柵欄的平均節(jié)點數(shù)比算法W-GraProj和D-eTriB的效率分別提高了約35.5%和56.1%。算法CPFWBβEC的時間復雜度遠小于W-GraProj，但與D-eTriB相當，然而其柵欄的構(gòu)建成功率和構(gòu)成柵欄的平均節(jié)點數(shù)均遠遠優(yōu)于W-GraProj 和D-eTriB，致使在節(jié)點部署密集、實時性要求較高的WVSN中，算法CPFWBβEC不但提高了全視角弱柵欄β-QoM 增強構(gòu)建的效率，還使WVSN生命周期得到了進一步延長。

本文僅研究了隨機部署WVSN中β-QoM增強型全視角弱柵欄的覆蓋問題，研究內(nèi)容沒有考慮視覺傳感器的旋轉(zhuǎn)移動以及存在視覺障礙物干擾等因素，這將是下一步研究工作的主要內(nèi)容。