Latest Article
Exact Decoding Probability of Random Linear Network Coding for Combinatorial Networks
LI Fang1,2
1. School of Information, Xi’an University of Finance and Economics, Xi’an 710100, Shaanxi, China;2. State Key Laboratory of Integrated Services Networks (ISN), Xidian University, Xi’an 710071, Shaanxi, China
Combinatorial networks are widely applied in many practical scenarios. In this paper, we compute the closed-form probability expressions of successful decoding at a sink and at all sinks in the multicast scenario, in which one source sends messages to k  destinations through m  relays using random linear network coding over a Galois field. The formulation at a (all) sink(s) represents the impact of major parameters, i.e., the size of field, the number of relays (and sinks) and provides theoretical groundings to numerical results in the literature. Such condition maps to the receivers’ capability to decode the original information and its mathematical characterization is helpful to design the cod-ing. In addition, numerical results show that, under a fixed exact decoding probability, the required field size can be minimized.
Key words:random linear network coding;successful probability; combinatorial networks
CLC number:TP 391.4
[1] Yeung R W, Zhang Z. Distributed source coding for satellite communications [J]. IEEE Transactions on Information Theory, 1999, 45(4): 1111-1120.
[2] Ahlswede R, Cai N, Li S Y, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.
[3] Li S Y, Yeung R W, Cai N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.
[4] Koetter R, Médard M. An algebraic approach to network coding[J]. IEEE/ACM Trans Network, 2003,11(5): 782-795.
[5] Jaggi S, Sanders P, Chou P A, et al. Polynomial time algo-rithms for multicast network code construction[J]. IEEE Transactions on Information Theory, 2005, 51(6): 1973- 1982.
[6] Fragouli C, Soljanin E. Network Coding Fundamentals[M]. Boston-Delft:Now Publishers Inc, 2007.
[7] Yeung R W. Information Theory and Network Coding[M]. New York: Springer-Verlag, 2008.
[8] Ho T, M´edard M, Shi J, et al. On randomized network cod-Ing[J]. Proceedings of the Annual Allerton Conference on Communication Control and Computing, 2003, 41(1): 11-20.
[9] Ho T, M´edard M, Koetter R, et al. A random linear network coding approach to multicast [J]. IEEE Transactions on  Information Theory, 2006, 52(10): 4413-4430.
[10] Balli H, Yan X, Zhang Z. On randomized linear network co-
des and their error correction capabilities[J]. IEEE Transcti-
ons on Information Theory, 2009, 55(7): 3148- 3160.
[11] Trullols-Cruces O, Barcelo-Ordinas J M, Fiore M. Exact de-
coding probability under random linear network coding[J]. IEEE Communications Letters, 2011, 15(1): 67 -69. 
[12] Zhao X B. Notes on ‘exact decoding probability under ran-dom linear network coding’ [J]. IEEE Communications Let-ters, 2012, 16(5): 720-721. 
[13] Chiasserini Carla-Fabiana, Viterbo Emanuele, Claudio Casetti. Decoding probability in random linear network cod-ding with packet losses[J]. IEEE Communications Letters, 2013, 17(11): 2128 - 2131.
[14] Li F, Guo W M. An efficient polynomial time algorithm for robust multicast network code construction[J]. IEEE Com-munications Letters, 2015, 19(2): 143-146. 
[15] Gai Y, Krishnamachari B, Liu M. Online learning for com-binatorial network optimization with restless Markovian re-wards[C]// 2012 9th Annual IEEE Communications Society Conference on SECON. Washington D C: IEEE, 2012: 28-36.
[16] Gai Y, Krishnamachari B, Jain R. Combinatorial network optimization with unknown variables: Multiarmed bandits with linear rewards and individual observations[J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1466-1478.
[17] Croitoru M, Croitoru C. Generalised network flows for combinatorial auctions[C]// 2011 IEEE/WIC/ACM Interna-tional Conference on WI-IAT, 2011, 2: 313-316.
[18] Cai N. Network Coding Theory[M]. Boston-Delft: Now Pub-lishers Inc, 2006. 
[19] Van Lint J H, Wilson R M. A Course in Combinatorics[M]. Cambridge: Cambridge University Press, 2001.