一种基于QoS的无线Mesh网络DSR路由优化算法

1 引言
    无线Mesh网络(WireleSS Mesh Network，简称WMN)是一种新型的宽带无线网络结构，即一种高容量、高速率的分布式无线网络，其网络拓扑与移动Ad hoc网络相似，但WMN的网络节点移动性较弱，一般不使用电池作为动力，拓扑变化较小。在单跳接入时，WMN看成是一种特殊的无线局域网(Wireless Lical Area Networks，简称WLAN)。目前无线Mesh网络已作为解决“最后一公里”的网络接入问题的解决方案写入IEEE标准。
    无线Mesh接入网络中，非常重要的问题就是路由选择其协议借鉴Ad hoc网络的路由协议，分为3种：第一种为先验式路由协议，也称为表驱动式路由协议(如DSDV、GSR、ZHLS等)；第二种为反应式路由协议，也称为源驱动按需路由协议(如AODV、DSR、TCRA等)；第三种是前二者的混合．称为混合式路由协议(如ZRP等)。
    源驱动按需路由协议中的动态源路由协议(DvnmicSarle Routing,称称DSR)是一种按需路由协议，它允许节点动态发现到目的节点的多跳路由。DSR协议具有支持单向链路，发现多条路由等优点，但对路由需求反应慢，这样可能造成时延、网络拥塞等故障，从而严重影响服务质量(Ouality ofService，简称QoS)。在优化DSR协议的基础上，对于多条可选择的非相关路由应用博弈论于各节点间的功率增益、源节点的发射功率、接收端(目的节点或目的网关)的噪声频谱密度等，提出一种可有效提高数据效率，减少时延和网络拥塞的新路由算法。

2 基于博弈论的DSR路由优化算法
    以DSR协议为基础，引入博弈论的思想，综合多种影响网络传输的因素实现DSR路由优化算法。
2．1 无线Mesh网络中的博弈论思想
    博弈论应用于无线Mesh网络，包括以下几个方面。
    (1)参与者 定义无线Mesh网络中的源节点l是参与者，l为一个有限集合，l={l，2，3…k}。
    (2)策略集合本算法假定在无线Mesh网络中，每个源节点都要选择一定路由才能到达目的节点(或目的网关)，并且所选的路由策略尽可能保证源节点的最大吞吐量，尽可能减少时延和网络拥塞等问题，以及提高QoS，所以在无线Mesh网络中源节点到达目的节点(或目的网关1的所有可能单跳或多跳路由策略就是Mesh博弈论的策略集合。
    (3)赢得集合无线Mesh网络中，算法设定任意一对节点间的功率增益、每个源节点的发射功率、接收端(目的节点或目的网关)的噪声频谱密度等网络必备因素。在此前提下，源节点根据一定的路由策略得到的符合完成吞吐量以及解决拥塞问题的路由，即博弈论中的Nash均衡点。
2．2 非相关路由的选择标准
    非相关路由数目的增加有利于源节点寻找到大吞吐量、小时延的路由。从而实现网络传输，随之选择非相关路由成为问题的关键。这里引用博弈论思想，由于备选的路由本身存在竞争关系，因此是一个动态博弈的过程。
    在两节点的并行链路拓扑情况下，均衡的存在性和唯一性可通过一定的弱凸条件得到。量化用户i的延时函数为：

   
式中，jil(fl)为节点i在链路l上的延时。
    对于每个用户来说，其延时为经过链路上的延时之和，每个链路占用率只与该链路上的业务流相关。假设链路的均衡条件：

   
    (2)Til连续可微，严格递增且是凸函数。为每单位流量。
    该假设保都是凸函数，链路占用函数为：

   
式中：Cl为链路带宽,fl为业务流速率。且fl<Cl，否则Til(fl)趋近于无穷，从(1)式可知它包含无穷大值(到无穷大的过程是连续的)。
    对于一个Nash均衡点．每个业务流分配都是对其他所有联合流分布的一个最佳反应，则：

   
    上述两个假设保证Til(fl)是严格凸于fil的。只要保证这个模型是凸博弈，则它的均衡就存在。作为每条链路的最佳响应，最优化的问题经上述假设成为一个存在均衡解凸问题。尽管如此，最佳响应的唯一性并不能保证均衡点的唯一性。当链路占用函数为无穷大时．即当发送的数据大小无法在一条链路上传输时，就无法通过上述两个约束条件来寻找Nash均衡点，即寻找最合适的路由进行传输，这样就引入均衡条件(3)：对于任何一个导致无限分配的流分配方案，至少可以找到一种将要传输通过更改流分配使其从无限代价转化成有限代价，引入一个效用函数的方法来解决，该效用函数通常默认是凸增的，也即当业务流速率可能大于链路带宽即有弹性需求时，其解决办法就是增加链路分流超出固定需求的部分，而其代价就是使用该部分业务流。
    对于无线Mesh网络来说，判断是否存在均衡点的方法就是利用齐次严凸(Diagonal Strict Convexity，简称DSC)，DSC是一种用来求解唯一均衡的常用工具。

    在这里，定义为流分配延时的加权和，并且

   
    如果DSC系统存在矢量ρ，那么均衡就是唯一的，也就是说该g(f ρ)Pseudo-Jacobian矩阵是正定的，则均衡是唯一存在的。
    由上述可知，当业务流速率小于链路带宽时，则依据均衡条件(1)和(2)，在延时和吞吐量等因素间的博弈中找到最佳路由。而当业务流速率可能大于链路带宽，即有弹性需求时，则依据均衡条件(3)，将流分配延时加入博弈的因素中，在这几种因素中进行博弈，得到最佳路由。
    依照以上对于基于博弈论的DSR路由优化算法的阐述，发现该算法在增加了源节点到目的节点的非相关路由之后，考虑业务流速率小于或大于链路带宽这两种情况，在众多备选的路由中，综合延时、网络吞吐量等因素，在这些因素的相互博弈中寻找到最佳的传输路由，理论上可以达到预定的优化效果。

3 协议仿真与性能评价
3．1 仿真环境设定
    仿真时选择Linux下的ns一2的2．3l版本，MAC层采用802．11协议，仿真环境是1 000 m×1 000 m，随机分布50个节点。节点0每隔0．05 s发送一个数据分组，目的节点是节点19，其他节点不发送数据。节点每次传输数据时，从自身的路由表中选取一条路由行传输。首先为节点1设定选取方向，沿着该方向以一定速度移动。当移动到边界时，再随机选取另一个方向，以相同的速度移动。节点在低于10 m／s的速度下仿真和模拟，以节点移动30 m为限与原始DSR协议相对比。
3．2 仿真结果分析
    为了准确有效地比较这两种算法的优劣，选定数据效率、总请求数目、总开销(按字节)、总开销分组数、端到端时延作为评估标准。综合多次的仿真实验数据后，得出仿真结果如图l所示。从图1(a)看出，优化的与原始的算法在数据效率上都比较好，但是随着节点移动距离的增加，优化后的算法更能体现数据效率上的优势，基本上都达到了95％以上的数据效率，具有很高的吞吐量。图1(b)所示优化后算法的请求数目明显小于原始DSR算法，这表明当使用的路由中断时，它有备用路由可用，不需要重新发起路由发现过程，体现其稳健性。由图1(c)可以看出优化的算法中以控制分组数的开销比原始DSR协议要小，虽然在路由发现过程中会回复更多的路由应答，但是在节点移动的过程中，由于备用路由的减少反而具有更小的开销分组数，并随着节点移动距离的增加会变得更加明显。由图1(d)明显看到优化的算法比原始DSR算法时延要小。随着节点移动距离的增加变得越来越明显。这是因为首先少了路由发现过程，其次每一次发送分组时，节点会随机选取一条路由，所以每条路由的负载不会很大，这就减少了排队拥塞问题，再次，即便当业务流速率大于链路带宽即有弹性需求时，则将流分配延时加入博弈的因素，在这几种因素中进行博弈，进而得到最佳路由进行传输，经过仿真实验证明可以有效的减少拥塞进而缩短时延。

4 结语
    仿真结果表明本算法在复杂网络环境之下可以有效提高网络吞吐量，增强健壮性，提高网络传输效率，有效减少端到端时延，更为重要的是这种改善的趋势随着节点运动距离的加长而变得更加明显，且不受复杂网络环境的影响。