面向水聲網(wǎng)絡(luò)可靠傳輸?shù)腇DR 編解碼算法

王麗娟，杜秀娟,2，李沖

（1.青海師范大學(xué)計(jì)算機(jī)學(xué)院，青海 西寧 810008；2.高原科學(xué)與可持續(xù)發(fā)展研究院，青海 西寧 810008）

1 引言

隨著海洋逐漸成為人們維持可持續(xù)發(fā)展的第二領(lǐng)域，水聲通信（UAC,underwater acoustic communication）[1-5]以其水下遠(yuǎn)距離傳輸?shù)莫?dú)特優(yōu)勢和巨大的社會效益而備受關(guān)注。陸地上的互聯(lián)網(wǎng)通信中，不僅應(yīng)用種類很多，數(shù)據(jù)量還很龐大。而對于水聲通信，基本的數(shù)據(jù)傳輸很難保障，但是人類賴以生存的環(huán)境與海洋息息相關(guān)，人類不得不了解海洋以達(dá)到科學(xué)利用海洋的目的。克服水聲通信中窄帶寬、長時延、高誤碼率、多普勒頻移、噪聲及時變性的困難，通過數(shù)字噴泉碼提高水下數(shù)據(jù)傳輸?shù)目煽啃詫?gòu)建高穩(wěn)健性水聲網(wǎng)絡(luò)具有重要意義[6-9]。

目前，水聲網(wǎng)絡(luò)可靠傳輸技術(shù)分為3 類，分別是基于重傳、糾錯、糾錯和重傳的可靠傳輸算法。數(shù)字噴泉碼屬于基于糾錯的可靠傳輸算法。較早的面向水聲網(wǎng)絡(luò)可靠傳輸?shù)臋C(jī)制有很多，例如，Guo 等[10]將網(wǎng)絡(luò)編碼和多徑路由相結(jié)合提出了網(wǎng)絡(luò)編碼機(jī)制；Liu 等[11]提出了包級的前向糾錯（FEC,forward error correction），用于可靠傳輸；Xie 等[12]提出了一種分段數(shù)據(jù)可靠傳輸方案；Liu 等[13]提出了最初的自適應(yīng)可靠傳輸協(xié)議（ARTP,adaptive reliable transport protocol），根據(jù)節(jié)點(diǎn)間的距離找到合適的FEC組合，實(shí)現(xiàn)水下數(shù)據(jù)的可靠傳輸；Mo 等[14]提出了一種基于編碼的多跳協(xié)調(diào)可靠數(shù)據(jù)傳輸機(jī)制。

數(shù)字噴泉碼對中間編碼信息的出錯并不敏感，只關(guān)注接收端最終是否能成功譯碼，并且即使傳輸過程發(fā)生個別信息丟失也不會進(jìn)行頻繁的數(shù)據(jù)重傳[15-16]。降低編碼信息與節(jié)點(diǎn)、信道的相關(guān)性，是數(shù)字噴泉碼適用于水聲網(wǎng)絡(luò)的一大優(yōu)勢。遞歸LT（RLT,recursive LT）碼[17-18]是一種基于數(shù)字噴泉碼的遞歸LT 碼，其采用遞歸思想改進(jìn)了LT 碼的編碼算法。RLT 解碼算法依賴度為1 的編碼分組，如果度為1 的編碼分組在信道傳播過程中發(fā)生丟失或誤碼，則解碼極有可能會失敗。如果在解碼時從編碼分組之間異或的角度出發(fā)，只要生成矩陣中2 個編碼分組對應(yīng)的列存在“嚴(yán)格短環(huán)”，那么二者即可進(jìn)行異或運(yùn)算。

對此，本文提出一種過濾式降維（FDR,filtering dimension reduction）譯碼算法，對RLT 碼譯碼算法做出改進(jìn)，彌補(bǔ)RLT 碼的譯碼缺陷，提高譯碼成功率。FDR 算法利用生成矩陣中構(gòu)成嚴(yán)格短環(huán)的編碼分組之間的異或操作，產(chǎn)生度為1 的編碼分組或者將高度數(shù)編碼分組進(jìn)行“降維”處理，使其度數(shù)降低。不會像RLT 譯碼算法那樣，F(xiàn)DR 譯碼算法不僅解除了對來自發(fā)送端編碼器產(chǎn)生的度為1 的編碼分組的依賴，還可以快速降低高度數(shù)編碼分組的度數(shù)，從而進(jìn)一步降低譯碼復(fù)雜度。此外，本文提出了一種與FDR 譯碼算法相結(jié)合的優(yōu)化度分布函數(shù)，在保證度為1 的編碼分組數(shù)量適當(dāng)?shù)那疤嵯?，增大了高度?shù)編碼分組的選取概率，從而增加了一次降維即可得到度為1 的編碼分組的概率，加快了譯碼進(jìn)度。

本文的貢獻(xiàn)如下。

1)對RLT 碼中存在的短環(huán)問題進(jìn)行數(shù)學(xué)分析，在此基礎(chǔ)上定義、分析嚴(yán)格短環(huán)問題，進(jìn)一步對嚴(yán)格短環(huán)加以利用，提出FDR 算法，解決了對度為1的編碼分組的依賴。

2)提出一種與FDR 算法相結(jié)合的優(yōu)化度分布函數(shù)，增加了FDR 算法在進(jìn)行解碼時一次降維即可得到度為1 的編碼分組的概率。

3)將FDR 算法和RLT 碼在NS3 仿真平臺上進(jìn)行大量測試，經(jīng)對比分析，實(shí)驗(yàn)結(jié)果驗(yàn)證了FDR算法的有效性和穩(wěn)健性。

2 相關(guān)工作

涉及本文研究內(nèi)容的相關(guān)算法包括RLT 編碼算法和RLT 解碼算法[17-18]。

2.1 RLT 編碼算法

RLT編碼器能夠由原始輸入分組產(chǎn)生無限多個編碼分組序列。對于給定的(k,d,Ω(d))，其中k為原始分組個數(shù)，d（d∈{1,2,3,4,k}）為編碼分組的度值，Ω(d)為度分布，輸入分組序列為{S1,S2,…,Sk}，k個輸入分組構(gòu)成集合I，編碼分組序列為{Y1,Y2,…,Yj,…,Yn}(n＞k)。編碼分組與原始分組對應(yīng)關(guān)系如圖1 所示，具體產(chǎn)生過程如下。

圖1 編碼分組與原始分組對應(yīng)關(guān)系

1)RLT 編碼器對集合I中的k個輸入分組先后分別執(zhí)行異或操作，產(chǎn)生一個度為k的編碼分組，復(fù)制得到個度為k的編碼分組，其中pp表示水下數(shù)據(jù)逐跳傳輸?shù)姆纸M錯誤率。

2)從集合I中隨機(jī)選取個不同的分組，構(gòu)成集合U1，產(chǎn)生個度為1 的編碼分組，其中表示期望接收到的度為1 的數(shù)據(jù)分組個數(shù)。

3)令U2=I-U1，從集合U2中隨機(jī)選取個輸入分組，分別與從U1中隨機(jī)選取的一個分組進(jìn)行異或操作，從而產(chǎn)生個度為2 的編碼分組。

4)令U3=I-U1-U2，若，則從U3中隨機(jī)選取|U3|個輸入分組，從集合I中隨機(jī)選取個輸入分組；否則從U3中隨機(jī)選取個輸入分組，分別與從U1、U2各自隨機(jī)選取的一個分組進(jìn)行異或操作，從而產(chǎn)生個度為3 的編碼分組。

5)令U4=I-U1-U2-U3，若，則從U4中隨機(jī)選取|U4|個輸入分組，從集合I中隨機(jī)選取個輸入分組；否則從U4中隨機(jī)選取個輸入分組，分別與從U1、U2、U3各自隨機(jī)選取的一個分組進(jìn)行異或操作，從而產(chǎn)生個度為4 的編碼分組。

2.2 RLT 解碼算法

當(dāng)編碼分組通過刪除信道傳輸時，要么被接收節(jié)點(diǎn)正確接收，要么產(chǎn)生分組丟失。RLT 解碼器試圖從接收的編碼分組中恢復(fù)原始輸入分組，RLT 解碼過程如下。

1)首先找到僅與一個輸入分組Xi相連的編碼分組Yj，若找不到，終止譯碼。

2)令Xi=Yj。

3)在圖1 中，對每一個連接到Xi的編碼分組Yj進(jìn)行異或操作，即Ym=Ym⊕Xi。

4)刪除與Xi相連的所有邊。

5)繼續(xù)從1)執(zhí)行，直至解碼成功。

3 RLT 碼存在的問題

3.1 短環(huán)問題

停止集S[19]是滿足如下條件的變量節(jié)點(diǎn)的集合：任意與S所包含變量節(jié)點(diǎn)相連的校驗(yàn)節(jié)點(diǎn)都至少2 次連接到S。停止集包含的變量節(jié)點(diǎn)的數(shù)量稱為停止集的尺度，停止集內(nèi)的變量節(jié)點(diǎn)構(gòu)成的生成矩陣中存在短環(huán)。生成矩陣Gkn是一個k×n階的二進(jìn)制矩陣，Gkn含有n個列向量，記作Gkn=[Y1,Y2,Y3,…]，列向量記作Ym=[Y1m,Y2m,…,Ykm]T，m=1,2,3,…,n，其元素的取值為0 和1。Gkn的示例為

每個列向量對應(yīng)一個由k個輸入分組（對應(yīng)矩陣中S1…Sk）中的某幾個分組異或而得到的編碼輸出分組Ym，如果向量元素取0 表示該輸入分組不參與此編碼分組的生成，如果向量元素取1 表示該輸入分組參與此編碼分組的生成，Ym如式(1)所示。

其中，xi表示向量元素取值。下面給出短環(huán)的定義及性質(zhì)。

定義1短環(huán)。在生成矩陣中，如果有這樣兩列，它們在相同位置上的兩行（或兩行以上）均為1，這些由1 構(gòu)成的行形成一個閉合的環(huán)，稱為短環(huán)。

如果滿足短環(huán)定義的行有兩行，那么這兩行構(gòu)成的短環(huán)為4 元環(huán)；如果滿足短環(huán)定義的行有三行，那么這三行構(gòu)成的短環(huán)為6 元環(huán)，以此類推，假設(shè)滿足短環(huán)定義的行有k'(2≤k' ＜k)個，它們構(gòu)成的短環(huán)為2k'元環(huán)。以圖2 所示的RLT 譯碼過程中出現(xiàn)終止現(xiàn)象為例解釋短環(huán)。

圖2(a)所示原始分組和編碼分組的對應(yīng)關(guān)系為Y1=S2，Y2=S2⊕S3⊕S4，Y3=S1⊕S2⊕S3，Y4=S1⊕S2⊕S3⊕S4。根據(jù)RLT 碼譯碼過程，首先找到度為1的編碼分組Y1，此時可直接譯出S2并將Y1和S2之間的連線去掉，如圖2(b)所示；下一步，將所有與S2相連的編碼分組{Y2、Y3、Y4}分別與S2進(jìn)行異或運(yùn)算，同時更新Y2、Y3、Y4的值為異或運(yùn)算結(jié)果，并且將它們之間的連線刪除，如圖2(c)所示。此時，剩余的編碼分組Y2、Y3、Y4的度值d分別為d(Y2)=2、d(Y3)=2、d(Y4)=3。根據(jù)LT 碼譯碼規(guī)則，需要找出度為1 的編碼分組，但是3 個編碼分組的度值均大于或等于2，所以譯碼被迫終止。此時，Y2、Y3、Y4對應(yīng)的生成矩陣如圖3 所示。

圖3 的生成矩陣中包含2 個環(huán)長為4 的短環(huán)：Y3,Y4對應(yīng)的兩列在第一行和第三行都是1，所以第一行和第三行構(gòu)成4 元短環(huán)；同樣地，Y2,Y4所對應(yīng)的兩列在第三行和第四行都是1，所以這兩行也構(gòu)成了4 元短環(huán)，如圖3 中虛線所示。以4 元環(huán)為例，假設(shè)RLT 碼參數(shù)為(n,k,Ω)，其中k為原始分組個數(shù)，n為編碼分組個數(shù)，在n×k階的生成矩陣G中重量為i的列向量在全體列向量中的比例是Ωi，也就是說，度為i的輸出符號（即編碼分組）在全體輸出符號中的比例為Ωi[19]。

那么，生成矩陣G中某個重量為i的列向量的生成概率為[19]

圖2 RLT 碼譯碼過程中出現(xiàn)終止現(xiàn)象

圖3 Y2、Y3、Y4 對應(yīng)的生成矩陣

生成矩陣G中某個重量為j(j＞ 1)的列向量與該重量為i(i＞ 1)的列向量構(gòu)成4 元短環(huán)的概率為

3.2 嚴(yán)格短環(huán)

定義2嚴(yán)格短環(huán)。在生成矩陣中，如果有這樣兩列，它們在相同位置上的兩行（或兩行以上）均為1，并且其中一列除了這兩行（或多行）其余位置的行上全是0，這些由1 構(gòu)成的行形成一個閉合的環(huán)，稱為嚴(yán)格短環(huán)。假設(shè)滿足嚴(yán)格短環(huán)定義的行有k'(2≤k' ＜k)個，則它們構(gòu)成的短環(huán)為嚴(yán)格(2k')元環(huán)。

生成矩陣G中重量為j(j＞ 2)的列和某一重量為2 的列構(gòu)成嚴(yán)格4 元短環(huán)的概率為

根據(jù)式(4)可近似地推導(dǎo)出重量為j的列和某一重量為m(m＜j)的列構(gòu)成嚴(yán)格2m元短環(huán)的概率為

則對于k×n階生成矩陣G存在嚴(yán)格4 元短環(huán)的概率為

根據(jù)式(6)可近似地推導(dǎo)出生成矩陣G存在嚴(yán)格2m元短環(huán)的概率為

其中，m＜j。

4 FDR 算法與優(yōu)化度分布函數(shù)

4.1 譯碼思想

在第3 節(jié)短環(huán)問題的分析中，當(dāng)出現(xiàn)圖2 所示的RLT 碼譯碼終止現(xiàn)象時，3 個編碼分組Y2、Y3、Y4構(gòu)成的生成矩陣中包含了2 個4 元嚴(yán)格短環(huán)。接下來，從參與編碼的原始分組集合的角度進(jìn)行分析。編碼分組Y2對應(yīng)的參與編碼的原始分組的集合為{S3,S4}，Y3對應(yīng)的參與編碼的原始分組的集合為{S1,S3}，Y4對應(yīng)的參與編碼的原始分組的集合為{S1,S3,S4}。這3 個集合存在明顯的包含關(guān)系，即。將Y2和Y4進(jìn)行異或運(yùn)算可得到S1=Y2⊕Y4，將Y3和Y4進(jìn)行異或運(yùn)算可得到S4=Y3⊕Y4，將S1和Y3進(jìn)行異或運(yùn)算可得到S3=S1⊕Y3。原本使用BP 譯碼算法只能依賴度為1 的Y1譯出S2，S2的譯碼運(yùn)算量，而S1,S3,S4根本無法解出，可以認(rèn)為，獲得S1,S3,S4的譯碼運(yùn)算量接近于無窮大，即，繼而得到所有原始分組的譯碼運(yùn)算量為。但是通過編碼分組之間的異或運(yùn)算，即可解出3 個原始分組S1、S3、S4。S1、S2、S3、S4的譯碼運(yùn)算量分別為，那么成功解碼所有原始分組的譯碼運(yùn)算量為。

表面上看，嚴(yán)格短環(huán)是一種編碼時的浪費(fèi)，對傳統(tǒng)的依賴度為1 的編碼分組的解碼方式并無價值，但是把譯碼方式進(jìn)行一定改變，就可以對嚴(yán)格短環(huán)加以利用。嚴(yán)格短環(huán)的貢獻(xiàn)將不可忽視，甚至可能成為解碼剩余的未成功的原始分組的關(guān)鍵步驟。因此，有結(jié)論1 成立。

結(jié)論1生成矩陣中構(gòu)成短環(huán)的兩列只要度z值不同，并且度值較小的那一列除了構(gòu)成短環(huán)的行存在1，其他行不存在1 時，它們所對應(yīng)的編碼分組之間即可進(jìn)行異或運(yùn)算。二者異或產(chǎn)生的新編碼分組（稱為二次編碼分組）的度值必定小于二者之一，甚至比二者度值都小。如果二者度值相差1，它們異或直接得到一個度為1 的分組；如果二者度值相差大于1，經(jīng)過異或之后，度值較大的那一列的度值可降低為二者度值之差。

LT 碼譯碼過程要在接收到一定數(shù)量編碼分組后進(jìn)行；RLT 碼在此做出改進(jìn)，數(shù)據(jù)編碼結(jié)束后首先發(fā)送度為1 的編碼分組，RLT 碼的譯碼過程在接收到編碼分組之時即刻啟動，但這2 種譯碼方式終究都是依賴度為1 的編碼分組啟動譯碼。而采用FDR 算法的譯碼器，在收到第一個編碼分組（無論度值是否為1）后可以開始譯碼。仍以圖2 為例，如果采用FDR 譯碼算法的接收端收到的第一個編碼分組是Y4、第二個編碼分組是Y3時，接收端對比參與二者編碼的原始分組集合，2 個集合存在真包含關(guān)系，接收端便可啟動譯碼過程，對2 個編碼分組進(jìn)行異或運(yùn)算。因此，有結(jié)論2 成立。

結(jié)論2接收端在收到第一個編碼分組時就可以啟動譯碼過程，只要其對應(yīng)的參與編碼的原始分組集合與后續(xù)收到的編碼分組對應(yīng)的參與編碼的原始分組集合之間存在真包含關(guān)系，就不必等待度為1 的編碼分組，這在一定程度上縮短了譯碼時間。

基于以上2 個結(jié)論，本節(jié)提出一種FDR 譯碼算法，接下來主要介紹譯碼器的設(shè)計(jì)和譯碼流程。首先給出FDR 譯碼算法中的幾個參數(shù)。

定義3k個輸入符號向量為S={S1,S2,…,Sk}，對k個輸入符號進(jìn)行編碼產(chǎn)生的n個編碼符號向量為Y={Y1,Y2,…,Yi,…,Yn}，其中，編碼分組Yi的度值表示為d(Yi)。FDR 算法將編碼分組分為2 種類型，除了由k個原始分組經(jīng)發(fā)送端編碼器產(chǎn)生的n個編碼分組Y1,Y2,…,Yn之外，還包括編碼分組在接收端譯碼器內(nèi)與其他編碼分組異或產(chǎn)生的二次編碼分組。為了區(qū)分，二次編碼分組用Ysec表示，那么二次編碼分組的度值表示為d(Ysec)。一個編碼分組（無論Y1,Y2,…,Yn中的某一個Yi還是某一個二次編碼分組Ysec）對應(yīng)參與其編碼原始分組的ID 集合為T。

4.2 譯碼器的設(shè)計(jì)

譯碼器根據(jù)編碼分組的度值范圍采用分層設(shè)計(jì)思想。在本文4.4 節(jié)提出的度分布函數(shù)中，編碼分組的度值d(d∈ Z)有5種，分別為d=1、d=2、d=3、d=4、d=k。譯碼器隨之設(shè)計(jì)為5 層，即l1、l2、l3、l4、lk，如圖4 所示。譯碼器的每層分別存放的是相應(yīng)度值的編碼分組，在這里，層內(nèi)的編碼分組既包括來自接收端的編碼分組，也包括來自發(fā)送端的編碼分組進(jìn)入譯碼器后在各層之間流動時與層內(nèi)已存在的（先進(jìn)入譯碼器的）編碼分組異或產(chǎn)生的二次編碼分組。比如，l2存放了所有度為2 的編碼分組，這些編碼分組當(dāng)中可能有接收到來自發(fā)送端的度為2 的編碼分組，還可能有一個度為3 的編碼分組與一個度為1 的編碼分組在l1層異或產(chǎn)生的度為2 的二次編碼分組。這里還需說明的是，lk層存放度值范圍為d∈(4,k]的編碼分組，度為k的編碼分組可以和任何一個編碼分組進(jìn)行異或，那么一個度為k（假設(shè)k＞ 8）的編碼分組和一個度為t(t=1,2,3,4)的編碼分組異或產(chǎn)生的二次編碼分組的度值為k-t且k-t＞ 4，因此將度值大于4 且小于k的二次編碼分組放入lk層。以度為4 的編碼分組在lk層發(fā)生異或運(yùn)算為例，產(chǎn)生的二次編碼分組Ysec的度為d=k-4=6，所以將二次編碼分組Ysec放在lk層。編碼分組在譯碼器內(nèi)的存在形式是一對key-value，key 表示該編碼分組對應(yīng)的參與構(gòu)成其編碼原始分組的ID 集合T，value 表示該編碼分組。例如，編碼分組Yi=S1⊕S2⊕S3，S1、S2、S3對應(yīng)的ID 分別為0、1、2，即，那么Yi在l3層的存在形式為{0,1,2}-Yi。編碼分組進(jìn)入譯碼器后向下流動，依次經(jīng)過譯碼器的各層，當(dāng)?shù)竭_(dá)某一層時，如果該編碼分組的T和當(dāng)前層內(nèi)某個編碼分組的T存在真包含關(guān)系，換句話說，度值小的編碼分組里的所有原始數(shù)據(jù)分組同樣參與了度值較大的編碼分組的異或運(yùn)算（此為異或條件），那么二者異或運(yùn)算之后，度值較大的編碼分組被更新為二次編碼分組，其度值被降低。此過程相當(dāng)于對度值大的編碼分組進(jìn)行過濾、降維，降低高度數(shù)編碼分組的度值，在一定程度上加快了譯碼進(jìn)度，度值較大或者度值很小的編碼分組在某層與其他編碼分組產(chǎn)生異或運(yùn)算的概率更大。

圖4 譯碼器層次設(shè)計(jì)

理論上，譯碼器的l2、l3、l4、lk層與它下面除l1層外所有層內(nèi)的每一個key 不存在真包含關(guān)系。FDR譯碼器從收到第一個編碼分組開始，一直處在解碼狀態(tài)，直至l1層包含整個向量S，視為譯碼成功。

4.3 FDR 譯碼流程

FDR 算法規(guī)定發(fā)送端將數(shù)據(jù)編碼完成后，先發(fā)送d=k的編碼分組Yn，再依次發(fā)送d=4、d=3、d=2、d=1的編碼分組。具體流程如算法1 所示。

算法1面向水聲網(wǎng)絡(luò)可靠傳輸?shù)腇DR 編解碼算法

輸入編碼分組序列Y={Yn,Yn-1,…,Y2,Y1}

輸出原始分組S={Sk,Sk-1,…,S2,S1}

4.4 與FDR 相結(jié)合的優(yōu)化度分布函數(shù)

對于給定的RLT 碼編碼參數(shù)(n,k)，其中k為原始分組數(shù)量，n為對k個原始分組進(jìn)行編碼后得到的編碼分組數(shù)量。編碼分組的入度定義為參與其構(gòu)成的原始分組的個數(shù)。

設(shè)每個編碼分組的平均入度值為Dper，所有編碼分組的總?cè)攵戎禐?/p>

不理想覆蓋問題使未被覆蓋（即未參與任何編碼分組的編碼）的原始分組無法譯出，是直接導(dǎo)致譯碼失敗的主要原因之一，所以在度分布的設(shè)計(jì)中必須考慮這一點(diǎn)。

數(shù)字噴泉碼的度分布函數(shù)影響編碼復(fù)雜度，關(guān)系到編碼效率。合理的度分布應(yīng)該在保證度為1 的編碼分組的數(shù)量適當(dāng)?shù)那疤嵯略龃蠖戎递^大的編碼分組的選取概率，這樣使由度分布產(chǎn)生的編碼分組平均度值較小，同時兼顧不理想覆蓋問題，保證對所有原始分組的良好覆蓋。

給定k個原始數(shù)據(jù)分組，度分布設(shè)計(jì)為

其中，ρ(d)和τ(d)的計(jì)算式分別為

當(dāng)d=1時，編碼分組的數(shù)量與k相關(guān)，原始分組數(shù)量k越大，度為1 的編碼分組數(shù)量越多，越有利于加快解碼速度；當(dāng)d=k時，編碼分組數(shù)量為1，保證所有原始分組都參與到該分組的編碼中，避免了不理想覆蓋問題。d=2、d=3、d=4的設(shè)計(jì)從理想孤波分布出發(fā)，將度為2、度為3、度為4 的選取概率設(shè)置為小于1 的數(shù)，從而將度分布的優(yōu)化轉(zhuǎn)化成常數(shù)的設(shè)計(jì)問題。

由式(10)可得，度分布的期望值為

表1 幾種度分布的編解碼復(fù)雜度比較

4.5 編解碼統(tǒng)計(jì)分析

將4.4 節(jié)度分布函數(shù)納入遞歸編碼思想中，并采用FDR 解碼算法進(jìn)行解碼，本節(jié)從統(tǒng)計(jì)角度出發(fā)對解碼成功概率進(jìn)行如下分析。

設(shè)水聲信道的糾刪概率為pp，編碼分組在信道上的傳輸符合二項(xiàng)分布，由概率質(zhì)量函數(shù)B(N;n,pp)可知，當(dāng)發(fā)送N個編碼分組時，成功接收到n個編碼分組的概率為

在完全隨機(jī)數(shù)字噴泉碼中，發(fā)送節(jié)點(diǎn)發(fā)送N個編碼分組，接收節(jié)點(diǎn)成功解碼的概率為

由于采用FDR 算法，k×n階生成矩陣中滿足嚴(yán)格短環(huán)的列向量在停止集中仍可繼續(xù)被用來解碼。發(fā)送同等數(shù)量的編碼分組，采用FDR 算法的通信雙方中的接收節(jié)點(diǎn)成功解碼的概率要比完全隨機(jī)的數(shù)字噴泉碼的解碼概率高。當(dāng)發(fā)送節(jié)點(diǎn)發(fā)送N（N由式(16)給出）個編碼分組時，接收節(jié)點(diǎn)能夠恢復(fù)k個原始分組的概率由式(17)給出。

其中，O=∑Ω(d)且O＞ 1。

5 仿真評估

5.1 度分布仿真實(shí)驗(yàn)

本節(jié)采用Matlab 工具，對理想孤波分布（ISD,ideal soliton distribution）、穩(wěn)健式孤波分布（RSD,robust soliton distribution）、二進(jìn)制指數(shù)分布（BED,binary exponential distribution）和本文優(yōu)化度分布進(jìn)行仿真對比。

圖5 給出當(dāng)k=10 時，度值從1～10 的編碼分組概率分布。圖6 給出當(dāng)k=20 時，度值從1～20 的編碼分組概率分布。圖7 給出當(dāng)k=40 時，度值從1～40的編碼分組概率分布。

圖5 k=10 時的編碼分組概率分布

圖6 k=20 時的編碼分組概率分布

圖7 k=40 時的編碼分組概率分布

從圖5～圖7 中可以看出，采用本文優(yōu)化度分布的編碼分組的平均度值較低，編碼分組的數(shù)量與k相關(guān)，原始分組數(shù)量k越大，度為1 的編碼分組數(shù)量越多。度為1、2、3、4 的編碼分組的概率較其他度分布稍大；度大于4 且小于k的編碼分組數(shù)量為0。在原始分組數(shù)量較多的情況下，這樣的度分布既可以控制解碼不至于太復(fù)雜，又可以保證較高的解碼成功概率，且無論k值如何，d=k的編碼分組一直存在，這保證了所有原始分組都參與編碼。

5.2 FDR 算法仿真實(shí)驗(yàn)

1)仿真場景

仿真實(shí)驗(yàn)中布置了7 個水下節(jié)點(diǎn)，其拓?fù)浣Y(jié)構(gòu)如圖8 所示。其中6 個節(jié)點(diǎn)構(gòu)成一個二維的正六邊形且分別位于6 個頂點(diǎn)，是數(shù)據(jù)源節(jié)點(diǎn)；剩余一個節(jié)點(diǎn)是網(wǎng)絡(luò)中的sink 節(jié)點(diǎn)，位于正六邊形的中心。數(shù)據(jù)的流動方向是源節(jié)點(diǎn)到sink 節(jié)點(diǎn)，且它們都是單跳通信，源/目的節(jié)點(diǎn)間距和傳輸半徑均為r=1 500 m。為了排除數(shù)據(jù)分組碰撞給數(shù)據(jù)恢復(fù)帶來的影響，實(shí)驗(yàn)中設(shè)置這6 個源節(jié)點(diǎn)不能同時向sink 節(jié)點(diǎn)發(fā)送數(shù)據(jù)，這可通過控制各源節(jié)點(diǎn)發(fā)送分組的時間來實(shí)現(xiàn)。

圖8 正六邊形網(wǎng)絡(luò)拓?fù)?/p>

2)仿真參數(shù)

實(shí)驗(yàn)中采用的協(xié)議架構(gòu)為micro-ANP 模型，節(jié)點(diǎn)在應(yīng)用層產(chǎn)生的源數(shù)據(jù)被分為多個大小為60 個數(shù)據(jù)分組的數(shù)據(jù)塊，每個數(shù)據(jù)分組分為幀頭、負(fù)載和幀尾3 個部分。數(shù)據(jù)分組格式如表2 所示。其中負(fù)載部分大小為200 B，尾部為FCS 校驗(yàn)位。

表2 數(shù)據(jù)分組格式

仿真實(shí)驗(yàn)的參數(shù)設(shè)置對實(shí)驗(yàn)結(jié)果影響較大，調(diào)整系統(tǒng)參數(shù)以較準(zhǔn)確地模擬水下通信環(huán)境，如節(jié)點(diǎn)的發(fā)送增益。實(shí)驗(yàn)中，通過改變2 個節(jié)點(diǎn)間的距離和發(fā)送增益，測得對應(yīng)距離下的發(fā)送增益值，如表3 所示。拓?fù)渲泄?jié)點(diǎn)間距為1 500 m，發(fā)送增益為-37 dB，節(jié)點(diǎn)的接收功率和休眠狀態(tài)下的功率分別是0.75 W和10 mW，聲波可用的頻帶寬度是10 kHz。

表3 傳輸范圍與發(fā)送增益

此外，依據(jù)水下聲信號衰減模型，仿真實(shí)驗(yàn)?zāi)M了信號在水聲信道傳輸時的損耗。實(shí)驗(yàn)采用Micro-ANP 通信架構(gòu)，信號到達(dá)接收節(jié)點(diǎn)的物理層，接收節(jié)點(diǎn)計(jì)算發(fā)送增益與路徑損耗的差值得出接收增益，通過判斷接收增益的閾值，物理層決定這個分組是否繼續(xù)向上層遞交。衰減模型具體計(jì)算式為

其中，x表示收發(fā)節(jié)點(diǎn)間距離，a的計(jì)算式為

通常，能量擴(kuò)散因子采用柱體擴(kuò)散因子k=1.5，中心頻率f=22 kHz。節(jié)點(diǎn)初始能量、數(shù)據(jù)塊大小、仿真時間等實(shí)驗(yàn)參數(shù)設(shè)置如表4 所示。

表4 實(shí)驗(yàn)參數(shù)設(shè)置

3)仿真結(jié)果

此處定義單跳的成功解碼概率，實(shí)驗(yàn)中可測得的數(shù)據(jù)是源節(jié)點(diǎn)向sink 節(jié)點(diǎn)發(fā)送數(shù)據(jù)的總次數(shù)NTotal-trans及經(jīng)歷二次編碼后成功的次數(shù)Nretrans，二者之差即為單次成功傳輸?shù)拇螖?shù)None-time-succ，None-time-succ和NTotal-trans的比值即為一次發(fā)送數(shù)據(jù)中接收端成功解碼的概率，如式(21)所示。

FDR 譯碼算法和RLT 譯碼算法在單次傳輸解碼成功概率方面的仿真結(jié)果如圖9 所示，其中橫軸表示單次發(fā)送的編碼分組數(shù)量，縱軸表示單次傳輸成功解碼概率。從圖9 可以看出，使用FDR譯碼算法的成功解碼概率普遍高于RLT 譯碼算法。當(dāng)編碼分組數(shù)量較少時，比如n=20，2 個譯碼算法的解碼成功概率相差無幾，RLT 譯碼算法達(dá)到92%，F(xiàn)DR 譯碼算法可達(dá)93%。當(dāng)n=25 時，F(xiàn)DR 譯碼算法出現(xiàn)突變情況，解碼成功概率為90%，略低于RLT 譯碼算法的92%。當(dāng)n=30 時，F(xiàn)DR 譯碼算法性能明顯優(yōu)于RLT 譯碼算法性能，二者分別為95%和89%。當(dāng)n＞40 時，RLT 譯碼算法的成功概率基本保持在86%，而FDR 譯碼算法的成功概率保持在89%左右。綜合來看，F(xiàn)RD譯碼算法的性能較RLT 譯碼算法更優(yōu)。

圖9 RLT 譯碼和FDR 譯碼成功概率對比

實(shí)驗(yàn)中還統(tǒng)計(jì)了采用FDR 算法在不同原始分組、不同編碼分組、不同發(fā)送分組頻率下的4×4組NTotal-trans與Nretrans實(shí)驗(yàn)數(shù)據(jù)，分別如圖10～圖13所示。圖10 顯示了在0.64 packet/s 發(fā)送分組頻率下，原始分組數(shù)為25、編碼分組數(shù)為32 時統(tǒng)計(jì)的4 組實(shí)驗(yàn)數(shù)據(jù)。圖11 顯示了在0.57 packet/s 發(fā)送分組頻率下，原始分組數(shù)為 30、編碼分組數(shù)為38 時統(tǒng)計(jì)的4 組實(shí)驗(yàn)數(shù)據(jù)。圖12 給出在0.51 packet/s 發(fā)送分組頻率下，原始分組數(shù)為35、編碼分組數(shù)為44 時統(tǒng)計(jì)的4 組實(shí)驗(yàn)數(shù)據(jù)。圖13給出在0.70 packet/s 發(fā)送分組頻率下，原始分組數(shù)為40，編碼分組數(shù)為50 時統(tǒng)計(jì)的4 組實(shí)驗(yàn)數(shù)據(jù)。

圖10 k=25、n=32 時的NTotal-trans 與Nretrans

圖11 k=30、n=38 時的NTotal-trans 與Nretrans

圖12 k=35、n=44 時的NTotal-trans 與Nretrans

圖13 k=40、n=50 時的NTotal-trans 與Nretrans

6 結(jié)束語

本文提出一種FDR 算法，消除采用傳統(tǒng)譯碼方式的RLT 譯碼算法在收到一定數(shù)量編碼分組才開始解碼的等待時間，實(shí)現(xiàn)邊接收邊嘗試解碼的快速譯碼方式。此外，通過編碼分組之間的異或運(yùn)算，有效增加了度為1 的編碼分組的產(chǎn)生概率，不再僅依賴于從發(fā)送端獲取度為1 的編碼分組，在降低傳輸時延的同時，通過增加度為1 的編碼分組出現(xiàn)的概率，從而提高譯碼成功率。通過NS3 仿真平臺在解碼成功概率方面與RLT 碼進(jìn)行仿真對比，實(shí)驗(yàn)結(jié)果顯示，F(xiàn)DR 算法的解碼成功概率普遍高于RLT碼，當(dāng)編碼分組數(shù)量為30～40 個時，F(xiàn)DR 算法的解碼成功概率比RLT 碼高5%，且FDR 算法譯碼成功率最高可達(dá)95%；當(dāng)編碼分組數(shù)量為40～60 個時，F(xiàn)DR 算法的解碼成功概率比RLT 碼高3%，且FDR算法的譯碼成功概率基本保持在89%～90%。實(shí)驗(yàn)結(jié)果驗(yàn)證了FDR 算法對于水聲網(wǎng)絡(luò)可靠傳輸?shù)挠行院头€(wěn)健性。