韓雨澇，房鼎益

（1.攀枝花學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，四川攀枝花 617000；2.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，西安 710127）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）廣泛應(yīng)用于動(dòng)物保護(hù)、森林防火、智慧交通、新型農(nóng)業(yè)和大遺址監(jiān)測(cè)等領(lǐng)域。這些應(yīng)用大多對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量（Quality of Service，QoS）要求較高，而無(wú)線傳感器網(wǎng)絡(luò)覆蓋服務(wù)質(zhì)量是影響網(wǎng)絡(luò)服務(wù)質(zhì)量重要性能指標(biāo)之一［1］。大規(guī)模傳感器網(wǎng)絡(luò)應(yīng)用如野外長(zhǎng)城遺址狀態(tài)監(jiān)測(cè)采用節(jié)點(diǎn)隨機(jī)部署，節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的不充分感知使得監(jiān)測(cè)區(qū)域存在未被感知的區(qū)域，該區(qū)域稱為覆蓋空洞（Coverage Hole，CH）［2］。此外，網(wǎng)絡(luò)運(yùn)行中節(jié)點(diǎn)能量消耗、不合理的休眠調(diào)度機(jī)制、軟硬件故障、受氣候（颶風(fēng)、強(qiáng)降雨等）影響的節(jié)點(diǎn)移動(dòng)和破壞等因素也能產(chǎn)生覆蓋空洞。覆蓋空洞導(dǎo)致網(wǎng)絡(luò)不連通，影響路由協(xié)議的性能，增加網(wǎng)絡(luò)數(shù)據(jù)擁塞，引起覆蓋空洞邊界節(jié)點(diǎn)能量過(guò)度消耗，影響數(shù)據(jù)收集的完整性和連續(xù)性，這些都降低了網(wǎng)絡(luò)服務(wù)質(zhì)量，甚至導(dǎo)致網(wǎng)絡(luò)不可用。因此應(yīng)及時(shí)對(duì)網(wǎng)絡(luò)中存在的空洞進(jìn)行檢測(cè)。

覆蓋空洞檢測(cè)問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用領(lǐng)域熱點(diǎn)研究問(wèn)題之一，得到了國(guó)內(nèi)外學(xué)者廣泛的關(guān)注。文獻(xiàn)［3］中提出了一種基于圖論的空洞檢測(cè)算法；但過(guò)多的限定條件降低了算法的可用性。文獻(xiàn)［4］中通過(guò)傳感器節(jié)點(diǎn)間的協(xié)作機(jī)制建立局部圖，每個(gè)節(jié)點(diǎn)檢測(cè)附近關(guān)鍵點(diǎn)實(shí)現(xiàn)覆蓋空洞的檢測(cè)和修復(fù)；但空洞檢測(cè)能耗較大，且不一定能實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋空洞的完全檢測(cè)。文獻(xiàn)［5］中基于網(wǎng)絡(luò)連通性檢測(cè)覆蓋空洞，將監(jiān)測(cè)區(qū)劃分為多個(gè)子區(qū)域，利用探測(cè)信息在網(wǎng)絡(luò)中傳輸?shù)木嚯x作為空洞判斷的依據(jù)，進(jìn)一步確定空洞的準(zhǔn)確區(qū)域位置。文獻(xiàn)［6］中根據(jù)節(jié)點(diǎn)剩余能量檢測(cè)和修復(fù)覆蓋空洞；但不能實(shí)現(xiàn)節(jié)點(diǎn)死亡引起的覆蓋空洞。文獻(xiàn)［7］中提出了一種基于網(wǎng)絡(luò)同構(gòu)性的覆蓋空洞檢測(cè)算法，并討論了空洞檢測(cè)的準(zhǔn)確性和實(shí)時(shí)性。文獻(xiàn)［8］中利用虛擬計(jì)算確定邊緣節(jié)點(diǎn)，以實(shí)現(xiàn)覆蓋空洞的檢測(cè)。文獻(xiàn)［9］中根據(jù)節(jié)點(diǎn)位置信息生成Voronoi 圖，通過(guò)節(jié)點(diǎn)到Voronoi 區(qū)域邊界的距離判斷覆蓋空洞的位置。上述文獻(xiàn)［7-9］對(duì)應(yīng)算法計(jì)算復(fù)雜度過(guò)高，難以大規(guī)模應(yīng)用。文獻(xiàn)［10］中提出了一種無(wú)需節(jié)點(diǎn)位置信息的k重覆蓋空洞檢測(cè)算法，檢測(cè)過(guò)程分為邊界節(jié)點(diǎn)檢測(cè)和邊界循環(huán)檢測(cè)，通過(guò)單重覆蓋空洞檢測(cè)方法的迭代發(fā)現(xiàn)所有k重空洞。文獻(xiàn)［11］中提出了一種基于置信信息覆蓋模型的無(wú)線傳感器網(wǎng)絡(luò)空洞檢測(cè)算法。首先劃分監(jiān)測(cè)區(qū)域?yàn)槎鄠€(gè)單元，然后計(jì)算每個(gè)單元的置信信息，最后利用圖像技術(shù)提取空洞邊界的位置。文獻(xiàn)［12］中提出了一種基于邊界節(jié)點(diǎn)的分布式覆蓋空洞檢測(cè)算法（Distributed Coverage Hole Detection algorithm，DCHD），通過(guò)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的交叉點(diǎn)類型判斷邊界節(jié)點(diǎn)，有效地提高了覆蓋空洞的檢測(cè)效率；但該算法存在節(jié)點(diǎn)能量過(guò)度消耗的問(wèn)題，擴(kuò)大了覆蓋空洞區(qū)域。文獻(xiàn)［13］中提出了一種基于分布式最小極角的覆蓋空洞檢測(cè)算法（Distributed Least Polar Angle algorithm，DLPA），基于邊界節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)檢測(cè)空洞，確定每個(gè)空洞位置的邊界節(jié)點(diǎn)，降低了空洞檢測(cè)能耗；但該算法不適用于檢測(cè)復(fù)雜空洞。

針對(duì)上述空洞檢測(cè)算法存在通信或計(jì)算能耗高、檢測(cè)時(shí)間長(zhǎng)、不能實(shí)現(xiàn)多種類型空洞聯(lián)合檢測(cè)的問(wèn)題，本文提出了一種基于鏈路交點(diǎn)相對(duì)位置信息的覆蓋空洞檢測(cè)算法（Coverage Hole Detection Algorithm based on Relative Position of Intersections，CHDARPI），主要研究工作包括：

1）定義鄰居邊界節(jié)點(diǎn)間鏈路的交點(diǎn)相對(duì)位置（Relative Position of Intersections，RPI）值，并通過(guò)節(jié)點(diǎn)未完全覆蓋交點(diǎn)數(shù)量（Number of Incomplete Coverage Intersections，NICI）值確定空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，進(jìn)而實(shí)現(xiàn)連通覆蓋空洞的并發(fā)檢測(cè)，有效地提高了空洞檢測(cè)的速度。

2）將檢測(cè)消息限定在空洞邊界節(jié)點(diǎn)內(nèi)，然后定義節(jié)點(diǎn)方向角，并根據(jù)節(jié)點(diǎn)與其上一跳節(jié)點(diǎn)基于NICI 和當(dāng)前節(jié)點(diǎn)的鄰居邊界節(jié)點(diǎn)數(shù)量，確定不同場(chǎng)景下檢測(cè)消息的轉(zhuǎn)發(fā)策略，有效地避免了冗余消息傳輸，降低了網(wǎng)絡(luò)節(jié)點(diǎn)能耗。

1 網(wǎng)絡(luò)模型

傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域Z內(nèi)隨機(jī)部署構(gòu)成的無(wú)線傳感器網(wǎng)絡(luò)表示為G=（V，E），其中V為節(jié)點(diǎn)集合，E為節(jié)點(diǎn)間鏈路集合。每個(gè)節(jié)點(diǎn)具有唯一的ID，它們的位置信息可通過(guò)裝載全球定位系統(tǒng)（Global Positioning System，GPS）或已有的傳感器網(wǎng)絡(luò)定位算法［14］獲取。節(jié)點(diǎn)的感知和通信范圍均使用圓盤模型［15］，每個(gè)節(jié)點(diǎn)感知半徑和通信半徑同構(gòu)，分別記為Rs和Rc，假定Rc=2Rs。本文空洞檢測(cè)算法基于以下定義。

定義1鄰居節(jié)點(diǎn)。如果監(jiān)測(cè)區(qū)域Z內(nèi)任意節(jié)點(diǎn)Ni和Nj滿足關(guān)系dist(Ni，Nj)≤2Rs，則定義節(jié)點(diǎn)Ni和Nj為鄰居節(jié)點(diǎn)。節(jié)點(diǎn)Ni的鄰居節(jié)點(diǎn)集合表示為：

定義5覆蓋空洞類型。如圖1 所示空洞A由一組HBN序列對(duì)應(yīng)的空洞圓弧構(gòu)成，該空洞稱為閉合覆蓋空洞；如果空洞區(qū)域位于HBN序列的外側(cè)，則稱為外側(cè)空洞；如圖1所示的空洞B是由一組HBN 序列與監(jiān)測(cè)區(qū)域的邊界線構(gòu)成，稱為柵欄空洞。

圖1 覆蓋空洞類型Fig.1 Types of coverage holes

定義6順時(shí)針節(jié)點(diǎn)序列。給定HBN 序列（Nu，Nm，Nn），當(dāng)它們的坐標(biāo)（xu，yu），（xm，ym），（xn，yn）滿足如下條件：

則定義該節(jié)點(diǎn)序列為順時(shí)針序列。其中：式（7）表示節(jié)點(diǎn)Nu，Nm，Nn之間的相鄰關(guān)系；式（8）表示節(jié)點(diǎn)序列為平面上順時(shí)針序列關(guān)系。為了便于敘述，將節(jié)點(diǎn)Nu的后續(xù)節(jié)點(diǎn)Nm記為SN（Nu）。

定義7有向鏈路交點(diǎn)相對(duì)位置（RPI）。令Pk為節(jié)點(diǎn)Ni和Nj感知圓盤的某個(gè)交點(diǎn)。Ni、Nj和Pk的坐標(biāo)分別為（xi，yi），（xj，yj），（xk，yk）。

2 空洞檢測(cè)算法CHDARPI設(shè)計(jì)

2.1 覆蓋空洞節(jié)點(diǎn)及鏈路RPI值確定

為了確定網(wǎng)絡(luò)中HBN 集合H以及鏈路的RPI 值，首先通過(guò)鄰居節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制確定每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及位置信息，基本思想是：網(wǎng)絡(luò)中節(jié)點(diǎn)向通信范圍內(nèi)的其他節(jié)點(diǎn)廣播包含自己編號(hào)及位置信息的Hello消息，該消息的發(fā)送局限于一跳范圍之內(nèi)；鄰居節(jié)點(diǎn)通過(guò)Hello消息獲得了發(fā)送節(jié)點(diǎn)的基本信息；當(dāng)鄰居節(jié)點(diǎn)發(fā)現(xiàn)周期結(jié)束時(shí)，在每個(gè)節(jié)點(diǎn)的鄰居信息表中保存了全部鄰居的信息。

假定鄰居節(jié)點(diǎn)Ni和Nj的位置坐標(biāo)分別為（xi，yi）和（xj，yj），感知圓盤的交點(diǎn)為P1和P2，對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示，連接交點(diǎn)Ni和Nj的線段NiNj的長(zhǎng)度記為d。

圖2 節(jié)點(diǎn)感知圓盤交點(diǎn)Fig.2 Intersections of node sensing disks

交點(diǎn)P1和P2的坐標(biāo)為：

根據(jù)定義2 及推論判斷交點(diǎn)的類型。如圖2 所示P1為未完全覆蓋交點(diǎn)，故節(jié)點(diǎn)Ni和Nj為HBN。在此基礎(chǔ)上，計(jì)算鏈路的RPI 值。表1 給出了圖2 所示節(jié)點(diǎn)Ni的鄰居信息表結(jié)構(gòu)。其中，鄰居節(jié)點(diǎn)類型分為完全覆蓋節(jié)點(diǎn)、未完全覆蓋節(jié)點(diǎn)和柵欄未完全覆蓋節(jié)點(diǎn)，依次標(biāo)記為0、1和2。

表1 鄰居信息表Tab.1 Neighbor information table

按照上述方法，確定網(wǎng)絡(luò)中HBN 集合H以及每條鏈路的RPI值。

2.2 基于RPI值的覆蓋空洞檢測(cè)

節(jié)點(diǎn)發(fā)送空洞檢測(cè)消息（Hole Detection Message，HDM）進(jìn)行覆蓋空洞檢測(cè)。HDM 消息包含所經(jīng)路徑每個(gè)節(jié)點(diǎn)的ID及每條鏈路RPI值。

2.2.1 空洞檢測(cè)發(fā)起節(jié)點(diǎn)確定

原則1 將網(wǎng)絡(luò)中具有最大NICI值的節(jié)點(diǎn)作為空洞檢測(cè)的發(fā)起節(jié)點(diǎn)。

算法在運(yùn)行過(guò)程中按照式（18）在集合H中選取具有最大NICI值的節(jié)點(diǎn)作為空洞檢測(cè)的發(fā)起節(jié)點(diǎn)：

選擇具有最大NICI 值的節(jié)點(diǎn)Ni作為空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，是因?yàn)樵摴?jié)點(diǎn)具有最多的未完全覆蓋交點(diǎn)，是最多覆蓋空洞的邊界節(jié)點(diǎn)，以該節(jié)點(diǎn)作為空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，有助于覆蓋空洞的并發(fā)檢測(cè)，從而降低覆蓋空洞的檢測(cè)時(shí)間以及節(jié)點(diǎn)能耗。如圖3所示節(jié)點(diǎn)N13的NICI值最大，具有最多的未完全覆蓋交點(diǎn)，是兩個(gè)覆蓋空洞的HBN，以該節(jié)點(diǎn)作為覆蓋空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，能夠?qū)崿F(xiàn)覆蓋空洞A和B的并發(fā)檢測(cè)。

圖3 基于NICI值的發(fā)起節(jié)點(diǎn)選擇Fig.3 Selection for starting node based on NICI

原則2 當(dāng)集合H中最大NICI 值的節(jié)點(diǎn)有多個(gè)時(shí)，優(yōu)先選擇其中的柵欄HBN。若集合H中有多個(gè)具有相同最大值的柵欄HBN，隨機(jī)選擇即可。

原則2 主要是基于多個(gè)節(jié)點(diǎn)具有相同NICI 值，雖可并發(fā)檢測(cè)多個(gè)覆蓋空洞，但柵欄覆蓋空洞僅能使用柵欄HBN 作為發(fā)起節(jié)點(diǎn)進(jìn)行檢測(cè)，故為了保證空洞檢測(cè)的效率，當(dāng)最大NICI值的節(jié)點(diǎn)有多個(gè)時(shí)，優(yōu)先選擇其中的柵欄HBN。如圖4 所示的節(jié)點(diǎn)N2和N3有相同的NICI值，此時(shí)選擇柵欄邊界節(jié)點(diǎn)N2能并發(fā)完成空洞A和B的檢測(cè)。倘若選擇N3則根據(jù)本文的空洞檢測(cè)流程，僅能檢測(cè)出空洞A，為了檢測(cè)柵欄覆蓋空洞B，需發(fā)起下一輪空洞檢測(cè)，這增加了空洞檢測(cè)的時(shí)間和能耗。

圖4 基于柵欄節(jié)點(diǎn)的發(fā)起節(jié)點(diǎn)選擇Fig.4 Selection of starting node based on fence nodes

2.2.2 空洞檢測(cè)過(guò)程

為了避免HDM 消息廣播引起的節(jié)點(diǎn)能量過(guò)度消耗，空洞檢測(cè)的發(fā)送節(jié)點(diǎn)僅向鄰居HBN 發(fā)送包含自己ID 的HDM 消息。如圖5 所示，空洞檢測(cè)發(fā)起節(jié)點(diǎn)N1向N2和N7發(fā)送HDM消息。

除了上一跳鄰居HBN，轉(zhuǎn)發(fā)節(jié)點(diǎn)需向其他鄰居HBN 發(fā)送HDM 消息。在這里定義轉(zhuǎn)發(fā)節(jié)點(diǎn)Nx的HBN 鄰居節(jié)點(diǎn)集合為L(zhǎng)B（Nx），該集合包含的節(jié)點(diǎn)數(shù)記為|LB（Nx）|。當(dāng)收到節(jié)點(diǎn)Ni的HDM 消息時(shí)，Nx向LB（Nx）中每個(gè)節(jié)點(diǎn)發(fā)送HDM 消息。為了避免冗余數(shù)據(jù)的傳輸，Nx對(duì)每個(gè)鄰居節(jié)點(diǎn)發(fā)送的HDM 消息采取了兩種處理模式，最后將處理后的HDM 消息發(fā)送到相應(yīng)的鄰居節(jié)點(diǎn)。

圖5 空洞檢測(cè)過(guò)程Fig.5 Process of hole detection

圖6 方向角計(jì)算Fig.6 Calculation of direction angle

基于以上方向角的定義，節(jié)點(diǎn)Nx轉(zhuǎn)發(fā)HDM消息分為以下幾種場(chǎng)景：

場(chǎng)景1 轉(zhuǎn)發(fā)節(jié)點(diǎn)Nx有且僅有一個(gè)鄰居HBN，即|LB（Nx）|=1，節(jié)點(diǎn)Nx向該鄰居節(jié)點(diǎn)發(fā)送包含所經(jīng)路徑每個(gè)節(jié)點(diǎn)ID 及對(duì)應(yīng)鏈路RPI 的HDM，即原HDM 信息保持不變，然后將自己的ID 以及信息追加到HDM 消息中，此消息轉(zhuǎn)發(fā)模式簡(jiǎn)稱為消息轉(zhuǎn)發(fā)模式1，用于檢測(cè)當(dāng)前覆蓋空洞。如圖5所示的節(jié)點(diǎn)N7將HDM 消息發(fā)送給節(jié)點(diǎn)N8，N8僅有一個(gè)下一跳鄰居HBNN9，此時(shí)N8在保持原有HDM 消息的基礎(chǔ)上，將自己的ID 以及追加到HDM 消息中，然后將該HDM消息發(fā)送給節(jié)點(diǎn)N9，用于當(dāng)前覆蓋空洞C的檢測(cè)。

場(chǎng)景2 轉(zhuǎn)發(fā)節(jié)點(diǎn)Nx有多個(gè)HBN 鄰居節(jié)點(diǎn)，且其數(shù)量大于Nx與其上一跳節(jié)點(diǎn)Ni的未完全覆蓋交點(diǎn)數(shù)量，即：

該場(chǎng)景下NiNx是兩個(gè)空洞的邊界線段，故節(jié)點(diǎn)Nx按照消息轉(zhuǎn)發(fā)模式1 向這兩個(gè)鄰居節(jié)點(diǎn)發(fā)送HDM 消息。如圖5 所示，=3，節(jié)點(diǎn)N5按照模式1 向節(jié)點(diǎn)N4和N12發(fā)送HDM 消息。N4和N12收到HDM 消息，將它們的ID 及其對(duì)應(yīng)RPI 值追加到HDM 消息的尾部，用于當(dāng)前覆蓋空洞B和C的檢測(cè)。

某個(gè)節(jié)點(diǎn)Nk收到兩個(gè)鄰居節(jié)點(diǎn)的HDM 消息，分別記為HDM1和HDM2。如果HDM1和HDM2消息的節(jié)點(diǎn)序列構(gòu)成一個(gè)環(huán)HBN 序列，表示檢測(cè)到以該環(huán)節(jié)點(diǎn)序列構(gòu)成的覆蓋空洞。如圖5 所示節(jié)點(diǎn)N5從兩個(gè)鄰居節(jié)點(diǎn)N4和N6分別收到源于節(jié)點(diǎn)N1的HDM1和HDM2消息，表示為：

消息HDM1和HDM2中節(jié)點(diǎn)序列構(gòu)成一個(gè)環(huán)HBN 序列，N1稱為該序列的源節(jié)點(diǎn)。

為了確定覆蓋空洞的類型，將HDM 消息按照定義6 分為順時(shí)針消息和逆時(shí)針消息。

在確定HDM1和HDM2分別為逆時(shí)針和順時(shí)針消息后，順時(shí)針消息保持不變，逆時(shí)針消息中的節(jié)點(diǎn)序列按照逆序排列，同時(shí)計(jì)算新節(jié)點(diǎn)序列中每條鏈路的RPI 值，最終得出逆時(shí)針消息HDM1處理后的結(jié)果為：

聯(lián)合HDM1和HDM2中節(jié)點(diǎn)ID 和RPI值，構(gòu)成如下HBN 環(huán)節(jié)點(diǎn)序列：

當(dāng)環(huán)節(jié)點(diǎn)序列中存在兩個(gè)有序節(jié)點(diǎn)Ni和Nj滿足式（23）的條件時(shí)，該環(huán)節(jié)點(diǎn)序列構(gòu)成閉合覆蓋空洞，如圖5 所示的空洞B和C：

當(dāng)環(huán)節(jié)點(diǎn)序列中存在兩個(gè)有序節(jié)點(diǎn)Ni和Nj滿足式（24）的條件時(shí)，該環(huán)節(jié)點(diǎn)序列的外側(cè)為外側(cè)覆蓋空洞。

當(dāng)環(huán)節(jié)點(diǎn)序列中任意兩個(gè)連續(xù)有序節(jié)點(diǎn)Ni和Nj滿足式（25）的條件時(shí)，該環(huán)節(jié)點(diǎn)序列包圍的區(qū)域構(gòu)成閉合覆蓋空洞，同時(shí)外側(cè)為外側(cè)覆蓋空洞。

柵欄空洞檢測(cè)：當(dāng)柵欄HBNNi作為空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，按照上述流程發(fā)送HDM 消息，經(jīng)歷若干HBN 的傳輸，到達(dá)某個(gè)柵欄HBNNj，此時(shí)HDM 消息經(jīng)歷了一個(gè)HBN 序列。如果該節(jié)點(diǎn)序列滿足定義6 的順時(shí)針序列條件，且該序列存在兩個(gè)連續(xù)節(jié)點(diǎn)的鏈路RPI值為1，則構(gòu)成柵欄覆蓋空洞。如圖5所示的柵欄HBNN1通過(guò)HDM消息發(fā)起空洞檢測(cè)，經(jīng)歷節(jié)點(diǎn)N2，N2按照?qǐng)鼍? 中的處理方式轉(zhuǎn)發(fā)HDM 消息達(dá)到N3，N3是柵欄HBN，且其再無(wú)其他鄰居HBN。N3的HDM 消息包含如下節(jié)點(diǎn)序列：

按照定義6 判斷該節(jié)點(diǎn)序列為時(shí)針序列，且存在鏈路的RPI為1，故該空洞為柵欄覆蓋空洞。

為了避免后續(xù)不必要消息傳遞，降低節(jié)點(diǎn)能量開銷，在每個(gè)覆蓋空洞（如Hk）成功檢測(cè)之后，算法需要更新該空洞鏈路的RPI 值以及空洞邊界節(jié)點(diǎn)集合H。Hk中任意節(jié)點(diǎn)Ni到Nj間鏈路的RPI值更新規(guī)則為：

按照上述空洞檢測(cè)過(guò)程，可以并發(fā)檢測(cè)到發(fā)起節(jié)點(diǎn)所在空洞對(duì)應(yīng)的全部連通空洞。對(duì)于其他尚未檢測(cè)的空洞，需在H中重新選擇空洞檢測(cè)的發(fā)起節(jié)點(diǎn)，按照上述空洞檢測(cè)過(guò)程進(jìn)行檢測(cè)，直到集合H為空，表示覆蓋空洞檢測(cè)結(jié)束。圖7 給出了本文覆蓋空洞檢測(cè)算法的流程。

圖7 空洞檢測(cè)流程Fig.7 Flowchart of hole detection

3 時(shí)間復(fù)雜度分析

假定網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)量為N，覆蓋空洞數(shù)量為k，具有不連通覆蓋空洞數(shù)為m。將算法分解為如下幾個(gè)階段，每個(gè)階段的時(shí)間復(fù)雜度為：

階段1 鄰居節(jié)點(diǎn)發(fā)現(xiàn)。每個(gè)節(jié)點(diǎn)向一跳鄰居節(jié)點(diǎn)發(fā)送Hello消息，該階段時(shí)間復(fù)雜度為O（N）。

階段2 鏈路RPI 計(jì)算。計(jì)算每對(duì)鄰居節(jié)點(diǎn)間鏈路的RPI值，該階段時(shí)間復(fù)雜度為O（N2）。

階段3 空洞檢測(cè)的發(fā)起節(jié)點(diǎn)確定。該階段需要比較每個(gè)節(jié)點(diǎn)的NICI值，對(duì)應(yīng)時(shí)間復(fù)雜度為O（N）。

階段4 并發(fā)空洞檢測(cè)。分析可知任意節(jié)點(diǎn)Ni最多收到|LNi|個(gè)鄰居節(jié)點(diǎn)的消息，|LNi|＜N。又因HBN數(shù)量不超過(guò)N，故該階段最壞情況時(shí)間復(fù)雜度為O（N2）。

階段5 判斷是否為空洞。每個(gè)節(jié)點(diǎn)根據(jù)HDM消息判斷覆蓋空洞，該階段對(duì)應(yīng)的時(shí)間復(fù)雜度為O（N2）。

階段6 更新鏈路RPI 值。該階段時(shí)間復(fù)雜度取決于覆蓋空洞的數(shù)量，對(duì)應(yīng)時(shí)間復(fù)雜度為O（k）。

階段7 判斷空洞是否檢測(cè)結(jié)束。該階段時(shí)間復(fù)雜度取決于非連通覆蓋空洞的數(shù)量，對(duì)應(yīng)時(shí)間復(fù)雜度為O（m）。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

使用Matlab 7.0 工具作為仿真實(shí)驗(yàn)平臺(tái)，節(jié)點(diǎn)數(shù)量依次為100，150，200，250，300，350，400，在400 m×100 m 區(qū)域內(nèi)隨機(jī)部署，節(jié)點(diǎn)感知半徑Rs=10 m，通信半徑Rc=20 m，發(fā)送和接收一個(gè)消息能耗均為0.2 J，算法運(yùn)行過(guò)程中除非指定否則覆蓋空洞大小和位置不變。采用如下度量評(píng)估算法的性能。

1）平均空洞檢測(cè)時(shí)間：檢測(cè)一個(gè)空洞平均所需時(shí)間，用總的空洞檢測(cè)時(shí)間除以空洞數(shù)量。

2）平均空洞檢測(cè)能耗：檢測(cè)一個(gè)空洞平均所需能耗，用總的空洞檢測(cè)能耗除以空洞數(shù)量。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 空洞數(shù)量對(duì)算法性能影響

1）平均空洞檢測(cè)時(shí)間。

圖8 為不同空洞數(shù)量下節(jié)點(diǎn)數(shù)量與平均空洞檢測(cè)時(shí)間的對(duì)比圖?？梢钥闯觯N空洞數(shù)量下的空洞檢測(cè)時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加而增加，這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加，在部署區(qū)域面積以及空洞面積固定的情況下，網(wǎng)絡(luò)節(jié)點(diǎn)密度增加，每個(gè)空洞將具有更多的HBN，將需要計(jì)算更多HBN 的RPI 和NICI值。另外，HDM 傳輸經(jīng)歷的HBN 也顯著增加，增加了并發(fā)空洞檢測(cè)的時(shí)間，在空洞數(shù)量固定的情況下，最終造成空洞平均檢測(cè)時(shí)間的增加。另外，由圖8 也可以發(fā)現(xiàn)，在相同節(jié)點(diǎn)數(shù)量下針對(duì)不同空洞數(shù)的空洞平均檢測(cè)時(shí)間相差較小，這是因?yàn)檫B通空洞的并發(fā)檢測(cè)使得空洞檢測(cè)總時(shí)間降低，因此在三種不同空洞數(shù)量情況下，空洞平均檢測(cè)時(shí)間相差較小，體現(xiàn)了本文算法對(duì)連通覆蓋空洞并發(fā)檢測(cè)的優(yōu)勢(shì)。

2）平均空洞檢測(cè)能耗。

圖9 反映了三種空洞數(shù)量下，平均空洞檢測(cè)能耗隨著節(jié)點(diǎn)數(shù)量的增加而增大，這是因?yàn)楣?jié)點(diǎn)數(shù)量增加導(dǎo)致HBN 增多，使得同一規(guī)格的覆蓋空洞將有更多的節(jié)點(diǎn)參與計(jì)算以及HDM 消息的傳遞，造成單個(gè)空洞的檢測(cè)能耗增大，最終導(dǎo)致整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)平均檢測(cè)能耗的增大。另外，覆蓋空洞數(shù)量對(duì)算法平均檢測(cè)能耗也有影響。由圖9 可以發(fā)現(xiàn)，空洞數(shù)量越少，空洞檢測(cè)能耗越低，這是因?yàn)楫?dāng)多個(gè)覆蓋空洞為連通覆蓋空洞，部分HBN 可能多次發(fā)送HDM 消息，增加了平均覆蓋空洞檢測(cè)的能耗；但從總體趨勢(shì)來(lái)看，覆蓋空洞數(shù)量對(duì)算法的平均檢測(cè)能耗影響不大，說(shuō)明了本文算法具有較好的擴(kuò)展性。

圖8 不同空洞數(shù)時(shí)本文算法節(jié)點(diǎn)數(shù)量與空洞檢測(cè)時(shí)間的關(guān)系Fig.8 Relationship between number of nodes and hole detection time with different hole number for the proposed algorithm

圖9 不同空洞數(shù)時(shí)本文算法節(jié)點(diǎn)數(shù)量與空洞檢測(cè)能耗的關(guān)系Fig.9 Relationship between number of nodes and energy consumption of hole detection with different hole number for the proposed algorithm

4.2.2 與現(xiàn)有同類算法性能比較

限定覆蓋空洞數(shù)量為10，從覆蓋空洞平均檢測(cè)時(shí)間和檢測(cè)能耗兩方面，比較了CHDARPI 與空洞檢測(cè)算法DCHD［12］和DLPA［13］的性能。

1）平均空洞檢測(cè)時(shí)間。

圖10 給出了三種算法在不同節(jié)點(diǎn)數(shù)量下的平均覆蓋空洞檢測(cè)時(shí)間。相較于算法DLPA 和DCHD，CHDARPI 的平均空洞檢測(cè)時(shí)間分別下降了15.2% 和40.9%，這是因?yàn)镃HDARPI 使用輕量級(jí)的消息廣播機(jī)制，將HDM 消息僅局限于HBN，且能夠?qū)崿F(xiàn)多個(gè)連通覆蓋空洞的并發(fā)檢測(cè)，從而降低了覆蓋空洞的平均檢測(cè)時(shí)間。

2）平均空洞檢測(cè)能耗。

圖11 反映了三種算法在不同節(jié)點(diǎn)數(shù)量下的平均覆蓋空洞檢測(cè)能耗。通過(guò)與DLPA 和DCHD 對(duì)比發(fā)現(xiàn)，CHDARPI 的平均空洞檢測(cè)能耗分別下降了16.7%和28.6%，這是因?yàn)镃HDARPI 在探測(cè)覆蓋空洞的過(guò)程中：1）將HDM 消息局限于HBN 中傳輸，縮小了消息傳輸?shù)姆秶?）在并發(fā)空洞檢測(cè)的過(guò)程中，根據(jù)不同場(chǎng)景對(duì)HDM 消息進(jìn)行了冗余處理，降低了部分節(jié)點(diǎn)收發(fā)的數(shù)據(jù)量；3）隨著覆蓋空洞的不斷檢測(cè)，更新已檢測(cè)覆蓋空洞鏈路的RPI 值，避免了這部分鏈路發(fā)送冗余HDM消息，減少了網(wǎng)絡(luò)中HDM消息的數(shù)量。

圖10 各算法節(jié)點(diǎn)數(shù)量與空洞檢測(cè)時(shí)間的關(guān)系Fig.10 Relationship between number of nodes and hole detection time for different algorithms

圖11 各算法節(jié)點(diǎn)數(shù)量與空洞檢測(cè)能耗的關(guān)系Fig.11 Relationship between the number of nodes and energy consumption of hole detection for different algorithms

5 結(jié)語(yǔ)

在無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，網(wǎng)絡(luò)覆蓋空洞影響網(wǎng)絡(luò)性能和服務(wù)質(zhì)量，本文提出了基于鏈路RPI 的覆蓋空洞檢測(cè)算法（CHDARPI），采用基于NICI 值的空洞檢測(cè)發(fā)起節(jié)點(diǎn)選擇策略，并根據(jù)HDM 消息攜帶鏈路的RPI 值判斷覆蓋空洞及其類型，能夠?qū)崿F(xiàn)多個(gè)連通覆蓋的并發(fā)檢測(cè)。實(shí)驗(yàn)結(jié)果驗(yàn)證了CHDARPI 的有效性，與現(xiàn)有同類空洞檢測(cè)算法相比具有更好的優(yōu)越性。

本文研究二維平面結(jié)構(gòu)下采用布爾感知模型的無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞檢測(cè)算法，為了進(jìn)一步提高算法的適用性，下一步工作將研究三維環(huán)境下采用概率感知模型的覆蓋空洞檢測(cè)算法。