Ad hoc网络中基于带宽的准入控制研究

胡桃英，程运安，官骏鸣

1.合肥工业大学计算机与信息学院，合肥 230009

2.合肥工大高科信息科技股份有限公司，合肥 230088

3.黄山学院信息工程学院，安徽黄山 245400

Ad hoc网络中基于带宽的准入控制研究

胡桃英1，程运安1，官骏鸣2，3

1.合肥工业大学计算机与信息学院，合肥 230009

2.合肥工大高科信息科技股份有限公司，合肥 230088

3.黄山学院信息工程学院，安徽黄山 245400

在决定无线自组织网服务质量的诸多参数中，可用带宽是至关重要的参数。通过引用泊松分布流量产生器产生数据包的概率和发送数据包的概率，研究由于隐藏节点引起冲突的概率，消除由于节点发生碰撞对可用带宽的消耗。通过分析与推导，建立IIAB算法模型，并将IIAB加载到AODV协议，利用RREQ/RREP对新的业务流进行准许接入和资源预留，在此基础上，提出了新的基于IIAB-AODV协议的准入控制机制。通过NS2网络仿真平台模拟表明：提出的模型提高了估测可用带宽的精度以及基于IIAB-AODV协议的准入控制机制更能够保障和提高网络的服务质量。

无线自组织网；可用带宽估测；准入控制；按需平面距离矢量路由（AODV）协议；服务质量

无线自组织网是由一组带有无线收发装置的移动节点组成的一种无线移动通信网络，它不依赖于固定的基础设施，因此为无线自组织网提供QoS保障是一个具有挑战性的难题，QoS保障最关键的一部分就是准入控制（Admission Control，AC）。AC的主要工作机制是负责对用户的请求进行准许判决，决定是否允许系统为用户提供相应请求服务的无线资源管理（Radio Resource Management，RRM）功能实体[1]。它能够有效缓解网络拥塞，保障和提高网络服务质量。

本文提出一种准确估测多跳无线自组织网络的可用带宽的方法，并基于带宽策略进行准入控制，从而进一步保障和提高网络服务质量。可用带宽是非常重要的网络参数之一，它可以定义为在不降低网络中其他业务流传输速率的情况下，链路所能提供的最大传输速率。传统的有线网络可用带宽测量方法主要有两类：一类是探测包间隔模型（PGM），如Spruce[2]、IGI[3]等；一类是基于探测包速率模型（PGM），如TOPP[4]、Pathchirp[5]等。然而由于无线网络共享信道会导致节点之间竞争资源，同时在信道接入过程中，需要多次握手，用于带宽测量的探测包将与网络中传输业务的数据包相互碰撞，触发重传甚至导致数据包丢失等原因，导致用于估测有线网络的可用带宽方法无法用于无线网络。另外，在研究测量无线网络可用带宽的方法时，需要综合考虑各种因素对可用带宽的消耗，例如：因节点同时发送数据时发生碰撞、隐藏节点的存在引起碰撞、碰撞后回避时间对带宽的消耗以及收发节点忙闲同步等问题。显然，相比于有线网络，无线网络可用带宽的估测方法要复杂很多。目前，关于无线自组织网络中多跳可用带宽测量方法最为经典的是Cheikh Sarr和Claude Chaudet等提出的ABE算法[6]以及Haitao Zhao等提出的IAB算法[7]。本文提出的IIAB（Improved IAB）算法主要是对Haitao Zhao提出的IAB算法进行了改进，并将IIAB算法加载到AODV协议，实现了基于带宽的接入控制技术。

1基本概念

1.1 传输距离和载波侦听距离

这里分别用Rtx和Rcs表示传输距离和载波侦听距离[8-9]。所谓传输距离Rtx是指在不存在其他无线节点干扰的情况下，一对无线节点能够实现可靠通信的最远距离，可以表示如下：

式中d0表示参考距离，P0表示在参考距离内接收到的信号强度，RXThresh为接收信号的阈值，α为路径损耗因子，通常取α≥2。载波侦听距离Rcs表示当一个节点在发送数据时，它能够触发其他节点进行载波侦听监测的最远距离，可以表示如下：

1.2 隐藏节点问题

为了研究方便，这里假设传输距离与载波侦听距离相同。在图1所示的简单网络拓扑结构中，两个实线圆分别表示节点B和节点C的传输距离（载波侦听距离），节点A位于节点B和节点C的传输距离之内，但是节点B和节点C不在彼此的传输距离之内。当节点B向节点A发送数据时，节点C无法侦听到节点B在发送数据，因此节点C认为信道空闲。若此时节点C也向节点A发送数据，那么节点A处就会发生数据碰撞。因此这种由于存在隐藏节点引起的碰撞，称为隐藏节点问题[10]。

图1 隐藏节点网路拓扑图

1.3 收发同步问题

对于A、B两个节点连接的链路而言，由于存在双方载波侦听范围不一致的现象，可能导致双方节点的忙闲时间段不一致。如图2（a）所示，此时节点A和节点B信道的忙闲时隙一致，假设链路容量为C且忙闲持续时间相等，则A、B双方从自己对信道的侦听情况就可以估算链路的剩余带宽，可以简单地视为C/2；另一种极端情况，如图2（b）所示，A、B侦听信道的忙闲时隙完全互补，即当节点A侦听到信道空闲的时候，节点B侦听到信道为繁忙状态，反之亦然。由于A、B双方对信道状态的判断完全相反，所以即使B节点空闲的时候可以接受数据，而此时节点却因为信道忙无法发送数据，显然它们之间的剩余带宽为0。上述情况即为收发同步问题。

图2 （a）收发双方对信道感受同步

图2 （b）收发双方对信道感受异步

2 改进IAB算法（Improved IAB，IIAB）

2.1 IIAB算法相关背景

当前，常用的带宽测量方法通常是考察在一段监测时间T内，节点探测的空闲时间Tidle，将两者的比值作为节点的空闲率，因此可以得出节点观测得到的系统可用带宽值为：

其中C为链路容量，AB为可用带宽值。但是，在无线网络情况下评测链路可用带宽不可忽视以下两个问题：（1）节点发生碰撞以及碰撞后退避时间对带宽的消耗；（2）由收发双方节点不同步导致忙闲时间不一致现象所带来的估测可用带宽的偏差。

其中，Haitao Zhao在文献[7]中提出的IAB算法主要是针对问题（2）而对ABE算法进行了改进。IAB算法中，作者对节点评测信道忙作了更为细致的划分，定义节点发送或接收数据时为BUSY状态，定义节点侦听信道是否空闲时为SENSE BUSY状态，其他情况为IDLE状态。通过严格区分这三种状态来判断收发节点是否同步。结果发现，若收发节点不在彼此的传输范围内，则收发双方发生不同步，即一方处于IDLE状态，而另一方处于SENSE BUSY状态。在计算可用带宽时，IAB算法消除了该情况下对带宽的消耗。但是，针对问题（1），IAB算法没有做出相应改进，这显然会降低估计可用带宽的精度。当前对冲突概率的估计主要采用实时监测和数学模型相结合的方式[11]，但是很多都是仅仅通过路由层的hello消息包丢失的情况来表示节点数据包发送的冲突概率。这样，显然考虑得不够全面，这是因为：（1）引进hello消息会增加网络负担；（2）冲突概率与包尺寸有关，一般来说，包尺寸越大其冲突概率也随之增大。因此，据此推断出来的冲突概率显然有失偏颇。本文引进了一种新的计算节点发送数据时产生碰撞概率的方法，以便达到改进IAB算法的目的。

2.2 IIAB的模型分析与推导过程

2.2.1 碰撞概率计算方法

以节点A为研究对象，导致其发送至B处的冲突原因可能是：（1）在其传播范围之内的节点，于同一时刻发送数据；（2）隐藏节点在特定时间段发送数据。然而，在低负荷的网络情况下，二进制退避机制可以有效地缓解因情况（1）而产生的冲突，吞吐量也不会明显下降。但是，隐藏节点导致的冲突在非饱和情况下可能会严重影响网络性能。为了更好地研究由于隐藏节点所产生的冲突概率，本模型采用的是非饱和状态下的网络，即节点不是始终保持数据发送状态。

本文对模型作了几个前提假设：（1）节点数据包产生服从参数为λ的泊松分布，并且以μ的概率发送它们；（2）网络中的节点按照均匀分布固定在节点C的载波侦听范围内；（3）节点的载波侦听范围和传输范围相同。如图3所示，节点A和B是两个隐藏节点，两个实线圆圈分别是A和B的载波侦听范围或传输范围，虚线圆圈表示节点C的载波侦听范围，HA为节点A的隐藏节点区域，即处于节点A侦听范围之外但却在节点C的侦听范围之内的所有节点的集合。

图3 网络拓扑示意图

在推导过程之前，假设节点C的载波侦听范围内所有的节点以λi的概率产生数据帧，以μi的概率传输数据帧，其中λi和μi满足以下关系式：

节点A向节点C发送数据时由于隐藏节点产生冲突可以分为两种情况：（1）A传输数据时，HA已经处于忙状态，即A的隐藏区域内有节点在传输数据；（2）A传输数据之后，HA由闲状态转为忙状态，即A的隐藏区域内的节点侦听到信道空闲开始发送数据。分别用Pb|txA和Pib，A表示这两种情况发生的概率。当第一种情况发生时，节点A向节点C传输数据时肯定会发生冲突；否则，节点A不可能与A的隐藏区域内节点在同一时间段内向节点C发送数据而产生冲突，只有在节点A向节点C发送数据时，节点A的隐藏区域的节点开始向节点C发送数据，即在发生第二种情况时节点A向节点C发送数据会产生冲突。

因此，节点A传输数据发生冲突的概率可以表示为：

根据前面对Pb|txA的定义，显然它可以用下面表达式表示：

由于本文假设节点的分布是按照均匀分布的，所以式（7）计算出来的节点A的冲突概率也可以表示为节点B的冲突概率，即Pc，B=Pc，A。

2.2.2 IIAB算法可用带宽理论方法

在计算给定收发节点的一条链路中的可用带宽值时，需要综合考虑节点发生碰撞、退避时间以及收发同步问题对可用带宽的消耗，在此引进两个修正系数K和α。

其中m与上述n的值相同，也表示为竞争窗口到达最大值的次数，即Wmax=2mW，Wmax为竞争窗口的最大值，W为竞争窗口的初始值。

系数α是用来消除收发同步问题对可用带宽的消耗，在IAB算法中，它是通过严格区分收发节点的BUSY状态和SENSE BUSY状态获得的，为了简单起见，本文直接引用其方法，即在观测时间内记录收发节点处于SENSE BUSY状态的时长，并将该时长与观测时间T的比值作为信道处于侦听状态的比率，再用该比值乘以收发双方发生不同步的概率，那么同步系数可以表示为：

综上所述，计算可用带宽的公式可以进一步修正为：

3 基于IIAB的准入控制分析

基于IIAB策略的接入控制是对按需平面距离矢量路由协议（Ad hoc On-demand Distance Vector Routing，AODV）的扩展。通过比较新的业务流所需带宽与网络中的剩余带宽来判断是否接入该业务流，并且在接入新的业务流后，是否会对网络中原有的业务流产生较小的干扰[12]。

3.1 内部业务流干扰

利用第3章计算出来的可用带宽值只是网络中每个节点的可用带宽值，但是，由于无线网络共享信道的特点，当一个流经过多跳时，会在各个节点受到内部业务流的干扰，所以仅仅通过比较节点的可用带宽来判断是否接入该业务流是不够的。关于该问题，文献[13]是将计算出来的可用带宽值除以竞争数（多跳链路上某个节点载波侦听范围内的节点个数）。

为了简单起见，本文采用的方法是文献[14]的方法，即利用端到端的吞吐量与路径跳数的关系，将计算出来的可用带宽值除以min（H，4），用H表示从源节点到收到RREQ的节点i的节点个数，公式表示如下：

这样，在接入控制时，只需要检查下式是否成立即可。

其中RB表示请求接入的业务流需求带宽。

3.2 准入控制分析

接入控制以IIAB和AODV协议为基础，可以分为路由请求阶段和资源预留阶段。

当有新的业务流接入时，源节点就会产生和广播RREQ，同时开启定时器，若源节点在一定时间内收到RREP应答包，则准许该业务流的接入，否则，拒绝该业务流的接入。本文重新定义RREQ消息格式，包括业务流的源节点IP地址、目的节点IP地址、数据包大小、发送速率、业务流需求带宽信息（Request Bandwidth，RB），如图4所示。当中间节点收到RREQ时，通过判断式（9）是否成立，若成立则继续转发RREQ，若不成立，则丢弃该请求包。当目的节点收到第一个RREQ时，目的节点产生RREP应答包，并且单播回送该应答包。在回送应答包RREQ的途中，路径上每个节点根据RB的值为该业务流进行带宽预留。一旦源节点在没有超时的情况下收到RREP应答包，该业务流便可以发送数据，否则拒绝该业务流。

图4 RREQ消息数据格式

4 仿真实现与结果分析

本文采用的仿真平台是网络仿真器NS2[15]，在NS2上比较了IIAB算法与IAB算法的性能以及实现了基于AODV协议和基于IIAB-AODV协议准入控制的性能比较与分析。

4.1 IIAB算法与IAB算法性能分析与比较

仿真场景如图3所示：将节点c的坐标设置为（0，0），然后选择节点c周围的8个节点作为背景节点源-目节点对，共组成4对业务流传输数据，将节点c为研究对象，首先统计其真实可用带宽，然后分别统计采用IIAB算法和IAB算法得到的可用带宽值。流量产生器设置为Application/Traffic/Pareto，数据包大小为512 Byte。每个节点的载波侦听半径为550 m，物理带宽为2 Mb/s，仿真时间为50 s。4对背景业务流流量如表1所示。

图5显示了采用IAB算法和IIAB算法与真实带宽的比较。显然，采用IAB算法高估了节点c可用带宽，而利用IIAB算法估测的可用带宽与真实可用带宽值接近，进而提高了可用带宽的精度。

图5 节点c的可用带宽

表1 背景业务流流量

4.2 基于AODV协议和基于IIAB-AODV协议准入控制性能比较与分析

首先在较简单的环境下进行验证。仿真参数设置如下：12个移动节点按照图3分布在700 m×500 m的范围内，它们的坐标为（0，0）、（250，125）、（250，375）、（500，0）、（0，250）、（0，500）、（500，250）、（750，125），其他14个节点按照图3的网络拓扑示意图均匀地分布在其他三个象限。随机选择两个节点作为源-目的节点对，共组成6对业务流传输数据，其他参数的设置与上述相同。6个业务流的详细信息如表2所示。

表2 流量设置

图6和图7分别给出了基于AODV协议和IIABAODV协议各个业务流的吞吐量。结果表明，由于普通的AODV协议没有考虑带宽接入策略，盲目接入所有的业务流，会导致新的业务流接入网络时对原有的业务流产生较大的干扰。例如，业务流1在5 s的时候开始接入，而在25 s之前吞吐量还是相对比较稳定，业务流2、3、4接入对其没有产生影响。但是，在25 s的时候，由于业务流5开始接入，业务流1的吞吐量开始大幅下降并且波动幅度较大。同样，业务流2、3、4的吞吐量也在25 s之后变得很不稳定。当把IIAB加载到AODV协议的时候，出现了图7的结果，即只有业务流1、2、3、4、6可以接入网络，业务流5由于不满足接入条件而被拒绝接入，此时网络中各个业务流吞吐量得到了很好的保证。

图6 基于AODV协议各流的吞吐量

图7 基于IIAB-AODV协议各流的吞吐量

接下来本文在相对一般的场景下进行了验证。场景设置如下：50个节点均匀的分布在1 300 m×1 100 m范围内，随机选择10对节点进行业务流的传输，每个业务流的流量产生器设置为Application/Traffic/Pareto。且10个业务流每隔10 s传输数据，仿真时间为120 s，数据包大小为1 024 Byte。其他参数与简单环境下的参数相同。图8和图9显示了采用基于AODV协议的准入控制和采用IIAB-AODV协议的准入控制的网络吞吐量和延迟时间的对比。从结果可以看出，采用基于IIAB-AODV协议的准入控制，网络的吞吐量和延迟都好于普通的AODV协议准入控制，从而有利地证明了基于带宽策略的准入控制可以有效地保障和提高网络服务质量。

图8 网络吞吐量变化图

图9 网络延迟时间变化图

5 结论

在充分研究IAB算法的基础上，通过利用泊松分布流量产生器的产生数据包的概率和发送数据包的概率，计算隐藏终端引起的冲突概率，进而消除因收发同步问题对带宽的消耗，提出了新的估测可用带宽的方法IIAB，并将该方法应用到AODV协议，设计出新的准入控制机制。仿真表明：新的准入控制机制提高了网络的稳定性以及吞吐量，降低了延迟时间，可以有效地保障和提高网络服务质量。下一步工作是研究将IIAB算法应用到其他协议如DSR协议来提高网络的性能。

[1]梁如冰，夏强.无线接入控制关键技术研究进展综述[J].计算机测量与控制，2011，19（2）：246-249.

[2]Strauss J，Katabi D，Kaashoek F.A measurement study of available bandwidth estimation tools[C]//Proc ACM Internet Measurement Conference（IMC），2003：39-44.

[3]Hu Ningning，Steenkiste P.Evaluation and characterization of available bandwidth probing techniques[J].IEEE Journal on Selected Areas in Communications，2003，21（6）：879-894.

[4]Melander B，Bjorkman M，Gunningberg P.A new end to end probing and analysis method for estimating bandwidth bottlenecks[C]//Proc Global Internet Symposium，2000：415-420.

[5]Ribeiro V，Riedi R，Baraniuk R，et al.PathChirp：efficient availablebandwidthestimationfornetworkpaths[C]// Workshop on Passive and Active Measurement（PAM），2003.

[6]SarrC，ChaudetC.BandwidthestimationforIEEE 802.11-based ad hoc networks[J].IEEE Transactions on Mobile Computing，2008，7（10）：1228-1241.

[7]Zhao Haitao，Garcia-Palaciso E，Wei Jibo.Accurate available bandwidth estimation in IEEE802.11-based ad hoc networks[J].Computer Communications，2009，32：1050-1057.

[8]Zhai H，Wang J，Fang Y.A new dual-channel MAC protocolformultihopadhocnetworks[J].IEEETransactions on Wireless Communication，2006，5（11）：3224-3233.

[9]Li J，Blake C，Couto D S J D.Capacity of ad hoc wireless[C]//Proc ACM MobiCom，2001.

[10]宿景芳，武穆清，徐春秀.无线多跳Ad Hoc网络最佳吞吐量分析[J].北京邮电大学学报，2011，34（3）：127-131.

[11]Jacquet P，Naimi A M，Rodolakis G.Asymptotic delay analysis for cross-layer delay-based routing in ad hoc networks[J].Advances in Multimedia，2007，4：1-11.

[12]刘春芳，张连芳.无线自组网络QoS流的准入控制和流量控制[J].计算机工程与应用，2008，44（25）：88-91.

[13]Sanzgiri K，Chakeres I D，Belding-Royer E M.Determining intra-flow contention along multihop paths in wirelessnetworks[C]//1stInternationalConferenceon Broadband Networks，2004：611-620.

[14]Chen L，Heinzelman W.QoS-aware routing based on bandwidth estimation for mobile ad hoc networks[J]. IEEE Journal on Selected Areas in Communications，2005，23（3）.

[15]Yang Y，Kravets R.Throughput guarantees for multi-priority traffic in ad hoc networks[J].Ad Hoc Networks，2007，5（2）：228-253.

HU Taoying1,CHENG Yun’an1,GUAN Junming2，3

1.School of Computer&Information,Hefei University of Technology,Hefei 230009,China
2.GOCOM Information&Technology Co.,Ltd,Hefei 230088,China
3.School of Information Engineering,Huangshan University,Huangshan,Anhui 245400,China

Available bandwidth is an important parameter of wireless ad hoc networks for guaranteeing QoS.Many approaches for estimating the available bandwidth of wireless networks are presented by many scholars,but no mechanism has been standardized because of many factors affecting the available bandwidth of wireless networks.The proposed approach called IIAB eliminates the consumption for available bandwidth through calculating the probability of conflict caused by hidden nodes.It establishes the IIAB model and uses the result to analyze the admission control and proposes a new IIAB-AODV protocol eventually.Through the simulation results,it is demonstrated that the model proposed in this paper can improve the accuracy of the estimation of the available bandwidth and the IIAB-AODV protocol can guarantee and improve the quality of the service of the network effectively.

wireless ad hoc networks;available bandwidth estimation;admission control;Ad hoc On-demand Distance Vector routing（AODV）protocol;quality of service

A

TP393.0

10.3778/j.issn.1002-8331.1211-0168

HU Taoying,CHENG Yun’an,GUAN Junming.Admission control based on bandwidth policy for ad hoc networks. Computer Engineering and Applications,2014,50（21）：85-90.

安徽省博士后基金（财教[2012]593号）；安徽省科技攻关计划（科计[2010]200号/11010201011）；安徽省高校优秀青年人才基金项目（No.2009SQRZ167）；安徽省高校省级自然科学研究项目（No.KJ2009B114）。

胡桃英（1987—），女，硕士研究生，主研方向为无线网络准入控制；程运安（1968—），男，研究员，主研方向为计算机应用；官骏鸣（1979—），男，副教授，主研方向为无线自组织网MAC、网络层协议研究。E-mail：695542201@qq.com

2012-11-14

2013-01-14

1002-8331（2014）21-0085-06

CNKI出版日期：2013-01-29,http://www.cnki.net/kcms/detail/11.2127.TP.20130129.1539.012.html