基于QoS的衛星網絡端-端通信可靠性分析

蔡睿妍，潘蕓,*，魏德賓，石懷峰

1. 大連大學 通信與網絡重點實驗室，大連 116622 2. 大連大學 信息工程學院，大連 116622 3. 南京理工大學 自動化學院，南京 210094 4. 南京信息工程大學 電子與信息工程學院，南京 210044

對于廣義上的衛星通信系統來說，其空間段的組成部分——衛星本身就是一個結構復雜功能多樣的系統。傳統的系統可靠性理論假設系統只有正常工作和完全失效2種狀態，然而在衛星網絡實際運行周期內，由于沖擊、負載和老化等運行環境因素的影響使得衛星通信網絡往往處于逐漸劣化過程中，相較于二態系統、多狀態系統可靠性理論能更清楚地反映系統在使用過程中狀態不斷變化的規律[1-2]。早期對網絡可靠性的研究主要是從網絡拓撲結構出發來研究網絡的連通性，并沒有考慮網絡完成用戶需求的能力。目前，絕大部分對網絡端-端可靠性算法都是基于最小路集來計算的[3-6]，這些算法的一般求解過程是：首先求出網絡系統的最小路集，然后再利用容斥原理法或不交積和法計算網絡端-端可靠性。

隨著信息技術的發展和人們對衛星通信網絡的業務要求逐步提高，網絡的可靠性[7-11]一直是研究的熱點問題。QoS(Quality of Service)對確保業務量不受延遲或丟棄、保證網絡的高效運行起著至關重要的作用。Lin[12]提出將系統可靠性定義為在時間閾值T和預算帶寬B下d單元數據從源發送到接收器的概率，以一種簡單的下邊界點生成算法為基礎計算系統的可靠性。宋鳳等[13]在傳統不帶路徑約束的雙端和k端網絡可靠性研究基礎上，提出了基于截斷的路徑約束方法，并根據該方法構造二元決策圖(Binary Decision Diagram，BDD)模型進行帶約束的k端網絡可靠性分析。王秀君等[14]將網絡中QoS約束指標指定為帶寬和時延，通過鏈路不相交相似路由篩選來找到鏈路不相交的最短相似路由。喬曉東[15]提出一種考慮容量、時間以及可靠度約束的網絡端-端可靠性計算，通過BDD不交化求出網絡端-端可靠性。

以上現狀并沒有針對不同業務對可靠性進行分析，只考慮了部分QoS約束。由于衛星通信網絡承擔著多種業務，典型的有語音業務、視頻業務、移動定位業務、圖像下載業務等。業務類型不同，其對端到端傳輸時延、傳輸帶寬等需求也有所不同。如何滿足不同業務的QoS需求實現網絡端-端可靠傳輸顯得尤其重要。

在以往的最小路集和最小割集的算法中，端-端可靠性的計算都是基于單路徑傳輸的。在多路徑傳輸方面，Lin[16]為了縮短傳輸時間，使用允許數據同時通過多個最小路徑發送的傳輸協議，將隨機流網絡流量從單路徑傳輸擴展到2條及多條不交化路徑傳輸的情況。為了解決使用具有不同延遲的不同路徑導致相同流的數據包之間出現重新排序的問題，Yabandeh等[17]提出基于UDP(User Datagram Protocol)的方法嘗試按順序將數據傳遞給接收者，同時在接收者的應用程序上施加盡可能小的延遲和緩沖空間。仿真結果表明，多路徑傳輸的性能與最優單路徑相當。

在實際網絡環境中，端-端多路徑傳輸可以有效地聚合多條接入路徑的帶寬，從而使得網絡獲得更大的吞吐量，來滿足業務對帶寬的需求。屬于同一業務的數據從多條路徑傳輸，增加了從單條路徑竊聽數據進而嘗試恢復初始數據內容的難度，提供了更好的數據私密性。而且多條端-端路徑同時使用，可以根據網絡中的擁塞狀況動態地調整數據在不同路徑的發送速率，從而實現在網絡邊緣處的負載均衡[18]。因此，多路徑傳輸的可靠性問題也不可忽視。

綜上，本文在衛星網絡的多狀態特性分析的基礎上，針對業務QoS需求進行了網絡端-端可靠性研究，即考慮鏈路的多狀態和傳輸不同業務類型對網絡可靠性產生的影響。本文中假設節點為正常工作狀態。又因為多路徑傳輸在衛星網絡中廣泛使用，在單路徑可靠性研究基礎上進一步對多路徑傳輸的可靠性進行分析。結果表明不同類型的業務由于不同的QoS需求，可靠性并不相同，且網絡多路徑傳輸比單路徑傳輸可靠性高。

1 基于MPSA的端-端可靠性分析

在經典的最小路集算法(Minimum Path Set Algorithms，MPSA)分析網絡端-端可靠性的算法中，其基本思想是：先確定網絡拓撲的源端和目的端,并寫出網絡的鄰接矩陣和終點矩陣,再通過最小路集算法計算得出網絡的所有最小路集，最后將這些最小路集通過不交化計算并代入各鏈路可靠性得出網絡端-端可靠性的精確值。下面給出基于最小路集的端-端可靠性分析方法的相關定義[19]。

問題描述 設N=(V,E)是一個簡單有向網絡，V={v1,v2,…,vn}為節點集，E={a1,a2,…,am}為弧集。一個簡單的雙端網絡如圖1所示。

圖1 一個簡單的雙端網絡Fig.1 A simple two-terminal network

定義2 網絡的終點矩陣Z=[zjk](1≤j≤n;1≤k≤n)， 其中，

且當j=k時，zjk=0。網絡的終點矩陣反映了網絡中每條弧的終點。

定義4 BDD是一種用來表達布爾邏輯函數的有向無環圖，在BDD上搜索從根節點到葉節點為1的路徑，即可獲得不交化最小路集。如圖1中以v1為源端、v4為目的端的端-端最小路集用函數,表示為f=a1a5+a2a6+a1a3a6+a2a4a5。根據BDD定義將函數f用BDD表示如圖2所示。

圖2 BDD不交化Fig.2 BDD minimization algorithm

則端-端最小路集不交化后為

定義5 端-端可靠性定義為在QoS約束下，將數據流從源節點成功傳輸到目的節點的概率。

2 端-端可靠性分析

2.1 業務分類

在實際網絡運行過程中，由于不同類型的業務對QoS要求不同，傳輸業務滿足QoS需求才是真正可靠。本文提出針對傳輸不同業務的約束條件(時延、帶寬和丟包率)的不同，將傳統的MPSA改進為適應不同業務QoS需求的算法，從而在網絡可靠性的分析中，對不同業務進行差異分析。

根據不同業務對指標要求的差異，將業務分為3類，分別為時延敏感業務、帶寬敏感業務和可靠性敏感業務[20]。時延敏感業務對時延指標較為敏感，要求具有較低的端到端時延。帶寬敏感業務的特點是需要大帶寬的鏈路進行傳輸，但不要求時延很快。可靠性敏感業務對端-端傳輸可靠性要求高，要求較小的網絡丟包率。

2.2 相關指標分析

1) 時延。時延是指一個報文或分組從網絡的一端傳送到另一端所需要的時間。包括報文或分組在節點上被處理、從節點發出以及在節點間傳播一定的距離而花費的時間消耗，即時延=處理時延+排隊時延+發送時延+傳播時延。本文僅考慮發送時延與傳播時延。文中設Tmax為端-端最大時延約束，傳輸路徑的總時延T應小于最大時延Tmax，否則此路徑認為不可靠。

2) 帶寬。帶寬表示數據的傳輸能力，指單位時間內能夠傳輸的比特數。文中設Bmin為最小帶寬，傳輸路徑中的每條鏈路帶寬B應大于最小帶寬Bmin，否則此路徑不可靠。

3) 丟包率。在本文中，將鏈路誤碼率通過丟包率Ploss來表現，指的是一次數據傳輸過程中，由于網絡擁塞、傳輸過程噪聲較多等因素影響，導致數據校驗時，數據包遭到破壞不能通過校驗被丟棄與所傳數據包總數的比值。文中設Pmax為最大丟包率，傳輸路徑中的總丟包率P應小于最大丟包率，否則此路徑不可靠。

4) 鏈路可靠度。規定的條件和時間內鏈路無故障工作的概率，反映鏈路完成規定功能的能力。

2.3 鏈路多狀態分析

由于星間鏈路傳輸距離較長，以及通信鏈路所處傳輸環境的復雜性，通常伴隨著較高的路徑損耗，且傳輸過程中通信信息受到噪聲及干擾的影響較多，使得鏈路的狀態處于正常工作和完全失效2種狀態之間的多個狀態。

2.4 端-端可靠性算法

2.4.1 算法思想

本文算法的基本思想是針對衛星網絡鏈路的多狀態特性，根據傳輸業務的QoS約束找到對應網絡狀態下的最小路徑集，對最小路集不交化處理再代入各鏈路可靠性計算網絡端-端可靠性。

2.4.2 時延相關表達式

本文端-端網絡時延由發送時延和傳播時延2部分組成，相關表達式為

Tsend=packet/B

(1)

Ttrans=Llink/c

(2)

T=Tsend+Ttrans

(3)

式中：Tsend為發送時延；packet為文件大小；B為帶寬；Ttrans為傳播時延；Llink為鏈路長度；c為電磁波在信道上的傳播速率。網絡端-端時延為發送時延和傳播時延之和。

2.4.3 算法步驟

基于業務QoS需求的端-端可靠性算法流程如圖3所示，算法基本步驟為

圖3 基于業務QoS需求的端-端可靠性分析流程圖Fig.3 Flowchart of end-to-end reliability analysis based on requirement of service QoS

步驟2 鄰接矩陣每一個元素代表著2節點之間的鏈路，將此時鏈路帶寬與最小帶寬比較，若鏈路帶寬小于最小帶寬，該元素設為0，更新矩陣A1，否則直接跳到步驟3。

步驟7 根據BDD定義將函數f不交化處理，代入各鏈路可靠度求得網絡端-端可靠度。

3 算例分析

3.1 問題描述

將衛星運行周期Tp分成n個時間片[t0=0,t1],[t1,t2],[t2,t3],…,[tn-1,tn=Tp]。在每個時間片內，假定拓撲結構不變，且鏈路的切換和網絡拓撲的變化只在時間點t0,t1,t2,…,tn-1時刻發生，一個時間片內的衛星網絡拓撲如圖4所示。

圖4 衛星網絡拓撲圖Fig.4 Topology of satellite network

每條鏈路遵循統計獨立的失效概率，各鏈路狀態及其對應帶寬如表1所示，每條邊的狀態概率分布及傳輸時間Ttrans和丟包率如表2所示，各業務的QoS需求如表3所示。

表1 各鏈路狀態及其對應的帶寬Table 1 Link states and their corresponding bandwidths

表2 鏈路狀態數據Table 2 Data if link states

續表2 鏈路狀態數據Table 2 Data if link states

表3 各業務QoS需求Table 3 QoS needs for each service

3.2 過程分析

根據表2鏈路狀態概率生成一組網絡狀態(3,2,3,3,2,3,3,3,2,3,3,3,3,1)，以傳輸2 Mbit的文件為例，分別對文件為時延敏感業務、帶寬敏感業務和可靠性敏感業務進行分析。

步驟1 根據圖3得知此端-端衛星通信網絡的源節點為v1、目的節點為v8,此網絡的鄰接矩陣為

A1=

終點矩陣為

步驟2 由2.4.3節算法步驟運算得知：對于時延敏感業務，此時滿足QoS需求的可靠最小路集為{a1a4a9,a1a4a8a12}；對于帶寬敏感業務，可靠最小路集為{a1a4a8a12}；對于可靠性敏感業務，可靠最小路集為{a2a5a12}。

步驟4 將各邊的可靠度代入，即可求出網絡端-端可靠性。此時，時延敏感業務端-端可靠性值為89.37%，帶寬敏感業務為81.45%，可靠性敏感業務為76.95%。

3.3 結果分析

設置多組文件大小，重復3.2節運算步驟，本文算法結果如圖5所示。

Lin等[12]中外學者沒有考慮不同業務下的網絡的端-端可靠性，在上述設定下，3種業務可靠性都相同。然而實際上從圖5可以看出，3種不同類型的傳輸業務，在文件大小為2.5 Mbit時，時延敏感業務可靠性此時降為0，而帶寬敏感業務和可靠性敏感業務此時仍具有高可靠性。可以看出在傳輸同等大小的文件下不同業務可靠性是不同的。本文算法顯示，相同文件大小的情況下，傳輸業務類型的差異終將導致端-端可靠度的差異。并且，本文算法與最小路集算法相比只增加了if-else判斷，沒有增加for循環的次數，所以算法的時間復雜度依舊沒變，但由于if-else判斷刪除了不滿足QoS需求的鏈路，導致最終滿足條件的最小路集里項數的減少，在BDD不交化處理時得到一定的簡化，使得計算復雜度得到有效的降低。

圖5 3種業務可靠性對比Fig.5 Comparison of reliabilities for three services

4 多路徑端-端可靠性

多路徑傳輸是指采用多條不相交的路徑來投遞分組以增加連接的容量和可靠性的機制。在3.2節最小路徑集求解網絡端-端可靠性的過程中，網絡可靠性為所有可靠路徑的概率和，但此時的路徑是獨立傳輸各種業務。本文在上述研究基礎上，進一步對多路徑傳輸可靠性進行了研究，與單路徑的對比顯示，多路徑傳輸的可靠性得到了提高。

4.1 算法思想

在端-端網絡中，找到源端到目的端的所有傳輸路徑。網絡多路徑傳輸若要可靠，則需要每條路徑時延都要滿足需求，所有路徑的總帶寬大于需要的傳輸帶寬。在每條路徑時延、帶寬滿足的情況下，計算多路徑可靠性，若可靠性滿足要求，則多路徑可靠，否則不可靠。約束公式為

(4)

式中：i為滿足條件的路徑集L中的路徑；m為路徑集L中的路徑個數。由于每條路徑帶寬不同，傳輸時需要對每條路徑應該承擔的帶寬大小進行分配。每條路徑應該承擔的帶寬大小為

(5)

多路徑傳輸時每條路徑的發送時延為路徑需要傳輸的數據帶寬在當前可用帶寬下的發送時延：

Tsend=B′i/Bii∈L

(6)

多路徑端-端時延為所有路徑的最大端-端時延：

T=Max{Ti}i∈L

(7)

4.2 可靠性分析

以圖4網絡為例，多路徑傳輸時，滿足時延敏感業務QoS需求的多路徑是{a1a4a9,a2a5a12,a3a7a14}，滿足帶寬敏感業務QoS需求的多路徑路集是{a1a4a9,a2a5a12,a3a7a14}，滿足可靠性敏感業務QoS需求的路徑是{a2a5a12}。多路徑傳輸時，網絡可靠性得到提高，時延得到縮短。

圖6顯示利用多路徑并行傳輸2 Mbit文件，在不同業務下單路徑與多路徑傳輸時間比較。可以看出，時延敏感業務和帶寬敏感業務多路徑傳輸時，時延都得到了縮短。而由于可靠性敏感業務滿足設定條件的路徑只有一條，實際上仍然是單路徑傳輸，所以時延沒有縮短。

圖6 多路徑和單路徑時延對比Fig.6 Comparison of delays for multipath and signal path methods

圖7顯示為傳輸時延敏感業務時，單路徑和多路徑端-端可靠性的比較。可以看出，在單路徑傳輸時隨著文件大小逐漸增大，時延敏感業務的時延需求漸漸達不到要求，單條可靠路徑降為0，而多路徑傳輸由于帶寬增大，傳輸同樣大小的文件的時延得到縮短，在單路徑可靠性降為0時，仍保持著高可靠性。同理，帶寬敏感業務和可靠性敏感業務隨著傳輸文件的增大，單路徑可靠性降為0時，多路徑共同傳輸起到提高網絡可靠性的重要作用。

圖7 多路徑和單路徑可靠性對比Fig.7 Comparison of reliabilities for multi-path and single-path methods

5 結 論

1) 本文針對傳統網絡端-端可靠性分析中，計算網絡端-端可靠性時沒有體現傳輸不同業務的可靠性差異的問題，在衛星網絡的多狀態特性分析的基礎上，通過案例模型分析了傳輸3種類型業務的可靠性。結果證明，該算法能很好地分析傳輸同樣大小的文件時，由于業務類型差異導致的QoS指標差異從而帶來的網絡端-端可靠性的區別，比傳統算法更貼近實際。

2) 由于端-端并行多路徑傳輸在衛星網絡上廣泛使用，本文在上述研究的基礎上，進一步對多路徑的端-端可靠性進行了研究。研究結果顯示多路徑數據傳輸對比單路徑傳輸時，端-端時延得到了縮短，可靠性在文件增大時得到了提高。本文的鏈路雖然有多個狀態，但在實際運算中，只在一組已知狀態下分析了網絡端-端的可靠性，在接下來的研究中，將考慮根據狀態概率生成的網絡狀態組合下的端-端可靠性。