基于虛力的移動(dòng)節(jié)點(diǎn)的無線傳感網(wǎng)絡(luò)空洞修復(fù)算法

宋喜忠，張韌志

（黃淮學(xué)院 信息工程學(xué)院，河南 駐馬店　463000）

基于虛力的移動(dòng)節(jié)點(diǎn)的無線傳感網(wǎng)絡(luò)空洞修復(fù)算法

宋喜忠，張韌志

（黃淮學(xué)院 信息工程學(xué)院，河南 駐馬店463000）

由于無線傳感網(wǎng)絡(luò)WSNs的內(nèi)在特性以及環(huán)境因素，興趣區(qū)域RoI內(nèi)出現(xiàn)覆蓋空洞是無法避免的。為此，提出基于虛力的局部移動(dòng)空洞處理（VF?LMH）算法。VF?LMH算法分為空洞檢測(cè)及空洞修復(fù)兩個(gè)階段。首先進(jìn)入空洞檢測(cè)階段，利用網(wǎng)絡(luò)Gabriel圖局部協(xié)議識(shí)別空洞以及空洞中心位置、尺寸，隨后進(jìn)入空洞修復(fù)階段，先明確空洞處理區(qū)域，然后空洞處理區(qū)域內(nèi)的節(jié)點(diǎn)依據(jù)虛力進(jìn)行局部移動(dòng)，修復(fù)空洞。仿真結(jié)果表明，提出的VF?LMH算法能夠有效檢測(cè)并修復(fù)空洞，與同類算法相比，VF?LMH算法的修復(fù)空洞成本低廉（參與移動(dòng)的節(jié)點(diǎn)數(shù)少、總移動(dòng)距離?。?。

虛力；Gabriel圖；興趣區(qū)域；空洞修復(fù)；無線傳感網(wǎng)絡(luò)

0　引言

由傳感節(jié)點(diǎn)組建的無線傳感網(wǎng)絡(luò)WSNs（Wireless Sensor Networks）被廣泛應(yīng)用，如棲息地監(jiān)控［1］、環(huán)境監(jiān)控［2?3］以及監(jiān)視系統(tǒng)［4］（Surveillance Systems）等。實(shí)際上，傳感節(jié)點(diǎn)是一個(gè)微型設(shè)備，具有有限的計(jì)算以及通信功能。然而，傳感節(jié)點(diǎn)是非常脆弱，易受到外界多種因素干擾，如瞬息震動(dòng)（Sudden Shock）、能量耗盡，致使傳感節(jié)點(diǎn)失效，一旦失效，就在對(duì)特定的興趣區(qū)域RoI（Re?gion of Interest）形成覆蓋空洞（Coverage Holes）［5］。

然而，WSNs提供的基礎(chǔ)性服務(wù)之一就是對(duì)RoI區(qū)域進(jìn)行持續(xù)監(jiān)測(cè)。而覆蓋空洞就會(huì)導(dǎo)致監(jiān)測(cè)的中斷，破壞了數(shù)據(jù)的傳輸。因此，維持RoI區(qū)域的覆蓋是非常重要的［6］。然而，由于WSNs內(nèi)在特性及環(huán)境因素，RoI出現(xiàn)空洞是無法避免的，為此，在WSNs中，提供檢測(cè)并修復(fù)空洞的機(jī)制是最基本的要求。為此，本文以檢測(cè)、修復(fù)空洞為主題，分析了目前空洞修復(fù)的算法［7?14］，并提出新的算法。目前，現(xiàn)有的多數(shù)算法都是以苛刻的假設(shè)為前提條件，現(xiàn)有算法的不足如表1所示。

表1　現(xiàn)有處理空洞方案的不足

為此，本文提出的基于虛力的局部移動(dòng)空洞修復(fù)VF?LMH（Virtual Forces?based Localized Movement HoleHealing）算法。VF?LMH算法主要有兩個(gè)階段。第一階段：空洞檢測(cè)。采用分布式基于網(wǎng)絡(luò)Gabriel圖GG（Ga?briel Graph）的局部空洞檢測(cè)方案。第二階段：空洞修復(fù)。在空洞修復(fù)時(shí)，先采用迭代算法計(jì)算HHA區(qū)域半徑，明確空洞處理區(qū)域HHA（Hole Healing Area）后，采用基于HHA內(nèi)的節(jié)點(diǎn)虛力驅(qū)動(dòng)節(jié)點(diǎn)移動(dòng)，修復(fù)空洞。

1　VF?LMH算法

具體而言，提出的VF?LMH算法從二個(gè)角度修復(fù)空洞：如何檢測(cè)空洞以及估計(jì)空洞的尺寸；在修復(fù)空洞時(shí)，哪個(gè)位置是移動(dòng)節(jié)點(diǎn)的最佳的目標(biāo)位置。

1.1空洞檢測(cè)

文獻(xiàn)［15］在貪婪多跳轉(zhuǎn)發(fā)方式中，定義了停足節(jié)點(diǎn)（Stuck Nodes）。假定節(jié)點(diǎn) p在其通信范圍外存在位置q。如果節(jié)點(diǎn) p的一跳鄰居的所有節(jié)點(diǎn)內(nèi)沒有節(jié)點(diǎn)比節(jié)點(diǎn) p離位置q更近，那么節(jié)點(diǎn) p就是Stuck Node。為此，文獻(xiàn)［15］提出用于檢測(cè)網(wǎng)絡(luò)節(jié)點(diǎn)是否為Stuck Node的規(guī)則，稱為TENT規(guī)則。在空洞檢測(cè)過程，采用了TENT規(guī)則。

1.1.1空洞識(shí)別

首先，通過識(shí)別Stuck Nodes，檢測(cè)空洞是否存在。網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)執(zhí)行TENT規(guī)則，檢測(cè)自己是否為Stuck Node。具體而言，節(jié)點(diǎn) p檢測(cè)過程如下：如圖1所示，假定節(jié)點(diǎn)u和v是一對(duì)邊緣鄰居節(jié)點(diǎn)，連接up和vp，然后過點(diǎn)o作up和vp的垂直平分線l1，l2。在節(jié)點(diǎn) p一跳鄰居節(jié)點(diǎn)范圍內(nèi)，沒有節(jié)點(diǎn)比 p離節(jié)點(diǎn)o更近，因此節(jié)點(diǎn) p是Stuck Node。

圖1　TENT規(guī)則實(shí)施示例

所有Stuck Nodes觸發(fā)空洞發(fā)現(xiàn)階段，并找出空洞的邊界以及空洞的尺寸，即空洞的中心位置以及半徑。

Stuck NodeSi產(chǎn)生一個(gè)用于空洞發(fā)現(xiàn)數(shù)據(jù)包Pack?et_discovery，并用自己的ID進(jìn)行標(biāo)識(shí)。數(shù)據(jù)包Pack?et_discovery的任務(wù)就是收集空洞邊界節(jié)點(diǎn)的位置信息。節(jié)點(diǎn)Si依據(jù)網(wǎng)絡(luò)GG，按照右手規(guī)則向邊界節(jié)點(diǎn)Si+1轉(zhuǎn)發(fā)數(shù)據(jù)包Packet_discovery。節(jié)點(diǎn) Si+1接收后，將自己的位置信息插入到數(shù)據(jù)包Packet_discovery中，并也依據(jù)網(wǎng)絡(luò)GG，按照右手規(guī)則向邊界節(jié)點(diǎn)Si+2轉(zhuǎn)發(fā)，直到數(shù)據(jù)包Packet_discovery遍歷了空洞邊界，最終傳遞到節(jié)點(diǎn)Si中，才停止轉(zhuǎn)發(fā)數(shù)據(jù)包Packet_discovery。

接收了數(shù)據(jù)包Packet_discovery后，節(jié)點(diǎn)Si從數(shù)據(jù)包中提取邊界節(jié)點(diǎn)｛S0，S1，???，SN｝的位置信息。從中選擇兩個(gè)節(jié)點(diǎn)Sm，Sn，這兩個(gè)節(jié)點(diǎn)間的距離是邊界節(jié)點(diǎn)｛S0，S1，???，SN｝間任意節(jié)點(diǎn)間距離最長的，如式（1）所示。

式中，dist（Sm，Sn）表示節(jié)點(diǎn)Sm，Sn間的歐式距離。

式中：xSm，ySm以及 xSn，ySn分別表示節(jié)點(diǎn)Sm，Sn的二維坐標(biāo)。

1.1.2空洞邊緣

網(wǎng)絡(luò)邊界Network boundary節(jié)點(diǎn)（所有節(jié)點(diǎn)一定是在RoI內(nèi)）執(zhí)行TENT規(guī)則，因此，它們檢測(cè)自己是否為Stuck Nodes。然后，由Stuck Nodes啟動(dòng)空洞檢測(cè)以及空洞修復(fù)階段。

以分布式方式檢測(cè)網(wǎng)絡(luò)邊界，步驟如下：

（1）網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)執(zhí)行TENT規(guī)則；

（2）每個(gè)Stuck Node觸發(fā)空洞發(fā)現(xiàn)階段，識(shí)別空洞邊界節(jié)點(diǎn)；

（3）在數(shù)據(jù)包Packet_discovery中，定義一個(gè)區(qū)域，用于表示Network boundary的最大、最小坐標(biāo) Xmax，Ymax，Xmin，Ymin。每個(gè)Stuck Node接收了數(shù)據(jù)包Pack?et_discovery后，將自己的位置坐標(biāo)與數(shù)據(jù)包Packet_dis?covery中的 Xmax，Ymax，Xmin，Ymin進(jìn)行比較。如果比Xmax，Ymax大，或者比 Xmin，Ymin更小，則替換；

（4）當(dāng)數(shù)據(jù)包Packet_discovery遍歷了空洞后，用數(shù)據(jù)包Packet_discovery存有的 Xmax，Ymax，Xmin，Ymin表示最大空洞的網(wǎng)絡(luò)邊界，空洞半徑r為：

1.2空洞修復(fù)

空洞檢測(cè)后，采用完全分布式的空洞處理算法對(duì)空洞進(jìn)行修復(fù)。提出空洞算法引用了虛力（Virtual Forc?es）概念。為了處理已檢測(cè)到的空洞，在空洞處理區(qū)域（Hole Healing Area，HHA）中定義引力和斥力。引力是空洞中心對(duì)節(jié)點(diǎn)的吸引力，而斥力是指兩節(jié)點(diǎn)間的排斥力，其用于最小化重疊覆蓋區(qū)域。

在空洞處理過程中，從Stuck Nodes中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為空洞主管（Healing Manger，HM），其擔(dān)任決策HHA以及通知節(jié)點(diǎn)的移動(dòng)信息任務(wù)。HM節(jié)點(diǎn)具有空洞的尺寸以及邊緣節(jié)點(diǎn)的所有信息。接下來，分析空洞處理的具體過程。

1.2.1規(guī)劃HHA

識(shí)別了空洞后，HM節(jié)點(diǎn)計(jì)算空洞的中心位置以及尺寸。如上所述，將空洞區(qū)域近似為圓，因此，為了規(guī)劃HHA，需要計(jì)算圓的半徑。

采用基于式（4）的迭代算法近似計(jì)算HHA圓的半徑。

式中：r表示空洞的半徑；β為常數(shù)，其取決于節(jié)點(diǎn)密度和節(jié)點(diǎn)的通信范圍RS。

首先（第一輪迭代，記為HHA?0），令 β=0，規(guī)劃HHA的圓的半徑等于r，那么這個(gè)圓的面積為πr2。則覆蓋區(qū)域πr2所需的節(jié)點(diǎn)數(shù)等于：

然后，HM節(jié)點(diǎn)計(jì)算HHA?0內(nèi)現(xiàn)有節(jié)點(diǎn)數(shù)量。HM節(jié)點(diǎn)請(qǐng)求其一跳鄰居節(jié)點(diǎn)估計(jì)它們?cè)贖HA?0內(nèi)一跳鄰居數(shù)。為此，HM節(jié)點(diǎn)廣播空洞處理區(qū)域估計(jì)（Hole?Healing Region Estimation，HHRE）數(shù)據(jù)包Packet_HHRE，其包含該空洞的信息。如果HM節(jié)點(diǎn)估計(jì)的數(shù)量少于處理該空洞要求的節(jié)點(diǎn)數(shù)，那么這些節(jié)點(diǎn)的移動(dòng)將帶來新的空洞。為了避免新空洞的出現(xiàn)，HM節(jié)點(diǎn)通過增加β開始新一輪估計(jì)鄰居節(jié)點(diǎn)，這個(gè)過程重復(fù)進(jìn)行，直到發(fā)現(xiàn)有足夠多的節(jié)點(diǎn)處理空洞。

估計(jì)了HHA后，HM節(jié)點(diǎn)向相關(guān)節(jié)點(diǎn)發(fā)送移動(dòng)數(shù)據(jù)包Packet_Move，以處理該空洞。接收了該數(shù)據(jù)包，節(jié)點(diǎn)就進(jìn)行了移動(dòng)，調(diào)整位置（Relocation）。

1.2.2節(jié)點(diǎn)Relocation

在計(jì)算HHA后，HM節(jié)點(diǎn)通知相應(yīng)的節(jié)點(diǎn)進(jìn)行移動(dòng)。這些節(jié)點(diǎn)將接收到來自空洞中心的力，并向其移動(dòng)，這個(gè)力包括引力和斥力，如圖2所示。

引力：空洞中心o對(duì)離自己距離大于dath的HHA內(nèi)的每個(gè)節(jié)點(diǎn)產(chǎn)生指向o的推動(dòng)作用。為此，HHA內(nèi)的節(jié)點(diǎn)p接收到來自空洞中心o的引力

圖2HHA內(nèi)節(jié)點(diǎn)移動(dòng)示意圖

接下來，分析節(jié)點(diǎn)的移動(dòng)原則。

式中，Np表示節(jié)點(diǎn)p的鄰居節(jié)點(diǎn)集。

式中V表示節(jié)點(diǎn)移動(dòng)速度。

VF?LMH算法的流程圖，如圖3所示。

2　系統(tǒng)仿真及性能分析

利用仿真軟件NS2對(duì)提出的VF?LMH算法進(jìn)行仿真，并考慮兩個(gè)仿真場(chǎng)景。

第一個(gè)場(chǎng)景用于驗(yàn)證VF?LMH算法空洞檢測(cè)以及空洞處理的能力。第二個(gè)場(chǎng)景用于將提出的VF?LMH算法與DSSA［17］和SMART［18］進(jìn)行性能比較，兩個(gè)場(chǎng)景的仿真參數(shù)如表2所示。

表2　仿真參數(shù)

圖3　VF?LMH算法流程圖

2.1場(chǎng)景1

場(chǎng)景1中，RoI中出現(xiàn)不同位置，并且尺寸變化的空洞，考察提出的VF?LMH算法檢測(cè)空洞以及處理空洞的能力。采用確定性部署（Deterministic Deployment）傳感節(jié)點(diǎn)。首先，產(chǎn)生42 m的兩個(gè)空洞，如圖4（a）所示。經(jīng)VF?LMH檢測(cè)及修復(fù)后結(jié)果如圖4（b）所示?？梢钥闯?，VF?LMH算法能夠有效地檢測(cè)空洞，并且成功地修復(fù)空洞。

2.2場(chǎng)景2

本小節(jié)的仿真，主要考察VF?LMH算法在修復(fù)空洞時(shí)參與移動(dòng)的節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)移動(dòng)的總距離、以及網(wǎng)絡(luò)覆蓋率性能，并與DSSA和SMART進(jìn)行比較。選擇DSSA 和SMART的原因在于：DSSA是基于虛力的集中式移動(dòng)修復(fù)空洞，SMART是基于grid?quorum的移動(dòng)修復(fù)算法，與VF?LMH算法，具有可比性。

圖5顯示了VF?LMH，DSSA以及SMART三個(gè)算法的網(wǎng)絡(luò)覆蓋率隨節(jié)點(diǎn)數(shù)的變化情況。從圖5可知，在節(jié)點(diǎn)數(shù)為200時(shí)，VF?LMH算法的覆蓋率最低。主要是因?yàn)椋涸?00 m×200 m的區(qū)域內(nèi)，隨機(jī)部署200個(gè)節(jié)點(diǎn)，在區(qū)域邊界以及ROI區(qū)域內(nèi)產(chǎn)生了較多的空洞。VF?LMH算法在檢測(cè)到空洞后，沒有足夠節(jié)點(diǎn)修復(fù)空洞。隨著節(jié)點(diǎn)密度提升，VF?LMH算法性能隨之提高，當(dāng)節(jié)點(diǎn)密度達(dá)到較大（350個(gè)節(jié)點(diǎn)），提出的VF?LMH算法優(yōu)于DSSA 和SMART。

圖4　空洞處理過程

圖5　網(wǎng)絡(luò)覆蓋率隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化情況

圖6顯示了VF?LMH，DSSA以及SMART三個(gè)算法在修復(fù)空洞參與節(jié)點(diǎn)移動(dòng)的總距離隨節(jié)點(diǎn)數(shù)的變化情況。從圖6可知，在節(jié)點(diǎn)數(shù)在［200，300］的范圍內(nèi)，VF?LMH算法的移動(dòng)的總距離隨節(jié)點(diǎn)數(shù)的增加而增加。此外，與SMART相比，提出的VF?LMH算法節(jié)點(diǎn)移動(dòng)的總距離更少，而DSSA算法的節(jié)點(diǎn)總移動(dòng)距離隨節(jié)點(diǎn)數(shù)的增加而下降，這主要是因?yàn)橹虚g節(jié)點(diǎn)力迅速下降，節(jié)點(diǎn)的分布區(qū)域更小，相應(yīng)地，節(jié)點(diǎn)覆蓋區(qū)域更小。此外，從圖7可知，節(jié)點(diǎn)數(shù)在［200，300］的范圍內(nèi)，SMART和VF?LMH算法在修復(fù)空洞時(shí)節(jié)點(diǎn)移動(dòng)數(shù)性能相近，但是，當(dāng)節(jié)點(diǎn)數(shù)大于300后，VF?LMH算法的節(jié)點(diǎn)移動(dòng)數(shù)低于SMART。在［200，300］的范圍內(nèi)，VF?LMH算法的平均移動(dòng)的節(jié)點(diǎn)數(shù)為40，SMART算法為160，并且VF?LMH算法的覆蓋率提高了7%（見圖4）。而在這間隔內(nèi)，DSSA獲取了大的覆蓋率（見圖4），但是，其以付出大的移動(dòng)節(jié)點(diǎn)數(shù)（1 200～1 600）。這主要是因?yàn)椋篤F?LMH算法和SMART算法的節(jié)點(diǎn)是定向移動(dòng)。而DSSA中所有節(jié)點(diǎn)依據(jù)虛力原則進(jìn)行移動(dòng)。

上述的仿真結(jié)果表明，VF?LMH算法能夠有效地檢測(cè)空洞、處理空洞，并且提高了網(wǎng)絡(luò)覆蓋率。

圖6　總的移動(dòng)距離隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化情況

圖7　參與移動(dòng)的節(jié)點(diǎn)數(shù)隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化情況

3　結(jié)語

本文提出了檢測(cè)、處理空洞的VF?LMH算法。VF?LMH算法首先利用TENT規(guī)則，檢測(cè)Stuck Nodes，隨后利用這些Stuck Nodes識(shí)別空洞，再利用網(wǎng)絡(luò)的GG圖，檢測(cè)空洞的中心位置以及半徑。然后，規(guī)劃空洞處理區(qū)域HHA，再利用基于虛力局部移動(dòng)算法，計(jì)算HHA內(nèi)節(jié)點(diǎn)所受的力。節(jié)點(diǎn)依據(jù)所受力的作用進(jìn)行移動(dòng)，從而修復(fù)空洞。

仿真結(jié)果表明，提出的VF?LMH算法能夠有效地處理空洞，并與DSSA和SMART相比，VF?LMF算法在網(wǎng)絡(luò)覆蓋率、參與移動(dòng)的節(jié)點(diǎn)數(shù)以及移動(dòng)距離方面占有優(yōu)勢(shì)。

［1］ZITTERBART D，WIENECKE B，BUTLER J，et al.Coordi?nated movements prevent jamming in an emperor penguin hud?dle［J］.PLoS ONE，2011，6（6）：202?216.

［2］XU H，HUANG L，ZHANG Y，et al.Energy?efficient coopera?tive data aggregation for wireless sensor networks［J］.Journal of parallel distrib comput，2010，70（9）：953?961.

［3］EL?MOUKADDEM F，TORNG E，XING G.Maximizing data gathering capacity of wireless sensor networks using mobile re?lays［J］.IEEE MASS，2010（2）：312?321.

［4］夏韻，陳志剛，曾鋒.無線傳感器網(wǎng)絡(luò)中基于MDS?MCC問題的啟發(fā)式算法研究［J］.計(jì)算機(jī)工程與科學(xué)，2013，35（4）：53?58.

［5］AHMED N，KANHERE S S，JHA S.The holes problem in wireless sensor networks：a survey［J］.SIGMOBILE mobile computing comm rev，2005，9（2）：4?18.

［6］CHANG C Y，HUNG L L，SCHAN G W，et al.Decentralized and energy?balanced algorithms for maintaining temporal full?coverage in mobile WSNs［J］.Journal of wireless comm.and mobile computing，2012，12（5）：445?462.

［7］KUN B，KUN T，NAIJIE G，et al.Topological hole detection in sensor networks with cooperative neighbors［C］//Proceedings of International Conference on Systems and Networks Comm.［S. l.：s.n.］，2006：31?40.

［8］GHRIST R，MUHAMMAD A.Coverage and hole?detection in sensor networks via homology［C］//Proceedings of Fourth Inter?national Symposium on Information Processing in Sensor Net?works.［S.l.：s.n.］，2005：254?260.

［9］DE SILVA V，GHRIST R，MUHAMMAD A.Blind swarms for coverage in 2?D［C］//Proceedings of Robotics：Science and Systems.［S.l.：s.n.］，2005：335?342.

［10］F.Stefan.Topological Hole Detection in wireless sensor net?works and its applications［C］//Proceedings of Joint Workshop on Foundations of Mobile Computing.［S.l.：s.n.］，2005：44?53.

［11］STEFAN F，CHRISTIAN K.Hole detection or：how much ge?ometry hides in connectivity［C］//Proceedings of 22nd Ann Symposium on Computational Geometry.［S.l.：s.n.］，2013：377?385.

［12］FEKETE S P，KRCOLLER A，PFISTERER D，et al.Neigh?borhood?based topology recognition in sensor networks［C］//Pro?ceedings of International Workshop on Algorithmic Aspects of Wireless Sensor Networks.［S.l.：s.n.］，2004：123?136.

［13］FEKETE S P，KAUFMANN M，KRCOLLER A，et al.A new approach for boundary recognition in geometric sensor net?works［C］//Proceedings of 17th Canadian Conference on Com?putational Geometry.［S.l.：s.n.］，2012：82?85.

［14］SHIRSAT A，BHARGAVA B.Local geometric algorithm for hole boundary detection in sensor networks［J］.Security and comm networks，2011，4（9）：1003?1012.

［15］FANG Q，GAO J，GUIBAS L J.Locating and bypassing holes in sensor networks［J］.Mobile networks and applica?tions，2011，11（2）：187?200.

［16］SIBLEY G T，RAHIMI M H，SUKHATME G S.Robomote：A tiny mobile robot platform for large?scale ad?hoc sensor net?works［C］//Proceedings of IEEE International Conference on Robotics and Automation.［S.l.：s.n.］，2002：1143?1148.

［17］YONG Z，LI W.A sensor deployment algorithm formobile wireless sensor networks［C］//Proceedings of 21st Ann.Inter?national Conference on Chinese Control and Decision Conf.［S. l.：s.n.］，2010：4642?4647.

［18］YANGY S，LIZ M，WU J.Scan?based movement?assisted sen?sor deployment methods in wireless sensor networks［J］.IEEE transactions on parallel and distributed systems，2010，18 （8）：1108?1121.

Virtual force mobile node based algorithm to heal holes in wireless sensor networks

SONG Xizhong，ZHANG Renzhi
（School of Information Engineering，Huanghuai University，Zhumadian 463000，China）

The emergence of holes in the region of interest（RoI）is unavoidable due to the inherent properties and environ?mental factors of WSNs.Therefore，the virtual forces?based localized movement hole healing（VF?LMH）algorithm is proposed in this paper.The VF?LMF algorithm is operated in two distinct phases：hole detection and hole repair.The VF?LMH algorithm in the phase of detecting hole is to discover the holes，hole center location and size by the localized protocol of Gabriel graph （GG）of network.In the hole repair phase，the hole healing area（HHA）is confirmed first，and then the nodes in HHA are moved according to the virtual force for the hole healing.The simulation results show that the proposed VF?LMH algorithm is able to detect and heal the holes.Compared with the similar algorithms，the cost for hole healing of VF?LMH algorithm is lower because it has less moved nodes and shorter total moving distance.

virtual force；Gabriel graph；interested region；hole healing；wireless sensor network

10.16652/j.issn.1004?373x.2016.14.018

TN926?34；TPT393

A

1004?373X（2016）14?0064?05

2015?12?09

河南省科技廳發(fā)展計(jì)劃（142102110088）

宋喜忠（1977—），男，河南駐馬店人，副教授，碩士。主要從事計(jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)庫方面的研究。

張韌志（1980—），男，河南泌陽人，講師，碩士。主要從事軟件工程開發(fā)、網(wǎng)絡(luò)管理等研究。