潘海龙　陈世平

摘要：无线网络传输数据因具有低成本高效率的优点，在智能交通领域得到广泛应用。然而智能交通拥有数据突发性强和拓扑范围广的特点，为无线网的准入控制带来了巨大挑战。采用FACP 算法（FilteringAware Admission Control Protocol ），在准入控制路由寻找阶段增加初级准入控制，以减少数据传输范围，并在路由回复阶段将资源预留淘汰功能放入准入控制以解决数据突发问题。与传统的DSR、CACP准入控制等算法进行对比实验，结果表明，采用FACP算法较现有的准入控制具有更大的优势。

关键词：智能交通；无线网；准入控制；路由寻找阶段；路由回复阶段

DOIDOI：10.11907/rjdk.151324

中图分类号：TP311

文献标识码：A 文章编号：16727800（2015）006006504

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

作者简介作者简介：潘海龙（ 1988- ） ， 男，上海人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为无线网络、P2P；陈世平（1964-），男， 浙江绍兴人，博士，上海理工大学光电信息与计算机工程学院教授，研究方向为计算机网络通信、数据库与知识库、信息系统研究和开发。

1 问题提出

随着科技与经济的发展，减少交通拥堵是各国政府致力解决的难题之一。智能交通能在多方面增强交通基础设施，如利用每个交叉路口的传感器接收信息并建立实时交通图，驾驶员通过此信息可以找到通往目的地的最佳路径。智能交通的智慧节点与交通灯结合，通过优化交通灯工作状态，提高道路车辆吞吐量。因智能交通需在所有交叉路口设置智能节点，如果用有线技术传输实时数据需要大规模开挖路面，铺设通信光缆以及连接交叉路口至控制室的各种设备，成本过大，因此，需在智能交通中采用无线网技术[1]。在无线网技术中任何一个节点发送数据都会竞争信道，从而影响其它节点的正常通信。为防止新的数据流消耗过多资源影响到正常通信，引入了准入控制，然而，智能交通的独特性给无线网中的准入控制带来了挑战。

挑战一：智能交通因需要覆盖整个城市，无线拓扑非常广，无线结点众多，这对于通过单纯广播方式完成准入控制代价是巨大的。假设结点传输范围R为传输范围内的结点密度，传统的准入控制规定每一结点收到路由寻找消息后，要将此消息再次转发给其传输范围内的所有节点，以此类推到经过n跳到达目标结点时会收到路由寻找信息，因此在整个路由寻找阶段，路由寻找信息将被发送n次。由此可发现，仅通过单纯广播来实现路由寻找的通信代价是巨大的；挑战二：早晚高峰时间交通状况较复杂，数据突发情况多，这时多个发送结点同时分享相同资源节点和目标节点可能性增大，不同数据流在相同结点进行准入控制以及资源预留的时间间隔变短，这时如果较低优先级的数据流通过了准入控制并产生了资源预留，高优先级的却因资源已被预留而被拒绝准入，这将对服务质量产生极大影响。

为解决上述问题，本文通过改进路由寻找阶段和路由回复阶段的准入控制，来适应智能交通系统对无线网的新要求。

2 文献综述

目前在准入控制算法中最常用的是DSR动态路由寻找，见参考文献[34]，[6]，[89]，[11]。它采用单纯的广播方法发送路由寻找请求，但是在传输范围广的情况下传输代价很大，这显然不适合智能交通。在路由回复阶段，带宽预测有3种不同的研究：①用空闲的带宽作为评估可用带宽的标准，这个方法不支持优先级[23]。然而在智能交通中，通信数据拥有优先级，比如交通指示灯数据比实时视频数据重要，需要优先保证其通信[47]；②通过估计信道的访问时间来估计可用带宽数，然而在新数据流还没到达前可用带宽的预估数是大于实际的[810，12]；③根据本地通信状况如竞争窗口大小、帧大小以及网络拥塞忍耐状况确定可用带宽[11]。这个方法的好处在于它权衡了本地通信状况以及对邻居节点的影响，给出了可用带宽预估方法。但是，这几种方法都忽视了数据突发情况下资源预留对可用资源预估的影响，这种缺陷对于具有数据突发特性的智能交通来说是致命的。为解决以上问题，本文提出了FACP算法。

3 FACP算法

无线准入控制由路由寻找和路由回应两部分组成。传统的无线准入控制在路由寻找过程中都采用了DSR动态路由算法。此路由算法是：发送者广播路由寻找请求，传输范围内的所有接受者收到请求信息并检测自身是否为目标节点，不是则将地址放入路由记录并再次广播，直至到达目标节点。由于智能交通智慧节点多且覆盖范围广，仅靠广播方式寻找路由通信代价是巨大的。

传统路由在回应阶段忽视了数据突发情况下对可用带宽预估的改变因素，数据突发情况下多个发送节点几乎同时分享相同资源点和目标节点间的路径和节点可能性增大，低优先级因比高优先级早到一点点时间通过准入控制并将资源预留，然而早到时间不足以发送完低优先级数据流，此时高优先级数据流却因资源已被低优先级预留而被大大延迟，降低了服务质量。本文提出的FACP算法在路由寻找和路由回应阶段分别采用初级筛选功能和预留淘汰的准入控制方法。

3.1 路由寻找阶段

路由寻找的目标是找到发送节点与目标节点间拥有足够资源的路由提供给数据流。作为拓扑结构复杂且拓扑范围广的智能道路，需要查找更准确代价更低的路由寻找方法。FACP在路由寻找阶段通过初级准入控制完成了筛选功能，解决了传统准入控制在路由阶段的不足。初级准入控制指为了减少不必要的广播转发，淘汰不符合初级准入条件的节点，以达到准确查找节点且代价更低的目的。新数据流对网络的负载预估Unew与节点数n有关（即Unew=nRnew，Rnew是新数据流要求速率），n为该结点传输范围内满足路由路径上的结点数量，公式表示为n=Total△∩Route△。Total△表示△的传输范围内节点总数量，Route△表示△的传输范围内新数据流路由经过的节点数量。因在路由阶段路由路径还未确定，n保守地设为1，即Unew=Rnew，此时对数据流负载的初期预估比实际要小，淘汰那些连初期负载预估都满足不了的资源节点，以避免这些节点作无谓的广播，按照这种预估作为准入控制的标准称为初级准入控制。在路由寻找阶段，每个节点通过广播方式已经收集到邻居节点通信状况信息，其中包括WXi竞争窗口大小、LXi帧大小、RXi数据速率、η*r拥塞忍耐状况等，这些数据都保存在节点的缓存中，当周围节点通信状况发生变化时才更新。当收集完邻居节点的通信后，节点根据这些信息预估出可用资源。参考文献[11]算法可以在路由寻找信息到达节点之前就完成可用资源预估Anew=C（1-ni=rRXiLXi[]C-1[]η*rr-1i=1LXi[]WXi），发送节点广播路由寻找信息，信息包括新数据流要求速率、路由信息等，节点收到路由寻找信息后，比较可用资源预测信息是否大于新数据流负载的初期预估，满足条件则将路由地址加入路由信息并继续广播路由寻找信息，以此类推直至达到目标节点。当不能满足要求时，则直接丢弃路由寻找信息。初级准入控制通过淘汰一些节点来实现减少路由广播次数、减少数据传播代价、加快路由寻找速度的目的。

3.2 路由回复阶段

路由寻找信息到达目标节点后，标志着路由寻找阶段的结束和路由回复阶段的开始。目标节点根据先前路由寻找阶段确定的路由，发送路由回复信息，其中包含路由信息、新数据流速率、数据流的优先级等。路由结点收到信息后，开始进行准入控制。由于此阶段路由已经确定，因此此时新数据流对网络负载预估是准确的。将可用资源的预估与流量对网络负载预估进行对比，进行准入控制，使新数据流不影响到比它优先级高的数据流正常通信。

这个关于x的不等式能满足新数据流的负载预估保留的最低资源预留优先级。当最低资源预留优先级x∈[1，k]，说明新数据流的加入需要淘汰优先级比自己高的资源预留才能通过准入控制，这将导致流经该节点的高优先级数据流阻塞，影响到服务质量，因此该新数据流不满足准入控制需要，该路由回复信息要丢弃。当最低预留优先级x=k时，表明新数据流的加入需要淘汰该节点预留优先级比它低的k+1至n的数据流。当x∈（k，n），说明只需淘汰x+1至n的数据流预留就能通过准入控制，不需要淘汰所有比新数据流优先级低的资源预留，达到充分利用节点资源的目的。当x∈（n，+∞），说明该节点通过准入控制并且节点有充分的带宽资源，不需要淘汰任何资源预留。资源预留淘汰机制过程如下：当确定好需要淘汰的预留资源时，节点根据这些数据流的路由信息发送节点撤销指令，并要求过一段时间之后重新进行准入控制。为保证资源预留的实时准确性，通过准入控制的新数据流，更新该节点的资源预留Uk=Uk+Unew，并继续根据路由信息进行转发直至到达发送节点，完成整个准入控制。图1为整个准入控制的工序流程。

4 模拟与分析

模拟数据如下：有100～300个结点随意分配在10×10至1 000×1 000的范围内，通信范围为300m，载波监听范围为600m，信道带宽为4mbps。本文通过以下3个方面检测FACP算法的优势与性能：①通过节点数量固定拓扑范围变化检测；②拓扑范围固定增加节点密度检测；③通过相同时刻数据流突发变化检测FACP的优势。

实验一：将FACP与传统的DSR在控制开销比率上进行对比。控制开销比例是整个准入控制中通信开销大小与数据流对网络的负载大小之比。从图2可以看出，当节点拓扑范围10×10时，控制开销几乎可以忽略。因为这时发送节点和目标节点距离很近，只需要一跳就能完成，所以此时FACP与传统DSR寻找路由的准入控制效果是一样的。然而随着拓扑范围越来越大，跳数增加导致转发次数增加最终引起的控制开销也明显增大。FACP在路由寻找过程中筛选不必要跳数的优势也就愈加明显。

实验二：考察不同节点密度下，控制信息的变化数。由图3可看出，随着节点密度的增加，控制信息转发的次数也不断增多，相较于传统DSR寻找路由，采用FACP算法的控制信息发送次数则大大减少，这是因为FACP在路由寻找过程中筛选出了不符合初级准入控制的结点，减少了控制信息发送的次数。

实验三：通过与MPARC[10]和CACP算法[11]进行对比，考察相同时刻数据流突发程度变化对PDR影响的程度。由图4可以看出，网络中同时产生的数据流条数为0～40时，CACP、MPARC和FACP的数据到达率都是相同的，这是因为网络未饱和时准入控制的效果未显现。而到40条数据流以后，网络开始出现一定拥塞，CACP数据到达率下降最快，这是因为CACP估算信道时对数据流优先级一视同仁，这时FACP与MPRARC数据到达率一样，因为这时数据流并未足够的多。而到60条数据流时，数据突发随之开始，FACP效果开始显现，FACP算法的数据到达率具有较好的稳定性。

5 结语

拓扑范围广、数据突发性高是目前无线网络在智能交通应用时所面临的难题。本文通过在路由寻找阶段增加初级准入控制，致使不满足初级数据流要求的结点淘汰，以此解决拓扑范围广引起的控制开销大的问题。本文还通过路由回复阶段将资源预留淘汰功能放入准入控制中，使数据突发情况下节点的可用带宽被低优先级数据流预留的情况得以解决。实验表明，采用控制开销比率、控制信息数量和数据到达率的方式，使FACP在拓扑范围广和数据突发情况下表现优异。

参考文献：

[1]U S. Department of Transportation.ITS Overview[EB/OL]. http：//www.its.dot.gov/its verview.htm， 2008.

[2]MICHAEL G BARRY， ANDREWT.Distributed control algorithm for service differentiation in wireless packet networks[J].IEEE INFOCOM ，2001，26（10）：439502.

[3]D MALTZ. Resource management in multihop Ad hoc networks[J].Technical Report CMU CS 00150，2000，623（8）：123231.

[4]AGRAWAL S，CHAPORKAR P UDWANI .All admission control for realtime applications in wireless network [J]. IEEEINFOCOM，2013，45（7）：330334 .

[5]AIKTUAN LEE，GERLA M.Performance evaluation of wireless network coding in TDMA networks[J].IEEE INFROCOM ，2012 ， 9（3）：1 6 .

[6]BRUHADESHWAR B.A fully dynamic and selfstabilizing TDMA scheme for wireless Adhoc networks advanced information networking and applications （AINA）[C].24th IEEE International Conference ，2010：706812.

[7]QING JIN ZENG.A crosslayer based TDMA protocol for wireless biomedical sensor networks biomedical engineering and informatics （BMEI）[C].5th International Conference ，2012：340456.

[8]MANTHOS KZANTZIDIS， MARIO GERLA， SUNGJU LEE.Permissible network feedback for adaptive multimedia in aodvmanets[C].IEEE Conference ，2001：56123.

[9]HONG PENG WANG.Nodetonode available bandwidth estimation in ad hoc networks computer and electrical engineering[C].International Conference，2008：701705.

[10]CABELLOS APARICIO A.A novel available bandwidth estimation and tracking algorithm[C].IEEE International Conference 2008 ， 8（7）：8794.

[11]YALING YANG.Throughput guarantees for multipriority traffic in Ad hoc networks[J].IEEE International Conference on Mobile Adhoc and Sensor Systems， 2004，30（1）：410500.

[12]PENGZHAO. Rateadaptive admission control for bandwidth assurance in multirate wireless mesh networks[J].IEEE International Conference on， 2010：659663.

责任编辑（责任编辑：杜能钢）

英文摘要Abstract：Intelligent traffic is of great importance to the development of transport infrastructure modernization. Wireless data transmission network because of its advantages with low cost and high efficiency has been well received by the Intelligent traffic， however intelligent traffic has characteristics of the data of sudden strong and large topological range ，which poses great challenges for wireless network access control. This paper adopts FACP algorithm （FilteringAware Admission Control Protocol）， the admission control protocol is included in the route finding phase to create primary access control， in order to reduce the data transmission range， and in the route reply phase will be the resource reservation elimination function to solve the problem of data burst. Compared with the traditional DSR， CACP admission control algorithm， It is verified the effectiveness of the proposed method. Experiments show that the FACP algorithm compared with the existing admission controlprotocol has more advantages.

英文关键词Key Words： Intelligent Traffic；Wireless Network；Admission Control Protocol；Route Finding Phase；Route Reply Phase