ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２０１０，４６（１２）１
◎博士论坛◎
无线Ｍｅｓｈ网中网络编码的研究进展
夏卓群，．ｚ，陈志刚－，沈小建１，赵明－
ＸＩＡＺｈｕｏ－ｑｕｎｌ，２ＣＨＥＮＺｈｉ—ｇａｎｇＩ，ＳＨＥＮＸｉａｏ－ｊｉａｎＩ，ＺＨＡＯＭｉｎ９１
１．中南大学信息科学与工程学院，长沙４１００８３
２．长沙理工大学计算机与通信工程学院，长沙４１００７６
１．１ｎｓｔｉｔｕｔｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８３，Ｃｈｉｎａ
２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＣｈａｎｇｓｈａＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７６，Ｃｈｉｎａ
Ｅ——ｍａｉｌ：ｘｉａｚｈｕｏｑｕｎ＠ｔｏｍ．ｃｏｍ
ＸＩＡＺｈｕｏ－ｑｕｎ．ＣＨＥＮＺｈｉ－ｇａｎｇ。ＳＨＥＮＸｉａｏ－ｊｉａｎ，ｅｔａ１．ＲｅｓｅａｒｃｈｏｎｎｅｔｗｏｒｋｃｏｄｉｎｇｉｎｗｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓ：Ａｓｕｒｖｅｙ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１０．４６（１２）：ｌ－４．
Ａｂｓｔｒａｃｔ：ＷｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓｉｓｂｅｃｏｍｉｎｇａｍａｊｏｒｐａｒａｄｉｇｍｆｏｒｃｏｎｓｔｒｕｃｔｉｎｇｕｓｅｒａｃｃｅｓｓｎｅｔｗｏｒｋｓｔｈａｔｐｒｏｖｉｄｅｃｏｍｍｕｎｉｔｙ
ｏｒｃｉｔｙ－ｗｉｄｅＩｎｔｅｒｎｅｔｃｏｎｎｅｃｔｉｖｉｔｙ．Ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇ．ａ８ａｎｅｗｔｅｃｈｎｉｑｕｅｗｈｉｃｈｉｎｔｅｒｍｅｄｉａｔｅｎｏｄｅｓｉｎｔｈｅｎｅｔｗｏｒｋｎｏｔｏｎｌｙｆｏ卜
ｗａｒｄｂｕｔａｌｓｏｐｒｏｃｅｓｓｔｈｅｉｎｃｏｍｉｎｇｉｎｆｏｒｍａｔｉｏｎｆｌｏｗｓ，ｗｉｌｌｈａｖｅａｇｏｏｄａｐｐｈｃａｆｉｏｎｉｎｗｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓ．Ｆｉｒｓｔｌｙ，ｔｈｅｂａｓｉｃ
ｉｄｅａｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇｉｓｉｎｔｒｏｄｕｃｅｄｂｙｃｏｍｐａｒｉｎｇｔｒａｄｉｔｉｏｎａｌｒｏｕｔｉｎｇａｎｄｎｅｔｗｏｒｋｃｏｄｉｎｇｕｎｄｅｒｕｎｉｃａｓｔ．Ｔｈｅｎｔｈｅｌａｔｅｓｔｒｅｓｅａｌ℃ｈ
ｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇｉｓｓｕｍｍａｒｉｚｅｄ．Ｆｕｒｔｈｅｒｍｏｒｅ。ｔｈｅｓｔａｔｅｓｏｆａｒｔｓｉｎａｐｐｌｉｃａｔｉｏｎｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇｔｏｉｍｐｒｏｖｅｔｈｒｏｕｇｈｐｕｔ，ｒｅｌｉａｂｉｌｉｔｙａｎｄｓｅｃｕｒｉｔｙｉｎｗｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓａｌｅｐｒｏｐｏｓｅｄｒｅｓｐｅｃｔｉｖｅｌｙ．Ｉｎｃｏｎｃｌｕｓｉｏｎ，ｔｈｅｏｐｅｎｉｓｓｕｅｓｆｏｒｎｅｔｗｏｒｋｃｏｄｉｎｇｒｅｆｅｒｒｉｎｇｔｏ
ａｐｐｌｉｃａｔｉｏｎｂａｓｅｄＯＵｔｈｅａｎａｌｙｓｉｓｉｎＭｅｓｈｎｅｔｗｏｒｋｓａｒｅｐｏｉｎｔｅｄｏｕｔ．
Ｋｅｙｗｏｒｄｓ：ＷｉｒｅｌｅｓｓＭｅｓｈＮｅｔｗｏｒｋｓ（ＷＭＮｓ）；ｎｅｔｗｏｒｋｃｏｄｉｎｇ；ｔｈｒｏｕｇｈ【ｐｕｔ；ｍｕｈｉ－ｐａｔｈｒｏｕｔｉｎｇ；ｓｅｃｕｒｉｔｙ
摘要：无线Ｍｅｓｈ网络是一种具有广泛应用前景的无线接入系统，网络编码允许网络节点对接收的数据报文进行加工处理，为解决Ｍｅｓｈ网网络问题提供了一条新途径。通过对比在单播中网络编码和传统路由的不同，阐述了网络编码基本原理；然后总结了网
络编码的发展现状：分析和归纳了网络编码提高无线Ｍｅｓｈ吞吐量、可靠性、安全性等性能的应用；最后对网络编码在Ｍｅｓｈ网络中
的进一步研究方向进行了展望。
关键词：无线Ｍｅｓｈ网；网络编码；吞吐量；多路径；安全性
ＤＯＩ：１０．３７７８０．ｉｓｓｎ．１００２—８３３１．２０１０．１２．００ｔ文章编号：１００２—８３３ｌ（２０１０）１２—０００１－０４文献标识码：Ａ中图分类号：ＴＰ３９３
ｌ引言
无线Ｍｅｓｈ网络（ＷｉｒｅｌｅｓｓＭｅｓｈＮｅｔｗｏｒｋｓ，ＷＭＮｓ）是一种
新型的宽带无线网络结构，被认为是一种可以解决无线接入
“最后一公里”瓶颈问题的新方案”２ｔ，可以应用在宽带家庭
网络、社区网络、城域网、企业网络、交通系统、楼栋自动化
以及完全监视系统中【３ｌ。作为一种新型的宽带接入技术，无线
Ｍｅｓｈ网络在给人们带来许多机遇的同时。也存在许多新的挑
战，还存在许多关键技术和开放性的问题等待人们去研究和
髌决。
网络编码１４１（ＮｅｔｗｏｒｋＣｏｄｉｎｇ）是通信领域的一个重大技术突破，在提高网络吞吐量、改善负载均衡、节省节点能耗、增强
网络鲁棒性等方面均显示出其优越性，已被国际学术界认定为
解决网络问题的重要手段。相对有线网络，无线网络中无线链
路的不可靠性和物理层广播特性更适合使用编码的方法，但网
络编码在无线中的研究和应用还处于探索阶段。
作为一种新兴网络，无线Ｍｅｓｈ网络结构如图ｌ所示【１１，任
何无线设备节点｜Ｊ时作为接入点和路由器，网络中的每个节点
都可以发送和接收信号，并与—个或者多个对等节点进行直接
通信。无线Ｍｅｓｈ网络的这种结构特点为网络编码的应用提供
了很好的平台。
基金项甘：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａＮｏ．０７７３０１２。Ｎｏ．６０８７３０８２）；国家预研基金（ｔｈｅＰｒｅ－－ＲｅｓｅａｒｃｈＦｏｕｎ－ｄａｔｉｏｎｏｆＣｈｉｎａ）：中国博士后科学基金项目（ＣｈｉｎａＰｏｓｔｄｏｃｔｏｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｕｎｄｅｒＧｒａｎｔＮｏ．２００９０４５１１０８）；湖南省科技计划项目（ｔｈｅＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＰｌａｎｎｉｎｇＰｒｏｊｅｃｔｏｆＨｕｎａｎＰｒｏｖｉｎｃｅｕｎｄｅｒＧｒａｎｔＮｏ．２００９ＲＳ３０３６ｏ作者简介：夏卓群（１９７７一），男．博士研究生，讲师。ＣＣＦ学生会员．研究方向为无线Ｍｅｓｈ网络与网络编码；陈志刚（１９６４一），男，博士，教授，博士生导师，ＣＣＦ理事，主要研究方向为网络计算与分布式处理、计算机网络；沈小建（１９７７一）。男，博士研究生，研究方向为无线网络；赵明（１９７５一），男，博士后．研究方向为无线传感器网络。
收稿Ｈ期：２００９—１２—１５
修ＩｎＪ日期：２０１０－０２—２２
万方数据２２０１０．４６（１２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
ＷｉｒｅｌｅｓｓＭｅｓｈＣｌｉｅｎｔｓ图１混合结构的Ｍｅｓｈ结构图
２网络编码原理及发展
网络编码是一种融合编码和路由的信息交换技术，在传统
存储转发的路由方法基础上，通过允许对接收的多个数据包进
行编码信息融合，增加单次传输的信息量，提高嘲络吞吐量等性能。网络编码在单播的应用Ｈ如图２所示，节点Ａ需要向节
点ｃ发送一个数据包，而节点Ｃ也想向节点Ａ发送—个数据
包。由于传输范围的限制，这两个路径都必须经过转发节点艿。假没时间轴被划分为时Ｉ’日Ｊ槽，每传输—个数据包需要花费一个
时间槽。如果采用传统路由的调度方法，完成两个方向的中继
传输需要四个时问槽，如图２（ａ）所示。
（１）节点Ａ发送数据包到节点Ｂ；（２）节点Ｂ转发Ａ的数据包到节点Ｃ；
（３）节点ｃ发送数据包到节点Ｂ；
（４）节点曰转发Ｃ的数据包到节点Ａ。
对比传统路由的传输方案，采用无线网络编码技术只需要
三个时间槽来完成两个方向的中继传输，如图２（ｂ）所示。
（Ｉ）节点Ａ发送数据包到节点曰；
（２）节点ｃ发送数据包到节点Ｂ；
（３）节点曰转发经过异或操作的数据包ＡｏＢ。
节点Ａ对从Ｂ接收到的新数据包ＡｏＢ进行异或操作，根据自身的数据包可以获得Ｃ的数据包；同理，节点Ｃ能得到Ａ
的数据包。
图２单播中传统路由与网络编码传输的比较图
自Ａｈｌｓｗｅｄｅ等人［５１于２０００年提出网络编码概念，指出对
组播网络中的某些节点附加额外的编码操作能使组播传输达
到最大流最小割１６１定理确定的最大理论传输量以来，网络编码
引起了国际学术界的广泛关注，其理论和应用已成为通信领域
研究的新热点川。目前网络编码的理论研究已取得重要进展，在应用基础和
工程实践方面的研究正在全方位展开。Ｌｉ等人ｌ蚪证明了使用线
性网络编码已经能足够达到Ｍ络多播容量。ＫｏｅｔｔｅｒＲ等９提出
了阿络编码的代数框架，并证明了存在满足多播容量的线性时
不变编码。这两者的工作为网络编码的发展准备了必要的理论
条件。随机网络编码㈣是由ＨｏＴ、Ｍ∈ｄａｒｄ等人在２００３年提出的，它的提出拓宽了网络编码的适用场景，使得网络编码不再
局限于确定的网络拓扑和集中式算法。Ｃａｉｌ“利用分布式网络编
码来纠正整个网络中的差错，并论述了阱络编码在安全方面的应用旧，为网络编码增加了新的应用领域。
３无线Ｍｅｓｈ网络中的网络编码研究
随着研究的不断深入，｝哪络编码的研究重点开始从集中在理论方面转向应用到具体网络中。越来越多的学者将网络编码
应用到无线Ｍｅｓｈ网络中，为解决Ｍｅｓｈ嘲络问题提供了一条
新途径。这里着重分析和归纳无线Ｍｅｓｈ网络中网络编码的研究现状。具体可以分为以下儿个方面：
（１）网络编码在无线Ｍｅｓｈ中的实现方法。Ｋａｔｔｉ等人首次
提出一种基于网络编码技术的ＣＯＰＥ协｝义，并给出了一个具体
实现方案ｐ，１３１。ＣＯＰＥ协议采用嘲络编码中最简单和常用的异或线性编码（ＸＯＲ），即在编码节点输入ｘ个数据包（扎ｘ２，…，
机），通过编码操作ｙ≈．砭》１９…砭弧计算得到一个混合数据包，
然后将混合数据包在网络中传输；接收节点利用侦听到的编码信息和本地信息对混合数据包进行解码，从而获得自己需要的
数据包。ＣＯＰＥ协议有效地减少了网络中数据包的发送量，使
得无线Ｍｅｓｈ网络单播通信吞吐量增加。但是该协议是对多个数据流从不同节点经过一个节点时进行编码，对于同一个数据
流传输时没有考虑编码的实现，且秘路由技术的结合考虑得少。
文献１１４１针对ＣＯＰＥ，提出一个支持无线网络编码技术ＣＯＰＥ的按需路由协议ＯＣＲ。以提高无线Ｍｅｓｈ网中的网络吞吐量。
ＫａｉＦａｎ等『针对ＣＯＰＥ进行改进使得达到负载均衡。文献［１６】把重叠编码和线性编码结合起来，在无线网络实现混合数据包
的传输，该方法可以较大地提高网络的性能，但是重叠编码不
容易实现。文献ｆｌ７】在｝《】４络编码的实现上设计出了基于符号级的编码，可是对于细粒度的编码可能带来更大的计算开销，且
编码节点需较多的缓存空间。Ｋｅｓｈａｖａｘｚ铮”研究了在Ｍｅｓｈ中
万方数据