胡青松， 王勝男

(1.中國礦業(yè)大學 地下空間智能控制教育部工程研究中心， 江蘇 徐州 221116； 2.中國礦業(yè)大學 信息與控制工程學院， 江蘇 徐州 221116； 3.中國礦業(yè)大學 徐州市智能安全與應急協(xié)同工程研究中心， 江蘇 徐州 221116)

0 引言

煤礦巷道中部署有大量有線通信網(wǎng)絡和無線通信節(jié)點，它們是地面與井下的信息傳遞橋梁，對于保障煤礦安全高效生產(chǎn)至關重要。在災害情況下，這些通信設施常受到不同程度的破壞，導致原有網(wǎng)絡拓撲損毀，無法快速準確感知、傳輸災情信息，使得救援工作難以開展或效率不高[1]。但此時仍有許多殘存節(jié)點可繼續(xù)工作，若能利用殘存節(jié)點和救援人員新布設的少量節(jié)點(簡稱新設節(jié)點)重構應急通信網(wǎng)絡，不但能夠感知災害現(xiàn)場態(tài)勢，而且可為確定受困人員位置提供條件[2]。其中，通過構造局部虛擬骨干網(wǎng)以輔助重構礦山救援網(wǎng)絡(Coal Mine Rescue Network，CMRN)[3]能夠顯著降低網(wǎng)絡能量開銷，增強連通覆蓋控制能力。

礦井通信系統(tǒng)通常包括1個骨干網(wǎng)、多個分支、若干專線。CMRN重構的目的是利用無線重構手段恢復網(wǎng)絡連通。需要說明的是，本文中虛擬骨干網(wǎng)與礦井通信系統(tǒng)中的骨干網(wǎng)概念不同。它是一種基于支配集的重構方法，旨在建立一種分層的拓撲關系，負責全網(wǎng)的路由分發(fā)和管理，使一些原本由有線骨干網(wǎng)處理的網(wǎng)絡功能轉(zhuǎn)為由無線通信節(jié)點來維護，從而恢復該部分網(wǎng)絡的連通性。虛擬骨干網(wǎng)的主要研究工具是圖論中的連通支配集(Connected Dominating Set，CDS)[4]。顧劍峰等[5]提出了一種基于代數(shù)連通度的虛擬骨干網(wǎng)構造算法，其核心是維護虛擬骨干網(wǎng)的穩(wěn)定性。閻新芳等[6]采用獨立支配集為移動自組織網(wǎng)絡(Mobile Ad-hoc Network，MANET)快速重構骨干網(wǎng)，重構網(wǎng)絡具有自恢復能力，同時針對簇頭間長距離傳輸導致能量消耗過大問題，進一步提出了一種基于多級簇樹的虛擬骨干網(wǎng)構造算法。

在外部環(huán)境大幅改變(如發(fā)生事故)致使信道條件惡化情況下，如何維護網(wǎng)絡有效性仍是一大挑戰(zhàn)。當?shù)V井發(fā)生事故后，煤礦巷道中的通信節(jié)點發(fā)生移位或失效，部分通信鏈路損壞，殘存節(jié)點間平均通信距離增大、分布呈不均勻性，網(wǎng)絡連通性急劇惡化。該情況下在部分區(qū)域仍有可能利用殘存節(jié)點有效構造虛擬骨干網(wǎng),以輔助恢復CMRN連通性。為此，本文提出一種基于多維度虛擬骨干網(wǎng)構造的煤礦井下無線自組網(wǎng)災后重構算法，在部分網(wǎng)絡設施損毀情況下，最大限度地恢復該部分網(wǎng)絡的連通性，為災后搶險救援提供通信保障。

1 問題模型

假設煤礦災后局部受損區(qū)域為一個矩形空間。該區(qū)域內(nèi)有1個目標節(jié)點和n個可用節(jié)點(包括殘存節(jié)點與新設節(jié)點)，如圖1所示。每個節(jié)點具有唯一的ID，目標節(jié)點ID為0，可用節(jié)點ID為i(i=1，2，…，n)。各節(jié)點初始能量不同且能量受限。假設可用節(jié)點具有相同的傳輸半徑，各節(jié)點可根據(jù)接收信號強度指示(Received Signal Strength Indication，RSSI)計算節(jié)點間距離。

圖1 煤礦災后無線自組網(wǎng)Fig.1 Wireless ad hoc network after coal mine disaster

可用節(jié)點在網(wǎng)絡重構過程中被分為感知節(jié)點、統(tǒng)治節(jié)點和中繼節(jié)點3類。感知節(jié)點負責感知災害區(qū)域態(tài)勢信息。統(tǒng)治節(jié)點接收其通信范圍內(nèi)感知節(jié)點傳遞的信息，融合壓縮后傳輸給下一跳中繼節(jié)點，構成虛擬骨干網(wǎng)[7]。網(wǎng)絡以周期性方式工作，完成虛擬骨干網(wǎng)構造、數(shù)據(jù)收集與轉(zhuǎn)發(fā)工作。

CDS用簡單無向圖G=(V,F)表示，其中V為可用節(jié)點集合，F(xiàn)為節(jié)點之間的連通邊集[8]。設D為G的一個非空子集，對于G中的任一頂點v，若滿足v屬于D或與D中的1個頂點相鄰，則D稱為G的支配集。如果由D導出的子圖為連通圖，則D稱為連通支配集。D中的節(jié)點稱為統(tǒng)治節(jié)點(支配節(jié)點)，不屬于D的節(jié)點稱為成員節(jié)點(被支配節(jié)點)。

2 虛擬骨干網(wǎng)構造指標

因事故而損壞的通信節(jié)點或鏈路，其位置具有隨機性[9]，可用節(jié)點在進行網(wǎng)絡連通性恢復時重要程度存在差異，需要對可用節(jié)點的重要性進行評估。本文提出以無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)介數(shù)中心度[10]、節(jié)點緊密度[9]為基礎，輔以節(jié)點剩余能量篩選機制的多維度綜合評價指標。構造虛擬骨干網(wǎng)時，順序選取綜合評價指標大的節(jié)點作為統(tǒng)治節(jié)點，以增強局部重構網(wǎng)絡的魯棒性，延長網(wǎng)絡壽命。

2.1 WSN介數(shù)中心度

如果某個節(jié)點被較多的最短路徑經(jīng)過，那么該節(jié)點在數(shù)據(jù)傳輸中的作用較重要。采用WSN介數(shù)中心度來描述這一特性。節(jié)點i的WSN介數(shù)中心度為

(1)

式中：nk(i)為任意可用節(jié)點k(k=1，2，…，n，k≠i)到目標節(jié)點最短路徑中經(jīng)過節(jié)點i的條數(shù)；nk為節(jié)點k到目標節(jié)點最短路徑的條數(shù)。

2.2 節(jié)點緊密度

不同于尋常的WSN節(jié)點分布，局部災后可用節(jié)點分布通常呈現(xiàn)聚集性或稀疏性，節(jié)點緊密度反映了這一特性。節(jié)點緊密度用于表征某節(jié)點通過網(wǎng)絡到達其他節(jié)點的難易程度，以此衡量節(jié)點的重要性，定義為該節(jié)點到達所有其他節(jié)點的距離之和的倒數(shù)。節(jié)點i的緊密度為

(2)

式中dij為節(jié)點i，j之間的距離。

2.3 多維度綜合評價指標

WSN介數(shù)中心度和節(jié)點緊密度只考慮了節(jié)點某方面的重要性，本文將這2種指標與節(jié)點剩余能量篩選機制結合，得到多維度綜合評價指標，步驟如下。

(1) 構建指標矩陣：

(3)

式中xir為節(jié)點i的第r項指標，r=1,2,…,h,h為評價指標數(shù)，本文中h=3,r=1表示W(wǎng)SN介數(shù)中心度，r=2表示節(jié)點緊密度，r=3表示節(jié)點剩余能量。

(2) 歸一化處理。虛擬骨干網(wǎng)評價指標越大，越有益于重構網(wǎng)絡的健壯性，因此對指標矩陣中的元素進行正向歸一化處理。

(4)

(3) 指標變異性處理。以標準差體現(xiàn)指標的變異性，標準差越大則指標差異越大，反映出的信息越多，該指標本身的評價強度越大，應該給該指標分配更大的權重。第r項指標的標準差為

(5)

(4) 構建多維度綜合評價指標。設Rmr為第m，r項指標之間的相關系數(shù)，m=1,2,…,h，則第r項指標用于指標沖突性分析的相關系數(shù)為

(6)

指標相關系數(shù)越大，則該指標與其他指標的相關性越強、沖突性越小，反映出的相同信息越多，所評價內(nèi)容越有重復之處，應在一定程度上削弱該指標的評價強度，減小該指標分配的權重。

綜合指標的標準差和相關系數(shù)，構建第r項指標的信息量：

(7)

cr越大，則第r項指標在整個評價指標體系中的作用越大，應給其分配更大的權重。

第r項指標的客觀權重為

(8)

礦井災后節(jié)點i的多維度綜合評價指標為

Hi=W1Mi+W2Ci+W3Ei

(9)

式中Ei為節(jié)點剩余能量。

經(jīng)過處理后的指標權重Wr為正向指標，即Hi越大，節(jié)點i當選為統(tǒng)治節(jié)點的優(yōu)先級越高。

3 虛擬骨干網(wǎng)構造過程

3.1 初始階段

初始階段礦井局部區(qū)域所有可用節(jié)點都為普通節(jié)點(感知節(jié)點)。設置20個可用節(jié)點隨機分布于巷道中，如圖2所示。虛擬骨干網(wǎng)構造過程將經(jīng)歷若干輪統(tǒng)治節(jié)點選舉，每一輪根據(jù)多維度綜合評價指標選舉出合適的統(tǒng)治節(jié)點并更新支配集，直至網(wǎng)絡呈現(xiàn)收斂狀態(tài)[11]。

圖2 虛擬骨干網(wǎng)構造初始狀態(tài)Fig.2 The initial state of virtual backbone network construction

統(tǒng)治節(jié)點選舉步驟如下。

(1) 各節(jié)點與1跳內(nèi)鄰居節(jié)點交互ID和綜合評價指標，生成1跳鄰居列表Neighbour_hop1。Neighbour_hop1內(nèi)各節(jié)點再與其1跳內(nèi)鄰居節(jié)點交互信息，生成2跳鄰居列表Neighbour_hop2。

(2) 在第1次統(tǒng)治節(jié)點選舉過程中，綜合評價指標最大的節(jié)點傳輸半徑內(nèi)ID最小的節(jié)點被選舉為初始統(tǒng)治節(jié)點，其廣播自身成為統(tǒng)治節(jié)點的信息。

(3) 收到該信息的感知節(jié)點將自身設置為被支配節(jié)點，并廣播自身成為被支配節(jié)點的信息，不參與下一次統(tǒng)治節(jié)點的選舉。

(4) 其余節(jié)點重復上述步驟，直至各節(jié)點通信范圍內(nèi)不存在孤立的感知節(jié)點。

圖2中的各節(jié)點與其通信范圍內(nèi)的鄰居節(jié)點交互自身ID和綜合評價指標，經(jīng)過多次選舉后，節(jié)點3，5，8，9，14，18當選為統(tǒng)治節(jié)點，處于其通信范圍內(nèi)的其他節(jié)點為感知節(jié)點，如圖3所示。初始階段結束后通過該選舉方式產(chǎn)生的統(tǒng)治節(jié)點可覆蓋全部可用節(jié)點。

3.2 支配集連接階段

在支配集連接階段，虛擬骨干網(wǎng)篩選支配節(jié)點并為各支配節(jié)點建立連接，形成連通支配集。具體步驟如下。

圖3 統(tǒng)治節(jié)點選舉Fig.3 Election of dominant nodes

(1) 各感知節(jié)點監(jiān)測Neighbour_hop1內(nèi)的初始統(tǒng)治節(jié)點數(shù)量，如大于1，即該節(jié)點位于2個或2個以上統(tǒng)治節(jié)點覆蓋范圍的交集內(nèi)，則該節(jié)點被選為候選中繼節(jié)點，否則距離2個不相交統(tǒng)治節(jié)點最近的感知節(jié)點被選為候選中繼節(jié)點。

(2) 經(jīng)步驟(1)篩選出的候選中繼節(jié)點可能有多個，將處于交集內(nèi)的候選中繼節(jié)點根據(jù)綜合評價指標排序，指標最大的節(jié)點被選為中繼節(jié)點，其他候選中繼節(jié)點退化為感知節(jié)點。

(3) 其余感知節(jié)點選擇距離自身最近的統(tǒng)治節(jié)點加入其統(tǒng)治集合，向其發(fā)送數(shù)據(jù)。

(4) 各統(tǒng)治節(jié)點與其通信范圍內(nèi)的統(tǒng)治節(jié)點或中繼節(jié)點建立虛擬骨干網(wǎng)鏈路，將采集數(shù)據(jù)以多跳形式傳輸至目標節(jié)點。

(5) 考慮到生成的虛擬骨干網(wǎng)可能存在閉合回路，引入Dijkstra算法[12]在網(wǎng)絡中生成較優(yōu)的樹形多跳網(wǎng)絡結構。

考慮統(tǒng)治節(jié)點長期處于工作狀態(tài)，能耗較大，而被統(tǒng)治節(jié)點具有間歇性休眠模式，且只需與所屬的統(tǒng)治節(jié)點通信，能耗較小，因此設置1個能量閾值，當統(tǒng)治節(jié)點能量低于閾值時觸發(fā)重新選舉過程，選舉出的新統(tǒng)治節(jié)點接替自身后主動退出連通支配集，避免因能量耗盡死亡而造成更大的網(wǎng)絡空洞。

中繼節(jié)點選舉如圖4所示。節(jié)點6處于統(tǒng)治節(jié)點9，14的支配范圍內(nèi)，且該范圍只有其1個節(jié)點可承擔中繼節(jié)點角色，因此當選為中繼節(jié)點。而統(tǒng)治節(jié)點8，14支配范圍內(nèi)的節(jié)點2，7，13，17，20均可作為候選中繼節(jié)點，因此選取綜合評價指標最大的節(jié)點20作為中繼節(jié)點，其他節(jié)點退化為感知節(jié)點。

選舉出中繼節(jié)點后，退化為感知節(jié)點的節(jié)點2，7加入距離自身較近的統(tǒng)治節(jié)點14，成為其成員節(jié)點，節(jié)點13，17成為統(tǒng)治節(jié)點8的成員節(jié)點，如圖5所示。類似地，節(jié)點4成為統(tǒng)治節(jié)點3的成員節(jié)點，節(jié)點1成為統(tǒng)治節(jié)點5的成員節(jié)點。各統(tǒng)治節(jié)點、中繼節(jié)點之間建立連接，將收集的災情數(shù)據(jù)傳輸至目標節(jié)點。

圖4 中繼節(jié)點選舉Fig.4 Election of relay nodes

圖5 虛擬骨干網(wǎng)構造完成Fig.5 Finished virtual backbone network construction

4 虛擬骨干網(wǎng)能耗分析

4.1 節(jié)點能耗模型

采用文獻[13]中的一階無線電能耗模型分析虛擬骨干網(wǎng)能耗。節(jié)點能耗由發(fā)射電路損耗和功率放大損耗組成。設置距離閾值d0，當節(jié)點通信距離小于d0時采用自由空間模型，否則使用多徑衰落模型。

(10)

式中εfs，εamp分別為自由空間模型和多徑衰落模型的功率放大損耗。

節(jié)點發(fā)送能耗為

(11)

式中：s為數(shù)據(jù)長度；Eelec為節(jié)點收發(fā)單位比特數(shù)據(jù)的電路能耗；d為通信距離。

節(jié)點接收能耗為

Esm=sEelec

(12)

4.2 數(shù)據(jù)融合與轉(zhuǎn)發(fā)能耗

統(tǒng)治節(jié)點可接收并轉(zhuǎn)發(fā)前一跳節(jié)點傳來的數(shù)據(jù)。統(tǒng)治節(jié)點轉(zhuǎn)發(fā)能耗為

Etrans=Erm+Esm=

(13)

式中dtrans為統(tǒng)治節(jié)點間距離。

假設某區(qū)域內(nèi)共有w個節(jié)點，其中1個為統(tǒng)治節(jié)點，其余w-1個為成員節(jié)點。若每個數(shù)據(jù)包大小均為s，在1個收發(fā)周期內(nèi)統(tǒng)治節(jié)點接收w-1次數(shù)據(jù)，融合w-1次數(shù)據(jù)，則其能耗為

Etrans_cs=(w-1)sEda+(w-1)sEelec

(14)

式中Eda為統(tǒng)治節(jié)點融合單位比特數(shù)據(jù)的能耗。

4.3 虛擬骨干網(wǎng)能耗

在每個收發(fā)周期內(nèi)，虛擬骨干網(wǎng)中節(jié)點能耗分為以下3種情況：

(1) 若節(jié)點為統(tǒng)治節(jié)點且承擔中繼功能，則節(jié)點能耗包括融合數(shù)據(jù)能耗、發(fā)送融合數(shù)據(jù)能耗、轉(zhuǎn)發(fā)數(shù)據(jù)能耗。

(2) 若節(jié)點為統(tǒng)治節(jié)點但不參與中繼過程，則節(jié)點能耗包括融合數(shù)據(jù)能耗和發(fā)送融合數(shù)據(jù)能耗。

(3) 中繼節(jié)點能耗包括發(fā)送自身數(shù)據(jù)能耗和轉(zhuǎn)發(fā)其他節(jié)點數(shù)據(jù)能耗。

統(tǒng)治節(jié)點采用多跳形式將融合數(shù)據(jù)通過虛擬骨干網(wǎng)傳輸至目標節(jié)點，其能耗與數(shù)據(jù)傳輸跳數(shù)有關[14-15]。虛擬骨干網(wǎng)多跳傳輸鏈路如圖6所示，統(tǒng)治節(jié)點A的融合數(shù)據(jù)經(jīng)T跳到達目標節(jié)點。

圖6 虛擬骨干網(wǎng)多跳傳輸鏈路Fig.6 Multi-hop transmission link of virtual backbone network

執(zhí)行第T跳轉(zhuǎn)發(fā)任務的節(jié)點能耗為

ET=Enet(T,T)+(T-1)Enet(T,T-1)

(15)

式中：Enet(T,T)為節(jié)點發(fā)送自身數(shù)據(jù)的能耗；Enet(T,T-1)為節(jié)點轉(zhuǎn)發(fā)第T-1跳數(shù)據(jù)的能耗。

除目標節(jié)點外，虛擬骨干網(wǎng)在1個傳輸周期內(nèi)的能耗為

Enet=Enet(T,T)+Enet(T-1,T-1)+…+Enet(1,1)+(T-1)×Enet(T,T-1)+(T-2)Enet(T-1,T-2)+…+Enet(2,1)

(16)

5 仿真實驗

采用Matlab R2017A平臺對基于本文算法重構的網(wǎng)絡能耗、規(guī)模、節(jié)點覆蓋率等指標進行驗證，并與考慮鄰居節(jié)點數(shù)的基于休眠機制和能量均衡的連通支配集(Sleep and Energy Balance-based Connected Dominating Set，SEBCDS)算法[16]和能量均衡的最小連通支配集(Energy Balance Minimum Connected Dominating Set，EBMCDS)算法[17]進行比較。3種算法采用相同的初始殘存局部網(wǎng)絡節(jié)點模型，參數(shù)見表1。為排除隨機因素影響，每種算法均重復300次實驗，取平均值作為實驗結果。

表1 實驗參數(shù)Table 1 Experimental parameters

設Eelec=5 nJ/bit，εfs=50 pJ/(bit·m2)，εamp=1.3 nJ/(bit·m2)，Eda=5 nJ/bit，各節(jié)點1輪傳輸數(shù)據(jù)大小為200 bit。網(wǎng)絡剩余能量如圖7所示?？煽闯鼍W(wǎng)絡運行300輪時，基于SEBCDS算法構建的網(wǎng)絡剩余能量趨近于0，而基于EBMCDS算法和本文算法構建的網(wǎng)絡仍有少量剩余能量，網(wǎng)絡生命周期較長。另外，基于本文算法構建的網(wǎng)絡能耗速率小于其他2種算法，原因是本文算法不僅引入節(jié)點剩余能量篩選機制，且考慮了對能耗影響較大的WSN介數(shù)中心度和節(jié)點緊密度因素。

圖7 網(wǎng)絡剩余能量Fig.7 Network residual energy

為了排除隨機性影響，研究了可用節(jié)點總數(shù)為20時的統(tǒng)治節(jié)點變化情況，如圖8所示。由于采用平均值，所以部分結果為小數(shù)。在相同的節(jié)點分布下，網(wǎng)絡收斂時虛擬骨干網(wǎng)規(guī)模越小，則網(wǎng)絡開銷越小，性能越優(yōu)。從圖8可看出，SEBCDS算法因僅考慮網(wǎng)絡規(guī)模，選出的統(tǒng)治節(jié)點較少；EBMCDS算法只將節(jié)點能量作為選取條件，易選出較多的冗余統(tǒng)治節(jié)點，生成的虛擬骨干網(wǎng)規(guī)模較大，造成能量浪費；本文算法綜合考慮網(wǎng)絡的拓撲性度量和能量因素，不求取局部最優(yōu)，因此在統(tǒng)治節(jié)點數(shù)未達到飽和時網(wǎng)絡規(guī)模介于其他2種算法之間；當節(jié)點通信半徑大于55 m時，各算法選出的統(tǒng)治節(jié)點數(shù)均趨于飽和，此時本文算法選出的統(tǒng)治節(jié)點數(shù)略少于SEBCDS算法，從而生成規(guī)模較小且性能較優(yōu)的虛擬骨干網(wǎng)。

圖8 統(tǒng)治節(jié)點數(shù)Fig.8 Number of dominant nodes

可用節(jié)點總數(shù)為50時網(wǎng)絡覆蓋率如圖9所示。可看出網(wǎng)絡覆蓋率隨節(jié)點通信半徑增大而增大；EBMCDS算法因只考慮節(jié)點剩余能量而忽視了網(wǎng)絡拓撲因素對虛擬骨干網(wǎng)的影響，得到的網(wǎng)絡覆蓋率較低；節(jié)點通信半徑大于27 m時，由于本文算法均衡了能量、WSN中心介數(shù)與節(jié)點緊密度3個維度，所以生成的網(wǎng)絡獲得了較優(yōu)的簇樹從屬關系，節(jié)點覆蓋率優(yōu)于其他2種算法。

圖9 節(jié)點覆蓋率Fig.9 Node coverage

6 結語

針對恢復煤礦災后CMRN連通性難題，提出了一種基于多維度虛擬骨干網(wǎng)構造的煤礦井下無線自組網(wǎng)災后重構算法，引入WSN介數(shù)中心度、節(jié)點緊密度及節(jié)點剩余能量篩選機制3個維度構建虛擬骨干網(wǎng)節(jié)點綜合評價指標。實驗結果表明，基于該算法重構的網(wǎng)絡在剩余能量、統(tǒng)治節(jié)點數(shù)、網(wǎng)絡覆蓋率等方面表現(xiàn)出較優(yōu)性能。在后續(xù)研究中，擬將該算法與礦井災后態(tài)勢感知與數(shù)據(jù)傳輸方法結合，實現(xiàn)災后數(shù)據(jù)高效感知與穩(wěn)定傳輸。