基于鏈路交點相對位置信息的輕量級覆蓋空洞檢測算法

韓雨澇，房鼎益

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交點P1和P2的坐標為：

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

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

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

2.2 基于RPI值的覆蓋空洞檢測

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

2.2.1 空洞檢測發(fā)起節(jié)點確定

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

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

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

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

原則2 當集合H中最大NICI 值的節(jié)點有多個時，優(yōu)先選擇其中的柵欄HBN。若集合H中有多個具有相同最大值的柵欄HBN，隨機選擇即可。

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

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

2.2.2 空洞檢測過程

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

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

圖5 空洞檢測過程Fig.5 Process of hole detection

圖6 方向角計算Fig.6 Calculation of direction angle

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖7 空洞檢測流程Fig.7 Flowchart of hole detection

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

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

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

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

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

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

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

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

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

4 仿真實驗與結(jié)果分析

4.1 實驗設(shè)置

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

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

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

4.2 實驗結(jié)果與分析

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

1）平均空洞檢測時間。

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

2）平均空洞檢測能耗。

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

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

圖9 不同空洞數(shù)時本文算法節(jié)點數(shù)量與空洞檢測能耗的關(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，從覆蓋空洞平均檢測時間和檢測能耗兩方面，比較了CHDARPI 與空洞檢測算法DCHD［12］和DLPA［13］的性能。

1）平均空洞檢測時間。

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

2）平均空洞檢測能耗。

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

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

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

5 結(jié)語

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

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