二進制線性網路編碼理論與其代數數論實現

Abstract

在本計劃書中，本人提出數個在網路編碼理論上的先期研究成果，以及數個後續衍 生的重要問題，首先，當通訊網路為無遲滯的有向無迴路網路時，且當只有單一訊號源的 情況，此類網路之拓墣可以視為一有向非循環圖，且可假設每一鏈結之通道容量為一。之 前所有的網路編碼理論研究均需要一個相當大的有限代數體以構造線性multicast、線性 broadcast、或是線性dispersion，然而此充分條件卻與原先的單位通道容量假設相違背，造 成所設計出的線性網路編碼完全無法運用於實際通訊網路中，因此在本計劃書中，本人率 先提出一套具有記憶性的線性網路編碼理論，並證明對任意的單一訊號源的有向無迴路網 路，必定存在其二進位的線性網路編碼實現，亦即無論是線性multicast、線性broadcast、 還是線性dispersion，都可以在binary field 中完成，而不需要更大的代數體，本人也證明構 造二進位線性網路編碼所需的計算複雜度小於先前所需構造非二進位碼之複雜度。本計劃 書中，針對二進位的線性broadcast 網路編碼，本人亦提出一明確詳盡的構造方法，此構造 方法是基於代數模理論(module theory)及有理函數體(rational function field)的理論， 並利用了組合最佳化中的矩陣滿秩實現(matrix completion)技巧，所得的方法具有多項式 關係之計算複雜度。 雖然針對任意的單一訊號源非循環網路，本人已提出完整的二進位構造方法，然而一 般的通訊網路幾乎都有迴路，因此本人將更深入研究如何將二進位線性網路編碼能更實際 運用於任意的通訊網路中。本人在此提出一為期三年 (2007-2010 年) 的研究計畫，並將研 究下列重要問題 1. (2007-2008 年) 研究任意單一訊號源循環網路的完整的二進位的線性網路編碼方 法。 2. (2007-2010 年) 利用代數數論及解析數論，完成一個以浮點數運算為基礎，能在所 有通訊網路中，構造出二進位的線性網路編碼的演算法。 3. (2008-2009 年) 研究二進位的線性 broadcast 網路編碼的排程演算法。 4. (2008-2010 年) 研究在多訊號源的通訊網路中的二進位的線性網路編碼方法。 本計劃預計將能產出一極高效率的二進位的線性網路編碼方法，並能運用於任意的超大型 通訊網路，此外，亦能大幅提昇網路效能與頻寬使用效率。

Several problems of network coding over a communication network are proposed for investigation in this research proposal. First, for the case of a delay-free acyclic communication network with single source, such network is modeled as a directed acyclic graph where each link is assumed to have unit link capacity. Previous works on network coding require a sufficiently large field such that the network has a linear multicast, a linear broadcast, or a linear dispersion solution. However, the requirement on field size contradicts the unit link capacity assumption and such solutions might not be feasible. To remedy this, we propose in this proposal the concept of the linear network codes with memory and show that for any directed acyclic network with single source, there exists a binary linear dispersion network code. The proposed code requires only the binary field for realization, but not any larger field. It is shown that the computational complexity required for constructing a binary linear dispersion is no more than that required for constructing a non-binary linear dispersion. Also contained in this paper is an explicit construction of binary linear broadcast network code. The construction is based on the matrix completion technique and has polynomial complexity. While in this proposal we have presented complete solution to binary linear codes for acyclic networks with single source, it should be noted that in the practical scenario, we often encounter cyclic networks. Thus, to make the binary linear code practical, more investigations are needed and we will propose to investigate some research problems that are of significant importance in this field. This proposal will take a three-year (2007-2010) time span and we will work on the following problems: 1. (Year 2007-2008): Linear Network Codes for General Networks with Single Source 2. (Year 2007-2010): Construction of Binary Linear Network Codes from Algebraic and Probabilistic Number Theory 3. (Year 2008-2009): Transmission Scheduling Schemes for Binary Linear Broadcast Codes 4. (Year 2008-2010): Binary Linear Network Codes with Multiple Sources By the end of this project, we will have a very efficient algorithm for constructing binary linear network codes for any large-scale communication networks. The resulting code will largely improve the performance and bandwidth efficiency of our computer network.