Two-hop relay algorithm with packet redundancy and erasure coding in MANETs

Two-hop relay algorithm serves as a class of promising routing protocols for mobile ad hoc networks (MANETs). This paper proposes a general two-hop relay algorithm with combination of both packet redundancy and erasure coding techniques, and focuses on the delay performance there. Our new algorithm is abbreviated as 2HR-(f, x), where f is the packet redundancy limit and x is an erasure coding parameter. The 2HR-(f, x) covers available two-hop rely algorithms as special cases, such as the two-hop relay algorithm with packet redundancy (f > 1, x = 1), and two-hop relay algorithm with erasure coding(f = 1, x > 1). To investigate the delay performance of our proposed 2HR-(f, x) algorithm, a multidimensional Markov chain model is developed, which depicts the complicated system state transitions. With the help of the Markov chain model, closed-form expected delivery delay is derived. Extensive simulations are conducted to verify the efficiency of our Markov chain model and the correctness of the derived delivery delay result. Finally, numerical results are provided to examine how network parameters will affect the delivery delay performance of the 2HR-(f, x) algorithm.