基于高度包保護的優化融合編碼算法

趙旦峰，文杰，倫貴陽

(哈爾濱工程大學 信息與通信工程學院, 黑龍江 哈爾濱 150001)

基于高度包保護的優化融合編碼算法

趙旦峰，文杰，倫貴陽

(哈爾濱工程大學 信息與通信工程學院, 黑龍江 哈爾濱 150001)

為了提升水聲網絡中現有的基于噴泉碼與網絡編碼融合傳輸方案的性能，減少LT編碼包經過中繼節點網絡編碼后度分布的變化，本文提出一種基于高度包保護的優化融合編碼算法(LTNC- HP)。LTNC- HP算法通過在各個中繼節點增加高度保護傳輸算法，解決融合編碼時存在的不理想覆蓋問題，有效減少了傳輸的信息量。同時LTNC- HP算法在中繼節點編碼時加入同度包優先選擇機制，提高各個中繼節點編碼信息的有效性，增加了網絡中數據包的多樣性。仿真結果表明，與改進前的融合編碼方案相比，LTNC- HP算法傳輸信息的有效性顯著提高，且傳輸冗余大幅度降低。

水聲網絡； 噴泉碼； 網絡編碼； 高度包保護傳輸； 同度包優先選擇； 編碼融合

Abstract：LTNC- HP, a novel optimized recoding algorithm for the protection of high- degree packets in underwater acoustic sensor networks, is proposed. The proposed algorithm improves the performance of a data transmission scheme and is based on the combination of LT codes with network coding. Moreover, the algorithm decreases the variation in the degree distribution of LT coding packets after passing the network coding at the relay point. By introducing a high- degree protection transmission algorithm at each intermediate node, the proposed algorithm can resolve the imperfect coverage of the input symbols and decrease the amount of data transmission. Moreover, the priority selection mechanism for the same degree packet is added in LTNC- HP when coding at each relay node, significantly improving the efficiency of coding information at each relay node and increasing the diversity of the data packets in the network. Simulation results showed that compared with existing encoding algorithms, LTNC- HP improves the effectiveness of the information transmission and decreases transmission redundancy.

Keywords：underwater acoustic network; LT code; network coding; protective transmission for high degree packets; priority selection mechanism of unison packets; coding fusion

隨著科技的快速發展，水聲通信正在迅速成長為一個具有廣泛的商業應用前景和軍事應用前景的領域。然而水聲傳感器網絡(underwater acoustic sensor networks, UASNs)[1]因其存在窄帶、時變、長延時、能源供給受限等惡劣的通信條件，使得水聲傳感器網絡在應用時面臨巨大的挑戰[2-4]。噴泉碼[5]和網絡編碼[6]都被認為是有助于提高水聲通信網絡魯棒性的信道編碼技術。噴泉碼憑借其獨特的編碼無速率特點，對于水聲通信環境表現出良好的適應性，但其應用于多跳通信網絡中時，采用數據包逐跳解碼轉發的方式不可避免的增加了整個網絡的傳輸延時[7]，并且帶來其他潛在的因素。同時網絡編碼因其較高的編譯碼運算復雜度[8]，使得其在應用時也受到了一定的限制。研究表明，結合噴泉碼和網絡編碼技術可以彌補兩種編碼技術各自的缺陷，大幅度提升網絡傳輸性能。

為了減少傳輸延遲，最初噴泉碼在多跳中繼傳輸網絡中采用中繼轉發的模式，該方案在各個節點不存在編碼開銷，但是在惡劣的信道條件下將造成大量的信息重傳和能量消耗。Khaldoun Al Agha等首次提出了一種基于指數分布的噴泉碼與網絡編碼融合編碼傳輸的方案，算法的核心在于中繼節點先通過簡單的網絡編碼運算降低高度LT編碼包的度數，然后按照指數分布生成度值完成中繼節點的異或網絡編碼[9]。然而該方案因受到度分布概率函數的限制，無法充分利用網絡編碼的優勢來增大網絡傳輸的效率，使其在應用中具有一定的局限性。Anya Apavatjrut等提出了LT自適應融合編碼(LT- adapted xor with network coding, XLT)算法，XLT算法利用節點的空閑時隙引入了低度包保護傳輸方法和異或網絡編碼算法，提高了低度編碼包在各個中繼節點編碼包中所占的比例，增加了網絡中數據包的多樣性[10]。但是XLT算法采用了時分復用的通信方式，在進行網絡編碼時只能使用當前時刻緩存序列中的編碼包，使其編碼包多樣性受到了一定的限制。在惡劣的信道條件下，緩存序列中編碼包的局限性將可能導致大量冗余信息的傳輸，引起大量的能量消耗。隨后，文獻[11]提出了基于LT碼和隨機線性網絡編碼(random linear network coding, RLNC)的融合編碼算法，算法的核心思想是利用LT碼和RLNC分別實現在時域編碼和空間域編碼，以此提高數據傳輸的可靠性。這種乘積型融合編碼算法，雖然通過RLNC來增加各個中繼節點編碼包的信息多樣性，可以保證信息的有效傳輸，但是其在譯碼時需要先進行網絡編碼包的高斯消元譯碼[12]恢復出LT編碼包，然后再進行BP譯碼[13]。在惡劣的通信環境下，這種方案將需要大量的傳輸冗余才能完成數據恢復，同時也將帶來較大的譯碼延時和運算復雜度，不適用于能量和帶寬受限的水聲通信環境。

為此，本文提出一種基于高度包保護傳輸策略的優化融合編碼算法(the combination of LT code and network coding for the protection of high- degree packets,LTNC- HP)，通過引入高度包保護(the protection of high degree packets,HP)算法和同度包優先選擇機制實現水聲傳感器網絡中低冗余數據可靠傳輸。

1 噴泉碼與網絡編碼的融合分析

從本質上來看，噴泉碼與網絡編碼的融合過程中存在的主要問題是經過網絡編碼后生成的新的編碼包度分布相比原始LT編碼包的度分布情況發生了顯著的變化。為了進一步分析度分布的變化情況，圖1展示了理想條件下在噴泉碼與網絡編碼的直接融合方案中，LT編碼包經過5跳中繼節點的再編碼處理后度分布的變化情況，這里的直接融合即中繼節點直接對于LT碼字進行伽羅華域的異或網絡編碼運算，不進行任何的特殊處理，其中信源的輸入符號數K=100，0跳代表原始RSD分布圖。從圖中可以看出，融合編碼后度分布的變化主要表現為兩個方面：1)經過5跳中繼節點的網絡編碼處理后，度數為1的數據包已經全部消失，這必將造成接收端因缺少度數為1的數據包而無法開始譯碼；2)相比原始的度分布，第5跳中繼節點生成的編碼包對于原始輸入符號的覆蓋度(這里編碼包度分布中最高度數值代表了對于輸入符號的覆蓋程度，在圖1中用豎直線標出)大幅度下降，覆蓋度的降低將直接導致大量數據包的重傳和冗余信息的發送。上述分析可知單純的直接融合編碼方案是可不行的。

圖1 度分布變化情況Fig.1 The situation of degree distribution

眾所周知，保證到達接收端的編碼包集合中存在度數為1是譯碼開始的充分條件，而確保可譯碼集合對于輸入符號的覆蓋度是保證譯碼持續進行的必要條件。在XLT算法中已經給出了保證低度編碼包存在的解決方法，因此如何提高接收端的可譯碼集合對于輸入符號的覆蓋度是本文研究的重點。

研究發現，中繼節點執行異或網絡編碼時關于編碼符號的選擇是影響覆蓋度的主要步驟。中繼節點進行編碼符號的選擇時主要存在兩個問題：1)選取編碼符號的方式。現有的融合算法中，中繼節點都是采用隨機的方式選擇編碼包進行異或網絡編碼，然而無規律地隨機選擇編碼包進行再編碼將高概率地造成信息的冗余編碼，使得譯碼端獲取的有效信息量減少，增加了譯碼過程的復雜度。因此，找到一個最佳的選擇方式是提高編碼信息有效性的一個直接思路。2)異或網絡編碼時存在度碰撞(degree collision, DC)。DC就是指利用LT編碼包進行異或網絡編碼時可能出現生成的編碼包的度數不等于所有參與編碼的數據包度數之和的現象，例如：(x1⊕x2)⊕(x3⊕x2)的度數是2而不是4。由于再編碼時DC現象的存在，導致高度編碼包(d>K/2)將很難通過中繼節點的網絡編碼運算生成，進而造成各個中繼節點對于輸入符號覆蓋度的降低。 由于DC問題是無法避免的，因此在中繼節點執行編碼處理時考慮保護原有高度數編碼包(d>K/2)的傳輸是解決可譯碼集合不理想覆蓋問題的一個解決辦法。

2 LTNC- HP算法的設計

LTNC- HP算法主要包含兩個階段的設計，一是在編碼前的階段引入高度包保護傳輸算法，保證各個中繼節點對于輸入編碼符號的覆蓋度；二是在編碼階段引入同度包優先選擇機制，提高各個中繼節點編碼信息的有效性。

2.1 高度保護傳輸算法

高度包保護傳輸(HP)是在中繼節點編碼前完成的。中繼節點在完成接收工作后，首先統計緩存序列中高度值編碼包(d>K/2)的個數，如果個數不為0，則將數據包放入高度編碼包集合SH中；否則，將直接進入異或網絡編碼階段。算法的具體步驟如下：

1)初始化。節點編碼次數N、高度數編碼包個數NH、高度編碼包集合{SH}，本節點新編碼包集合S′;

2)統計緩存序列中高度編碼高的個數，記為NH，并將滿足條件的編碼包存入集合SH；

3)如果SH≠?，將SH集合中數據包全部轉存至集合S′中；否則執行步驟5；

4)更新節點的編碼次數N=N-NH；

5)結束。

在添加了HP算法的融合編碼方案中，所有參與傳輸的中繼節點都將對于接收的高度數編碼進行保護傳輸，間接避免了中繼節點再編碼時因DC問題無法生成高度包的情形，同時也將提高各個節點對于原始輸入符號的覆蓋度，減少信息重傳的次數，進而減少冗余信息傳輸帶來的延時問題。

2.2 同度包優先選擇機制

傳統的編碼符號隨機選擇方式所造成的編碼包重復選擇是無規律且不可控制的。圖2為某節點緩存序列中27個度數為2的編碼包通過隨機選擇方式各自在本節點網絡編碼操作中出現的次數。從圖2可以看出，編碼符號的隨機選擇造成了同度編碼包不均勻地參加本節點網絡編碼操作。這種選取的不均勻性將導致編碼信息重復的可能性增大，使得對于原始輸入符號的覆蓋度降低。針對存在的不均勻選擇問題，提出了同度包優先選擇機制。

同度包優先選擇機制(priority selection mechanism for the same degree packets, PSM)是指每個中繼節點進行異或網絡編碼時，標記每個編碼包參與本節點異或網絡編碼的次數，在面對多個同度數編碼包是否參與編碼的選擇時，選取在當前時刻參與本節點編碼操作最少的編碼包進行編碼，避免了不均勻選擇的問題。這樣在整體的編碼操作中，所有同度數的編碼包參與編碼的次數大致上將是相同的。PSM機制通過避免重復無意義的編碼操作來提高編碼信息的有效性，避免了冗余信息的傳輸。

圖2 度為2的編碼包出現次數Fig.2 Occurrences of coded packets with the degree of 2

2.3 LTNC- HP優化融合編碼方案

在前面的內容中介紹了HP算法和PSM機制，本節將對基于高度包保護的優化融合編碼方案LTNC- HP的整體流程進行詳細闡述：

假設信源數據塊由K個輸入符號構成，各個節點將按照預設的RSD分布進行編碼，且編碼在伽羅華域GF(2)進行。

中繼節點首先進行數據初始化，初始化完成后進入分階段處理：第一階段，執行HP算法，前面的內容已經敘述過算法的原理，這里將不再贅述；完成高度保護傳輸后，進入第二階段，執行異或網絡編碼運算，具體的編碼過程如下：

1)結合RSD分布和約束條件生成度值d。中繼節點進行異或網絡編碼時，參與編碼的數據包不僅僅包括度值為1的原輸入符號而且包含上一跳節點生成的編碼包，這樣在度d的選擇上必須要通過約束條件判斷d是否可達，約束條件如下

(1)

d

(2)

式中：n(i)是指節點緩存中包含的度數為i的數據包個數，upper_bound是代表節點緩存序列中包含源輸入符號的個數。如果d不滿足其中的任何一個約束條件，則按照RSD分布重新生成d，直至找到滿足條件的d，方可執行下一步。

2)編碼符號的選擇。根據生成的度值d，節點首先利用PSM機制選出滿足條件的數據包，如果當前已經參與編碼的數據包個數大于1，則需要通過異或運算來判斷是否存在DC問題。如果存在DC，則重新使用PSM機制進行篩選，直至找到滿足條件的編碼包；如果判斷不存在DC問題，則執行異或網絡編碼運算。

3)重復步驟2，生成預設數目的數據包后，將全部的編碼數據包傳輸至下一跳中繼節點。

那么，LTNC- HP算法的流程圖如下。

圖3 LTNC- HP算法流程圖Fig.3 The flow chart of LTNC- HP

LTNC- HP算法通過引入高度包保護傳輸(HP)算法，提高了各個中繼節點編碼后對于原始輸入符號的覆蓋度，減少了信息重傳的次數；同時，在編碼時加入同度優先選擇機制(PCM)彌補了傳統隨機選擇編碼的不可控性和隨機性，再次減少了冗余信息的傳輸，使得整個系統的傳輸延遲性能得到改善。

3 算法仿真與分析

本文基于OPNET仿真平臺搭建一個簡單的線性網絡模型對于LTNC- HP算法進行驗證。仿真實驗分別從度分布情況、傳輸跳數的影響及信道條件的影響3方面進行，以平均傳輸冗余Overhead為衡量指標將LTNC- HP與傳統多種融合算法進行仿真比較。平均傳輸冗余用來描述傳輸方案的編碼效率，冗余越低，說明傳輸方案的傳輸效率越高。那么平均傳輸冗余Overhead的計算表達式如下

(3)

式中：pk_numi代表第i跳節點發送的編碼包數，h為傳輸跳數。

仿真參數設置如下：信源輸入符號數K=100；各個節點的編碼冗余均設為1.2；RSD度分布表達式如下

(4)

(5)

其中

(6)

式中：c=0.03，δ=0.5；選用BP算法進行譯碼；反饋確認ACK信號在接收端完成全部數據恢復后由譯碼節點發出，且假設反饋信道中無信息丟失。

3.1 度分布情況

假設信道丟包率為0.5，傳輸跳數為6跳，分別對于采用XLT算法和LTNC- HP算法的方案中第5跳中繼節點編碼前后的度分布情況進行仿真分析。

圖4和圖5分別為XLT算法和LTNC- HP算法編碼前后度分布對比圖，圖4和圖5中已經將最高度數值即代表對于輸入符號的覆蓋度用豎直虛線標注。從圖4中可以看出，中繼節點采用XLT算法進行異或網絡編碼時，雖然編碼后中低度包所占的比例顯著提升，但是大部分其他度值的編碼包已經消失，并且編碼后新的編碼包的度分布和 RSD分布的結構有很大區別。同時值得注意的是，高度數編碼包在連續5跳節點的編碼處理后也已經全部消失，這將不可避免的導致到達第6跳譯碼節點的編碼包對于輸入符號的覆蓋度大幅度降低，進而造成譯碼過程的中斷。相比較之下，圖5給出的采用LTNC- HP算法編碼糾正后的度分布基本保留了RSD原始度分布的形狀，同時也實現了對于高度編碼包的保護傳輸，對于輸入符號的覆蓋度基本保持不變，這將有利于譯碼過程的順利進行，減少不必要的冗余重傳。

圖4 XLT算法度分布Fig.4 The degree distribution of XLT

圖5 LTNC- HP算法度分布Fig.5 The degree distribution of LTNC- HP

3.2 傳輸跳數

為了驗證高度包保護傳輸算法對于融合編碼傳輸方案的影響，圖6展示了丟包率為0.5時，增加HP算法和無保護方案在不同網絡傳輸跳數的條件下，平均傳輸冗余性能的比較情況。從圖中可以看出，引入了HP算法的傳輸方案，平均傳輸冗余明顯少于傳統無高度保護的傳輸方案，并且隨著網絡中傳輸跳數的增加，性能提升的幅度逐漸增大。當傳輸跳數達到6時，引入HP算法的傳輸方案性能提升最大，與無保護的傳輸方案相比平均傳輸冗余下降了2.0，這對于能源有限的水聲通信系統是十分有利的。上述仿真證明，在中繼節點編碼時引入HP算法可以用來抵抗在惡劣水聲信道進行通信時，編碼信息傳輸有效性降低的情況。

圖6 高度保護傳輸(HP)對傳輸冗余的影響Fig.6 The influence of HP on the transmission redundancy

進一步驗證LTNC- HP算法的性能，假設信道丟包率為0.5。圖7展示了中繼節點分別采用Passive Relay算法、XLT算法及LTNC- HP算法進行處理時，平均傳輸冗余隨傳輸跳數變化的曲線對比圖。如圖所示，隨著傳輸跳數的增加，三種方案的平均傳輸冗余均呈現逐漸上升的趨勢，但其上升的速率有明顯的差異。三種方案的平均傳輸冗余性能符合LTNC- HP算法最優、XLT算法次之、Passive Relay算法最差的規律。仿真結果也同時驗證了隨著網絡傳輸跳數的增加，LTNC- HP算法的性能優勢更加明顯。

圖7 三種方案平均傳輸冗余隨跳數變化Fig.7 Average transmission redundancy under different transmission schemes varied with Hop

3.3 信道條件

固定傳輸跳數為6跳，本文以信道丟包率來描述水聲傳感器網絡中信道條件的變化。圖8以丟包率為變量，比較了三種算法的平均傳輸冗余性能。通過仿真結果可以發現，隨著丟包率的逐漸增大，三種方案的平均傳輸冗余均表現出上升的趨勢。在信道條件較好丟包率較小的條件下，即丟包率小于0.11時，三種算法的性能基本相同；在丟包率大于0.11時，XLT算法和LTNC- HP算法相比Passive Relay算法逐漸表現出優勢；隨著信道條件繼續變差，XLT算法的平均傳輸冗余上升速度明顯高于LTNC- HP算法，可以證明XLT算法的優勢在惡劣的信道條件下逐漸降低，然而LTNC- HP算法的優越性更加凸顯的表現出來。這是因為LTNC- HP算法在各個中繼節點編碼效率更加有效，同時提高了對于輸入符號的覆蓋度，在惡劣的信道條件下，接收端可以實現以更少的編碼包即可完成譯碼，即實現以低冗余完成數據傳輸。

圖8 不同信道條件下平均傳輸冗余性能Fig.8 Average transmission redundancy under different transmission schemes varied with Packet Loss Rate

4 結論

1)LTNC- HP算法使得中繼節點融合編碼后的度分布接近于RSD度分布。

2)高度包保護方案相對于非保護方案可明顯減少數據包的傳輸冗余。

3)與Passive Relay算法、XLT算法相比，LTNC- HP算法可顯著降低數據包的傳輸冗余，有效地提高節點的能量效率。

LTNC- HP算法為網絡編碼與噴泉碼的編碼融合傳輸提供了參考，后續的研究中將探討如何把融合算法擴展用于典型網絡中。

[1] GAO Xiujing, ZHANG Feifei, ITO M. Underwater acoustic positioning system based on propagation loss and sensor network[C]//Processing of OCEANS 2012, Yeosu, 2012: 1-4.

[2] 趙旦峰,梁明珅,段晉玨. 水聲網絡中噴泉碼的應用研究現狀與發展前景[J]. 系統工程與電子技術, 2014,36(9): 1838-1843.

ZHAO Danfeng, LIANG Mingshen, DUAN Jinjue. Survey of fountain codes in underwater acoustic sensor networks[J]. Systems engineering and electronics, 2014, 36(9): 1838-1843.

[3] CAI Shaobin, GAO Zhenguo, YANG Desen, et al. A network coding based protocol for reliable data transfer in underwater acoustic sensor[J]. Ad Hoc networks, 2013, 11(5): 1603-1609.

[4] OTNES R, ASTERJADHI A, CASARI P, et al. Underwater acoustic networking techniques[M]. Berlin: Springer, 2012: 19-81.

[5] CASTURA J, MAO Y. Rateless coding over fading channels[J]. IEEE communications letters, 2012, 10(1): 46-48.

[6] WU Huayang, CHEN Min, GUAN Xin. A network coding based routing protocol for underwater sensor networks[J]. Sensors, 2012, 12(4): 4559-4577.

[7] CASTURA J, MAO Yongyi. Rateless coding for wireless relay channels[J]. IEEE trans wireless commun,2007，6(5):1638-1642.

[8] CUI Tao, CHEN Lijun, HO T. Energy efficient opportunistic network coding for wireless networks[C]. INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008: 361-365.

[9] AI A K, KADI N, STOJMENOVIC I. Fountain code with XOR of encoded packets for broadcasting and source independent backbone in multi- hop networks using network coding[C]//Vehicular Technology Conference, VTC-2009, Barcelona, Spain, 2009.

[10] APAVATJRUT A, GOURSAUD C, JAFFRES R K, et al. Toward increasing packet diversity for relaying LT fountain codes in wireless sensor networks[J]. Communications letters, IEEE, 2011, 15(1):52-54.

[11] BASSOLI R, TALOOKI V N, MARQUES H, et al. Product network codes for reliable communications in diamond networks[M]∥Wireless Internet. 2014,146: 85-90

[12] NOURA H, MARTIN S, AGHA K A, et al. ERSS- RLNC: Efficient and robust secure scheme for random linear network coding[J]. Computer networks, 2014, 75: 99-112.

[13] 李璐穎，吳湛擊. 噴泉碼編譯碼原理研究和分析 [J].中國新通信， 2010， 4(7)： 41-46. LI Luying, WU Zhanji. Code research and analysis on fountain codes[J].China new telecommunications, 2010， 4(7)： 41-45.

ThealgorithmbasedonthecombinationofLTcodeandnetworkcodingfortheprotectionofhigh-degreepackets

ZHAO Danfeng, WEN Jie, LUN Guiyang

(College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)

10.11990/jheu.201607030

http://www.cnki.net/kcms/detail/23.1390.u.20170427.1328.022.html

TN929.3

A

1006- 7043(2017)09- 1491- 06

2016-07-11. < class="emphasis_bold">網絡出版日期

日期：2017-04-27.

國家自然科學基金項目(61371099).

趙旦峰(1961-), 男, 教授,博士生導師； 文杰(1991-)，女，碩士研究生.

文杰,E- mail：wenjie_wsq@126.com.

本文引用格式：趙旦峰，文杰，倫貴陽. 基于高度包保護的優化融合編碼算法的設計[J]. 哈爾濱工程大學學報， 2017， 38(9): 1491-1496.

ZHAO Danfeng, WEN Jie, LUN Guiyang. Optimized algorithm based on the combination of LT code and network coding for the protection of high- degree packets[J]. Journal of Harbin Engineering University， 2017， 38(9): 1491-1496.