基于预测时延的无线mesh网络组播路由算法*

王 震，常颖华

(重庆大学通信工程学院，重庆400044)

0 引言

无线mesh网络作为最有潜力的下一代网络［1］。mesh拓扑结构能够提供高的可靠性、覆盖和稳定性。满足用户随时随地获得高质量的无线宽带服务是无线mesh网络设计目标之一，组播作为一种能有效节约网络资源的通信服务成为发展方向［2］。研究有效的组播路由算法是实现这些功能的基础，这已成为无线Mesh网络研究的热点。研究人员提出了多种路由算法，主要分为两类:一是基于树，如AMRoute［3］，AMRIS［4］，它们在源节点与接收节点之间提供一条路由;另外一类是基于格网的，如 ODMRP［5］，CAMP，它们在源节点和目的节点形成多条路由，从而提高路由的可靠性。基于网格的路由算法尽管在可靠性方面提高，但算法复杂度、路由形成机制上比基于树的复杂［6］。组播路由算法为了达到QoS要求，提出了很多改进措施，如采用遗传算法、退火算法等启发式算法［7～10］。这些算法复杂度高。基于此提出一种具有满足低时延QoS保障组播路由算法。这种路由算法具有传播时延小，高可靠性。

1 基于预测时延的组播路由算法基本思想

首先，采用预测时延的算法获得源节点S到目的节点D的最短传输时延路径。从而保障源节点到目的节点间具有最短的传输时延，使得组播业务获得低时延的QoS保障。根据预测时延算法获得每条路由的传输时延算法后，将路由路径按照传输时延从高到低排列，同时按照源节点到目的节点的跳数分层。将距离源节点到目的节点第一跳设置为第一层，依次类推。接着由低时延路径的高层次节点向高时延节点寻找距离一跳的节点，如果存在就删除低时延路径的从源节点到此节点的路径。从而获得路径复用，同时获得最短时延的组播树T。如果有节点离开组播树T，由于保存了已删除的路径，只需要重新采用路径，使得路由算法不需要重新执行。如果有新的节点加入到组播树T，节点首先建立到源节点的最短时延路径P，接着合并路径。这种路由算法能够保障无线mesh网络的业务QoS具有高可靠性。路由算法具有局部更新的能力，使得路由算法具有高效性。那么这个路由算法最基础的是寻找预测传输时间的路径。下面详细介绍这种方法。

2 基于传输预测时间的路径选择

2.1 传输时间预测的基本思路

根据节点位置将干扰通信量分为相邻节点通信量CS和隐含节点通信量HT。CS通信量是处于链路发射机载波侦听范围内所有节点积累的通信量。在无线网络中，当发送节点要通过链路发送一个数据帧时，它必须与处于CS范围内的节点竞争接入到网络，这样较大的CS通信量将导致较长的接入时间。HT通信量是由于链路接收节点侦听范围内节点累积的通信量，但是其链路发送节点不在载波侦听范围。较大的HT通信量将导致较多的碰撞发生，这将导致较长的传输时间。为了预测通信传输时间，就必须要对其位置进行区分。

节点到数据中心都选择最短路径，那么，每个节点到数据中心的传输时间预测定义为分组进入链路发送终端队列的时刻开始到其发送成功到达数据中心或被丢弃的时间，其中包含队列延迟和分组服务时间。使用M/M/1模型来计算队列延迟。那么，特定的链路传输时间与现存的CS通信量、HT通信量和自通信量相关。链路传输时间表示为(τCS，τHT，τ)，其中，τCS和 τHT分布表示平均 CS 通信速率和HT通信速率。使用2个参数来表示，即载波侦听因子(CSF)和隐含端因子(HTF)来表示自通信的干扰。链路的CSF是CS接收机范围内相同信道中的链路数量，但不处于发送节点范围内。对于从节点i到节点j的链路，由其通信量干扰增加的HT通信量为CSFij·τ，而由自通信量干扰增加的HT通信量为HTFij·τ。其中，τ为沿着最短路径的通信量速率。

对于链路(i，j)，考虑到自身通信量干扰，CS通信量变为 τCS+CSFij·τ，而 HT 通信量变为 τHT+HTFij·τ。因此，考虑自身干扰通信量的前提下，两节点间预测通信时间为(τCS+CSFij·τ，τHT+HTFij·τ，τ)。对于 n 条路径，根据每天链路在路径中的位置来获得CSF和HTF。将每条链路的预测传输时间求和，可以得到整个最短路径的预测传输时间。从每个节点域中找出时间最短节点。

2.2 传输时间预测

基于IEEE 802.11协议的流量引入一个新的MAC模型，根据给定的和干扰的通信量来估计分组碰撞概率。假定网络中所有节点按照指数规律发送数据，采用泊松通信量模型。为了进行下一步分析，引入表1的符号。

表1 采用符号列表Tab 1 The list of symbol

其中，τnormCS(i，j)为链路(i，j)归一化的 CS 通信量。

图1 两种情况引起的信道忙Fig 1 Arousing the channel being busy in two conditions

引起DATA分组碰撞的可能情况如图2所示。DATA分组的成功发送概率PiDATA分组传输时段内CHij中没有链路传输任意分组的概率相等，即

其中，τnormht(i，j)为链路(i，j)归一化的 CS 通信量。

图2 导致DATA分组冲突的2种情况Fig 2 Arousing the collision of data packets in two conditions

为了获得分组服务时间，考虑节点i到节点j的k次重传。首先，节点需要等待使信道空闲，满足DIFS的要求。这将消耗DIFS/PiDIFS时间。然后，回退计数器选定一个回退时隙的随机数。考虑到回退计数器的停止所期望的回退时隙的时间间隔为

在IEEE 802.11中，回退计数器的值在0与竞争窗口CW之间随机选取。CW典型值最大为1023，最小为31.初始化是选择最小值，不成功时，CW被加倍，直到达到最大CW。在k次重传回退时隙的平均数为

如果DATA分组在k次发送没有成功，则花费的全部时间为

如果DATA分组在第k次发送时被成功传送，则花费的全部时间为

为了获得队列延迟时间，使用M/M/1队列模型。令φ表示分组由链路(i，j)传输的速率，而分组服务速率为ε，其中，ε =1/TMAC。

M/M/1队列的队列延迟为

将ε代入到上式，有

将队列延迟为分组服务时间求和，得到预测传输时延T(τCS，τHT，τ)为

因此，通过上述相关公式的推证和式(7)，式(10)可以获得从源节点S到目的节点D的最短传输时延路径。

3 基于传输预测时间的组播路由算法

由上面获得每条由源节点S到目的节点D的预测传输时延后，就可以执行组播路由算法。

路由算法的执行流程如图3所示。

图3 算法执行流程Fig 3 Execution flow chart of algorithm

4 算法仿真与分析

在NS—2中，设置在IEEE 802.11 Ad Hoc组网环境下，分别采用新路由协议和MAODV的对比。MAODV是一种共享树组播路由协议，一种典型的组播路由协议，是在路由协议AODV基础上增加了组播功能。

1)平均端到端时延:该参数包括了所有可能的时延:源节点路由发现时延、路径中断修复时延、多跳转发时延、数据报文处理时延、接口排队时延、MAC层分组重传时延、链路传播时延等。通过分析证明在同样条件下，新路由协议的传输时延要低于MAODV，这是由于新协议对传输时延进行预测，得到最短时延路径，从而使得传输时延要低于MAODV。端到端传输时延对比如图4。

图4 端到端传输时延对比Fig 4 Comparison of the time delay of end to end transmission

2)节点吞吐率:新协议通过传输时延预测寻找最短时延路径的同时，也避免了节点间干扰。如图5所示，组播树节点吞吐率随着时间变化，节点吞吐率没有较大变化。新的路由算法要比MAODV的吞吐率高，新算法能够提高网络的吞吐性能。在节点密度较小的情况下，网络的吞吐率要比节点密度大时高，如图6。随着节点密度的增加，节点吞吐率下降，这是由于节点间干扰增大。在节点密度较小的情况下，算法能够获得较高的吞吐率。

图5 节点吞吐率对比Fig 5 Comparison of throughput rate of nodes

图6 不同节点密度下节点吞吐率对比Fig 6 Comparison of throughput rate in different nodes density

5 结论

本文采用预测时延算法，通过对源节点到目的节点传输数据的时延预测，获得源节点到目的节点最短时延的路径。通过对路径进行合并，得到组播路由树。组播路由树中的路由具有传输时延小、吞吐率高特点。同时利用保存合并前的路径，使得路由在受到破坏时，能够局部修复，路由具有高可靠性。通过仿真证明这种算法的性能是优越的。

［1］Akyildiz I F，Wang Xudong.Wireless mesh network:A survey［J］.Computer Networks，2005，47:445-487.

［2］Huang Jun，LiuYanbing.MOEAQ:A QoS-aware multicast routing algorithm for MANET［J］.Expert Systems with Applications，2010，37(3):1391-1399.

［3］Jason X，Rajesh R T.AM route:Ad Hoc multicast routing protocol mobile networks and applications［J］.Multipoint Communication in Wireless Mobile Networks，2002，12:429-439.

［4］Wu CW，Tay Y C.AMRIS:A multicast protocol for Ad Hoc wireless networks proceedings［C］∥IEEE Military Communications(MILCOM)Conference，1999:25-29.

［5］Jabbehdari S，Shamaei M，Darehshoorzadeh A.IQoS-ODMRP:A novel routing protocol considering QoS parameter in MANET［C］∥2010 IEEE Symposium on Industrial Electronics and Applications，2010:126-130.

［6］方艺霖，李方敏，吴 鹏，等.无线 mesh网络组播路由协议［J］.软件学报，2010，21:1308-1325.

［7］葛连升.基于蚁群优化的组播路由算法研究［M］.济南:山东大学，2010:4.

［8］王新红，王光兴.基于遗传算法的时延受限代价最小组播路由选择方法［J］.通信学报，2002，3(3):112-117.

［9］潘 耘，王行刚，冯烟利，等.求解带度约束多播路由问题的启发式遗传算法［J］.通信学报，2007，28(1):134-141.

［10］Wang X W，Cao JN，Cheng H，et al.QoSmulticast routing formulize diagraph communications using intelligential positional methods［J］.Computer Communications，2006，29:2217-2229.