一种基于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为业务流速率。且flCl，否则Til(fl)趋近于无穷，从(1)式可知它包含无穷大值(到无穷大的过程是连续的)。
对于一个Nash均衡点．每个业务流分配都是对其他所有联合流分布的一个最佳反应，则：

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

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

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