CCCN2010報告混沌在網(wǎng)絡(luò)傳輸應(yīng)用層的數(shù)字噴泉編碼技術(shù)中的應(yīng)用

1、,CCCN2010報告混沌在網(wǎng)絡(luò)傳輸應(yīng)用層的數(shù)字噴泉編碼技術(shù)中的應(yīng)用,報告人：陳增強 單位：南開大學 2010年10月,混 沌 簡 介,混沌是確定性非線性系統(tǒng)所表現(xiàn)的隨機行為的總稱 它的軌道有界；但卻不是固定點，周期軌，極限環(huán)或是準周期軌 具有對初始條件敏感,內(nèi)隨機性，遍歷性等特征 出現(xiàn)在自然科學和社會科學的幾乎各個領(lǐng)域,數(shù)字噴泉碼產(chǎn)生的背景 數(shù)字噴泉碼實現(xiàn)的各個發(fā)展階段 數(shù)字噴泉碼的研究現(xiàn)狀 混沌在數(shù)字噴泉碼中的應(yīng)用研究的意義和主要工作,混沌在數(shù)字噴泉碼中的應(yīng)用研究,數(shù)字噴泉碼產(chǎn)生的背景,因特網(wǎng)上數(shù)據(jù)的可靠傳輸已成為人們研究的一個熱點問題. 目前, 大多數(shù)網(wǎng)絡(luò)通訊通過運用合適的通訊協(xié)議來保證

2、傳輸?shù)目煽啃? 例如TCP/IP協(xié)議 TCP協(xié)議把數(shù)據(jù)處理成有序的數(shù)據(jù)包，并利用發(fā)送確認信息和重傳丟失的數(shù)據(jù)包的方法來保證傳輸質(zhì)量。 引發(fā)的問題：服務(wù)器的負荷過重, 網(wǎng)絡(luò)擁塞，在有些情況下, 網(wǎng)絡(luò)根本沒有發(fā)送反饋信息的條件, 例如有些無線網(wǎng)絡(luò)和衛(wèi)星通訊網(wǎng)絡(luò),什么是數(shù)字噴泉碼？,數(shù)字噴泉碼的編碼方法可以由原始數(shù)據(jù)包生成任意數(shù)量的編碼包, 而接收方只要收到其中任意 m 個編碼包, 即可通過解碼以高概率成功恢復(fù)全部原始數(shù)據(jù)包。一般情況下, 這里的 m 略大于 k , k是原始數(shù)據(jù)的長度。,數(shù)字噴泉碼的特點,單向傳輸，不受丟包率影響，糾錯能力強 快速編碼和解碼算法，具有線性編解碼復(fù)雜度的新型隨機編碼方

3、式。 與碼率無關(guān) ，由原始數(shù)據(jù)包生成任意數(shù)量的編碼包 支持異步接入，且與多種編碼技術(shù)和傳輸協(xié)議兼容,應(yīng)用：多播，并行下載，視頻流，無線網(wǎng)絡(luò)等領(lǐng)域,數(shù)字噴泉碼的發(fā)展,J. Byers, M. Luby 1等人于1998 年首次提出數(shù)字噴泉的概念, 但當時并沒有給出現(xiàn)實可行的噴泉碼設(shè)計方案。 M. Luby、A. Shokrollahi 等人聯(lián)合創(chuàng)立了Digital Fountain 公司, 以推廣數(shù)字噴泉概念的實際應(yīng)用。,2002 年, M. Luby 2 提出了第一種現(xiàn)實可行的噴泉碼LT (Luby transform) 碼。在學術(shù)理論日漸完善的同時, 噴泉碼也日益受到產(chǎn)業(yè)界的關(guān)注, 獲得了越

4、來越多的實際應(yīng)用。,目前, 一種由Digital Fountain 公司設(shè)計的系統(tǒng)Raptor 碼 3 已經(jīng)被DVB- H 標準和3GPP 組織的 MBMS 標準采用, 并且正在參與其他多項國際標準的制定。,數(shù)字噴泉碼實現(xiàn)的各個階段,Reed-Solomn (RS)碼：編碼在有限域上的操作限制了生成的編碼的數(shù)目；對于數(shù)目較大的 k 和 m，其編碼算法的復(fù)雜性令人望而卻步,Tornado 碼（1998年）：從嚴格意義上講還不是數(shù)字噴泉碼，因為其每次編碼生成的包的數(shù)目是事先確定并固定不變的，這與噴泉碼的初衷相悖。但是它以其稀疏不規(guī)則隨機二分圖和以異或操作來定義邊的思想成為了后來的 LT 碼和Rap

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

6、算法的方法來尋找使LT碼性能最好的度分布7 從解碼算法入手，利用接收到的編碼包所含的冗余信息，來提高LT碼的成功解碼概率 從理論上驗證了用偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的性能和理論上差別不大9 分析在更現(xiàn)實的通信信道環(huán)境下，LT碼和Raptor碼的糾刪率與編碼包長度之間的依賴關(guān)系10 。,數(shù)字噴泉碼的研究現(xiàn)狀（續(xù)）,研究工作主要分為兩個方面：,另一方面致力于數(shù)字噴泉碼的應(yīng)用研究 ，例如： Raptor codes在無線廣播系統(tǒng)中的可靠下載12和手機廣播網(wǎng)絡(luò)中的多媒體可靠下載13中的應(yīng)用 將基于數(shù)字噴泉碼的協(xié)議與基于TCP協(xié)議在擁塞情況下的通信效果進行比較 存儲系統(tǒng)14, 視頻編碼15，流媒體技術(shù)1

7、6，無線傳感網(wǎng)絡(luò)17等領(lǐng)域的應(yīng)用,混沌在數(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)的這些特性來幫助確定編碼包的度和鄰居信息,混沌在數(shù)字噴泉碼中的應(yīng)用的研究意義和主要工作（續(xù)）,混沌在數(shù)字噴泉碼

8、中的應(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ù)的可靠傳輸和保密通信。,混沌在數(shù)字噴泉碼中的應(yīng)用的研究

9、意義和主要工作,研究工作將從形式簡單的LT碼的實現(xiàn)入手，以減少解碼開銷為目標，選擇合適的混沌系統(tǒng)利用到LT碼的編碼過程中，在解碼過程中利用混沌減少解碼成功需要的編碼包的數(shù)目。,噴泉碼：一種迥異于TCP/IP的新穎的信道編碼技術(shù)；更可靠，更省時；丟包率更小,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,發(fā)送方：像水龍頭 不需要區(qū)分各個接收者 接收方：像杯子 不關(guān)心接包的順序，只關(guān)心接收的數(shù)據(jù)包的數(shù)目,研究背景,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,LT碼: 第一種真正意義上的噴泉碼，現(xiàn)實可行,具有簡單的編譯碼方法以及較小的解碼開銷和編解碼復(fù)雜度,編碼過程：,LT 碼的每個編碼包的生成步驟： （1）按照事先確定的度分

10、布(d) 為該編碼包隨機抽樣選擇度d的值。 （2）以均勻概率從構(gòu)成源文件的k個數(shù)據(jù)包中隨機選擇d個不同的包作為該編碼包的鄰居。 （3）把這d個鄰居的值進行異或操作，得到的值作為該編碼包的值。,我們提出了基于Kent 混沌映射的LT 碼的編解碼算法，巧妙利用混沌序列的隨機性和遍歷性的特性來替代傳統(tǒng)的偽隨機數(shù)發(fā)生器，滿足LT 碼編碼過程中對隨機的要求。,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,一種基于混沌的LT碼的編解碼算法,Kent 混沌映射：,LT 碼的每個編碼包的生成步驟： （1）按照 （2）以,特點：（1）對初始條件非常敏感； （2）均勻一致分布,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,一種基于混沌的LT

11、碼的編解碼算法,編碼算法原理,（1）編碼包的度值的確定： 假設(shè)構(gòu)成源文件的輸入符號的數(shù)目為k ，按照Robust Soliton 度分布函數(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)

12、的前d 個最大值，記錄它們在序列中的位置，那么輸入向量中與它們位置相同的d 個輸入符號就作為該編碼包的d 個鄰居。,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,一種基于混沌的LT碼的編解碼算法,由偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的傳輸效率,由混沌序列實現(xiàn)的LT碼的傳輸效率,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,仿真研究結(jié)果,源文件長度k=1000,源文件長度k=2000,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,一種基于混沌的LT碼的編解碼算法,仿真研究結(jié)果,由偽隨機數(shù)發(fā)生器實現(xiàn)的LT碼的傳輸效率,由混沌序列實現(xiàn)的LT碼的傳輸效率,源文件長度k=5000,提出了一種基于混沌的LT碼的編解碼算法，巧妙使用了混沌序列的隨機性，遍歷性特征為編碼包選擇度值和鄰居。 仿真結(jié)果發(fā)現(xiàn)在編碼中使用混沌序列替代傳統(tǒng)的偽隨機數(shù)發(fā)生器能夠提高LT碼的傳輸效率。 并且基于混沌的LT碼能夠使發(fā)送方和接收方更方便有效的通信編碼包的度和鄰居信息，減小傳輸消耗。,混沌在數(shù)字噴泉編碼技術(shù)中的應(yīng)用,一種基于混沌的LT碼的編解碼算法,結(jié)論：,在改進的Robust Soliton 分布中，我們將原度分布中的(i) 和(i) 結(jié)合起來，并取消了允許失敗概率參數(shù)。依據(jù)是在仿真研究