城市复杂动态交通自适应局部路由策略

王　丹, 李蓓蕾

(沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳　110044)



城市复杂动态交通自适应局部路由策略

王丹, 李蓓蕾

(沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳110044)

摘要:针对实际交通动态网络情况,提出一种自适应局部路由动态诱导策略.该策略不仅考虑了静态路网结构信息,同时也结合了车辆等待排队时间等因素,通过引入可调节参数,可以给定车辆传输的实际路径,直至车辆到达目标节点.数值仿真试验表明,与已有的局部路由策略和随机游走策略相比,该自适应局部路由算法能更有效地增加网络的通行能力.

关键词:自适应; 局部路由策略; 复杂交通网络

随着人们生活水平和对生活质量需求的不断提高,出行频率不断增加,而交通工具的多样化,使交通路网的压力与日俱增.近几年来城市交通发展的障碍和瓶颈愈发凸显,现代交通网络的纷繁性、复杂性及时变性,给路径疏导策略的研究提出了新的挑战.复杂网络的兴起,为研究城市交通网络拥塞控制提供了新的视角和方法.

城市交通网络是一个实际存在的大型复杂网络系统,在进行研究的时候要了解其本身的网路特点及变化,在此基础上才能够通过它的基本属性分析网络结构对城市交通网络上费用、流量,以及拥堵的影响情况,从而为城市交通的疏导提供切实有效的改进方案,为交通控制做更好的服务.同时通过这些研究,反推城市交通网络演化机理,从而为城市交通规划、控制和管理策略提供决策依据[1].

复杂网络的核心问题在于如何提高网络中边和节点的运输效率,从而优化整个网络的传输能力.根据目前的研究进展,路由策略从宏观上来讲,可分为基于网络结构的路由策略和基于动力学的路由策略;在此基础上又将基于网络结构的路由策略细分为基于节点和边的路由策略及改变拓扑结构的路由策略;从动力学角度而言,又可以分为路径选择策略和排队策略.无论从什么角度出发,研究的目的都是为了优化和提高整个路网的通行能力,因此路由策略的选择,控制拥塞是研究的当务之急.要了解网络传输策略,并与实际的交通网络相结合,从而进一步缓解拥塞提高路网容量的需求.

在一个给定的交通网络中,当某节点的车辆数超过了节点的容量时,拥塞现象必然会出现,并会相继扩展.在这种情况下最短路径路由策略得到了广泛的关注,阻塞最严重的地方往往会是hub节点,但只要分配给hub节点更多的容量就可能对拥塞有所缓解.文献[2]提出了依据节点度的大小来决定节点容量的模型.此模型认定度较大的节点一定会有更强的接受能力,因此将会被分配多一些的容量.与节点容量相同的情况比较,该模型较大地提高了网络的容量.文献[3]提出了一个数据包容量是定常量的传输模型.此模型中节点的度与节点的容量之间是一种线性关系.

提高网络的运输效率还可以从拓扑结构方面来研究,以往的研究表明网络的运输效率很大程度上取决于拓扑结构的形式,因此可以通过删除和增加一些节点和边来达到优化整个网络的目的.文献[4]提出由于介数比较大的节点在网络中数量不多,因而同构网络要比异构网络容量大,能够接受更多的车辆.文献[5]从另一个角度出发, 以边两端节点的介数乘积为依据,进行删边扩容,以减少网络中介数较大节点的个数.

路径选择策略可以分为静态路径选择策略和动态路径选择策略.早期的随机游走策略由于其独特的搜索机制而被广泛使用.之后又有学者提出经典最短路径路由策略,主要操作步骤是每一次传输都按照从起点开始到终点结束的路径进行,它的优点在于经济性和可操作性,被广泛应用于交通网络中.这种最短路径的选择在很大程度上造成了hub节点的高负荷,随着时间的推移有可能造成节点的瘫痪.学者们也考虑到了hub节点的高负荷问题,因此又提出了一个更优的路由策略----ER策略[6].文献[7]利用介数这一概念提出了介数路径选择策略.

上述路径选择策略均是基于全局信息的,在实际的网络中由于各方面的原因可能做不到将全局信息纳入到考虑范围之中,因此基于局部拓扑信息的路由策略[8-10]更加有现实意义.局部路由策略不需要了解整个网络的全局信息,而是将侧重点放在局部网络的搜索上,通过对局部信息的掌控、节点的选择,最后达到整个网络的可控和优化的效果.本文拟从实际交通网络出发,结合交通道路信息和交通车辆动态信息的角度进行研究制定路径选择策略.

1自适应局部路由策略

1.1交通路网拥塞指标

网络中路由策略的设计,首先要依据此网络的传输能力大小.交通网络的传输性能主要表现在两个方面,其一是对车流量的疏导,其二是对网络中车流通行能力进行衡量.但是仅仅将单个节点的通行能力做简单的相加并不能得到整个网络的准确通行能力.在研究中发现可以这样表示,即单个节点i的通行能力记作ni,并且假设每个网络都会存在一个临界车流量,也就是说在一定的范围内,网络中有允许存在的最大车流量,可以将临界车流量作为网络通行能力的一个表述,记作Rc.以Rc为切入点,作为网络中连续相变的转折点,即从自由态向拥塞态的变化过程.

所谓自由态是指在网络中,同一时间步内,新增车辆数与到达目标节点的数目相同时可以相互抵消的一种状态,道路上并不会发生拥塞现象,车辆流通顺畅.而拥塞态表现的是另外一种形式,新产生的车辆会不断进入网络中,在新产生车辆的这部分中,仅有少量的车辆会到达目标节点,到达目标节点的车辆可以视为已经从系统中消失了,而剩下的大部分车辆仍然存留在网络中,而且会逐步积累,不断放大,最后有可能造成交通系统的瘫痪.因此,交通网络中的拥塞转变可以采用参数

(1)

式中,R为单位时间内交通网络中产生的车流数量,W(t)为t时刻交通网络中总的车流数量.W(t+Δt)-W(t)表示在Δt时间段内网络中存在的车流数量.H(R)为Δt时间段内交通网络中现存的车流数量与网络中新产生车流数量的比值.H(R)≈0时,表示网络畅通,网络中没有明显的车辆滞留,当H(R)>0时,表示网络出现了车辆滞留,而当H(R)≈1时,表示网络中的车流完全拥堵.

1.2交通路网模型演化规则

经过对以往路由策略的研究,并针对当前研究的交通网络的特点,在本文中将结合交通路网的特有属性设计车辆动态诱导的行进及演化规则,如图1所示.

图1　车辆动态诱导演化规则流程图

(1) 新增车辆.即在交通网络中开始出现新的车辆数.假设整个交通网络从无负载的顺畅态开始,在经过每一时间步后网络都将会产生R辆车辆,此时系统中存在的这些车辆都会并且随机选择源节点和目标节点.

(2) 搜索目标节点.从进入该网络中开始根据各方面因素搜索适应度最大的目标节点.而网络中单个节点都可以看作一个沟通连接站,在做传递车辆的任务中,对于目标节点的搜索首先在邻节点内完成,如果发现目标,搜索任务顺利完成,下一步就将车辆直接按照路线进行传输;如果没有发现目标节点,则会依据以下诱导策略进行下一节点的选择.

(3) 车辆传输.搜索任务完成后,将会把车辆作为数据包传递给被选中的节点,此时该车辆将会依照给定的传递路线行驶,最后到达目标节点后将在网络中消失,完成了整个车辆(数据包)在交通网络中的进入到流出的过程.

以上演化规则是基于交通网络是从无负载开始的.在整个网络中每个节点的能力是不同的,即它接收并处理车流量数据包的能力不同,这里把节点所表现的能力的大小看成此节点在网络中的重要程度ni,节点的能力大小也可以通过实际操作的数量来表示,即在单位时间内所传递车辆数具有上限,最多只能传递ni个车辆数据包至下一个目标节点.队列的尾端将依次接受新产生的车辆数据包,这部分也将被纳入到该节点的队列长度中.为了研究的可行性及有效性,假定队列长度无上限.

1.3自适应局部动态诱导策略设计

以往的研究表明,不同的路由策略对整个网络的容量的影响有所不同,因此动态的诱导策略在缓解拥塞及疏导网络流量的方面显得极其重要.但是我们发现实际的网络变化有可能是瞬时的,然而以前的路由策略(例如最短路径,局部最优路由策略)都不能根据实际负载而做出相应的变化,考虑到以往设计中的不足,本文设计的自适应局部动态诱导策略不仅考虑到静态的路径信息而且也考虑到动态车流量的变化而引起的对路径选择的影响.给出选择的局部动态诱导算法的优先选择概率为

(2)

(3)

2数值仿真与分析

用式(1)中拥塞转变系数进行描述.如果H≈0时,交通网络处于通畅状态下;如果H>0时,交通网络将会发生拥塞,拥塞的程度大小将会随着H的增大而愈加明显.

图2显示了网络拥堵程度表征参数H与四种不同路由策略下网络瞬时车流增加量R之间的关系曲线.“△”曲线表示自适应路由策略,“□”曲线表示随机游走策略,“◇”曲线表示负相关的路由策略,“○”曲线表示正相关的路由策略.从图1中可以看出,采用自适应路由策略得到的最大网络吞吐量明显好于其他三种策略,次优的策略是度负相关的路由策略,而度正相关和平均游走策略的效果明显不如前两者.这是因为自适应策略可以根据车流量自动调节自身的参数,充分利用节点度的大小与负载量的变化情况,重新对路径做出选择.当车流负载较轻时,α增加,充分利用度高的节点传输流量,减小路由步数;当车流负载较重时,α减小,避开度高的节点,减少拥堵程度.所以自适应策略可以最有效地增加网络的流通能力.

图2　　　　在4种路由策略下,网络拥堵程度表征

3结论

与其他路由策略相比,自适应局部路由策略的优点在于能够实时的根据车辆负载信息做出调整和变化,尤其是对动态车流量的大小做出了敏感的反应.一般情况下,交通网络中度比较大的节点承担着较大的输送任务,如果发生拥堵,根据度的大小来讲,拥堵程度高的节点大部分会出现在度大的节点中,此时就需要使用自适应局部路由策略来降低这部分节点的负载量.通过有效地利用调节参数可以对车辆的路径进行重新选择和优化,大大提高了交通网络的可通行能力和运行效率.

参考文献:

[ 1 ] 高自友,赵小梅,黄海军. 复杂网络理论与城市交通系统复杂性问题的相关研究[J]. 交通运输系统工程与信息, 2006,6(3):41-47.

(GAOZY,ZHAOXM,HUANGHJ.Researchonproblemsrelatedtocomplexnetworksandurbantrafficsystems[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2006,6(3):41-47.)

[ 2 ]LIUZ,MAW,ZHANGH,etal.Anefficientapproachofcontrollingtrafficcongestioninscale-freenetworks[J].PhysicaA:StatisticalMechanicsandItsApplications, 2006,370(2):843-853.

[ 3 ]YANGHX,WANGWX,WUZX,etal.Trafficdynamicsinscale-freenetworkswithlimitedpacket-deliveringcapacity[J].PhysicaA:StatisticalMechanicsandItsApplications, 2008,387(27):6857-6862.

[ 4 ]GUIMERAR,DIAZ-GUILERAA,VEGA-REDONDOF,etal.Optimalnetworktopologiesforlocalsearchwithcongestion[J].PhysicalReviewLetters, 2002,89(24):128-134.

[ 5 ]ZHANGGQ,WANGD,LIGJ.Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks[J].PhysicalReviewE, 2007,76(2):55-86.

[ 6 ]YANG,ZHOUT,HUB,etal.Efficientroutingoncomplexnetworks[J].PhysicalReviewE, 2006,73(4):046108.

[ 7 ]JIANGZY,LIANGMG.Improvedefficientroutingstrategyonscale-freenetworks[J].InternationalJournalofModernPhysicsC, 2012,23(2):302-313.

[ 8 ]WANGWX,WANGBH,YINCY,etal.Trafficdynamicsbasedonlocalroutingprotocolonascale-freenetwork[J].PhysicalReviewE, 2006,73(2):026111.

[ 9 ]YINCY,WANGBH,WANGWX,etal.Efficientroutingonscale-freenetworksbasedonlocalinformation[J].PhysicsLettersA, 2006,351(4):220-224.

[10] 王丹,李蓓蕾.无标度网络的局部路由策略仿真分析[J]. 沈阳大学学报(自然科学版), 2015,27(5):394-399.

(WANGD,LIBL.SimulatedAnalysisofLocalRoutingStrategiesBasedonScale-FreeNetworks[J].JournalofShenyangUniversity(NaturalScience), 2015,27(5):394-399.)

[11]BARABASIAL,ALBERTR.Emergenceofscalinginrandomnetworks[J].Science, 1999, 286(5439):509-512.

【责任编辑: 李艳】

AdaptiveLocalRoutingStrategyinComplexUrbanDynamicalTrafficNetworks

Wang Dan, Li Beilei

(KeyLaboratoryofManufacturingIndustrialIntegratedAutomation,ShenyangUniversity,Shenyang110004,China)

Abstract:In view of the actual traffic dynamical road networks, a new adaptive local routing strategy is proposed for inducing vehicles. The adaptive local routing strategy not only considers the static road network structure information, but also combines the waiting queue time of the vehicles. By introducing the adjustable parameters in the new routing, the actual path of the vehicles can be given until the vehicle reaches the target node. Numerical simulations show that the proposed adaptive local routing algorithm can effectively increase the traffic capacity of the traffic network, compared with the existing local routing strategy and the random walk strategy.

Key words:adaptive; local routing strategy; complex traffic network

文章编号:2095-5456(2016)03-0219-04

收稿日期:2015-11-20

基金项目:国家自然科学基金青年科学基金资助项目(61203152); 辽宁省自然科学基金资助项目(2015020037); 辽宁省教育厅杰出青年学者成长计划资助项目(LJQ2014131).

作者简介:王丹(1979-),女,辽宁沈阳人,沈阳大学副教授,博士.

中图分类号:N 941.4

文献标志码:A