Priority-Based and Zigzag Decodable Online Fountain Codes for Underwater Acoustic Networks

0
0
0

Priority-Based and Zigzag Decodable Online Fountain Codes for Underwater Acoustic Networks

Introduction

Underwater acoustic networks (UANs) play a crucial role in marine exploration, environmental monitoring, and disaster prevention. However, UANs face significant challenges due to their unique characteristics, including long propagation delays, high bit error rates, low bandwidth, and half-duplex communication. These challenges severely impact the reliability of data transmission in underwater environments. Traditional error control mechanisms, such as forward error correction (FEC) and automatic repeat request (ARQ), are inadequate for UANs due to their fixed coding rates and reliance on feedback, which introduce inefficiencies in dynamic underwater channels.

Digital fountain codes, particularly online fountain codes (OFCs), have emerged as a promising solution for UANs due to their rate-adaptive nature, low encoding/decoding complexity, and efficient feedback mechanisms. However, existing recursive online fountain codes with limited feedback (ROFC-LF) suffer from two major issues: (1) non-ideal coverage, where not all original packets participate in the encoding process during the buildup phase, leading to increased overhead and frequent feedback; and (2) 4-membered rings, where redundant encoded packets are generated, further increasing overhead.

To address these challenges, this paper proposes Priority-based and Zigzag-decodable ROFC-LF (P-ZROFC-LF), an improved online fountain coding scheme tailored for UANs. P-ZROFC-LF introduces a priority-based encoding strategy to ensure full coverage of original packets and incorporates Zigzag-decodable (ZD) coding to convert useless encoded packets into useful ones, thereby improving decoding performance. Theoretical analysis and simulation results demonstrate that P-ZROFC-LF significantly reduces feedback and overhead compared to existing online fountain codes, making it highly suitable for UANs.

Background and Related Work

Challenges in Underwater Acoustic Networks

UANs rely on acoustic signals for communication, which propagate much slower than radio waves, resulting in long propagation delays. Additionally, underwater channels are prone to high bit error rates due to multipath fading, Doppler effects, and ambient noise. These factors make reliable data transmission a significant challenge. Traditional error control mechanisms, such as FEC and ARQ, are inefficient in UANs because: • FEC requires a fixed redundancy rate, which is unsuitable for time-varying underwater channels.

• ARQ relies on frequent feedback, increasing communication delays and energy consumption.

Online Fountain Codes for UANs

Online fountain codes (OFCs) are a class of rateless codes that dynamically adjust their coding rate based on channel conditions. Unlike traditional fountain codes, OFCs incorporate feedback mechanisms to optimize encoding and decoding efficiency. Several variants of OFCs have been proposed to enhance performance in UANs: • Improved OFC with Shaped Left Degree Distribution (IOFC-SLDD) prioritizes packets with the smallest degrees to reduce overhead.

• OFC with Pre-Buildup and Enhanced Completion Phase (OFC-Pre-EC) improves intermediate decoding by sending degree-1 packets early.

• Zigzag-Decodable OFC with Buffer Decoding (ZDOF-BDM) enhances decoding efficiency by leveraging ZD coding.

• Recursive OFC with Limited Feedback (ROFC-LF) reduces feedback frequency but suffers from non-ideal coverage and 4-membered rings.

Despite these advancements, existing OFCs still exhibit inefficiencies in UANs, particularly in terms of feedback overhead and redundant packet generation.

The Proposed P-ZROFC-LF Scheme

Key Innovations

P-ZROFC-LF introduces two key improvements over ROFC-LF:

  1. Priority-Based Encoding in the Buildup Phase • Instead of randomly selecting packets for encoding, P-ZROFC-LF assigns priorities to original packets.

• Packets with the highest priority are selected first, ensuring that all packets participate in encoding.

• This strategy minimizes the number of isolated packets (size-1 components), reducing the need for additional encoding in the completion phase.

  1. Zigzag-Decodable (ZD) Coding • Traditional OFCs rely on simple XOR operations, which can produce redundant packets when the same pair of packets is encoded multiple times (4-membered rings).

• ZD coding introduces bit-level shifting and XORing, allowing two encoded packets generated from the same pair of original packets to be decoded without requiring degree-1 packets.

• This reduces dependency on degree-1 packets and improves decoding efficiency.

Encoding Process

The encoding process of P-ZROFC-LF consists of two phases:

  1. Buildup Phase • All original packets are initialized with the same priority.

• The encoder selects two packets with the highest priority and performs ZD coding.

• The priority of selected packets is decremented to ensure all packets are eventually encoded.

• Encoding continues until a large connected component (covering a fraction β₀ of packets) is formed.

  1. Completion Phase • Similar to ROFC-LF, the encoder uses feedback to identify undecoded packets.

• Degree-1 and degree-2 packets are generated adaptively based on feedback.

• ZD coding is applied to degree-2 packets to minimize redundancy.

Decoding Process

P-ZROFC-LF employs a combined belief propagation (BP) and ZD decoding strategy: • BP decoding is used when degree-1 packets are available.

• ZD decoding is triggered when two encoded packets generated from the same pair of original packets are received in different shift states.

• This hybrid approach reduces dependency on degree-1 packets and accelerates decoding.

Performance Analysis

Theoretical Insights

Using random graph theory, we analyze the relationship between the number of encoded packets and original packets in P-ZROFC-LF. Key findings include: • Reduced Overhead: P-ZROFC-LF minimizes redundant packets by ensuring full coverage in the buildup phase and leveraging ZD coding.

• Lower Feedback Frequency: By reducing the number of isolated packets, P-ZROFC-LF requires fewer feedback transmissions compared to ROFC-LF.

Simulation Results

Extensive simulations compare P-ZROFC-LF with existing OFCs under various conditions (ε = 0, ε = 0.1, ε = 0.2). Key results include:

  1. Overhead Reduction • P-ZROFC-LF achieves a 0.0176 lower overhead than ROFC-LF when β₀ = 0.5.

• Compared to OFC and IOFC, P-ZROFC-LF reduces overhead by 0.1636 and 0.0702, respectively.

  1. Feedback Efficiency • P-ZROFC-LF reduces feedback transmissions by 18% compared to ROFC-LF.

• As the number of packets (k) increases, P-ZROFC-LF maintains low feedback rates, unlike SROFC-LF, which exhibits degraded performance.

  1. Intermediate Decoding Performance • P-ZROFC-LF recovers packets earlier in the buildup phase due to ZD coding.

• For k = 1000, P-ZROFC-LF requires fewer encoded packets than ZDOF-BDM and OFC-Pre-EC to achieve full recovery.

  1. Robustness to Channel Errors • At ε = 0.2, P-ZROFC-LF outperforms ROFC-LF and SROFC-LF in both overhead and feedback efficiency.

Conclusion

P-ZROFC-LF addresses the limitations of ROFC-LF by introducing priority-based encoding and Zigzag-decodable coding, making it highly efficient for UANs. Theoretical and simulation results demonstrate that P-ZROFC-LF significantly reduces overhead and feedback while improving decoding performance. Future work will focus on integrating P-ZROFC-LF into UAN transport protocols to further enhance reliability and throughput.

For more details, refer to the original paper: https://doi.org/10.19734/j.issn.1001-3695.2024.07.0246

Was this helpful?

0 / 0