通信網絡連通性分析方法比較研究

毛晨曦,穆志煒,張亮泉,王 濤

(1. 中國地震局工程力學研究所 中國地震局地震工程與工程振動重點實驗室,黑龍江 哈爾濱 150080;2. 地震災害防治應急管理部重點實驗室,黑龍江 哈爾濱 150080; 3. 東北林業大學 土木工程學院,黑龍江 哈爾濱 150040)

0 引言

通信系統是一類重要的城市生命線系統。目前在我國,通信產業與國民經濟其他產業高度關聯,已經成為國民經濟發展的“加速器”和社會效益的“倍增器”[1]。同時,我國又是一個地震多發國家。依據工業與信息產業部官網的數據報道,自2008年汶川地震后,已有多次6級以上地震造成大量通信系統基礎設施損壞,導致災區通信服務中斷和巨額經濟損失。2010年,青海玉樹7.0級地震造成全州超過90%的通信基站遭受不同程度的破壞,嚴重影響震后的應急救援工作[11];2013年,四川省蘆山7.0級地震造成724個基站退服,同時雅安的通信光纜中斷幾十處,合計約千余公里[11];2019年四川長寧6.0級地震造成三大通信運營商中斷基站385個,通信鐵塔中290站次存在不同程度受損,機房及設備嚴重受損201站,塔基嚴重受損38處[3];2021年云南漾濞6.4級地震造成三大運營商共計37座基站退服[2]。這些受災數據都說明了通信系統在地震中的脆弱性以及對通信系統進行抗震研究的必要性。通信系統震后功能評估是指在地震發生前,或者在地震剛剛發生尚缺乏災區詳細災情數據的情況下,對災區通信系統經受了地震打擊后的功能狀況給出評估。該方法基于待評估城市/地區各類通信建構筑物、通信設備、通信線路的地震易損性和該地區通信網絡的拓撲結構,給出整個地區所有通信基站在指定地震動強度下的功能狀態。在地震發生前,評估結果可以用來檢驗通信系統的抗震能力是否符合預期,以及發現通信網絡中的抗震薄弱環節,從而服務于通信系統抗震規劃制定;在地震發生后災區通信暫時中斷的時期,則可以了解災區損傷節點分布,指導維修人員和物資部署。

在本文中,通信系統的震后功能水平用地震后仍能維持通信服務的基站在全部基站中的占比來衡量。每個基站在震后是否能維持通信服務則基于兩方面因素:1)各基站及其上級節點(交換中心和匯聚機房)的建構筑物和設備的地震損傷水平[4-6],以及網絡內各條通信線路的損傷水平(假設這些基本元件發生超過嚴重破壞的損傷即導致其自身功能失效)。2)在這樣的損傷狀況下,尚能正常工作的基站與交換中心間是否可以采用變換路由的方法維持信息傳輸,即基站能否尋找到未損傷線路與交換中心實現連通。本文的研究重點針對上述第二方面,即分析選擇適用于通信網絡的連通性分析方法。

關于網絡連通性分析方法的研究,在其他生命線系統里如城市供水和供電系統等已有較多成果。如陳永盛[7]采用深度優先搜索算法,對電力網絡采用一般賦權網絡建模并進行連通性分析,通過實例驗證了該算法模型的準確性;柳春光等[8]在供電系統圖模型中通過對比Warshall算法、圖論法和模糊數學法的計算精度和效率,驗證了Warshall算法更適合計算大型復雜網絡的連通性;龍立[10]在蒙特卡洛模擬方法的基礎上結合寬度優先搜索算法,利用CUDA(compute unified device architecture,統一計算設備架構)并行運算平臺,提高了有向邊權網絡連通性分析的效率。

通信網絡有自己獨特的組網規則,因而網絡建模方法和連通性分析方法均需符合這些規則。本文首先介紹了通信網絡的組網架構和拓撲規則,并據此給出通信網絡圖模型的建模方法;隨后,以兩座不同規模城市的通信網絡為研究對象,以計算時間和計算收斂速度為評價指標,分析比較了Warshall算法、深度優先搜索算法和寬度優先搜索算法對不同規模通信網絡進行連通性分析的適用性,為后續城市通信系統震后功能評估軟件開發提供方法選擇依據。

1 通信網絡的圖模型

1.1 通信網絡的組網架構

通信網絡由通信節點和光纜線路組成,節點主要包括:交換中心MSC(mobile switching center),負責全網業務數據的交互,是通信網絡的核心節點;匯聚機房BSC(base station controllers),在用戶數據接入交換中心前先做匯聚,以減輕核心層設備的負荷;通信基站BTS (base transceiver stations),負責將終端用戶業務接入網絡以實現數據交換。其中交換中心組成了通信網絡中的核心層,匯聚機房組成了匯聚層,通信基站則組成了接入層,并按照環狀、網狀拓撲的方式布設。城市通信網絡架構如圖1所示。

圖1 通信網絡架構Fig. 1 Communication network framework

通信節點之間主要通過光纜線路連接。憑借低損耗、高容量和抗電磁干擾能力強等特點,光纜線路已經被越來越多地應用在現代通信網絡的建設中。光纜線路通常使用管道、直埋和架空等方式鋪設,其中管道鋪設光纜埋在地下,抗震性能最好但建設成本也高,施工周期長,常用于城市主干線路;直埋鋪設光纜造價略低于管道鋪設光纜,抗震性能與之大致相當,常見于野外平原地帶;架空光纜造價較低,抗震性能不如管道和直埋光纜,一般用于城市長途二級或二級以下的線路。不同光纜鋪設形式如圖2所示。在本文的分析中,對于連接交換中心、匯聚機房的主干線路選用管埋光纜,連接通信基站的配線線路選用架空光纜,并在這兩種光纜的地震損傷估計時采用了不同的地震易損性。

圖2 不同鋪設形式的光纜Fig. 2 Different laying forms of optical fiber cable

1.2 通信網絡的圖模型

圖論是數學的一個分支,可用于對物理、生物、社會和信息系統中許多類型的關系和過程建模,如被用來表示生命線網絡中各基本部分間的相互關系。通?！皥D”用一個二元組G=(V,E)來表示,其中:V是圖的節點集,E是圖的邊集。每個節點和邊單元均可賦以權,用來表示節點或者節點之間關系的某種屬性。如果只對邊單元E賦值,而設定節點單元V均為1,則圖稱為邊權圖;如果只對節點單元V賦值,而設定邊單元E為1,則圖稱為點權圖;如果對節點單元V和邊單元E均賦值,則該圖稱為一般賦權圖。根據有向邊(有特定方向的邊)在圖中所占比例,又可將圖分為有向圖、無向圖和混合圖。為了便于使用計算機對圖進行分析研究,通常把圖以鄰接矩陣、關聯矩陣或鄰接表的形式儲存起來。

本文依據通信網絡中各節點連接的拓撲規則,把通信網絡簡化為同時考慮點權和邊權的一般賦權網絡G=(V,E),用V表示系統中的數據交換中心、匯聚機房和通信基站等節點的集合,E表示連接節點之間光纜線路的邊集合。由于通信網絡通常是開放系統,與本地網之外的其他網絡相連,因此將與外界網絡連接且進行大量數據交換的交換中心視為本地網的源點。通信網絡中各節點單元間的信息傳遞是雙向的,故通信系統網絡圖模型應當為無向圖模型。本文中的圖模型采用基于鄰接表優化而來的鄰接壓縮表儲存,可以減小儲存空間,提高計算效率。通信節點通常采用垂直分層和水平分區的方式布設,通信線路采用雙回路和環狀拓撲的方式連接。在垂直方向上分為核心層(由交換中心組成)、匯聚層(由匯聚機房組成)和接入層(由通信基站組成),每層通信節點采用環狀拓撲連接。在垂直的層級之間為了保護通信功能不受個別線路中斷的影響,提升網絡可靠性,不同層級用雙回路的方式連接組網。這樣可以預留一條傳輸線路作為備用通道,在遇到一條線路中斷時可以迅速切換到另一條線路,實現對正常通信功能的保護。在接入層,構成一個接入環的基站數量通常根據該地區業務量的大小確定。典型的通信網絡組網拓撲結構如圖3所示。

圖3 典型通信網絡組網拓撲結構模型Fig. 3 Topology model of typical communication network

2 圖的連通性分析算法

本文分別采用Warshall算法、深度優先搜索算法和寬度優先搜索算法對通信網絡在地震后的連通狀態進行分析,通過對三種算法的比較得出適用于通信網絡的連通性分析方法。以下對這三種算法的核心思想給出介紹。

2.1 Warshall算法

Warshall算法是在1962年提出求二元關系傳遞閉包的算法。這種算法的核心思想是:通過對表示某二元關系的鄰接矩陣(傳遞閉包)進行布爾運算,以替代對鄰接矩陣重復進行多次冪運算,最終得出的矩陣即為矩陣M的傳遞閉包[8-9],比應用圖論算法計算效率更高。Warshall算法的優點在于它的實現形式簡單,步驟簡潔,使用計算機編程時只需少量代碼就可以實現,缺點則在于矩陣運算量大,在進行復雜網絡的連通性判別時需要的時間更長。

2.2 深度優先搜索算法

深度優先搜索屬于圖的遍歷算法的一種。其核心思想是從一個源點出發訪問最近的一個鄰接節點,從這個節點向下擴展,每次只擴展一個鄰接節點直至最后無法向下擴展;此時回退到上個節點并選擇另一個沒有被訪問的鄰接節點向下擴展;重復這個過程直至找到目標節點或者遍歷過所有與源點相通的節點,視為算法結束[12]。圖4(a)展示了深度優先搜索算法進行連通性分析的過程。

圖4 兩種算法的連通性分析路徑Fig. 4 Connectivity analysis path of the two algorithms

2.3 寬度優先搜索算法

寬度優先搜索是另一種圖的遍歷算法。其核心思想是分層搜索,從初始節點出發,向下擴展,遍歷這一層中所有與初始節點相連的節點,這一層完成后接著向下擴展,重復這一過程直至找到目標節點或者遍歷過所有與源點相通的節點,視為算法結束[10]。圖4(b)展示了寬度優先搜索算法進行連通性分析的過程。

3 通信網絡震后功能評估方法

基于通信網絡中各基本元件的地震易損性,結合上述網絡連通性分析方法,即可進行通信網絡震后功能狀態的評估。該方法采用公式(1)定義的震后通信網絡服務功能滿意度指數來衡量通信網絡的震后功能水平。

(1)

式中:F為震后通信網絡的服務功能滿意度指數,即震后可以保持通信服務的基站數與所評估地區基站總數之比;NAvl為震后可以提供通信服務的基站總數。這些基站的機房建筑、鐵塔和設備沒有發生嚴重破壞(假設機房建筑、鐵塔和設備發生超過嚴重破壞的損傷即導致功能失效),并且在地震后可以找到未破壞的線路與交換中心實現連通,從而保持信息傳輸;NTot為所評價的城市/地區通信基站的總數。

通信網絡震后功能評估采用課題組前期研究的方法,詳細評估過程請參考文獻[11]。該方法中,通信網絡系統的震后功能評估需要先后完成兩個方面的評估:首先評估網絡中各個基本元件(如機房建筑、通信設備、通信線路和通信鐵塔等)在地震后的損傷狀態和功能狀態,并據此推斷由基本元件構成的基本單元(如交換中心、匯聚機房和通信基站)在地震后的功能狀態;然后針對未損傷或輕微損傷的通信基站,分析計算每個基站與交換中心間的連通性。為能較準確考慮地震動的隨機性,還需對上述過程進行多次地震動作用下的蒙特卡洛模擬。評估方法的具體步驟如下:

1)導入待評估地區通信網絡圖模型,以及該地區地震動強度PGA場(本文未考慮地震動強度隨傳播距離的衰減,假設整個地區的各地點具有相同的PGA,即采用一致地震動場)。

2)判斷每個通信節點(交換中心、匯聚機房和基站)內各基本元件(機房建筑、通信設備和通信鐵塔等)的地震損傷狀態和功能狀態;判斷每條通信線路的地震損傷狀態和功能狀態。具體方法:依據節點和線路所在位置的PGA,對比各基本元件地震易損性,采用隨機采樣法確定每個基本元件的震后損傷水平;當機房建筑、通信設備、通信鐵塔和通信線路發生超過嚴重破壞的損傷,即認定其功能失效。本環節中各機房建筑、通信設備、通信鐵塔和通信線路的地震易損性依據2022年6月住房和城鄉建設部正式頒布的《城市工程系統抗震韌性評價導則》(RISN-TG041—2022)內的建議確定給出。

3)判斷每個通信節點(交換中心、匯聚機房和基站)的震后功能狀態。判斷方法:節點內任一類基本元件(如基站的機房建筑、鐵塔和設備)功能失效,即判斷該節點功能失效,刪除該節點單元和與之相連的線路單元,更新通信網絡圖模型。

4)判斷每個尚未功能失效的基站節點與交換中心間能否連通,即采用連通性分析方法(本文采用Warshall算法、深度優先搜索算法和寬度優先搜索算法)判斷這些基站節點與交換中心間是否存在連通路徑。若基站本身未因地震損傷導致功能失效,且能與交換中心保持連通,則認為該基站在地震后仍可提供通信服務。

5)根據公式(1)計算震后通信網絡的功能滿意度指數,給出整個通信網絡的震后功能水平。

4 通信網絡連通性分析方法比較研究

4.1 兩個不同規模城市的通信網絡

本文以抗震設防等級均為7度的某省會城市(1號城市)和某縣級市(2號城市)的通信網絡為研究對象,分別建立圖模型,采用上述方法評估其在7度小震、中震和大震作用后的功能水平。在連通性分析環節,采用了Warshall算法、深度優先搜索算法和寬度優先搜索算法,比較研究三種方法對通信網絡連通性分析的適用性。

省會城市通信網絡如圖5(a)所示,該市有數據交換中心2座,匯聚機房6座,通信基站786個,主干線路9條,配線線路827條?？h級市通信網絡如圖5(b)所示,該市數據交換中心2座,匯聚機房3座,通信基站298個,主干線路6條,配線線路329條。采用1.2節的方法建立了兩座城市通信網絡的圖模型。

圖5 兩個城市的通信網絡Fig. 5 Communication networks of the two cities

4.2 通信網絡震后功能評估結果

假設兩個城市的整個城區內為一致地震動場,7度小震、中震和大震對應的PGA數值依照現行《建筑抗震設計規范》(GB 50011—2010)[13]的建議確定,分別為0.05 g、0.1 g和0.2 g。對兩座城市在三個地震動水平下震后各個基站的功能狀態進行了評估。

表1給出了三個地震動水平下,單次地震動作用后兩個城市的震后功能滿意度指數。圖6展示了震后每個基站的功能狀態,圖中綠色的各單元(節點和線路)表示在地震后可以保持通信服務,紅色的各單元則表示喪失了功能(節點單元喪失通信功能,線路單元喪失傳輸功能)。三種連通性分析方法計算得出的各節點和線路震后功能狀態結果相同。

表1 兩座城市通信系統單次地震作用后的功能滿意度指數Table 1 Functional satisfaction index of the communication network of the two cities after once earthquake

圖6 單次地震作用后兩座城市的通信網絡各節點和線路功能狀態Fig. 6 Functional status of communication networks of the two cities after earthquake

由于單次地震動模擬的結果難以全面體現地震動的隨機性對分析結果的影響,對上述兩座城市在三個地震動水平下的震后功能狀態進行了蒙特卡洛模擬,模擬次數為10000次。以大震作用下的結果為例,圖7給出了蒙特卡洛模擬得到的兩座城市每個基站和線路震后發生功能失效的概率,即每個基站和每條線路在10000次地震后發生功能失效的次數與蒙特卡洛模擬總次數的比值。圖中綠色表示失效概率處于0%～40%范圍的單元,黃色表示失效概率處于40%～70%范圍的單元,紅色表示失效概率高于70%的單元。從這幅圖可以看出兩座城市內抗震能力薄弱(失效概率>70%)的基站和線路的位置。通過提升相應基本元件的地震易損性(如改善設備抗震能力和架空線路改為埋地線路等)或者改善通信網絡的拓撲結構設計(增加冗余線路),可以有效提高通信系統網絡的抗震性能。這一結果可以為通信系統防震減災規劃的制訂提供依據。

圖7 10000次蒙特卡洛模擬后每個基站和線路失效概率(大震)Fig. 7 Failure probability of each BTS and line after 10000 Monte Carlo simulations (under large earthquake level)

為了觀察蒙特卡洛模擬得到的通信系統震后功能滿意度指數的概率分布,將功能滿意度指數的區間(0～1.0)均勻劃分為若干份,并計算出滿意度指數落在每個數值區間內的頻率。圖8給出了1號城市分別用三種連通性分析算法進行蒙特卡洛模擬后得到的功能滿意度指數頻率點。這些頻率點基本以一個頻率值為中位數對稱分布,因而選用正態分布的概率密度函數擬合這些頻率點數據,也繪在圖8各圖中。表2給出了兩座城市采用三種連通性分析方法進行10000次蒙特卡洛模擬后,通信系統震后功能滿意度指數的中位值和標準差。

如今，美國和中國是世界上的兩大力量。兩個國家都不能忽視另一個國家的存在。但是，隨著中國政治、經濟、文化的快速發展，資本主義國家提出的“中國威脅”理論開始流行。此外，由于政治體制的不同，一些以美國為首的西方國家千方百計地想要降低中國對全球的影響。

表2 10000次模擬的震后功能滿意度參數Table 2 Post-earthquake functional satisfactionindex of Monte Carlo simulation (10000)

圖8 通信系統震后功能滿意度指數的概率密度曲線Fig. 8 Probability density curve of functional satisfaction index of communication system

4.3 連通性方法比較分析

1)計算耗時比較分析

上述兩座城市通信系統的震后功能分析,在連通性分析環節本文分別采用了Warshall算法、深度優先搜索算法和寬度優先搜索算法。下面從計算時間和收斂速度兩個方面對這三種方法進行比較。本文程序運行環境如下:Windows10操作系統;計算機CPU為Inter(R) Xeon(R) W-2235,6核,主頻3.80 GHz,32 GB內存;顯卡為T1000,4 GB顯存。

在統計了不同城市在不同算法、地震動強度和模擬次數下的計算時間后,發現同一城市在相同算法、地震動強度作用下的計算時間與模擬次數成線性相關,且變化趨勢相同,故選擇本文選擇10000次模擬下的計算時間進行分析對比。圖9統計了三個地震動水平下,兩座城市采用三種連通性方法進行10000次的蒙特卡洛模擬所用的計算時間。從圖中可以很明顯看出:同一通信網絡在地震動強度相同、模擬次數相同時,寬度優先搜索算法的運算時間最短并且效率最高,深度優先搜索算法次之,Warshall算法時間最長。此外,從1號城市與2號城市的模擬時間對比可以看出:復雜度越高的網絡在相同條件下進行震后功能評估的時間越長。對比同一座城市不同地震動強度作用下的計算時間,呈現出地震動強度越大,功能失效節點越多,評估時間越短的趨勢,但在使用寬度優先搜索算法和深度優先搜索算法時,中震作用下的計算時間反而最長,這是由兩種算法遍歷所有節點時優先選擇最短路徑的特點決定的。在中震作用下,通信網絡中少量基本單元出現損傷,導致部分節點無法通過最短路徑連通,為了遍歷所有節點,算法會選擇其他更長的路徑,通過延長計算時間來確保分析結果的準確性。

圖9 三種連通性方法計算時間對比Fig. 9 Computational cost of the three algorithms

2)收斂速度比較分析

圖10給出了1號城市在大震作用下采用三種算法進行100次、1000次和10000次模擬后得到的功能滿意度指數的正態分布概率密度曲線。從圖中看出:三種方法得出的震后功能滿意度指數基本一致,但蒙特卡洛模擬次數較少時,計算出的功能滿意度指數尚不準確,隨著模擬次數增加功能滿意度指數才逐漸趨于穩定,收斂到一個較為準確的數值。

圖10 通信系統震后功能滿意度指數的正態分布概率密度曲線Fig. 10 Probability density curve of functional satisfaction index of communication system

為了比較三種算法的收斂速度,圖11-12繪出了兩個城市通信系統在大震后功能滿意度指數的中位值隨蒙特卡洛模擬次數的變化曲線。從這兩幅圖可以看出震后功能滿意度指數的收斂過程。為了能更直觀地判斷出哪一種算法收斂更快,本文以功能滿意度指數變化率作為判斷計算結果收斂速度的指標?！肮δ軡M意度指數變化率”指此次蒙特卡洛模擬工況得到的滿意度指數相比上一次蒙特卡洛模擬工況獲得的滿意度指數,除以前述工況中滿意度指數的歷史最大值。當變化率不超過歷史最大值的0.1%,即認為滿意度指數計算結果達到收斂。

圖11 通信系統震后功能滿意度指數隨蒙特卡洛模擬次數的收斂(1號城市)Fig. 11 Function satisfaction index of communication system converges with Monte Carlo simulation times (City 1)

圖12 通信系統震后功能滿意度指數隨蒙特卡洛模擬次數的收斂(2號城市)Fig. 12 Function satisfaction index of communication system converges with Monte Carlo simulation times (City 2)

從圖11-12可以看出:三種算法隨蒙特卡洛模擬次數增加而收斂的速度大致相當。深度優先搜索算法和寬度優先搜索算法的收斂略早于Warshall算法。Warshall算法雖然用時遠超過另外兩種算法,但其隨蒙特卡洛模擬次數的收斂并無明顯劣勢。此外,城市規模對算法收斂速度也有影響。城市越大,其通信網絡越復雜,收斂也越慢。1號城市三種算法在9000次左右變化幅值均穩定小于0.1%,達到收斂,2號城市則只需要6000次。

5 結論

本文首先研究了典型通信網絡的組網規則和拓撲結構,并基于此給出了建立通信網絡圖模型的方法;然后,以兩座不同規模的城市為研究對象,以計算時間和收斂速度為指標,對比研究了Warshall算法、寬度優先搜索算法和深度優先搜索算法對通信網絡連通性分析的適用性。通過本文研究得到如下結論:

1)依據通信節點垂直分層和水平分區,通信線路雙回路和環狀拓撲方式連接的規則建立通信網絡圖模型,更貼合通信網絡的實際建設規劃。

2)根據地震后各基站保持通信服務的概率,可以判斷出通信網絡內薄弱節點和線路的位置。通過提升相應基本元件的地震易損性(如架空線路改為埋地線路)或者改善通信網絡的拓撲結構設計(增加冗余線路),可以有效提高通信系統網絡的抗震性能。

3)同一通信網絡在地震動強度相同和模擬次數相同時,寬度優先搜索算法的運算時間最短和效率最高,深度優先搜索算法次之,Warshall算法時間最長。

4)三種算法隨蒙特卡洛模擬次數增加而收斂的速度大致相當。深度優先搜索算法和寬度優先搜索算法的收斂略早于Warshall算法。城市越大,其通信網絡越復雜,收斂也越慢。