无线网络中基于网络编码的路由算法

沈啸

摘 要：网络编码为无线网络带来了更高的可靠性，二者的结合已经引起了很多研究学者的关注，无线网络中基于网络编码的路由算法更是值得探讨和研究的问题，本文在网络编码的基础上分别对网络编码的多路径路由算法和编码感知的路由算法进行了分析和研究，以期实现提高无线传输效率的目标。

关键词：无线网络；网络编码；多路径路由；编码感知

随着信息技术的迅速发展以及移动通讯技术应用的日益广泛，无线网络的覆盖范围扩张明显，如何提高无线传输效率，已经成为研究学者关注的重要问题之一，网络编码的提出则让人们看到了最大限度利用网络资源的有效路径，网络编码技术被认为是解决无线传输问题的重要手段，现就无线网络中基于网络编码的路由算法问题进行研究，有其重要的理论指导意义。

1 网络编码技术概述

网络编码（Network Coding）是一种融合了路由与编码的信息交换技术，其核心思想是在网络各节点上对收集的信息进行线性或非线性处理，进而传送到下游节点，与传统通信网络传送数据的不同在于，中间节点在此过程中扮演的是编码器的角色，而不是转发器的角色。网络编码技术颠覆了传统的数据传输方式，作为一种新的编码算法，网络编码技术能够将现有的网络吞吐量提高一倍，为改变当前基于路由的网络架构带来了希望。根据最大流-最小割定理，传统的多播路由并不能达到数据传输流值的上界，而通过网络编码则可以达到多播路由传输的最大流界，从而提高无线传输效率[1]。

2 基于网络编码的多路径路由算法

2.1 MPBNC多路径路由算法设计

MPBNC是一种基于网络编码的多路径路由算法，主要利用多路径上存在的可能性编码，在路由发现阶段从目的节点向源节点返回多条路径，并从中选择编码机会较多的路径，进而根据编码机会的多少来对流量进行分割。在路径发现阶段，多路径路由可以根据节点之间的关联性来划分为三个种类：链路不相交、节点不相交以及相交多路径。链路不相交路径指的是路径间没有共用的路径，节点不相交路径指的是路径间没有共同节点和共用路径，相交多路径则是指路径间既有共同节点也有共用路径。MPBNC多路径路由的发现过程分为四个阶段，分别是产生路由请求分组、处理路由请求分组和处理路由响应分组，整个阶段结束后，源节点就会从多路径中选取最优路径传输数据，即具有编码机会的路径在单位时间内能够传输更多的数据，分配更多的流量。

2.2 MPBNC多路径路由仿真及性能分析

为了测试MPBNC的效率，可以通过NS2仿真模型来实现，NS2是一款开放源代码的网络协议模拟软件，同时也是一款非常出色的分析各种网络协议的仿真工具，这里所说的网络协议包括了计算机网络协议、卫星网络协议、无线网络协议以及应用层协议。NS2中的构件由分别在C++和Otcl中相关联的两个类来实现，这种仿真模型能够增强整个构件库的组合性和扩展性。网络编码的优点在于能够提高網络吞吐量，仿真的目的就是从网络吞吐量上评估MPBNC多路径路的性能，MPBNC算法按照编码机会的多少在返回路径中对流量进行分割，因此能够传输更多的数据，其网络吞吐量自然就会提高[2]。

3 基于编码感知的无线网络单路径路由算法

3.1 NCASR单路径路由算法设计

NCASR是一种基于编码感知的无线网络单路径路由算法，通过设置适用于多个数据包的编码增益公式，在路由发现阶段从源节点和目的节点之间的传输路径上选择编码机会较多的最优路径进行数据传输。这种路由模式实际上是将网络编码技术与网络层的路由有机地结合在一起，以此来实现逼近网络容量理论传输极限的可能。无线网络的路由选取应根据一定的度量标准来找到一条最优的路径，该度量标准即为路由判据，常用的路由判据主要有跳数、每跳往返时间、平均传输次数、平均传输时间等，路由判据的选取应考虑到无线网络传输路径的真实特性，只有以此为度量标准，才能找到最优路径，从而提高网络吞吐量以及无线传输效率。NCASR单路径路由的发现过程分为四个阶段，分别是产生路由请求分组、更新分组信息、回复分组信息、计算编码增益、选取最大的编码增益值，整个阶段结束后，源节点就会从多路径中选取最优路径传输数据，即具有编码机会的路径在单位时间内能够传输更多的数据，分配更多流量。

3.2 NCASR单路径路由仿真及性能分析

为了测试NCASR的效率，同样可以通过NS2仿真模型来实现，仿真参数类型主要包括无线信号传输模型、网络接口、MAC层协议、接口队列、链路层、节点传输半径等类型，仿真模型主要从网络吞吐量来评估NCASR算法的性能。NCASR算法与传统的COPE算法在不同发送速率下的平均吞吐量是不同的，当网络符合增加到一定值时（通常是55kdps），二者所反映的吞吐量就会出现明显的差异，随着数据流的不断增加，NCASR能够主动寻找更多的编码机会的路由，因此，NCASR平均吞吐量的增量将持续大于COPE。由此可见，NCASR能够将编码增益作为路由的选择判据，并以此为依据选择最小代价的路径去传输最大限量的网络容量，从而提高无线传输效率[3]。

4 结论

为了提高网络吞吐量，提高无线网络的性能，网络编码以及基于网络编码的路由算法应运而生，实践证明，无线网络中基于网络编码的路由算法能够减少数据包传输的次数，从而提高无线传输效率。

[参考文献]

[1]田贤忠.无线网络中基于网络编码的路由算法[D].浙江工业大学.2013.

[2]王欢.无线网络环境下基于网络编码的路由技术研究[D].中国科学技术大学.2011.

[3]陈贵海，李宏兴，韩松，钟子飞，陈明达.多跳无线网络中基于网络编码的多路径路由[J].软件学报.2010，13（8）：19-20.