面向智慧道路无线网络的双路径路由准入控制协议

吴彦琼，陈世平

（上海理工大学光电信息与计算机工程学院，上海200093）

面向智慧道路无线网络的双路径路由准入控制协议

吴彦琼，陈世平

（上海理工大学光电信息与计算机工程学院，上海200093）

为满足智慧道路系统中不同优先级数据包的吞吐量需求，提出一个基于优先级的双路径路由准入控制协议。分析节点基于优先级的可用带宽，将满足数据流带宽请求的路径通过数据包传输到终节点，在收到所有候选路径后，选出2条满足数据流带宽请求的最优路径。当终节点进行路由返回时，通过对本地节点及其周围节点的可用带宽预测进行准入控制，保证优先级高的数据流能够优先准入。仿真实验结果表明，与基于单路径的准入控制协议相比，该协议具有更高的吞吐量、更低的延迟和抖动，并且保障了高优先级数据流的带宽需求。

智慧道路；无线网络；优先级；双路径路由；准入控制

1 概述

智慧道路（iRoad）系统利用现有的符合标准的组件定制无线设备（称为智慧节点，iNode），并将它们沿街安装在交通信号灯处，由此建立iNode间的无线链路完成通信。由于需要传输的数据重要性各不相同，如：控制邻近交通灯的iNode之间的通信应拥有最高优先级，实时交通图、最佳路径查询及交叉路口监控类的优先级相对较低。所以，如何按照优先级保证带宽分配是本文研究的重点。

准入控制协议分为2种：一种与路由相关；另一种与路由无关。路由无关的准入控制协议有：SWAN（Stateless Wireless Ad Hoc Networks）［1］，MPARC（Multi-Priority Admission and Rate Control）［2］，基于自适应带宽分配的呼叫准入控制协议［3］和AODV改进算法［4］。因为文献［5］研究表明路由相关的准入控制协议优于路由无关的准入控制协议，所以路由相关的准入控制协议（Contention-aware Admission Control Protocol，CACP）［6］、基于Ad Hoc网络的多路径准入控制协议［7］、流量感知准入控制协议［8］被相继提出，但它们都是基于单路径的路由。平行多路径路由是将数据流分配到多条节点不重合的路径上，相比单路径路由，能提供更加稳定的服务质量（Quality of Service，QoS）以及更好的实现负载均衡。另外，AODVM（Ad Hoc Distance Vector Routing Multipath Protocol）［9］，MSR（Multipath Source Routing）［10］，MP-DSR（Multi-path Dynamic Source Routing）［11］、独立多路径路由算法［12］等多路径路由算法也被相继提出。目前，路由相关的准入控制协议大多基于单路径，并且与优先级无关。由于在无线网格网络（W ireless Mesh Network，WMN）中，多路径路由通常使用2条不相交的路径来路由数据包［13］，因此为了更好地应用于智慧道路系统，本文提出一种基于优先级的双路径路由准入控制协议（Dual-path Adm ission Control，DPAC）。将请求的数据流分为不同优先级，利用带宽估算算法估算节点可用带宽和基于优先级的可用带宽进行准入控制。

2 双路径带宽分析

准入控制思想是在不影响数据传输的情况下尽可能多地准入数据流，因此，需要进行带宽检测，包括信道可用带宽和请求准入数据流的带宽。本文主要研究面向智慧道路的无线网络，在智慧道路系统中，有固定的无线路由器安装在交通信号灯上，无线

路由器使用的是802.11的无线网络协议和CSMA/ CA协议（未使用RTS/CTS），其中，载波监听范围基于文献［14］的结论：载波监听范围至少是传输距离的2倍，因此本文研究是在此基础上进行的。

2.1 可用带宽预测

可用带宽是无线网络中非常重要的资源，当一个路由节点周围有一条一直处于忙碌状态的信道，那么该路由节点的可用带宽就会很少，导致长时间延迟。文献［15］提出一种被动检测可用带宽的方法PABE，具有较好的可用带宽预测性能。本文使用PABE预测某一特定节点的可用带宽。

在PABE方法中，将可用带宽定义为：节点在不中断网络中进行通信，可提供最大带宽。对于可用带宽（Ba）的预测依赖于数据传输速率和信道空闲时间比（Channel Idle Time Ratio，CITR），Ba计算如下：

其中，DTE为数据传输速率，表示为节点在一秒钟内能够传输的最大有效比特数，DTE取决于接口卡的发送速率以及其他随机因素；Ridle为可用信道在一段时间内的空闲时间比。

2.2 数据传输速率

一个节点成功传输一个大小为SDATA的单播数据包所需的平均时间为T，该时间是从数据包开始传输进行计算，到ACK数据包被收到且信道又变为空闲为止。时间T中包含重传时间DTE计算如下：

当第i次发送单播数据包时，所需时间Ti计算如下：

其中，TDATA和TACK是传送数据帧和ACK帧数据所需的时间；BACKOFFi是在发送数据包前所需的平均退避时间；DIFS和SIFS是指IEEE 802.11标准中的帧间隔。

如式（4）所示，TDATA由两部分组成，传输速率各不相同。第一部分以传输数据包速率（DR）来传送数据帧以及MAC层头帧所需的时间，第二部分以基本物理层规定的速率（BR）来传输物理层头帧所需的时间。

ACK帧（ACKframe）及其物理层头部帧都是以BR的速率近场传输，因此，传输ACK帧所需时间TACK计算如下：

在IEEE 802.11中，退避过程使用竞争窗口机制处理传输失败。当节点传送数据时，必须收到对方发送的确认帧，否则认为传输失败。当节点发现传输失败后，需要等待一段时间再发送数据。使用指数型退避算法（Exponential Backoff A lgorithm，EBA）计算等待时间：在发送数据前，在竞争窗口［0，W-1］之间随机选择一个退避时间W（W取决于重传次数）。第一次传输数据时，W等于可能的最小值（CWmin）。在每次传输失败后，W会翻倍，直至到达最大值（CWmax）。退避时间计算如下：

假设每次重传数据帧都是相对独立的，均有一个相应的成功率ps，那么第n次尝试发送数据的成功率为p（n）计算如下：

其中，0≤n≤RL，RL是在IEEE 802.11标准中定义的最大重传次数。传输一个数据帧的总时间T计算如下：

当求出总时间T后，将式（10）代入式（2）计算出DTE。由于在真实无线网络环境中，ps是很难获取到的，因此用本地节点及其邻居节点的历史数据来获得ps的估计值。p0表示该节点之前发送数据包的成功率（i=0），pi表示该节点第i个邻居的历史发送成功率，i=1，2，…，m。ps计算如下：

2.3 信道空闲时间比

为预测信道的空闲时间比，引入NCSR（No Collision Sensing Range）阈值预测周围传输情况。在一段时间Δt内，表示发送端使用NCSR检测到信道忙碌的时间，表示发送端使用802.11的载波监听域（CS-threshold）检测到信道忙的时间。依据文献［11］的结论，信道空闲时间比Ridle计算如下：

2.4 多路径下的消耗带宽计算

本节主要介绍在多路径下，一个特定节点被准入数据流消耗的带宽计算。假设一条数据会话的带宽需求是Breq，且该会话将通过n条路径进行传输，那么定义Pi表示第i条路径，Ri表示在路径Pi上分配的发送速率，则Breq表示为：

当一个数据会话被准入后，需通过n条路径进行传输，那么对于一个特定节点，该数据会话会消耗多少带宽取决于：（1）该数据会话的传输路径上有多少节点会与当前节点竞争信道；（2）每条路径所分配的传输速率。基于以上因素，假设给定一个特定的节点x，被准入的数据会话对其消耗的带宽为，计算如下：

其中，CSNx表示在节点x的载波监听范围内的节点，包括x；｛Pid｝表示在第i条路径上的节点，除了终点d；‖表示该集合的节点数。

对于任意一个节点x，假设它在该数据会话被准入前的可用带宽为。当数据会话被准入后，剩余带宽为，则剩余带宽计算如下：

3 基于双路径路由的准入控制协议

3.1 双路径路由

本文提出的准入控制与路由相耦合，整个准入控制过程为：（1）智慧道路无线网络的初始化；（2）路由发现，找到2条最优路径；（3）路由返回，进行准入控制。智慧道路无线网络初始化是指网络中的所有节点都会定期发送数据包来交换和采集本地节点和邻居节点的信息，因此，所有节点都会采集周围的邻居节点的信息并且记录下来。

3.2 基于优先级的可用带宽计算

在智慧道路无线网络中，由于数据流有不同优先级，因此优先级高的数据流应当被优先准入，如果一个特定节点，低优先级的数据流被准入且剩余带宽已经不能满足高优先级数据流的情况下，低优先级的数据流应当从准入的队列中剔除，释放出其占有带宽来优先满足高优先级的数据流。所以，在同一节点，不同优先级的数据流拥有不同的可用带宽，对于高优先级的数据流来说，节点可用带宽是节点目前可用的带宽减去低优先级数据流预留的带宽。

为方便计算某一个优先级数据流的可用带宽总和，设计一个基于优先级的带宽预留索引表，如图1所示，每个优先级都有一个带宽预留总和TBRi，即优先级i下所有数据流带宽预留的总和，每个优先级有一个表格记录每一个预留数据的信息。

图1 优先级带宽预留索引表

3.3 路由发现

路由发现过程如下：源节点创建一个RREQ数据包并将它广播到所有邻居节点，该RREQ数据包包含一个数据包ID。当节点收到RREQ数据包后，将数据包ID与本地记录作对比。如果在记录中没有找到该ID相应的记录，那么记录RREQ数据包信息，并在这个数据包中加入该节点的信息，包括此节点中基于该数据流优先级的可用带宽信息。否则将这个数据包直接丢弃。当RREQ数据包最终到达终节点时，包括从源节点到终节点整条路径的所有信息。终节点通过设置一个时间窗口来收集RREQ数据包，该时间窗口的取值与路由延迟和发现路径数目相关，如果窗口取值偏大，会增加路由延迟；如果窗口取值偏小，可能得不到需要的路径数目。

3.4 路径选择和速率分配

当终节点收集到所有RREQ数据包后，在这些路径中选出2条最优路径并为它们分配速率。

定义1 一条路径P的可用带宽设为RBp，它是该路径上拥有最小可用带宽的节点带宽，这在一定程度上反映了整条路径的传输能力，假设路径P有n个节点，并且第x个节点的可用带宽为Bxr，那么RBp计算如下：

定义2 假设ρ为一个路由节点不重合的路径集合，这个路径集合的可用带宽为ρ中拥有最小可用带宽的路径带宽RBρ，假设ρ=｛P1，P2，…，Pn｝，第x条路径的可用带宽为RBρx（x=1，2，…，n），那么RBρ计算如下：

求解max｛RB｛P1，P2|P1，P2∈ρ｝｝，使其满足RBP1≥0，RBP2≥0，并且为2条路径分配的速率R1，R2不仅要大于0，而且相加为请求准入数据流的带宽需求Rreq。假设一个节点的可用带宽与速率R呈线性关系，即a+b×R，且2条路径分别有m个和n个节点，所以，2条路径的RBp计算如下：

从定义2可以看出，当且仅当2条路径的可用带宽RBp相等时（RBP1=RBP2），才能取得多路径下可用带宽的最大值，即求出所有路径中的瓶颈节点的可用带宽，从中选出2条路径，它们的瓶颈节点的可用带宽相同且为最大值。假设求解得到2条路径的瓶颈节点的带宽相同且是所有路径中的最大值，分别为节点i，j，RBP1=ai+bi×R，RBP2=cj+dj×R，所以，ai+bi×R=cj+dj×R，从而求得分配速率R。

3.5 路由返回和准入控制

当求出2条最优路由路径和分配速率后，终节点会发送2个分别携带2条路径信息的RREP数据包（包含分配速率信息），并且将它们按原路返回源节点。当一个节点（包括源节点和终节点）收到RREP数据包后，进行准入控制，包括以下3种情况：

算法1 数据流释放算法

输出 数据流释放表ReleaseTable［］

在计算出数据流释放表ReleaseTable后，按照该列表进行低优先级数据流的带宽释放，满足高优先级数据流的带宽要求。

算法2 基于双路径路由的准入控制算法

输出 准入标志adm ittance

如果准入控制算法可以判断出请求数据流被予以准入，则对此节点及其载波监听范围（CSNx）内的节点进行资源预留。如果不予准入，则从候选路径中选出2条最优路径进行路由返回及准入控制，直至没有候选路径符合要求为止。

4 实验与结果分析

本文使用NS-2软件评估DPAC性能。实验使用802.11DCF和CSMA/CA作为MAC层协议。由于智慧交通的无线网络拓扑基本是不会的，因此使用150个节点均匀地分布在边长为2 000 m的正方形内进行模拟。传输范围和载波监听范围分别设为250 m和500 m。使用MSR，CACP-Multihop（CACP-M）和MSR-AC协议与DPAC进行比较。其中，MSR是一个多路径路由协议；CACP-M ultihop是一个基于单路径路由的准入控制协议；MSR-AC是在MSR的基础上加入了准入控制的协议。虽然MSR和CACPMultihop都没有将优先级考虑在内，但是将DPAC和它们比较更加能够体现出DPAC的高QoS、带宽利用率以及优先级。

使用UDP协议下的CBR流进行数据会话请求，每个数据包大小为1 000 Byte，信道容量为1 M b/s。源节点和终节点都是随机选择的，一旦选定，在整个实验中都不会改变，假设有4个优先级的数据流。模拟8个具有不同带宽需求、不同优先级的数据会话请求。流1、流3、流5、流7的带宽需求为200 Kb/s，流2、流4、流6、流8的带宽需求为100 Kb/s。优先级分配为：流1、流2为优先级4；流3、流4为优先级3；流5、流6为优先级2；流7、流8为优先级1。数据流从流1开始发送请求，每隔30 s下一个数据流开始请求准入。

图2分别展示了DPAC，CACP-M，MSR-AC，MSR协议8个数据流的平均吞吐量。可以看出，DPAC除流1外，平均吞吐量都接近带宽需求，流1之所以没有达到带宽需求是因为当流8请求准入后，节点剩余带宽不足，由于流8的优先级最高，因此释放具有较大带宽需求的流1的带宽，来满足流8的请求。

图2 数据流吞吐量

虽然CACP-M和MSR-AC的平均吞吐量都能基本满足需求，但是流6、流7和流8都没有数据，意味着流6、流7、流8的请求被拒绝，流6、流7、流8的优先级相对较高，所以，CACP-M和MSR-AC不能满足高优先级的数据包请求。MSR的8个数据流均有数据，但是平均吞吐量相对较低，达不到数据流的带宽需求。DPAC具有高平均吞吐量的原因就在于其利用双路径来分配带宽，使得拥塞问题得以缓解、负载得到均衡。相反地，MSR未考虑拥塞和负载均衡，以至于当更多的数据流进行带宽请求时，会导致性能大幅下降。

通过图3数据可以看出，当有更多的数据流请求准入后，DPAC延迟仍保持稳定，并且在DPAC中，数据流平均延迟都低于50 m s（由于流1在流8被准入后，其带宽被释放，因此流1的延迟数据不包含它被释放后的延迟）。CACP-M和MSR-AC的延迟相对较低，但都要高于DPAC的延迟。MSR的延迟则相对较大，且当更多数据流进行请求时，它的延迟变得不稳定，在最坏情况下，平均延迟达到0.2 s。

图3 数据流延迟

图4 表明，DPAC，CACP-M和MSR-AC的延迟抖动都很低，DPAC的平均抖动小于4 m s，而CACPM和MSR-AC的平均抖动小于6 m s，这样传输抖动能够提供很好的QoS服务。相反地，MSR平均抖动较大，最差情况下达到50 ms。

图4 数据流延迟抖动

可以看出，DPAC在吞吐率、延迟和抖动方面均优于现有的CACP-M，MSR-AC和MSR协议，并且DPAC加入了优先级保障，当节点带宽不足时，通过释放低优先级数据流的带宽来满足高优先级数据流的带宽需求，使得优先级高的数据流带宽得到保障。

5 结束语

在智慧交通系统中，无线网络传输的数据包是有优先级区分的。为了更好地满足高优先级数据包的带宽需求，本文提出一个基于优先级的双路径路由准入控制协议（DPAC），将路由与准入控制相结合，提高准入控制效率。同时将传统的单路径路由准入控制扩展为双路径路由准入控制，实现负载均衡及提供更好的服务质量。通过与传统单路径路由准入控制和双路径路由协议进行比较得出，DPCA在吞吐量、时延和抖动方面均具有较好性能。

［1］ Ahn G S，Campbell A T，Veres A，et al.SWAN：Service Differentiation in Stateless Wireless Ad Hoc Networks［C］//Proceedings of the 21st Annual Joint Conference of the IEEE Computing and Communications Societies.Washington D.C.，USA：IEEE Press，2002：457-466.

［2］ Yang Y，Kravets R.Throughput Guarantees for Multipriority Traffic in Ad Hoc Networks［J］.Ad Hoc Networks，2007，5（2）：228-253.

［3］ Chowdhury M Z，Jang Yeong-Min，Haas Z J.Call Admission Control Based on Adaptive Bandwidth Allocation for Wireless Networks［J］.Journal of Communications and Networks，2013，15（1）：15-24.

［4］ 张惠娟，王科特.基于Ad hoc负载均衡的AODV改进算法［J］.计算机工程，2010，36（10）：129-132.

［5］ Hanzo L，Tafazolli R.QoS-aware Routing and Admission Control in Shadow-fading Environments for Multirate MANETs［J］.IEEE Transactions on Mobile Computing，2011，10（5）：622-637.

［6］ Yang Y，Kravets R.Contention-aware Admission Control for Ad Hoc Networks［J］.IEEE Transactions on Mobile Computing，2005，4（4）：363-377.

［7］ Lindgren A，Belding-Royer E M.Multi-path Admission Control for Mobile Ad Hoc Networks［C］//Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous System s.Washington D.C.，USA：IEEE Press，2005：407-417.

［8］ Asif M，Sun Z，Cruickshank H，et al.Flow Aware Admission Control-multipath Protocol with Multiple Constraints（FAAC-MM）for Assurance of Multiple QoS Metrics in MANETs［C］//Proceedings of the 18th IEEE Symposium on Communications and Vehicular Technology in the Benelux.Washington D.C.，USA：IEEE Press，2011：1-6.

［9］ Ye Zhenqiang，Krishnamurthy S V，Tripathi S K.A Framework for Reliable Routing in Mobile Ad Hoc Networks［C］//Proceedings of the 22nd Annual Joint Conference of the IEEE Computing and Communications. Washington D.C.，USA：IEEE Press，2003：270-280.

［10］ W ang Lei，Zhang Lianfang，Shu Yantai，et al.Multipath Source Routing in Wireless Ad Hoc Networks［C］// Proceedings of Canadian Conference on Electrical and Computing Engineering.Washington D.C.，USA：IEEE Press，2000：479-483.

［11］ Leung R，Liu Jilei，Poon E，et al.MP-DSR：A QoS-aware Multi-path Dynamic Source Routing Protocol for Wireless Ad-hoc Networks［C］//Proceedings of the 26th Annual IEEE Conference on Local Computing Networks. Washington D.C.，USA：IEEE Press，2001：132-141.

［12］ 史景伦，张 凌.Ad hoc网络中的一种独立多路径路由算法［J］.计算机工程，2003，29（21）：14-22.

［13］ Thulasiram an P，Ramasubramanian S，Krunz M.Disjoint Multipath Routing to Two Distinct Drains in a Multidrain Sensor Network［C］//Proceedings of the 26th IEEE International Conference on Computing Communications.Washington D.C.，USA：IEEE Press，2007：643-651.

［14］ Zhai Hongqiang，Fang Yuguang.Physical Carrier Sensing and Spatial Reuse in Multirate and Multihop Wireless Ad Hoc Networks［C］//Proceedings of the 25th IEEE International Conference on Computing Communications. Washington D.C.，USA：IEEE Press，2006：1-12.

［15］ Zhao Peng，Yang X inyu，Dong Chiyong，et al.On an Efficient Estimation of Available Bandwidth for IEEE 802.11-based Wireless Networks［C］//Proceedings of 2011 IEEE Global Telecommunications Conference. Washington D.C.，USA：IEEE Press，2011：1-5.

编辑 陆燕菲

Admission Control Protocol of Dual-path Routing for Intelligent Road Wireless Network

WU Yanqiong，CHEN Shiping
（School of Optical-Electrical and Computing Engineering，University of Shanghai for Science and Technology，Shanghai200093，China）

In the Intelligent Road（iRoad）system，in order to meet the throughput requirement of packets with different priority，this paper presents an admission control protocol of dual-path routing based on priority.It analyzes the node available bandwidth based on priority and sends the paths which satisfies the requirement by data streaming to the final routing node.After receiving all the candidate paths，it selects the two best paths to meet the data streaming bandwidth requirement.W hen the data packet returns from final routing node，the local node uses its surrounding node available bandwidth prediction to do admission control to ensure preferential access of high-priority data streaming.Simulation results show that compared with the single-path-based admission control，the proposed algorithm has higher throughput，lower latency and jitter，which guarantees bandwidth demand for high-priority data flow.

Intelligent Road（iRoad）；wireless network；priority；dual-path routing；admission control

吴彦琼，陈世平.面向智慧道路无线网络的双路径路由准入控制协议［J］.计算机工程，2015，41（11）：24-29，40.

英文引用格式：Wu Yanqiong，Chen Shiping.Admission Control Protocol of Dual-path Routing for Intelligent Road Wireless Network［J］.Computing Engineering，2015，41（11）：24-29，40.

1000-3428（2015）11-0024-06

A

TP393.02

10.3969/j.issn.1000-3428.2015.11.005

国家自然科学基金资助项目（61170277，61472256）；上海市教委科研创新基金资助重点项目（12zz137）；上海市一流学科建设基金资助项目（S1201YLXK）。

吴彦琼（1990-），女，硕士研究生，主研方向：无线通信，云计算；陈世平，教授、博士生导师。

2014-12-24

2015-01-27 E-m ail：adeline1899@126.com