基于圖分級的水下有向傳感器網絡柵欄覆蓋策略

常 娟 申曉紅 王海燕 趙紅言 李祥祥

①(西北工業大學航海學院 西安 710072)

②(空軍工程大學基礎部 西安 710051)

1 引言

近年來，隨著我國海洋事業的發展，對水下移動目標，特別是對離陸地較近的淺海海域內移動目標的入侵檢測已經成為我國水聲傳感器網絡技術發展的重點之一。決定檢測水平的基本要素就是網絡覆蓋的質量，水下傳感器網絡的覆蓋問題已經開始得到廣泛關注[1-5]。在不同的應用場景中，需要有不同類型的覆蓋，環境感知和監測網絡的覆蓋主要分為3種：用于監測目標點的目標覆蓋，用于監測所有監測區域的面覆蓋和用于入侵檢測的柵欄覆蓋[6,7]。目前，很多有關水下入侵檢測的柵欄覆蓋的研究都是基于各向同性的傳感器進行的，這種傳感器的感知區域通常被建模為圓盤模型。只要入侵目標在感知區域內就會被檢測到。但在入侵檢測中，用于探測的傳感器往往是有向感知的。與全向傳感器不同，有向傳感器的感知范圍不僅取決于傳感器的感知半徑，還取決于它的感知方向角和偏移角，因此有向傳感器網絡的柵欄覆蓋問題復雜度更高。

關于有向傳感器網絡柵欄覆蓋問題，大量成果利用盡可能少的移動節點進行方向角旋轉，旋轉角度盡可能小來對柵欄進行增強。文獻[8]通過一個新的全視角覆蓋模型，將部署區域劃分為若干連接的網格并提出了基于網格的部署策略為每個網格部署傳感器。文獻[9]利用了虛擬力和虛擬邊界轉距的概念提出了柵欄增強部署算法解決了可移動、旋轉的異構傳感器網絡的柵欄增強問題。文獻[10]首次提出了可行方向范圍的概念，并提出一種在可行性范圍內選擇傳感器方向的快速算法，通過調整節點的方向角來填補柵欄空洞。文獻[11]將有向傳感器網絡目標柵欄覆蓋問題轉化為更簡單的優化問題，采用一種分布式粒子群算法利用調節節點的方向角來填補空洞，對柵欄進行優化。文獻[12]提出了一種新的基于網絡區域的聚類算法來減少信息交換，再提出了一種啟發式算法利用最小移動距離來彌補漏洞修復柵欄。也有學者直接根據有向傳感器節點的最小旋轉角度來構建柵欄。文獻[13]研究異構視頻傳感器網絡全視角覆蓋估計問題，為消除邊界效應，提出了擴展監測區域及最大探測區域的概論，并推導出目標全視角覆蓋估計模型，采用該模型減小了平均絕對覆蓋誤差。文獻[14]首次定義了安全單元并設計了查找安全單元和柵欄空隙的算法，提高了柵欄覆蓋率。以上算法僅討論了如何利用移動傳感器來構建柵欄或對柵欄漏洞進行彌補，未深入討論如何對靜態傳感器網絡進行首次柵欄覆蓋問題。由于水下傳感器網絡能量十分有限，在水下傳感器網絡柵欄覆蓋中，通常希望在首次柵欄構建中就能夠只采用靜態節點成功構建柵欄，以減少二次柵欄構建帶來的傳感器資源浪費。

文獻[15]提出了一種分布式擴散算法，在有向傳感器網絡柵欄的首次構建階段采用了Dijkstra算法對局部網絡的靜態節點進行搜索選擇，再利用移動節點進行補充來構成完整的柵欄。該算法解決了采用盡可能少的移動節點實現可旋轉攝像機傳感器的全視圖柵欄覆蓋問題。該算法中進行局部柵欄首次構建所采用Dijkstra算法，時間復雜度較高，構建柵欄所需的節點數也較多。但是為節約水聲傳感器資源，通常采用盡可能少的靜態有向傳感器構建柵欄。顯然該算法并不適用于水下傳感器網絡的首次柵欄覆蓋。

文獻[16]首次在網絡覆蓋中提出了分級圖的概念，通過對構建的覆蓋圖進行分級使傳感器節點之間的拓撲關系更加清晰，在此基礎上構建的柵欄所用的節點數較少。該算法研究了采用盡可能少的節點進行柵欄的首次構建問題，但主要針對靜態全向水聲傳感器網絡進行首次柵欄覆蓋，不適用于靜態有向水聲傳感器網絡。全向傳感器網絡構建覆蓋圖時傳感器之間的位置關系簡單，只需根據傳感器之間的距離和感知半徑的關系來判斷兩個有向傳感器的感知區域是否相交，進而構建網絡覆蓋圖。而有向傳感器之間位置關系判斷比較復雜，要綜合考慮傳感器之間的距離和感知半徑的關系，傳感器方向角之間的關系和偏移角的大小。文獻[17]從這兩方面討論了強柵欄覆蓋的條件，并基于鄰接矩陣給出了強柵欄覆蓋算法，但分析不夠全面，且該覆蓋算法所需的節點數較多，且要求數據存儲量較大。

在水聲傳感器網絡覆蓋中，通常認為海域深度小于傳感器節點感知半徑2 倍的海域為淺海海域，此時用于淺海入侵目標檢測所用的水聲傳感器節點為2維分布。本文主要研究應用于淺海入侵目標檢測的2維水下有向傳感器網絡的首次柵欄覆蓋問題。本文首先研究有向傳感器多種位置下建立連接關系的條件以便于建立有向傳感器網絡覆蓋圖，并在圖分級的基礎上研究了靜態節點隨機部署前提下，采用盡可能少的節點實現首次柵欄構建，以節約水下傳感器資源。

2 傳感器感知模型

有向傳感器的感知范圍為一個扇形區域，可表示為：〈s(x,y),Rs,α,β〉[3]，如圖1所示，其中s(x,y)為傳感器s的位置坐標，Rs為感知半徑，α(0≤α ≤2π)為X軸正方向與扇形感知區域中心線的夾角，即方向角，β(0≤β ＜π)為扇形感知區域兩側的邊界相對于其中心線的偏移角。當β= π時，感知模型為0/1布爾圓盤模型，因此0/1布爾圓盤模型是有向感知模型的特殊情況。

圖1 有向感知模型

圖1所示有向感知模型的數學表達式為

其中，d(s,z)為空間某一點z與傳感器節點s之間的歐氏距離，as(s,z)為它們之間的夾角。

3 問題描述

本文主要研究以采用盡可能少的節點為目標，構建水下有向傳感器網絡柵欄的問題，為便于下文討論，對研究的前提條件做一下假設：

(1)水聲傳感器網絡由N個靜止的有向傳感器s1,s2,...,sN被隨機分布在一個2維矩形區域A2-dim=[0, L] × [0, W]，其中L和W分別表示該矩形區域的長和寬，且各傳感器是獨立同分布的，如圖2所示。

圖2 隨機分布下的有向傳感器網絡

(2)有向傳感器網絡中的每一個有向傳感器都能夠獲取自己的位置信息，并能夠通過一些定位算法得到與其他傳感器之間的相對位置；

(3)有向傳感器網絡內所有節點都是靜態的且同性質的，它們的感知半徑、位置坐標和偏移角都相等且保持不變；

(4)有向傳感器網絡始終保持連通性。

4 基于圖分級的有向傳感器網絡柵欄覆蓋策略

基于圖分級的有向傳感器柵欄覆蓋策略是基于覆蓋圖展開的[16]，在構建覆蓋圖的過程中需要各節點確定自己的感知區域與其每一個相鄰節點的感知區域是否相交，即判斷兩節點在覆蓋圖中是否連接。能否正確判斷兩個節點之間的連接關系是構建覆蓋圖和柵欄的關鍵。

4.1 兩個節點之間的連接判斷方法

柵欄覆蓋分為弱柵欄覆蓋和強柵欄覆蓋兩種，定義如下：

定義1通過傳感器網絡覆蓋，使沿任意垂直于帶狀區域的路徑穿越帶狀區域的移動目標都能被傳感器網絡檢測到的覆蓋稱為弱柵欄覆蓋。在水聲傳感器網絡中，弱柵欄覆蓋主要針對機動性較弱的水下目標入侵進行檢測。

定義2通過傳感器網絡覆蓋，使沿任意路徑穿越帶狀區域的移動目標都能被傳感器網絡檢測到的覆蓋稱為強柵欄覆蓋。在水聲傳感器網絡中，強柵欄覆蓋主要針對機動性較強的水下目標入侵進行檢測。

與全向傳感器不同，有向傳感器的感知區域不僅受感知半徑的限制，還受其水平角和偏移角影響。因此兩個有向傳感器之間連接關系的判斷比較復雜。兩個傳感器感知區域相交的情況分為兩種：弱連接和強連接。如果一條柵欄中兩個相鄰節點滿足弱連接，則該柵欄是弱柵欄；如果一條柵欄中每兩個相鄰節點都滿足強連接，則該柵欄是強柵欄。

定義3如果兩個相鄰節點感知區域的水平投影相交，則兩個節點是弱連接。

定義4如果兩個相鄰節點感知區域相交，則兩個節點是強連接。

4.1.1 弱連接

弱柵欄覆蓋能夠檢測到沿垂直路徑穿越監測區域的入侵者。將監測區域的下邊界作為2維坐標系的水平坐標，監測區域的左邊界作為2維坐標系的垂直坐標。當dx(s1,s2)≤2Rs時，這兩個節點感知區域的水平投影才有可能相交。

當0≤β ≤π/2且dx(s1,s2)≤2Rs時，兩個弱連接的節點有兩種位置關系：

(1)兩節點中的任一個節點不在另一個節點的水平投影中，這時又有4種位置關系。

(a)0＜α1-β ＜π/2 且π/2＜α2+β ＜π且Rscos(α1-β)+Rscos[π-(α2+β)]≥dx(s1,s2)時，位置關系如圖3(a)所示；

圖3 當0 ≤β ≤π/2時，兩個弱連接的節點中的任一個節點不在另一個節點的水平投影中時的位置關系

(b)-π/2＜α1-β ＜0 且π＜α2+β ＜3π/2且Rscos[2π-(α1+β)]+Rscos[(α2-β)-π]≥dx(s1,s2)時，位置關系如圖3(b)所示；

( c )0＜α1-β ＜π/2且π＜α2+β ＜3π/2且Rscos(α1-β)+Rscos[(α2-β)-π]≥dx(s1,s2)時，位置關系如圖3(c)所示；

(d)-π/2＜α1-β ＜0 且π/2＜α2+β ＜π且Rscos[2π-(α1+β)]+Rscos[π-(α2+β)]≥dx(s1,s2)時，位置關系如圖3(d)所示。

(2) 兩節點中有一個節點在另一個節點的水平投影內。

(a)-π/2＜α1-β ＜π/2且dx(s1,s2)≤Rs時，位置關系如圖4(a)所示；

圖4 當0 ≤β ≤π/2時，兩個弱連接的節點中有一個節點在另一個節點的水平投影內時的位置關系

(b)π/2＜α2+β ＜3π/2且dx(s1,s2)≤Rs時，位置關系如圖4(b)所示；

當π/2≤β ≤π且dx(s1,s2)≤2Rs時，兩個弱連接的節點有兩種位置關系：

(1)兩節點中的任一個節點不在另一個節點的水平投影中，這時有3種位置關系。

(a)max{Rscos(2π-α1-β),Rscos(α1-β)}+max{Rscos(π-α2-β),Rscos(α2-β-π)}≥dx(s1,s2)且β ＜α1＜2π-β且2π-β ＜α2＜2π+β時，位置關系如圖5(a)所示；

圖5 當π/2 ≤β ≤π時，兩個弱連接節點的位置關系

(b)Rs+max{Rscos(π-α2-β),Rscos(α2-β-π)}≥dx(s1,s2)且β ＜α1＜2π-β且0＜α2＜π/2 或3π/2＜α2＜2π時，位置關系如圖5(b)所示；

(c)Rs+max{Rscos(2π-α1-β),Rscos(α1-β)}≥dx(s1,s2) 且π/2＜α1＜3π/2 且2π-β ＜α2＜2π+β時，位置關系如圖5(c)所示；

(2)兩節點中有一個節點在另一個節點的水平投影內時，dx(s1,s2)≤Rs，位置關系如圖5(d)所示。

4.1.2 強連接

強柵欄覆蓋能夠檢測到沿任意路徑穿越監測區域的入侵者。水下有向傳感器網絡中，兩個相鄰傳感器之間的位置關系判斷更為復雜。為便于分析判斷，每次將兩相鄰傳感器的連線作為新的水平軸如圖6所示。

圖6 水平坐標重新建立過程示意圖

文獻[1 7]給出了d(s1,s2)≤2Rs時，0≤β≤π/2 和π/2≤β ≤π兩種情況下，兩個強連接節點的位置關系。

4.2 基于圖分級的有向傳感器網絡分布式強柵欄覆蓋算法(Distributed strong barrier coverage algorithm in underwater Directional sensor network based on Hierarchy Graph, DDHG)

基于圖分級的柵欄覆蓋策略是在對網絡覆蓋圖進行分級的基礎上進行柵欄構建。經過分級的覆蓋圖可以更加清晰地反映網絡的拓撲關系，在構建柵欄時每一個節點只需要知道自己相鄰節點的位置和層級信息即可[16]。因此，基于圖分級的柵欄覆蓋策略既可用于集中式柵欄覆蓋又可用于分布式柵欄覆蓋。這里以分布式柵欄覆蓋為例，討論了一種基于圖分級的分布式有向傳感器網絡強柵欄覆蓋算法。

4.1節分析了兩個有向傳感器節點各種位置關系下分別滿足弱連接和強連接的條件。依據這些條件各節點建立連接關系并構建覆蓋圖。對圖2所示的有向傳感器網絡構建強柵欄覆蓋圖如圖7所示，在此基礎上建立的分級圖如圖8所示。在構建柵欄時，只要尋找與前一級和后一級某個節點都建立連接的節點即可，最后構建出的柵欄如圖9所示?；趫D分級的有向傳感器網絡弱柵欄覆蓋算法中除了弱連接條件與基于圖分級的有向傳感器網絡強柵欄覆蓋算法中的強連接不同之外，后續的柵欄圖和分級圖的構建都相同。因此本文只給出基于圖分級的有向傳感器網絡強柵欄覆蓋算法(如算法1所示)。

圖7 有向傳感器網絡強柵欄覆蓋圖

圖8 有向傳感器網絡分級圖

圖9 隨機分布下的有向傳感器網絡構建的強柵欄

5 性能分析

為了檢驗提出的DDHG算法性能，本文將從構建成功率、構建柵欄所需節點數和耗能3方面與文獻[14, 15]中的分布擴散算法(Distributed Proliferation Algorithm, DPA)進行比較并進行討論。水聲傳感器的偏移角通常在30°～120°，感知半徑一般在500～1 000 m。為了研究有向傳感器偏移角和感知半徑對水聲傳感器網絡柵欄覆蓋的影響，仿真中通常取偏移角為30°, 60°和120°，感知半徑在500～1 000 m進行比較討論。仿真采用N個靜態傳感器構成的隨機同分布的有向傳感器網絡，監測區域為10 000 m×500 m。為保證算法性能檢驗的可靠性，生成500個隨機拓撲，并采用500次仿真結果的平均值。

5.1 柵欄構建成功率比較

圖10比較了偏移角為β=60°，DDHG算法和DPA算法分別在感知半徑為400, 500和600 m時構建1-強柵欄的成功率。構建成功率隨著感知半徑的增大而增大，并且采用DDHG算法的構建成功率稍低于采用DPA算法的構建成功率，特別在隨機部署的節點數較多時，兩種算法的差別不大。由該圖可知：偏移角為β=60°，若構建半徑為400 m，要使構建成功率達到85%以上，在該檢測區域的隨機部署節點數需達到400以上；若構建半徑為600 m，要使構建成功率達到85%以上，隨機部署節點數需達到300即可。

圖10 不同構建半徑下，采用兩種算法構建1-強柵欄的成功率

5.2 節點個數和柵欄個數比較

圖11比較了隨機分布300個節點，采用兩種算法在不同構建半徑和不同偏移角下構建1-強柵欄所需的傳感器數目。該圖顯示：構建1-強柵欄所需的傳感器數目隨著構建半徑和偏移角的增大而減少，采用DDHG算法的構建柵欄所需的傳感器數目小于DPA算法。

圖11 不同構建半徑下，構建1-強柵欄所需的傳感器數目

圖12比較了隨機分布300個節點，采用兩種算法在不同構建半徑和不同偏移角下能夠構建強柵欄的數目。構建的強柵欄數目隨著構建半徑和偏移角的增大而增多。采用DDHG算法能夠構建的柵欄數比采用DPA算法構建的柵欄數多。

圖12 不同構建半徑下，構建強柵欄的數目

5.3 水聲傳感器網絡檢測概率比較

本小節比較了采用強M-DDHG算法和強M-DPA算法時水聲傳感器網絡的檢測概率。構建出多個柵欄的工作模式為多柵欄共同工作模式。

算法1 基于圖分級的有向傳感器網絡強柵欄覆蓋算法

圖13比較了虛警概率Pf=0.1，隨機部署總節點數為300，構建半徑Rvs=700 m時，不同發射聲源級和偏移角情況下，采用兩種算法的網絡檢測概率。由該圖可以看到：采用兩種算法時網絡的檢測概率隨著發射聲源級和偏移角的增大而增大。多個柵欄采用共同工作模式下，采用強M-DDHG算法時網絡的檢測概率高于采用強M-DPA算法時網絡的檢測概率。并且當構建半徑Rvs=700 m，發射聲源級大于150 dB，偏移角大于60°時，采用強MDDHG 算法網絡的檢測概率可達到95%。

圖13 不同發射聲源級下，水聲傳感器網絡的檢測概率

5.4 水聲傳感器網絡壽命比較

圖14比較了隨機部署總節點數為 300，構建半徑和偏移角β不同時，分別采用兩種算法時的網絡壽命。這里構建出的多個柵欄采用交替工作模式來延長網絡壽命。假設每一個傳感器的壽命為2周。由該圖可以看到：采用兩種算法的網絡壽命隨著構建半徑和偏移角的增大而增大，其中相同條件下采用強M-DDHG算法的網絡壽命比采用強M-DPA算法的網絡壽命長。原因有兩個：一是如圖13所示，采用強M-DDHG算法構建的平均柵欄數比采用強M-DPA算法的平均柵欄數多，參與交替工作的柵欄數也就更多；二是采用強M-DPA算法節點在構建柵欄過程中需要旋轉方向角消耗能量，這也會導致網絡壽命縮短。

圖14 不同構建半徑下，水聲傳感器網絡的壽命

5.5 算法執行時間比較

柵欄覆蓋算法的執行時間不僅取決于算法的優劣，還取決于構建柵欄的數量。為了比較DDHG算法和DPA 算法的優劣，這里只比較構建1-柵欄的算法執行時間。圖15比較了隨機部署總節點數300，不同構建半徑下，采用不同強1-柵欄算法的算法執行時間。該圖顯示：采用兩種算法的執行時間隨著構建半徑的增大而減少，這是由于構建半徑越大，構建柵欄的節點數就越少，節點搜索時間就越短。并且可以看到：采用強1-DDHG 算法的執行時間比強1-DPA 算法的執行時間更短，說明強1-DDHG 算法的速度更快。

圖15 不同構建半徑下，算法的執行時間

通過以上仿真結果可以看到：在靜態節點的柵欄覆蓋中，采用強1-DDHG算法的構建柵欄成功率比采用強1-DPA算法的構建柵欄成功率高。在偏移角一定的情況下，采用強1-DDHG算法所需的傳感器數目比采用強1-DPA算法少，并且強1-DDHG算法的運算速度更快。采用強M-DDHG算法構建的平均柵欄數比采用強M-DPA算法構建的平均柵欄數大。當采用多個柵欄共同工作模式時，采用強M-DDHG算法網絡的檢測概率高于采用強M-DPA算法網絡的檢測概率。當發射聲源級SL=150 dB，偏移角大于60°時，構建半徑大于700 m時，采用強M-DDHG算法網絡的檢測概率可達到95%。

6 結束語

本文通過對有向傳感器之間位置關系的討論，明確了兩個有向傳感器之間建立連接關系的條件。以此條件為基礎構建覆蓋圖并進行分級，基于分級圖能夠以盡可能少的節點對靜態有向傳感器網絡進行首次柵欄覆蓋。本文提出的強1-DDHG算法的柵欄構建成功率比強1-DPA算法柵欄構建成功率高，構建柵欄所需的節點數比強1-DPA算法少，運算速度比強1-DPA算法快。采用強M-DDHG算法所構建的柵欄數比采用強M-DPA算法多，并且采用強M-DDHG算法時網絡的檢測概率和網絡壽命都優于采用強M-DPA算法時網絡的檢測概率和網絡壽命。因此，在進行靜態有向傳感器網絡柵欄的首次構建時，DDHG算法性能優于DPA算法。但正如文獻[14]所述，DPA算法主要適用于移動可旋轉有向無線傳感器網絡的全視野柵欄構建。