一种基于网络编码的新型卫星网络可靠组播机制＊

桂永茂，赵宝康，唐 竹，彭 伟，夏 艳，徐 芬

（1.国防科学技术大学计算机学院，湖南 长沙410073；2.湖南大学信息科学与工程学院，湖南 长沙410082；3.中国空气动力研究与发展中心超高速空气动力研究所，四川 绵阳621000）

1 引言

卫星网络具有天然的广播特性，具有覆盖范围广和拓扑简单等优点，使得其非常适合组播业务传输。然而，卫星传输链路带宽受限，长时延和高误码的特点，使得传统组播传输协议面临可靠性等难题。数据的可靠传输涉及到数据的重传，因此，针对卫星网络设计一种高效的重传机制，尽可能地减少反馈重传的次数并提高带宽利用率，具有十分重要的意义。

传统的卫星网络可靠组播协议［1～4］大多使用ARQ（Automatic Repeating re－Quest）技术，即自动请求重传来保证组播数据的绝对可靠性，然而在卫星网络中，当组播接收端数目过大时，单独使用ARQ 技术容易发生“确认风暴”问题。还有部分可靠组播协议［5～7］使用了发送窗口机制来最大限度地减少重传开销，虽然减少了重传，但是并没有减少确认次数，因此仍然存在“确认风暴”的问题，而且在发送端等待发送窗口，一定程度上降低了差错恢复的实时性。

另外一些卫星可靠组播协议使用了混合ARQ机制［8］，虽然混合ARQ 机制较大程度上减少了反馈重传的次数和提高了差错恢复的实时性，但是并没有实现结构化的传输。

本文提出了一种基于网络编码的卫星网络可靠组播机制NCM（Network Coding Mechanism）。该机制采用结构化的分块传输方法，通过在发送端主动发送原始报文的冗余编码包，可实现接收端多个丢失报文的本地恢复，从而大大减少了反馈重传次数，提高了差错恢复的实时性；同时结合ARQ机制，当出现原始报文和编码报文同时丢失时，通过一次重传编码包，即可恢复多个丢失报文，不但减少了重传次数，还保证了组播的可靠性。

2 网络编码组播机制

2.1 卫星网络模型

图1描述了卫星网络可靠组播协议的层次结构。卫星网络包含GEO（GEosynchronous Orbit）卫星和若干地面站，地面站包括发送端地面站和接收端地面站。卫星网络通过网关和地面网络及用户终端相连。

Figure 1 Model of satellite networks图1 卫星网络模型

2.2 问题描述

卫星网络传输链路容易受到天气等因素的干扰，具有高误码和长时延的固有特性，这两个特性为可靠多播提出了难题。本文提出的NCM 机制针对“确认风暴”、实时差错恢复及结构化传输这三个问题进行了重点优化。

2.3 NCM 机制描述

NCM 机制采用随机线性网络编码［9］，主要由两部分组成：一个是结构化传输，另一个是本地恢复结合ARQ 重传。

（1）结构化传输。

混合ARQ 机制通过采用前向纠错编码FEC（Forward Error Correction）机制，虽然能较大程度上减少重传，但是并没有实现明显的结构化传输。NCM 机制采用分块的结构化传输方法，块结构如图2所示，每块包含k个原始报文和一个编码包，其中定义第i块为Bi，第i块中的第m个报文表示为第i块的原始报文的编码包为Ui。组播源将待发送的数据分成n块，对于每块Bi，平均分成k个原始数据包，然后将这k个数据包经过k次编码组合，得到k个编码报文，最后把这k个编码报文压缩成一个编码包Ui，根据随机线性网络编码原理，对于第i块，设随机产生的k个编码系数为［ai，1，ai，2，…，ai，k］，则有接收端在接收到编码包后，先解压缩还原出编码报文，然后通过高斯消元法［9，10］，即可解码出原始报文。

（2）本地恢复结合ARQ 重传。

NCM 主要分为三个过程：检测、恢复、反馈重传。三个过程的转换如图3所示。

Figure 2 Block structure图2 块结构

Figure 3 Process switching图3 过程转换

传统ARQ 主要缺少过程①，所以NCM 相比ARQ，提升性能的关键在于①。

（1）检测→恢复：对应于图3中的状态①，为本地恢复过程。当接收端接收到数据块Bi之后，进行检测。如果检测到一个或者多个原始报文（0＜j＜k＋1）丢失，而编码包Ui未丢失，则通过在本地解码Ui即可实现丢失报文本地恢复，从而大大增强了数据恢复的实时性，减少了反馈重传。

（2）检测→反馈重传→恢复：对应于图3中的状态②，即传统ARQ 重传过程。当接收端接收到数据块Bi之后，进行检测。如果检测到原始报文丢失，编码包Ui也丢失，则接收端通过反馈链路向组播源发送反馈报文NACK，请求重传丢失编码包Ui。当接收端正确接收到编码包Ui之后，通过在本地解码Ui，即可实现一次重传，恢复多个丢失报文。

（3）检测→检测：对应图3中的状态③，用于处理上述（1）和（2）之外的情况。比如出现编码包Ui丢失，而原始报文Kji未丢失，这种情况是不需要处理的。

3 理论分析

定义组播组大小为s（s＞0），设接收端丢包率均为p（0＜p＜1），丢失报文数记为D，平均重传次数记为E，考虑端到端即s＝1，传输一块数据Bi的情况。

（1）ARQ 机制。

传统的ARQ 机制主要包含两个过程：反馈、重传。即当接收端检测到报文丢失时，向发送端发送反馈信息，接收端接收到反馈信息后，重传对应的丢失报文。

ARQ 机制不需要传输编码包，对于一块数据Bi，包含k个原始报文，则丢失报文数为D＝pk，对任意一个丢失报文而言，平均需要重传的次数记为Ee，则Ee＝1/（1－p），故可以得到E＝D＊Ee＝pk/（1－p）。

（2）NCM 机制。

NCM 机制在ARQ 机制的基础上，主动发送了冗余编码包，当检测到报文丢失时，并不立即向发送端发送反馈信息，而是先检测对应的编码包是否丢失，如果没有丢失，则尝试本地恢复，否则进行反馈重传。

对于任意一块数据Bi，包含k个原始报文和1个编码包，所以传输的报文总数为k＋1，丢包数D＝p（k＋1）。假设D＞1，事件X＝｛编码包Ui未丢失｝，每块数据平均需要重传的次数记为Re，则有P（X），其中k＞0，0＜p＜1。对于编码包Ui未丢失的情况，可以通过在接收端解码编码包，本地还原出丢失报文，此时不需要重传，故Re（X）＝0；若编码包丢失，则只需要重传一次编码包，因此则使用NCM 机制，发送端每发送一块数据，平均需要的重传次数可以表示为：

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

考虑组播组大小为s、传输n块的情况。假设待传输的数据可分成n块，则传输的有效报文的总数为nk，设组播发送端和接收端使用单播反馈和修复，且不使用退避机制和反馈抑制机制［11］。

（1）ARQ 机制。

ARQ 机制，由于组播系统不使用反馈抑制机制，即使不同接收端出现相同丢包，都需要反馈和重传一次，因此平均重传次数和组播组大小s成正比，使用ARQ 机制传输n块数据时平均需要的重传次数为：

（2）NCM 机制。

使用NCM 机制，对于n块数据，传输的报文总数为n（k＋1），重传次数最多为n次。设需要重传i次的概率为Pi（0＜i＜n＋1），则Pi服从n和P（） 的二项分布，即Pi～B（n，P（）） ，在不使用反馈抑制的情况下，重传次数和组播组大小正比，所以：

取n＝400，k＝5，s＝5，p∈（0，0.2），用Matlab绘出公式（1）、公式（2）中E随p变化的曲线，如图4 所示。从图4 可以看出，理论上讲，ARQ 机制和NCM 机制的平均重传次数随丢包率的增加而增大；在丢包率较高，即传输链路状况不佳的情况下，相比NCM 机制，ARQ 机制需要的平均重传次数急剧增加，很容易发生“确认风暴”，而NCM 机制通过采用网络编码本地恢复策略，虽然引入了一定的冗余，但是即使在高丢包的环境，也很大程度上减少了反馈重传次数，有效避免了“确认风暴”的发生，从而提高了差错恢复的实时性和组播的可靠性。

Figure 4 Comparison of retransmission in theory value图4 两种方法平均重传次数理论值的比较

4 仿真分析

4.1 仿真场景和参数设置

为了评估NCM 机制的有效性，针对ARQ 和NCM 分别进行了仿真实验。仿真实验使用的操作系统是Ubuntu，在自研网络仿真平台上进行实现。仿真实验的拓扑如图5所示，包含一个GEO卫星节点和若干组成员接收节点。其中卫星节点模拟组播源和卫星，组成员接收节点模拟地面接收网关。实验仿真的参数设置如表1所示。

Figure 5 Simulation topology图5 仿真拓扑

Table 1 Simulation parameter settings表1 仿真参数设置

4.2 性能评估指标

在本文中，主要使用如下两个参数来评价NCM 机制的性能：

（1）重传次数：定义可靠组播系统实际需要的重传次数为每个地面站需要的重传次数之和。重传次数是衡量组播协议可靠性最为重要的指标，同时也是NCM 方法优势的最直观体现。

（2）吞吐量：吞吐量是通信链路利用率的重要衡量指标。在本文中，吞吐量的计算方法为单位时间内接收端接收到的有效数据量。NCM 机制虽然引入了冗余，但是却减少了数据修复的时延，从而在一定程度上可获得较好的吞吐量增益。

4.3 性能分析

下面在不同丢包率、数据量和组播组大小的情况下，分别使用ARQ 和NCM 两种机制对可靠组播系统的实际重传次数和吞吐量性能比较。

4.3.1 丢包率对性能的影响

仿真实验在设置组播组大小为5 个，发送2 000个报文的情况下，测试了两种机制在不同丢包率下对卫星可靠组播系统性能的影响。

（1）重传次数。

图6a给出了在不同丢包率下，通过仿真实验两种机制所获得的实际重传次数的比较。对比图4，可以发现实验值和理论值基本一致，说明本文提出的NCM 机制是可行而且有效的。实验结果表明，相比传统的ARQ 反馈重传方式，NCM 能很大程度上减少反馈重传次数，提高链路的可靠性；同时也证明了NCM 机制非常适合在高丢包率和高误码率的卫星传输链路中使用，有效地提高了组播的可靠性。

Figure 6 Comparison of retransmission and throughput under different loss rates图6 不同丢包率下重传次数和吞吐量的比较

（2）吞吐量。

图6b给出了不同丢包率下，通过仿真实验所获得的系统吞吐量的对比。从图6b中我们可以看出随着丢包率的增加，吞吐量都是呈下降趋势。这是因为在高丢包率的环境下，要保证组播的可靠性，重传是不可避免的。丢包率越高，需要重传的次数越多，从而引起整个链路吞吐量的下降。相比传统ARQ 机制，NCM 机制在高丢包率的环境下能获得很好的吞吐量增益。但是，在链路状况较好的情况下，由于NCM 引入了冗余编码包，占用了部分带宽，所以吞吐量性能不如ARQ。

4.3.2 数据量对性能的影响

仿真实验在设置组播组大小为5个、丢包率为10%的情况下，测试了两种机制在不同数据量下对卫星可靠组播系统性能的影响。

（1）重传次数。

图7a给出了在不同数据量下，分别使用ARQ和NCM 机制，实验所获得的实际重传次数的比较。图7a中的实验结果表明，在相同组播组大小和丢包率的情况下，单次传输的数据量越多，两种机制下重传次数也增多。但是，NCM 机制相比ARQ 机制，二者需要重传的次数相差越来越大，NCM 机制获得的可靠性增益变得越来越明显。NCM 机制在发送4 000个数据包时，重传报文数量约占发送的原始数据量的5%，相比ARQ 机制，重传比例降低了近10倍，很大程度上抑制了“确认风暴”的发生。

Figure 7 Comparison of retransmission and throughput under different amount of data图7 不同数据量下重传次数和吞吐量的比较

（2）吞吐量。

图7b给出了在相同丢包率和组播组大小、不同数据量下，通过仿真ARQ 和NCM 机制，实验获得的系统吞吐量的对比。从图7b中可以看出，随着单次发送的数据量增加，两种机制下组播系统的吞吐量基本上保持稳定。这主要是因为发送的数据量越多，数据的发送时延越大，在相同丢包率下，单位时间内需要重传的报文数量维持在一个相对稳定的状态。由于NCM 机制虽然引入了一定的冗余，但是相比ARQ 机制，很大程度上减少了重传次数，获得了发送时延上的增益，所以NCM 机制的吞吐量性能表现更优。

4.3.3 组播组大小对性能的影响

实验测试了在单次发送的数据量为2 000个报文、丢包率为10%的情况下，分别使用ARQ 和NCM 机制，组播组大小对卫星可靠组播系统性能的影响。

（1）重传次数。

图8a给出了在不同组播组大小的情况下重传次数的比较。随着组播组规模的增大，重传次数也在增加。但是，NCM 机制增加的速度远小于ARQ 机制。由于本文重点研究网络编码本地恢复机制的可靠性增益，实验中仅使用单播反馈和修复，所以即使不同地面站出现了相同丢包，都只需要反馈和重传一次，重传次数和组播组大小呈正比，与理论推导相符。此外，NCM 机制的可靠性增益非常明显，说明它更适合组播组规模较大的可靠组播系统。

Figure 8 Comparison of retransmission and throughput under different group sizes图8 不同组播组大小下重传次数和吞吐量的比较

（2）吞吐量。

图8b给出了在不同组播组大小的情况下吞吐量的对比。可以看到，吞吐量随着组播组规模的增大而增加。这是因为在组播系统中，整个系统的吞吐量是每个组播组成员吞吐量的叠加，因此吞吐量与组播组大小呈正比。而且，在相同丢包率下，NCM 机制比ARQ 机制获得了更好的吞吐量增益。

5 结束语

本文提出了一种卫星网络可靠组播机制NCM，该机制可有效减少反馈重传的次数，提高卫星传输链路的利用率和可靠性，增强了丢失数据恢复的实时性。下一步将重点考虑不同的编码方式对系统性能的影响等，对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－hua，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］ 刘功亮，顾学迈，郭庆，等.一种适合卫星可靠组播的差错恢复方案［J］.计算机应用研究，2007，24（12）：352－353.

［7］ 肖潇，杨路明，蒲保兴.基于网络编码的多节点无线广播重传策略［J］.计算机应用，2008，28（4）：849－852.

［8］ 郑庆华，储春生，赵登科.一种适用于天地网可靠多播的传输模型［J］.小型微型计算机系统，2005，26（7）：1133－1139.