一種二進位刪除信道下的噴泉碼方法
2023-08-13 02:38:06
一種二進位刪除信道下的噴泉碼方法
【專利摘要】本發明是一種二進位刪除信道下的噴泉碼方法：它對原始數據流進行基礎LT碼預編碼；將編碼數據流進行分割處理，按需要分成數個支信息流；對每個支信息流進行基礎LT碼編碼；按預先制定好的路由方案發送各支路信息流；在解碼端用最大似然法解碼最先到達的支信息流；將經過編譯的支信號流按原分割方案進行重組；對重組信息流進行最大似然解碼法編譯，得到原始數據流，完成了對原始數據的正確完整編譯。其方法設計合理，它能基本達到信息傳輸時機密性、完整性、可用性，也可以保證解碼方的正確解碼。本發明為信息的安全傳輸奠定了基礎，對編碼理論、網絡信息安全架構建設具有重大意義。
【專利說明】一種二進位刪除信道下的噴泉碼方法
【技術領域】
[0001]本發明屬於編碼領域，具體地說是涉及一種改進的二進位刪除信道下噴泉碼的編解碼方法。
【背景技術】
[0002]隨著網際網路及其應用的快速發展，近年來政府、軍事以及民用信息的安全傳遞越發重要。安全信息傳輸要求信息安全三要素一機密性、完整性和可用性之間相互平衡，達到網絡資源的最佳分配，提供必要的網絡彈性。網絡的彈性通常經由網絡節點、鏈路的冗餘，信息重新傳輸，數據的複製，多樣性來實現，需要犧牲某些資源來達到最佳網絡彈性，使得網絡在受到自然影響、不確定幹擾、甚至蓄意破壞的情況下仍能維持一定質量的服務，同時完成信息安全三要素之間的平衡。
[0003]如何通過對信息進行加密編碼，使之在無線或有線網絡信道受到潛在竊聽、信道損壞、信道不穩定的情況下中進行安全傳輸，已成為近年來的熱門研究課題。目前，已有多種編碼手段已得到了理論證明和實驗考證，實現了一定程度上信息安全的保障。例如，參考文獻題目為 Protecting Network Coded Packets in Coalition Networks (該文作者是:Soon Y.0h和Mario Gerla，洛杉磯加利福尼亞大學計算機科學學院，2010年出版在 Wireless On-demand Network Systems and Services (WONS), 2010 SeventhInternational Conference),文獻闡述了如何利用網絡編碼實現對傳輸過程中各節點的控制，在網絡節點不可信任度高達50%、並且信道因遭受不穩定、損壞和堵塞而產生錯誤傳輸的嚴峻情況下提高正確傳輸成功率；參考文獻題目為Wireless Information-TheoreticSecurity(該文作者是:Matthieu Bloch, Joao Barros,Miguel R.D.Rodrigues和Stevenff.McLaughlin, 2008 年出版在期刊:IEEE Transactions on Information Theory),文中提出了根據衰減信道震蕩情況產生密鑰，在傳統通訊系統中添加一層新的加密層，使得單方向數據傳輸可以在準靜態無線信道中得到安全保證，雖然此法可以在很大的SNR範圍內提供絕對安全傳輸，但其算法繁複、對存儲的要求非常高；參考文獻題目為Secrecy andReliability Using Raptor Codes in the Presence of a Wiretapper in Multiple PathWireless Network,(該文作者是:Anna Kacewicz 和 Stephen B.Wicker, 2009 年出版在IEEE),根據信道的擦除概率和所用LT編碼數據，計算出可糾正的擦出概率，從而制定相應的路由方案；參考文獻題目為Raptor Codes(該文作者是:Amin Shokrollahi and MichaelLuby, 2009 年發表於 Foundations and Trends in Communications and InformationTheory)中，對噴泉碼及其應用進行了詳盡的介紹。
[0004]TCP/IP採用重傳機制來保證傳輸的可靠性，但在嚴重損壞的信道上進行傳輸(質量很差的無線或衛星鏈路)或傳輸距離太長的時候其性能很差，因為將導致發送方等待反饋確認信息時的空閒時間長。另外，當接收者數量很多時，也不太可能估計每個信道的刪除概率和丟包情況。數字噴泉碼一LT碼是Luby於2002年提出的，主要針對大規模數據分發和可靠廣播的應用特點而提出的一種理想的解決方案。LT碼生成的編碼包中有少量連接度很高的包，這些包的作用主要是保證對所有數據包的良好覆蓋，從而保證解碼的完整性，然而這些高連接度數據包的存在，消耗了很多編解碼異或操作，同時也降低了低連接度數據包的比例，從而減小了解碼過程中可譯集的大小，降低了解碼成功率。為了代替高連接度數據包完成對數據的良好覆蓋，有效地提高解碼成功率並降低編解碼複雜度，Shokrollahi提出了 Raptor碼。Raptor碼採用兩步編碼的方式:第一步，對原始信息用一個分組碼進行預編碼，然後採用一個弱化的LT碼對數據進行編碼並發送。
[0005]Raptor碼同時使用高連接度和低連接度的編碼數據包，完成對數據的良好覆蓋，有效地提高解碼成功率，同時降低了編解碼複雜度。在Raptor編碼中，弱化的LT碼是指它生成的編碼包沒有高連接度包，無法完全譯出原始數據。Raptor碼解碼時，首先用BP算法對數據進行正常解碼。由於弱化LT碼能以很高的概率恢復出絕大多數的數據包，因此剩下未被解碼的數據包所佔的比例就被控制在一個很小的範圍以內，這些未被解碼的數據不再通過高連接度的編碼包來保證覆蓋和恢復，而是利用預編碼的糾錯能力進行恢復。通過聯合優化弱化LT碼和預編碼的碼率和參數，Raptor可以獲得更低的編解碼複雜度，而在相同解碼開銷下能實現更高的解碼成功率。
[0006]Raptor解決了基於重傳機制的TCP/IP在應用過程中所遇到的問題，但是Raptor對於信息的安全性保障存在缺陷。根據其設計原理，任意接收端或竊聽者只要截獲足夠數量的數據包，即可解碼數據竊取信息。
【發明內容】
[0007]本發明所要解決的技術問題是針對現有技術的不足，提供了一種改進了的二進位刪除信道下的噴泉碼方法；該方示在保持解碼可靠性的條件下，獲得提高編碼效率、降低解碼複雜度的信道編碼策略。
[0008]本發明所要解決的技術問題是通過以下的技術方案來實現的。本發明是一種二進位刪除信道下的噴泉碼方法，其特點是，其步驟如下:
(1)對原始數據流使用分組碼進行預編碼操作，C=dG ;其中，c為預編碼數據包，d為原始數據包，G為生成矩陣，在預編碼時選用密度為0.2的稀疏矩陣作為生成矩陣來獲得預編碼數據；生成矩陣是由眾多小稀疏矩陣構成，然後按行與列分別進行洗牌而得到的；
(2)將預編碼後得到的數據流進行分割處理，按需要分成數個支信息流；
(3)對每個支信息流按LT碼的定義進行編碼，LT編碼時「度」Ω參數的選取範圍是I
<Ω〈 K;其中，K為原始數據包長度；
(4)按預先制定好的路由方案發送各支路信息流；
(5)在解碼端用高斯消元法也即最大似然法解碼最先到達的支信息流，d』=c』/G』，其中，c』為接收到的數據包，d』為LT編碼前的數據包，G』為LT編碼生成矩陣；
(6)將經過編譯的各路支信號流按原分割方案進行重組；
(7)對重組後的信息流進行最大似然解碼法編譯，得到原始數據流，完成了對原始數據的正確完整編譯。
[0009]本發明所述的二進位刪除信道下的噴泉碼方法的步驟(3)中，「度」 Ω的優選範圍是I〈 Ω〈 6。這樣可以提高解碼效率。
[0010]本發明所述的二進位刪除信道下的噴泉碼方法中:步驟(4)所制定的路由方案考慮每段路徑的擦除信道概率，保證在物理距離最短且丟包現象避免得最好，優選的路由方案如下:
(1)根據每一段路徑的長短，為其相關一個模擬的擦除信道概率Pi=di/d總；其中，Pi是該段路徑的擦除概率，di為該路徑的長度，d總為收端到發端的直線距離；注意，這裡假設的擦除信道是一個根據實際路徑長度得到的簡單估計，真實的網絡布局中，每段路徑的擦除概率是不一定的，並且會是事實變動的，所以應該配備更加靈活的路由方案；
(2)將網絡中檢測到的處於收端和發端之間的節點位置，計算所有可能的路徑；這種計算方法屬於列舉法，比如:只跳一步就能到達收端的路徑是「發端-收端」，只跳2步就能到達收端的路徑有「發端-某中間節點-收端」，3步到達的路徑有「發端-某中間節點-另個中間節點-收端」；需要跳的步數越多，可能的路徑越多，算法時間也就越長；
(3)為所有這些路徑計算丟包率；即:將第一步所得到的擦除信道概率應用到每段路徑中去，計算採用每種可能的路線時的丟包情況；將所有路線的丟包情況進行排序，選擇丟包情況最優的前幾種方案。
[0011]最優路線條數的選擇應遵循本發明中所設置的限制(即:排序選擇路線時，任意節點被使用次數達到上限時，之後所有經過它的線路都不能被選用)。這樣，路由方案就完美地配合了編碼方案，達到了數據傳輸絕對安全保密的效果。
[0012]使用該方法編譯的數據在進行傳輸時，配合特定的路由方案可以100%保證信息不被第三方竊聽，達到了信息傳輸的絕對安全；同時，由於採用噴泉碼作為編碼基礎，可以保證解碼方的正確解碼。
[0013]本發明改進的編碼方法遵循「預編碼-分流-LT編碼」思路。本發明中:(1)對原始數據流進行基礎LT碼預編碼，在預編碼時選用了密度為0.2的稀疏矩陣來生成預編碼數據，生成矩陣由眾多小稀疏矩陣構成，然後按行與列分別進行洗牌。詳細方法可參見2009年 Luby 在 Foundations andTrends in Communications and Information Theory 發表的文章Raptor Code。(2)將預編碼數據流進行分割處理，按需要分成數個支信息流，每個支信息流後續將對應一條支路進行傳播。如圖1所示，是一個具有多節點的網絡中使用本發明的編解碼方案模型。在本網絡中，數據可經由中間節點從數據源發送到目標地。經過預編碼的K_pre比特數據包被分為5路，分割後的數據包分別為SplitC比特和SplitD比特。這兩路數據包將會分別接受後續LT編碼處理，並經由不同的物理路徑傳送出去。
[0014]對於複雜的網絡，需要事先確定將要使用的路徑數，然後依此確定相應的分割數。為了保證接收端數據的可還原性，並且保證網絡中其它任何節點不能破譯出原始數據，分割數據包Split必須小於1(_01^811^1=100比特。這是由於如果編碼數據包不大於原始數據包長度，就無法還原出原始數據包，且其還原結果在數學上將會有無數個解。
[0015]另外，可對原始預編碼數據包進行多一些的分割，設置稍微多一些的發送支路來對它們一一傳送。這樣當接收端最早接收到的幾個分割數據包中數據總長度超過了 K_original，不必等接收到所有支路數據包就可開始解碼。如圖中，分割後每路數據包長度為40比特，則在接收端，根據最先收到的3個子數據包(即收到40比特x3=120比特的預編碼數據包)，即可解碼原數據包。這樣的設置可以保證在網絡中某些節點或支路出現故障時接收端仍然能儘可能快 地收取足夠多數據來解碼原數據。因此，實際支路數(分割數)可以大於所必需的支路數(分割數)。[0016]而當網絡分布較為複雜時，傳播路徑數確定後，分割後的數據包如果制定了大小限制為Split_min到Split_max比特(Split_max〈K_original),則在制定傳播路線時,須確定每個網絡中的節點都不得被使用超過 K_original/Split_max 次，以保證任何網絡中間結點都不能解碼獲得原始數據；
與現有技術相比，本發明所述的一種改進的二進位刪除信道下的噴泉碼方法設計合理，它能基本達到信息傳輸時機密性、完整性和可用性的100%安全保證。使用該算法編譯的數據在進行傳輸時，配合適當的路由方案可以100%保證信息不被第三方竊聽，達到了信息傳輸的絕對安全；同時，由於採用噴泉碼作為編碼基礎，可以保證解碼方的正確解碼。本發明為信息的安全傳輸奠定了基礎，對編碼理論、網絡信息安全架構建設具有重大意義。
【專利附圖】
【附圖說明】
[0017]圖1為編解碼示例模型；
圖2為簡單傳輸信道模型；
圖3為編解碼及傳輸流程示意圖；
圖4為複雜傳輸信道模型；
圖5為模型的運行結果圖；
圖6展示的是優化後的路由方案。
【具體實施方式】
[0018]以下參照附圖，進一步描述本發明的具體技術方案，以便於本領域的技術人員進一步地理解本發明，而不構成對其權利的限制。
[0019]實施例1，一種二進位刪除信道下的噴泉碼方法，其步驟如下:
(1)對原始數據流使用分組碼進行預編碼操作，C=dG ;其中，c為預編碼數據包，d為原始數據包，G為生成矩陣，在預編碼時選用密度為0.2的稀疏矩陣作為生成矩陣來獲得預編碼數據；生成矩陣是由眾多小稀疏矩陣構成，然後按行與列分別進行洗牌而得到的；
(2)將預編碼後得到的數據流進行分割處理，按需要分成數個支信息流；
(3)對每個支信息流按LT碼的定義進行編碼，LT編碼時「度」Ω參數的選取範圍是I
<Ω〈 K;其中，K為原始數據包長度；
(4)按預先制定好的路由方案發送各支路信息流；
(5)在解碼端用高斯消元法也即最大似然法解碼最先到達的支信息流，d』=c』/G』，其中，c』為接收到的數據包，d』為LT編碼前的數據包，G』為LT編碼生成矩陣；
(6)將經過編譯的各路支信號流按原分割方案進行重組；
(7)對重組後的信息流進行最大似然解碼法編譯，得到原始數據流，完成了對原始數據的正確完整編譯。
[0020]實施例2，實施例1所述的二進位刪除信道下的噴泉碼方法中:步驟(3)中，「度」Ω的選取範圍是I〈 Ω〈 6。
[0021]實施例3，實施例1或2所述的二進位刪除信道下的噴泉碼方法中:步驟(4)所制定的路由方案考慮每段路徑的擦除信道概率，保證在物理距離最短且丟包現象避免得最好，具體的路由方案如下:(1)根據每一段路徑的長短，為其相關一個模擬的擦除信道概率Pi=di/d總；其中，Pi是該段路徑的擦除概率，di為該路徑的長度，d總為收端到發端的直線距離；
(2)將網絡中檢測到的處於收端和發端之間的節點位置，計算所有可能的路徑；
(3)為所有這些路徑計算丟包率；即:將第一步所得到的擦除信道概率應用到每段路徑中去，計算採用每種可能的路線時的丟包情況；將所有路線的丟包情況進行排序，選擇丟包情況最優的前幾種方案。
[0022]實施例4，二進位刪除信道下的噴泉碼方法實例:
如圖2所示，為一個簡單的傳輸信道模型。A點和B點分別為發送端和接收端。C、D兩點為中轉節點，也即模擬的竊聽者。每段信道都有一個二進位刪除信道概率，記為P/i=JXm。發送端A點的數據流分兩路到達接收到B點。SHAPE \* MERGEFORMAT本實例的編碼方案遵循「預編碼-分流-LT編碼」思路，在Raptor碼的基礎上引進了分流操作。具體流程如圖2所示。
[0023](I)如圖3，SHAPE \* MERGEFORMAT K_original比特為要傳遞的數據包，首先，該數據包被預編碼。在預編碼時選用了密度為0.2的稀疏矩陣來生成預編碼數據，生成矩陣由眾多小稀疏矩陣構成。K_original被擴大SK_bit比特。預編碼的碼率，結合分發支路數量，有嚴格的限制。即預編碼後的數據包，要求長度K_pre滿足:
K_origina l〈K_pre〈K_original氺(L-1)
其中，L為支路數，預編碼碼率最小值為1/L。
[0024](2)將K_bit分流，得到長度分別為SplitC比特和SplitD比特的兩個子數據包，因一串長為K_origi nal的數據包不能被長度比它短的數據包解碼，所以預編碼後分割出的每個支路數據包長度不得超過K_original,即SplitC和SplitD最大值為K_original_l比特。
[0025](3)對SplitC比特和SplitD比特這兩個子數據包進行LT編碼，長度變為TxC比特和TxD比特。為了提高解碼效率，在本發明中「度」 Ω的最終選取範圍是I〈 Ω〈 6。
[0026](4)在二進位刪除信道中，數據包收到損耗丟失，到達中轉站C、D兩點時，子數據包長度衰減為EvsC比特和EvsD比特。中轉C和D點無權對經過的數據進行任何操作，直接將子數據包再轉發到B點，最終接收端B收到的兩個子數據包分別為RxC比特和RxD比特。
[0027](4-1)根據每一段路徑的長短，為其相關一個模擬的擦除信道概率Pi= (di/(d總))。其中，Pi是該段路徑的擦除概率，di為該路徑的長度，d總為收端到發端的直線距離。
[0028](4-2)將網絡中檢測到的處於收端和發端之間的節點位置，計算所有可能的路徑。這種計算方法屬於列舉法，本網絡中一共有3條路徑:A_B、A_C_B和A_D_B。注意，本網絡不例中網絡為正方形，C、D兩點距發送端A點距離相同，故不可返回跳步，不會出現A-C-D-B或A-D-C-B的路線情況。另，一般網絡中發送端和接收端相距都很遠，所以A-B這種情況一般也不會出現，最終確定傳播路線只有A-C-B和A-D-B兩條。
[0029](4-3)為所有這些路徑計算丟包率。即:將(4-1)所得到的擦除信道概率應用到每段路徑中去，計算採用每種可能的路線時的丟包情況。由於K_original/Splt_max =1,即每個中間節點不得使用超過I次。再將所有路線的丟包情況進行排序，選擇出丟包情況最優的2種路由方案，在本發明中也即唯一的兩條。
[0030](5)最後，從兩個支路ACB和ADB將編碼完成的子數據包發往接收端B點。在接收端，對兩個子數據包分別進行LT解碼。用最大似然法(即高斯消元法)解碼最先到達的2支信息流，本發明在實現的過程中採用了「平均分布編碼+高斯消元法解碼」；
(6)將經過編譯的支信號流按原分割方案進行重組；
(7)對重組信息流進行最大似然解碼法編譯，得到原始數據流，完成了對原始數據的正確完整編譯。
[0031]在以上過程中，LT碼的碼率可以無限小，接近於零。這樣即使信道遭受嚴重損壞導致數據大幅丟失，也依然可以保證接收端能夠解碼。這一特性是繼承了噴泉碼的解碼優越性。但是考慮到LT解碼的複雜性和系統性能功耗，可以根據對於信道情況的預估，調整相應的碼率，在儘量減少系統功耗的情況下保證LT成功解碼。LT成功解碼對於整體解碼具有重要作用。
[0032]將傳輸信道模型複雜化，如圖4是一個具有10個網絡節點的模型。點I和點10分別為發送端和接收端，其它的中間節點都是潛在的竊聽者。
[0033]在這個複雜的模型中，假設一共分類出η個子數據包，從η條支路發送，n〈L。為了儘量減少因信道堵塞而引起的延遲，提高傳輸效率，預編碼碼率可以更加小，這樣在接收端不需要接收到所有η個子數據包就可以進行解碼，即設置n>L。至此，接收端可以對發送端發送通知，讓其停止發送當前數據包，開始發送下一個數據包。
[0034]在這種情況下，雖然每個支路的數據包能保證不被任一中間節點解碼出原始數據，但如果某個竊聽者截獲多個子數據包，則有可能得到足夠多的數據來解譯原數據。為保證網絡中的每個數據節點，不能有機會接觸足夠多個子數據包。
[0035]對於路由方案的確定，根據事先掌握網絡中各節點的位置和信道情況，在發送數據前確定好發送路徑，保證所經過的每個中轉節點只會接手到有限個子數據包。這種關於網絡的統計和預估，可以是周期性的，周期越短，發送效率越高，處理機也就越複雜。
[0036]使用該算法編譯的數據在進行傳輸時，配合特定的路由方案可以100%保證信息不被第三方竊聽，達到了信息傳輸的絕對安全；同時，由於採用噴泉碼作為編碼基礎，可以保證解碼方的正確解碼。
[0037]圖5為用Matlab軟體製作模型的運行結果。該模型中，最少3個子數據包就可以還原出原始數據，設定需要路徑為5條以便選取最先到達的3個子數據包，提高解碼效率和性能。如圖5，網絡結點一共有10個，點I和點10分別表示發送端和接收端。根據各個鏈路的擦除信道以及各結點的地理位置，最終確定了 5條路徑，由運行結果可見，排名最優的路徑開銷最小，但是受到信道擦除概率的影響，物理距離最短的並不一定是最優路徑。
[0038]圖6展示的是優化後的路由方案。這種方案對落在虛線外的網絡節點採取屏蔽措施，只考慮地理位置處於發送端和接收端之間的結點，從而提高了計算路由方案時的效率，避免了對於較遠網絡結點的考慮。
[0039]以上運行結果表示出本發明對於數據完整傳輸處理過程的優越性和可靠性。由圖可見，開銷控制在10%左右，最優時可達1%以內，非常高效。可見，發送端在對網絡情況進行估計後，可以對整個編解碼方案進行綜合平衡，在保證可解碼性和完整性的同時，快速地將數據絕對可靠地傳輸給目標地址。
【權利要求】
1.一種二進位刪除信道下的噴泉碼方法，其特徵在於，其步驟如下: (1)對原始數據流使用分組碼進行預編碼操作，c=dG;其中，C為預編碼數據包，d為原始數據包，G為生成矩陣，在預編碼時選用密度為0.2的稀疏矩陣作為生成矩陣來獲得預編碼數據；生成矩陣是由眾多小稀疏矩陣構成，然後按行與列分別進行洗牌而得到的； (2)將預編碼後得到的數據流進行分割處理，按需要分成數個支信息流； (3)對每個支信息流按LT碼的定義進行編碼，LT編碼時「度」Ω參數的選取範圍是I<Ω〈 K;其中，K為原始數據包長度； (4)按預先制定好的路由方案發送各支路信息流； (5)在解碼端用高斯消元法也即最大似然法解碼最先到達的支信息流，d』=c』/G』，其中，c』為接收到的數據包，d』為LT編碼前的數據包，G』為LT編碼生成矩陣； (6)將經過編譯的各路支信號流按原分割方案進行重組； (7)對重組後的信息流進行最大似然解碼法編譯，得到原始數據流，完成了對原始數據的正確完整編譯。
2.根據權利要求1所述的二進位刪除信道下的噴泉碼方法，其特徵在於:步驟(3)中，「度」 Ω的選取範圍是I〈 Ω〈 6。
3.根據權利要求1所述的二進位刪除信道下的噴泉碼方法，其特徵在於:步驟(4)所制定的路由方案考慮每段路徑的擦除信道概率，保證在物理距離最短且丟包現象避免得最好，具體的路由方案如下: (1)根據每一段路徑的長短，為其相關一個模擬的擦除信道概率Pi=di/d總；其中，Pi是該段路徑的擦除概率，di為該路徑的長度，d總為收端到發端的直線距離； (2)將網絡中檢測到的處於收端和發端之間的節點位置，計算所有可能的路徑； (3)為所有這些路徑計算丟包率；即:將第一步所得到的擦除信道概率應用到每段路徑中去，計算採用每種可能的路線時的丟包情況；將所有路線的丟包情況進行排序，選擇丟包情況最優的前幾種方案。
【文檔編號】H04L1/18GK103888225SQ201410154586
【公開日】2014年6月25日 申請日期:2014年4月17日 優先權日:2014年4月17日
【發明者】李婧婧 申請人:李婧婧