基于无线网络的快捷高效率网络编码方法研究

第1章绪论

1.1研究背景
与多收发机多信道技术以及MIMO天线技术等相比，网络编码作为一种无需增加额外硬件设备的方法，为无线网络性能优化提供了一个薪新的思路。由于无线媒介的广播特性以及拓扑的多跳特征，使得无线网络中存在着大量的冗余报文。通过对网络中冗余报文实施合理的网络编码并利用无线媒介的广播特性，可有效减少传输次数，进而提高无线网络性能。下面通过两个例子来说明网络编码在无线网络中应用的主流方法以及相应的性能优势。

1.2面向无线网络的高效网络编码方法研究
一般而言，在多信道环境中，无线节点可根据链路的信道状态信息选择合适的信道速率。为了支持网络编码而选择广播传输时，出于信道传输可靠性需求的考虑，信道广播速率的选择通常由广播所含的多条单播链路上的最坏信道状态决定，从而使得广播速率为多条单播链路传输速率的最低值。因此，如果盲目地应用网络编码，可能会导致性能的下降。基于此，对于多信道环境，如何为节点设计合理的网络编码方案，使得基于网络编码的数据传输性能得到优化，是网络编码应用中的一个关键问题。本文针对图1.2所示的简单却又泛在的确定网络编码方法，对面向多信道环境的网络编码方法进行了研宄，并提出了多个高效的网络编码感知的信道调度算法。
随机线性网络编码通常具有较高的解码时延，而节点的移动性易于引起网络拓扑变化，使得随机线性网络编码的解码时延更难以得到保证。（2)中的研究在一定程度上能够保证随机线性网络编码在单个目的节点上的解码时延，然而，由于不同目的节点之间传输的差异性，（2)中的研究难以优化应用于数据广播场景中。如何针对节点的移动性，设计合理高效的网络编码方法，从而保证数据广播场景中所有节点上的解码时延，是面向无线移动环境中网络编码应用中的一个重要问?题。本文从单个消息广播问题出发，对随机线性网络编码在无线移动网络中的应用与性能进行了探讨，提出了一种基于随机线性网络编码的广播协议，并论证了其在广播时延方面的渐进最优性。
……………

第2章相关工作

2.1网络编码理论相关工作
上述研究主要针对无圈网络中的单信源网络编码。然而，在有圈网络中，节点之间不存在偏序关系，从而破坏了上述方法的最优性。针对此问题，研究者对单位时延有圈网络中的卷积网络编码(convolutional network codes)进行了研究。Koettei和Medard间首先证明了在单位时延网络中存在卷积多播(convolutionalmulticast)。此后，Erez和Feder、Pragouli和Soljanin，以及Barbero和Ytrehus对于卷积多播的存在性与构造进行了深入的研宄。Li则基于环论给出了卷积网络编码的一般抽象形式。相比于单信源网络编码，多信源网络编码的最优构造更为困难。Medard等人、Lehman等人以及Riis证明了特殊形式的线性编码对于多信源网络编码是不充分的。Doughert等人则证明了更一般的线性编码的不充分性。然而，当所有信源都由网络同一个节点产生时，Chan构造了一类基于群的网络编码并证明了其最优性。这些工作对网络编码的理论研究具有较大的促进作用，但是这些工作中大多引入了非常强的假设，距离实际应用仍有较大的距离。

2.2确定网络编码方法研究
上述大多数关于确定网络编码的研究注重在基于协议的单信道无线网络中。由于协议下信道调制速率是固定的，因此无需考虑无线信道广播速率限制的问题。然而，在多信道环境中，同一个信道在不同链路上速率可能存在较大的差异，因此网络编码的应用需要适应于无线广播信道速率。目前，只有少数的工作考虑了确定网络编码在多信道场景(如OFDMA网络)中的应用与性能增益。Zhang和Li考虑了基于OFDMA的单跳蜂窝网络中基站上确定网络编码的应用方法，并提出了信道分配的启发式算法。Xu和Li, Xu等人，Liu等人[34]以及Kim和Lee[35]则考虑了确定网络编码在OFDMA中继网络中的中继站上的应用。然而，这些工作中大多(1)采用香农公式计算链路速率，从而使得信道广播时，每一条链路上的速率与单播时相同，这不符合实际应用中无线广播传输模式下信道速率选择方法；（2)采用启发式算法对信道进行调度，缺乏一定的性能保证；（3)忽略了一些实际因素的影响，如中继站上数据缓存的能力[35]，信道环境的不稳定性等等；（4)一味地追求网络整体的性能，从而忽略了用户之间的公平性。
……………

3面向多信道无线网络的网络编码方法研究………………16
3.1 引言 ………………16
3.2相关工作 ……………18
3.3系统建模 ……………19
4面向无线移动网络数据传送的网络编码方法研究……… 47
4.1问题建模……………… 49
4.1.1编码与解码………… 49
4.1.2性能分析模型 ………50
4.2预编码的重要性…………51
4.3无重叠分块码的可达速率 …………54
4.4扩展分块码 ……………57
5面向无线移动网络数据广播的网络编码方法研究……………69
5.1引言 ………………69
5.2相关工作………70
5.3系统建模………………………… 71

第5章面向无线移动网络数据广播的网络编码方法研究

5.1引言
在本章中，我们通过考虑移动自组网中的数据广播问题以及如何利用网络编码优化数据广播时延来对上述问题进行初步的探讨。为完整起见，首先对移动自组网中的广播问题进行介绍。一个典型的移动自组网是自配置的无线网络，其中的网络节点不仅可以充当主机，也可以作为中继，为其它网络节点存储转发数据，此外，节点还可以按照自己的意愿进行移动。移动自组网中一个基本操作是广播，被用在了各种各样的应用中。广播操作的任务是将源节点的一个消息分发给网络中所有的其他节点。出于对时间紧急的应用(如发送警报，救灾抢险等)的考虑，本章致力于最小化广播时延，即网络中所有节点均收到该消息所需要的时间。

5.2相关工作
近年来，已有一些工作考虑了节点移动对广播时延的影响。这些工作可根据传输半径是否超出关键半径分成两类。在稀疏的情况下，即传输半径低于关键半径时，研究者在各种移动模型下对广播时延进行了讨论。这些模型包括广为人知的独立同分布移动模型[138丨，随机行走模型[139]等等。在密集的情况下，即传输半径高于关键半径时，Clementi等人[140，141, 142]在与本章工作中几乎相同的网络模型下对广播时延进行了一些研宄。他们建立了一个广播时延的下界，并对洪泛方法下的广播时延进行了分析。然而，他们的工作并没有考虑并发传输时的干扰问题。Chen等人[143]引入了一种闲谈的方法，这种方法采用了功率控制从而有效地对抗了干扰问题，然而这种方法没有利用无线媒介的广播特性，从而导致性能是次优的。

……………

第6章总结与展望

本文首先从适应无线信道广播速率的角度对多信道环境中的网络编码方法进行了研究，接着从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法进行了研宄，其主要贡献总结如下：
以OFDMA中继网络为应用背景，对适应无线信道广播速率的网络编码方法进行了探讨。以优化性能与负载为切入点，提出了全局方法和局部方法用以支持网络编码感知的信道调度策略。针对全局方法下的网络编码感知信道分配问题，证明了其是NP难旳且不存在PTAS，并提出了一种低时间复杂度的启发式算法EMW。针对局部方法下的网络编码感知信道分配问题，证明了其是NP难的，并提出了一种PTAS解法以及一种实用的具有1/2近似率的贪姿算法HAG。仿真实验结果表明，EMW和HAG相比于无网络编码的机制，能够极大地提高网络吞吐率。
对面向无线移动网络中可靠数据传送的具有常数复杂度的分块码方法进行了研究。首先证明了预编码在对分块码的不可或缺性，否则分块码的可达码率在渐进意义下为0。接着在预编码的前提下，对无重叠分块码的可达码率进行了紧的分析，并发现其较为低下。进一步地，提出了一类新颖的采用扩展图生成重叠报文块的扩展分块码，并通过树的分析以及扩展论证对其可达码率进行了刻画，从而表明扩展分块码是第一类具备非平凡性能保证的重叠分块码。扩展分块码的可达码率极大地超出了无重叠分块码，并且仿真结果表明，当输入报文数目有限时，扩展分块码与其它重叠分块码相比，具有低得多的传输负载和解码错误概率。
……………

参考文献（略）