无线Mesh网络下基于网络编码的机会路由协议的研究

朱朗 张宁

一、引言

现有的无线服务主要是基于蜂窝网和无线局域网。蜂窝网是在基于基站的基础上为直径几公里范围内的设备提供网络服务。而无线局域网的设计是覆盖百米左右的区域，然后通过有线网络接入。公共的频谱使用权虽然让系统成本降低，但也对抗干扰能力提出了高要求。Mesh网络与这两者的架构是有本质的区别。未来Mesh可以作为蜂窝网和无线局域网的扩充，它可以弥补两者的劣势，甚至融合到蜂窝网和无线局域网中，形成无线网络的统一。，Mesh网络还可以独立存在，用在特殊场景如车辆自组织网，无线传感器网络，战时通信等。无线Mesh网络技术的瓶颈之一就是路由协议的设计。网络编码和机会路由作为新兴技术能够有效地提高网络系统的吞吐量和可靠性，已经成为研究的热点。

二、网络编码和机会路由

网络编码起始于Ahlswede，Cai等的一篇开创性论文。该论文指出，传统路由的基本作用是存储和转发，假设允许网络中间节点对传输的信息可以进行简单的编码处理，那么基于新路由参与的网络多播就能够达到理论上的最大传输容量。这也引出了最大流最小割原理：一个网络的最大多播吞吐量等于分割源节点和目的节点的最小割集容量。随着研究的深入，研究者发现，网络编码不仅能改善网络的吞吐量，在均衡网络负载，降低节点能耗，提高网络安全性等方面也有较好的表现。

机会路由（也称机会转发）的概念是2004年由麻省理工学院的Biswas等人提出。机会路由中每个节点都有自己的一个候选转发节点集合，每次传递信息时，并没有确定下一跳节点，而是根据广播数据分组来选择合适的候选节点，通过对比接收到分组数据的应答顺序给出候选节点的优先级，从而选择最佳的下一跳来转发数据。机会路由的突出优点是增加单跳传输的可靠性，减少总的传输跳数来提高吞吐量。

三、主流协议

第一个把两者相结合是2006年提出的独立于MAC层的机会路由与编码—MORE协议。简单地说，MORE协议是把流内随机网络编码与机会路由相结合。MORE的路由策略如下：源节点把需要传送的文件以K个数据包分批，每批的K值不同。这些K个数据包叫做原生数据包。当MAC层准备发送时，源节点对K个数据包随机线性编码后广播编码包。源节点对每个数据包附加一个MORE层，用来说明这个数据包的编码向量，批次，源节点，多个目的节点IP地址，以及转发节点集。转发节点以ETX值排序。源节点一直发送当前批次的数据包直到收到目的节点的确认包，然后发送下一批次数据包。中间节点监听所有无线数据传输，当一个节点监听到一个数据包时，先检查自己是否属于转发节点集中，如果是，检查是否为更新包，如果是储存，否则丢弃。当中间节点属于转发节点时，这会触发一个程序，将监听到的数据包再次随机线性编码并广播，这时的数据包可能为更新包，也可能不是更新包。目的节点在接收数据包时，首先检查是否为当前批次的更新包，即检查编码向量是否线性相关。线性相关，则不是更新包，丢弃。只要目的节点收到K个更新包，在数学理论上就能证明可以正确解码。此时目的节点会发送ACK确认包通过最佳路径传输给源节点，以发送下一批次的数据。每个节点收到确认包之后相对于数据包会优先发送。最优化多路径网络编码路由（OMNC）继承了MORE协议的思想，也是通过机会路由来传输编码后的数据。不仅如此，OMNC还考虑了节点的编码能力、信道的通信质量、网络的广播速率等因素来设计路由度量以选择最优路径来提高吞吐量。OMNC也是流内网络编码机会路由协议。

与之对应的流间网络编码机会路由协议主要有CAOR，BEND和PACE。CAOR协议是在COPE协议的基础上引入了机会路由策略。它可以提高多流无线网络的吞吐量。具体做法是将编码效率高的节点加入转发节点集，通过排序选择较高的编码节点。这需要维护相邻两跳节点的信息。BEND协议相比较CAOR是实现在MAC层上的，PACE协议引入了区域联合编码与传输算法，它实行了网络多点联合编码，以增益的大小来对转发节点进行排序。它的优势在于减少了碰撞，提高了系统的传输效率。

基于网络编码和机会路由协议的重点在于（1）如何选择候选转发节点。目前已经有很多路由度量作为选择标准。经典的路由测度如跳数HOP，预期传输次数ETX，期望传输时间ETT等，近年来考虑较全面的路由测度如加权累计期望传输时间WCETT，接口和信道切换测度MIC，干扰感知路由测度iAWARE。任何路由度量都具有两面性，因为真实环境的复杂性决定了路由度量趋向于模拟真实环境，但这无疑也会增加额外的计算负担。研究的难点就是在实际网络环境中如何取舍。（2）如何协调候选转发节点。候选转发节点的加入，退出和转发会带来数据重发、解码、冲突、冗余等问题，从而降低系统性能。目前的协调机制有数据分组应答模式、控制包应答模式和无协调模式。对研究者来说，全面设计新地无线Mesh路由协议主要从多借口多信道、链路质量、QOS保障、跨层设计、结合调度等方面进行突破。

四、结语

无线Mesh网络既能自组织、自愈合，又可与当前的蜂窝网和WLAN网络相融合，提高现有的网络服务，已成为未来宽带接入技术的研究热点。而其中基于网络编码和机会路由两大技术的路由协议在吞吐量和可靠性方面有着巨大的优势，但是还没有统一的路由算法得到广泛的认可。