別玉霞，潘成勝，劉海燕，王延春

（1. 南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094；2. 大連大學(xué) 信息工程學(xué)院，遼寧 大連 116622；3. 遼寧省通信網(wǎng)絡(luò)與信息處理重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116622）

1 引言

衛(wèi)星通信網(wǎng)絡(luò)正在與地面互聯(lián)網(wǎng)融合，利用衛(wèi)星通信系統(tǒng)的大容量傳輸和廣播特性提供互聯(lián)網(wǎng)業(yè)務(wù)，充分利用衛(wèi)星網(wǎng)絡(luò)的帶寬分流地面互聯(lián)網(wǎng)流量，以緩解地面網(wǎng)絡(luò)擁塞和帶寬資源不足的問(wèn)題[1]。同時(shí)，衛(wèi)星通信網(wǎng)絡(luò)可與作戰(zhàn)指控系統(tǒng)、應(yīng)急通信系統(tǒng)等結(jié)合，形成融合陸、海、空、天的一體化網(wǎng)絡(luò)。空間數(shù)據(jù)系統(tǒng)咨詢(xún)委員會(huì)(CCSDS, consultative committee for space data systems)提出的高級(jí)在軌系統(tǒng)(AOS, advanced orbiting systems)[2]適用于大型航天器，傳輸?shù)拇a速率范圍寬，業(yè)務(wù)種類(lèi)多，具有網(wǎng)絡(luò)接入功能，可與地面網(wǎng)互聯(lián)實(shí)現(xiàn)空間多媒體通信，已經(jīng)成為空間數(shù)據(jù)系統(tǒng)設(shè)計(jì)的重要標(biāo)準(zhǔn)。AOS能夠統(tǒng)一組織星上數(shù)據(jù)流，將文本、音頻、視頻、靜態(tài)圖像等多種類(lèi)型的數(shù)據(jù)在一條物理信道上傳輸。為有效傳輸來(lái)自多個(gè)用戶(hù)[3,4]的重要性和實(shí)時(shí)性要求各不相同的大容量、高速率數(shù)據(jù)，AOS中各虛擬信道(VC, virtual channel)[5]以時(shí)分復(fù)用的方式高效地共享地—空、空—地或空—空信道。

研究表明，地面互聯(lián)網(wǎng)的業(yè)務(wù)流量普遍呈現(xiàn)出自相似性[6]，并已得到廣泛公認(rèn)。國(guó)內(nèi)外已有關(guān)于衛(wèi)星網(wǎng)絡(luò)業(yè)務(wù)自相似性的研究。文獻(xiàn)[1]基于地面互聯(lián)網(wǎng)自相似性的研究成果，得到了如下結(jié)論：地面網(wǎng)絡(luò)的自相似業(yè)務(wù)經(jīng)過(guò)信關(guān)站進(jìn)入衛(wèi)星鏈路后的業(yè)務(wù)流量仍具有自相似性，自相似業(yè)務(wù)在衛(wèi)星網(wǎng)絡(luò)中匯聚和傳播后的業(yè)務(wù)流量仍然是自相似的，即業(yè)務(wù)的自相似性在衛(wèi)星網(wǎng)絡(luò)中普遍存在并能夠傳播。文獻(xiàn)[7]通過(guò)建立包含低軌衛(wèi)星網(wǎng)絡(luò)、地面網(wǎng)絡(luò)和信關(guān)站的網(wǎng)絡(luò)模型，仿真驗(yàn)證了低軌衛(wèi)星網(wǎng)絡(luò)中流量的自相似性。已有文獻(xiàn)在研究寬帶衛(wèi)星通信網(wǎng)絡(luò)時(shí)也采用了自相似業(yè)務(wù)模型[8～10]，并研究了衛(wèi)星通信網(wǎng)絡(luò)中自相似業(yè)務(wù)流量的預(yù)測(cè)問(wèn)題[11～13]。文獻(xiàn)[14]表明，網(wǎng)絡(luò)流量的自相似性不僅存在于互聯(lián)網(wǎng)絡(luò)中，同時(shí)也存在于衛(wèi)星網(wǎng)絡(luò)中[15]。網(wǎng)絡(luò)內(nèi)部數(shù)據(jù)流量的特性取決于傳送的業(yè)務(wù)類(lèi)型，自相似性揭示了高速網(wǎng)絡(luò)業(yè)務(wù)流量的一個(gè)普遍特性，自相似性與業(yè)務(wù)發(fā)生的時(shí)間地點(diǎn)或信源編碼方式無(wú)關(guān)，并且無(wú)論網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、用戶(hù)數(shù)量、傳輸介質(zhì)、協(xié)議類(lèi)型等如何變化，這種自相似性始終存在[16]。

網(wǎng)絡(luò)業(yè)務(wù)自相似性的一個(gè)突出表現(xiàn)為長(zhǎng)時(shí)間的數(shù)據(jù)突發(fā)，在此情況下，星上路由節(jié)點(diǎn)的分組處理系統(tǒng)隊(duì)列性能會(huì)受到較大影響，依靠增加緩存容量，對(duì)系統(tǒng)性能的改善并不明顯，反而會(huì)增加延時(shí)；同時(shí)，不同用戶(hù)的數(shù)據(jù)業(yè)務(wù)具有不同的重要性和傳輸實(shí)時(shí)性要求。為保證在突發(fā)情況下使重要數(shù)據(jù)得到及時(shí)傳輸，且能有效地利用緩存資源，需要基于A(yíng)OS數(shù)據(jù)流的自相似性對(duì)網(wǎng)絡(luò)性能的影響以及不同數(shù)據(jù)業(yè)務(wù)的傳輸需求，設(shè)計(jì)一種合理的隊(duì)列管理與虛擬信道調(diào)度算法。

為有效地進(jìn)行擁塞控制，中繼衛(wèi)星節(jié)點(diǎn)上的隊(duì)列管理算法按照一定的規(guī)則對(duì)緩存資源進(jìn)行分配，通過(guò)一定的丟棄分組概率來(lái)提前通知數(shù)據(jù)源端調(diào)整發(fā)送速度。典型的隊(duì)列管理算法有RED[17]以及改進(jìn)算法 ARED[18]、SRED[19]、BLUE[20]、文獻(xiàn)[21～24]所提出的算法等，這些隊(duì)列管理算法是基于流量的短相關(guān)模型的，沒(méi)有考慮流量的自相似性，不能有效解決突發(fā)業(yè)務(wù)的隊(duì)列管理問(wèn)題。文獻(xiàn)[25]把流量的自相似參數(shù)引入到 RED算法的丟棄概率中，提高了隊(duì)列長(zhǎng)度的穩(wěn)定性，減少了丟棄分組率、排隊(duì)時(shí)延和排隊(duì)抖動(dòng)。文獻(xiàn)[26]提出了基于時(shí)間槽的自相似流量隨機(jī)早檢測(cè)，在每個(gè)時(shí)間槽內(nèi)計(jì)算一次丟棄分組概率，大大降低了系統(tǒng)負(fù)擔(dān)。文獻(xiàn)[27]利用自相似業(yè)務(wù)流的可預(yù)測(cè)性，采用經(jīng)典控制理論中的預(yù)測(cè)PI控制器來(lái)進(jìn)行隊(duì)列管理，保持隊(duì)列穩(wěn)定在期望的長(zhǎng)度。上述算法能夠較好地實(shí)現(xiàn)自相似流量下的隊(duì)列管理，但對(duì)所有分組公平丟棄，不能滿(mǎn)足AOS中多種類(lèi)型業(yè)務(wù)的不同重要性。因此，需要基于 AOS的數(shù)據(jù)流量特性和業(yè)務(wù)重要性設(shè)計(jì)隊(duì)列管理算法。

虛擬信道調(diào)度算法是按照一定的服務(wù)規(guī)則對(duì)各虛擬信道中的幀進(jìn)行傳輸。虛擬信道調(diào)度方式主要有全同步方式、全異步方式和同步/異步混合方式[28]。在全同步方式中，各虛擬信道以固定的時(shí)隙占用物理信道，信道利用率低，且不利于處理突發(fā)性強(qiáng)的異步數(shù)據(jù)。在全異步方式中，根據(jù)優(yōu)先級(jí)決定各虛擬信道的傳送，可以靈活地處理異步數(shù)據(jù)，但同步數(shù)據(jù)會(huì)產(chǎn)生排隊(duì)延時(shí)，且延時(shí)量會(huì)隨其數(shù)據(jù)量的變化而變化，從而出現(xiàn)延時(shí)抖動(dòng)。單一的全同步方式和全異步方式不能滿(mǎn)足 AOS不同類(lèi)型業(yè)務(wù)的傳輸要求。同步/異步混合方式把信道分成同步虛擬信道和異步虛擬信道2部分，分配某些時(shí)隙傳送同步數(shù)據(jù)，其余時(shí)隙傳送異步數(shù)據(jù)，這種方式適合于業(yè)務(wù)類(lèi)型較多的系統(tǒng)，但不能保證某些重要性極強(qiáng)的數(shù)據(jù)的及時(shí)傳輸。因此，可以基于同步/異步混合方式，兼顧重要性極強(qiáng)的數(shù)據(jù)，設(shè)計(jì)3級(jí)復(fù)用方式。

在傳統(tǒng)的研究中，隊(duì)列管理和虛擬信道調(diào)度相互獨(dú)立，缺乏相關(guān)性，不能有效地利用緩存和處理資源[29]。本文針對(duì) AOS數(shù)據(jù)流及其業(yè)務(wù)特點(diǎn)，有效結(jié)合隊(duì)列管理和虛擬信道調(diào)度，提出了Hurst-優(yōu)先級(jí)自適應(yīng) RED與動(dòng)態(tài)調(diào)度 (HPRED-DS, hurst and priority adaptive RED combined with dynamic scheduling) 算法。基于HPRED-DS算法，在粗粒度根據(jù)流量的自相似程度、在細(xì)粒度根據(jù)優(yōu)先級(jí)自適應(yīng)調(diào)整丟棄分組概率，并根據(jù)不同業(yè)務(wù)的傳輸要求進(jìn)行VIP/同步/異步混合的虛擬信道動(dòng)態(tài)調(diào)度。實(shí)驗(yàn)結(jié)果表明，該算法可滿(mǎn)足AOS不同數(shù)據(jù)流量特性和不同業(yè)務(wù)的傳輸需求，保證信道的合理高效利用。

2 AOS隊(duì)列管理與虛擬信道調(diào)度系統(tǒng)模型

作為衛(wèi)星網(wǎng)絡(luò)的一個(gè)中繼節(jié)點(diǎn)，航天器的數(shù)據(jù)包括自身數(shù)據(jù)和來(lái)自網(wǎng)絡(luò)中其他節(jié)點(diǎn)的數(shù)據(jù)，每個(gè)信源都可包含工程數(shù)據(jù)、音頻數(shù)據(jù)、視頻數(shù)據(jù)、有效載荷數(shù)據(jù)和延時(shí)回放數(shù)據(jù)。音頻和視頻數(shù)據(jù)傳輸實(shí)時(shí)性和等時(shí)性要求高，稱(chēng)為同步數(shù)據(jù)，工程數(shù)據(jù)、有效載荷和延時(shí)回放數(shù)據(jù)具有較強(qiáng)的突發(fā)性但等時(shí)性要求不高，稱(chēng)為異步數(shù)據(jù)。AOS將共用同一條物理信道的數(shù)據(jù)以時(shí)分復(fù)用的方式在不同的虛擬信道中傳輸。由于每種數(shù)據(jù)業(yè)務(wù)的優(yōu)先級(jí)不同，本文為每種數(shù)據(jù)業(yè)務(wù)分別分配一條虛擬信道，如圖 1所示。異步數(shù)據(jù)對(duì)傳輸?shù)葧r(shí)性要求不高，采用異步傳輸模式，在異步虛擬信道中動(dòng)態(tài)傳輸。同步數(shù)據(jù)具有很強(qiáng)的等時(shí)性與實(shí)時(shí)性要求，采用同步傳輸模式，在專(zhuān)用的同步虛擬信道中傳輸，同步虛擬信道提供的固定時(shí)隙保證了固定的延時(shí)，可滿(mǎn)足同步數(shù)據(jù)的等時(shí)性要求。此外，將數(shù)據(jù)源中某些重要性和實(shí)時(shí)性極強(qiáng)的同步和異步數(shù)據(jù)分離出來(lái)，稱(chēng)為VIP數(shù)據(jù)，VIP數(shù)據(jù)可以包括航天器故障數(shù)據(jù)、重要的戰(zhàn)場(chǎng)數(shù)據(jù)、應(yīng)急數(shù)據(jù)（地震監(jiān)測(cè)數(shù)據(jù)、搶險(xiǎn)救災(zāi)數(shù)據(jù)、突發(fā)公共安全數(shù)據(jù)等），這類(lèi)數(shù)據(jù)在總數(shù)據(jù)源中的比重隨網(wǎng)絡(luò)應(yīng)用環(huán)境的不同而改變，但總體來(lái)說(shuō)，比重相對(duì)較低。設(shè)置一條VIP虛擬信道專(zhuān)用于傳送VIP數(shù)據(jù)，以保證此類(lèi)業(yè)務(wù)的及時(shí)傳輸。

到達(dá)各虛擬信道的分組要先進(jìn)入其相應(yīng)的輸入緩存隊(duì)列，輸入緩存采用最小分配共享方案，即根據(jù)各虛擬信道的平均業(yè)務(wù)量為每條虛擬信道分別預(yù)留一定的緩存，以保證其緩存的最小值。隊(duì)列管理模塊按照設(shè)計(jì)的隊(duì)列管理算法確定每個(gè)分組進(jìn)入輸入緩存隊(duì)列的概率。處理單元將各虛擬信道的分組復(fù)用成幀，并暫存于相應(yīng)的處理器緩存中。虛擬信道調(diào)度模塊根據(jù)設(shè)計(jì)的調(diào)度算法在每個(gè)時(shí)隙選擇一條虛擬信道，從其處理器緩存中取幀并傳輸。

當(dāng)緩存大小和系統(tǒng)利用率固定時(shí)，排隊(duì)性能與流量的自相似程度有關(guān)，自相似程度可由Hurst參數(shù)H來(lái)刻畫(huà)[30]，H值越大，自相似性越強(qiáng)。流量的自相似性會(huì)導(dǎo)致緩存溢出率高、延時(shí)長(zhǎng)，自相似程度越高，突發(fā)性就越強(qiáng)，對(duì)隊(duì)列性能造成的影響也越大[31]。因此，隊(duì)列管理算法要根據(jù)流量的自相似程度自適應(yīng)調(diào)整，并要保證高優(yōu)先級(jí)數(shù)據(jù)具有低丟棄概率。為合理利用處理資源，虛擬信道調(diào)度算法要兼顧VIP虛擬信道、同步虛擬信道和異步虛擬信道的傳輸特性，并與隊(duì)列管理算法有效結(jié)合起來(lái)。

圖1 AOS隊(duì)列管理與虛擬信道調(diào)度模型

3 HPRED-DS算法

3.1 HPRED算法設(shè)計(jì)

隊(duì)列管理算法HPRED采用基于H值與優(yōu)先級(jí)的2級(jí)丟棄分組策略：每隔一定時(shí)間間隔T (粗粒度)，根據(jù)流量的平均速率m、方差系數(shù)a和H值自適應(yīng)調(diào)整下一時(shí)間間隔內(nèi)分組的粗粒度丟棄概率Pb1，Pb1對(duì)所有分組都是公平的。對(duì)到達(dá)的每個(gè)分組（細(xì)粒度），根據(jù)其優(yōu)先級(jí)計(jì)算當(dāng)前分組的細(xì)粒度丟棄概率Pb2。丟棄分組概率Pb由2級(jí)丟棄概率Pb1和Pb2決定。

1) 粗粒度丟棄概率

Norros提出用如下的分形布朗運(yùn)動(dòng)模型來(lái)擬合自相似業(yè)務(wù)流[32]

其中，At代表 t時(shí)間內(nèi)到達(dá)的業(yè)務(wù)流，m＞0為流量的平均輸入速率，a＞0為方差系數(shù)，Bt為具有0均值、方差和H∈(0.5,1)的標(biāo)準(zhǔn)分形布朗運(yùn)動(dòng)。當(dāng)H=0.5時(shí)，At為無(wú)自相似性的布朗業(yè)務(wù)流。

將At輸入一個(gè)服務(wù)速率為C(C＞m)的隊(duì)列，根據(jù)Reich’s公式[32]可得到隊(duì)列長(zhǎng)度

其中，At是時(shí)間參數(shù)為t的分形布朗業(yè)務(wù)流，t, s∈(-∞,+∞)。根據(jù)Norros的推導(dǎo)，得出隊(duì)列長(zhǎng)度超過(guò)x的概率為[32]

其中，

根據(jù)式(3)和式(4)，可以得到P(X＞x)與x的關(guān)系曲線(xiàn)如圖2所示。

可以看出，P(X＞x)與x的變化關(guān)系與H有關(guān)，隨著x的增加，H越大，曲線(xiàn)下降越緩慢，即對(duì)于自相似性強(qiáng)的業(yè)務(wù)流，增大緩存容量并不能有效地改善溢出。因此，應(yīng)根據(jù)P(X ＞ x)的變化規(guī)律來(lái)設(shè)計(jì)粗粒度丟棄概率。

圖2 P(X ＞x)與x的關(guān)系曲線(xiàn)

設(shè)共享緩存區(qū)的最大隊(duì)長(zhǎng)閾值為Qmax、最小隊(duì)長(zhǎng)閾值為 Qmin、平均隊(duì)列長(zhǎng)度為 Qavg。當(dāng) Qmin

其中，

Pb1’與x的關(guān)系曲線(xiàn)如圖3所示。可以看出，Pb1’與x的關(guān)系較好地體現(xiàn)了P(X ＞ x)與x的變化規(guī)律，H=0.5時(shí)，Pb1’與x為線(xiàn)性關(guān)系。

圖3 Pb1’與x的關(guān)系曲線(xiàn)

基于以上分析，粗粒度丟棄概率為

通過(guò)對(duì)前j個(gè)時(shí)間間隔內(nèi)流量的測(cè)量，可計(jì)算m、a和H值。計(jì)算m的時(shí)間復(fù)雜度為O(j)，計(jì)算a的時(shí)間復(fù)雜度為O(j)[26]，R/S法估計(jì)H值的時(shí)間復(fù)雜度為O(j2)[33]。每隔一定時(shí)間根據(jù)流量參數(shù)計(jì)算粗粒度丟棄概率 Pb1，既可根據(jù)流量的自相似程度自適應(yīng)調(diào)整丟棄分組概率，又能避免在每個(gè)分組到達(dá)時(shí)分別計(jì)算m、a和H值，降低了系統(tǒng)負(fù)擔(dān)。

2) 細(xì)粒度丟棄概率

由于每種數(shù)據(jù)業(yè)務(wù)的優(yōu)先級(jí)不同，還應(yīng)根據(jù)分組的優(yōu)先級(jí)自適應(yīng)調(diào)整丟棄分組概率。

為每條虛擬信道分配一個(gè)優(yōu)先級(jí)，同一條虛擬信道的分組具有相同的優(yōu)先級(jí)。設(shè)共享緩存區(qū)的平均隊(duì)列長(zhǎng)度為 Qavg、最大隊(duì)長(zhǎng)閾值為 Qmax、最小隊(duì)長(zhǎng)閾值為Qmin，第i條虛擬信道的優(yōu)先級(jí)為pr(i)、平均隊(duì)列長(zhǎng)度為 Qavg(i)、預(yù)留的緩存最小值為Qmin(i)，則進(jìn)入當(dāng)前虛擬信道分組的細(xì)粒度丟棄概率Pb2為

其中，

Pmax(i)表示第 i條虛擬信道的最大丟棄概率，Pmax(i)與優(yōu)先級(jí)有關(guān)，優(yōu)先級(jí)越高，Pmax(i)越小，如下式

3) 分組丟棄概率

通過(guò)當(dāng)前粗粒度T內(nèi)的丟棄分組概率Pb1和當(dāng)前分組的細(xì)粒度丟棄概率Pb2，可得到HPRED算法下的丟棄分組概率Pb，Pb為Pb1和Pb2的線(xiàn)性疊加

其中，1=+βα。

3.2 DS算法設(shè)計(jì)

為保證VIP數(shù)據(jù)的及時(shí)傳輸，兼顧同步數(shù)據(jù)的等時(shí)性和異步數(shù)據(jù)的突發(fā)性，虛擬信道調(diào)度采用VIP /同步/異步混合的動(dòng)態(tài)調(diào)度(DS)算法。將一個(gè)調(diào)度周期分為Nt個(gè)時(shí)隙，分別分配給VIP虛擬信道、同步虛擬信道和異步虛擬信道，且3個(gè)部分之間的邊界是可以移動(dòng)的。只要出現(xiàn)VIP數(shù)據(jù)，則中斷當(dāng)前傳送的數(shù)據(jù)，搶占后續(xù)時(shí)隙，直到將VIP數(shù)據(jù)傳送完畢。

設(shè)VIP虛擬信道、同步虛擬信道和異步虛擬信道的時(shí)隙數(shù)分別為 Nv、Ns和 Na，若無(wú)空閑時(shí)隙，則有

由于VIP數(shù)據(jù)要隨到隨傳，因此Nv是無(wú)法事先計(jì)算的，但在每個(gè)調(diào)度周期都要實(shí)時(shí)計(jì)算并調(diào)整

Ns與Na。設(shè)同步虛擬信道的個(gè)數(shù)為Nsyn，幀到達(dá)率為Fsyn；異步虛擬信道的個(gè)數(shù)為Nasyn，幀到達(dá)率為

Fasyn，則Ns與Na之比為

同步虛擬信道采用加權(quán)周期輪詢(xún)調(diào)度策略。若分配給同步虛擬信道 VC2、VC3的時(shí)隙數(shù)分別為n2、n3，則在同一調(diào)度周期的同步時(shí)隙內(nèi)，對(duì)VC2和VC3的調(diào)度順序?yàn)?/p>

異步虛擬信道采用動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略。在每個(gè)異步時(shí)隙，判斷是否有超過(guò)最大延時(shí)的異步虛擬信道，若有，將其傳送；否則，傳送動(dòng)態(tài)優(yōu)先級(jí)最高的異步虛擬信道。各異步虛擬信道的動(dòng)態(tài)優(yōu)先級(jí)與緊迫度、待傳的幀數(shù)和延時(shí)有關(guān)。

異步虛擬信道的緊迫度系數(shù)E由優(yōu)先級(jí)決定，設(shè)最低優(yōu)先級(jí)異步虛擬信道的緊迫度系數(shù)為Emin，則次低優(yōu)先級(jí)異步虛擬信道的緊迫度系數(shù)為Emin+1，依次類(lèi)推。

設(shè)第 i條虛擬信道處理器緩存中的幀數(shù)為F1(i)，幀長(zhǎng)為L(zhǎng)f，分組長(zhǎng)為L(zhǎng)p，則該虛擬信道中待傳的幀數(shù)F(i)為

在初始時(shí)隙，延時(shí)基數(shù)B為

在每個(gè)異步調(diào)度時(shí)隙結(jié)束，對(duì)當(dāng)前時(shí)隙未被傳送的異步虛擬信道，若F≥1，則B+1→B。

基于以上分析，異步虛擬信道的動(dòng)態(tài)優(yōu)先級(jí)Dp為

3.3 HPRED-DS算法流程

隊(duì)列管理和虛擬信道調(diào)度是相輔相成的，兩者相互配合才能獲得最優(yōu)的控制效果。HPREDDS算法通過(guò)各虛擬信道的優(yōu)先級(jí)和隊(duì)列長(zhǎng)度將HPRED算法和DS算法結(jié)合起來(lái)。HPRED算法負(fù)責(zé)系統(tǒng)緩存資源的分配，DS算法負(fù)責(zé)帶寬資源的分配，并可根據(jù)各虛擬信道的變化動(dòng)態(tài)調(diào)整，使它們相互影響。在對(duì)HPRED算法和DS算法設(shè)計(jì)的基礎(chǔ)上，HPRED-DS算法的步驟如下。

步驟 1 為同步虛擬信道和異步虛擬信道分配時(shí)隙；定義各虛擬信道的優(yōu)先級(jí)；為各虛擬信道分配最小緩存；定義共享緩存區(qū)的最大隊(duì)長(zhǎng)閾值和最小隊(duì)長(zhǎng)閾值；設(shè)置粗粒度T。

步驟2 判斷當(dāng)前時(shí)隙是否為T(mén)的整數(shù)倍，若是，轉(zhuǎn)入步驟3；否則，轉(zhuǎn)入步驟4。

步驟3 估計(jì)前j個(gè)粗粒度內(nèi)流量的均值m、標(biāo)準(zhǔn)差a及自相似參數(shù)H；計(jì)算共享緩存區(qū)的平均隊(duì)列長(zhǎng)度Qavg；計(jì)算下一粗粒度T內(nèi)分組的粗粒度丟棄概率Pb1；轉(zhuǎn)入步驟4。

步驟 4 判斷當(dāng)前時(shí)隙內(nèi)是否有分組到達(dá)，若有，轉(zhuǎn)入步驟5；否則，轉(zhuǎn)入步驟7。

步驟5 計(jì)算各虛擬信道的平均隊(duì)列長(zhǎng)度Qavg(i)；計(jì)算各分組的細(xì)粒度丟棄概率Pb2；轉(zhuǎn)入步驟6。

步驟6 由Pb1和Pb2計(jì)算各分組的丟棄概率Pb；各分組以1-Pb的概率進(jìn)入相應(yīng)虛擬信道的隊(duì)列；轉(zhuǎn)入步驟7。

步驟7 計(jì)算VIP虛擬信道待傳的幀數(shù)F，若F≥1，傳輸VIP虛擬信道，下一時(shí)隙，轉(zhuǎn)入步驟2；否則，轉(zhuǎn)入步驟8。

步驟 8 判斷當(dāng)前時(shí)隙是否同步時(shí)隙，若是，轉(zhuǎn)入步驟9；否則，轉(zhuǎn)入步驟12。

步驟 9 計(jì)算當(dāng)前時(shí)隙對(duì)應(yīng)的同步虛擬信道的F，若F≥1，轉(zhuǎn)入步驟10；否則，轉(zhuǎn)入步驟11。

步驟10 傳輸當(dāng)前時(shí)隙對(duì)應(yīng)的同步虛擬信道，下一時(shí)隙，轉(zhuǎn)入步驟2。

步驟 11 計(jì)算其他同步虛擬信道的 F，若F≥1，傳輸其他同步虛擬信道，下一時(shí)隙，轉(zhuǎn)入步驟2；否則，轉(zhuǎn)入步驟12。

步驟 12 計(jì)算異步虛擬信道的 F，若 F≥1，轉(zhuǎn)入步驟13；否則，轉(zhuǎn)入步驟14。

步驟 13 按照動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略選擇一條異步虛擬信道并傳輸，下一時(shí)隙，轉(zhuǎn)入步驟2。

步驟14 傳輸空幀，下一時(shí)隙，轉(zhuǎn)入步驟2。

HPRED-DS算法以各虛擬信道的優(yōu)先級(jí)和隊(duì)列長(zhǎng)度為紐帶，將HPRED算法和DS算法有機(jī)結(jié)合起來(lái)，可滿(mǎn)足 AOS數(shù)據(jù)業(yè)務(wù)在不同自相似程度下、不同業(yè)務(wù)類(lèi)型的傳輸要求，優(yōu)化系統(tǒng)的處理效率、隊(duì)列長(zhǎng)度和延時(shí)等性能。

4 仿真實(shí)驗(yàn)與分析

按圖1所示的系統(tǒng)模型對(duì)HPRED-DS算法進(jìn)行仿真實(shí)驗(yàn)，并與RED隊(duì)列管理-優(yōu)先級(jí)虛擬信道調(diào)度(以下簡(jiǎn)稱(chēng)RED-Priority)算法進(jìn)行比較。參數(shù)設(shè)置為：Qmax=200packet，Qmin= 100packet，每幀封裝的分組個(gè)數(shù) N=3。各虛擬信道的平均分組到達(dá)率(packet/s)、優(yōu)先級(jí)和緊迫度系數(shù)如表1所示。

表1 虛擬信道參數(shù)設(shè)置

到達(dá)每條虛擬信道的數(shù)據(jù)為若干同類(lèi)單數(shù)據(jù)源的疊加，每種數(shù)據(jù)源按ON/OFF模型產(chǎn)生數(shù)據(jù)。當(dāng)ON和OFF的持續(xù)時(shí)間長(zhǎng)度服從指數(shù)分布時(shí)，疊加業(yè)務(wù)流是短相關(guān)的，不具有自相似性， 0.5=H ；當(dāng)ON和OFF的持續(xù)時(shí)間長(zhǎng)度服從Pareto分布且形狀參數(shù) 1<α≤2時(shí)，疊加業(yè)務(wù)流具有自相似性，H∈(0.5,1)。在H=0.5和H=0.8 2種流量下，對(duì)算法的處理效率、隊(duì)列長(zhǎng)度和延時(shí)進(jìn)行仿真。

1) 處理效率

圖4為在RED-Priority算法與HPRED-DS算法下系統(tǒng)總的處理效率。

從圖4中可以看出，H=0.5時(shí)，在RED-Priority算法與 HPRED-DS算法下系統(tǒng)總的處理效率基本相同，且趨于1。H=0.8時(shí)，RED-Priority算法的處理效率為 0.7～0.9，HPRED-DS算法的處理效率為0.8～1。因此，在自相似流量下，HPRED-DS算法可提高處理效率，從而提高系統(tǒng)的吞吐率。

圖5為H=0.8時(shí)，RED-Priority算法與HPREDDS算法下各虛擬信道的處理效率。

圖4 系統(tǒng)總處理效率

圖5 各虛擬信道的處理效率(H=0.8)

從圖5中可以看出，H=0.8時(shí)，與RED-Priority算法相比，HPRED-DS算法在保證高優(yōu)先級(jí)虛擬信道具有較高處理效率的同時(shí)，適當(dāng)降低部分次高優(yōu)先級(jí)虛擬信道的處理效率，避免了最低優(yōu)先級(jí)虛擬信道處理效率的大幅度下降。

2) 隊(duì)列長(zhǎng)度

圖6為在RED-Priority算法與HPRED-DS算法下共享緩存區(qū)的隊(duì)列長(zhǎng)度。

圖6 共享緩存區(qū)的隊(duì)列長(zhǎng)度

從圖6中可以看出，H=0.5時(shí)，在RED-Priority算法與 HPRED-DS算法下共享緩存區(qū)的隊(duì)列長(zhǎng)度基本相同，隊(duì)列長(zhǎng)度穩(wěn)定。H=0.8時(shí)，RED-Priority算法下的隊(duì)列長(zhǎng)度平均值為 114packet，最大值為266packet，標(biāo)準(zhǔn)差為75packet；HPRED-DS算法下的隊(duì)列長(zhǎng)度平均值為 100packet，最大值為195packet，標(biāo)準(zhǔn)差為44packet，即HPRED-DS算法比 RED-Priority算法的隊(duì)列長(zhǎng)度平均值降低了14packet，最大值降低了 71packet，標(biāo)準(zhǔn)差減少了31packet。因此，在自相似流量下，HPRED-DS算法與 RED-Priority算法的隊(duì)列長(zhǎng)度相差不大，但HPRED-DS算法的隊(duì)列長(zhǎng)度穩(wěn)定。

圖7為H=0.8時(shí)，RED-Priority算法與HPREDDS算法下各虛擬信道的隊(duì)列長(zhǎng)度。

從圖7中可以看出，H=0.8時(shí)，VIP虛擬信道得到了及時(shí)傳輸，即隊(duì)列長(zhǎng)度為 0，同步虛擬信道具有較小的隊(duì)列長(zhǎng)度，可保證同步數(shù)據(jù)的實(shí)時(shí)性。與RED-Priority算法相比，HPRED-DS算法在保證高優(yōu)先級(jí)虛擬信道具有較低隊(duì)列長(zhǎng)度的同時(shí)，通過(guò)適當(dāng)增加部分次高優(yōu)先級(jí)虛擬信道的隊(duì)列長(zhǎng)度，避免了最低優(yōu)先級(jí)虛擬信道隊(duì)列長(zhǎng)度的大幅度波動(dòng)。

圖7 各虛擬信道的隊(duì)列長(zhǎng)度(H=0.8)

3) 延時(shí)

圖8為在RED-Priority算法與HPRED-DS算法下的排隊(duì)延時(shí)。

圖8 排隊(duì)延時(shí)

從圖 8中可以看出，H=0.5時(shí)，RED-Priority算法與HPRED-DS算法下排隊(duì)延時(shí)基本相同，延時(shí)抖動(dòng)較小。H=0.8時(shí)，RED-Priority算法下的排隊(duì)延時(shí)平均值為64ms，最大值為154ms，標(biāo)準(zhǔn)差為46ms；HPRED-DS算法下的排隊(duì)延時(shí)平均值為 28ms，最大值為96ms，標(biāo)準(zhǔn)差為25ms，即HPRED-DS算法比RED-Priority算法的排隊(duì)延時(shí)平均值降低了36ms，最大值降低了58ms，標(biāo)準(zhǔn)差減少了21ms。因此，在自相似流量下，HPRED-DS算法比RED-Priority算法的排隊(duì)延時(shí)和延時(shí)抖動(dòng)小。

以上仿真實(shí)驗(yàn)結(jié)果表明，本文提出的HPREDDS算法可保持較高的處理效率和吞吐率；采用基于H值的粗粒度丟棄，可在自相似流量下穩(wěn)定隊(duì)列長(zhǎng)度，降低排隊(duì)延時(shí)和延時(shí)抖動(dòng)；采用基于優(yōu)先級(jí)的細(xì)粒度丟棄，可降低高優(yōu)先級(jí)數(shù)據(jù)的丟棄概率，提高重要數(shù)據(jù)的處理效率；基于VIP /同步/異步混合的動(dòng)態(tài)調(diào)度算法，可使某些極重要的數(shù)據(jù)得到及時(shí)傳輸，使同步虛擬信道具有較小的延時(shí)，并在保持高優(yōu)先級(jí)虛擬信道性能的前提下，通過(guò)適當(dāng)降低部分次高優(yōu)先級(jí)虛擬信道的性能，來(lái)改善低優(yōu)先級(jí)虛擬信道的性能，避免了把性能惡化全部壓在最低優(yōu)先級(jí)的虛擬信道上，具有較好的公平性。

5 結(jié)束語(yǔ)

本文通過(guò)分析 AOS數(shù)據(jù)流量特性和不同業(yè)務(wù)的傳輸要求，設(shè)計(jì)了隊(duì)列管理和虛擬信道調(diào)度相結(jié)合的HPRED-DS算法。隊(duì)列管理算法采用粗粒度基于H值、細(xì)粒度基于優(yōu)先級(jí)的2級(jí)丟棄分組策略，既能根據(jù)流量的自相似程度和業(yè)務(wù)重要性自適應(yīng)調(diào)整丟棄分組概率，又能降低了系統(tǒng)負(fù)擔(dān)。虛擬信道調(diào)度算法采用VIP /同步/異步混合的動(dòng)態(tài)調(diào)度模式，可兼顧VIP數(shù)據(jù)的重要性、同步數(shù)據(jù)的等時(shí)性和異步數(shù)據(jù)的突發(fā)性。實(shí)驗(yàn)結(jié)果表明，HPRED-DS算法具有較好的處理效率、隊(duì)列長(zhǎng)度和延時(shí)性能，可滿(mǎn)足 AOS數(shù)據(jù)在不同自相似程度下、不同業(yè)務(wù)的傳輸要求?；谂抨?duì)論模型的分析和優(yōu)化調(diào)度問(wèn)題，將在后續(xù)研究中繼續(xù)深入。

[1] 那振宇. 衛(wèi)星互聯(lián)網(wǎng)服務(wù)質(zhì)量保障方法研究[D]. 哈爾濱： 哈爾濱工業(yè)大學(xué), 2010.NA Z Y. Research on QoS Guarantee Methods in Satellite Internet[D].Harbin： Harbin Institute of Technology, 2010.

[2] CCSDS. Advanced Orbiting Systems, Networks and Data Links：Architectural Specification[S]. CCSDS 701.0-B-3, 2001.

[3] CCSDS. Space Link Extension—Forward Space Packet Service Specification[S]. CCSDS 912.3-B-2, 2010.

[4] CCSDS. Space Packet Protocol[S]. CCSDS 133.0-B-1, 2003.

[5] CCSDS. AOS Space Data Link Protocol[S]. CCSDS 732.0-B-2, 2006.

[6] LELAND W E, TAQQU M S, WILLINGER W, et al. On the selfsimilar nature of Ethernet traffic (extended version)[J]. IEEE/ACM Transactions on Networking, 1994, 2(1)： 1-15.

[7] NA Z Y, GAO Z H, GUO Q. Performance analysis of self-similar traffic in LEO satellite network[A]. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics[C]. Hong Kong, China, 2007.19-22.

[8] RYU B. Modeling and simulation of broadband satellite networks—part II： traffic modeling[J]. IEEE Communications Magazine, 1999,37(7)：48-56.

[9] CHITI F, FANTACCI R, TARCHI D, et al. QoS provisioning in GEO satellite with onboard processing using predictor algorithms[J]. IEEE Wireless Communications, 2005,12(5)：21-27.

[10] 李斗, 姬冰輝, 王峰等. 基于混沌預(yù)測(cè)的寬帶 DVB-RCS衛(wèi)星接入信道動(dòng)態(tài)分配方案研究[J]. 電子與信息學(xué)報(bào), 2008,30(3)：607-611.LI D, JI B H, WANG F, et al. The dynamic allocation of broadband DVB-RCS satellite access channel based on chaotic prediction[J].Journal of Electronics & Information Technology, 2008,30(3)： 607-611.

[11] JIANG Z F, LI Y H, LEUNG V C M. A predictive demand assignment multiple access protocol for Internet access over broadband satellite networks[J]. International Journal of Satellite Communication Network, Wiley InterScience, 2003, 21： 451-467.

[12] MITCHELL P D, GRACE D, TOZER T C. Burst targeted demand assignment multiple-access for broadband Internet service delivery over geostationary satellite[J]. IEEE Journal on Selected Areas in Communications, 2004, 22(3)： 546-558.

[13] 陳劍, 聞?dòng)⒂? 趙大哲, 等. VBR視頻流量的小波包分解及其長(zhǎng)時(shí)預(yù)測(cè)[J]. 通信學(xué)報(bào), 2008,29(6)：34-42.CHEN J, WEN Y Y, ZHAO D Z, et al. Long-term prediction for VBR video traffic based on wavelet packet decomposition[J]. Journal on Communications, 2008,29(6)：34-42.

[14] 張賓, 楊家海, 吳建平. Internet流量模型分析與評(píng)述[J]. 軟件學(xué)報(bào),2011, 22(1)：115-131.ZHANG B, YANG J H, WU J P. Survey and analysis on the internet traffic model[J]. Journal of Software, 2011, 22(1)：115-131.

[15] ILOW J, LEUNG H. Self-Similar texture modeling using FARIMA processes with applications to satellite images[J]. IEEE Transactions on Image Processing, 2001, 10(5)：792-797.

[16] CROVELLA M E, BESTAVROS A. Self-similarity in World Wide Web traffic evidence and possible causes[J]. IEEE/ACM Transactions on Networking. 1997,5(6)：835-846.

[17] FLOYD S, JAEOBSON V. Random early detection gateways for congestion avoidance[J]. IEEE/ACM Transactions on Networking,1993, 1(4)： 397-413.

[18] FLOYD S, GUMMADI R, SHENKER S. Adaptive RED： an algorithm for Increasing the Robustness of RED’s Active Queue Management[R].Technical Report, 2001.

[19] VERMA R, IYER A, KARANDIKAR A. On tuning of RED parameters[EB/OL]. http：//www.ee.iitb.ernet.in/uma/～ncc2002/proc/NCC-2002/pdf/n093.pdf.

[20] CHRISTIANSEN M, JEFFAY K, OTT D. Tuning RED for Web traffic[J]. IEEE/ACM Transactions on Networking, 2001, 9(3)： 249-269.

[21] JAVAM H, ANALOUI M. SARED： stabilized ARED[A]. Proceedings of International Conference on Communication Technology[C]. Guilin,China, 2006.1-4.

[22] WANG C，SOHRABY K, HOU T, et al. LRED：a robust and responsive AQM algorithm using packet loss ratio measurement[J]. IEEE Transactions on Parallel And Distributed Systems, 2007, 18(l)：29-43.

[23] SUN J, ZUKERMAN M, PALANISWAMI M. Stabilizing RED using a fuzzy controller[A]. Proceedings of IEEE International Conference on Communications[C]. Glasgow, Scotland, 2007. 266-271.

[24] USHADEVI M B, MAHESH H M, RAVIKUMAR H M. Efficient fair queuing using adaptive RED algorithm for high speed networks[A].Proceedings of International Conference on Intelligent and Advanced Systems[C]. Kuala Lumpur, Malaysia, 2007. 389-392.

[25] 黃麗亞, 王鎖萍. 基于自相似業(yè)務(wù)流的Hurst加權(quán)隨機(jī)早檢測(cè)算法[J]. 通信學(xué)報(bào), 2007, 28(4)： 95-100.HUANG L Y, WANG S P. Hurst weighted random early detection algorithm based on self-similar traffic input[J]. Journal on Communications, 2007, 28(4)： 95-100.

[26] 王暉, 季振洲, 孫彥東等. 基于時(shí)間槽的自相似流量隨機(jī)早檢測(cè)算法—SFRED[J]. 通信學(xué)報(bào), 2010, 31(10)： 115-120.WANG H, JI Z Z, SUN Y D, et al. Time slot-based RED algorithm on self-similar flows：SFRED[J]. Journal on Communications, 2010, 31(10)：115-120.

[27] 吳清亮, 陶軍, 姚婕. 一種基于預(yù)測(cè)PI控制器的自相似網(wǎng)絡(luò)主動(dòng)隊(duì)列管理算法[J]. 電子學(xué)報(bào), 2006,34(5)：938-943.WU Q L, TAO J, YAO J. An active queue management algorithm based on predictable PI controller in self-similar network[J]. Acta Electronica Sinica, 2006,34(5)：938-943.

[28] CCSDS. Advanced Obriting Systems，Netwoks and Data Links：Summery of Concept，Rational and Performance[S]. CCSDS 700.0-G-3, November 1992.

[29] CHO J W, CHO D H. Dynamic buffer management scheme based on rate estimation in packet-switched networks[J]. Computer Networks,2002, 39(6)： 2304-2309.

[30] 石江濤, 王永綱, 戴雪龍等. 自相似網(wǎng)絡(luò)業(yè)務(wù)流量的研究與實(shí)現(xiàn)[J].通信學(xué)報(bào), 2005, 26(6)： 112-117.SHI J T, WANG Y G, DAI X L, et al. On study and implementation of self-similar network traffic[J]. Journal on Communications, 2005,26(6)： 112-117.

[31] PARK K, WILLINGER W. Self Similar Network Traffic and Performance Evaluation[M]. New York： Wiley, 2000.

[32] NORROS I. On the use of fractional brownian motion in the theory of connectionless networks[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(6)：953-962.

[33] HOLLOT C V, MISRA V, TOWSLEY D. On designing improved controllers for AQM routers supporting TCP flows[A]. IEEE INFOCOM 2001[C]. Anchorage, Alaska, USA, 2001. 1726-1734.