Ad Hoc网络中基于概率预测的拥塞控制算法

彭玉艳，杜文才，任 佳

（海南大学 信息科学技术学院，海南 海口570228）

0 引 言

在无线Ad Hoc网络中，由于资源的限制，数据包经常会在任意的转发节点出现拥塞。拥塞会导致高丢包率、长延时，浪费网络可用资源［1］。TCP 协议中的拥塞控制算法有效地避免了网络拥塞崩溃，但是TCP拥塞控制策略趋于保守，限制了网络的吞吐量［2］，针对这个问题，研究者提出多种改进的拥塞控制协议，其中有TCP NewReno［3］、TCP SACK［4］、TCP Vegas［5－6］等。TCP NewReno 和TCP SACK 协议通过发送节点接收到的ACK 确认包来判断网络状态。但在Ad Hoc网络中，可能由于链路问题发生丢包使网络不能及时接收到应答，因此，这些协议不能准确判断Ad Hoc网络拥塞状态。TCP Vegas协议通过观测往返时延比较实际吞吐量与期望吞吐量的差值，以判断网络状态［5，6］，更适合于无线Ad Hoc网络。近年来，一些学者针对Ad Hoc网络提出了IEDCA［7］、CL－QF［8］、CCOC［9］等跨层拥塞控制方法，但这些算法需要增加更多的专用接口，设计难度较大，扩展性较差。而贝叶斯网络采用有向图来描述概率关系的理论［10］，在解决许多实际问题的过程中，贝叶斯网络可以从不完全的、不精确的或不确定的知识和信息中做出推理和判断，具有很强的鲁棒性和通用性［10，11］。由于无线Ad Hoc网络获得的数据并不十分精确，有学者提出使用贝叶斯网络拥塞识别方法进行拥塞控制［12，13］，并已验证该方法能够判断网络的拥塞。但是，现有的方法并没有考虑到所获得参数具有很多种数值状态，如果直接使用这样的数据构建贝叶斯网络具有很大的难度，而使用简单分类的数据进行推理又不能够利用网络实时数据的微小差别提前预测，避免网络发生拥塞。

因此，本文针对使用TCP Vegas协议的Ad Hoc网络进行分析，提出了基于概率预测的拥塞控制算法 （PPCC）。该算法首先利用模糊方法处理数据，然后，根据处理后的数据构建贝叶斯网络。为了更好地利用网络实时参数的微小差别来预测网络拥塞状态概率，本文改进了贝叶斯网络的推理过程。最后根据预测概率调整网络参数，达到拥塞控制的目的。

1 问题分析

在无线Ad Hoc网络中，当到达某一节点的数据包总量大于它的缓存空间时，节点就会出现拥塞，然后开始丢包［14］。TCP拥塞控制协议通过重传可以避免数据包丢失，但是会增加数据包的延时，造成网络资源浪费和降低网络服务质量。为了提高网络服务质量，需要提前检测网络状态，避免网络由于负载过重产生拥塞。目前，研究者提出很多检测网络拥塞状态的指标，如平均队列长度、数据包延时、剩余缓存空间等［14］。但是，单独使用某一指标不能准确判断网络拥塞状态，同时，考虑到某一刻的参数具有多种误差对网络状态有很大影响。因此，本文使用指定时间段的多个指标构建贝叶斯网络找出它们之间的关系，用于预测出网络拥塞状态。

通过对无线Ad Hoc网络进行分析发现网络的拥塞状态与平均延时、抖动、平均吞吐量和平均队列长度有关，所以可用平均延时和抖动表示当前网络的运行状态，用平均吞吐量表示网络资源的利用情况，用平均队列长度表示网络缓存中的数据量。因此，使用这些参数构建贝叶斯网络。

本文使用的参数定义如下：

平均时延：在定义时间段内，统计目的节点接收到的所有数据包时延的平均值。其中，本文使用的数据包时延定义为源节点发送出一个数据包到目的节点接收到该数据包之间的时间差，记为x1；抖动：在定义时间段内，数据包时延最大值减去平均时延与平均时延减去时延最小值的较大值，记为x2；平均吞吐量：在定义时间段内，目的节点接收到的数据量除以该时间段的时间，记为x3；平均队列长度：在定义时间段内，每一次发送、接收或丢失数据包时，都统计没有被发送节点接收的数据包的数量，最后将所有的数据包数相加除以统计次数，记为x4。

2 概率预测拥塞控制算法

PPCC算法是基于贝叶斯网络的概率预测模型算法。该算法需要利用网络参数构建贝叶斯网络的概率预测模型以用于对网络的实时参数进行推理预测来调整网络参数。该算法过程如图1所示。

图1 PPCC算法过程

其中，PPCC算法由3个部分构成：第1部分通过对已有网络参数进行处理和学习，构建贝叶斯网络；第2部分通过对实时网络参数进行处理，然后使用改进的贝叶斯网络推理方法来预测网络的实时拥塞状态；第3部分根据预测得到的网络拥塞状态，调整实时运行网络的参数，缓解网络拥塞。下面将详细介绍PPCC算法的实现过程。

2.1 贝叶斯网络的构建

贝叶斯网络是由节点和数条有向边组成的带有概率注释的无环图。虽然通过问题分析可以得到构建贝叶斯网络的节点，但是，不能直接使用这些参数来构建贝叶斯网络。因此，需要首先对数据进行处理；对处理后的数据进行学习，才能得到贝叶斯网络。

（1）数据处理

由于网络运行获得的数据有太多种数值状态，使用这样的数据构建贝叶斯网络具有一定的难度，所以，使用三角模糊化隶属函数对数据进行了模糊化处理，公式如下

式中：a，b，c——常数，通常根据实践经验进行指派。

对以上4个参数分别指定模糊区间进行三角模糊化处理，求得其隶属度，记为d（xij）。d（xij）表示参数xj为状态i的隶属度，其中xij表示参数xj为状态i。使用隶属度最大的状态ij为参数xj的状态，这样就获得了贝叶斯网络的输入参数（i1，i2，…，im）（其中，m＝4），将所有已知的参数进行处理后就可以得到输入矩阵Im。

（2）贝叶斯网络结构及参数的学习

通过对已有网络参数进行处理获得构建贝叶斯网络的输入矩阵Im，就可以使用已有成熟贝叶斯网络学习算法来构建贝叶斯网络。贝叶斯网络的构建过程为：使用K2算法获得贝叶斯网络结构；使用最大似然估计算法进行参数学习，获得贝叶斯网络。由于K2算法和最大似然估计算法是贝叶斯网络中大家比较熟悉和常用的算法，具体的过程可见文献 ［13，14］。

2.2 概率预测模型的构建

文献 ［1］提出使用估计队列长度来识别网络的拥塞等级，以为网络的平均队列长度能够表示网络的拥塞程度。但在实时运行的系统中获得网络的平均队列长度具有一定的难度。因此，本文考虑使用贝叶斯网络来推理预测网络的平均队列长度。

（1）数据处理

为了更准确地使用获得的实时参数进行推理，使用式（2）将隶属度d（）进行归一化处理，得到参数xj为状态i的概率p（）；然后，使用所得到的概率值进行推理对参数进行模糊处理后，可以获得已知所有参数分别属于某个状态的概率为

式中：p（xi11，xi22，…，xinn）——对于所有的j∈｛1，2，…，n｝，参数xj——状态ij时的概率。

（2）贝叶斯网络推理的改进

贝叶斯网络推理是在给定贝叶斯网络模型的条件下，根据已知参数，利用条件概率的计算方法，计算出感兴趣节点的概率。如果利用已有的贝叶斯网络推理方法，只能计算出平均队列长度在双亲节点属于某一状态时的概率值，即p（yk｜i1，i2，…，in）。然而，在实时运行的网络系统所获得参数可能属于多个状态，因此，为了更好地利用实时数据，必要对贝叶斯网络推理进行改进。

根据构建的贝叶斯网络和式 （3）可以推导得出使用实时数据进行贝叶斯网络推理式 （4）

式中：y——要预测的节点 （这里为平均队列长度，即x4），x1，x2，…，xn——y 的双亲节点的值。

例如：已知y 的双亲节点x1，x2且均有2 种状态 （1，2），根据式 （4）可以求得y 为状态1的概率计算公式如式（5）。

根据上一部分构建的网络可以得到p（yk｜i1，i2，…，in），同时使用式 （2）获得实时数据属于每个状态的概率p（xij）；然后，使用式 （4）就可以计算得到Ad Hoc网络在实时数据情况下平均队列长度分别属于各种状态的概率值。

2.3 拥塞控制算法的实现

拥塞控制的主要目的就是最好地利用网络中的可用资源，同时，保持网络的负载量低于且尽可能接近网络可以承受容量的限度。本文通过对使用CBR 流量发生器的发送速率进行调整，使得网络负载量满足拥塞控制的目的。根据网络运行获取的实时数据使用上一部分构建的概率预测模型来预测网络中平均队列长度所属状态概率；根据预测结果实时调整网络的发送速率，缓解网络拥塞。调整实时网络参数的拥塞控制算法实现伪代码如图2所示。

图2 基于概率预测模型的拥塞控制算法伪代码

其中：vmax为最大发送速率；vmin为最小发送速率；Δv为调整步长；p30为当前时段平均队列长度为状态3的概率；p3i为前i时段平均队列长度为状态3的概率 （i＝1，2，…，5）；count为调整阶段用来判断网络是否进入稳定状态的指标；vnext为下一时段网络的发送速率；vcurrent为当前时段网络的发送速率；vpast为前一时段网络的发送速率。

参数调整算法分为了调整和稳定2个阶段，这2个阶段是不可逆的。在调整阶段，根据网络平均队列长度为3的概率，依据条件调整网络的发送速率和相关参数，同时保证网络的发送速率在最小发送速率与最大发送速率之间；而调整步长的变化使得网络可以在一定时间获得较优发送速率，进入稳定阶段。在稳定阶段，网络根据6 个时段网络平均队列长度为3的概率，判断是否将要发生拥塞来调整发送速率。为了确保服务质量，调整步长不宜过大，以避免网络发送速率大幅度变化引起网络振荡，降低服务质量。

3 实验仿真

本文使用NS2.35 软件进行实验仿真。网络拓扑结构为3个节点的线性结构。其中，节点1 为发送节点，节点2为转发节点，节点3 为接收节点。同时，网络的发送范围半径为250 m，干扰范围半径为550 m，网络可用带宽为1 Mb。在进行仿真时，路由层使用AODV路由协议，传输层使用TCP Vegas协议。设定获取数据的 时 间 段 为1s，将x1，x2，x3模 糊 化 为2 类，x4模 糊 化为3类。使用模糊化的数据构建贝叶斯网络，得到如图3所示的网络结构。

图3 贝叶斯网络结构

为了验证PPCC 算法，设定最大发送速率vmax为400 KB／s，最小发送速率vmin为200KB／s，调整步长初始值Δv为20KB／s。分别针对网络初始发送速率为200KB／s，337 KB／s和400KB／s进行仿真。其中，337KB／s是经过多次仿真实验获得此网络结构下的较优发送速率。在仿真过程所有时段中，根据概率预测模型计算得到实时运行网络中平均队列长度为状态3的概率，结果如图4所示。

图4 预测网络出现状态3的概率变化情况

图5 发送速率变化情况

根据每个时段预测网络状态3 的概率对网络的发送速率进行调整，得到发送速率变化情况 （如图5所示）。

图5显示发送速率在开始调整时出现阻尼振荡的状况，但是经调整很快就获得了相对较优的发送速率后进入稳定状态。

使用本文提出算法 （PPCC）调整网络发送速率与未用本文算法 （PPCC－N）进行仿真，获得的网络平均延时和平均吞吐量的变化情况如图6、图7所示。

根据图6 发现使用PPCC 算法对发送速率进行调整，使得网络达到稳定状态后，平均延时处于相对较小的值；而未使用PPCC算法的情况下，当网络的负载大于其承受能力范围时，网络的平均延时会处于较大值状态。从图7可以看出，使用PPCC算法可以使网络在达到稳定状态后，平均吞吐量保持相对较大的值；而对于未用PPCC 算法的情况，当网络的负载远小于其承受能力时，会使网络的吞吐量较小，导致网络资源浪费。

图6 平均延时变化情况

图7 平均吞吐量变化情况

综上所述，PPCC 算法能够很好地利用网络实时运行中获取的数据，准确地预测网络拥塞情况；能够在一定时间内将网络调整到稳定状态，使网络达到平均吞吐量较高、平均延时较低的理想状态，能满足对服务质量要求较高的数据流，使网络资源得到更好的利用。

4 结束语

为了更好的利用网络的实时数据，对贝叶斯网络的推理进行改进，利用预测结果使用本文提出的速率调整方法对网络发送速率进行调整，避免网络由于负载过重发生拥塞的情况。仿真实验结果表明：PPCC算法能够根据实时网络拥塞状况自适应的调整网络发送速率，在短时间内使得网络获得较优的发送速率，且保持网络的平均延时较小，平均吞吐量较高，从而使网络获得较高的服务质量。同时，PPCC算法不局限于TCP Vegas中，还可以用于使用CBR数据流的任何传输协议中。然而，该算法需要对数据进行模糊化处理，不同网络结构的模糊处理区间不同对网络发送速率的影响，还需要进一步研究。

［1］Senthikumaran T，Sankaranarayanan V.Dynamic congestion detection and control routing in Ad Hoc networks［J］.Journal of King Saud University－Computer and Information Sciences，2013，25 （1）：25－34.

［2］YI Fasheng，ZHAO Jidong.Fuzzy TCP congestion control algorithm using delay ［J］.Journal of University of Electronic Science and Technology of China，2010，39 （2）：260－265 （in Chinese）.［易发胜，赵继东.利用时延特性的模糊TCP 拥塞控制算法［J］.电子科技大学学报，2010，39 （2）：260－265.］

［3］Nadim Parvez，Anirban Mahanti，Carey Williamson.An analytic throughput model for TCP NewReno ［J］.IEEE／ACM Transactions on Networking，2010，18 （2）：448－461.

［4］Mehta RD，Vithalani CH.Distinguishing congestion loss from random loss on wireless erroneous links to improve performance of wireless TCP－SACK ［C］／／International Conference on Communication Systems and Network Technologies，2012：383－387.

［5］Neda Alipasandi，Shahram Jamali.An improvement over TCP Vegas by solving rerouting problem ［C］／／AWERProcedia Information Technology ＆Computer Science，2011：82－86.

［6］Shubhada P Deshmukh，Sanjesh S Pawale.TCP Vegas rerouting detection and improving performance ［J］.International Journal of Wired and Wireless Communications，2012，1 （1）：11－14.

［7］Mbarushimana C.A cross－layer TCP enhancement in QoS－aware mobile Ad Hoc networks ［J］.Computer Networks，2013，57 （1）：286－301.

［8］Evangelos Papapetrou，Panos Vassiliadis，Efthymia Rova，et al.Cross－layer routing for peer database querying over mobile Ad Hoc networks［J］.Computer Networks，2012，56 （2）：504－520.

［9］XU Weiqiang，WANG Yaming，YU Chenghai，et al.Crosslayer optimal congestion control scheme in mobile Ad Hoc networks［J］.Journal of Software，2010，21 （7）：1667－1678（in Chinese）.［徐伟强，汪亚明，俞成海，等.移动Ad Hoc网络的跨层优化拥塞控制 ［J］.软件学报，2010，21 （7）：1667－1678.］

［10］XIAO Qinkun，GAO Song.Application of Bayesian network in intelligent information processing ［M］.Beijng：National Defence Industry Press，2012 （in Chinese）.［肖秦琨，高嵩.贝叶斯网络在智能信息处理中的应用 ［M］.北京：国防工业出版社，2012.］

［11］Dojer N，Bednarz P，Podsiadlo A，et al.BNFinder2：Faster Bayesian network learning and Bayesian classification ［J］.Bioinformatics，2013，29 （16）：2068－2070.

［12］Ersyhad Sharifahmadian，Shahram Latifi.Cognitive congestion control for data portals with variable link capacity ［J］.Int Jouranl Communications Network and System Sciences，2012，5 （8）：481－489.

［13］Giorgio Quer，Henmanth Meenakshisundaram，Bheemarjuna R Tamma，et al.Using Bayesian networks for congnitive control of multi－hop wireless networks［C］／／Military Communications Conference，2010：201－206.

［14］Senthil Kumaran T，Sankaranarayanan V.Early congestion detection and adaptive routing in MANET ［J］.Egyptian Informatics Journal，2011，12 （3）：165－175.