2008/07/08 by Yingda Chen, Chen, Yingda, Shalinee Kishore +1
Computer Science · Mathematics · #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Ad Hoc Networks #Wireless Networks and Protocols #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.0807.1313
22 pages, 5 figures, submitted to IEEE Transactions on Communications
openalex publication_date 2008/07/08 · arxiv created 2009/02/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Randomized network coding (RNC) greatly reduces the complexity of implementing network coding in large-scale, heterogeneous networks. This paper examines two tradeoffs in applying RNC: The first studies how the performance of RNC varies with a node's randomizing capabilities. Specifically, a limited randomized network coding (L-RNC) scheme - in which intermediate nodes perform randomized encoding based on only a limited number of random coefficients - is proposed and its performance bounds are analyzed. Such a L-RNC approach is applicable to networks in which nodes have either limited computation/storage capacity or have ambiguity about downstream edge connectivity (e.g., as in ad hoc sensor networks). A second tradeoff studied here examines the relationship between the reliability and the capacity gains of generalized RNC, i.e., how the outage probability of RNC relates to the transmission rate at the source node. This tradeoff reveals that significant reductions in outage probability are possible when the source transmits deliberately and only slightly below network capacity. This approach provides an effective means to improve the feasibility probability of RNC when the size of the finite field is fixed.