通信網(wǎng)絡(luò)連通性分析方法比較研究

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

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

0 引言

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

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

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

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

1 通信網(wǎng)絡(luò)的圖模型

1.1 通信網(wǎng)絡(luò)的組網(wǎng)架構(gòu)

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

圖1 通信網(wǎng)絡(luò)架構(gòu)Fig. 1 Communication network framework

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

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

1.2 通信網(wǎng)絡(luò)的圖模型

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

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

圖3 典型通信網(wǎng)絡(luò)組網(wǎng)拓撲結(jié)構(gòu)模型Fig. 3 Topology model of typical communication network

2 圖的連通性分析算法

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

2.1 Warshall算法

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

2.2 深度優(yōu)先搜索算法

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

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

2.3 寬度優(yōu)先搜索算法

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

3 通信網(wǎng)絡(luò)震后功能評估方法

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

(1)

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

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

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

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

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

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

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

4 通信網(wǎng)絡(luò)連通性分析方法比較研究

4.1 兩個不同規(guī)模城市的通信網(wǎng)絡(luò)

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

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

圖5 兩個城市的通信網(wǎng)絡(luò)Fig. 5 Communication networks of the two cities

4.2 通信網(wǎng)絡(luò)震后功能評估結(jié)果

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

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

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

圖6 單次地震作用后兩座城市的通信網(wǎng)絡(luò)各節(jié)點和線路功能狀態(tài)Fig. 6 Functional status of communication networks of the two cities after earthquake

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

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

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

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

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

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

4.3 連通性方法比較分析

1)計算耗時比較分析

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

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

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

2)收斂速度比較分析

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

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

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

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

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

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

5 結(jié)論

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

1)依據(jù)通信節(jié)點垂直分層和水平分區(qū),通信線路雙回路和環(huán)狀拓撲方式連接的規(guī)則建立通信網(wǎng)絡(luò)圖模型,更貼合通信網(wǎng)絡(luò)的實際建設(shè)規(guī)劃。

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

3)同一通信網(wǎng)絡(luò)在地震動強度相同和模擬次數(shù)相同時,寬度優(yōu)先搜索算法的運算時間最短和效率最高,深度優(yōu)先搜索算法次之,Warshall算法時間最長。

4)三種算法隨蒙特卡洛模擬次數(shù)增加而收斂的速度大致相當(dāng)。深度優(yōu)先搜索算法和寬度優(yōu)先搜索算法的收斂略早于Warshall算法。城市越大,其通信網(wǎng)絡(luò)越復(fù)雜,收斂也越慢。