空间网络编码的关键理论与方法

Currently,the research of routing can be divided into one in graph and the other in space, the latter of which is often considered as the Euclidean space. When taking into account the network coding, there should also exist the research of network coding in graph as well as in space, however the current study almost focused on the case in graph with hardly any attention on network coding in space. Due to the absence of such work, this project anticipates to create a theoretical framework and methods of network coding in space, including: (1) The function models and corresponding algorithms of network coding in space based on single session and multiple session which regard multicast and multiple unicast as the typical research contents; (2) Exploring the unified theorem of network coding in space and routing in space, in order to further reveal the essence of network coding from the novel angle of space; (3) To illustrate the correlation between network coding in space with that in graph, and apply the geometric approach in space to tackle the problems of network coding in graph; (4) Research on the typical examples of network coding in space based on wireless networks, to certify the correctness and feasibility of the theory. Network coding in space proposed by the application team is originally innovative, moreover, a novel tool to investigate network coding, namely geometry, is introduced, which is of important theoretical significance. Network coding in space can provide not only a general introduction for the planning and design in space, but also a theoretical guidance for the refinement and modification in graph, therefore, it owns fairly wide application values.

目前路由的研究可以分为二类：图(Graph)中路由和空间(Space)中路由，后者常指欧氏空间。对于网络编码，目前研究多集中于图中，暂未见空间中网络编码的研究。针对此较大研究空白，本项目拟构建空间中网络编码的理论框架和方法，包括基于单会话和多会话的空间中网络编码的性能模型和相关算法，分别以多播和多单播为典型研究对象；探索空间中网络编码和路由的统一定理，旨在从空间的新角度进一步揭示网络编码的本质；阐明空间中网络编码与图中网络编码的关系，将空间中的几何方法应用于解决图中网络编码的难题；研究面向无线的空间中网络编码典型实例以验证其正确性和可行性。申请团队所提出的空间中网络编码理论属于原始创新，并为网络编码研究引入新的数学工具- - 几何，具有重要理论意义。空间中网络编码不仅可为空间中规划设计提供理论指导，而且可为图中性能优化提供理论指导，具有较广泛的应用价值。

本项目研究欧氏空间中网络编码相关理论和方法，从单会话和多会话二方面开展。对于多播空间网络编码：构造五角星网络实例显示其代价优势严格大于1，阐明空间网络编码与空间路由存在本质不同及本项目研究必要性；证明多播空间网络编码重要性质包括凸性、凸包、信源无关性、120°等；提出具有多项式复杂度最小代价多播空间网络编码最优算法，结合Delaunay三角剖分和非均匀划分获取候选中继点，分别支持中继点与终端点具有任意空间密度分布和支持终端点与终端点具有任意空间密度分布，并通过线性规划计算最优中继点，然后基于力学平衡原理微调中继点位置进一步减少代价，有限迭代非均匀划分最终获得最优解；该算法已推广至三维欧氏空间；证明二维空间多播代价优势上界是1.155，小于无向网络中编码优势（与代价优势对偶）上界2，小于有向网络中编码优势∞；虽多播空间网络编码代价优势上界降低，但由于空间多播路由是NP-难问题，而所提出最优算法证明空间中采用网络编码也可降低问题复杂性，揭示网络编码优势本质所在，对网络编码走向实用具有较重要的应用价值。对于多单播空间网络编码，证明其代价优势为1。提出基于空间网络编码的几何框架，构建空间网络编码和图中网络编码联系桥梁，包括吞吐量对偶转化代价、等距嵌入空间、高维空间降维、单维空间证明等四步，可将网络中难题转化为空间问题以通过几何方法加以解决。以无向网络中多单播网络编码编码优势等于1的多单播猜想难题证明为例，该统一框架验证现有结论，包括两对单播和星形网络多单播结论，并证明两个新结论，包括链路代价均等完全网络和分层网络多单播结论。本项目研究将离散域拓扑扩展至连续域空间，从更一般角度深入揭示网络编码本质，具有较大理论价值；将几何引入网络编码领域，丰富研究网络编码的方法，具有较大方法论价值。空间网络编码不仅可用于网络规划设计和优化，而且通过几何框架可从空间几何角度解决图中网络编码难题，具有较广泛的理论和应用价值。