译码移动互联网下基于RS编码的文件传输软件设计体系建设

移动互联网下基于RS编码的文件传输软件设计体系建设

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

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

针对上述问题提出了多种解决方法常见的方法是对TCP进行优化如TCP网络编码[3-4]、改进拥塞控制[5-7] 。

上述方法的优点是对上层应用透明无需修改即可使用。缺点是需要修改TCP协议栈 由于协议栈与操作系统是紧密结合的。而移动互联网中各种节点上所运行的操作系统型号和版本各不相同需要针对每种系统进行专门的优化从应用的角度来说上述方案可行性较低。

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

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

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 列的矩阵D 1  n这就是编码过程见式1  。其中Mmn称为生成矩阵它满足这样的一个特性 由该矩阵的任意m 列数据所组成的m*m的方阵M’mm都存在逆矩阵M’-1mm。由编码的过程可以得到下面的公式1  对于方阵M’mm 由式1  可以得到式2 依然成立。又根据生成矩阵的定义对任意的M’mm都存在逆矩阵M’-1mm因此可以得到式3 。由于D1 m是任选的因此式3 即译码过程对于最终剩余的编码数据只要个数大于m个即可从中选择m个组成D1  m 同时选择m个数据在生成矩阵中对应的列组成方阵M’mm计算逆矩阵M’-1m m再运用式1  按照固定的大小对待发送的文件进行分割划分的每个单元称为1个Block每个Block的大小不超过网络的MTU这样做的目的是防止Block在数据链路层进行分片由于分片的传输没有重传机制因此任意一个分片的丢失都会导致上层Block的传输失败需要重传整个Block数据

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

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多线程任务处理框架

按照设计需求传输软件需要支持多任务并行处理包括同时支持发送任务和接收任务 以及多个发送任务或多个

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

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 Mag azi ne IEEE 2001  39 4  52-58.

[3]Sundararaj an J K Shah DMédard M et al.Network coding meets TCP Theory and implementation[J].Proceedings

of the IEEE 201 1  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 201 1  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 201 1  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].201 1  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 201 1  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-1 1.