基于改进MORE协议的无线Mesh网络簇内路由研究

尹凤杰，关博文

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引言

无线Mesh网络(WMN)作为一种关键技术越来越受到研究人员的关注，已经成为宽带家庭网络、社区网络和企业网络等许多应用的关键技术.无线Mesh网络是自组织和自配置网络，其中参与节点能够自动建立和维护连接，还能快速部署，具有易于维护、成本低并且可伸缩性高的特点.路由协议作为推动无线网络发展的关键技术，是当前国内外研究人员较为注重的研究热点.现有的无线Mesh网络的路由协议大多是沿用了已有的Ad hoc网络路由协议.移动无线网络因其高移动性，所用路由协议多为被动路由协议.而无线Mesh网络与典型的Ad hoc网络如移动自组网(MANET)[1]、无线传感器网络(WSNs)[2]、车载自组网(VANETs)[3]等不同，无线Mesh网络骨干的中继Mesh路由器是静态网格路由器，因此，混合路由协议更加适合无线Mesh网络.

已有的无线Mesh网络混合路由协议中，人们更多地关注网络的QoS(Quality of Service)指标，如文献[4]提出一种针对无线Mesh局域网的解决方案，无线Mesh路由(WMR)在最小带宽和最大端到端延迟方面提供了QoS保证.文献[5]提出一种基于QoS的混合路由协议，该协议是在由基于IEEE802.16j的基础设施和不同的基于IEEE802.11s的客户端组成的混合的无线网络体系结构的基础上提出的，文中所提出的HQMR(High Quality Mesh Router)路由协议在无线Mesh网络中提供了QoS保证，并且为了降低网络负载，提出了一种面向IEEE802.16j全局无线网络体系结构的聚类算法.HQMR协议有效地保证了无线Mesh网络QoS指标，在平均吞吐量、平均端到端延迟和平均抖动方面有很好的表现.但是QoS更多体现网络技术层面的性能，当今的网络评价标准更多地应该体现在用户体验方面，即QoE(Quality of Experience)指标.与QoS相比，QoE更能体现用户主观体验，并且所涵盖的物理指标也更为广泛.所以，以QoE这一能够体现用户主观感受的指标来评价网络的性能是更令人信服的.文献[6]提出一种OLSR(Optimized Link State Routing)路由协议，它基于度量的动态选择，并在模糊链路成本中确定多媒体数据包的最佳路由，同时实现了多媒体应用的QoS和QoE要求，但是因为模糊规则的收敛性较差，所以最终的效果有限.文献[7]针对视频流、音频流、普通文件数据流3种网络场景设计了完整的路由协议，在3种网络场景中QoE指标有明显的优化效果，同时具有较低的控制报文开销.研究使用基于双向强化学习的路由算法，对不同服务的QoE进行预测，这可能会导致预估结果与实际结果相差较大，降低QoE的指标.

上述文献主要是面向3种数据流通用的优化路由协议，而现在的网络更受用户青睐的是视频数据，也就是视频流传输，本文以视频流媒体为背景，从簇内路由方面入手，加入网络编码，将传统的MORE(MAC-independent Opportunistic Routing & Encoding)协议进行改进，使其能够降低网络传输的延迟，提高视频的用户体验质量.

1 基于QoE的分簇路由协议

为了使用本文的路由协议，实验先将路由器分簇.为了实现分簇，网络中所有的Mesh路由器会将自身的信息以Hello数据包的形式周期性地广播给邻居，以此让网络中的路由器完成邻居Mesh路由器列表的建立，Hello数据包的格式如图1所示.邻居路由器在收到Hello数据包后会根据数据包的内容更新邻居表的内容，这一列表在簇头以及簇成员选择的过程中有着很大的作用.邻居表的格式如图2所示.

图1 Hello数据包的格式

图2 邻居表的格式

对于满足QoE约束的路由器，邻居路由器将会继续转发数据包，关于Hello数据包的发送过程将一直持续，直到它满足距离约束以及期望传输约束，式(1)和式(2)给出关于距离约束以及期望传输约束的条件.

(1)

(2)

其中，d(MRi，MRi+1)表示2个Mesh路由之间的距离，d(GW，MRi)表示网关到路由器的距离，dmax表示最大距离，EXT(MRi，MRi+1)表示2个Mesh路由之间的所需的期望传输数，EXT(GW，MRi)表示网关到路由器的所需的期望传输数，EXTmax表示最大的期望传输数，满足式(1)以及式(2)中给出的约束的会被划分为簇内成员，分簇之后，同一簇内的路由器需要选择权重最大的簇成员作为簇头，Mesh路由器的权重计算由式(3)表示，其中，W(v)表示路由器的权重，D(v)表示Mesh路由器的邻居数量，B(v)表示Mesh路由器的可用带宽，α、β是缩放因子.

W(v)=α×D(v)+β×B(v)

(3)

簇间路由协议为Mesh网络簇间路由协议(ICMR)，该协议主要是在簇间建立通信，当接收到数据请求，如果目标路由器不在同一簇内，则使用反应式路由协议建立通信，簇头将请求转发到Mesh网关，Mesh网关将会把包含Mesh路由器以及目的路由器所在的簇的簇头地址回复给发出请求的簇头，随后簇头会启动请求程序，在源Mesh路由器以及目的Mesh路由器之间，寻找满足丢包率以及视频编码比特率等QoE约束的最佳路径.

2 基于改进的MORE协议的簇内路由协议

本文的路由协议是针对簇内通信提出的，当簇头接收到簇成员发来的数据传输请求时，簇头会首先检查自己的路由表，如果在路由表中找到目的地址，目的地址处于簇内，那么就可以使用簇内路由协议直接将数据转发至目的地址，避免了向网关发送路由请求.在以视频传输为主要传输目标的网络中，传统的“储存—转发”的数据处理方式会在一定程度上影响网络的延迟，从而影响用户的服务体验，因此，本文采取在节点处加入网络编码的方式来降低网络延迟，即在数据传输时采用“储存—编码—转发”机制.

网络编码的原理[8]如图3所示.图中有3个节点，节点S需要将分组信息包p1传输至节点D，与此同时，节点D也要将分组信息包p2传输至节点S，因为2个节点受传输距离的限制，无法直接将信息包传输至目的节点，因此需要通过中间节点R进行数据的转发，以此来完成本次传输.按照图3(a)中传统的储存转发式结构进行本次的数据传输，在没有数据包丢失的情况下，实验共需要4次传输才能够完成本次的信息交换.而使用加入了网络编码的结构之后，如图3(b)所示，当节点S和节点D分别将信息包p1和p2传输至节点R之后，节点R侦察到有编码的机会，便会将2个信息包进行编码操作，将编码后的数据包以广播的形式传输给节点S和节点D，2个节点分别解码后就可以得到期望的信息包.这种方式可以有效地节省一次传输.在网络中，编码的机会越多，那么通过网络编码获得的收益也就越大，因此在视频传输中，选择网络编码的数据传输方式就可以在很大程度上降低网络的延迟.

图3 储存转发结构与网络编码结构

MORE协议是一种改进的机会路由协议[9]，它使用了随机线性编码，在数据包转发之前会随机选择系数将数据包线性组合，生成的数据包会将各自使用的系数封装在一个特殊的报头之中，一般将其称为MORE报头，目的节点收到适当数量的数据包后，就会通过逆函数执行解码过程，以得到需要接收的数据包.MORE协议的传输调度依赖于CSMA/CA，就吞吐量性能而言优于ExOR等机会路由协议，具有一定的研究意义.此外，为了保证传输的质量，MORE协议有自己的确认机制，在源和中继节点完成数据包的发送及转发之后，源和中继节点会持续地发送和重传数据包，这一过程会一直持续到目的节点发送回确认信息为止.这会很大程度上保证数据包的传输成功率，但是对时延也会有不小的影响，而在视频传输过程中按时传输往往比可靠更为重要.因此本文对MORE协议作了如下改进：1)将随机线性编码改变为延迟最小化网络编码；2)增加拒绝确认机制.

图4 延迟最小化网络编码算法流程

2.1 延迟最小化网络编码

延迟最小化网络编码是最小化系统的总体接入时间，也就是从网络中的所有用户出发考虑最小的时延.对于单个用户而言，假设该用户所需的数据包数量为m，那么如果服务器在前m次广播中，每一次都能够得到自己所需要的新数据包，那么该用户就可以得到理论上的最小接入时间，即m个单位数据包的传输时间m.也就可以理解为，单个用户所需的接入时间取决于该用户所需数据包在整个服务器的广播序列中所占的位置，当所需数据包发送出得越早，用户的时延也就可相应降低，用户的服务体验质量就会越好.但是在日常中，整个系统往往不止1个用户，如果系统每次的广播都只针对某一用户的数据请求，该用户就可以以最短的时间获得数据包，但是系统中的其他用户就将迟迟无法得到自己所请求的数据包，对整个系统而言，数据的传输效率就会降低，整体时延将会上升，整体用户的服务体验质量极有可能变得不可接受.因此，在数据包传输时需要考虑整体系统，以全局的时延优化作为目标.那么，问题就变成了在每次传输中，如何将数据包编码能够满足所有的用户请求数据.

延迟最小化网络编码的算法流程如图4所示.M表示编码组合能够定位到的用户数量，N表示用户总数.该算法流程将接收到的第1个请求数据包作为搜索条件，计算该数据包能够定位到的用户数量，如果所定位的用户数量等于用户的总数，那么该数据包就是本次传输的最优选择，算法随即将该数据包广播，并且更新用户的数据包接收以及请求信息，如果所定位的用户数量不等于用户总数，那么将编码组合的大小增加至2，重新计算这2个数据包所能定位的用户数量，如果等于用户总数，就将这一编码组合广播给用户，并更新接收和请求数据，如果不等于用户总数，就将编码组合大小增加至3，并继续重复上述过程.算法的搜索会一直持续，直至找到能够定位到所有的用户的编码组合，并将其广播给用户，发送完成后随即更新用户接收到的数据包以及请求数据包的信息.上述整个算法过程会不断重复，直到所有用户接收到所请求的数据包.

下面以一个实例来说明时延最小化网络编码传输方式.假设系统中共有4个用户u1、u2、u3、u4，他们已经接收到的数据包和正在请求的数据包如表1所示：

表1 系统中用户已接收到的数据包与请求数据包

首先生成编码数据集S={a1、a2、a3、a5、a6、a7、b2、b3、b4、b6、c2、c4、c7}，然后定位数据包a1所请求的用户，只有用户u2请求，显然不满足条件中定位所有的用户，然后加入数据包a2，同样还是只有用户u2请求此数据包，加入数据包a3，此时有用户u1、u3请求此数据包，这时定位用户数为3，但是还未满足条件，可以发现直到搜索至数据包a7时，编码包{a1、a2、a3、a5、a6、a7}满足定位到全部用户这一条件，因此将这一编码包作为本轮的最优编码包广播给用户，第1轮广播后，用户已收到的数据包与请求的数据包如表2所示.以此类推经过4轮广播后能够满足所有用户的请求.

表2 第1轮广播后用户已收到数据包与请求数据包

2.2 增加拒绝确认机制

在原本的MORE协议中，源会持续发送同一批数据包直到接收到目的节点发回的确认通知，再开始下一批数据包的转发.很显然，这种机制很难满足时间的要求，因此，在改进的MORE协议中，通过强制源节点和中继节点广播有限的时间来克服这一问题，在这一协议中，源节点不会等待目的节点的确认信息，在源节点将数据包广播之后，它会启动1个倒计时器，所启动的倒计时器为1个特定的时间间隔定义为τ，它以视频流施加的时间约束来估计τ，假定传输1组帧速率为f，大小为g的图片的视频流，该视频流必须在小于或等于g/f的时间段内转发.如果该组图片在平均l个大小为b的包中使用封装，那么每一批数据包转发需要等待τ，如式(4)所示.在倒计时时间归零之后，立即启动下一批数据包的广播，而不管上一批是否交付成功.

τ=(g/f)/(l/k)=gk/fl

(4)

拒绝确认机制可以很好地控制转发所需时间，这是一个极好的特性，因为对于源和中继节点来说，持续发送已经过时的数据包是十分浪费能量和时间的.因此在不需要考虑数据转发是否可靠的情况下，增加拒绝确认机制能够最大程度上降低时延.

3 仿真与分析

本实验采用MATLAB仿真软件进行实验结果测量及分析.通过文献[10]可以得知，对于网络时延的影响主要有3个方面，用户平均储存数据的长度、用户平均请求的数据长度以及用户数，因此，本实验以这3点为变量进行比较.实验将加入了基于改进MORE协议的簇内路由的分簇协议(IMIC)与加入基于原始MORE协议的簇内路由的分簇协议(MIC)以及基于排序蚁群算法的分簇路由协议(SACR)在时延方面进行比较.

1)首先对比当用户平均储存数据长度不同时，基于改进的MORE协议的簇内路由协议的性能.本次实验模拟1个用户数为4的场景，仿真时给每个用户随机生成大小为10的请求数据包，同时生成1个大小在4到14之间变化的已储存数据包.进行1 000次随机实验并求出实验的平均值.

图5 用户平均储存长度不同时的时延

仿真结果如图5所示，可以看出基于改进的MORE协议的簇内路由协议当用户平均储存数据长度较低时，原始的MORE协议有着更好的表现，但是当用户平均储存数据长度增加时，改进的MORE协议性能逐渐改进，并且优于其余2个路由协议.这是因为时延最小化网络编码，对于时延的优化很大程度上取决于用户所请求的数据包与用户已储存的数据包之间的重合度，当用户本身储存的数据包较少时，时延最小化网络编码能够搜寻到的最优编码机会也相应减少，因此相对应的时延就会较长，而随着用户储存的数据包逐渐增多，延迟最小化网络编码能够搜索到最优编码包的概率也将增加，时延相应也会降低.而在实际应用中，用户所储存的数据包与请求的数据包重合度会远大于实验所示.由此来看，基于改进MORE协议的簇内路由协议在时延方面有着一定的提升.

图6 用户平均请求长度不同时的时延

2)本次实验分析用户平均请求数据长度对时延的影响，同样模拟1个用户数为4的仿真场景，仿真时随机分配给每个用户大小为10的数据储存包，大小在1到10之间的数据请求包.进行1 000次随机实验并取平均值.

图6显示实验结果，可以看出基于改进MORE协议的簇内路由协议在所有不同的数据请求长度下，时延均低于基于原始MORE协议的簇内路由协议和基于排序蚁群算法的分簇路由协议.正如在上一个实验中所讨论的，用户的平均储存数据足够大，每个用户的储存数据与请求数据的重合度大概率也会增大，时延最小化网络编码能够寻找到最优编码包的机会同时增加.从图6的趋势可以看出，当用户平均储存数据长度一定时，请求数据长度越大，系统时延相应也会增加.

图7 用户数不同时的时延

3)本次实验需要验证用户数对系统时延的影响，因此分别选择了用户数为4、6、8、10的情况，仿真时，随机向每个用户分配大小相同的用户储存数据包以及请求数据包.实验结果如图7所示，可以发现，在不同用户数情况下，基于改进的MORE协议的簇内路由优化效果并无明显变化，说明所提出的路由协议的优化能力并不受用户数量的影响.

4 结论

本文提出了一种基于改进的MORE协议的簇内路由协议，该协议以MORE协议为基础，将MORE协议中所使用的随机线性编码改进为时延最小化网络编码，并且加入了拒绝确认机制，有效地降低了簇内路由在数据包传输过程中的时延.实验表明，基于改进MORE协议的簇内路由能够有效地提升用户体验质量在时间方面的要求，使得无线Mesh网络在QoE方面的性能进一步提高.