网络编码在无线网络中的应用综述

关键词： 编码 网络

2000年, 网络编码的概念在被提出后[1]就得到了广泛地关注。网络编码融合了路由和编码的概念, 使网络节点不仅可以对数据进行存储转发, 还可以进行编码处理, 已证明了使用线性网络编码已经能足够达到网络多播容量[2]。但网络编码的好处不止这些。尤其是当网络编码应用于无线网络时。网络编码首先应被应用在无线网络环境[3], 无线网络的特性:不可靠性和广播特性, 使网络编码非常适合应用在无线网络上, 因为无线链路的不可靠性和物理层广播特性非常适合使用编码的方法。应用网络编码, 可以解决传统路由、跨层设计等技术无法解决的问题, 提高网络性能。

1 网络编码的概念

用一个例子来说明网络编码。图1是一个蝴蝶网络图。假设链路的容量都是1比特/单位时间。

图1 (a) 采用的是传统的路由方式, , 即节点C一次只能传送1比特到节点D, 节点D也只能传送1比特到节点E和F, 节点E和F总共收到3比特, 平均速率是1.5比特/单位时间;图1 (b) 采用网络编码方法, 节点C对输入信息流进行编码, 将编码的结果x1和x2的异或值 (模2和) 传送到节点D, 再传送给节点E和F。节点E根据收到的信息x 1和x 1+x 2, 可以解码出x 2。同理, 节点F也能解码出完整的信息, 这样的平均速率是2比特/单位时间。

网络节点对信息比特流进行一定的操作, 如模2加、或、与等操作, 而不是仅仅对其进行复制转发, 就称之为网络编码。网络编码的分类:根据网络中所有节点是否对其输人信息进行线性操作, 分为线性网络编码和非线性网络编码;根据网络节点对信息进行操作的系数是否是随机选取的, 分为随机网络编码和确定性网络编码。

2 网络编码在无线网络中的应用

无线网络的广播特性使其非常适合使用网络编码。当一个节点传输一个数据包给它的一个邻居节点时, 它的其它邻居节点也可以接收到这个数据包。因此, 当一个节点的邻居节点对不同的数据包感兴趣时, 可以将这些数据包编码后再一起传输, 这样子可以使其所有的邻居节点都收到感兴趣的数据包并可以节约无线资源。应用网络编码, 可以解决传统路由、跨层设计等技术无法解决的问题, 提高网络性能。网络编码在无线网络中的应用可以提高网络的吞吐量, 尤其是组播吞吐量;可以减少数据包的传播次数, 降低无线发送能耗;当网络部分节点或链路失效时采用随机网络编码, 最终在目的节点仍然能恢复原始数据, 增强网络的容错性和鲁棒性等。

网络编码对无线网络的性能改善主要体现在提高网络编码的吞吐量上。网络编码已经被证明对于提高某些网络[1, 4]的吞吐量有着很大的作用。运用网络编码可以在很大程度上提高网络吞吐量, 但是同时会增加网络的复杂性.不少研究者在研究提高无线网络的组播吞吐量的同时, 研究降低因采用网络编码带来的复杂性[5].在网络状况恶劣的条件下, 网络编码和路由之间组播吞吐量的差别不大, 网络编码的优势体现在降低网络复杂性上;在网络状况较好的条件下, 网络编码相对于路由方法, 在很大程度上, 提高了组播吞吐量。这为根据网络状况动态调整网络编码算法提供了可能[6]。

网络编码在提高无线网络的安全性研究方面亦取得了一定的成果。在无线网络组播中, 对于数据包的恶意修改的检测, 过去是使用基于消息认证码[7]或者数字签名[8]的方法。基于网络编码产生了一种基于数据包的随机网络编码检测策略[9], 这种方法计算量小, 而且检测概率可以根据通信控制开销、网络编码复杂程度和检测时间这些因素进行调控。但这种方法亦存在不足。这种方法要求接收节点需要预先获得至少一个没有被恶意修改过的数据包, 并且数据包的内容不能被攻击者知晓, 因此, 这种方法抗已知明文攻击效果不好。

3 网络编码在无线网络的应用发展方向

网络编码正在给现有的网络带来革命性的变化:网络编码从用来达到有线网络中的组播容量, 发展到在有线和无线网络中提高吞吐量、节省能量、增强鲁棒性和安全性, 甚至改变网络结构、改变网络协议设计方法。网络编码在无线网络中的应用还存在着以下的几个问题:

网络编码的具体实现和降低网络编码的复杂性。现在已经提出了很多网络编码方法, 有集中式线性网络编码、分布式随机网络编码, 但是如何在实际网络环境中实现网络编码, 需要考虑许多实际应用问题, 例如同步、控制开销等。网络编码在实际网络环境中如何实现是一个很迫切的问题。采用网络编码可以在很大程度上提高网络性能, 但设计和实现上的复杂性也随之增加。如何在不显著增加网络开销, 综合考虑效率和性能的前提下, 实现网络编码问题是将来需要进行深入研究的方向。

摘要：网络编码可以优化网络的传输性能。网络编码的基本思想是网络节点不仅对数据进行存储转发, 参与数据处理。本文关注了网络编码在无线网络中的研究和应用, 对其发展进行了展望。

关键词：网络编码,无线通信网

参考文献

[1] R.Ahlswede, N.Cai, S.-Y.R.Li, and R.W.Yeung, “Network in-formation flow, ”IEEE Trans.Inform.Theory, 2000, 46 (4) :1204～1216.

[2] Li S-Y R, Yeung R W, Cai N.Linear network coding.IEEE Trans Info Theory, 2003, 49 (2) ;371～381.

[3] Widmer J, Fragouli C, Le Boudec J-Y.Low-complexity energy efficient broadcasting in wireless ad-hoc net-works using network coding.In:Proc.WINMEE, RAWNET and NETCOD2005Workshops, Apr.2005.

[4] Sanders P, Egner S, Tolhuizen, L.Polynomial time algorithms for net-work information flow.In:Pr oc.15th ACM Symp on Parallel Algo-rithms and Architectures, 2003:286～294.

[5] Ho Tracey, Jin Jia-Qi, Viswananthan H.On network coding and routing in dynamic wireless multicast networks.In:Information Theory and its Applications, February, 2006.

[6] Neely M, Modiano E, Rohrs C E.Dynamic power allocation and routing for time-varying wireless networks.In;Proceedings of IEEE Infocom, 2003.

[7] Castro M, Liskov B.Practical Byzan-tine Fault Tolerance.OSDI, 1999.

[8] Kihlstrom K P, Moser L E, Melliar Smith PM.The SecureRing Protocols for Securing Group Communication HICSS, 98.

[9] Ho T, Leong B, Koetter R, et al.Byzantine modification detection in multicast networks using randomizednetwork coding.In:IEEE Interna-tional Symposium on Information Theory (ISIT2004) , 2004, 6.