一种基于QoS的无线Mesh网络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路由优化算法的阐述，发现该算法在增加了源节点到目的节点的非相关路由之后，考虑业务流速率小于或大于链路带宽这两种情况，在众多备选的路由中，综合延时、网络吞吐量等因素，在这些因素的相互博弈中寻找到最佳的传输路由，理论上可以达到预定的优化效果。

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协议相对比。