水聲網(wǎng)絡基于優(yōu)先級與可Zigzag解碼的在線噴泉碼

摘 要：水聲網(wǎng)絡（underwater acoustic network，UAN）具有長傳播時延、高誤碼率、半雙工通信等特性，這些特性嚴重影響了UAN中數(shù)據(jù)的可靠傳輸。而在線噴泉碼具有在線控制、編解碼復雜度低、碼率自適應等諸多優(yōu)勢，在線噴泉碼適合于保障UAN中數(shù)據(jù)的可靠傳輸。針對遞歸與限制反饋的在線噴泉碼（recursive OFC with limited feedback，ROFC-LF）存在不理想覆蓋和4元環(huán)問題導致略高的開銷和頻繁的反饋，提出適用于UAN的基于優(yōu)先級與可Zigzag解碼的ROFC-LF（priority-based and zigzag-decodable ROFC-LF，P-ZROFC-LF）。P-ZROFC-LF在建立階段選取具有最高優(yōu)先級的原始包進行編碼直至所有原始包均參與編碼。同時，引入可Zigzag解碼編碼，將無用編碼包進行移位異或轉換為有用編碼包來提高解碼性能。通過隨機圖理論，分析P-ZROFC-LF所需編碼包數(shù)與原始包數(shù)之間的關系。理論分析與仿真結果表明，與大部分在線噴泉碼相比，P-ZROFC-LF顯著提高了反饋和開銷性能。其中P-ZROFC-LF相比于ROFC-LF的反饋和開銷分別減少了18%和0.0176，更適用于UAN。

關鍵詞：水聲網(wǎng)絡；在線噴泉碼；可Zigzag解碼；反饋；開銷

中圖分類號：TN911.22"" 文獻標志碼：A"" 文章編號： 1001-3695（2025）03-033-0895-08

doi： 10.19734/j.issn.1001-3695.2024.07.0246

Priority-based and Zigzag decodable online fountain codes for underwater acoustic network

Du Xiujuan1， 2， Wang Yujie1， Liu Xiuxiu1， Zhao Jian1

（1. Qinghai Provincial Key Laboratory of IoT， College of Computer， Qinghai Normal University， Xining 810008， China; 2. The State Key Laboratory of Tibetan Intelligent Information Processing amp; Application， Xining 810008， China）

Abstract：Underwater acoustic network （UAN） is characterized by long propagation delay， high bit error rate， low bandwidth， and half-duplex communication， seriously affecting the reliable transmission of data in UAN. While online fountain codes have many advantages such as online control， low coding and decoding complexity， and code rate adaption， online fountain codes are suitable for guaranteeing reliable transmission of data in UAN. Aiming at the problems of higher overhead and frequent feedback of recursive online fountain codes with limited feedback （ROFC-LF） resulted by unideal coverage and four-membered rings， this paper proposed a priority-based and zigzag-decodable ROFC-LF （P-ZROFC-LF） for UAN. P-ZROFC-LF selected the original packet with the highest priority in the build-up phase and encodes until all original packets were encoded.Further， it introduced zigzag-decodable code to convert useless packets into useful packets by shifting and XORing operation to improve decoding performance. The relationship between the number of encoded packets required by P-ZROFC-LF and analyzed the number of original packets by random graph theory. Theoretical analysis and simulation results show that compared with most online fountain codes， P-ZROFC-LF significantly improves the feedback and overhead performance. Specifically， P-ZROFC-LF reduces the feedback and overhead by 18% and 0.0176 respectively， compared with ROFC-LF， making it more suitable for UAN.

Key words：underwater sensor network; online fountain code; Zigzag-decodable; feedback; overhead

0 引言

海洋是地球上最廣闊的水體，占據(jù)了約71%的地球表面，其中蘊涵了豐富的生物、石油、礦物等資源。保護和可持續(xù)利用海洋資源，對維護生態(tài)平衡和增進人類福祉至關重要。水聲網(wǎng)絡（underwater acoustic network，UAN）作為人類獲取海洋資源的重要手段，已廣泛應用于水下環(huán)境監(jiān)測、海洋資源勘探、災害預防等諸多領域［1，2］。由于UAN具有長傳播時延、高誤碼率、半雙工通信、節(jié)點移動性等特性，使得水下節(jié)點在數(shù)據(jù)轉發(fā)的過程中，數(shù)據(jù)存在較高的錯誤或丟失［3，4］。因此，提高數(shù)據(jù)的傳輸可靠性成為UAN傳輸?shù)难芯繜狳c。

針對UAN中數(shù)據(jù)的可靠傳輸，研究人員通常采用兩種差錯控制策略：冗余機制和重傳機制。冗余機制旨在為接收端提供錯誤檢測和糾正能力，而重傳機制旨在保證可靠傳輸?shù)那闆r下提高接收端的接收成功率。一方面，傳統(tǒng)基于冗余的向前糾錯機制（forward error correction，F(xiàn)EC）［5］是一種固定碼率的糾刪碼，需要提前預估信道確定冗余包的數(shù)量，然而對于時變的水聲信道而言，無法提前預估信道的擦除概率，預估過高會浪費信道資源，預估過低則會導致解碼失敗。另一方面，傳統(tǒng)自動重傳請求機制（automatic repeat-request，ARQ）［6］依靠接收端的確認來更新發(fā)送端的接收狀態(tài)和定時方案，然而，由于UAN中聲波速度較慢導致的長傳播延遲，使得ARQ難以保證數(shù)據(jù)的實時可靠傳輸。

具有碼率無關性［7］的數(shù)字噴泉碼［8］非常適用于高度動態(tài)變化的UAN，所以不少學者將數(shù)字噴泉碼用于支持UAN數(shù)據(jù)的可靠傳輸［9～11］。在線噴泉碼（online fountain code，OFC）［12］作為一種帶反饋的新型無速率數(shù)字噴泉碼，具有在線控制、編解碼復雜度低、碼率自適應等諸多優(yōu)勢。因此，將在線噴泉碼用于支持UAN數(shù)據(jù)的可靠傳輸具有廣闊的應用前景。

近年來，不少學者對OFC作出進一步研究，并取得了較好的效果。Huang等人［13］提出了基于剩余度分布改進的在線噴泉碼（improved online fountain codes based on shaping for left degree distribution，IOFC-SLDD），在產(chǎn)生下一個編碼包時優(yōu)先選取度數(shù)最小的原始包，有效降低了開銷和反饋包數(shù)量。Huang等人［14］引入了指定的原始包選擇方法，提出了改進在線噴泉碼（improved online fountain codes，IOFC）。Zhao等人［15］提出了一種具有預建立階段和增強完成階段的OFC（online codes with a pre-buildup phase and enhanced completion phase，OFC-Pre-EC）。該機制在預建立階段發(fā)送一定數(shù)量的度為1的編碼包，以提高中間解碼性能。此外，接收方增加了一個緩沖區(qū)，用于保留由三個未解碼的原始包異或生成的編碼包。Shi等人［16］在OFC基礎上，在建立階段形成可zigzag解碼的在線噴泉碼（zigzag decodable online fountain，ZDOF）以及在完成階段引入緩沖區(qū)形成緩沖區(qū)解碼的可zigzag解碼的在線噴泉碼（zigzag decodable online fountain with buffer decoding method，ZDOF-BDM），來有效提高中間解碼性能。Xiao等人［17］為減少OFCNB（online fountain codes without no build-up phase）的反饋次數(shù)，提出了一種基于估計的度選擇（estimation based degree selection，EBDS）方案，在OFCNB-EBDS方案中，編碼包的度是發(fā)送方基于當前解碼狀態(tài)的估計。然而，在反饋次數(shù)有限的情況下，OFCNB-EBDS的性能會顯著下降。Liu等人［18］基于水聲網(wǎng)絡的特點提出了遞歸與限制反饋的OFC（recursive OFC with limited feedback，ROFC-LF），ROFC-LF在開銷、編解碼復雜度、能耗等方面優(yōu)于大多數(shù)在線噴泉碼。然而，其在建立階段的編碼過程中未覆蓋所有原始包，導致完成階段所需編碼包數(shù)和反饋包數(shù)的增加。此外，其在編碼過程中產(chǎn)生重復編碼包（4元環(huán)），進一步增加了開銷。同時，ROFC-LF在解碼過程中依賴度1的編碼包，若度1編碼包在水聲信道中轉發(fā)的過程中丟失，可能會阻礙解碼過程的推進。對于能量受限、數(shù)據(jù)率低的UAN而言，大量的編碼包和反饋包會增加通信時延、能耗和降低信道利用率。柳秀秀等人［19］在ROFC-LF基礎上進一步提出按序遞歸和限制反饋的OFC（sequential recursive online fountain code with limited feedback，SROFC-LF），在建立階段構造大小為8的連通組件，同時在完成階段設置反饋門限來進一步降低編解碼開銷和減少反饋包數(shù)量。然而，隨著原始包數(shù)的增加，該機制的反饋性能急劇下降。

本文基于ROFC-LF的優(yōu)勢，針對UAN的特點，提出了一種適用于UAN的基于優(yōu)先級與可zigzag解碼的ROFC-LF（priority-based and zigzag-decodable ROFC-LF，P-ZROFC-LF），對ROFC-LF算法作出改進，降低編解碼開銷和反饋包數(shù)。在建立階段，P-ZROFC-LF采取高優(yōu)先級的隨機選擇策略，在預先指定優(yōu)先級的原始包中選取兩個具有最高優(yōu)先級的原始包進行異或編碼，以確保編碼覆蓋所有原始包。其次，P-ZROFC-LF還考慮了可Zigzag解碼（zigzag-decodable，ZD）編碼的特點，在需要異或運算的原始包間進行移位異或，以確保在下次選擇相同原始包進行編碼時無須依賴度1編碼包即可實現(xiàn)解碼。

1 相關工作

1.1 ROFC-LF

ROFC-LF的編碼方式與數(shù)字噴泉碼的編碼方式類似，均采用簡單的異或操作。但與使用二部圖表示編解碼過程的數(shù)字噴泉碼不同，ROFC-LF的解碼圖采用單部圖表示。

圖1為二部圖對應的單部圖。如圖1（a）所示，在二部圖中，圓節(jié)點代表原始包，方形節(jié)點代表編碼包。如圖1（b）所示，在單部圖中，僅使用圓節(jié)點代表原始包。若一個編碼包為兩個原始包異或所得，則在對應節(jié)點中建立一條邊。若存在原始包被恢復，則其對應的節(jié)點為黑色，否則為白色。單部圖中的連通組件是由邊相連的白色節(jié)點構成的連通圖，組件大小為連通組件中包含的節(jié)點個數(shù)，如圖1（b）中最大連通組件的大小為3。若一個組件中存在節(jié)點變黑，則此組件中的所有節(jié)點均會變黑。

ROFC-LF的編解碼過程包括建立階段和完成階段。假設發(fā)送方需要傳輸k個原始包，ROFC-LF編解碼過程如下：

a）建立階段：首先，發(fā)送方持續(xù)隨機發(fā)送度2編碼包，直至接收方的解碼圖中存在大小｜D｜=β0k的最大連通組件。接著，接收方發(fā)送反饋包來告知發(fā)送方。然后，發(fā)送方隨機發(fā)送度1編碼包，直至接收方成功解碼圖中的最大連通組件。接著，接收方發(fā)送反饋包告知發(fā)送方將要進入完成階段。

b）完成階段：發(fā)送方根據(jù)接收方所提供的帶所有原始包解碼狀態(tài)字段的反饋包，將原始包分為已恢復原始包集合Ri（｜A｜，SNs）和未恢復原始包集合Wi（k-｜A｜，SNs）（｜A｜表示已經(jīng)恢復的原始包數(shù)，SNs表示原始包編號）。發(fā)送方根據(jù)反饋包來更新Wi（k-｜A｜，SNs），并在Wi（k-｜A｜，SNs）中根據(jù)預先設置的度1、度2占比α和θ隨機選取原始包進行遞歸編碼。接收方僅在前后兩次恢復率差值Δβ達到反饋門限σ時才進行反饋。本文所提的P-ZROFC-LF與ROFC-LF完成階段類似，故本文將σ仍設為0.006。

1.1.1 不理想覆蓋問題

因ROFC-LF在建立階段采用原始的隨機編碼策略，根據(jù)隨機圖理論，會造成在建立階段的編碼過程中未覆蓋所有原始包，從而在建立階段結束時產(chǎn)生大量連通組件，其中大小為1的連通組件數(shù)［13］為

V1=kelog（1-β0）β0

（1）

根據(jù)式（1），當β0=0.5，在建立階段結束時，大小為1的組件數(shù)量幾乎占原始包總數(shù)的25%。根據(jù)文獻［13，14］可知，完成階段所需編碼包數(shù)與建立階段生成的連通組件數(shù)成正比。所以減少建立階段連通組件的數(shù)量可減少完成階段的編碼包數(shù)。由于反饋大多在完成階段產(chǎn)生，減少建立階段連通組件的數(shù)量可減少反饋包數(shù)。

UAN具有數(shù)據(jù)率低、能量受限等特點，大量編碼包會消耗額外能量和占用信道帶寬。此外，大多數(shù)UAN調制解調器只能以半雙工模式運行，傳輸和接收反饋包會增加通信時延。鑒于此，本文在建立階段引入基于優(yōu)先級的隨機編碼策略，使編碼覆蓋所有原始包來解決不理想的覆蓋問題。

1.1.2 4元環(huán)問題

定義1 在生成矩陣中，如果在兩列的相同兩行（或兩行以上）位置的值均為1，則生成矩陣中這幾行在對應列上構成的閉合環(huán)稱為短環(huán)［20］。

若存在兩行滿足短環(huán)的定義，則這兩行構成的環(huán)稱為4元環(huán)。圖1中存在一個4元環(huán)，其對應的生成矩陣如圖2所示。

由于ROFC-LF在建立階段和完成階段僅發(fā)送度2或度1編碼包，所以在編碼過程中的生成矩陣中會產(chǎn)生的短環(huán)為4元環(huán)。4元環(huán)意味著存在由相同的一對原始包異或生成的重復度2編碼包，從而增加開銷。

引理1 在建立階段，若給定k和β0，ROFC-LF中冗余的編碼包數(shù)量NROFC-LFrb（k，β0）［16］為

NROFC-LFrb（k，β0）=k12c-1+2χ（c）-χ2（c）2c

（2）

其中：c為每個原始包平均選擇次數(shù)，且滿足：

β0+e-cβ0=1

（3）

根據(jù)式（3），χ=χ（c）為滿足方程χe-χ=ce-c的唯一解，即

χ（c）=∑∞γ=1γγ-1γ！（ce-c）γ

（4）

引理2 在完成階段，給定原始包個數(shù)k和接收方計算的當前原始包的恢復率βt，ROFC-LF生成重復的度2編碼包的概率Prc（k，βt）［18］為

Prc（k，βt）=2（k-kβt）（k-kβt-1）

（5）

根據(jù)引理2，當僅剩2個原始包未解碼時，只要發(fā)送度2編碼包，則為重復編碼包的概率為1。由于度1編碼包占比為α，度2編碼包占比為θ，且α+θ=1，所以當僅剩2個原始包未解碼時，每次選取度2重復編碼包的概率為θ。

基于上述分析，在ROFC-LF建立和完成階段均有可能出現(xiàn)重復編碼包，這不僅增加開銷且對解碼沒有幫助。在UAN中，重復編碼包會消耗額外的能量和浪費信道帶寬。因此，如果能有效利用4元環(huán)來產(chǎn)生不同的編碼包以實現(xiàn)原始包的解碼，將有效推進解碼進程。

1.2 ZD碼

傳統(tǒng)編碼僅采取簡單異或操作，編碼包長度與原始包長度相同。但ZD碼采取位級移位異或操作，因此ZD編碼包長度略長于原始包長。ZD編碼包長表示為l+r，其中l(wèi)表示為原始包長，r（r≥0）表示為編碼包的冗余度。給定度分布Ω（x）=∑ki=1Ωixi和移位分布Δ（x）=∑smi=0Δixi，其中Ωi表示為編碼包度為i的概率，k為原始包的總個數(shù)（即編碼包的最大度數(shù)），Δi表示偏移量為i的概率，sm表示為最大偏移量，其中Ω（1）=1，Δ（1）=1。ZD編碼過程如下：

a）根據(jù)度分布Ω（x）選擇編碼包的度d。

b）根據(jù)移位分布Δ（x）選取d個編碼偏移量（1，…，d）∈［0，sm］d，其中最小編碼偏移量為min=min{1，…，d}，每個原始包的編碼偏移量為zi=i-min，i∈［1，d］。

c）隨機選擇d個原始包，根據(jù)b）中的編碼偏移量分別進行移位操作，然后異或生成長度為l+r的編碼包，其中r=max{z1，z2，…，zd}且rEuclid Extra}@pl，這里僅考慮右移。

ZD的解碼過程通過圖3和4來進行闡述。如圖3和4所示，定義了每個原始包的長度為5（即l=5）。編碼包C1為原始包D1和D2逐位異或所得，即C1，1=D1，1D2，1，C1，2=D1，2D2，2，…，C1，5=D1，5D2，5，顯然D1和D2的編碼偏移量均為0。編碼包C2為D1和右移一位的D2逐位異或所得，D1和D2的編碼偏移量分別為0、1，此時r=1，C2的長度為6。編碼包的移位狀態(tài)表示為第二個原始包與第一個原始包的編碼偏移量之差，因此C1和C2的移位狀態(tài)分別為0和1。C1和C2均為原始包D1和D2編碼所得，但處于不同移位狀態(tài)。當接收方收到編碼包C1和C2，解碼器通過D1，1=C2，1實現(xiàn)D1，1解碼，進而依次解碼D2，1、D1，2、D2，2、D1，3、D2，3、D1，4、D2，4、D1，5和D2，5，從而恢復原始包D1和D2。因此，只要兩個編碼包均由相同的幾個原始包移位異或計算得出，且它們處于不同的移位狀態(tài)，便可實現(xiàn)原始包的解碼。

2 P-ZROFC-LF

針對ROFC-LF存在的不理想覆蓋和4元環(huán)問題，本文提出了基于優(yōu)先級與可Zigzag解碼的ROFC-LF（P-ZROFC-LF）。下面分別介紹P-ZROFC-LF的編碼和解碼過程。

2.1 P-ZROFC-LF編碼

P-ZROFC-LF在建立階段引入高優(yōu)先級的隨機選擇策略，并與ZD碼結合進行移位異或；完成階段與ROFC-LF類似，但在編碼過程中引入了ZD編碼。

P-ZROFC-LF在建立階段開始時，將所有原始包指定為相同優(yōu)先級。P-ZROFC-LF每次隨機選取優(yōu)先級最高的兩個原始包進行度2的ZD編碼，已選擇的原始包的優(yōu)先級會降1。

ZD編碼是在隨機選取的兩個原始包中進行的。首先，設置序號小的原始包Ds偏移量為0，然后根據(jù)移位分布Δ（x）=∑1i=-1Δixi產(chǎn)生另一個原始包Dl的偏移量為z。為減小存儲空間，偏移量僅在-1，0，1中進行取值。即在編碼過程中，序號較小的原始包不進行移位，序號較大的原始包右移z位。接下來，對移位后的兩個原始包進行逐位異或操作來產(chǎn)生編碼包。在傳統(tǒng)ZD編碼中，每個原始包均可進行偏移，且最大偏移量為zmax，從而產(chǎn)生z2max種可能的編碼結果。而所提方法僅產(chǎn)生三種可能的編碼結果，大大降低了編碼復雜度。經(jīng)編碼后，此時編碼包長度最長為l+1，最短為l。為使編碼包長度保持一致，當所選的兩個原始包偏移量均為0時，則在這兩個原始包前均補一位0，然后進行逐位異或，此時所有的編碼包長度均為l+1。當下次隨機選取兩個原始包時，若這兩個原始包已被同時選取過，即在編碼矩陣中出現(xiàn)4元環(huán)時，將根據(jù)上次偏移量動態(tài)調整移位分布Δ（x）來設置大序號原始包的偏移量，確保此次大序號編碼包偏移量在與上次不同的偏移量中高概率選擇，從而使接收方在收到兩次均由兩個相同原始包編碼時即可實現(xiàn)解碼。

在發(fā)送方使用優(yōu)先級狀態(tài)E（Pi）來表示每個節(jié)點的優(yōu)先級。對于k個原始包，剛進入建立階段時，原始包優(yōu)先級狀態(tài)E（Pi）表示為

E（Pi）={1，1，1，…，1，1，…，1，1，1}k bit

（6）

設原始包數(shù)量為1 000，即k=1 000，其中i為每個原始包的序號，每個比特位代表一個原始包，其對應的值為原始包的優(yōu)先級。初始時，P1=P2=…=P1 000=1，此時最高優(yōu)先級Maxp=1。首先，發(fā)送方隨機選取優(yōu)先級最高的兩個原始包進行移位異或編碼，其中每個原始包被選擇的概率均相同。若第一次隨機選擇的兩個原始包序號為3和998，則E（Pi）={1，1，0，…，1，1，…，0，1，1}。由于Maxp仍為1，所以將繼續(xù)在優(yōu)先級為1的原始包中進行選擇。重復該過程，直至所有原始包均參與過編碼，即Maxp=0。然后，在所有原始包中等概率隨機均勻選取原始包，持續(xù)生成度2編碼包，直至存在最大連通組件｜D｜=β0k。最后，隨機發(fā)送度1編碼包，直至最大連通組件全部解碼成功。

在完成階段，P-ZROFC-LF的編碼與ROFC-LF的編碼類似，均采用遞歸編碼策略。與ROFC-LF不同的是，P-ZROFC-LF進行度2編碼時引入ZD編碼。P-ZROFC-LF編碼算法具體流程如算法1所示。

算法1 P-ZROFC-LF編碼算法

初始化 將原始包的優(yōu)先級狀態(tài)E（Pi）初始化為{1，1，…，1，1}k，并記錄E（Pi）中的最大優(yōu)先級為Maxp和E（Pi）中1的個數(shù)為Num1。

while 原始包未全部解碼成功 do

if 單部圖中最大連通組件的大小未達到｜D｜=β0k then

if Maxp==1且Num1≥2 then

在優(yōu)先級為1的原始包中等概率隨機選取兩個原始包，被選取的

原始包優(yōu)先級降1，更新E（Pi）和Maxp并設置d=2。

else if Maxp==1且Num1==1 then

選取優(yōu)先級為1的一個原始包和在剩余的原始包中等概率隨機選

取一個原始包，被選取的原始包優(yōu)先級降1，更新E（Pi）和Maxp并設置d=2。

else if Maxp==0 then

在所有原始包中等概率隨機選取兩個原始包，并設置d=2。

end if

else

if 最大連通組件已解碼成功 then

根據(jù)預先設置的度1和度2編碼包的比值，在集合Wi（k-｜A｜，SNs）中等概率隨機選取一個原始包或二個原始包，并設置d=1或d=2。

else

"等概率隨機選取一個原始包，并設置d=1。

end if

end if

if d==2 then

if 第一次選取這兩個原始包 then

設置小序號原始包偏移量為0，大序號原始包根據(jù)移位分布Δ（x）設置偏移量，將這兩個原始包根據(jù)偏移量進行ZD編碼生成度2編碼包，將該編碼包發(fā)送到UAN信道中。

else

小序號原始包偏移量為0，根據(jù)上次大序號原始包偏移量動態(tài)調整移位分布Δ（x）設置偏移量，將原始包進行移位異或生成度2編碼包，將該編碼包發(fā)送到UAN信道中。

end if

else if" d==1" then

將度1編碼包發(fā)送到UAN信道中。

end if

end while

2.2 P-ZROFC-LF解碼

P-ZROFC-LF解碼采用BP算法［20］和ZD算法相結合的聯(lián)合解碼算法。BP算法在算法復雜度、解碼延時等方面具有不錯的優(yōu)勢，但解碼依賴于度1編碼包。因此，當解碼圖中存在度1編碼包時，P-ZROFC-LF采用BP解碼。而ZD解碼有效解決了BP算法中依賴于度1編碼包的問題，當接收方收到兩個均由相同原始包移位異或而形成的編碼包，但它們的移位狀態(tài)不同時即可實現(xiàn)解碼。其中，s（Ds，Dl）表示為原始包Ds和Dl所生成編碼包的移位狀態(tài)。由于Ds不進行移位，所以s（Ds，Dl）與Dl的偏移量相同。當存在不同移位狀態(tài)的重復包時，P-ZROFC-LF采用ZD算法。P-ZROFC-LF解碼算法流程如算法2所示。

算法2 P-ZROFC-LF解碼算法

while β＜1 do

接收度為dh的編碼包

if" dh==1 then

采用BP解碼，解碼對應原始包，并解碼原始包所在組件全部原始包。

所在組件大小為n1，將組件中所有原始包加入已解碼集合中。

β←β+n1k

else if" dh==2 then

if 原始包Ds和Dl未在同一組件中 then

在單部圖中建立連接，并計算移位狀態(tài)s（Ds，Dl）。

else

計算當前接收的移位狀態(tài)sn（Ds，Dl）。

if" sn（Ds，Dl）==s（Ds，Dl） then

丟棄編碼包。

else

恢復原始包Ds和Dl，并解碼原始包所在組件全部原始包。所

在組件的大小為n2，將組件中所有原始包加入已解碼集合中。

β←β+n2k

end if

end if

else

丟棄編碼包。

end if

end while

3 P-ZROFC-LF性能分析

3.1 編解碼分析

將水聲信道等效為擦除信道，下面分別分析在無信道擦除率和有信道擦除率（即ε=0和ε＞0）情況下，P-ZROFC-LF的編解碼。

3.1.1 無信道擦除率

P-ZROFC-LF在建立階段采用基于優(yōu)先級的隨機編碼策略。

a）每次選擇具有最大優(yōu)先級的原始包進行移位異或生成度2編碼包，直至所有原始包均參與過編碼，此時發(fā)送的編碼包數(shù)為k/2或「k/2。當值較大時，k/2與「k/2的差異很小，可忽略不計。則步驟a）發(fā)送的編碼包數(shù)為k/2，此時相當于構建了k/2個大小為2的連通組件，k′=k/2。

b）對k個原始包進行隨機選取生成度2編碼包，直至接收方的解碼圖中的最大組件達到｜D｜=β0k。基于隨機圖理論，當最大組件的大小達到｜D｜=β0k時，ROFC-LF對應的解碼圖為G=G（k，c/k），其中k（k-1）/2條邊都以c/k的概率獨立選取，c為每個原始包平均選擇次數(shù)，且滿足式（3）。在P-ZROFC-LF中，當最大組件的大小達到｜D｜=β0k時，相當于由多個大小為2的連通組件構成的最大連通組件，則P-ZROFC-LF對應的解碼圖為Gs=G（k′，c/k′），c為每個大小為2的連通組件平均選擇的次數(shù)。由于每個編碼包為兩個原始包移位異或編碼所得，所以在步驟b）需要發(fā)送的編碼包數(shù)量為k′c/2=kc/4。當建立階段結束時，P-ZROFC-LF需要發(fā)送度2編碼包數(shù)量期望為

NBuild-upd=2=12k+14kc

（7）

c）由于在建立階段引入了ZD碼，若兩次出現(xiàn)相同原始包移位異或時即可實現(xiàn)解碼，由此可以恢復大小為｜D｜=β0k的最大連通組件。此時P-ZROFC-LF在建立階段結束時，需要發(fā)送度1編碼包數(shù)量預計為0。為避免在建立階段未出現(xiàn)重復選取情況，需要發(fā)送度1編碼包數(shù)量期望為

NBuild-upd=1≥0

（8）

推理1 在完成階段，P-ZROFC-LF與ROFC-LF編碼方式類似，在未恢復原始包集合Wi（k-｜A｜，SNs）中選擇原始包發(fā)送度1或度2編碼包，所以完成階段發(fā)送的編碼包均有助于解碼。但由于反饋門限限制，存在反饋不及時而產(chǎn)生部分冗余包，所以完成階段需要發(fā)送的編碼包數(shù)量期望為

NCompletiond=1｜2≥（1-β0）k2［1-12（1-β0）c］

（9）

證明 根據(jù)文獻［13，15］，在k′個大小為2的節(jié)點構成的解碼圖G=G（k′，c/k′）中，除最大連通子圖外的其他子圖構成隨機圖G′=G′（t′，d′/t′），t′=（1-β0）k′表示大小為2的未解碼連通組件的數(shù)量，d′=（1-β0）c表示大小為2的連通組件的平均度。根據(jù)文獻［13］，在完成階段，平均恢復一個原始包需要一個有用編碼包。但由于P-ZROFC-LF對反饋進行限制，發(fā)送方不能及時更新集合Wi（k-｜A｜，SNs）而產(chǎn)生重復編碼包。因此在完成階段恢復t′個大小為2的節(jié)點，至少需要t′個有用編碼包，而在建立階段，步驟b）中已生成了t′d′/2個有用編碼包，則完成階段需要度1和度2編碼包的數(shù)量至少為

NCompletiond=1｜2=t′-12t′d′=（1-β0）k2［1-c（1-β0）2］

（10）

為恢復k個原始數(shù)據(jù)包，P-ZROFC-LF需要發(fā)送的編碼包總數(shù)預計為

E（N）P-ZROFC-LF=NBuild-upd=2+NBuild-upd=1+NCompletiond=1｜2≥12k+14kc+（1-β0）k2［1-c（1-β0）2］（11）

3.1.2 有信道擦除率

在建立階段的步驟a）中，發(fā)送方發(fā)送的編碼包數(shù)仍為k/2。由于ε＞0，在接收方收到了編碼包數(shù)為k（1-ε）/2。此時在接收方相當于在解碼圖中構建了k′（1-ε）個大小為2的連通組件和kε個大小為1的連通組件。

步驟b）中，由于ε值較小，所以在驟a）結束時大小為1的連通組件數(shù)量很少，且選擇大小為1的連通組件的概率是選擇大小為2的連通組件概率的一半。因此，在步驟b）中相當于在大小為2的組件中繼續(xù)構成大小為｜D｜=β0k的最大組件。由于ε＞0，當解碼圖中出現(xiàn)大小為｜D｜=β0k的連通組件時，相當于在ε=0的情況下最大組件的占比為β′0，表示為

β′0=β01-ε

（12）

每個大小為2的連通組件的平均選擇次數(shù)c′仍滿足式（3），則c′表示為

c′=-ln（1-β′0）β′0

（13）

此時，相當于由k′（1-ε）個大小為2的連通組件構成解碼圖Gε=G（k′（1-ε），c′/k′（1-ε））。所有大小為2的連通組件對應原始包的總個數(shù)為k（1-ε），則大小為2的連通組件被選擇的概率為1-ε。大小為2的連通組件的總度數(shù)為k′（1-ε）c′。因此，所有原始包的總度數(shù)為k′（1-ε）c′1-ε=k′c′。每個編碼包由兩個原始包進行移位異或生成，所以在步驟b）中所需的度2編碼包數(shù)期望為

12 k′（1-ε）c′1-ε=14kc′

（14）

因此，在信道擦除率ε＞0的情況下，建立階段結束時，P-ZROFC-LF需要發(fā)送度2編碼包數(shù)量期望為

NBuild-upd=2（ε）=12k+kc′4（1-ε）（15）

在建立階段的步驟c）中，需要發(fā)送度1編碼包數(shù)量期望為

NBuild-upd=1（ε）=1β0（1-ε）（16）

除最大連通子圖外的子圖是由大小為2的連通組件構成隨機圖G″=G（t″，d″/t″），其中t″為子圖中大小為2的連通組件數(shù)量，即未解碼的大小為2的連通組件的數(shù)量，t″=k′（1-ε）（1-β′0），d″為子圖中大小為2連通組件的平均度，d″=（1-β′0）c′。在完成階段恢復t″個大小為2的連通組件，接收方需要的編碼包數(shù)為t″-t″d″/2。若在建立階段的步驟a）所生成的大小為1的連通組件未參與建立階段步驟b）中最大組件的構造，則這些大小為1的連通組件在建立階段結束時仍未被恢復。即在完成階段開始時，存在未解碼的大小為1的連通組件數(shù)量為kε。為恢復這些大小為1的連通組件，接收方需要的編碼包數(shù)為kε。由于實際上大小為1的連通組件參與了最大組件的構建，所以當ε＞0時，在完成階段所需度1和度2編碼包數(shù)滿足

NCompletiond=1｜2（ε）＜t″-12t″d″+kε1-ε=k2（1-β′0）1-12（1-β′0）c′+kε1-ε

（17）

當ε＞0時，為恢復k個原始包，P-ZROFC-LF需要發(fā)送的編碼包總數(shù)上界為

E（Nε）P-ZROFC-LF=NBuild-upd=2（ε）+NBuild-upd=1（ε）+NCompletiond=1｜2（ε）＜12k+kc′4（1-ε）+1β0（1-ε）+k2（1-β′0）1-12（1-β′0）c′+kε1-ε

（18）

當信道擦除率ε＞0時，由于反饋包中存在所有原始包的編解碼狀態(tài)，可以動態(tài)更新集合Wi（k-｜A｜，SNs）。即使由于高信道擦除率未能及時反饋而產(chǎn)生冗余包，P-ZROFC-LF引入的ZD碼在出現(xiàn)選擇兩個相同原始包異或編碼時仍可實現(xiàn)解碼。因此，當信道擦除概率ε較大時，P-ZROFC-LF對于所需編碼包數(shù)仍具有一定優(yōu)勢。

3.2 反饋分析

在建立階段，當最大組件達到｜D｜=β0k或最大組件被成功解碼時，接收方發(fā)送一次反饋，所以在建立階段發(fā)送兩次反饋，即NBuild-upfeedback=2；在完成階段，當Δβ的閾值達到反饋門限σ時才進行反饋。

在完成階段，接收方發(fā)送的反饋包的數(shù)量依賴于兩種情形：a）完成階段度1編碼包的數(shù)量NCompletiond=1；b）完成階段度2的重復編碼包的數(shù)量NCompletiond=2-rc。因此，P-ZROFC-LF在完成階段的反饋數(shù)滿足

NCompletionfeedback≤NCompletiond=1+NCompletion2-rc

（19）

對于P-ZROFC-LF，產(chǎn)生的反饋包總數(shù)定義為

NP-ZROFC-LFfeedback=NBuild-upfeedback+NCompletiond=1+NCompletiond=2-rc≤NCompletiond=1+NCompletiond=2-rc+2

（20）

由于P-ZROFC-LF在建立階段采用基于高優(yōu)先級的隨機編碼策略，在建立階段已減少連通組件數(shù)，所以在完成階段僅需少量編碼包。與ROFC-LF相比，P-ZROFC-LF實現(xiàn)更少的反饋，更適用于UAN。

3.3 開銷分析

當發(fā)送方想要發(fā)送k個原始包，發(fā)送方實際發(fā)送的總編碼包數(shù)Ntotal減去k為冗余編碼包數(shù)，開銷Pr定義為冗余編碼包數(shù)與k的比值，即

Pr=Ntotal-kk

（21）

根據(jù)式（11）（18）和（21）計算出P-ZROFC-LF在ε=0和ε＞0情況下的開銷分別滿足：

PP-ZROFC-LFr=E（N）P-ZROFC-LF-kk≥-12+14c+1kβ0+（1-β0）2［1-c（1-β0）2］

（22）

PP-ZROFC-LFr（ε）=E（Nε）P-ZROFC-LF-kk＜ε1-ε+c′4（1-ε）+1β0k（1-ε）+12（1-β′0）1-12（1-β′0）c′-12

（23）

4 仿真實驗

在本章中，為驗證本文所提P-ZROFC-LF的性能，與OFC［12］、IOFC-SLDD［13］、IOFC［14］、OFC-Pre-EC［15］、ZDOF-BDM［16］、OFCNB-EBDS［17］、ROFC-LF［18］和SROFC-LF［19］進行對比實驗。圖中“Analysis”代表理論分析結果，“Sim”代表仿真實驗結果。由于每篇文獻中所提編碼機制的仿真參數(shù)存在差異，將本文P-ZROFC-LF分別使用對比機制的參數(shù)進行仿真實驗，并將結果進行對比分析。

在ROFC-LF中，將β0設為0.5實現(xiàn)了最小開銷。因此，首先將β0設置為0.5。當ε=0和β=0.5時，P-ZROFC-LF在α不同取值下對編碼包數(shù)和反饋包數(shù)的影響如圖5所示。

根據(jù)圖5（a），當α取值在0.3～0.5，所需編碼包數(shù)與理論分析結果基本保持一致；α取值在其他范圍內，所需編碼包數(shù)略高于理論分析結果。根據(jù)圖5（b），隨著α增加，所需反饋包數(shù)明顯增加。綜合考慮編碼包數(shù)和反饋包數(shù)，α=0.1時的效果最好，因此圖6～10將α取值為0.1。根據(jù)文獻［18］，當k=1 000、 β0=0.5和α=0.1時，ROFC-LF恢復所有原始包所需的平均反饋包數(shù)量為16.5。在圖5（b）中可以發(fā)現(xiàn)，P-ZROFC-LF在相同條件下所需反饋包數(shù)比ROFC-LF所需的反饋包數(shù)減少了18%。

圖6給出ε=0和k=1 000時，β0取值對開銷的影響。可以發(fā)現(xiàn)，對所有編碼機制而言，開銷均會隨β0值的增加而增加。在UAN中，開銷越小越適合。因所有編碼機制在β0=0.5時的仿真開銷達到最低，所以本文一般將β0取值為0.5。根據(jù)文獻［12，15，18］可知，當β0=0.5時，P-ZROFC-LF相較于OFC、IOFC、ROFC-LF的仿真開銷分別減少了0.163 6、0.070 2和0.017 6。

圖7給出β0=0.5和k=1 000時，P-ZROFC-LF在ε不同取值下傳輸編碼包數(shù)與恢復原始包數(shù)之間的關系。圖中詳細呈現(xiàn)了在ε=0、ε=0.1和ε=0.2的情況下，P-ZROFC-LF傳輸編碼包數(shù)的理論與仿真結果的比較。從圖中可以發(fā)現(xiàn)，在建立階段完成時，理論計算得出的編碼包數(shù)量與仿真實驗中得到的結果高度一致。進一步分析無損信道和有損信道兩種情況下的完成階段，發(fā)現(xiàn)兩種情況下的理論分析值與仿真結果均有較好的一致性。

圖8給出β0=0.5和k=1 000時，傳輸編碼包數(shù)與恢復原始包數(shù)之間的關系。在發(fā)送650個數(shù)據(jù)包之前，P-ZROFC-LF相比于其他編碼具有較好的中間解碼能力。由于其他編碼在建立階段開始時，僅發(fā)送度2編碼包，所以在構建最大連通分量之前，不會恢復任何原始包。而P-ZROFC-LF采用ZD移位編碼，在建立階段如果出現(xiàn)4元環(huán)即可實現(xiàn)解碼，并且對于恢復所有原始包而言，P-ZROFC-LF所需編碼包數(shù)最少。

圖9給出ε=0、 β0=0.65和k=1 000時，不同機制的傳輸編碼包數(shù)與恢復原始包數(shù)之間的關系。在發(fā)送808個數(shù)據(jù)包之前，ZDOF-BDM、OFC-Pre-EC和P-ZROFC-LF顯示出較強的中間解碼性能，其中ZDOF-BDM表現(xiàn)最佳。而在發(fā)送超過904個數(shù)據(jù)包后，P-ZROFC-LF和IOFC-SLDD展現(xiàn)了更優(yōu)的中間解碼性能。同時，在恢復1 000個原始包時，IOFC-SLDD和P-ZROFC-LF所需的編碼包數(shù)最少，均適合于UAN。

圖10給出ε=0.1和β0=0.5時，原始包數(shù)k對開銷和反饋包數(shù)的影響。在開銷方面，IOFC和OFC始終具有較高的開銷并基本保持恒定。SROFC-LF的開銷隨k值的增加而逐漸降低。當k≤2 000時，P-ZROFC-LF的開銷低于SROFC-LF；然而，當k＞2 000時，P-ZROFC-LF的開銷雖略高于SROFC-LF，但差距很小。在反饋包數(shù)量方面，IOFC、OFC以及SROFC-LF的反饋包數(shù)量均隨k值的增加而顯著上升，而P-ZROFC-LF的反饋包數(shù)量一直較低。由于SROFC-LF的反饋閾值設置為δ＞8/k，在k=1 500時，SROFC-LF和P-ZROFC-LF的反饋閾值幾乎一致。因此，當k＞1 500時，SROFC-LF反饋包數(shù)量明顯增加且多于P-ZROFC-LF的反饋包數(shù)。對于UAN而言，過多的反饋包會占用寶貴的信道資源并且增加通信時延；較高的開銷意味著更多無效編碼包的產(chǎn)生，這會增加水聲通信設備的能耗并降低信道帶寬效率。綜合來看，P-ZROFC-LF和SROFC-LF均適合于UAN。

表1給出ε=0.2、β0=0.5和k=1 000時，P-ZROFC-LF與其他在線噴泉碼編碼機制在所需編碼包數(shù)和反饋包數(shù)的比較。可以發(fā)現(xiàn)，P-ZROFC-LF在編碼包數(shù)和反饋包數(shù)上具有不錯的性能，更適合于信道擦除率略高的UAN。

表2分別為ε=0、 β0=0.65和k=1 000、2 000、3 000時所需的編碼包數(shù)和反饋包數(shù)。由此可見，P-ZROFC-LF具有最少的編碼包數(shù)和反饋包數(shù)，更適合UAN。

5 結束語

本文為解決ROFC-LF存在的不理想覆蓋和4元環(huán)的問題，提出了基于優(yōu)先級與可Zigzag解碼的ROFC-LF（P-ZROFC-LF），根據(jù)隨機圖理論分析P-ZROFC-LF所需編碼包數(shù)和原始包數(shù)之間的關系。理論分析與仿真結果表明，與大部分在線噴泉碼相比，P-ZROFC-LF在開銷和反饋方面具有更好的性能，更好地適用于UAN。在未來的研究工作中，將所提編碼應用于可靠傳輸機制或傳輸協(xié)議，從而進一步提高水聲網(wǎng)絡的可靠性和吞吐量。

參考文獻

［1］Jiang Shengming. On reliable data transfer in underwater acoustic networks： a survey from networking perspective ［J］. IEEE Communications Surveys amp; Tutorials， 2018， 20 （2）： 1036-1055.

［2］Zhao Haihong， Li Xinbin， Yan Lei， et al. Partial expert-based adversarial relay learning strategy for underwater acoustic sensor networks ［J］. IEEE Sensors Journal， 2022， 22 （8）： 7961-7970.

［3］Wei Xiaohui， Guo Hao， Wang Xingwang， et al. Reliable data collection techniques in underwater wireless sensor networks： a survey ［J］. IEEE Communications Surveys amp; Tutorials， 2021， 24 （1）： 404-431.

［4］周文軒， 周杰， 劉少云， 等. 水聲環(huán)境UWA信道散射模型參數(shù)仿真分析 ［J］. 計算機工程與應用， 2020， 56 （24）： 229-235. （Zhou Wenxuan， Zhou Jie， Liu Shaoyun， et al. Parameter simulation analysis of UWA channel scattering model in underwater acoustic environment ［J］. Computer Engineering and Applications， 2020， 56 （24）： 229-235.）

［5］Rizzo L. Effective erasure codes for reliable computer communication protocols ［J］. ACM SIGCOMM Computer Communication Review， 1999， 27 （2）： 24-36.

［6］Gao M， Soh W S， Tao M. A transmission scheme for continuous ARQ protocols over underwater acoustic channels ［C］// Proc of IEEE International Conference on Communications. Piscataway，NJ：IEEE Press， 2009： 14-18.

［7］黃靖軒， 費澤松， 李歡. 無速率編碼及其應用綜述 ［J］. 無線電通信技術， 2020， 46 （1）： 44-54. （Huang Jingxuan， Fei Zesong， Li Huan. Overview of rateless codes and their applications ［J］. Radio Communications Technology， 2020， 46 （1）： 44-54.）

［8］Mackay， David J C. Fountain codes ［J］. IEE Proceedings Communications， 2005， 152 （6）： 1062-1068.

［9］Liang Mingshen， Duan Jinjue， Zhao Danfeng. Optimal redundancy control strategy for fountain code-based underwater acoustic communication ［J］. IEEE Access， 2018， 6： 69321-69334.

［10］Sprea N， Bashir M， Truhachev D， et al. BATS coding for underwater acoustic communication networks ［C］// Proc of OCEANS. Piscata-way，NJ：IEEE Press， 2019： 1-10.

［11］Kaythry P， Kishore R， Priyanka V N. Performance analysis of LT code-based HARQ error control in underwater acoustic sensor networks ［J］. Journal of Marine Engineering amp; Technology， 2022， 21 （1）： 54-64.

［12］Cassuto Y， Shokrollahi A. Online fountain codes with low overhead ［J］. IEEE Trans on Information Theory， 2015， 61 （6）： 3137-3149.

［13］Huang Taiqi， Yi Benshun. Improved online fountain codes based on shaping for left degree distribution ［J］. AEU-International Journal of Electronics and Communications， 2017， 79： 9-15.

［14］Huang Jingxuan， Fei Zesong， Cao Congzhe， et al. Performance analy-sis and improvement of online fountain codes ［J］. IEEE Trans on Communications， 2018， 66 （12）： 5916-5926.

［15］Zhao Yuli， Zhang Yin， Francis C M L， et al. Improved online fountain codes ［J］. IET Communications， 2018， 12 （8）： 2297-2304.

［16］Shi Pengcheng， Wang Zhenyong， Li Dezhi， et al. Zigzag decodable online fountain codes with high intermediate symbol recovery rates ［J］. IEEE Trans on Communications， 2020， 68 （11）： 6629-6641.

［17］Xiao Yongwei， Zhang Yasheng， Huang Jingxuan. Estimation based feedback reduction for online fountain codes ［C］// Proc of the 3rd Information Communication Technologies Conference. Piscataway，NJ：IEEE Press， 2022： 194-198.

［18］Liu Xiuxiu， Du Xiujuan， Zhang Jiliang， et al. ROFC-LF： recursive online fountain code with limited feedback for underwater acoustic networks ［J］. IEEE Trans on Communications， 2022， 70 （7）： 4327-4342.

［19］柳秀秀， 杜秀娟， 韓多亮. 水聲網(wǎng)絡按序遞歸與限制反饋的在線噴泉碼算法與分析 ［J］. 電子學報， 2023， 51 （7）： 1734-1740. （Liu Xiuxiu， Du Xiujuan， Han Duoliang. Algorithm and analysis of sequential recursive online fountain code with limited feedback in underwater acoustic networks ［J］. Acta Electronica Sinica， 2023， 51 （7）： 1734-1740.）

［20］王麗娟， 杜秀娟， 李沖. 面向水聲網(wǎng)絡可靠傳輸?shù)腇DR編解碼算法 ［J］. 通信學報， 2020， 41 （4）： 81-91. （Wang Lijuan， Du Xiujuan， Li Chong. FDR coding and decoding algorithm for reliable transmission in underwater acoustic network［J］. Journal on Communications， 2020， 41 （4）： 81-91.）

［21］Motwani R， Raghavan P. Randomized algorithms ［J］. ACM Computing Surveys， 1996， 28 （1）： 33-37.

［22］Hussain I， Xiao Ming， Rasmussen L. Buffer-based distributed LT codes ［J］. IEEE Trans on Communications， 2014， 62 （11）： 3725-3739.