基于M/M/1模型的流量分配算法*

付金锋 戴小文

西南交通大学电气工程学院 四川 成都 610097

引言

由于Ad Hoc的易组织和消耗资源低等特性，目前Ad Hoc网络主要应用在临时网络，譬如抢险、救灾、军事等[1-3]。但这些临时组建的网络往往资源有限，网络通信质量偏低，无法满足实际工作的需要。对于网络服务质量要求较高，尤其是时延性能要求较高的场景，传统通信协议无法满足要求。

针对以上这种情况，本文从多路径路由协议出发，将多路径路由过程抽象成M/M/1服务排队模型，利用拉格朗日方程求得排队时延最低的流量分配算法，并利用该算法改进按需矢量多路径路由协议，仿真表明，相比原协议，新协议的时延性能更好。

1 多路径多跳路由时延模型

Ad Hoc网络的通信时延包括传输时延，处理时延以及排队时延，针对单个数据包而言，传输时延以及处理时延相对固定，而排队时延受网络中的拥塞情况影响较大[4]，是本章的主要研究对象。

1.1 多路径路由时延模型相关研究

多路径路由是相比单路径路由而言的，利用多路径传输技术MPT，并行的传输数据分组，可以为源节点和目的节点之间提供多条不相交路径，具有很好的数据分流效果[5]。多路径路由可以有效减少网络拥塞和丢包率，降低端到端延迟，提高网络的稳定性[6-7]，越来越受到大家的重视。

依据网络流量的测量数据以及中心极限定理[8]，得出了多路经路由中间队列中大量独立延迟组成的路径端到端延迟近似正态分布，并且推理出路径j对应的端到端时延期望。

针对多路径路由提出了流量分配模型[9-10]，但这两篇论文都是假设源节点和目的节点之间的流量平均分配，并没有考虑最优分配问题。

1.2 基于M/M/1服务模型的流量分配算法

本文对多路径无线网络建模参考了多节点M/M/1串联网络，网络模型如图1所示，其中源节点到目的节点有N条路径。整个无线网络可以看成一个有向图，所有参与多路径路由的原始节点都是原始图的一个子图。

图1 无线网络多条多路径模型

如图1所示，假定源节点S与目的节点D之间存在N条子路径，每个子路径都是M/M/1串联网络，用Pi表示，Pi中有L个中继节点。S到D上存在一个平均到达率为λ的流量，符合泊松分布，平行分布于各条子路径上的流量为λj，也符合泊松分布，则有：

图中的μi,j是队列在路径上的平均处理速率，bi,j是队列本身沿路径发出的流量和路径间流量之和。假设各条子路径间的流量也是相对独立的，即λi,j=λj（i=1...L），由M/M/1排队服务模型可得：

ρ是服务模型中的排队强度，即服务器的利用率，Ws,j是流量在队列中的全部停留时间，Wq,j是流量在队列中的等待时间，将公式（2）、（3）带入（4）可得：

式（5）得到的是子路径λ上的总时延，当优化目标为系统时延时，目标函数如式（6）所示：

此时考虑到式1对λ的约束，可以构建拉格朗日乘数法进一步确定具有最小时延的流量最优分配方案：

式（7）中的γ是拉格朗日乘数。要确定时延最低的流量分配方案即转换成求式7的最优解。公式（7）对λj求偏导可得：

从式（8）中可以看出，最优解与j的取值无关，继续转换可得：

假定流量模型中各子路径流量相对独立，各个子路径处理速率相同，路径间流量相同，即μi,j=μj(j=1,2,...,N)，bij=bj(j=1,2,...,N)，则由式（9）可知，流量分配最优解只与路径长度和处理速率有关。假定子路径j上传输时延为dj，根据M/M/1服务模型得出dj=1/(μij-(λj+bj))，代入式（9）得：

由式（10）可知，在不考虑路径长度差异的情况下，要将最优流量分配给第i条路径λi，应满足（λi+bi）di/μi不变。

2 基于流量分配算法的协议改进

根据M/M/1串联网络模型得到流量分配最优解后，发送端节点需要根据算法结果将业务流量分配到各个子路径上。由上述分析可知，流量分配与队列在路径上的平均处理速率μj，队列本身沿路径发出的流量和路径间流量之和bj，子路径上传输时延dj有关。其中，μj和bj都是定值，所以最优流量分配即根据各个子路径的传输时延进行流量分配。

2.1 路径传输时延测量

目前测量路径上的端到端时延最通用的方法是利用ICMP报文记录数据包沿路径从源节点发出到返回所花费的时间。假设源节点收到ICMP探测包与发送ICMP探测包的时间差值为RTT，则该路径上的传输时延即为RTT/2。由于单次测量数据具有不确定性，通常会对RTT进行整形处理，整形公式如下：

式（11）中的α是整形参数。根据冯美玉等学者指出当整形参数α为0.2时，整形效果较好，波动幅度较小。

2.2 流量分配策略

由式（11）可以得到各个子路径的传输时延RTTpt，又由上述的流量分配算法得可以出当流量分配与队列在路径上的平均处理速率μj，队列本身沿路径发出的流量和路径间流量之和bj，子路径上传输时延dj满足(λi+bi)di/μi(di=RTTpt)不变时，时延最小。假定路径j上的流量分配权值归一化值为Wj，则有：

由式（12）和式（10）得出当时延最小时，路径j的流量分配权值如下：

假定Gj为流量开始分配时子路径j上已分配的流量，则各个子路径上已分配的权重Wh为：

为控制数据包发送速率，应优先将流量分配给已分配权值Wh值较小的路径。

2.3 算法流程

求得流量最优分配方案后，源节点需将业务流量按照计算所得的最优分配权值分配给各条子路径。假定业务流量的最小分配单元是数据包，流量分配算法描述如下：

Step1：利用AOMDV协议，获取多条源节点到目的节点的不相交路径；

Step2：利用ICMP探测包获取各条子路径上的传输时延RTT并通过式（11）对RTT进行整形处理；

Step3：根据Step2整形处理后得到的RTT和式（14）计算子路径已分配权值，优先将流量分配给Wh值较小的路径；

Step4：重复上述步骤直至流量分配完毕。

按照上述算法分配流量不仅能降低排队时延，还能控制数据包的发送速率，减小突发流量的影响。

3 仿真结果与分析

为了验证新算法的时延性能，本文利用NS3仿真软件进行仿真，将新算法与传统算法进行比较，部分仿真参数见表1。

表1 部分仿真参数列表

按照表1所示参数搭建好仿真模型后，利用AOMDV协议获取源节点到目的节点的3条不相交路径，有效带宽均为2Mbps,背景流量为CBR业务，数据传输速率分别为40/60/80 bits/s，数据包最大长度为256 Bytes，数据包产生速率为100packages/s，源节点与目的节点随机，测量时间间隔T为5s。假设仿真开始时，3条路径上的流量分配采用平均分配的策略。新算法与传统算法在3条路径上的流量分配如图2、图3所示。

从图2和图3可以看出，新算法给3条路径分配的流量比较平稳，而传统算法的流量基本都集中在其中1条路径上，这是因为新算法在分配流量时会优先将流量分配给流量不饱和的路径，不会出现某条路径流量过大的情况。合理的分流可以有效地防止网络中出现拥塞，从而降低时延。

图2 新算法归一化流量分配

图3 传统算法归一化流量分配

新算法和旧算法的平均分组传输时延如图4所示。

图4 两种算法的平均分组传输时延

从图4可以看出，总体上新算法的平均分组时延要低于传统算法，这是因为新算法分配流量时是按照系统排队时延最低的方案进行分配的，同时对网络中的流量进行了分流，防止某条路径出现流量过多，阻塞网络的情况。综上，新算法的时延性能明显优于传统算法。

4 结束语

本文基于传统多路径路由协议，利用排队服务模型M/M/1搭建多路径多跳网络时延模型，通过拉格朗日方程求出排队时延最优解，并利用结果提出了基于流量分配的新算法，仿真结果表明，该算法相比传统算法，时延性能有较大提高，同时中和了网络的流量分配，防止网络中出现拥塞，对于时延性能要求较高的场景有一定参考意义。