胡青松， 范莘舸， 李鶴

（1.中國(guó)礦業(yè)大學(xué) 地下空間智能控制教育部工程研究中心，江蘇 徐州 221116；2.中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116；3.中國(guó)礦業(yè)大學(xué) 徐州市智能安全與應(yīng)急協(xié)同工程研究中心，江蘇 徐州 221116；4.徐州燃燒控制研究院有限公司，江蘇 徐州 221000）

0 引言

煤礦物聯(lián)網(wǎng)通過大量節(jié)點(diǎn)以自組織方式對(duì)井下人、機(jī)、環(huán)境進(jìn)行感知[1]。然而，煤礦災(zāi)害通常會(huì)造成部分節(jié)點(diǎn)損壞，形成網(wǎng)絡(luò)空洞，使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化，可能導(dǎo)致通信中斷，使決策指揮者和救援人員無法及時(shí)了解災(zāi)害現(xiàn)場(chǎng)信息，嚴(yán)重影響應(yīng)急響應(yīng)速度和災(zāi)后救援效果[2]。鑒于此時(shí)仍存在許多殘存的物聯(lián)網(wǎng)節(jié)點(diǎn)（簡(jiǎn)稱殘存節(jié)點(diǎn)）可以工作，若能利用這些節(jié)點(diǎn)及救援人員、救援設(shè)施攜帶的通信終端（簡(jiǎn)稱移動(dòng)節(jié)點(diǎn)）重構(gòu)事故區(qū)域物聯(lián)網(wǎng)[3]，不僅可以修復(fù)網(wǎng)絡(luò)空洞，為不連通的區(qū)域提供連通路徑，而且可為災(zāi)后態(tài)勢(shì)感知及救援工作提供條件。因此，研究災(zāi)后環(huán)境下煤礦物聯(lián)網(wǎng)網(wǎng)絡(luò)空洞的發(fā)現(xiàn)和覆蓋問題具有重要意義。

網(wǎng)絡(luò)空洞覆蓋問題的主流研究方法是通過增加移動(dòng)節(jié)點(diǎn)進(jìn)行修復(fù)。文獻(xiàn)[4]提出了一種基于Voronoi圖及Delaunay三角剖分結(jié)合的改進(jìn)虛擬力算法的高效部署策略，運(yùn)用圖論工具定位網(wǎng)絡(luò)中的覆蓋空洞，通過虛擬力移動(dòng)已部署的節(jié)點(diǎn)，但未考慮災(zāi)后多障礙物的情況。文獻(xiàn)[5]提出了人工勢(shì)場(chǎng)法，可使移動(dòng)節(jié)點(diǎn)在有障礙物的情況下移動(dòng)到需要覆蓋的地點(diǎn)，但當(dāng)斥力范圍大于障礙物半徑時(shí)會(huì)導(dǎo)致障礙物與移動(dòng)節(jié)點(diǎn)碰撞。文獻(xiàn)[6-9]對(duì)人工勢(shì)場(chǎng)法進(jìn)行改進(jìn)，提高了移動(dòng)節(jié)點(diǎn)避障能力和移動(dòng)路徑平滑性，減少了規(guī)劃步數(shù)，但僅適用于有單個(gè)移動(dòng)節(jié)點(diǎn)的簡(jiǎn)單環(huán)境。文獻(xiàn)[10]提出了一種分布式協(xié)調(diào)策略，適用于有多個(gè)移動(dòng)節(jié)點(diǎn)的復(fù)雜環(huán)境，但節(jié)點(diǎn)移動(dòng)后會(huì)出現(xiàn)覆蓋率減小或節(jié)點(diǎn)停留在障礙物邊緣的問題，造成能量浪費(fèi)。

相比于正常情況，災(zāi)后殘存節(jié)點(diǎn)的能量差異較大，部分殘存節(jié)點(diǎn)能量可能過早耗盡而影響整個(gè)網(wǎng)絡(luò)的穩(wěn)定性?，F(xiàn)有的網(wǎng)絡(luò)空洞覆蓋算法未考慮井下災(zāi)后的地理環(huán)境因素，且未對(duì)修復(fù)后的網(wǎng)絡(luò)進(jìn)行優(yōu)化，無法滿足災(zāi)后煤礦物聯(lián)網(wǎng)重構(gòu)需求。本文提出一種煤礦物聯(lián)網(wǎng)災(zāi)后有障礙物情況下的網(wǎng)絡(luò)空洞覆蓋重構(gòu)算法（Network Hole Coverage Reconstruction Algorithm with Obstacles, NHCRA?O），提升了節(jié)點(diǎn)的匹配收斂速度，縮短了節(jié)點(diǎn)移動(dòng)距離，提升了網(wǎng)絡(luò)覆蓋率，延長(zhǎng)了網(wǎng)絡(luò)壽命，在修復(fù)災(zāi)后煤礦物聯(lián)網(wǎng)網(wǎng)絡(luò)空洞方面具有較大優(yōu)勢(shì)。

1 系統(tǒng)建模

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

本文以煤礦井下局部災(zāi)后物聯(lián)網(wǎng)為研究對(duì)象，如圖1所示。節(jié)點(diǎn)分為殘存節(jié)點(diǎn)及救援人員攜帶的移動(dòng)節(jié)點(diǎn)，各節(jié)點(diǎn)初始能量可不相同。假定基站和殘存節(jié)點(diǎn)是靜止的，節(jié)點(diǎn)數(shù)據(jù)能以多跳方式傳輸?shù)交?。各?jié)點(diǎn)通信半徑和感知半徑均相同，彼此之間可通過接收信號(hào)強(qiáng)度值（Received Signal Strength Indicator, RSSI）計(jì)算距離。

圖1 煤礦井下局部災(zāi)后物聯(lián)網(wǎng)Fig.1 Post-disaster Internet of things in coal mine underground

在網(wǎng)絡(luò)重構(gòu)階段，節(jié)點(diǎn)被分為成員節(jié)點(diǎn)和簇頭節(jié)點(diǎn)。成員節(jié)點(diǎn)對(duì)受災(zāi)區(qū)域進(jìn)行動(dòng)態(tài)感知；簇頭節(jié)點(diǎn)接收成員節(jié)點(diǎn)收集的信息，并對(duì)其進(jìn)行壓縮和融合處理后傳遞給下一簇頭節(jié)點(diǎn)。

為不失一般性，將災(zāi)后網(wǎng)絡(luò)用圖模型G=(V,U)表示，其中V為頂點(diǎn)集，U為邊集。V由網(wǎng)絡(luò)中所有節(jié)點(diǎn)集合和障礙物角點(diǎn)集合組成[11]。障礙物信息可通過災(zāi)后移動(dòng)節(jié)點(diǎn)獲取。

1.2 節(jié)點(diǎn)感知模型

假定感知范圍為以殘存節(jié)點(diǎn)為圓心、感知半徑為r的圓形區(qū)域。在網(wǎng)絡(luò)空洞覆蓋問題上，往往由多個(gè)殘存節(jié)點(diǎn)同時(shí)感知某一區(qū)域，本文采用Neyman?Pearson聯(lián)合感知模型來計(jì)算感知概率[12]。殘存節(jié)點(diǎn)Si從目標(biāo)區(qū)域k接收到的信號(hào)強(qiáng)度為

式中：τ為均值為0、標(biāo)準(zhǔn)差為 σ 的高斯噪聲；C0，C1分別為目標(biāo)區(qū)域信號(hào)源未丟失和丟失的情況；η為信號(hào)源能量；di，k為殘存節(jié)點(diǎn)Si與目標(biāo)區(qū)域k之間的距離；λ為信號(hào)衰減指數(shù)，通常取2或4，煤礦災(zāi)后場(chǎng)景中一般取4。

式中Einit為殘存節(jié)點(diǎn)初始能量。

在目標(biāo)區(qū)域信號(hào)源未丟失的情況下，殘存節(jié)點(diǎn)Si的感知概率為

在目標(biāo)區(qū)域信號(hào)源丟失情況下，殘存節(jié)點(diǎn)Si的感知概率為

根據(jù)Neyman?Pearson聯(lián)合感知模型可得，殘存節(jié)點(diǎn)Si對(duì)目標(biāo)區(qū)域k的感知概率為

式中： Φ (·)為標(biāo)準(zhǔn)正態(tài)分布累積分布函數(shù)；δmin為 最小誤警率。

在實(shí)際感知過程中，目標(biāo)區(qū)域k可能同時(shí)被周圍W個(gè)殘存節(jié)點(diǎn)感知，因此，目標(biāo)區(qū)域k的聯(lián)合感知概率為

當(dāng)Pk<0.3時(shí)，認(rèn)定該目標(biāo)區(qū)域?yàn)榭斩磪^(qū)域。

整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率為

式中：Acov為所有殘存節(jié)點(diǎn)覆蓋面積；A為所有區(qū)域（包含障礙物）面積。

考慮到障礙物的存在，假設(shè)c>0.85 時(shí)整個(gè)監(jiān)測(cè)區(qū)域獲得有效覆蓋，具體取值可調(diào)節(jié)。

2 災(zāi)后煤礦物聯(lián)網(wǎng)網(wǎng)絡(luò)空洞覆蓋重構(gòu)

NHCRA?O基本思想：首先，利用Delaunay三角剖分對(duì)殘存節(jié)點(diǎn)及障礙物角點(diǎn)進(jìn)行區(qū)域劃分，進(jìn)而利用節(jié)點(diǎn)感知模型判斷區(qū)域內(nèi)是否存在網(wǎng)絡(luò)空洞；其次，計(jì)算Delaunay三角形質(zhì)心位置，利用質(zhì)心和Delaunay三角形頂點(diǎn)之間的距離確定虛擬修復(fù)節(jié)點(diǎn)位置；再次，計(jì)算移動(dòng)節(jié)點(diǎn)的優(yōu)先級(jí)，并與虛擬修復(fù)節(jié)點(diǎn)進(jìn)行可視化判斷與匹配，根據(jù)匹配結(jié)果修復(fù)網(wǎng)絡(luò)空洞；最后，融合剩余能量因子、節(jié)點(diǎn)連通度和方向介數(shù)計(jì)算節(jié)點(diǎn)優(yōu)先級(jí)，根據(jù)優(yōu)先級(jí)選舉簇頭節(jié)點(diǎn)，其他成員節(jié)點(diǎn)就近入簇，形成新的重構(gòu)網(wǎng)絡(luò)。

2.1 虛擬修復(fù)節(jié)點(diǎn)位置確定

以圖2所示物聯(lián)網(wǎng)網(wǎng)絡(luò)空洞為例進(jìn)行NHCRA?O說明。S1?S12為殘存節(jié)點(diǎn)，O1?O4為障礙物角點(diǎn)。S1?S10構(gòu)成一個(gè)網(wǎng)絡(luò)空洞。由S1?S10，O1?O4構(gòu)成頂點(diǎn)集V={S1，S2，…，S10，O1，O2，O3，O4}={Vp}（p=1，2，…，14）。

圖2 物聯(lián)網(wǎng)網(wǎng)絡(luò)空洞Fig.2 Network hole in Internet of things

對(duì)V進(jìn)行Delaunay三角剖分，得到Delaunay三角形修復(fù)模型，如圖3所示。

圖3 Delaunay 三角形修復(fù)模型Fig.3 Delaunay triangle repair model

計(jì)算Delaunay三角形質(zhì)心Q的位置（x，y）：

式中（xp，yp）為 Delaunay三角形頂點(diǎn)位置。

計(jì)算Delaunay三角形頂點(diǎn)V1與Q的距離dV1,Q。根據(jù)三點(diǎn)最優(yōu)覆蓋模型，若dV1,Q大 √于殘存節(jié)點(diǎn)感知半徑r，則在V1與Q連線上距離Q3r處放置修復(fù)節(jié)點(diǎn)I1，這樣可使I1覆蓋范圍與相鄰Delaunay三角形的重疊面積最小，達(dá)到最佳覆蓋效果。實(shí)際放置修復(fù)節(jié)點(diǎn)時(shí)會(huì)對(duì)其位置做進(jìn)一步優(yōu)化，所以這里將I1稱為虛擬修復(fù)節(jié)點(diǎn)。

對(duì)Delaunay三角形頂點(diǎn)V2，V3重復(fù)上述操作，完成該Delaunay三角形區(qū)域空洞覆蓋。其他Delaunay三角形空洞區(qū)域覆蓋過程與此相同。

2.2 基于優(yōu)先級(jí)的雙向匹配

通過上述過程可確定虛擬修復(fù)節(jié)點(diǎn)I的位置。實(shí)際用于修復(fù)的移動(dòng)節(jié)點(diǎn)M會(huì)與其進(jìn)行匹配，從而確定修復(fù)節(jié)點(diǎn)最終位置。由于災(zāi)后障礙物的存在，虛擬修復(fù)節(jié)點(diǎn)位置與實(shí)際部署位置存在偏差，同時(shí)移動(dòng)節(jié)點(diǎn)到達(dá)虛擬修復(fù)節(jié)點(diǎn)位置過程中存在因躲避障礙物導(dǎo)致移動(dòng)路徑過長(zhǎng)或無法到達(dá)指定位置等問題，需要對(duì)虛擬修復(fù)節(jié)點(diǎn)進(jìn)行可視化判斷。

依次連接障礙物角點(diǎn)，得到一組邊集U。若線段與邊集U沒有交點(diǎn)，則認(rèn)為該移動(dòng)節(jié)點(diǎn)與虛擬修復(fù)節(jié)點(diǎn)直接可視，將二者的匹配狀態(tài)記為可視，反之記為非可視。在匹配過程中，直接可視的移動(dòng)節(jié)點(diǎn)會(huì)優(yōu)先得到虛擬修復(fù)節(jié)點(diǎn)的匹配邀約，若虛擬修復(fù)節(jié)點(diǎn)周圍無直接可視移動(dòng)節(jié)點(diǎn)，則對(duì)非可視節(jié)點(diǎn)發(fā)出匹配邀約。

虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)基于雙向匹配策略進(jìn)行匹配。移動(dòng)節(jié)點(diǎn)基于閾值 κ對(duì)虛擬修復(fù)節(jié)點(diǎn)進(jìn)行匹配優(yōu)先級(jí)排序，κ越大，則優(yōu)先級(jí)越高。

式中：a1，b1為權(quán)重因子，a1+b1=1；κ1為虛擬修復(fù)節(jié)點(diǎn)距障礙物的距離優(yōu)先級(jí)，κ1越小，則虛擬修復(fù)節(jié)點(diǎn)距離障礙物越近；κ2為虛擬修復(fù)節(jié)點(diǎn)附近節(jié)點(diǎn)剩余能量因子， κ2越小，則對(duì)虛擬修復(fù)節(jié)點(diǎn)的需求度越高，對(duì)于災(zāi)后井下環(huán)境來說，需求度越高，則匹配優(yōu)先級(jí)越高；dI,Om為虛擬修復(fù)節(jié)點(diǎn)距最近障礙物Om的距離；dmin，dmax分別為網(wǎng)絡(luò)中虛擬修復(fù)節(jié)點(diǎn)和障礙物之間的最小距離和最大距離；Ecnow為構(gòu)成Delaunay三角形的殘存節(jié)點(diǎn)當(dāng)前平均能量；Ecavg，Emax，Emin分別為當(dāng)前網(wǎng)絡(luò)中殘存節(jié)點(diǎn)的平均能量、最大能量和最小能量。

虛擬修復(fù)節(jié)點(diǎn)基于閾值 ω 對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行匹配優(yōu)先級(jí)排序，ω越大，則優(yōu)先級(jí)越高。

式中：a2，b2為權(quán)重因子，a2+b2=1； ω1為移動(dòng)節(jié)點(diǎn)與虛擬修復(fù)節(jié)點(diǎn)的距離因子， ω1越小，則匹配優(yōu)先級(jí)越高； ω2為移動(dòng)節(jié)點(diǎn)現(xiàn)有能量因子， ω2越大，則匹配優(yōu)先級(jí)越高；dM,I為虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)的距離；N為當(dāng)前移動(dòng)節(jié)點(diǎn)可移動(dòng)范圍內(nèi)的虛擬修復(fù)節(jié)點(diǎn)數(shù)；dM,Ij為當(dāng)前移動(dòng)節(jié)點(diǎn)與其可移動(dòng)范圍內(nèi)虛擬修復(fù)節(jié)點(diǎn)Ij的距離；Emnow為當(dāng)前移動(dòng)節(jié)點(diǎn)的剩余能量；Emavg，Emmax，Emmin分別為網(wǎng)絡(luò)中所有移動(dòng)節(jié)點(diǎn)的平均能量、最大能量和最小能量。

本文基于Gale?Shapley算法[13]進(jìn)行虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)雙向匹配，其是基于穩(wěn)定匹配策略而設(shè)計(jì)的貪心算法。1個(gè)虛擬修復(fù)節(jié)點(diǎn)可能會(huì)同時(shí)向多個(gè)移動(dòng)節(jié)點(diǎn)發(fā)出匹配邀約，而1個(gè)移動(dòng)節(jié)點(diǎn)可能同時(shí)收到多個(gè)虛擬修復(fù)節(jié)點(diǎn)的匹配邀約。發(fā)出匹配邀約的次數(shù)越多，則能耗越大。考慮到災(zāi)后節(jié)點(diǎn)能量寶貴，對(duì)參與雙向匹配的節(jié)點(diǎn)進(jìn)行預(yù)剪枝處理，即虛擬修復(fù)節(jié)點(diǎn)根據(jù)自身計(jì)算的優(yōu)先級(jí)對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行排序，刪除后1/4結(jié)果，只對(duì)排序前3/4的節(jié)點(diǎn)發(fā)出匹配邀約。以圖4為例，虛擬修復(fù)節(jié)點(diǎn)I1根據(jù)計(jì)算的優(yōu)先級(jí)排序刪除后1/4數(shù)據(jù)，向優(yōu)先級(jí)處于前3/4的移動(dòng)節(jié)點(diǎn)M1，M2，M3發(fā)出匹配邀約，收到匹配邀約的移動(dòng)節(jié)點(diǎn)根據(jù)自身計(jì)算結(jié)果選擇優(yōu)先級(jí)最高的虛擬修復(fù)節(jié)點(diǎn)進(jìn)行匹配，從而加快NHCRA?O收斂速度。

圖4 虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)匹配過程Fig.4 Matching process between virtual repair node and mobile mode

2.3 網(wǎng)絡(luò)重構(gòu)

經(jīng)移動(dòng)節(jié)點(diǎn)修復(fù)空洞后的網(wǎng)絡(luò)僅實(shí)現(xiàn)了簡(jiǎn)單連通，節(jié)點(diǎn)位置并非最優(yōu)，需對(duì)其進(jìn)行重構(gòu)處理，從而優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。本文采用層次性網(wǎng)絡(luò)優(yōu)化結(jié)構(gòu)，綜合剩余能量因子、節(jié)點(diǎn)連通度和方向介數(shù)計(jì)算節(jié)點(diǎn)優(yōu)先級(jí)，根據(jù)優(yōu)先級(jí)選舉簇頭節(jié)點(diǎn)[14]。

（1） 剩余能量因子。簇頭節(jié)點(diǎn)將承擔(dān)更多的數(shù)據(jù)收發(fā)任務(wù)，因此應(yīng)盡量將剩余能量高的節(jié)點(diǎn)選為簇頭節(jié)點(diǎn)。定義剩余能量因子e為當(dāng)前節(jié)點(diǎn)能量Enow與網(wǎng)絡(luò)中節(jié)點(diǎn)能量均值Eavg的比值。

節(jié)點(diǎn)剩余能量采用文獻(xiàn)[15]中的能耗模型進(jìn)行計(jì)算。

式中：Etx為節(jié)點(diǎn)發(fā)送數(shù)據(jù)能耗；l為數(shù)據(jù)包大小；Eelec為轉(zhuǎn)發(fā)大小為l的數(shù)據(jù)所消耗的能量； εfs，εamp分別為自由空間和多徑衰落空間下的功率放大系數(shù)；d為收發(fā)節(jié)點(diǎn)之間的距離；d0為臨界距離，Erx為節(jié)點(diǎn)接收數(shù)據(jù)能耗。

dd0時(shí)采用多徑衰落空間能耗模型。

（2） 節(jié)點(diǎn)連通度。為均衡網(wǎng)絡(luò)能耗，節(jié)點(diǎn)密集的區(qū)域應(yīng)增加簇頭節(jié)點(diǎn)數(shù)量，減小簇的規(guī)模，而節(jié)點(diǎn)稀疏區(qū)域則與之相反。定義節(jié)點(diǎn)連通度n為鄰居節(jié)點(diǎn)數(shù)Nnei與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)Ntotal的比值：

（3） 方向介數(shù)。方向介數(shù)表示某節(jié)點(diǎn)通過最短路徑到達(dá)目標(biāo)節(jié)點(diǎn)的橋接次數(shù)，方向介數(shù)越大，則該節(jié)點(diǎn)承擔(dān)的收發(fā)數(shù)據(jù)任務(wù)越重。

式中：D為節(jié)點(diǎn)方向介數(shù)；Gother為網(wǎng)絡(luò)中除目標(biāo)節(jié)點(diǎn)外的其他節(jié)點(diǎn)集合；gh,q(t)為t時(shí)刻從節(jié)點(diǎn)q經(jīng)過節(jié)點(diǎn)h到達(dá)目標(biāo)節(jié)點(diǎn)的最短路徑數(shù)；gq(t)為t時(shí)刻從節(jié)點(diǎn)q到達(dá)目標(biāo)節(jié)點(diǎn)的最短路徑數(shù)；Nother為網(wǎng)絡(luò)中除目標(biāo)節(jié)點(diǎn)外其他節(jié)點(diǎn)總數(shù)。

綜合上述3個(gè)指標(biāo)，得到簇頭選舉優(yōu)先級(jí)：

式中 α，β， χ 為權(quán)重因子，α + β+χ=1。

節(jié)點(diǎn)的 ρ 越大，則當(dāng)選為簇頭的概率越大。完成簇頭節(jié)點(diǎn)選舉后，其他節(jié)點(diǎn)依據(jù)就近原則加入簇。待網(wǎng)絡(luò)中所有節(jié)點(diǎn)都成為簇頭或加入某個(gè)簇后，網(wǎng)絡(luò)重構(gòu)結(jié)束。

3 仿真與結(jié)果分析

采用Matlab2016a仿真軟件驗(yàn)證NHCRA?O性能。虛擬修復(fù)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)匹配優(yōu)先級(jí)的權(quán)重因子a1=a2=0.6，b1=b2=0.4，簇頭選舉的權(quán)重因子α=0.7，β=χ=0.15，其余參數(shù)設(shè)置見表1。

表1 網(wǎng)絡(luò)空洞覆蓋重構(gòu)仿真參數(shù)Table 1 Simulation parameters of network hole coverage and reconstruction

網(wǎng)絡(luò)空洞修復(fù)前后節(jié)點(diǎn)位置分布如圖5所示，其中多邊形區(qū)域?yàn)檎系K物。在障礙物的干擾下，殘存節(jié)點(diǎn)隨機(jī)部署形成網(wǎng)絡(luò)覆蓋空洞，通過移動(dòng)節(jié)點(diǎn)進(jìn)行修復(fù)。

圖5 網(wǎng)絡(luò)空洞修復(fù)前后節(jié)點(diǎn)位置分布Fig.5 Node position distribution before and after network hole repair

NHCRA?O與 Gale?Shapley算法的匹配效率比較如圖6所示?？煽闯鯣ale?Shapley算法經(jīng)歷86次匹配后完成移動(dòng)節(jié)點(diǎn)與虛擬修復(fù)節(jié)點(diǎn)的匹配工作，而NHCRA?O只需59次匹配，較Gale?Shapley算法減少31.4%。其原因在于，Gale?Shapley算法是基于穩(wěn)定匹配策略而設(shè)計(jì)的貪心算法，而NHCRA?O算法通過可視化判斷，基于距離因子和能量因子對(duì)虛擬修復(fù)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)進(jìn)行雙向匹配，同時(shí)采用預(yù)剪枝處理，剪去了后1/4的匹配數(shù)據(jù)，從而加快了匹配速度。

圖6 虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)匹配效率Fig.6 Matching efficiency of virtual repair node and mobile node

NHCRA?O 與 C?V 算法[12]、PSO（Particle Swarm Optimization，粒子群優(yōu)化）算法[16]的網(wǎng)絡(luò)覆蓋效率對(duì)比如圖7所示。從圖7（a）可看出，NHCRA?O網(wǎng)絡(luò)覆蓋率隨移動(dòng)節(jié)點(diǎn)的增多而迅速提升，原因是其通過Delaunay三角剖分鎖定網(wǎng)絡(luò)空洞區(qū)域，并利用雙向匹配策略為網(wǎng)絡(luò)空洞選取最優(yōu)修復(fù)節(jié)點(diǎn)。當(dāng)移動(dòng)節(jié)點(diǎn)超過25個(gè)時(shí)，網(wǎng)絡(luò)覆蓋率趨于穩(wěn)定，約為90%。C?V算法和PSO算法需要35個(gè)移動(dòng)節(jié)點(diǎn)才能使覆蓋率進(jìn)入穩(wěn)定狀態(tài)。此外，無論是算法執(zhí)行過程中還是穩(wěn)定狀態(tài)下，NHCRA?O的網(wǎng)絡(luò)覆蓋率均大于其他2種算法。從圖7（b）可看出，NHCRA?O的節(jié)點(diǎn)平均移動(dòng)距離明顯小于其他2種算法，這歸功于NHCRA?O進(jìn)行了可視化判斷，并基于能量因子和距離因子挑選最優(yōu)修復(fù)節(jié)點(diǎn)。

圖7 網(wǎng)絡(luò)覆蓋效率對(duì)比Fig.7 Comparison of network coverage efficiency

重構(gòu)網(wǎng)絡(luò)的生存時(shí)間隨節(jié)點(diǎn)數(shù)量變化情況如圖8 所示?？煽闯雠c SEP（Sequential Exchange Protocol，按先后順序交換）算法[14]、LEACH（Low Energy Adaptive Clustering Hierarchy）算法[15]相比，經(jīng)NHCRA?O修復(fù)空洞后，網(wǎng)絡(luò)生存時(shí)間明顯高于其他2種算法，原因在于NHCRA?O不但直接將剩余能量考慮在內(nèi)，還考慮了網(wǎng)絡(luò)連通情況和方向介數(shù)，從而大幅提高了網(wǎng)絡(luò)壽命。

圖8 網(wǎng)絡(luò)生存時(shí)間對(duì)比Fig.8 Comparison of network time-to-live

4 結(jié)論

（1） 針對(duì)災(zāi)后煤礦物聯(lián)網(wǎng)因節(jié)點(diǎn)損毀和障礙物遮擋出現(xiàn)的網(wǎng)絡(luò)空洞問題，提出了NHCRA?O。該算法通過可視化判斷與雙向匹配策略，對(duì)虛擬修復(fù)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)進(jìn)行匹配，并引入剩余能量因子、節(jié)點(diǎn)連通度及方向介數(shù)對(duì)修復(fù)后的網(wǎng)絡(luò)進(jìn)行重構(gòu)。

（2） 采用 Matlab2016a 軟件進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明NHCRA?O在匹配效率、網(wǎng)絡(luò)覆蓋效率和網(wǎng)絡(luò)生存時(shí)間等方面均表現(xiàn)出良好的性能。

（3） 在后續(xù)研究中，計(jì)劃將 NHCRA?O 與災(zāi)后實(shí)測(cè)數(shù)據(jù)采集融合，研發(fā)可修復(fù)網(wǎng)絡(luò)空洞和重構(gòu)網(wǎng)絡(luò)的救災(zāi)機(jī)器人，用于指導(dǎo)礦井災(zāi)害救援實(shí)踐。