基于馬爾可夫鏈的軍用Ad hoc網絡可用性建模

傅妍芳， 王贊， 蘇一昶， 戴飛， 鐘聯炯， 郭登登， 盧穎， 梁洪濤

(1.西安工業大學 計算機科學與工程學院， 西安 710021； 2.陜西師范大學 物理學與信息技術學院， 西安 710119)

0 引言

自1991年海灣戰爭以來，現代戰爭的作戰模式已然發生了極大的變化。美國國防預先研究計劃局(DARPA)正在發展名為“馬賽克”作戰的新作戰概念，提出由傳統上單一平臺提供的整體式殺傷鏈功能，向由多種殺傷鏈組成的動態分布式網絡作戰效果發展。隨著這場軍事的變革，軍用通信網絡的規模和復雜程度日益擴大，軍事通信業務迅猛增長，尤其由無線移動節點組成的多跳、無中心、能量有限、臨時的分布式協同網絡(移動Ad hoc網絡)，其可用性的建模與驗證評估的需求也越來越迫切，建立高可用性的網絡是準確、及時進行信息交換的基礎，從而滿足網絡系統適應面向各類用戶提供高可靠服務的需求。因此，研究基于不同環境條件下多種網絡參數的分布式協同網絡可用性技術，通過可用性分析信息統一建模與表達，構建新一代分布式作戰網絡可用性定量評估模型，提升新作戰概念下多平臺信息交互及戰術協同能力，確保系統服務效能的發揮及穩定可靠運行能力的形成。

軍用網絡傳統可用性概念是可靠性理論中一個度量可靠性指標?？煽啃灾荒芊从吵鼍W絡系統或者組件出現故障的概率，而可用性考慮了網絡的可修復能力，更能反映出網絡的品質。因此，分析戰術通信網系統的可用性是衡量系統組網設計優劣、系統穩定性以及系統維護能力的一個重要指標。網絡可用性是評估網絡質量好壞的一個重要標準，它是對網絡中節點可靠性、鏈路質量可靠性、網絡拓撲、業務流量、路由算法等因素的一個綜合評價，反映了網絡在不考慮外來破壞性作用的情況下節點間能夠提供可持續性服務的能力。

現如今，國內對可用性的研究大都是針對復雜系統的工程能力：馮海林[1]研究了網絡系統中的可靠性以及可用性，并分析計算了其穩態可用度；張靜樂[2]針對電商系統建立了基于隨機Petri的可用性模型。

在網絡可用性的研究方面：Yin等[3]指出對網絡可靠性的研究應該從環境與業務等不同剖面進行分析；董海青等[4-6]研究了基于業務的網絡可用性指標，從用戶的角度出發，考量了計算機網絡滿足用戶需求的能力，提出影響網絡的性能的主要指標包括傳輸延時、延時抖動、吞吐量、丟包率等參數，并對網絡可用性的分析做了一些探索。

為了研究移動Ad hoc網絡的定量評估問題，需要認真關注移動Ad hoc網絡的時變參數，包括鏈路負載、路由長度、延遲、移動性等，而早期的大部分研究工作都是針對具體的單個參數進行的。

考慮到節點的移動性，Cho等[7]研究了恒定速度模型下、單跳情況下鏈路持續時間的平均值，并推廣到多跳情況下；Liu等[8]使用隨機路點移動模型研究了源節點和目標節點為固定雙跳移動自組網(MANET)的鏈路持續時間機制；Guo等[9]提出了一種利用神經網絡方法預測每包單跳平均延遲的方案，然后節點使用預測的1跳延遲參與路由信息擴散；Tickoo等[10]從延遲和隊列長度方面分析了IEEE 802.11 MAC的性能，還評估了IEEE 802.11 MAC支持延遲敏感流量的能力，并發現延遲主要是與每個包傳輸相關的信道訪問和保留時間有關。該方面文獻重點開展了移動特性在鏈路持續時間機制和單跳中繼的建模研究。

Bisnik等[11]推導了基于開放G/G/1排隊網絡的多跳無線自組網分析模型，利用擴散近似法求解開放排隊網絡，推導出MANET端到端平均時延的封閉表達式，并得到了最大可實現吞吐量的表達式。文獻[12]在有損鏈路和有限緩存的情況下，提出了一種兩跳中繼-f冗余路由策略的中繼節點選擇策略；文獻[13]提出了一種應用于多跳網絡、基于協作節點可以自發幫助轉發數據包以提升系統性能的機制，在該機制中，分別研究信道優劣、節點Buffer長度和節點個數對整個系統的影響。

本文根據網絡可用性的定義,考慮了移動Ad hoc網絡節點的移動、故障、傳輸協議以及中繼節點選擇策略等影響因素，針對移動Ad hoc網絡端到端的通信,提出了一種基于延時的業務性能定量評估模型，并通過移動Ad hoc網絡節點的移動特性建立了基于多跳的業務可用性模型，提升了軍用網絡適應多維度服務的能力，并確保軍用網絡服務效能的發揮及穩定可靠運行能力的形成。

1 基于故障的馬爾可夫可用性建模

1.1 Ad hoc網絡故障類型分析

在軍用通信網絡系統的規劃、論證、方案設計與優化方面，軍用通信網絡的安全性、可靠性問題顯得尤為重要。造成軍用通信網絡戰時出現故障的因素較多，可劃分為3個層次上的主要原因類型：

1) 在作戰過程中，部分戰術通信網絡因戰線推移或其他戰事需要實施戰術轉移或替換，由于通信節點移動或維修等問題導致網絡的持續工作能力和重組能力變差導致連接中斷為1類故障。

2)通信網絡系統在戰場上受地形、環境等原因造成的節點間通信鏈路阻斷、信號衰落、噪聲等引發的通信鏈路故障，隨機或突發的戰場軟殺傷為2類故障[14]。

3) 作戰過程中出現硬殺傷，包括指控系統及其重要組成部分通信網絡成為敵方首選的擊毀目標；指揮機構、指控車輛、干線節點等在作戰過程中由于電磁輻射密集暴露而擊毀；由于大量精制導武器的使用，使得通信網絡及其主要組成部件被發現直接摧毀?；蛘咴O備的自然損傷或故障，這類稱之為3類故障。3類故障因其發生概率較小、故障恢復時間較大而忽略不計。

1.2 移動模型

移動模型是用移動實體移動軌跡的一組規則來表示。作戰網絡的移動模式與人類日常生活和移動車輛的移動模式各不相同。一個綜合移動模型應該是代表性和簡單性的一個很好折衷，也就是說，它應該考慮某一運動模式的顯著特征，而忽略次要的細節。目前主要移動性模型包括隨機路點、參考點群、曼哈頓網格、高斯馬爾可夫模型等。為了進行模擬和分析，移動性模擬也應該是輕量級的，這樣就可以方便地與網絡模擬集成，本文采用的是隨機路點移動模型。

根據Ad hoc網絡的特點，建立如圖1所示的網絡模型，網絡中節點均勻分布且節點的運動相互獨立。A、B、C是一個作戰區域的3個子區域，a1、a2是區域A的節點，z1、z2是區域A、B的中繼節點，b1是區域B的節點，c1、c2、c3是區域C的節點，z3是區域B、C的中繼節點。為簡化分析，假設每個移動終端節點通信半徑相同并且同一區域內的節點可以直接通信，而位于不同區域的節點由于通信半徑的限制無法直接通信。例如，節點a1與節點b1通信時，需要通過中繼結點z1或z2.當中繼區域存在多個節點時，需要一種可以選出最合適中繼節點的選擇策略。

圖1 Adhoc中繼基本模型Fig.1 Ad hoc relay basic model

1.3 移動Ad hoc網絡可用性定義

傳統可用性的定義為：產品在任意時刻需要和開始執行任務時，處于可工作或可使用狀態的程度，可用性的概率度量稱為可用度。

Ad hoc網絡可用性目前沒有公認的定義，在由兩個以上網簇(子網)通過交互區的中間交換節點組成的自組網中，其交互區的所有交換節點或壞或移出交互區，兩個子網就成為兩個孤島。盡管網簇內的節點還能通信，但在本質上已不能認為是能互聯的移動自組網了。

基于以上觀點，根據傳統可用性的定義，結合Ad hoc網絡特性，則Ad hoc網絡可用性的定義可以描述為：Adhoc網絡的網簇間公共交換區有存活節點可提供中繼能力，使網簇間構成一個互通完整網絡的程度，其概率度量稱為Adhoc網絡的可用度。

1.4 馬爾可夫鏈模型

移動Ad hoc通信網絡系統是一個多狀態馬爾可夫可修復系統。系統由若干個網絡節點和若干個修理設備組成，每個節點的壽命分布均為1-e-λft,t≥0,λf>0，節點故障后的修理時間均為1-e-μft,t≥0,μf>0，所有這些隨機變量相互獨立，故障節點經修理后，其壽命與新的節點一樣。本文所采用的可用性模型為n中取g的表決系統模型，n為網絡系統中的節點總數，g為正?；蛘吖收系墓濣c個數。n中取g表決系統模型有兩類：一類為n中取g個好的節點系統，意思是組成系統的n個單元中有g個或者g個以上完好，系統才能正常工作，記為g/n[G]；另一類為n中取g個壞的系統，意思是組成系統的n個單元中有g個或者g個以上失效，系統就不能正常工作，記為g/n[F][15]。本文所采用的是第2類——g/n[F]系統，當故障節點小于g個時，系統正常工作并且修復故障節點；當有g個節點故障時，系統出現故障，這時剩下正常工作的節點也停止工作，不會發生故障，直到正在修理的節點修理好一個，又有小于g個故障節點，系統重新工作[16]。為簡化分析，給出以下條件：

1)所有節點移動、1類故障(節點故障)、2類故障(鏈路故障)等事件相互獨立；

2)所有獨立事件發生的概率服從負指數分布；

3)1類、2類故障轉換時延較小，在轉換延遲期間沒有額外的節點移入移出事件發生。

為評估圖1所示的Ad Hoc網絡端到端通信的可用性，選擇1跳通信線路a1?zi?b1進行分析，此時，通信系統的主要影響因素有a1,z={zi|1,2,3，…，n}和b1，其中z集合中的N個節點都可能成為a1到b1通信的中繼結點，i表示當前位于交叉區域并可供正常連接使用的中繼節點個數，i∈I={1,2,3,…,N}。設J為故障類型,J={0,1,2}，0為無故障，1為1類故障，2為2類故障。二元組{(i,j)|i∈I,j∈J}表示a1?zi?b1連接有效(或失效)時，當前交叉區域有i個(包括zi)可供中繼的正常節點，并且同時系統處于j類故障狀態[17]。

例如，狀態(1，0)表示當前網絡工作狀態正常并且交叉區域只有一個中繼節點參與中繼轉發；狀態(N，0)則表示網絡工作狀態正常，N個中繼節點位于交叉區域都能正常工作。當其中未參與中繼轉發的節點移出交叉區域時，網絡狀態轉移到(N-1，0)；當正在參與中繼轉發的節點移出交叉區域時，網絡狀態轉移到(N-1，1)；當中繼節點的通信鏈路受到干擾而導致中斷時，網絡狀態轉移到(N-1，2)。

由此可給各個狀態分配轉換概率，各個狀態與轉換概率的集合就轉化為一個連續時間的馬爾可夫鏈，如圖2所示。

圖2 馬爾可夫狀態轉換圖Fig.2 Markov states transition diagram

根據故障轉換延遲的長短，將故障類型作簡化為：

1)考慮節點的移動性，節點的平均移出率是λ，平均移入率為μ；

2)1類故障的發生間隔時間期望值是λf，1類故障維修時間期值是μf；

3)2類故障的發生間隔時間期望值是λs，2類故障維修時間期值是μs；

2 可用度分析

2.1 單跳端到端可用度分析

穩態可用度是馬爾可夫可修系統的可靠性特征量之一，其含義是當網絡運行達到穩態時，網絡在整個運行時間內處于正常工作的時間所占的比例，也就是網絡在整個運行過程中處于連通狀態的概率。

1類故障的發生間隔時間期望值為λf，2類故障的發生間隔時間期望值為λs，并且λf+λs=1；用二元組{(i,j)|i∈I,j∈J}表示源節點?中繼節點?目的節點連接的網絡可用狀態,計算網絡業務的可用度，其中對(n，0)有：

(1)

式中：πn,0為網絡處于狀態(n,0)時的穩態可用度。因此通過一次中繼網絡端到端的穩態可用度為

(2)

2.2 多跳網絡的可用度分析

圖3為Ad hoc網絡的多跳傳輸模型，數據包從源節點出發經中繼結點最終成功傳輸給目的節點的穩態可用度計算可通過(2)式計算。

圖3 多跳傳輸模型Fig.3 Multi-hop transmission model

通過理論簡化，為了計算多次中繼通信網絡端到端的穩態可用度,可以將這次網絡中存在的多次中繼穩態可用度進行綜合，當然各跳所占的比重有差別，即

(3)

式中：Δ1為1跳情況下網絡系統中所占的比重；A2為2跳的穩態可用度，Δ2為該情況下網絡系統中所占的比重；Ak為k跳的情況下的穩態可用度，Δk為該情況下在網絡系統中所占的比重。

2.3 中繼節點選擇策略

中繼區域往往有多個中繼節點存在，中繼節點的選擇策略對網絡的性能有著至關重要的影響。因此，本文根據所建立的網絡可用性模型的特點，從節點故障的角度出發，結合節點的負載開銷和飽和度兩方面的限制，提出了一種基于瞬時失效率的中繼節點選擇策略。

負載方面的限制可表示為0

(4)

式中：li為中繼節點i上層業務的負載開銷；lt為中繼節點的負載閾值，負載開銷不能超過負載閾值；pli為節點i負載開銷的合格率，如果pli≤0，則該中繼節點不參與數據包的轉發。

瞬時失效率qi為x時刻還在正常工作的產品中，在x時刻后Δx時間間隔內有多大概率的發生故障，導致產品不能正常工作，

(5)

式中：A(x)是網絡的穩態可用度，x是中繼節點i已經工作時間，由于每次節點故障修復后，節點壽命與新的一樣，即x從0 s時刻開始重新計時，所以每個節點的實際工作時間是不一樣的，qi也具有差異性。

節點飽和度方面的限制可表示為：當節點飽和時，si=1，當節點處于空閑狀態時，si=ε，ε是一個非常接近于0的很小值，防止計算結果出現0.

結合瞬時失效率qi、負載開銷li和中繼節點飽和度si計算出定義中繼節點選擇策略的目標函數Q(0

(6)

根據當前時刻中繼節點i瞬時故障率對中繼節點優先級排序，Qi越小優先級越高，數據包在每次發送時，優先選擇Qi最小的中繼節點，當該中繼節點繁忙時，選擇次優節點，依次類推。

3 基于延時的業務可用性評估模型

在一子網內，節點對信道的占用機制通常為CSMA/CA通信機制。本研究是通過對CSMA/CA通信機制進行定量分析來討論受網絡性能影響的網絡可用度問題。通過參考文獻[18-19]，建立以下假設：

1)滿足飽和條件。即每一個節點都總是有將要需要發送的數據包；

2)信道中沒有隱藏的網絡節點，是理想化的信道；

3)n個網絡節點爭用同一個接入信道傳輸數據。

基于上述假設，根據馬爾可夫模型對單一網絡節點行為的研究，得到網絡節點在一個隨機時隙內傳輸發生沖突的概率P與傳輸數據包的穩態概率τ. 有n個相互競爭處于飽和狀態下的節點，每次發送成功后，每個節點都有一個準備發送的數據包。此外，所有的數據包都是連續的，每個數據包在發送之前都有一個隨機的回避時間以減少發生沖突的概率。

CSMA/CA采用的離散時間回避機制是指數回避機制，在每個包的傳輸中，回避時間均勻地選擇在(0,w-1)范圍內。w的值稱為競爭窗口，競爭窗口的大小取決于包發送失敗的次數[20]。不管重發次數,每個包嘗試發送時,發生沖突的概率是P.w0為最小競爭窗口，wm=2mw0，m為發送失敗回退階數，m∈[0,M]，M為最大回避階數。

由于所有的站點只有在回退計數器為0時才傳輸包，因此得到穩態概率τ的值。τ和P分別為

(7)

P=1-(1-τ)n-1,

(8)

式中：(1-τ)n-1為其他n-1個節點都不傳輸數據包的概率，用迭代逼近法可求取τ和P. 根據τ和P，計算每一輪平均回退窗口：

(9)

Ps=nτ(1-τ)n-1，

(10)

PN=(1-τ)n，

(11)

Pc=1-Ps-PN,

(12)

式中：Ps為每一輪發數據包成功傳輸的概率；PN為數據包不傳輸的概率；Pc為數據包傳輸但發生沖突的概率。

當計算每一輪發報文平均回退時間是和每一輪發報文平均回退窗大小、時隙時長等因素相關。延遲時間由(12)式計算得到：

(13)

式中：Ebm為每一輪發報文平均回退時間；Ts為數據包成功傳輸時信道處于通道忙碌狀態的時間；Lγ=Ebγ+Tc+T0，Tc為數據包傳輸發生沖突時通道忙的時間。

報文的平均傳輸延遲概率分布率是Pm=P(1-P)m，當發送M次都發生沖突不成功時，終止發送報告上層相應m-1次沖突后，報文發送成功，其報文的傳輸延遲時間是Em，其中對所有的Em≤TB，TB為軍用網絡時延的戰技指標。

(14)

式中：u為跳數,u∈[0,k]；F1為1跳的時延達標率。多跳平均時延達標率為

(15)

應用統計學原理，建立了基于時延的業務可用度模型，即將網絡業務性能(多跳平均時延)達標率和穩態可用度進行綜合運算，則得到整個戰術通信網絡的業務可用度。

4 仿真實驗結果分析

為驗證上述模型在通信網絡中的正確性和實用性，本節參照圖1所示的網絡模型進行仿真實驗，設計了多組實驗并與理論計算結果進行對比。本實驗仿真對象是執行作戰任務的戰術小分隊，分隊由20個單兵組成，每個單兵都裝備Ad hoc通信設備，均勻分布于20 km×20 km的平面區域，無線電臺通信半徑為2 km，作戰半徑為4 km，節點最大移動速度為5 km/h，信道傳輸速率2 Mbit/s，中繼最大值為4跳。其中所有節點的運動均按照隨機路點移動模型進行仿真。

通過對軍用移動自組織網絡可用性建模理論的研究，進行了建模和仿真實驗，其參數如表1和表2所示。

表1 可用度基本參數

表2 業務可用度參數

各實驗根據Ad hoc網絡特點以及建模時分析的故障類型，輸入節點發生故障的時間間隔以及故障維修時間，鏈路故障發生的時間以及修復時間，節點因功耗問題出故障的恢復時間等參數，最終計算出當前條件下網絡的穩態可用度，然后在CSMA/CA通信機制的業務可用度參數計算出基于傳輸時延的可用度值。以下實驗采用表2中的具體數值，并通過對照仿真結果，比較在不同實際網絡參數對網絡可用性的影響。

首先通過大量實驗模擬軍用Ad hoc網絡在不同干擾時間間隔對可用度的影響。在不同的干擾時間間隔實驗下，網絡穩態可用度的計算結果如圖4所示。然后根據模型算法將穩態可用度和時延達標率進行量化后可以計算得到基于傳輸時延的業務可用度，結果如表3所示。從模型算法結果可以看出，在干擾頻率超出一定界限時，網絡的穩態可用度急劇下降，并且受干擾的影響隨節點數的增加變大。

圖4 穩態可用度仿真結果Fig.4 Simulated results of steady state availability

表3 可用度量化表

在相同環境參數的條件下，也進行仿真實驗，實驗數據與本文模型數據非常接近(見圖5)。同時也表明了在干擾時間間隔發生變化時，隨著干擾時間間隔的增大，時延的業務可用度也在增大的實驗現象。

圖5 干擾時間間隔對可用度的影響Fig.5 Effect of interference time interval on availability

考量在中繼區域的節點選擇對網絡可用性的影響，本文提出的可用性評估模型中分別采用基于2跳中繼冗余策略和基于瞬時失效率的中繼節點選擇策略，并與仿真實驗進行可用度數值分析。在不同節點個數的網絡情況下，分別針對基于2跳中繼冗余策略模型和本文模型與仿真結果進行比對，結果如圖6所示。

圖6 節點個數對可用度的影響Fig.6 Effect of the number of nodes on availability

對比數據反映了作戰區域內節點個數與業務可用度的關系，隨著節點個數的增加，時延的達標率降低，基于時延的業務可用度會變小。此外，通過擬合度檢驗方法得出基于失效率的中繼選擇策略與仿真實驗的擬合度較高。說明中繼節點若發生故障而維修，將會影響節點之間的傳輸連續性，同時，若數據傳輸流量較大，中繼節點容易滿足飽和條件，通過選擇空閑中繼節點發出數據，網絡可用度更高。

針對信道傳輸速率和報文長度兩個因素分別對Ad hoc網絡可用性進行分析。實驗結果(見圖7)反映了信道傳輸速率與業務可用度的關系。并通過趨勢可以看出信道傳輸速率越快，傳輸時間越短，節點之間的時延就越小，時延達標率就越高。因此隨著信道傳輸速率的增加，基于時延的業務可用度也就越大。

圖7 信道傳輸速率對可用度的影響Fig.7 Effect of channel transmission rate on availability

實驗結果(見圖8)反映了報文長度與業務可用度的有緊密的關系。通過數據可以看出報文長度和信道傳輸速率剛好相反，報文長度越大，傳輸單個報文所需要的時間也就越多，所以節點之間的時延就越大，時延達標率就越低。因此，隨著報文長度的增加，基于時延的業務可用度在變小。

圖8 報文長度對可用度的影響Fig.8 Effect of message length on availability

5 結論

本文分析了移動Ad hoc網絡節點的移動特性和作戰環境造成的故障因素對網絡可用性的影響，建立了基于故障的移動Ad hoc網絡馬爾可夫可用性模型，并針對中繼區域節點的優先選擇問題，結合節點的負載開銷和飽和度兩方面的限制，提出了一種基于瞬時失效率的中繼節點選擇策略。通過分析基于CSMA/CA的傳輸機制，研究影響網絡業務主要因素的延時模型，建立了基于業務可用度的定量計算方法，計算了基于傳輸延遲的網絡業務可用度。最終以某典型陸軍戰術分隊通信網為例，通過理論建模與仿真實驗進行對比，二者之間的數據平均誤差小于9%，說明建立的可用性計算模型能夠較準確地反映軍用Ad hoc網絡可用性。