一種煤礦井下無線自組網災后重構算法

胡青松， 王勝男

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

0 引言

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

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

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

1 問題模型

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

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

可用節點在網絡重構過程中被分為感知節點、統治節點和中繼節點3類。感知節點負責感知災害區域態勢信息。統治節點接收其通信范圍內感知節點傳遞的信息，融合壓縮后傳輸給下一跳中繼節點，構成虛擬骨干網[7]。網絡以周期性方式工作，完成虛擬骨干網構造、數據收集與轉發工作。

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

2 虛擬骨干網構造指標

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

2.1 WSN介數中心度

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

(1)

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

2.2 節點緊密度

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

(2)

式中dij為節點i，j之間的距離。

2.3 多維度綜合評價指標

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

(1) 構建指標矩陣：

(3)

式中xir為節點i的第r項指標，r=1,2,…,h,h為評價指標數，本文中h=3,r=1表示WSN介數中心度，r=2表示節點緊密度，r=3表示節點剩余能量。

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

(4)

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

(5)

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

(6)

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

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

(7)

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

第r項指標的客觀權重為

(8)

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

Hi=W1Mi+W2Ci+W3Ei

(9)

式中Ei為節點剩余能量。

經過處理后的指標權重Wr為正向指標，即Hi越大，節點i當選為統治節點的優先級越高。

3 虛擬骨干網構造過程

3.1 初始階段

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

圖2 虛擬骨干網構造初始狀態Fig.2 The initial state of virtual backbone network construction

統治節點選舉步驟如下。

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

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

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

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

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

3.2 支配集連接階段

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

圖3 統治節點選舉Fig.3 Election of dominant nodes

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

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

(3) 其余感知節點選擇距離自身最近的統治節點加入其統治集合，向其發送數據。

(4) 各統治節點與其通信范圍內的統治節點或中繼節點建立虛擬骨干網鏈路，將采集數據以多跳形式傳輸至目標節點。

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

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

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

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

圖4 中繼節點選舉Fig.4 Election of relay nodes

圖5 虛擬骨干網構造完成Fig.5 Finished virtual backbone network construction

4 虛擬骨干網能耗分析

4.1 節點能耗模型

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

(10)

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

節點發送能耗為

(11)

式中：s為數據長度；Eelec為節點收發單位比特數據的電路能耗；d為通信距離。

節點接收能耗為

Esm=sEelec

(12)

4.2 數據融合與轉發能耗

統治節點可接收并轉發前一跳節點傳來的數據。統治節點轉發能耗為

Etrans=Erm+Esm=

(13)

式中dtrans為統治節點間距離。

假設某區域內共有w個節點，其中1個為統治節點，其余w-1個為成員節點。若每個數據包大小均為s，在1個收發周期內統治節點接收w-1次數據，融合w-1次數據，則其能耗為

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

(14)

式中Eda為統治節點融合單位比特數據的能耗。

4.3 虛擬骨干網能耗

在每個收發周期內，虛擬骨干網中節點能耗分為以下3種情況：

(1) 若節點為統治節點且承擔中繼功能，則節點能耗包括融合數據能耗、發送融合數據能耗、轉發數據能耗。

(2) 若節點為統治節點但不參與中繼過程，則節點能耗包括融合數據能耗和發送融合數據能耗。

(3) 中繼節點能耗包括發送自身數據能耗和轉發其他節點數據能耗。

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

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

執行第T跳轉發任務的節點能耗為

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

(15)

式中：Enet(T,T)為節點發送自身數據的能耗；Enet(T,T-1)為節點轉發第T-1跳數據的能耗。

除目標節點外，虛擬骨干網在1個傳輸周期內的能耗為

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

表1 實驗參數Table 1 Experimental parameters

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

圖7 網絡剩余能量Fig.7 Network residual energy

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

圖8 統治節點數Fig.8 Number of dominant nodes

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

圖9 節點覆蓋率Fig.9 Node coverage

6 結語

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