Redundancy Minimizing Techniques for Robust Transmission in Wireless Networks

다국어 초록 (Multilingual Abstract)

In this paper, we consider a wireless multiple path network
in which a transmitting node would like to send a message
to the receiving node with a certain probability of success. These
two nodes are separated by N erasure paths, and we devise two
algorithms to determine minimum redundancy and optimal symbol
allocation for this setup. We discuss the case with N = 3
and then extend the case to an arbitrary number of paths. One
of the algorithms minimum redundancy algorithm in exponential
time is shown to be optimal in several cases, but has exponential
running time. The other algorithm, minimum redundancy algorithm
in polynomial time, is sub-optimal but has polynomial worstcase
running time. These algorithms are based off the theory of
maximum-distance separable codes. We apply the MRAET algorithm
on maximum-distance separable, Luby transform, and Raptor
codes and compare their performance.

참고문헌 (Reference)

1 J. Lee, "Split multipath routing with maximally disjoint paths in ad hoc networks" 3201-3205, 2001

2 P. Papadimitratos, "Secure message transmission in mobile ad hoc networks" Ad Hoc Netw 193-209, 2003

3 S. B. Wicker, "Reed Solomon Codes and Their Applications" IEEE Press 1994

4 A. Shokrollahi, "Raptor codes" 52 (52): 2551-2567, 2006

5 A. Kacewicz, "Optimizing redundancy using MDS codes and dynamic symbol allocation in mobile ad hoc networks" Princeton University 2008

6 E. Maneva, "New model for rigorous analysis of LT codes" 2006

7 M. Luby, "LT-codes" 271-280, 2002

8 T. H. Cormen, "Introduction to Algorithms. 2nd ed" MIT Press 2001

9 David J.C. MacKay, "Information Theory, Inference, and Learning Algorithms" Cambridge University Press 2003

10 P. Cataldi, "Implementation and performance evaluation of LT and Raptor codes for multimedia applications" 2006

11 Karp, M. Luby, "Finite length analysis of LT codes" 2004

12 S. B. Wicker, "Error Control Systems for Digital Communication and Storage" Prentice Hall 1995

13 Thomas M. Cover, "Elements of Information Theory" John-Wiley and Sons, Inc 2006

14 M.Luby, "Efficient erasure correcting codes" 47 (47): 569-584, 2001

15 M. O. Rabin, "Efficient dispersal of information for security, load balancing, and fault tolerance" 335-348, 1989

16 A. Tsirigos, "Analysis of multipath routing, part 2: Mitigation of the effects of frequently changing network topologies" 3 (3): 2004

17 A. Tsirigos, "Analysis of multipath routing, part 1: The dffect on the packet delivery ratio" 3 (3): 2004