基于覆蓋網絡的災后通信網絡恢復策略*

趙 珩，苗 堃，白繼武，李 頌，趙 倩，范爭爭

(國網河南省電力公司濟源供電公司，河南 濟源 454650)

0 引 言

覆蓋網絡的源路由連接方式結合了主動連接保護與被動重路由兩種策略的優勢，有效解決了主動式保護中無法適用于區域損毀場景問題，避免了被動重路由恢復時間受限的局限。Neumayer[1]運用信息計算機技術與數學幾何工具完成了區域損毀的模型建構，確定了網絡損毀中最為脆弱的位置。在計算幾何理論的幫助下，運用圓形區域與線段標志顯現了災后損毀區域的具體化。王振東[2]通過設計一種改進差分進化算法實現了無限傳感器網絡節點覆蓋率的有效提升，節點設計中通過因子結構優化實現了函數模型優化。羅杰超等[3]針對高速公路救援點設置與選址問題進行了專項分析，從全局角度構建了覆蓋網絡救援點選址模型，并集合救援點與路網拓撲結構計算了各個路段的救援響應時間，最終建立了常駐救援點與備勤救援點。金石等[4]為提升用戶體驗感受，基于無定形無限覆蓋網絡的信道特性與基礎理論內容，結合外部環境與系統動態資源實現了多層重疊覆蓋與費力結合控制，大大提升了用戶層面上下行接入模式的解耦特性。Wang等[5]依據災后區域特征提出了通信區域損毀模型，通信網絡鏈路存在發生故障的概率，損毀故障概率與網絡鏈路的長度、災害區域范圍大小存在直接關系，通信網絡的損毀程度會隨著破壞強度的遞減而減弱。Agarwal等[6]提出,假設在災害發生后，區域網絡平面中會產生一個明顯的故障概率分布，在區域災后區域中每個地理區位中分布著不同的故障概率，依據假設內容，為了提升災后網絡故障概率計算水平提出了統一區域損毀模型。Zheng等[7]提出了一種響應式重路由算法(Reliable Transaction Router,RTR)，是目前比較高效的一種災后通信網絡恢復算法，RTR算法恢復中包含兩個階段:第一階段為發送探測包，探測包可以迅速包圍故障區域傳輸，收集遇到的故障鏈路信息；第二階段為源節點收回，根據探測包信息可以獲取最短的故障連接路徑。謝小軍等[8]提出了QoS約束的電力通信網絡故障恢復算法，實現了電力通信網絡因鏈路故障導致電力通信基礎網絡損失最小化的目標。張鋒等[9]考慮到變結構耗散網絡故障恢復算法，無法便捷操作特殊隔離設備，通過加入系統虛擬開關的方式提出了變結構耗散網絡理論故障恢復改進算法，滿足了對特殊設備操作的需求。黃潮[10]提出了一種基于功率譜密度估計的云計算環境下海量光纖通信故障數據挖掘算法，通過去除冗余干擾可對時頻域中進行功率譜密度特征提取，實現故障數據的經驗模態分解與故障特征聚類，提高了故障數據定位挖掘能力。

本文應用覆蓋網絡技術提出了災后大規模通信損毀連接恢復策略。結合現有主動式連接保護與被動重路由連接的優勢與技術不足，引用覆蓋網絡設計思路提出了災后網絡快速恢復系統，覆蓋網絡通信恢復系統通過提前設置的網絡鏈路代理節點可實現網絡的快速重構，提升網絡恢復的靈活性。

1 landmark與源節點結合的區域通信損毀恢復策略

1.1 系統設計

區域網絡中單一的網絡節點與landmark連接，若系統源節點與單一網絡節點之間出現故障，源節點會在源路由配合下最短時間以網絡流量方式將故障信息傳遞到中間節點，節點尋路過程中不需要知道具體的故障區域位置與大小信息。覆蓋網絡中每個節點都與landmark具有通信聯系，源節點會以源路由方式將流量發送到最佳的landmark，再由landmark進行轉發并迅速匹配到相對應的節點。

覆蓋網絡通信恢復系統中landmark與源節點的運作流程如圖1所示。

圖1 覆蓋網絡通信恢復系統中landmark與源節點運作流程

圖1中的l1和l2作為系統中間節點，若區域損毀問題出現在n2和n3網絡鏈路位置，src與dst間的默認路由便會直接中斷。覆蓋網絡中的src會獲取到與l2的故障后也會直接斷開，此時，src仍可通過l2將網絡流量重路由傳送到dst。系統中單個landmark的受損并不會影響到整個覆蓋網絡的穩定性，通過其他備用路徑仍可恢復src與dst間的網絡連接，故障的出現并不會直接中斷系統網絡流量的傳遞。基于覆蓋網絡與源路由系統設計中包含兩條互通的連接傳輸路徑。以l1和l2分別作為中間節點的傳輸路徑可分別完成src到dst的網絡流量傳輸。基于覆蓋網絡構建的系統新路徑長度為

(1)

1.1.1 landmark選取策略

系統中間節點的選取直接關系了覆蓋網絡恢復策略的運作性能。本文借助k-mean算法將網絡節點進行網絡分塊處理，將所有系統節點處理轉變為k個集合，S={Si|1≤i≤k}，獲取網絡所有節點距離之和的最小值。最小值計算如下：

(2)

Input:網絡拓撲G=(V,E),V中的所有節點坐標

Output:含有k個landmark的集合L

begin

L←?

初始化每個集合的中心點位置，C={ci|1≤i≤k}

C←隨機選擇的k個網絡節點

repeat

將V中的每個網絡節點分配到對應的集合中，每個網絡節點離對對應集合的中心點距離最近(即所有網絡節點分配到k個集合中去)，使得Si={xp|d(xp,ci)≤d(xp,cj),?1≤j≤k}

until每個集合的中心點位置不在變化；

forall theC的所有元素do

找到在Si中度最大的節點x

L←LU{x}

returnL

從理論角度而言，k-mean算法的運行復雜度隨著節點數的增加會出現指數倍的增長[11]。但應用k-mean算法劃分運算是在系統中間節點選取前進行的，導致k-mean算法的復雜程度并不會直接對覆蓋網絡系統恢復策略的效果產生直觀影響。

1.1.2 通信網絡恢復路徑選取

應用覆蓋網絡與源路由進行通信快速恢復時，系統源節點會直接調用路徑探測數據包，并將數據直接推送到landmark中，中間節點接收到探測數據包會將數據分別轉發到系統中的各個節點上，源節點與landmark傳輸中使用標準的SPR(Sharp Proactive Routing)協議。系統目的節點接收到探測數據包后會在最短時間內傳輸送回響應結果。源節點會統一篩選全部返回的響應結果數據，依據系統適用性建立通信網絡快速恢復備選路徑集合，源節點同時會計算所有備選路徑的時延，選取集合中時延最短的路徑作為網絡重路由路徑。備選路徑節點的時延越短，維護其到landmark的成本越低。災后區域大規模通信損毀時，運用上述算法選取合適數量的中間節點可實現系統網絡的快速恢復。

1.2 快速恢復策略性能分析

1.2.1 仿真內容

以仿真實驗檢驗通信快速恢復策略性能，以隨機拓撲與真實拓撲為仿真實驗基礎，運用LEMON Graph Library庫拓撲生成器形成隨機拓撲，運用Rocketfuel數據庫生成獲取真實拓撲。隨機拓撲與真實拓撲信息內容如表1所示。

表1 隨機拓撲與真實拓撲基本信息內容

仿真性能分析中以傳達性衡量通信系統故障連接的成功率，系統故障連接恢復的指標測量公式為

(3)

式中:#of recovered paths為可通過快速恢復策略成功進行的通信網絡連接；#of recoverable paths為災后區域通信故障出現后所有被破壞的網絡連接中可恢復的連接，兩者比值為仿真實驗中系統的實際傳達率。傳達率與網絡連接源節點及目的節點有著直接關系，若故障后兩個階段仍能實現連接則可恢復，若源節點與目的節點無法連接則無法恢復。嚴重的災害后會導致通信網絡故障不可恢復概率增加。

以恢復路徑長短作為衡量恢復性能指標之一。系統快速恢復路徑過程會導致恢復中資源消耗量增加，路徑長度計算公式為

(4)

1.2.2 性能結果分析

仿真實驗中測試了不同中間節點數量下快速恢復流量的實際比例，恢復比例與landmark數量間的關系如圖2所示，隨機拓撲與真實拓撲的landmark測試結果如圖2(a)與圖2(b)所示。

(a)隨機拓撲

(b)真實拓撲圖2 恢復比例與landmark數量間的關系

由圖2可知，隨機拓撲網絡仿真實驗中，當節點數量達到3個時，系統網絡恢復系統提升明顯；節點數量超過3個時，系統網絡連接恢復比例并未發生明顯提升，仿真結果表明少量的landmark，4～5個節點或拓撲總結點的1%數量即可保證系統網絡具有較高的恢復能力。真實拓撲仿真實驗結果中，同樣在節點數量達到3個時，系統網絡恢復比例達到60%以上，隨著節點數量增加，系統網絡恢復強度增益并不明顯，因此保持少量的landmark即可達到系統網絡恢復效果。

網絡路徑長度大小結果如圖3所示。由圖3可知，覆蓋網絡與原路由連接快速恢復系統(Fast Landmark System of Original Route Connection，FLSR)結果在Random結果之上，表明系統快速恢復中可選取到比Random4路徑長度更短的恢復路徑,但FLSR算法的恢復路徑明顯比Path Splicing的路徑長度值大。

圖3 不同算法恢復路徑長度值情況

在驗證FLSR系統在災后區域損毀快速恢復性能的同時，驗證分析災后多鏈路故障場景下系統的恢復效果。在隨機拓撲與真實拓撲中分別配置故障概率，在拓撲上的每條鏈路e∈E分配一個故障概率pe，且拓撲中不同鏈路出現通信故障的概率獨立存在，以平均故障概率代表拓撲鏈路中出現故障的期望鏈路數量。平均故障概率公式如下：

(5)

經過仿真分析驗證，覆蓋網絡與源路由快速恢復系統在災后區域獨立多鏈路場景下有著顯著作用。

由圖4可知，FLSR在獨立多鏈路故障場景下效果顯著，若Random-4拓撲中有5%鏈路出現故障時，覆蓋網絡與源路由快速恢復系統可實現90%的快速恢復，性能較佳。

圖4 獨立多鏈路故障場景恢復對比

2 信息爆炸下網絡連接恢復策略

2.1 系統設計

覆蓋網絡與源路由快速恢復策略應在保證性能兼具災后區域現實問題，提升快速恢復系統的響應速度、可靠性與便捷性。依據災后區域通信網絡恢復要求與現實問題，我們提出了基于覆蓋網絡的單跳原路由策略，選取最短恢復路徑，設計了一種災后通信網絡恢復急救系統(Post-disaster Communication Network Recovery Emergency System,PES)。PES系統應用需要在網絡拓撲中提前配置代理服務器。網絡恢復急救系統進行系統恢復時，路徑為節點0到節點12。PES系統網絡故障恢復用例如圖5所示。

圖5 PES網絡故障恢復用例圖

圖5中，節點0設置為源節點，其中目的節點為節點12，系統恢復中源節點會經由節點5、節點10、節點11最終至目的節點12。圖5中多邊形陰影區域為系統中受災難影響的故障區域。故障損毀了系統中節點10及其附近的網絡流量鏈路，節點10相互連接距離最近的節點8與節點11并未因災害發生故障。故障出現后節點10所在位置在短時間內會出現信息爆炸現象，同時節點10附近的節點8與節點11 也會受到影響而出現嚴重的網絡信息流量過載問題。為了避免信息過載制約通信網絡恢復，不應使用圖5中虛線所框選的區域。運用系統中的代理服務器l1與l2，災后區域故障中產生的流量可以通過代理服務器以新的路徑進行傳輸。結合PES系統中源節點與目的節點，可確定流量重新傳輸的路徑長度為

(6)

式中:li與lj為PES系統中的代理服務器，略過故障位置及附近節點進行網絡流量重傳需要進行多跳代理，以保證源節點s傳送到目的節點t。

網絡流量傳輸中系統會主動選取可用傳輸路徑，若傳輸中出現路徑阻塞，則會直接丟棄無用流量轉發數據包。快速恢復中選用擁塞感知路由可防止故障區域網絡不穩定狀態的影響，保證系統的連通性，可以最大程度地降低網絡流量路徑傳送中的鏈路壓力；多跳代理方式可在路徑堵塞后及時判斷選擇新的節點路徑。本文基于勢能路由策略[12]，提出了覆蓋網絡節點擁塞感知的轉發算法：

(7)

式中:Vd(υ)為節點到系統目的節點的距離，Vc(υ)為故障節附近節點的網絡流量負載情況。

同樣基于勢能路由策略，結合災后故障快速恢復系統需求提出了網絡流量驅動力。與路徑距離和路徑負載相對應的網絡流量驅動力計算公式如下：

(8)

(9)

式中:Fd(υ,ω)的存在可保證快速恢復網絡路徑中不出現回環，Fc(υ,ω)是覆蓋網絡中構建擁塞感知路由的主要驅動力。擁塞感知路由算法(算法2)偽代碼如下：

nbrd(υ)←?

forall theω∈nbr(υ)do

ifFd(υ,ω)>0 then

nbrd(υ)←nbrd(υ)∪ω

forall theω∈nbrd(υ)do

找到驅動力Fc(υ,ω)最大的鄰居節點ω

將流量轉發給鄰居節點ω

2.2 PES系統實現

應用覆蓋網絡與源路由技術，考慮到災后區域故障損毀后信息爆炸增長現象設計的PES系統由覆蓋節點與客戶端兩個模塊構成。災后故障損毀快速恢復中若成功應用PES系統，需解決覆蓋節點轉發數據問題。現有解決方案為在系統應用層通過添加自定義頭部信息完成數據包處理[13]，系統轉發節會依據添加的頭部信息確定流量后序跳轉節點。此方法雖實現了覆蓋節上轉發數據，但所有轉發數據都需經協議處理，系統時延過長。

本文基于netfilter框架提出了覆蓋網絡上轉發節點的新方式。在netfilter框架下用戶可主動進行轉發數據包修改與刪除等操作，系統IP層也可對轉發數據包改動，netfilter框架下的數據處理工作更加高效。

PES系統快速恢復運行框架如圖6所示。

圖6 PES系統運行基本框架

PES系統客戶端模塊中由故障檢測子模塊與轉發自模塊構成。客戶端啟動開始運行PES系統后，故障子模塊同時啟動，工作中以TCP/IP子協議控制報文協議回顯請求包進行路徑探測。系統客戶端可設置故障檢測的路徑探測時間間隔，路徑探測中若子模塊未收取到響應信息，客戶端模塊系統將直接判定系統路徑中出現了故障。客戶端模塊會借助Linux系統中的Iptables防火墻工具將數據包發送至轉發子模塊中，信息收取后轉發子模塊將有序進行修改數據包，確保數據流中的連接信息可全部傳輸到PES系統重傳數據包中，系統覆蓋節點可按照數據內容將數據包轉發給相應的覆蓋網絡節點。上述流程為PES系統運行框架中的第2步。考慮到PES系統運行中的額外流量負載，僅通過源節點與目的地址中進行連接。

PES系統覆蓋網絡節點模塊由鄰近檢測子模塊與轉發器構成。應用PES系統進行快速恢復網絡時擁塞感知路由需要及時捕獲鄰近節點的網絡負載信息，覆蓋網絡節點模塊中的鄰近檢測子模塊主要承擔此項工作，模塊運行中覆蓋節點會主動與鄰近節點交換負載信息，附近節點的負載信息通過UDP封裝進行數據傳輸。覆蓋節點接收到重路由數據包后會借助Iptables工具將數據傳送到轉發器子模塊，并確定數據包的目的節點。

覆蓋網絡與源路由網絡快速恢復系統應用中應考慮到系統適用性與低成本性。災后通信網絡損毀后必然會導致網絡流量短期內爆炸性增加，此時應充分考慮到系統擴充代理的重要性。系統需要借助擴展代理方式提升網絡流量的負載能力。在PES系統基礎上提出了代理節點擴展算法(算法3)，偽代碼如下：

Input:鄰接矩陣A(G)、G的拉普拉斯矩陣L(G)和候選集E

Output:最優負載結果eij=St

begin

循環，第t(t≥1)次循環

若Ecard(St)=1或t>[lb(ξ/ε)]，跳出循環

S+={φ},S-={φ}

對St中信息進行二分運算

foru=1 to card(St) do

iff(M)>0 theneij→S+

elseeij→S-

M=(L+U)/2

t=t+1 return

2.3 PES系統實用性檢驗

2.3.1 仿真實驗設定

(1)PES系統仿真實驗拓撲選取隨機拓撲與真實拓撲。隨機拓撲由LEMON Graph Library庫的拓撲生成器隨機生成。仿真實驗選擇美國本土的CONUS為真實拓撲來源，隨機拓撲被全部搭建在Emulab平臺中，并全部隨機均勻分布于區域上。本次仿真實驗選取隨機拓撲中的50個節點隨機拓撲與真實拓撲基本信息如表2所示。

表2 兩類拓撲基本信息

(2)應用Totem工具箱中的Gravity模型為隨機拓撲與真實拓撲提供流量需求。選取確定性區域損毀模型表示區域損毀對網絡的實際影響。以圓形范圍區域表示災后區域損毀的實際影響范圍，地震自然災害的一般損毀范圍可達90 km。仿真實驗中將隨機拓撲故障區域影響范圍半徑設置為40 km，真實拓撲故障區域影響范圍設置為86 km。

(3)PES系統性能評估中選取了網絡流量恢復比例指標、路徑長度與跳數指標、收斂時間指標。為突出PES系統的實際性能，與響應式重路由算法進行對比。

2.3.2 仿真實驗結果分析

(1)覆蓋網絡節點數量情況

覆蓋網絡節點數量直接影響了PES系統性能，若系統中覆蓋網絡節點數量過低，單個節點信息處理工作量將會顯著增加，PES系統可能會出現信息負載現象，網絡周邊鏈路也會出現阻塞現象，快速恢復系統的應用性能極大下降。觀察不同覆蓋網絡節點數量下PES系統的恢復性能，對比結果如圖7所示。

圖7 覆蓋網絡不同節點數量對PES系統性能的影響

由圖7不同覆蓋網絡節點數量下PES系統恢復性能對比結果可知，當覆蓋節點數量為達到拓撲節點總數的20%時，PES系統具有非常高的恢復比例。

(2)PES系統與響應式重路由算法性能對比

圖8為兩類不同策略恢復流量比例，兩類系統隨機拓撲與真實拓撲的性能對比如圖8(a)和(b)所示。

(a)兩類系統隨機拓撲性能對比

(b)兩類系統真實拓撲性能對比圖8 兩類系統隨機拓撲與真實拓撲的性能對比

由圖8可知，兩類系統性能對比中，隨著兩類網絡的流量需求不斷增加，兩類系統的網絡負載性能發生了顯著變化，流量矩陣的比值從原始的1倍速提升到了5倍速。RTR系統隨著流量比例的增加系統快速恢復性能逐漸下降，并且下降趨勢不斷增加，在流量比例提升到測試最大值后期恢復性能僅為初始性能的20%。隨機拓撲與真實拓撲仿真測試結果表明，響應式重路由算法無法在災后區域通信故障中實現系統的快速恢復，系統無法滿足故障區域短時間信息爆炸所產生的網絡流量擁塞處理需求。而本文提出的PES系統隨著網絡負載信息的顯著提升雖有所下降，但系統仍保持著較高的信息處理能力，PES系統通過多路徑方式可有效避免單一路徑的網絡擁堵，防止出現嚴重的網絡擁塞情況，系統在災后區域通信故障快速恢復中可發揮積極作用，滿足災后通信故障處理的需求。

PES系統在不同拓撲下的路徑長度大小如圖9所示,災后通信網絡恢復路徑經過的覆蓋節點跳數如圖10所示。

圖9 不同拓撲下PES系統路徑長度大小

圖10 災后通信網絡恢復路徑經過的覆蓋節點跳數

由圖9可知，PES系統在不同拓撲下由65%的網絡快速恢復路徑小于1.8。PES系統進行網絡快速恢復中重路由數據包通過主動探測會避開災后故障區域與系統堵塞區域，系統將數據包從源節點傳遞到目的節點會經過較長且比較復雜的路徑完成恢復工作。

災后通信網絡恢復路徑經過覆蓋網絡節點跳數與網絡快速恢復時間密切相關。借助Emulab平臺進行仿真實驗中，發現單一覆蓋網絡節點處理單一數據包的時間處于0.3～0.5 ms。通信網絡快速恢復中所經過的覆蓋網絡節點跳數越多，總體時間會不斷增加，系統運行中源節點至目的節點的網絡時延也會明顯增加，影響快速恢復速度。由圖10可知，仿真測試重路經過的覆蓋網絡節點跳數以1～2個為主，根據重路由覆蓋網絡節點跳數，可基本判斷出系統數據包傳送時間處于1 ms以內，快速恢復速度較快。

3 結 論

本文綜合災后區域通信故障問題，應用覆蓋網絡與源路由提出了災后通信網絡連接恢復策略，結合了傳統主動式與被動式網絡恢復策略的優勢。 基于覆蓋網絡的災后通信網絡快速恢復策略具有顯著優勢:一是系統應用有效的中間節點算法選取區域位置中分布最為合理的中間節點，通信網絡恢復策略可快速選取新的傳輸路徑，網絡流量在傳輸中可借助源路由可及時跳過故障區域，通信網絡恢復可靠性明顯提升；二是考慮到網絡恢復中災后故障區域極容易發生網絡信息擁堵現象，在新恢復策略系統上加入了擁塞感知恢復系統，構建了PES系統。系統構建與覆蓋網絡架構上，在災后通信網絡發生損毀故障后，系統可實現跳級處理，系統中客戶端模塊與覆蓋節點模塊可保障系統中節點不會發生環路傳輸情況。仿真實驗表明系統在災后故障處理與系統恢復中均具有顯著作用。