多信源网络编码容量域的计算机辅助研究

The network coding capacity (rate) region is a fundamental problem in information theory and network science. The distributed storage and caching systems, proposed to solve the challenges of storage and communication in the era of big data, are two of the applications. While many researchers focus on the tractable networks with high symmetry, this project intends to study the network coding capacity region of multi-user multicast networks, especially the asymmetric cases. The project will not only provide a theoretically optimal capacity region based on Shannon outer bound and representable matroid inner bound, but also provide a guiding solution for the actual coding design. Especially, when the linear codes considered are easy to implement, such as binary codes, the solutions we provide can be directly used in real-world systems. In terms of research methodologies, in order to overcome the limitations of manual derivation in information theory and multi-user networks, we introduce a computer-aided method, by which the work that many humans can't do can be done efficiently by compute. This accelerates the derivation and proof of the theories, which may be a bottleneck for the human brain. For instance, we will use a computer to enumerate (in accordance with network constraints) the non-isomorphic representatives of representable matroids in a particular field, which further help us obtain a corresponding achievable inner bound of the capacity region; we will use a high-dimensional polyhedral projection algorithm to obtain the outer bound on the network coding capacity region; we will use a linear programming algorithm to automatically generate a theoretical derivation and proof process simulating humans. Our research will make some breakthroughs in the theory of network coding, and also provides guidance for the storage and caching systems in practice.

研究网络编码容量域是信息论和网络科学中的一个基本问题。为解决大数据时代存储和通信挑战而提出的分布式存储和缓存系统即是其中的应用。本项目拟研究多用户（信源）网络，尤其是非对称网络的编码容量域。项目将从香农外界和可表示拟阵内界的角度提供理论上的最优容量域，并为实际编码设计提供指导。当考虑的线性码是易实现的，如二元码，我们提供的方案可直接用于现实系统。在方法上，为克服手工推导的限制，我们引入计算机辅助的方法，将很多人力无法完成的工作交由计算机来高效完成，从而加速理论的推导和证明，突破目前人脑瓶颈。例如，我们会利用计算机来列举（符合网络限制条件的）某个域上的非同构可表示拟阵，从而得到与其对应的可达容量域内界； 利用高维度多面体的投影算法得到网络编码容量域的外界； 利用线性规划算法自动生成模拟人类的理论推导证明过程。我们的研究将在网络编码理论上取得突破，对构建实际的存储和缓存系统也具有指导意义。

研究网络编码容量域从而指导编码设计以及网络架构是信息论和网络科学中的一个基本问题。网络编码容量域不仅仅是一个信息论方面的难题，它更重要的是给出了实际系统中编码方案的指导， 避免了资源浪费又可以实现高效存储或传输。本项目研究以分布式存储和缓存为应用的多用户多播网络，尤其是非对称网络的编码容量域以及其线性编码可达容量域并提出高效的编码构造。项目不仅从香农外界和可表示拟阵内界理论上提供最优容量域，并且为实际的编码设计提供指导方案。本项目完成了一下三个方面任务，解决了关键的问题：.1、基于可表示拟阵的可达容量域内界的计算以及编码构造；列举服从网络限制条件的非同构可表示拟阵和线性多拟阵，使其服务于网络容量域内界的求解和线性编码构造。可表示拟阵将独立集与向量空间中传统的独立概念联系起来，建立了可表示拟阵和熵向量之间的关系。.2、基于高维多面体投影的网络编码容量域外界的计算；多面体投影和多目标线性规划的高效算法，使其用于网络容量域外界的求解。我们研究了7360个非同构MDCS实例的区域，这些实例代表134617个同构实例。如果从香农外界获得的外边界速率域与对应的熵矢量内边界速率区域的任何内边界匹配，我们不仅知道精确的速率域，而且知道足以实现其中任何点的码。我们证明了6803个非同构实例中6326个的香农外界是紧的。.3、基于线性规划的人类可读理论证明的自动产生；基于多目标线性规划和投影的结果，利用线性规划的方法自动生成人类可读证明。香农外界加上网络约束的投影给出编码率域上的外边界，原则上等同于逆向证明。给出了算法确定人类可读证明的不等式应用顺序。.本项目研究的课题是目前此类问题的前沿，也是原创性的。