一種基于網(wǎng)絡(luò)編碼的新型衛(wèi)星網(wǎng)絡(luò)可靠組播機制＊

桂永茂，趙寶康，唐 竹，彭 偉，夏 艷，徐 芬

（1.國防科學(xué)技術(shù)大學(xué)計算機學(xué)院，湖南 長沙410073；2.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙410082；3.中國空氣動力研究與發(fā)展中心超高速空氣動力研究所，四川 綿陽621000）

1 引言

衛(wèi)星網(wǎng)絡(luò)具有天然的廣播特性，具有覆蓋范圍廣和拓撲簡單等優(yōu)點，使得其非常適合組播業(yè)務(wù)傳輸。然而，衛(wèi)星傳輸鏈路帶寬受限，長時延和高誤碼的特點，使得傳統(tǒng)組播傳輸協(xié)議面臨可靠性等難題。數(shù)據(jù)的可靠傳輸涉及到數(shù)據(jù)的重傳，因此，針對衛(wèi)星網(wǎng)絡(luò)設(shè)計一種高效的重傳機制，盡可能地減少反饋重傳的次數(shù)并提高帶寬利用率，具有十分重要的意義。

傳統(tǒng)的衛(wèi)星網(wǎng)絡(luò)可靠組播協(xié)議［1～4］大多使用ARQ（Automatic Repeating re－Quest）技術(shù)，即自動請求重傳來保證組播數(shù)據(jù)的絕對可靠性，然而在衛(wèi)星網(wǎng)絡(luò)中，當(dāng)組播接收端數(shù)目過大時，單獨使用ARQ 技術(shù)容易發(fā)生“確認風(fēng)暴”問題。還有部分可靠組播協(xié)議［5～7］使用了發(fā)送窗口機制來最大限度地減少重傳開銷，雖然減少了重傳，但是并沒有減少確認次數(shù)，因此仍然存在“確認風(fēng)暴”的問題，而且在發(fā)送端等待發(fā)送窗口，一定程度上降低了差錯恢復(fù)的實時性。

另外一些衛(wèi)星可靠組播協(xié)議使用了混合ARQ機制［8］，雖然混合ARQ 機制較大程度上減少了反饋重傳的次數(shù)和提高了差錯恢復(fù)的實時性，但是并沒有實現(xiàn)結(jié)構(gòu)化的傳輸。

本文提出了一種基于網(wǎng)絡(luò)編碼的衛(wèi)星網(wǎng)絡(luò)可靠組播機制NCM（Network Coding Mechanism）。該機制采用結(jié)構(gòu)化的分塊傳輸方法，通過在發(fā)送端主動發(fā)送原始報文的冗余編碼包，可實現(xiàn)接收端多個丟失報文的本地恢復(fù)，從而大大減少了反饋重傳次數(shù)，提高了差錯恢復(fù)的實時性；同時結(jié)合ARQ機制，當(dāng)出現(xiàn)原始報文和編碼報文同時丟失時，通過一次重傳編碼包，即可恢復(fù)多個丟失報文，不但減少了重傳次數(shù)，還保證了組播的可靠性。

2 網(wǎng)絡(luò)編碼組播機制

2.1 衛(wèi)星網(wǎng)絡(luò)模型

圖1描述了衛(wèi)星網(wǎng)絡(luò)可靠組播協(xié)議的層次結(jié)構(gòu)。衛(wèi)星網(wǎng)絡(luò)包含GEO（GEosynchronous Orbit）衛(wèi)星和若干地面站，地面站包括發(fā)送端地面站和接收端地面站。衛(wèi)星網(wǎng)絡(luò)通過網(wǎng)關(guān)和地面網(wǎng)絡(luò)及用戶終端相連。

Figure 1 Model of satellite networks圖1 衛(wèi)星網(wǎng)絡(luò)模型

2.2 問題描述

衛(wèi)星網(wǎng)絡(luò)傳輸鏈路容易受到天氣等因素的干擾，具有高誤碼和長時延的固有特性，這兩個特性為可靠多播提出了難題。本文提出的NCM 機制針對“確認風(fēng)暴”、實時差錯恢復(fù)及結(jié)構(gòu)化傳輸這三個問題進行了重點優(yōu)化。

2.3 NCM 機制描述

NCM 機制采用隨機線性網(wǎng)絡(luò)編碼［9］，主要由兩部分組成：一個是結(jié)構(gòu)化傳輸，另一個是本地恢復(fù)結(jié)合ARQ 重傳。

（1）結(jié)構(gòu)化傳輸。

混合ARQ 機制通過采用前向糾錯編碼FEC（Forward Error Correction）機制，雖然能較大程度上減少重傳，但是并沒有實現(xiàn)明顯的結(jié)構(gòu)化傳輸。NCM 機制采用分塊的結(jié)構(gòu)化傳輸方法，塊結(jié)構(gòu)如圖2所示，每塊包含k個原始報文和一個編碼包，其中定義第i塊為Bi，第i塊中的第m個報文表示為第i塊的原始報文的編碼包為Ui。組播源將待發(fā)送的數(shù)據(jù)分成n塊，對于每塊Bi，平均分成k個原始數(shù)據(jù)包，然后將這k個數(shù)據(jù)包經(jīng)過k次編碼組合，得到k個編碼報文，最后把這k個編碼報文壓縮成一個編碼包Ui，根據(jù)隨機線性網(wǎng)絡(luò)編碼原理，對于第i塊，設(shè)隨機產(chǎn)生的k個編碼系數(shù)為［ai，1，ai，2，…，ai，k］，則有接收端在接收到編碼包后，先解壓縮還原出編碼報文，然后通過高斯消元法［9，10］，即可解碼出原始報文。

（2）本地恢復(fù)結(jié)合ARQ 重傳。

NCM 主要分為三個過程：檢測、恢復(fù)、反饋重傳。三個過程的轉(zhuǎn)換如圖3所示。

Figure 2 Block structure圖2 塊結(jié)構(gòu)

Figure 3 Process switching圖3 過程轉(zhuǎn)換

傳統(tǒng)ARQ 主要缺少過程①，所以NCM 相比ARQ，提升性能的關(guān)鍵在于①。

（1）檢測→恢復(fù)：對應(yīng)于圖3中的狀態(tài)①，為本地恢復(fù)過程。當(dāng)接收端接收到數(shù)據(jù)塊Bi之后，進行檢測。如果檢測到一個或者多個原始報文（0＜j＜k＋1）丟失，而編碼包Ui未丟失，則通過在本地解碼Ui即可實現(xiàn)丟失報文本地恢復(fù)，從而大大增強了數(shù)據(jù)恢復(fù)的實時性，減少了反饋重傳。

（2）檢測→反饋重傳→恢復(fù)：對應(yīng)于圖3中的狀態(tài)②，即傳統(tǒng)ARQ 重傳過程。當(dāng)接收端接收到數(shù)據(jù)塊Bi之后，進行檢測。如果檢測到原始報文丟失，編碼包Ui也丟失，則接收端通過反饋鏈路向組播源發(fā)送反饋報文NACK，請求重傳丟失編碼包Ui。當(dāng)接收端正確接收到編碼包Ui之后，通過在本地解碼Ui，即可實現(xiàn)一次重傳，恢復(fù)多個丟失報文。

（3）檢測→檢測：對應(yīng)圖3中的狀態(tài)③，用于處理上述（1）和（2）之外的情況。比如出現(xiàn)編碼包Ui丟失，而原始報文Kji未丟失，這種情況是不需要處理的。

3 理論分析

定義組播組大小為s（s＞0），設(shè)接收端丟包率均為p（0＜p＜1），丟失報文數(shù)記為D，平均重傳次數(shù)記為E，考慮端到端即s＝1，傳輸一塊數(shù)據(jù)Bi的情況。

（1）ARQ 機制。

傳統(tǒng)的ARQ 機制主要包含兩個過程：反饋、重傳。即當(dāng)接收端檢測到報文丟失時，向發(fā)送端發(fā)送反饋信息，接收端接收到反饋信息后，重傳對應(yīng)的丟失報文。

ARQ 機制不需要傳輸編碼包，對于一塊數(shù)據(jù)Bi，包含k個原始報文，則丟失報文數(shù)為D＝pk，對任意一個丟失報文而言，平均需要重傳的次數(shù)記為Ee，則Ee＝1/（1－p），故可以得到E＝D＊Ee＝pk/（1－p）。

（2）NCM 機制。

NCM 機制在ARQ 機制的基礎(chǔ)上，主動發(fā)送了冗余編碼包，當(dāng)檢測到報文丟失時，并不立即向發(fā)送端發(fā)送反饋信息，而是先檢測對應(yīng)的編碼包是否丟失，如果沒有丟失，則嘗試本地恢復(fù)，否則進行反饋重傳。

對于任意一塊數(shù)據(jù)Bi，包含k個原始報文和1個編碼包，所以傳輸?shù)膱笪目倲?shù)為k＋1，丟包數(shù)D＝p（k＋1）。假設(shè)D＞1，事件X＝｛編碼包Ui未丟失｝，每塊數(shù)據(jù)平均需要重傳的次數(shù)記為Re，則有P（X），其中k＞0，0＜p＜1。對于編碼包Ui未丟失的情況，可以通過在接收端解碼編碼包，本地還原出丟失報文，此時不需要重傳，故Re（X）＝0；若編碼包丟失，則只需要重傳一次編碼包，因此則使用NCM 機制，發(fā)送端每發(fā)送一塊數(shù)據(jù)，平均需要的重傳次數(shù)可以表示為：

其中，k＞0，0＜p＜1，D＞1。

考慮組播組大小為s、傳輸n塊的情況。假設(shè)待傳輸?shù)臄?shù)據(jù)可分成n塊，則傳輸?shù)挠行笪牡目倲?shù)為nk，設(shè)組播發(fā)送端和接收端使用單播反饋和修復(fù)，且不使用退避機制和反饋抑制機制［11］。

（1）ARQ 機制。

ARQ 機制，由于組播系統(tǒng)不使用反饋抑制機制，即使不同接收端出現(xiàn)相同丟包，都需要反饋和重傳一次，因此平均重傳次數(shù)和組播組大小s成正比，使用ARQ 機制傳輸n塊數(shù)據(jù)時平均需要的重傳次數(shù)為：

（2）NCM 機制。

使用NCM 機制，對于n塊數(shù)據(jù)，傳輸?shù)膱笪目倲?shù)為n（k＋1），重傳次數(shù)最多為n次。設(shè)需要重傳i次的概率為Pi（0＜i＜n＋1），則Pi服從n和P（） 的二項分布，即Pi～B（n，P（）） ，在不使用反饋抑制的情況下，重傳次數(shù)和組播組大小正比，所以：

取n＝400，k＝5，s＝5，p∈（0，0.2），用Matlab繪出公式（1）、公式（2）中E隨p變化的曲線，如圖4 所示。從圖4 可以看出，理論上講，ARQ 機制和NCM 機制的平均重傳次數(shù)隨丟包率的增加而增大；在丟包率較高，即傳輸鏈路狀況不佳的情況下，相比NCM 機制，ARQ 機制需要的平均重傳次數(shù)急劇增加，很容易發(fā)生“確認風(fēng)暴”，而NCM 機制通過采用網(wǎng)絡(luò)編碼本地恢復(fù)策略，雖然引入了一定的冗余，但是即使在高丟包的環(huán)境，也很大程度上減少了反饋重傳次數(shù)，有效避免了“確認風(fēng)暴”的發(fā)生，從而提高了差錯恢復(fù)的實時性和組播的可靠性。

Figure 4 Comparison of retransmission in theory value圖4 兩種方法平均重傳次數(shù)理論值的比較

4 仿真分析

4.1 仿真場景和參數(shù)設(shè)置

為了評估NCM 機制的有效性，針對ARQ 和NCM 分別進行了仿真實驗。仿真實驗使用的操作系統(tǒng)是Ubuntu，在自研網(wǎng)絡(luò)仿真平臺上進行實現(xiàn)。仿真實驗的拓撲如圖5所示，包含一個GEO衛(wèi)星節(jié)點和若干組成員接收節(jié)點。其中衛(wèi)星節(jié)點模擬組播源和衛(wèi)星，組成員接收節(jié)點模擬地面接收網(wǎng)關(guān)。實驗仿真的參數(shù)設(shè)置如表1所示。

Figure 5 Simulation topology圖5 仿真拓撲

Table 1 Simulation parameter settings表1 仿真參數(shù)設(shè)置

4.2 性能評估指標(biāo)

在本文中，主要使用如下兩個參數(shù)來評價NCM 機制的性能：

（1）重傳次數(shù)：定義可靠組播系統(tǒng)實際需要的重傳次數(shù)為每個地面站需要的重傳次數(shù)之和。重傳次數(shù)是衡量組播協(xié)議可靠性最為重要的指標(biāo)，同時也是NCM 方法優(yōu)勢的最直觀體現(xiàn)。

（2）吞吐量：吞吐量是通信鏈路利用率的重要衡量指標(biāo)。在本文中，吞吐量的計算方法為單位時間內(nèi)接收端接收到的有效數(shù)據(jù)量。NCM 機制雖然引入了冗余，但是卻減少了數(shù)據(jù)修復(fù)的時延，從而在一定程度上可獲得較好的吞吐量增益。

4.3 性能分析

下面在不同丟包率、數(shù)據(jù)量和組播組大小的情況下，分別使用ARQ 和NCM 兩種機制對可靠組播系統(tǒng)的實際重傳次數(shù)和吞吐量性能比較。

4.3.1 丟包率對性能的影響

仿真實驗在設(shè)置組播組大小為5 個，發(fā)送2 000個報文的情況下，測試了兩種機制在不同丟包率下對衛(wèi)星可靠組播系統(tǒng)性能的影響。

（1）重傳次數(shù)。

圖6a給出了在不同丟包率下，通過仿真實驗兩種機制所獲得的實際重傳次數(shù)的比較。對比圖4，可以發(fā)現(xiàn)實驗值和理論值基本一致，說明本文提出的NCM 機制是可行而且有效的。實驗結(jié)果表明，相比傳統(tǒng)的ARQ 反饋重傳方式，NCM 能很大程度上減少反饋重傳次數(shù)，提高鏈路的可靠性；同時也證明了NCM 機制非常適合在高丟包率和高誤碼率的衛(wèi)星傳輸鏈路中使用，有效地提高了組播的可靠性。

Figure 6 Comparison of retransmission and throughput under different loss rates圖6 不同丟包率下重傳次數(shù)和吞吐量的比較

（2）吞吐量。

圖6b給出了不同丟包率下，通過仿真實驗所獲得的系統(tǒng)吞吐量的對比。從圖6b中我們可以看出隨著丟包率的增加，吞吐量都是呈下降趨勢。這是因為在高丟包率的環(huán)境下，要保證組播的可靠性，重傳是不可避免的。丟包率越高，需要重傳的次數(shù)越多，從而引起整個鏈路吞吐量的下降。相比傳統(tǒng)ARQ 機制，NCM 機制在高丟包率的環(huán)境下能獲得很好的吞吐量增益。但是，在鏈路狀況較好的情況下，由于NCM 引入了冗余編碼包，占用了部分帶寬，所以吞吐量性能不如ARQ。

4.3.2 數(shù)據(jù)量對性能的影響

仿真實驗在設(shè)置組播組大小為5個、丟包率為10%的情況下，測試了兩種機制在不同數(shù)據(jù)量下對衛(wèi)星可靠組播系統(tǒng)性能的影響。

（1）重傳次數(shù)。

圖7a給出了在不同數(shù)據(jù)量下，分別使用ARQ和NCM 機制，實驗所獲得的實際重傳次數(shù)的比較。圖7a中的實驗結(jié)果表明，在相同組播組大小和丟包率的情況下，單次傳輸?shù)臄?shù)據(jù)量越多，兩種機制下重傳次數(shù)也增多。但是，NCM 機制相比ARQ 機制，二者需要重傳的次數(shù)相差越來越大，NCM 機制獲得的可靠性增益變得越來越明顯。NCM 機制在發(fā)送4 000個數(shù)據(jù)包時，重傳報文數(shù)量約占發(fā)送的原始數(shù)據(jù)量的5%，相比ARQ 機制，重傳比例降低了近10倍，很大程度上抑制了“確認風(fēng)暴”的發(fā)生。

Figure 7 Comparison of retransmission and throughput under different amount of data圖7 不同數(shù)據(jù)量下重傳次數(shù)和吞吐量的比較

（2）吞吐量。

圖7b給出了在相同丟包率和組播組大小、不同數(shù)據(jù)量下，通過仿真ARQ 和NCM 機制，實驗獲得的系統(tǒng)吞吐量的對比。從圖7b中可以看出，隨著單次發(fā)送的數(shù)據(jù)量增加，兩種機制下組播系統(tǒng)的吞吐量基本上保持穩(wěn)定。這主要是因為發(fā)送的數(shù)據(jù)量越多，數(shù)據(jù)的發(fā)送時延越大，在相同丟包率下，單位時間內(nèi)需要重傳的報文數(shù)量維持在一個相對穩(wěn)定的狀態(tài)。由于NCM 機制雖然引入了一定的冗余，但是相比ARQ 機制，很大程度上減少了重傳次數(shù)，獲得了發(fā)送時延上的增益，所以NCM 機制的吞吐量性能表現(xiàn)更優(yōu)。

4.3.3 組播組大小對性能的影響

實驗測試了在單次發(fā)送的數(shù)據(jù)量為2 000個報文、丟包率為10%的情況下，分別使用ARQ 和NCM 機制，組播組大小對衛(wèi)星可靠組播系統(tǒng)性能的影響。

（1）重傳次數(shù)。

圖8a給出了在不同組播組大小的情況下重傳次數(shù)的比較。隨著組播組規(guī)模的增大，重傳次數(shù)也在增加。但是，NCM 機制增加的速度遠小于ARQ 機制。由于本文重點研究網(wǎng)絡(luò)編碼本地恢復(fù)機制的可靠性增益，實驗中僅使用單播反饋和修復(fù)，所以即使不同地面站出現(xiàn)了相同丟包，都只需要反饋和重傳一次，重傳次數(shù)和組播組大小呈正比，與理論推導(dǎo)相符。此外，NCM 機制的可靠性增益非常明顯，說明它更適合組播組規(guī)模較大的可靠組播系統(tǒng)。

Figure 8 Comparison of retransmission and throughput under different group sizes圖8 不同組播組大小下重傳次數(shù)和吞吐量的比較

（2）吞吐量。

圖8b給出了在不同組播組大小的情況下吞吐量的對比?？梢钥吹剑掏铝侩S著組播組規(guī)模的增大而增加。這是因為在組播系統(tǒng)中，整個系統(tǒng)的吞吐量是每個組播組成員吞吐量的疊加，因此吞吐量與組播組大小呈正比。而且，在相同丟包率下，NCM 機制比ARQ 機制獲得了更好的吞吐量增益。

5 結(jié)束語

本文提出了一種衛(wèi)星網(wǎng)絡(luò)可靠組播機制NCM，該機制可有效減少反饋重傳的次數(shù)，提高衛(wèi)星傳輸鏈路的利用率和可靠性，增強了丟失數(shù)據(jù)恢復(fù)的實時性。下一步將重點考慮不同的編碼方式對系統(tǒng)性能的影響等，對NCM 進行進一步改進。

［1］ Akyildiz I F.TCP－peachtree：A multicast transport protocol for satellite IP networks［J］.IEEE Journal on Selected Areas in Communications，2004，22（2）：388－400.

［2］ Cheng Wang，Leung V C M.A reliable multicast transport protocol satellite networks［C］∥Proc of IEEE 2002International Conference on Communications，Circuits and Systems and West Sino Expositions，2002：445－449.

［3］ Cheng Wang，Leung V C M.Performance evaluations of SRMTP for reliable multicasting over satellite networks［C］∥Proc of IEEE WCNC’03，2003：1813－1818.

［4］ Basu P，Kanchanasut K.A reliable multicast protocol for unidirectional satellite link［C］∥Proc of IEEE 2003Symposium on Applications and Internet（SAINT’03），2003：325－329.

［5］ Liu Gong－liang，Gu Xue－mai，Guo Qing，et al.Error recovery schema for reliable multicast via satellite［J］.Computer Application，2007，24（12）：352－353.（in Chinese）

［6］ Nguyen D，Nguyen T，Bose B.Wireless broadcasting using network coding［R］.Technical Report：OSU－TR－2006－06.Oregon：Oregon State University，2006.（in Chinese）

［7］ Xiao Xiao，Yang Lu－ming，Pu Bao－xing.Research on multinode wireless broadcasting retransmission scheme based on networking coding［J］.Computer Application，2008，28（4）：849－852.（in Chinese）

［8］ Zheng Qing－h(huán)ua，Chu Chun－sheng，Zhao Deng－ke.A model for reliable multicast via integrated Internet［J］.Journal of Chinese Computer System，2005，26（7）：1133－1139.（in Chinese）

［9］ Ho T，Medard M，Koetter R，et al.BA random liner network coding approach to multicast［J］.IEEE Transactions on Information Theory，2006，52（10）：4413－4430.

［10］ Kim M，Cloud J.Modeling network coded TCP throughput：A simple model and its validation［C］∥Proc of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools（ICST），2011：131－140.

［11］ Nonnenmacher J，Biersack E W.Optimal multicast feedback［C］∥Proc of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies，1998：964－971.

附中文參考文獻：.

［5］ 劉功亮，顧學(xué)邁，郭慶，等.一種適合衛(wèi)星可靠組播的差錯恢復(fù)方案［J］.計算機應(yīng)用研究，2007，24（12）：352－353.

［7］ 肖瀟，楊路明，蒲保興.基于網(wǎng)絡(luò)編碼的多節(jié)點無線廣播重傳策略［J］.計算機應(yīng)用，2008，28（4）：849－852.

［8］ 鄭慶華，儲春生，趙登科.一種適用于天地網(wǎng)可靠多播的傳輸模型［J］.小型微型計算機系統(tǒng)，2005，26（7）：1133－1139.