网络编码技术是近些年来提出的可达到最大传输速率的一种新兴技术。不同于传统路由技术,即存储转发模式,网络编码允许中间节点对其收到的信息进行线性或者非线性的编码操作后转发给下一个节点。相比于传统的路由方法,网络编码被证明了具有提高吞吐量、降低传输延迟、减少传输能耗、增加系统鲁棒性等优点,并应用到了多个领域中。特别地,由于操作简单和编、译码复杂度低,随机网络编码被广泛应用到实际网络中。随机网络编码允许网络的中间节点对接收到的信息进行线性组合操作,其中组合系数是在一个有限域内随机选择的一个元素。研究显示随着有限域基数趋于无穷,这种方法的成功率就可以趋于1。这种随机选取系数的方法带来的缺点有两个。一个是需增大编码操作中所需编码域的大小,另一个是保证特定的概率实现正确的传输。网络节点频繁的从编码域中选取编码系数进行编、译码操作。如果编码域选取的过小,那么信宿节点的成功译码概率过低。这将不利于实际操作的应用。如果编码域选取的过大,那么编、译码的复杂性过大。这将造成不必要的能源损耗和时间浪费。显而易见,在保证固定成功译码概率的同时,减小所需编码域基数是一个很有意义的研究课题。本文围绕这个问题展开讨论,所取得的主要成果包括以下三个方面。第一部分研究基于线性代数、鲁棒网络流和随机化给出一个鲁棒性的多项式时间的随机线性网络编码的构造方法,全文中简称算法RPR。建立了基于有丢包的单源多播网络的一般模型,并在此模型上给出了算法的构造方法和具体步骤。随后给出了算法的性能分析,包括成功译码概率和时间复杂度等。最后给出了算法的理论增益,通过在大规模网路上的理论分析给出算法在减少编码边数上的优势,并且通过两个特定网络(即蝴蝶网络和组合网络)给出算法在减少编码域基数上的贡献。通过算法RPR的构造,得出一个网络编码存在的问题等价于排列从信源到信宿的信息流的组合问题。网络编码之所以优于存储转发的路由协议可以达到最大传输速率,其本质就是在忙碌边上进行编码操作。如果网络中没有忙碌边,则网络必定存在路由解保障最大速率的可达性。如果网络是最小多播网络,算法中给出的编码边的个数是最少的。第二部分研究一类组合网络的成功译码概率问题。组合是构造网络的一种基本方法,且组合网络应用在各个领域,例如,用组合网络构造分组密码,用组合网络分析城市道路网等。针对在组合网络拓扑中研究了随机线性网络编码的成功译码概率问题,当网络模型中不发生丢包时,给出一个信宿节点和所有信宿节点都成功译码的闭式解。根据这些闭式解,在固定的成功译码概率下,可以选取基数最小的编码域。通过这些表达式,还分析了主要参数,即编码选取的有限域的基数、信宿节点的个数和网络中继节点的个数对译码性能的影响。当网络模型中发生丢包时,给出一个信宿节点和所有信宿节点都成功译码的下界。第三部分研究基于树型网络的随机线性网络编码的成功译码概率问题。在应急领域,网络常用于环境监测,灾难信息获取等。因此针对灾难环境的真实需求,在这种情况下,分层结构是一种很方便的分布式管理。从网络拓扑上看,分层结构可以简化成树型网络。此外,增加网络深度就可以扩大网络的覆盖范围。由于其灵活性和低时延性,树型网络适用于各种应急需求中。给出有丢包的树型网络的一般模型,并在此模型上研究了随机线性网络编码成功译码概率问题。考虑了网络中没有丢包和有丢包两种情况。在这两种情况下,分别给出一个信宿节点和所有信宿节点都成功译码的闭式解。通过仿真,分析了一些参数,即编码选取的有限域的基数、网络中间节点的个数、信宿节点的个数、和链路失败概率对译码性能的影响。