基于QoS的衛(wèi)星網(wǎng)絡(luò)端-端通信可靠性分析

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

1. 大連大學(xué) 通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，大連 116622 2. 大連大學(xué) 信息工程學(xué)院，大連 116622 3. 南京理工大學(xué) 自動化學(xué)院，南京 210094 4. 南京信息工程大學(xué) 電子與信息工程學(xué)院，南京 210044

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

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

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

在以往的最小路集和最小割集的算法中，端-端可靠性的計(jì)算都是基于單路徑傳輸?shù)摹Ｔ诙嗦窂絺鬏敺矫妫琇in[16]為了縮短傳輸時間，使用允許數(shù)據(jù)同時通過多個最小路徑發(fā)送的傳輸協(xié)議，將隨機(jī)流網(wǎng)絡(luò)流量從單路徑傳輸擴(kuò)展到2條及多條不交化路徑傳輸?shù)那闆r。為了解決使用具有不同延遲的不同路徑導(dǎo)致相同流的數(shù)據(jù)包之間出現(xiàn)重新排序的問題，Yabandeh等[17]提出基于UDP(User Datagram Protocol)的方法嘗試按順序?qū)?shù)據(jù)傳遞給接收者，同時在接收者的應(yīng)用程序上施加盡可能小的延遲和緩沖空間。仿真結(jié)果表明，多路徑傳輸?shù)男阅芘c最優(yōu)單路徑相當(dāng)。

在實(shí)際網(wǎng)絡(luò)環(huán)境中，端-端多路徑傳輸可以有效地聚合多條接入路徑的帶寬，從而使得網(wǎng)絡(luò)獲得更大的吞吐量，來滿足業(yè)務(wù)對帶寬的需求。屬于同一業(yè)務(wù)的數(shù)據(jù)從多條路徑傳輸，增加了從單條路徑竊聽數(shù)據(jù)進(jìn)而嘗試恢復(fù)初始數(shù)據(jù)內(nèi)容的難度，提供了更好的數(shù)據(jù)私密性。而且多條端-端路徑同時使用，可以根據(jù)網(wǎng)絡(luò)中的擁塞狀況動態(tài)地調(diào)整數(shù)據(jù)在不同路徑的發(fā)送速率，從而實(shí)現(xiàn)在網(wǎng)絡(luò)邊緣處的負(fù)載均衡[18]。因此，多路徑傳輸?shù)目煽啃詥栴}也不可忽視。

綜上，本文在衛(wèi)星網(wǎng)絡(luò)的多狀態(tài)特性分析的基礎(chǔ)上，針對業(yè)務(wù)QoS需求進(jìn)行了網(wǎng)絡(luò)端-端可靠性研究，即考慮鏈路的多狀態(tài)和傳輸不同業(yè)務(wù)類型對網(wǎng)絡(luò)可靠性產(chǎn)生的影響。本文中假設(shè)節(jié)點(diǎn)為正常工作狀態(tài)。又因?yàn)槎嗦窂絺鬏斣谛l(wèi)星網(wǎng)絡(luò)中廣泛使用，在單路徑可靠性研究基礎(chǔ)上進(jìn)一步對多路徑傳輸?shù)目煽啃赃M(jìn)行分析。結(jié)果表明不同類型的業(yè)務(wù)由于不同的QoS需求，可靠性并不相同，且網(wǎng)絡(luò)多路徑傳輸比單路徑傳輸可靠性高。

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

在經(jīng)典的最小路集算法(Minimum Path Set Algorithms，MPSA)分析網(wǎng)絡(luò)端-端可靠性的算法中，其基本思想是：先確定網(wǎng)絡(luò)拓?fù)涞脑炊撕湍康亩?并寫出網(wǎng)絡(luò)的鄰接矩陣和終點(diǎn)矩陣,再通過最小路集算法計(jì)算得出網(wǎng)絡(luò)的所有最小路集，最后將這些最小路集通過不交化計(jì)算并代入各鏈路可靠性得出網(wǎng)絡(luò)端-端可靠性的精確值。下面給出基于最小路集的端-端可靠性分析方法的相關(guān)定義[19]。

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

圖1 一個簡單的雙端網(wǎng)絡(luò)Fig.1 A simple two-terminal network

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

且當(dāng)j=k時，zjk=0。網(wǎng)絡(luò)的終點(diǎn)矩陣反映了網(wǎng)絡(luò)中每條弧的終點(diǎn)。

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

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

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

定義5 端-端可靠性定義為在QoS約束下，將數(shù)據(jù)流從源節(jié)點(diǎn)成功傳輸?shù)侥康墓?jié)點(diǎn)的概率。

2 端-端可靠性分析

2.1 業(yè)務(wù)分類

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

根據(jù)不同業(yè)務(wù)對指標(biāo)要求的差異，將業(yè)務(wù)分為3類，分別為時延敏感業(yè)務(wù)、帶寬敏感業(yè)務(wù)和可靠性敏感業(yè)務(wù)[20]。時延敏感業(yè)務(wù)對時延指標(biāo)較為敏感，要求具有較低的端到端時延。帶寬敏感業(yè)務(wù)的特點(diǎn)是需要大帶寬的鏈路進(jìn)行傳輸，但不要求時延很快。可靠性敏感業(yè)務(wù)對端-端傳輸可靠性要求高，要求較小的網(wǎng)絡(luò)丟包率。

2.2 相關(guān)指標(biāo)分析

1) 時延。時延是指一個報(bào)文或分組從網(wǎng)絡(luò)的一端傳送到另一端所需要的時間。包括報(bào)文或分組在節(jié)點(diǎn)上被處理、從節(jié)點(diǎn)發(fā)出以及在節(jié)點(diǎn)間傳播一定的距離而花費(fèi)的時間消耗，即時延=處理時延+排隊(duì)時延+發(fā)送時延+傳播時延。本文僅考慮發(fā)送時延與傳播時延。文中設(shè)Tmax為端-端最大時延約束，傳輸路徑的總時延T應(yīng)小于最大時延Tmax，否則此路徑認(rèn)為不可靠。

2) 帶寬。帶寬表示數(shù)據(jù)的傳輸能力，指單位時間內(nèi)能夠傳輸?shù)谋忍財(cái)?shù)。文中設(shè)Bmin為最小帶寬，傳輸路徑中的每條鏈路帶寬B應(yīng)大于最小帶寬Bmin，否則此路徑不可靠。

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

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

2.3 鏈路多狀態(tài)分析

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

2.4 端-端可靠性算法

2.4.1 算法思想

本文算法的基本思想是針對衛(wèi)星網(wǎng)絡(luò)鏈路的多狀態(tài)特性，根據(jù)傳輸業(yè)務(wù)的QoS約束找到對應(yīng)網(wǎng)絡(luò)狀態(tài)下的最小路徑集，對最小路集不交化處理再代入各鏈路可靠性計(jì)算網(wǎng)絡(luò)端-端可靠性。

2.4.2 時延相關(guān)表達(dá)式

本文端-端網(wǎng)絡(luò)時延由發(fā)送時延和傳播時延2部分組成，相關(guān)表達(dá)式為

Tsend=packet/B

(1)

Ttrans=Llink/c

(2)

T=Tsend+Ttrans

(3)

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

2.4.3 算法步驟

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

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

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

步驟7 根據(jù)BDD定義將函數(shù)f不交化處理，代入各鏈路可靠度求得網(wǎng)絡(luò)端-端可靠度。

3 算例分析

3.1 問題描述

將衛(wèi)星運(yùn)行周期Tp分成n個時間片[t0=0,t1],[t1,t2],[t2,t3],…,[tn-1,tn=Tp]。在每個時間片內(nèi)，假定拓?fù)浣Y(jié)構(gòu)不變，且鏈路的切換和網(wǎng)絡(luò)拓?fù)涞淖兓辉跁r間點(diǎn)t0,t1,t2,…,tn-1時刻發(fā)生，一個時間片內(nèi)的衛(wèi)星網(wǎng)絡(luò)拓?fù)淙鐖D4所示。

圖4 衛(wèi)星網(wǎng)絡(luò)拓?fù)鋱DFig.4 Topology of satellite network

每條鏈路遵循統(tǒng)計(jì)獨(dú)立的失效概率，各鏈路狀態(tài)及其對應(yīng)帶寬如表1所示，每條邊的狀態(tài)概率分布及傳輸時間Ttrans和丟包率如表2所示，各業(yè)務(wù)的QoS需求如表3所示。

表1 各鏈路狀態(tài)及其對應(yīng)的帶寬Table 1 Link states and their corresponding bandwidths

表2 鏈路狀態(tài)數(shù)據(jù)Table 2 Data if link states

續(xù)表2 鏈路狀態(tài)數(shù)據(jù)Table 2 Data if link states

表3 各業(yè)務(wù)QoS需求Table 3 QoS needs for each service

3.2 過程分析

根據(jù)表2鏈路狀態(tài)概率生成一組網(wǎng)絡(luò)狀態(tài)(3,2,3,3,2,3,3,3,2,3,3,3,3,1)，以傳輸2 Mbit的文件為例，分別對文件為時延敏感業(yè)務(wù)、帶寬敏感業(yè)務(wù)和可靠性敏感業(yè)務(wù)進(jìn)行分析。

步驟1 根據(jù)圖3得知此端-端衛(wèi)星通信網(wǎng)絡(luò)的源節(jié)點(diǎn)為v1、目的節(jié)點(diǎn)為v8,此網(wǎng)絡(luò)的鄰接矩陣為

A1=

終點(diǎn)矩陣為

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

步驟4 將各邊的可靠度代入，即可求出網(wǎng)絡(luò)端-端可靠性。此時，時延敏感業(yè)務(wù)端-端可靠性值為89.37%，帶寬敏感業(yè)務(wù)為81.45%，可靠性敏感業(yè)務(wù)為76.95%。

3.3 結(jié)果分析

設(shè)置多組文件大小，重復(fù)3.2節(jié)運(yùn)算步驟，本文算法結(jié)果如圖5所示。

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

圖5 3種業(yè)務(wù)可靠性對比Fig.5 Comparison of reliabilities for three services

4 多路徑端-端可靠性

多路徑傳輸是指采用多條不相交的路徑來投遞分組以增加連接的容量和可靠性的機(jī)制。在3.2節(jié)最小路徑集求解網(wǎng)絡(luò)端-端可靠性的過程中，網(wǎng)絡(luò)可靠性為所有可靠路徑的概率和，但此時的路徑是獨(dú)立傳輸各種業(yè)務(wù)。本文在上述研究基礎(chǔ)上，進(jìn)一步對多路徑傳輸可靠性進(jìn)行了研究，與單路徑的對比顯示，多路徑傳輸?shù)目煽啃缘玫搅颂岣摺?/p>

4.1 算法思想

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

(4)

式中：i為滿足條件的路徑集L中的路徑；m為路徑集L中的路徑個數(shù)。由于每條路徑帶寬不同，傳輸時需要對每條路徑應(yīng)該承擔(dān)的帶寬大小進(jìn)行分配。每條路徑應(yīng)該承擔(dān)的帶寬大小為

(5)

多路徑傳輸時每條路徑的發(fā)送時延為路徑需要傳輸?shù)臄?shù)據(jù)帶寬在當(dāng)前可用帶寬下的發(fā)送時延：

Tsend=B′i/Bii∈L

(6)

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

T=Max{Ti}i∈L

(7)

4.2 可靠性分析

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

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

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

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

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

5 結(jié) 論

1) 本文針對傳統(tǒng)網(wǎng)絡(luò)端-端可靠性分析中，計(jì)算網(wǎng)絡(luò)端-端可靠性時沒有體現(xiàn)傳輸不同業(yè)務(wù)的可靠性差異的問題，在衛(wèi)星網(wǎng)絡(luò)的多狀態(tài)特性分析的基礎(chǔ)上，通過案例模型分析了傳輸3種類型業(yè)務(wù)的可靠性。結(jié)果證明，該算法能很好地分析傳輸同樣大小的文件時，由于業(yè)務(wù)類型差異導(dǎo)致的QoS指標(biāo)差異從而帶來的網(wǎng)絡(luò)端-端可靠性的區(qū)別，比傳統(tǒng)算法更貼近實(shí)際。

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