Upper bound on function computation in directed acyclic networks
作者： Cupjin Huang , Zihan Tan , Shenghao Yang
关键词:
摘要: Function computation in directed acyclic networks is considered, where a sink node wants to compute target function with the inputs generated at multiple source nodes. The network links are error-free but capacity-limited, and intermediate nodes perform coding. required be computed zero error. computing rate of code measured by average number times that can for one use network. We propose cut-set bound on using an equivalence relation associated function. Our holds general functions topologies. also show our tight some special cases capacity characterized.
arxiv.org
sci-hub.se 参考文章(9)
Hemant Kowshik, P. R. Kumar, Optimal Function Computation in Directed and Undirected Graphs IEEE Transactions on Information Theory. ,vol. 58, pp. 3407- 3418 ,(2012) , 10.1109/TIT.2012.2188883
Brijesh Kumar Rai, Bikash Kumar Dey, On Network Coding for Sum-Networks IEEE Transactions on Information Theory. ,vol. 58, pp. 50- 63 ,(2012) , 10.1109/TIT.2011.2169532
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
S.-Y.R. Li, R.W. Yeung, Ning Cai, Linear network coding IEEE Transactions on Information Theory. ,vol. 49, pp. 371- 381 ,(2003) , 10.1109/TIT.2002.807285
A. Giridhar, P.R. Kumar, Computing and communicating functions over sensor networks IEEE Journal on Selected Areas in Communications. ,vol. 23, pp. 755- 764 ,(2005) , 10.1109/JSAC.2005.843543
K Zeger, R Appuswamy, N Karamchandani, M Franceschetti, Network Coding for Computing: Cut-Set Bounds IEEE Transactions on Information Theory. ,vol. 57, pp. 1015- 1030 ,(2011) , 10.1109/TIT.2010.2095070
Aditya Ramamoorthy, Michael Langberg, Communicating the Sum of Sources Over a Network IEEE Journal on Selected Areas in Communications. ,vol. 31, pp. 655- 665 ,(2013) , 10.1109/JSAC.2013.130404
R. Koetter, M. Medard, An algebraic approach to network coding IEEE ACM Transactions on Networking. ,vol. 11, pp. 782- 795 ,(2003) , 10.1109/TNET.2003.818197
Rathinakumar Appuswamy, Massimo Franceschetti, Computing Linear Functions by Linear Coding Over Networks IEEE Transactions on Information Theory. ,vol. 60, pp. 422- 431 ,(2014) , 10.1109/TIT.2013.2283075