CCCN2010報告

混沌在網(wǎng)絡(luò)傳輸應(yīng)用層的數(shù)字噴泉編碼技術(shù)中的應(yīng)用/sundae_meng混沌簡介混沌是確定性非線性系統(tǒng)所表現(xiàn)的隨機行為的總稱它的軌道有界；但卻不是固定點，周期軌，極限環(huán)或是準(zhǔn)周期軌具有對初始條件敏感,內(nèi)隨機性，遍歷性等特征

出現(xiàn)在自然科學(xué)和社會科學(xué)的幾乎各個領(lǐng)域/sundae_meng數(shù)字噴泉碼產(chǎn)生的背景

數(shù)字噴泉碼實現(xiàn)的各個發(fā)展階段數(shù)字噴泉碼的研究現(xiàn)狀混沌在數(shù)字噴泉碼中的應(yīng)用研究的意義和主要工作混沌在數(shù)字噴泉碼中的應(yīng)用研究/sundae_meng數(shù)字噴泉碼產(chǎn)生的背景

因特網(wǎng)上數(shù)據(jù)的可靠傳輸已成為人們研究的一個熱點問題.

目前,大多數(shù)網(wǎng)絡(luò)通訊通過運用合適的通訊協(xié)議來保證傳輸?shù)目煽啃?例如TCP/IP協(xié)議TCP協(xié)議把數(shù)據(jù)處理成有序的數(shù)據(jù)包，并利用發(fā)送確認(rèn)信息和重傳丟失的數(shù)據(jù)包的方法來保證傳輸質(zhì)量。引發(fā)的問題：服務(wù)器的負(fù)荷過重,網(wǎng)絡(luò)擁塞，在有些情況下,網(wǎng)絡(luò)根本沒有發(fā)送反饋信息的條件,例如有些無線網(wǎng)絡(luò)和衛(wèi)星通訊網(wǎng)絡(luò)糾錯（刪）編碼技術(shù)（Erasurecoding）:利用冗余信息恢復(fù)丟失數(shù)據(jù)數(shù)字噴泉碼（DigitalFountainCodes）/sundae_meng什么是數(shù)字噴泉碼？數(shù)字噴泉碼的編碼方法可以由原始數(shù)據(jù)包生成任意數(shù)量的編碼包,而接收方只要收到其中任意m個編碼包,即可通過解碼以高概率成功恢復(fù)全部原始數(shù)據(jù)包。一般情況下,這里的m略大于k,k是原始數(shù)據(jù)的長度。

/sundae_meng數(shù)字噴泉碼的特點單向傳輸，不受丟包率影響，糾錯能力強快速編碼和解碼算法，具有線性編解碼復(fù)雜度的新型隨機編碼方式。與碼率無關(guān)，由原始數(shù)據(jù)包生成任意數(shù)量的編碼包支持異步接入，且與多種編碼技術(shù)和傳輸協(xié)議兼容應(yīng)用：多播，并行下載，視頻流，無線網(wǎng)絡(luò)等領(lǐng)域/sundae_meng數(shù)字噴泉碼的發(fā)展J.Byers,M.Luby[1]等人于1998年首次提出數(shù)字噴泉的概念,但當(dāng)時并沒有給出現(xiàn)實可行的噴泉碼設(shè)計方案。M.Luby、A.Shokrollahi等人聯(lián)合創(chuàng)立了DigitalFountain公司,以推廣數(shù)字噴泉概念的實際應(yīng)用。2002年,M.Luby[2]提出了第一種現(xiàn)實可行的噴泉碼——LT(Lubytransform)碼。在學(xué)術(shù)理論日漸完善的同時,噴泉碼也日益受到產(chǎn)業(yè)界的關(guān)注,獲得了越來越多的實際應(yīng)用。目前,一種由DigitalFountain公司設(shè)計的系統(tǒng)Raptor碼[3]已經(jīng)被DVB-H標(biāo)準(zhǔn)和3GPP組織的MBMS標(biāo)準(zhǔn)采用,并且正在參與其他多項國際標(biāo)準(zhǔn)的制定。/sundae_meng數(shù)字噴泉碼實現(xiàn)的各個階段Reed-Solomn(RS)碼：編碼在有限域上的操作限制了生成的編碼的數(shù)目；對于數(shù)目較大的k和m，其編碼算法的復(fù)雜性令人望而卻步Tornado碼（1998年）：從嚴(yán)格意義上講還不是數(shù)字噴泉碼，因為其每次編碼生成的包的數(shù)目是事先確定并固定不變的，這與噴泉碼的初衷相悖。但是它以其稀疏不規(guī)則隨機二分圖和以異或操作來定義邊的思想成為了后來的LT碼和Raptor碼的先驅(qū)。

LT碼（2002年）：M.Luby提出的LT碼是第一種實用的數(shù)字噴泉碼,具有簡單的編譯碼方法以及較小的解碼開銷和編解碼復(fù)雜度,為噴泉碼的進(jìn)一步發(fā)展奠定了基礎(chǔ)。Raptor碼（2006年）：A.Shokrollahi設(shè)計的Raptor碼是目前數(shù)字噴泉碼的最好的實現(xiàn)。生成每個編碼包需要的運算量是一個與k無關(guān)的常數(shù),而成功解碼m個編碼包獲得k個原始數(shù)據(jù)包需要的運算量是一個關(guān)于k的線性函數(shù)。/sundae_meng數(shù)字噴泉碼的研究現(xiàn)狀研究工作主要分為兩個方面：一方面致力于從理論上分析和提高噴泉碼的性能，例如：提出嚴(yán)格分析LT碼的模型[6]。設(shè)計了一種優(yōu)化算法的方法來尋找使LT碼性能最好的度分布[7]從解碼算法入手，利用接收到的編碼包所含的冗余信息，來提高LT碼的成功解碼概率

從理論上驗證了用偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的性能和理論上差別不大[9]分析在更現(xiàn)實的通信信道環(huán)境下，LT碼和Raptor碼的糾刪率與編碼包長度之間的依賴關(guān)系[10]。/sundae_meng數(shù)字噴泉碼的研究現(xiàn)狀（續(xù)）研究工作主要分為兩個方面：另一方面致力于數(shù)字噴泉碼的應(yīng)用研究

，例如：Raptorcodes在無線廣播系統(tǒng)中的可靠下載[12]和手機廣播網(wǎng)絡(luò)中的多媒體可靠下載[13]中的應(yīng)用

將基于數(shù)字噴泉碼的協(xié)議與基于TCP協(xié)議在擁塞情況下的通信效果進(jìn)行比較存儲系統(tǒng)[14],視頻編碼[15]，流媒體技術(shù)[16]，無線傳感網(wǎng)絡(luò)[17]等領(lǐng)域的應(yīng)用/sundae_meng混沌在數(shù)字噴泉碼中的應(yīng)用的研究意義和主要工作將混沌應(yīng)用到數(shù)字噴泉碼中是一個創(chuàng)新性的想法，目前還沒有這方面的研究工作。選題依據(jù)：目前數(shù)字噴泉碼的編碼實現(xiàn)過程中需要用到偽隨機數(shù)發(fā)生器來選擇編碼包的度和鄰居；混沌本身就是一種復(fù)雜的類似噪聲的行為，且具有如下特性：（1）時域上為類似隨機過程；（2）頻域上為寬帶非對稱連續(xù)譜；（3）對初始值的敏感依賴性；（4）具有分形結(jié)構(gòu)。混沌的這些特征非常適合用來設(shè)計形式簡單，性能好的偽隨機數(shù)發(fā)生器

因此，可以用混沌系統(tǒng)的這些特性來幫助確定編碼包的度和鄰居信息

/sundae_meng混沌在數(shù)字噴泉碼中的應(yīng)用的研究意義和主要工作（續(xù)）混沌在數(shù)字噴泉碼中的應(yīng)用的優(yōu)勢：混沌系統(tǒng)的遍歷性的特征，可以幫助編碼過程中的原始數(shù)據(jù)包以更均勻的概率被隨機選擇，使解碼的成功概率更高，減小解碼開銷。

由于混沌偽隨機數(shù)發(fā)生器形式簡單且生成的時間序列是確定性的，可使發(fā)送方在向接收方發(fā)送了混沌系統(tǒng)的方程和初始條件之后，通過接收雙方的同步，使接收方自動推算出接收到的各個編碼包的度和鄰居信息，這樣就不需要在編碼包中放入度和鄰居信息，尤其在原始數(shù)據(jù)包數(shù)目大的情況下，可以極大減少傳輸?shù)南?，提高信道容量的利用率。目前混沌加密的研究已有良好的基礎(chǔ)，如果將數(shù)字噴泉碼的混沌編碼和混沌加密巧妙的結(jié)合起來，就可以同時實現(xiàn)數(shù)據(jù)的可靠傳輸和保密通信。

/sundae_meng混沌在數(shù)字噴泉碼中的應(yīng)用的研究意義和主要工作研究工作將從形式簡單的LT碼的實現(xiàn)入手，以減少解碼開銷為目標(biāo)，選擇合適的混沌系統(tǒng)利用到LT碼的編碼過程中，在解碼過程中利用混沌減少解碼成功需要的編碼包的數(shù)目。/sundae_meng噴泉碼：一種迥異于TCP/IP的新穎的信道編碼技術(shù)；更可靠，更省時；丟包率更小

混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用發(fā)送方：像水龍頭

不需要區(qū)分各個接收者接收方：像杯子

不關(guān)心接包的順序，只關(guān)心接收的數(shù)據(jù)包的數(shù)目研究背景/sundae_meng混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用LT碼:第一種真正意義上的噴泉碼，現(xiàn)實可行,具有簡單的編譯碼方法以及較小的解碼開銷和編解碼復(fù)雜度編碼過程：LT碼的每個編碼包的生成步驟：（1）按照事先確定的度分布ρ(d)為該編碼包隨機抽樣選擇度d的值。（2）以均勻概率從構(gòu)成源文件的k個數(shù)據(jù)包中隨機選擇d個不同的包作為該編碼包的鄰居。（3）把這d個鄰居的值進(jìn)行異或操作，得到的值作為該編碼包的值。我們提出了基于Kent混沌映射的LT碼的編解碼算法，巧妙利用混沌序列的隨機性和遍歷性的特性來替代傳統(tǒng)的偽隨機數(shù)發(fā)生器，滿足LT碼編碼過程中對隨機的要求。/sundae_meng混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用一種基于混沌的LT碼的編解碼算法Kent混沌映射：LT碼的每個編碼包的生成步驟：（1）按照（2）以特點：（1）對初始條件非常敏感；（2）均勻一致分布/sundae_meng混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用一種基于混沌的LT碼的編解碼算法編碼算法原理（1）編碼包的度值的確定： 假設(shè)構(gòu)成源文件的輸入符號的數(shù)目為k，按照RobustSoliton度分布函數(shù)將(0,1)這個區(qū)間劃分成k個不重疊的長度不等的子區(qū)間，并且使每個子區(qū)間對應(yīng)一個度值j（1≤j≤k）。由于Kent混沌映射的時間序列的值在（0，1）區(qū)間內(nèi)均勻分布，因此該序列的每個值都會落在其中的某個子區(qū)間中，這個子區(qū)間對應(yīng)的度值就可作為一個編碼包的度值。（2）編碼包的鄰居的選取; 設(shè)已經(jīng)確定一編碼包的度值為d，我們?nèi)ent映射的一時間序列Y(n)（1≤n≤k），其長度應(yīng)為輸入符號構(gòu)成的輸入向量的長度，即輸入符號的數(shù)目k。找出序列Y(n)的前d個最大值，記錄它們在序列中的位置，那么輸入向量中與它們位置相同的d個輸入符號就作為該編碼包的d個鄰居。/sundae_meng混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用一種基于混沌的LT碼的編解碼算法/sundae_meng由偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的傳輸效率由混沌序列實現(xiàn)的LT碼的傳輸效率混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用仿真研究結(jié)果源文件長度k=1000源文件長度k=2000/sundae_meng混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用一種基于混沌的LT碼的編解碼算法仿真研究結(jié)果由偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的傳輸效率由混沌序列實現(xiàn)的LT碼的傳輸效率源文件長度k=5000源文件長度解碼低效率系數(shù)傳統(tǒng)偽隨機數(shù)發(fā)生器KENT混沌映射k=10001.1651.095k=20001.1151.079k=50001.0871.065/sundae_meng提出了一種基于混沌的LT碼的編解碼算法，巧妙使用了混沌序列的隨機性，遍歷性特征為編碼包選擇度值和鄰居。仿真結(jié)果發(fā)現(xiàn)在編碼中使用混沌序列替代傳統(tǒng)的偽隨機數(shù)發(fā)生器能夠提高LT碼的傳輸效率。并且基于混沌的LT碼能夠使發(fā)送方和接收方更方便有效的通信編碼包的度和鄰居信息，減小傳輸消耗?；煦缭跀?shù)字噴泉編碼技術(shù)中的應(yīng)用一種基于混沌的LT碼的編解碼算法結(jié)論：/sundae_meng在改進(jìn)的RobustSoliton分布中，我們將原度分布中的ρ(i)和τ(i)結(jié)合起來，并取消了允許失敗概率參數(shù)δ。依據(jù)是在仿真研