CIF: Small: Information Flow in Networks: Entropy, Matroids and Groups

CIF：小：网络中的信息流：熵、拟阵和群

• 批准号: 1018927
• 负责人: Babak Hassibi
• 金额: $ 50万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-15 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018927&HistoricalAwards=false
• 关键词: CIF; Small; Information; Flow; Networks

This research aims to develop an optimization-based approach to network information theory, that goes well beyond current networking theory and practice. There is a great deal of recent interest in the problem of simultaneous information transmission among many users over wired and wireless networks. Information theory is well poised to have an impact on the manner in which such future networks are designed and maintained, both because wired networks are ripe for applications such as network coding (where information streams are actually combined rather than simply routed) and also because wireless networks cannot be satisfactorily dealt with using conventional networking tools. The challenge is that even the simplest network information theory problems are notoriously difficult and, as a result, information theory has not been able to provide many tools to network practitioners. The research aims to remedy this situation by developing tools for more effective network design. While, in principle, it is possible to obtain the information-theoretic rates in wired networks via convex optimization over the space of entropy vectors, this effort is severely hampered by the fact that an explicit characterization of the entropic space does not appear to be within reach. To circumvent this, the research will consider frameworks that, while possibly suboptimal, apply to arbitrary networks, have reasonable complexity and lend themselves to distributed implementation. The mathematical approach taken is four-fold and makes use of the representation theory of matroids (to design linear network codes), Monte Carlo Markov chain methods to distributedly design "good" network codes, group-theoretic techniques to construct nonlinear network codes from non-Abelian groups, and determinantal inequalities to study the entropic space.

本研究旨在开发一种基于优化的网络信息理论方法，远远超出当前的网络理论和实践。最近，在有线和无线网络上的多个用户之间的同时信息传输的问题引起了极大的兴趣。信息论很有可能对未来网络的设计和维护方式产生影响，这既是因为有线网络对于网络编码（信息流实际上是组合的，而不是简单的路由）等应用已经成熟，也是因为无线网络不能使用传统的网络工具令人满意地处理。挑战在于，即使是最简单的网络信息理论问题也是出了名的困难，因此信息理论无法为网络从业者提供很多工具。该研究旨在通过开发更有效的网络设计工具来纠正这种情况。虽然，在原则上，它是可能的，以获得有线网络中的信息理论速率通过凸优化的熵向量的空间，这一努力是严重阻碍了一个显式表征的熵空间似乎并没有达到的事实。为了规避这一点，研究将考虑框架，虽然可能是次优的，适用于任意网络，具有合理的复杂性，并借给自己的分布式实现。所采取的数学方法是四重的，并利用拟阵的表示理论（设计线性网络代码），蒙特卡罗马尔可夫链方法来分布式设计“好”的网络代码，群论技术来构建非阿贝尔群的非线性网络代码，以及行列式不等式来研究熵空间。