移動(dòng)互聯(lián)網(wǎng)下基于RS編碼的文件傳輸軟件設(shè)計(jì)與實(shí)現(xiàn)

文艾

摘要：針對移動(dòng)互聯(lián)網(wǎng)環(huán)境下，基于TCP的文件傳輸軟件效率較低的問題，設(shè)計(jì)并實(shí)現(xiàn)了基于RS（Reed-Solomon）編碼的文件傳輸軟件。該軟件基于UDP協(xié)議，利用RS編碼的特性實(shí)現(xiàn)文件分塊傳輸?shù)那跋蚣m錯(cuò)，可容忍一定范圍內(nèi)的數(shù)據(jù)丟失，無需重傳，可有效減少交互開銷，對超出糾錯(cuò)范圍的分片數(shù)據(jù)，利用重傳機(jī)制，保證可靠傳輸。實(shí)驗(yàn)結(jié)果表明，在高誤碼率，大時(shí)延情況下，該軟件的傳輸性能（成功率、傳輸速率）相對傳統(tǒng)的文件傳輸軟件顯著提升。

關(guān)鍵詞：RS編碼；文件傳輸；移動(dòng)互聯(lián)網(wǎng)

中圖分類號：TP393.093 文獻(xiàn)標(biāo)識碼：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

文件傳輸是一項(xiàng)非常重要的網(wǎng)絡(luò)應(yīng)用。傳統(tǒng)的文件傳輸軟件，如FTP等，通常采用TCP協(xié)議，TCP是面向連接的運(yùn)輸層協(xié)議，它可以實(shí)現(xiàn)數(shù)據(jù)的按序、可靠傳輸。TCP最初是針對有線網(wǎng)絡(luò)設(shè)計(jì)的，該網(wǎng)絡(luò)的特點(diǎn)是：低時(shí)延、低誤碼率。而在移動(dòng)互聯(lián)網(wǎng)環(huán)境下，情形相反，大時(shí)延，高誤碼率是其特點(diǎn)。TCP原有的一些設(shè)計(jì)并不能很好地適應(yīng)這一新的網(wǎng)絡(luò)環(huán)境，導(dǎo)致效率低下。其中，TCP協(xié)議的重傳機(jī)制和擁塞控制機(jī)制是導(dǎo)致其在移動(dòng)互聯(lián)網(wǎng)環(huán)境下效率低下的兩個(gè)主要原因，分析如下。

首先，TCP協(xié)議使用重傳機(jī)制來實(shí)現(xiàn)數(shù)據(jù)的可靠傳輸。TCP會自動(dòng)對發(fā)送方所發(fā)出的數(shù)據(jù)進(jìn)行編號，并且啟動(dòng)計(jì)時(shí)器，如果在規(guī)定的時(shí)間內(nèi)，未收到接收方對該數(shù)據(jù)的ACK，便會觸發(fā)計(jì)時(shí)器，自動(dòng)重發(fā)數(shù)據(jù)。如果重傳次數(shù)超過系統(tǒng)所設(shè)定的閾值，TCP協(xié)議棧會向上層報(bào)告?zhèn)鬏斒?。對于一次成功的?shù)據(jù)傳輸，包括數(shù)據(jù)發(fā)送和ACK成功兩個(gè)部分，缺一不可。對于傳統(tǒng)的有線網(wǎng)絡(luò)來說，收發(fā)雙方的信道質(zhì)量是有保證的。而對于移動(dòng)互聯(lián)網(wǎng)，由于處在無線環(huán)境下，其誤碼率大大高于有線環(huán)境，甚至還會存在信道不對稱的情況。TCP的重傳機(jī)制，會顯著增加交互開銷，從而降低數(shù)據(jù)傳輸?shù)某晒Ω怕屎退俾省?/p>

其次，傳統(tǒng)的TCP協(xié)議會將傳輸中所遇到的丟包和時(shí)延增大作為網(wǎng)絡(luò)擁塞的主要判據(jù)，這在傳統(tǒng)的有線網(wǎng)絡(luò)中，是沒有問題的。但是，在移動(dòng)互聯(lián)網(wǎng)環(huán)境下，時(shí)延和誤碼率受多種因素的影響，如信道質(zhì)量、干擾、以及移動(dòng)速率等。大多數(shù)情況下，出現(xiàn)丟包或者時(shí)延增大，并不是因?yàn)槌霈F(xiàn)了網(wǎng)絡(luò)擁塞。由于TCP協(xié)議誤判，從而啟動(dòng)擁塞控制，通常的做法是，將原有的發(fā)送窗口縮小一半，由于此時(shí)網(wǎng)絡(luò)并未真正擁塞，因此，降低速率并不會改善當(dāng)前狀況，問題依舊，然而，TCP協(xié)議會繼續(xù)誤判，認(rèn)為擁塞非常嚴(yán)重，再次降低一半的發(fā)送速率，如此循環(huán)，導(dǎo)致在移動(dòng)互聯(lián)網(wǎng)環(huán)境下，TCP的性能下降非常明顯[1-2]。

針對上述問題，提出了多種解決方法，常見的方法是對TCP進(jìn)行優(yōu)化，如TCP網(wǎng)絡(luò)編碼[3-4]、改進(jìn)擁塞控制[5-7]。上述方法的優(yōu)點(diǎn)是，對上層應(yīng)用透明，無需修改，即可使用。缺點(diǎn)是，需要修改TCP協(xié)議棧，由于協(xié)議棧與操作系統(tǒng)是緊密結(jié)合的。而移動(dòng)互聯(lián)網(wǎng)中，各種節(jié)點(diǎn)上所運(yùn)行的操作系統(tǒng)型號和版本各不相同，需要針對每種系統(tǒng)進(jìn)行專門的優(yōu)化，從應(yīng)用的角度來說，上述方案可行性較低。

為此，該文設(shè)計(jì)并實(shí)現(xiàn)了基于RS編碼的文件傳輸軟件。該軟件基于UDP協(xié)議，利用RS編碼的特性實(shí)現(xiàn)文件分塊傳輸?shù)那跋蚣m錯(cuò)，可容忍一定范圍內(nèi)的數(shù)據(jù)丟失，無需重傳，可有效減少交互開銷，對超出糾錯(cuò)范圍的分片數(shù)據(jù)，利用重傳機(jī)制，保證可靠傳輸。它具有如下優(yōu)點(diǎn)：首先，根除了TCP擁塞誤判所帶來的性能下降；其次，利用RS編碼進(jìn)行前向糾錯(cuò)，可有效降低交互開銷；最后，軟件獨(dú)立于操作系統(tǒng)，無需修改協(xié)議棧，可行性高。實(shí)驗(yàn)結(jié)果表明，在高誤碼率，大時(shí)延情況下，該軟件的傳輸速率明顯高于傳統(tǒng)的文件傳輸軟件。

1 基于RS編碼的容錯(cuò)傳輸機(jī)制endprint

1.1 RS編碼原理

RS編碼是一種常見的糾刪碼，它由Reed I S， Solomon G于1960年提出[8]。RS算法的基本原理是，通過對原始的m個(gè)數(shù)據(jù)，進(jìn)行編碼，得到n個(gè)數(shù)據(jù)，n>m，對于n個(gè)編碼數(shù)據(jù)，取其中任意的m個(gè)數(shù)據(jù)，通過譯碼操作，均可恢復(fù)出m個(gè)原始數(shù)據(jù)[9-10]，示意圖如下所示（基于RS糾刪碼的信息分散算法）。

RS算法的關(guān)鍵編碼和譯碼過程實(shí)際上是一個(gè)矩陣的運(yùn)算過程。假設(shè)原始數(shù)據(jù)為m個(gè)，則可以視為1行m列的矩陣S1，m，與一個(gè)m行n列的矩陣Mm，n相乘，最后的結(jié)果為1行n列的矩陣D1，n，這就是編碼過程，見式（1） 。其中，Mm，n稱為生成矩陣，它滿足這樣的一個(gè)特性，由該矩陣的任意m列數(shù)據(jù)所組成的m*m的方陣Mm，m都存在逆矩陣M-1m，m。由編碼的過程，可以得到下面的公式（1） ，對于方陣Mm，m，由式（1） 可以得到式（2） 依然成立。又根據(jù)生成矩陣的定義，對任意的Mm，m都存在逆矩陣M-1m，m，因此，可以得到式（3） 。由于D1，m是任選的，因此，式（3） 即譯碼過程，對于最終剩余的編碼數(shù)據(jù)，只要個(gè)數(shù)大于m個(gè)，即可從中選擇m個(gè)組成D1，m，同時(shí)選擇m個(gè)數(shù)據(jù)在生成矩陣中對應(yīng)的列，組成方陣Mm，m，計(jì)算逆矩陣M-1m，m，再運(yùn)用式1） 按照固定的大小對待發(fā)送的文件進(jìn)行分割，劃分的每個(gè)單元稱為1個(gè)Block，每個(gè)Block的大小不超過網(wǎng)絡(luò)的MTU，這樣做的目的是防止Block在數(shù)據(jù)鏈路層進(jìn)行分片，由于分片的傳輸沒有重傳機(jī)制，因此，任意一個(gè)分片的丟失，都會導(dǎo)致上層Block的傳輸失敗，需要重傳整個(gè)Block數(shù)據(jù)；

2） 按序?qū)lock進(jìn)行分組，每組Block就是一個(gè)編碼的基本單元，假設(shè)一組Block的數(shù)量為m，m的值可以由上層指定，默認(rèn)為4，編碼后的Block數(shù)量為n，默認(rèn)為6；

3） 確定需要編碼的Block組號，如果該組已編碼，則直接進(jìn)入發(fā)送模塊，進(jìn)行發(fā)送，如果未編碼，則調(diào)用編碼函數(shù)，對該組數(shù)據(jù)進(jìn)行編碼，然后進(jìn)入發(fā)送模塊；

4） 發(fā)送模塊檢查當(dāng)前待發(fā)送的Block組，根據(jù)每個(gè)Block的接收情況，確定組內(nèi)需要發(fā)送的Block，需要考慮兩種情況，一種是該組Block未發(fā)送，那么直接按序發(fā)送組內(nèi)所有Block；第二種情況是，該組Block已發(fā)送，且有部分Block已接收，但不滿足譯碼條件，此時(shí)，需要計(jì)算要達(dá)到譯碼條件還需要繼續(xù)發(fā)送的Block數(shù)，并在此基礎(chǔ)上加1，例如，在m=4，n=8的情況下，已經(jīng)收到2個(gè)Block，那么可以計(jì)算出還需要譯碼還需要4-2=2個(gè)Block，在此基礎(chǔ)上再增加1，那么此次發(fā)送3個(gè)Block，只需要收到其中任意2個(gè)，即可譯碼，至于待發(fā)送的3個(gè)Block，則從未收到的8-2=6個(gè)Block中任意挑選即可；

5） 發(fā)送模塊發(fā)送完若干組Block數(shù)據(jù)后，會等待接收方的ACK回饋，同時(shí)啟動(dòng)定時(shí)器。如果超時(shí)，則會跳到3） 重新計(jì)算分片序列，重新發(fā)送。如果接收到ACK，清除定時(shí)器，ACK會包含已收到各組Block 的情況，如果接收的Block均已滿足譯碼條件，則再看該文件的所有數(shù)據(jù)是否發(fā)送完畢，如果是，則結(jié)束，如果未完成，則跳至3） 。如果該組Block不滿足譯碼條件，則跳至3） 繼續(xù)發(fā)送。

接收方流程：

1） 在指定端口監(jiān)聽，接收Block組；

2） 向發(fā)送方發(fā)送Block接收的ACK；

3） 計(jì)算已接收的Block組是否滿足譯碼條件，如果不滿足，跳至1） ，如果滿足，則跳至4） ；

4） 對Block組進(jìn)行譯碼，根據(jù)相應(yīng)的信息，將譯碼得出的Block寫入文件對應(yīng)的偏移處；

5） 判斷文件接收是否完畢，如果是，則退出，如果否，則跳至1） ，繼續(xù)接收。

1.3 性能分析

與TCP重傳機(jī)制相比，采用RS編碼的容錯(cuò)傳輸機(jī)制可以有效提升數(shù)據(jù)發(fā)送的成功概率。假設(shè)Block在發(fā)送過程中成功率為p，待傳輸?shù)腂lock數(shù)為m，編碼后的Block數(shù)為n（n>m），為簡化模型，不考慮接收方到發(fā)送方信道質(zhì)量的影響，即發(fā)送方總能收到ACK。RS編碼譯碼模塊是RS算法的實(shí)現(xiàn)模塊，向上提供以字節(jié)為單位的RS編碼和譯碼接口。生成矩陣的構(gòu)建是RS算法實(shí)現(xiàn)的一個(gè)關(guān)鍵，常用的是范德蒙矩陣和柯西矩陣。由于柯西矩陣的特性，譯碼時(shí)，對于原始的數(shù)據(jù)，無需譯碼，因此相對范德蒙矩陣效率高。此外，不管是范德蒙矩陣，還是柯西矩陣，在進(jìn)行譯碼時(shí)，都需要進(jìn)行矩陣的逆運(yùn)算，由于實(shí)數(shù)域的運(yùn)算都將存在無法整除的可能，因此，將矩陣的運(yùn)算轉(zhuǎn)移到伽羅華域，在進(jìn)行編碼和譯碼時(shí)都采用伽羅華域的運(yùn)算，一次編碼和一次譯碼，正好實(shí)現(xiàn)最終的數(shù)據(jù)回歸到實(shí)數(shù)域，此外，伽羅華域的運(yùn)算還將實(shí)數(shù)域的加法轉(zhuǎn)換為異或、乘法轉(zhuǎn)換為加、除法轉(zhuǎn)換為減，轉(zhuǎn)換后的運(yùn)算非常適合在計(jì)算機(jī)上進(jìn)行優(yōu)化，從而提高效率。

異常處理模塊主要是對程序中所遇到的各種異常情況進(jìn)行進(jìn)行分類、分級的處理，并且寫入相應(yīng)的日志信息。

2.2 多線程任務(wù)處理框架

按照設(shè)計(jì)需求，傳輸軟件需要支持多任務(wù)并行處理，包括同時(shí)支持發(fā)送任務(wù)和接收任務(wù)，以及多個(gè)發(fā)送任務(wù)或多個(gè)接收任務(wù)，且任務(wù)的執(zhí)行、操作、狀態(tài)顯示三者都需要并行處理。這就要求，軟件必須支持任務(wù)的異步執(zhí)行，而且，底層傳輸任務(wù)的處理與界面的顯示和操作之間要有良好的處理接口。為此，設(shè)計(jì)了基于任務(wù)隊(duì)列的多線程處理框架來解決上述問題。

該框架包括消息隊(duì)列、任務(wù)隊(duì)列、以及調(diào)度線程、發(fā)送線程、接收線程等構(gòu)件。其中，用戶通過任務(wù)界面將發(fā)送任務(wù)或其它操作提交到任務(wù)隊(duì)列，然后立即返回，定義專門的任務(wù)結(jié)構(gòu)來保存用戶提交的操作，調(diào)度線程負(fù)責(zé)從任務(wù)隊(duì)列的首部取節(jié)點(diǎn)，根據(jù)任務(wù)的類型，啟動(dòng)不同處理線程進(jìn)行操作，其中發(fā)送線程和接收線程的可以根據(jù)需要設(shè)定為多個(gè)，從而支持多任務(wù)并行處理。此外，對于底層線程在處理過程中的各種信息，如任務(wù)的執(zhí)行的狀態(tài)，傳輸速度等，需要在界面顯示和處理，則將這些信息封裝成相應(yīng)的消息對象，插入GUI顯示的消息隊(duì)列中，然后，由GUI 的主線程順序處理，進(jìn)行刷新，避免多線程操作圖形界面所帶來的不穩(wěn)定因素。endprint

4 結(jié)束語

本文針對移動(dòng)互聯(lián)網(wǎng)環(huán)境下，誤碼率高、時(shí)延大的特點(diǎn)，設(shè)計(jì)了基于RS編碼的文件傳輸軟件，利用RS編碼進(jìn)行前向糾錯(cuò)，同時(shí)

結(jié)合重傳機(jī)制，保證超出糾錯(cuò)范圍的數(shù)據(jù)的可靠傳輸。實(shí)驗(yàn)結(jié)果表明，在高誤碼率、大時(shí)延情況下，該軟件在文件傳輸?shù)某晒β屎退俣壬厦黠@優(yōu)于傳統(tǒng)的文件傳輸軟件。該文中所涉及的文件傳輸協(xié)議和基于RS傳輸?shù)南嚓P(guān)技術(shù)同樣可應(yīng)用于其它無線環(huán)境下傳輸軟件的設(shè)計(jì)。

參考文獻(xiàn)：

[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] 羅象宏，舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展，2013，49（1）：1-11.

[10] 吳海佳，陳衛(wèi)衛(wèi).基于RS 糾刪碼的信息分散算法[J].計(jì)算機(jī)應(yīng)用，2010，30（12）：3197-3200.endprint

4 結(jié)束語

本文針對移動(dòng)互聯(lián)網(wǎng)環(huán)境下，誤碼率高、時(shí)延大的特點(diǎn)，設(shè)計(jì)了基于RS編碼的文件傳輸軟件，利用RS編碼進(jìn)行前向糾錯(cuò)，同時(shí)

結(jié)合重傳機(jī)制，保證超出糾錯(cuò)范圍的數(shù)據(jù)的可靠傳輸。實(shí)驗(yàn)結(jié)果表明，在高誤碼率、大時(shí)延情況下，該軟件在文件傳輸?shù)某晒β屎退俣壬厦黠@優(yōu)于傳統(tǒng)的文件傳輸軟件。該文中所涉及的文件傳輸協(xié)議和基于RS傳輸?shù)南嚓P(guān)技術(shù)同樣可應(yīng)用于其它無線環(huán)境下傳輸軟件的設(shè)計(jì)。

參考文獻(xiàn)：

[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] 羅象宏，舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展，2013，49（1）：1-11.

[10] 吳海佳，陳衛(wèi)衛(wèi).基于RS 糾刪碼的信息分散算法[J].計(jì)算機(jī)應(yīng)用，2010，30（12）：3197-3200.endprint

4 結(jié)束語

本文針對移動(dòng)互聯(lián)網(wǎng)環(huán)境下，誤碼率高、時(shí)延大的特點(diǎn)，設(shè)計(jì)了基于RS編碼的文件傳輸軟件，利用RS編碼進(jìn)行前向糾錯(cuò)，同時(shí)

結(jié)合重傳機(jī)制，保證超出糾錯(cuò)范圍的數(shù)據(jù)的可靠傳輸。實(shí)驗(yàn)結(jié)果表明，在高誤碼率、大時(shí)延情況下，該軟件在文件傳輸?shù)某晒β屎退俣壬厦黠@優(yōu)于傳統(tǒng)的文件傳輸軟件。該文中所涉及的文件傳輸協(xié)議和基于RS傳輸?shù)南嚓P(guān)技術(shù)同樣可應(yīng)用于其它無線環(huán)境下傳輸軟件的設(shè)計(jì)。

參考文獻(xiàn)：

[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] 羅象宏，舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展，2013，49（1）：1-11.

[10] 吳海佳，陳衛(wèi)衛(wèi).基于RS 糾刪碼的信息分散算法[J].計(jì)算機(jī)應(yīng)用，2010，30（12）：3197-3200.endprint