移动互联网下基于RS编码的文件传输软件设计与实现

文艾

摘要：针对移动互联网环境下，基于TCP的文件传输软件效率较低的问题，设计并实现了基于RS（Reed-Solomon）编码的文件传输软件。该软件基于UDP协议，利用RS编码的特性实现文件分块传输的前向纠错，可容忍一定范围内的数据丢失，无需重传，可有效减少交互开销，对超出纠错范围的分片数据，利用重传机制，保证可靠传输。实验结果表明，在高误码率，大时延情况下，该软件的传输性能（成功率、传输速率）相对传统的文件传输软件显著提升。

关键词：RS编码；文件传输；移动互联网

中图分类号：TP393.093 文献标识码：A 文章编号：1009-3044（2014）29-6834-05

Abstract： In view of the low efficiency of file transfer software based on TCP in mobile internet environment， a new file transfer software based on RS（Reed-Solomon） code was designed and implemented. The software is based on UPD protocol and it takes advantage of RS code to achieve FEC（forward error correction） of file block transfer. This characteristic can make the software to tolerate a range of block loss and no need to repeat， so it can reduce the communication overhead effectively. For the data which exceeds the error correction range， the retransmission mechanism is used to ensure the reliable transmission. The result of experiment shows that， under the condition of high error rate and long time delay， the transfer performance of the software（success rate， transfer speed）is significantly better than traditional file transfer software.

Key words： RS code； file transfer； mobile internet environment

文件传输是一项非常重要的网络应用。传统的文件传输软件，如FTP等，通常采用TCP协议，TCP是面向连接的运输层协议，它可以实现数据的按序、可靠传输。TCP最初是针对有线网络设计的，该网络的特点是：低时延、低误码率。而在移动互联网环境下，情形相反，大时延，高误码率是其特点。TCP原有的一些设计并不能很好地适应这一新的网络环境，导致效率低下。其中，TCP协议的重传机制和拥塞控制机制是导致其在移动互联网环境下效率低下的两个主要原因，分析如下。

首先，TCP协议使用重传机制来实现数据的可靠传输。TCP会自动对发送方所发出的数据进行编号，并且启动计时器，如果在规定的时间内，未收到接收方对该数据的ACK，便会触发计时器，自动重发数据。如果重传次数超过系统所设定的阈值，TCP协议栈会向上层报告传输失败。对于一次成功的数据传输，包括数据发送和ACK成功两个部分，缺一不可。对于传统的有线网络来说，收发双方的信道质量是有保证的。而对于移动互联网，由于处在无线环境下，其误码率大大高于有线环境，甚至还会存在信道不对称的情况。TCP的重传机制，会显著增加交互开销，从而降低数据传输的成功概率和速率。

其次，传统的TCP协议会将传输中所遇到的丢包和时延增大作为网络拥塞的主要判据，这在传统的有线网络中，是没有问题的。但是，在移动互联网环境下，时延和误码率受多种因素的影响，如信道质量、干扰、以及移动速率等。大多数情况下，出现丢包或者时延增大，并不是因为出现了网络拥塞。由于TCP协议误判，从而启动拥塞控制，通常的做法是，将原有的发送窗口缩小一半，由于此时网络并未真正拥塞，因此，降低速率并不会改善当前状况，问题依旧，然而，TCP协议会继续误判，认为拥塞非常严重，再次降低一半的发送速率，如此循环，导致在移动互联网环境下，TCP的性能下降非常明显[1-2]。

针对上述问题，提出了多种解决方法，常见的方法是对TCP进行优化，如TCP网络编码[3-4]、改进拥塞控制[5-7]。上述方法的优点是，对上层应用透明，无需修改，即可使用。缺点是，需要修改TCP协议栈，由于协议栈与操作系统是紧密结合的。而移动互联网中，各种节点上所运行的操作系统型号和版本各不相同，需要针对每种系统进行专门的优化，从应用的角度来说，上述方案可行性较低。

为此，该文设计并实现了基于RS编码的文件传输软件。该软件基于UDP协议，利用RS编码的特性实现文件分块传输的前向纠错，可容忍一定范围内的数据丢失，无需重传，可有效减少交互开销，对超出纠错范围的分片数据，利用重传机制，保证可靠传输。它具有如下优点：首先，根除了TCP拥塞误判所带来的性能下降；其次，利用RS编码进行前向纠错，可有效降低交互开销；最后，软件独立于操作系统，无需修改协议栈，可行性高。实验结果表明，在高误码率，大时延情况下，该软件的传输速率明显高于传统的文件传输软件。

1 基于RS编码的容错传输机制endprint

1.1 RS编码原理

RS编码是一种常见的纠删码，它由Reed I S， Solomon G于1960年提出[8]。RS算法的基本原理是，通过对原始的m个数据，进行编码，得到n个数据，n>m，对于n个编码数据，取其中任意的m个数据，通过译码操作，均可恢复出m个原始数据[9-10]，示意图如下所示（基于RS纠删码的信息分散算法）。

RS算法的关键编码和译码过程实际上是一个矩阵的运算过程。假设原始数据为m个，则可以视为1行m列的矩阵S1，m，与一个m行n列的矩阵Mm，n相乘，最后的结果为1行n列的矩阵D1，n，这就是编码过程，见式（1） 。其中，Mm，n称为生成矩阵，它满足这样的一个特性，由该矩阵的任意m列数据所组成的m*m的方阵Mm，m都存在逆矩阵M-1m，m。由编码的过程，可以得到下面的公式（1） ，对于方阵Mm，m，由式（1） 可以得到式（2） 依然成立。又根据生成矩阵的定义，对任意的Mm，m都存在逆矩阵M-1m，m，因此，可以得到式（3） 。由于D1，m是任选的，因此，式（3） 即译码过程，对于最终剩余的编码数据，只要个数大于m个，即可从中选择m个组成D1，m，同时选择m个数据在生成矩阵中对应的列，组成方阵Mm，m，计算逆矩阵M-1m，m，再运用式1） 按照固定的大小对待发送的文件进行分割，划分的每个单元称为1个Block，每个Block的大小不超过网络的MTU，这样做的目的是防止Block在数据链路层进行分片，由于分片的传输没有重传机制，因此，任意一个分片的丢失，都会导致上层Block的传输失败，需要重传整个Block数据；

2） 按序对Block进行分组，每组Block就是一个编码的基本单元，假设一组Block的数量为m，m的值可以由上层指定，默认为4，编码后的Block数量为n，默认为6；

3） 确定需要编码的Block组号，如果该组已编码，则直接进入发送模块，进行发送，如果未编码，则调用编码函数，对该组数据进行编码，然后进入发送模块；

4） 发送模块检查当前待发送的Block组，根据每个Block的接收情况，确定组内需要发送的Block，需要考虑两种情况，一种是该组Block未发送，那么直接按序发送组内所有Block；第二种情况是，该组Block已发送，且有部分Block已接收，但不满足译码条件，此时，需要计算要达到译码条件还需要继续发送的Block数，并在此基础上加1，例如，在m=4，n=8的情况下，已经收到2个Block，那么可以计算出还需要译码还需要4-2=2个Block，在此基础上再增加1，那么此次发送3个Block，只需要收到其中任意2个，即可译码，至于待发送的3个Block，则从未收到的8-2=6个Block中任意挑选即可；

5） 发送模块发送完若干组Block数据后，会等待接收方的ACK回馈，同时启动定时器。如果超时，则会跳到3） 重新计算分片序列，重新发送。如果接收到ACK，清除定时器，ACK会包含已收到各组Block 的情况，如果接收的Block均已满足译码条件，则再看该文件的所有数据是否发送完毕，如果是，则结束，如果未完成，则跳至3） 。如果该组Block不满足译码条件，则跳至3） 继续发送。

接收方流程：

1） 在指定端口监听，接收Block组；

2） 向发送方发送Block接收的ACK；

3） 计算已接收的Block组是否满足译码条件，如果不满足，跳至1） ，如果满足，则跳至4） ；

4） 对Block组进行译码，根据相应的信息，将译码得出的Block写入文件对应的偏移处；

5） 判断文件接收是否完毕，如果是，则退出，如果否，则跳至1） ，继续接收。

1.3 性能分析

与TCP重传机制相比，采用RS编码的容错传输机制可以有效提升数据发送的成功概率。假设Block在发送过程中成功率为p，待传输的Block数为m，编码后的Block数为n（n>m），为简化模型，不考虑接收方到发送方信道质量的影响，即发送方总能收到ACK。RS编码译码模块是RS算法的实现模块，向上提供以字节为单位的RS编码和译码接口。生成矩阵的构建是RS算法实现的一个关键，常用的是范德蒙矩阵和柯西矩阵。由于柯西矩阵的特性，译码时，对于原始的数据，无需译码，因此相对范德蒙矩阵效率高。此外，不管是范德蒙矩阵，还是柯西矩阵，在进行译码时，都需要进行矩阵的逆运算，由于实数域的运算都将存在无法整除的可能，因此，将矩阵的运算转移到伽罗华域，在进行编码和译码时都采用伽罗华域的运算，一次编码和一次译码，正好实现最终的数据回归到实数域，此外，伽罗华域的运算还将实数域的加法转换为异或、乘法转换为加、除法转换为减，转换后的运算非常适合在计算机上进行优化，从而提高效率。

异常处理模块主要是对程序中所遇到的各种异常情况进行进行分类、分级的处理，并且写入相应的日志信息。

2.2 多线程任务处理框架

按照设计需求，传输软件需要支持多任务并行处理，包括同时支持发送任务和接收任务，以及多个发送任务或多个接收任务，且任务的执行、操作、状态显示三者都需要并行处理。这就要求，软件必须支持任务的异步执行，而且，底层传输任务的处理与界面的显示和操作之间要有良好的处理接口。为此，设计了基于任务队列的多线程处理框架来解决上述问题。

该框架包括消息队列、任务队列、以及调度线程、发送线程、接收线程等构件。其中，用户通过任务界面将发送任务或其它操作提交到任务队列，然后立即返回，定义专门的任务结构来保存用户提交的操作，调度线程负责从任务队列的首部取节点，根据任务的类型，启动不同处理线程进行操作，其中发送线程和接收线程的可以根据需要设定为多个，从而支持多任务并行处理。此外，对于底层线程在处理过程中的各种信息，如任务的执行的状态，传输速度等，需要在界面显示和处理，则将这些信息封装成相应的消息对象，插入GUI显示的消息队列中，然后，由GUI 的主线程顺序处理，进行刷新，避免多线程操作图形界面所带来的不稳定因素。endprint

4 结束语

本文针对移动互联网环境下，误码率高、时延大的特点，设计了基于RS编码的文件传输软件，利用RS编码进行前向纠错，同时

结合重传机制，保证超出纠错范围的数据的可靠传输。实验结果表明，在高误码率、大时延情况下，该软件在文件传输的成功率和速度上明显优于传统的文件传输软件。该文中所涉及的文件传输协议和基于RS传输的相关技术同样可应用于其它无线环境下传输软件的设计。

参考文献：

[1] Holland G，Vaidya N.Analysis of TCP performance over mobile ad hoc networks[J].Wireless Networks，2002，8（2/3）： 275-288.

[2] Xylomenos G，Polyzos G C，Mahonen P，et al.TCP performance issues over wireless links[J].Communications Magazine，IEEE，2001，39（4）：52-58.

[3] Sundararajan J K，Shah D，Médard M，et al.Network coding meets TCP： Theory and implementation[J].Proceedings of the IEEE，2011，99（3）： 490-512.

[4] Juan L，Weimin G，Junke W，et al.Enhanced Network Coding for TCP in Wireless Networks[C].7th International Conference on Wireless Communications，Networking and Mobile Computing.Wuhan，China，2011：1-4.

[5] El Rakabawy S M，Lindemann C.A practical adaptive pacing scheme for TCP in multihop wireless networks[J].EEE ACM Trans.，Netw，2011， 19（4）：975-988.

[6] Dunaytsev R，Moltchanov D，Koucheryavy Y，et al.Modeling tcp sack performance over wireless channels with completely reliable arq/fec， Int. J. Communication Systems[J].2011，24（12）：1533-1564.

[7] Shin K，Kim J，Choi S B.Loss Recovery Scheme for TCP Using MAC MIB over Wireless Access Networks[J].IEEE Communications Letters， 2011，15（10）：1059-1061.

[8] Reed I S，Solomon G.Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics，1960， 8（2）：300-304.

[9] 罗象宏，舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展，2013，49（1）：1-11.

[10] 吴海佳，陈卫卫.基于RS 纠删码的信息分散算法[J].计算机应用，2010，30（12）：3197-3200.endprint

4 结束语

本文针对移动互联网环境下，误码率高、时延大的特点，设计了基于RS编码的文件传输软件，利用RS编码进行前向纠错，同时

结合重传机制，保证超出纠错范围的数据的可靠传输。实验结果表明，在高误码率、大时延情况下，该软件在文件传输的成功率和速度上明显优于传统的文件传输软件。该文中所涉及的文件传输协议和基于RS传输的相关技术同样可应用于其它无线环境下传输软件的设计。

参考文献：

[1] Holland G，Vaidya N.Analysis of TCP performance over mobile ad hoc networks[J].Wireless Networks，2002，8（2/3）： 275-288.

[2] Xylomenos G，Polyzos G C，Mahonen P，et al.TCP performance issues over wireless links[J].Communications Magazine，IEEE，2001，39（4）：52-58.

[3] Sundararajan J K，Shah D，Médard M，et al.Network coding meets TCP： Theory and implementation[J].Proceedings of the IEEE，2011，99（3）： 490-512.

[4] Juan L，Weimin G，Junke W，et al.Enhanced Network Coding for TCP in Wireless Networks[C].7th International Conference on Wireless Communications，Networking and Mobile Computing.Wuhan，China，2011：1-4.

[5] El Rakabawy S M，Lindemann C.A practical adaptive pacing scheme for TCP in multihop wireless networks[J].EEE ACM Trans.，Netw，2011， 19（4）：975-988.

[6] Dunaytsev R，Moltchanov D，Koucheryavy Y，et al.Modeling tcp sack performance over wireless channels with completely reliable arq/fec， Int. J. Communication Systems[J].2011，24（12）：1533-1564.

[7] Shin K，Kim J，Choi S B.Loss Recovery Scheme for TCP Using MAC MIB over Wireless Access Networks[J].IEEE Communications Letters， 2011，15（10）：1059-1061.

[8] Reed I S，Solomon G.Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics，1960， 8（2）：300-304.

[9] 罗象宏，舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展，2013，49（1）：1-11.

[10] 吴海佳，陈卫卫.基于RS 纠删码的信息分散算法[J].计算机应用，2010，30（12）：3197-3200.endprint

4 结束语

本文针对移动互联网环境下，误码率高、时延大的特点，设计了基于RS编码的文件传输软件，利用RS编码进行前向纠错，同时

结合重传机制，保证超出纠错范围的数据的可靠传输。实验结果表明，在高误码率、大时延情况下，该软件在文件传输的成功率和速度上明显优于传统的文件传输软件。该文中所涉及的文件传输协议和基于RS传输的相关技术同样可应用于其它无线环境下传输软件的设计。

参考文献：

[1] Holland G，Vaidya N.Analysis of TCP performance over mobile ad hoc networks[J].Wireless Networks，2002，8（2/3）： 275-288.

[2] Xylomenos G，Polyzos G C，Mahonen P，et al.TCP performance issues over wireless links[J].Communications Magazine，IEEE，2001，39（4）：52-58.

[3] Sundararajan J K，Shah D，Médard M，et al.Network coding meets TCP： Theory and implementation[J].Proceedings of the IEEE，2011，99（3）： 490-512.

[4] Juan L，Weimin G，Junke W，et al.Enhanced Network Coding for TCP in Wireless Networks[C].7th International Conference on Wireless Communications，Networking and Mobile Computing.Wuhan，China，2011：1-4.

[5] El Rakabawy S M，Lindemann C.A practical adaptive pacing scheme for TCP in multihop wireless networks[J].EEE ACM Trans.，Netw，2011， 19（4）：975-988.

[6] Dunaytsev R，Moltchanov D，Koucheryavy Y，et al.Modeling tcp sack performance over wireless channels with completely reliable arq/fec， Int. J. Communication Systems[J].2011，24（12）：1533-1564.

[7] Shin K，Kim J，Choi S B.Loss Recovery Scheme for TCP Using MAC MIB over Wireless Access Networks[J].IEEE Communications Letters， 2011，15（10）：1059-1061.

[8] Reed I S，Solomon G.Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics，1960， 8（2）：300-304.

[9] 罗象宏，舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展，2013，49（1）：1-11.

[10] 吴海佳，陈卫卫.基于RS 纠删码的信息分散算法[J].计算机应用，2010，30（12）：3197-3200.endprint