基于LBS及网络编码的HWMP路由协议

龙昭华，秦晓焕，刘达明，2

（1.重庆邮电大学 计算机科学与技术学院，重庆400065；2.重庆邮电大学 移通学院，重庆401520）

0 引 言

无线Mesh网络的标准化研究推动着无线Mesh技术的发展，IEEE 802.11s标 准 正 是 在 这 种 推 动 下 建 立 的［1，2］。HWMP［3］是IEEE 802.11s标准的默认路由协议。HWMP协议将按需路由和先验式路由有机的结合在了一起，同时兼顾了按需路由的灵活性及反应式路由的快速性，为网络中路由的查找提供了较好的方法。HWMP只适用于节点通信较少的网络中，如果无线网络中有很多节点要和外面的有线网络中节点进行通信，就会产生大量的数据流，此时就会造成根节点的拥塞。

为更好满足无线Mesh 网络路由协议快速、准确、高效、可扩展性的目标，本文在原来HWMP 协议生成先验式生成树的过程中加入节点信息本地链接库 （local association base，LBS），一定程度上减少了根节点的负担；在生成树建立以后，根据节点通信过程中数据流的特点，在原来协议的基础上加入了网络编码算法。仿真结果表明，加入编码算法后网络吞吐量在网络通信量增加时大大增加。

1 HWMP协议中存在的问题

HWMP协议中主要存在的问题是在无线Mesh网络的混合路由模式中 （按需路由＋到根节点的树），如果源节点没有到目的节点的路径，将把数据先发送到根节点。如果目的节点在Mesh网络中，根节点将数据转发到目的节点，从而建立从源节点到根节点再到目的节点的路径。这种方式虽然能使网内2个节点立即开始通信，但也存在一定缺陷：网络中的2个节点即使有最优的路径也得通过根节点进行数据的转发，根节点将成为网络中通信的瓶颈，同时非最优化路径的选择也将会造成时延［4］。在目前的无线Mesh网络的网络架构中，因为大部分Mesh节点都是固定的，所以网络拓扑也相对稳定。当HWMP 中基于先验式的生成树建立后，网络中就会存在多个核心节点，当网络中的通信流量很大时，就容易在这些节点处拥塞，网络编码则增加了转发数据时对数据包的处理能力，通过对收到的数据包进行一定的线性或者非线性编码，然后再转发出去，从而提高整个网络的吞吐量、均衡网络负载、降低能量消耗。在这些核心节点上将会有多个数据流通过，这就给核心节点进行流间编码创造了机会。

2 基于LBS的HWMP协议改进

2.1 现有的路由协议介绍

在HWMP协议的先验式生成树路由模式中，如果源节点没有到目的节点的路径，源节点不会发起路径查找而是将数据直接发给父节点。父节点收到数据包后会首先查看目的地址是否是自己的子节点，如果是则转发数据，如果不是则继续向上层父节点转发。当根节点MPP［5］收到数据包后会查看目的地址是否在Mesh网内部，如果是则通过先验树转发至内网，否则转发到外部网络。这种通信方式适合于网络中的数据大部分是与Mesh外网交互。然而当网络内部节点通信时，将会因为通信节点之间路径不是最优，且数据通信大部分集中于根节点，从而导致网络性能的降低。图1为Mesh网络内部节点通信时的情形。假设根节点MPP为1，源节点为4，目的节点为6，按照先验式生成树建立起来的节点4和节点6之间的路径为4—2—1—3—6，这时即使两节点间存在最优路径4—5—6，数据仍然是按4—2—1—3—6进行转发［6］，从而造成数据的时延和网络吞吐量的降低。

图1 无线Mesh网内部节点通信

2.2 改进的路由协议

HWMP先验式生成树路由模式在Mesh 网络节点与外部网的通信情境中有很大的优势；而按需路由模式则在Mesh网络内部节点的通信中占优势。因此，需要把两种模式的优点结合起来找到适合上述两种通信方式的最佳路径。

在先验式生成树模式中，网络生成树建立后，根节点MPP中有到网络中每个节点的路径信息，我们可以以此为基础建立简单的节点信息本地链接库LBS，网络中节点获知这些信息后就可以以这些信息来判定目的节点是否在Mesh网络内部，从而决定是否采用按需路由来获得最佳路径。LBS是一个hash表，表中内容为以网络中节点MAC地 址 为key 的hash 值［7］。通 过 对RANN 帧 的 扩 展 加 入LBS，可以将这些信息发送到网络中的每个节点。新的RANN 控制帧如图2所示。其中changed 字段B0位标示根节点MPP本地LBS信息是否改变，如为1则表明LBS信息改变，0则表示未改变，此时LBS 中只包含changed及CRC信息，changed B0位默认值为1。CRC 为hashID 的校验码，hashID 是根节点根据网络内节点MAC 值生成的hash值。根节点MPP产生RANN 消息及网络中节点收到RANN 消息处理过程如下：

（1）根节点MPP 生成RANN 消息：先验式生成树建立时，根节点将根据网络中节点的MAC地址建立hash表，以hash表中的hash值为基础建立LBS信息库。将LBS及其CRC加入RANN 中广播到Mesh网络中。如果本地LBS未改变将只在RANN 中加入LBS的CRC值。

（2）Mesh节点收到RANN 消息：网络中的Mesh节点收到RANN 时首先查看RANN 中的Changed B0位，当B0位为0，如果CRC与本地LBS的CRC值相同则忽略，否则将向根节点MP 发送请求LBS 的RLBS 帧；当B0 位为1时，将提取LBS更新节点本地的LBS库。

为了同步Mesh节点和根节点MP的LBS信息，Mesh节点可以向根节点MPP发送RLBS （Request LBS）帧，主动请求LBS信息。RLBS帧的帧格式如图3所示。

改进的Mesh 网内节点间路径选择算法伪代码如图4所示。

在新的路径选择算法中，如果Mesh 网内源节点需要向目的节点发送数据，若到目的节点的路径不在本地路由表中，源节点首先以目的节点MAC 为key，通过hash 函数得出相应的hashID 值，如果该值不存在本地LBS信息库中，源节点将把数据发给根节点MPP。否则源节点将把数据发给父节点，通过中间节点直接通信，同时源节点发出PREQ 消息开始新的路径发现过程。当源节点收到目的节点返回的RREP消息后，如果得到的新路径优于现有的路径，将使用新路径建立起与目的节点通信。通过这种新的路径选择算法，即保留了原有路径选择的优势，同时又可使网内节点间通信时可以找到最优的通信路径，降低了根节点转发数据的压力。

图2 HWMP RANN 控制帧格式及LBS字段

图3 HWMP RLBS帧格式

图4 改进的HWMP路径选择算法

3 HWMP协议中的机会主义网络编码

在无线Mesh网络的网络架构中，因为Mesh节点大部分都是固定的，所以网络拓扑也相对稳定［8，10］。当HWMP中基于先验式的生成树建立后，网络中就会存在多个核心节点，在这些核心节点上将会有多个数据流通过，这就给核心节点进行流间编码创造了机会。

图5是无线Mesh网络先验式生成树的一部分，核心节点为R，在COPE［9］中是采用邻节点间不断的交换接收报告来确定编码机会的，这需要浪费很大的带宽，而一旦接收报告丢失或者延迟也将导致无法进行最优编码。但在无线Mesh网络中，对于经过核心节点的数据流，如果知道两条数据流的下一跳节点是邻节点，就可以判断两个节点间可以互相侦听到对方发送的数据包，核心节点也就可以据此对这两条数据流数据包进行编码。从而省去了不断传输邻节点间接收报告。以图5为例，数据流f1，f2都经过核心节点R，通过获知邻节点A、B、D、E 的邻节点信息可知流f1和流f2的下一跳节点之间互为邻节点，这也就意味着A、B，D、E两对节点都分别可以侦听到对方发出的数据包。R 将A 发给D，E发给B 的数据包异或编码后随机选定D 为目的节点发出去，B、D 在收到编码数据包后根据收到的邻节点数据均可以正确解码，提取出自己所需要的数据。具体编码算法及流程将在下面进行分析。

图5 基于HWMP协议流间编码示例

3.1 HWMP协议流间网络编码算法

流间无线网络编码是在HWMP 协议先验式生成树的基础上，利用到根节点的生成树的路由表项来探测每个节点的编码机会，对于有编码机会的核心节点如果满足条件，就对经过核心节点的数据流进行编码，从而提高网络的吞吐量。流间网络编码主要用于无线Mesh网络基础网络架构，只要编码的节点所存储的与编码多个数据流相关的路由表项没变化，且编码节点与邻节点的拓扑链接状况良好，就可以对满足条件的数据流进行持续的相似编码操作，而不像现有的面向数据包的算法一样对每个数据包都要进行编码条件判断［11］。

3.2 编码算法

流间网络编码是在HWMP 先验式生成树的基础上，充分利用网络中节点所维护的路由表项来探测编码的机会。具体的算法流程如下：

（1）数据传输初始阶段：假设网络中存在n个独立的数据流f1，f2，...，fn，则n个数据流在HWMP 协议中采用先验式或者按需式的方式选定各自的路由。每一条数据流有源节点Srci和目的节点Dsti来唯一的确定。在流fi路径上的每个中间节点R 的路由表项包含以下信息：到达Dsti的下一跳节点NH（Dsti） （fi流经节点R 时的下一跳），到达Srci的下一跳节点PreHop（Srci）（fi流经节点R 时的上一跳节点，用于建立反向路径）。

（2）在未使用编码时，数据流f1，f2，...，fn分别沿着各自的路径传输数据。当引入无线网络编码的机制后，网络中存在多个数据流的节点 （即核心节点）在通信的过程中对流经当前节点的数据流路由表项进行检查，如果满足编码条件，就启动编码进程，否则只对数据包进行简单的存储转发。

假设网络中存在一个核心节点R，数据流fi，fj流经R，此时R 通过编码判定就可以决定是否可以对流fi数据包pifj数据包pj进行编码操作。

具体的编码算法伪代码如图6所示。

图6 流间网络编码算法

当节点R 发现fi，fj流经时，首先会探测编码的机会，如果fi流经R 时的下一跳节点NH（pi）为fj流经R时的上一跳节点PreH（pj）的邻节点，且如果fj流经R时的下一跳节点NH（pj）为fi流经R 时的上一跳节点Preh（pi）的邻节点，就可以判定流fi，fj的数据可以编码，如果节点R 处存储的关于流fi，fj路由信息表项PathTable（fi），PathTable（fj）未发生变化，且节点R维护的与流fi，fj有关的局部拓扑信息未变化，就可以对2个数据流的数据包进行持续的编码操作。

为了清楚的表述流间编码，下面结合一个具体的例子进行说明。图5中2个单播数据流f1：A →D 及f2：E→C。

（1）数据流fi，fj在传输初始阶段按照2.2节中改进的HWMP协议寻找通信路径路由。f1：A →R →D，f2：E→R →B →C，表1为节点R 处的主要的路由表项。表中的NHN （next hop neighbour）为新加的一条信息项，是R要传输的下一跳节点的邻居节点 （除去R 外）可通过3.4节改进的RM－AODV 的Hello报文获得。

表1 节点R 处部分路由表项

（2）但节点R 的缓存中有流f1的数据包p1i，流f2的数据包p2j时，根据节点R 处的路由表项 （表1）反应的各个数据包的上一跳和下一跳节点的信息，以及节点R 所维护的邻节点信息可知：p1i的下一跳节点D 是p2j上一跳节点E的邻节点p2j的下一跳节点B为p1i上一跳节点的邻节点，满足图6中的编码算法机会判定，可以进行网络编码。

于是节点R 可以发送编码数据包p1i⊕p2j，则R 的所有邻居节点A、B、D、E都可以收到该编码包。

因为p1i的下一跳节点D 是p2j上一跳节点E 的邻节点，所以节点D 可以侦听到E 发的数据包p2j，因此节点D可以解码。通过 （p1i⊕p2j）⊕p2j解 码 操 作，节 点D 会得到发给自己的数据包p1i。同理，节点E 也可以通过解码得到发给自己的数据包p2j。如果节点R 中存储的与流f1，f2相关的路由表项没有变化，且R 所维护的与f1，f2有关的局部邻节点信息没有变化，就可以持续的对流f1，f2进行编码操作。

3.3 解码算法

为了使收到编码数据包的节点能够识别出其中是否有发给自己的数据包，在编码数据包头部需要添加一个简单的编码包头，如图7所示。其中CodeType标明该数据包是否编码，RA1和RA2是编码包中每个源数据包的下一跳节点MAC地址；PKT＿ID 为源数据包的包ID 号，该ID 号有源数据包中的MAC地址及序列号所生成的hash值。

图7 编码头格式

网络中每个节点需要为每一个邻节点建立一个缓存队列，用来存储收到的邻节点的数据包。当网络中一个节点收到一个编码包时，首先查看编码包头，检测自己是否是编码包的接收端。如果是，就会检查自己的邻节点缓存队列，看是否有解码所需的数据包，如果有就进行相应的解码操作，提取出发给自己的源数据包。

由于编码包的发送时采用单播的形式，编码包头只包含一个节点的MAC 地址，发送编码包的节点无法收到全部目的节点的确认信息［12］。因此这种通信方式是不可靠的，为了提高链路层通信的可靠性，要求编码包头所指定的接收节点都要向上一跳的发送者发送ACK 确认帧。发送编码节点收到ACK 后将删除ACK 确认帧中标明的PKT＿ID 相对应的源数据包，从而避免数据包的重传。如果在一定的时间内未收到确认帧，为了降低丢包率，将把源数据包重新发送给未发确认帧的节点。

3.4 网络节点局部拓扑信息维护

在3.2节所述的编码算法中，编码机会的探测是以核心节点上下行邻节点的局部拓扑信息为基础的。为了获得节点的局部拓扑信息，本文采用对HWMP按需路由RM－AODV的HELLO报文扩展的方法。在RM－AODV 中，邻节点间需要间隔性的互相发送HELLO 报文来确认彼此的连接状态，以此来维护邻节点间的信息，因此对HELLO 报文进行扩展所需要的开销并不多。在扩展的HELLO 报文中，Neighbor－ID为以邻节点MAC地址为key的32位hash值。

4 仿真及性能分析

本文对改进协议在NS－3［13，14］下进行仿真。实现环境：在100m×100m 范围内随机分布50个节点。其它参数见表2。

在仿真环境，节点间数据流为512byte的UDP包。

表2 仿真参数

图8为网络中随着负载的增加系统吞吐量的变化。随着网络中数据流的增加，网络吞吐量也随之增大，当吞吐量达到峰值时，网络中的数据包冲突将导致系统吞吐量的下降。从图中可以看出，改进的协议吞吐量明显优于原有的协议。这是因为改进的协议中使用的基于LBS信息的方案降低了网络节点内部通信时核心节点处的数据包，从而降低了在核心节点处的数据拥塞；另外，无线网络编码的引入也使系统的吞吐量随之增加。

图8 网内节点通信网络吞吐量

图9为网络中数据包投递率，从图中可以看出随着网络中数据流的增加，数据包在中继节点冲突增加，导致数据包的投递率也随之下降。但是改进的协议的数据包投递率明显高于原有的协议，这是因为未改进的协议在节点内部通信时数据包集中于核心节点 （特别是根节点）处，从而导致网络拥塞严重，数据包冲突增大，使丢包率增大，降低了数据包的投递率。

图10为随着网络中数据流的增加数据包的端到端时延。从图中可以看出随着数据流的增加，数据包的端到端时延随着增加，这是因为网络中通信量增大导致冲突的增加。而改进的HWMP 协议的端到端时延要优于为改进的协议，这是因为改进的HWMP 协议中使用了更加优化的路由判据使选择的路径更优，另外基于LBS消息的改进与原有的协议相比，网络内部节点通信时选择的路径也是最优的，所以最终使得改进的协议优于原来的协议。

图9 网内节点通信数据包投递率

图10 网内节点通信平均端到端时延

5 结束语

本文主要选定了IEEE 802.11s中关于无线Mesh网络的默认路由协议HWMP 协议作为研究的对象。通过对原来的HWMP路由协议的改进，无线Mesh网络内部节点通信时在保持HWMP 协议原来优势的基础上，使节点间的路径达到最优，从而降低了网络内部节点通信的端到端时延，提高了网络性能。结合HWMP协议的基本特点，提出了基于HWMP协议的流间无线网络编码，并给出了具体的编码算法和解码算法。对HWMP协议中的RM－AODV［14］协议的HELLO报文进行了扩充，使其能携带邻节点的基本信息与其它邻节点进行交换，从而使邻节点间能够获得两跳内的局部拓扑信息，为流间无线网络的编码机会探测提供了依据。仿真结果表明，基于HWMP协议的无线流间编码对提高无线Mesh网络的性能是行之有效的。

［1］Dimitrios Koutsonikolas，Hu Y Charlie，Wang Chih－Chun.Pacifier：High－throughput，reliable multicast without“crying babies”in wireless Mesh networks ［C］／／Proceedings of the 28th IEEE Communications Society Conference on Computer Communications.IEEE，2009：2473－2481.

［2］Sun Xuemei，Li Chunqing，Zhang Mingwei.A QoS routing algorithm based on culture－particle swarm optimization in wireless Mesh networks ［C］／／Proceedings of 6th International Conference on Wireless Communications，Networking and Mobile Computing.IEEE，2010：1－4.

［3］Wang X，Lim AO.IEEE 802.11s wireless Mesh networks：Framework and challenges ［J］.Ad－Hoc Networks，2008，6（1）：32－40.

［4］Hu Xiaobing，Mark Leeson，Evor Hines.An effective genetic algorithm for network coding ［J］.Computers and Operations Research，2012，39 （5）：952－963.

［5］Da Gang G.Research on 802.11sRM－AODV path selection protocol［J］.Jiangxi Science，2010，2 （l）：31－40.

［6］Bakhshi Bahador，Siavash Khorsandi.Complexity and design of QoS routing algorithms in wireless Mesh networks ［J］.Computer Communications，2011，34 （14）：1722－1737.

［7］Pinheiro M，Sampaio S，Vasques F，et al.A DHT－based approach for path selection and message forwarding in IEEE 802.11sindustrial wireless MES－h networks ［C］／／IEEE Conference on Emerging Technologies ＆ Factory Automation.IEEE，2009：1－10.

［8］Kowalik K，Davis M.Why are there so many routing protocols for wireless Mesh networks ［C］／／Irish Signaland Systems Conference，2006.

［9］Sengupta S，Rayanchu S，Banerjee S.Network coding－aware routing in wireless networks［J］.IEEE／ACM Transactions on Networking，2010，18 （4）：1158－1170.

［10］Perkins C，Belding－Royer E，Das S.IETF RFC 3561：Ad Hoc on－demand distance vector（AODV）routing ［S］.2010.

［11］Dong Q，Wu J，Hu W，et al.Practical network coding in wireless networks ［C］／／Proceedings of the 13th Annual ACM International Conference on Mobilecomputing and Networking.ACM，2007：306－309.

［12］Dimitrios Koutsonikolas，Charlie Hu Y，Wang Chih－Chun.XCOR：Synergistic interflow network coding and opportunistic routing ［C］／／Proceedings of the ACM International Conference on Mobile Computing and Networking.ACM，2008：2980－2989.

［13］Xi Yufang，Edmund M Yeh.Distributed algorithms for minimum cost multicast with network coding ［J］.IEEE／ACM Transactions on Networking，2010，18 （2）：379－392.

［14］Yang Zhenyu，Li Ming，Lou Wenjing.R－Code：Network coding based reliable broadcast in wireless Mesh networks［J］.Ad Hoc Networks，2011，9 （5）：788－798.