On the feasibility of precoding-based network alignment for three unicast sessions
作者： Chun Meng , Abinesh Ramakrishnan , Athina Markopoulou , Syed Ali Jafar
DOI: 10.1109/ISIT.2012.6283630
关键词: Mathematics 、 Minimum cut 、 Theoretical computer science 、 Graph (abstract data type) 、 Directed acyclic graph 、 Unicast 、 Linear network coding 、 Directed graph 、 Precoding 、 Zero-forcing precoding
摘要: We consider the problem of network coding across three unicast sessions over a directed acyclic graph, when each session has min-cut one. Previous work by Das et al. adapted precoding-based interference alignment technique, originally developed for wireless channel, specifically to this problem. refer approach as (PBNA). Similar setting, PBNA asymptotically achieves half minimum cut; different from its feasibility depends on graph structure. provided set conditions with respect particular precoding matrix. However, consisted an infinite number conditions, which is impossible check in practice. Furthermore, were purely algebraic, without interpretation regards In paper, we first prove that Das. al are also necessary any Then, using two graph-related properties and degree-counting reduce just four conditions. This reduction enables efficient algorithm checking given graph.
harvard.edu
arxiv.org
sci-hub.se 参考文章(12)
Robert Kleinberg, April Rasala Lehman, Kamal Jain, Micah Adler, Nicholas J. A. Harvey, On the capacity of information networks symposium on discrete algorithms. pp. 241- 250 ,(2006) , 10.5555/1109557.1109585
V.R. Cadambe, S.A. Jafar, Interference Alignment and Degrees of Freedom of the $K$ -User Interference Channel IEEE Transactions on Information Theory. ,vol. 54, pp. 3425- 3441 ,(2008) , 10.1109/TIT.2008.926344
Abhik Das, Sriram Vishwanath, Syed Jafar, Athina Markopoulou, Network coding for multiple unicasts: An interference alignment approach international symposium on information theory. pp. 1878- 1882 ,(2010) , 10.1109/ISIT.2010.5513311
April Rasala Lehman, Eric Lehman, Complexity classification of network information flow problems symposium on discrete algorithms. pp. 142- 150 ,(2004) , 10.5555/982792.982814
T. Ho, M. Medard, R. Koetter, D.R. Karger, M. Effros, J. Shi, B. Leong, A Random Linear Network Coding Approach to Multicast IEEE Transactions on Information Theory. ,vol. 52, pp. 4413- 4430 ,(2006) , 10.1109/TIT.2006.881746
Jaemin Han, Chih-Chun Wang, Ness B. Shroff, Analysis of precoding-based intersession network coding and the corresponding 3-unicast interference alignment scheme allerton conference on communication, control, and computing. pp. 1033- 1040 ,(2011) , 10.1109/ALLERTON.2011.6120281
M. Kim, M. Medard, U.-M. O'Reilly, D. Traskov, An Evolutionary Approach To Inter-Session Network Coding international conference on computer communications. pp. 450- 458 ,(2009) , 10.1109/INFCOM.2009.5061950
R. Ahlswede, Ning Cai, S.-Y.R. Li, R.W. Yeung, Network information flow IEEE Transactions on Information Theory. ,vol. 46, pp. 1204- 1216 ,(2000) , 10.1109/18.850663
N.J.A. Harvey, R. Kleinberg, A.R. Lehman, On the capacity of information networks IEEE Transactions on Information Theory. ,vol. 14, pp. 2345- 2364 ,(2006) , 10.1109/TIT.2006.874531
Abinesh Ramakrishnan, Abhik Das, Hamed Maleki, Athina Markopoulou, Syed Jafar, Sriram Vishwanath, Network coding for three unicast sessions: Interference alignment approaches allerton conference on communication, control, and computing. pp. 1054- 1061 ,(2010) , 10.1109/ALLERTON.2010.5707026