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.

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