动态交通分配

动态交通分配（共8篇）

动态交通分配 篇1

传统的交通规划所采用的模型主要是20世纪50年代起源于美国的“四阶段”模型。基于出行的“四阶段”模型把出行分成发生、分布、方式选择以及交通分配四个步骤,然后以交通小区为单位,用集计数据进行模拟。“四阶段”模型在以交通基础设施建设为主的城市交通规划中发挥了重要的作用。然而,随着交通需求管理政策的日益广泛应用,“四阶段”模型暴露出明显的不足。针对“四阶段”方法的局限性,交通研究人员提出了基于活动的方法,该方法认为居民一天出行的需求源于居民一天的各种活动所构成的出行链[1]。相对于基于出行的“四阶段”法,基于活动的方法具有如下优点[2]:(1)考虑了时间维因素,活动和出行决策都是动态的;(2)以活动和出行模式为研究对象而不是以单个出行为研究对象;(3)考虑各种活动-出行之间的相互联系,一次决策受过去和预期事件的影响;(4)考虑了时空约束对活动和出行的影响。

近二十年,基于活动的出行行为建模方法在国内外已做了大量的分析研究。如荷兰开发了基于往返行程的系统[3],Ben-Akiva和Bowman开发了日活动计划系统[4],Gliebe和Koppelman开发了基于效用的日时间比例参与模型[5],另外,比较典型的还有基于活动的仿真系统STARCHILD[6]、基于规则的多代理系统Albatross[7]、基于微观仿真的综合计量系统CEMDAP[8]。然而,这些研究在进行交通分配时大多忽视了出行链行为,而认为出行链中的每次出行是独立的。William等[9]提出了一个基于活动的时间相关的交通分配模型,然而该模型中路径选择行为并没有考虑到预先确定的相关活动,另外,求解算法烦琐,计算量大,不适用于实际交通网络。Maruyama等[10,11]提出了一个基于出行链的静态模型,该模型假设用户对路网信息有完全的了解,用户不能改变路径来减少整个出行链上的成本,但忽略了停驻点及停驻时间的影响。Abdelghany[12]等提出了一个基于活动/出行的仿真分配模型,模型仿真出行者如何选择路径以最小化他们的总出行成本,该模型假设出行者对路网信息有完全的了解,然而现实中,出行者对路段的出行成本只能是估计,而且不同出行者的估计值也会不同,因此本文放松出行者对整个出行链路径信息完全了解的假设,提出了一个基于出行链的随机动态交通分配模型。出行链模式由出发地点、出发时间、中间停驻点、停驻时间、目的地定义,定义的出行链输入到模型中,模型选择路径以最小化出行者整个出行链上的感知成本。针对所提出的模型,结合时间相关的K最短路算法和连续平均法,设计了一个基于仿真的迭代求解算法,最后通过一个算例验证了模型和算法的有效性。

1基于出行链的动态随机用户均衡

传统的基于出行的四阶段模型在进行交通分配时常采用用户均衡的假设,即在静态条件下用户对路网信息有完全的了解,当用户不能改变自己的出行路径而减少其出行成本时达到用户均衡状态。后来,学者放松了出行者对路网信息完全了解的假设,提出了随机用户均衡,即当达到均衡时,出行者不能通过改变自己的路径来减少他们感知的出行成本。静态模型(确定性和随机性)适用于长期的规划分析,但由于它不能描述网络中的拥挤情况,认为整个规划时期路段交通流量和OD需求是常量,显然这和实际交通情况是不相符的。如果时变的OD需求是已知的,就可以分析各个时间段的路网状况,这就导致了时间相关的用户均衡问题[12]:即在任何出发时间间隔,没有出行者能通过改变出行路径来减少他们所感知的成本。

为避免基于出行的四阶段模型的缺点,越来越多的交通规划人员开始采用基于活动的模型进行交通需求分析与预测。活动链可以描述一个人一段时间内不同活动的顺序,也可以反映一个人在空间上的活动规律。为满足相应的活动所经过的路径常称为基于出行链的路径,如图1所示,假设一个人的一天的活动顺序为:家-单位-商店-家。设p为2个连续停驻点之间的一条路径,该出行链对应的路径为:p1→p2→p4;p1→p2→p5;p1→p3→p4;p1→p3→p5。

扩展基于出行的用户均衡到出行链的情况下,可得到基于出行链的时间相关的随机动态用户均衡:即在任何出发时间间隔,没有出行者能通过改变出行路径来减少他们所感知的整个出行链上的成本。

2 模型系统结构

研究动态交通分配通常有两类方法:解析法和仿真法。解析法有严格的数学定义,对动态交通分配有很精确的描述,可以研究解的存在性、唯一性、稳定性。但由于交通系统动态性能的复杂性,对其进行精确的建模很难求解。采用仿真方法能克服解析模型的缺点,再现交通流在交通网络中运行的复杂动态特性。因此,采用仿真的方法求解基于出行链的动态随机交通分配问题。求解基于出行链的动态随机交通分配问题,本质上是求解每个发车间隔分配到各条路径的交通量,所选择的路径能满足出行者完成其相应的活动。模型系统主要分三个模块:(1)交通/活动仿真模型;(2)出行者行为模块;(3)路径处理及交通分配模块。交通/活动仿真模型用于再现交通流在交通网络中运行的动态特征,描述交通流传播及时间-空间互动关系,评价交通网络相关特性;出行者行为模块在一个效用最大化框架下,描述出行者的路径选择决策;路径处理模块用于求解符合条件的路径选择集合。

2.1 交通/活动仿真模型

根据对交通系统描述细节的程度,交通仿真模型可以分为宏观、中观、微观三种。中观交通仿真模型适用于面向交通诱导系统的仿真开发与研究,实现在较大范围内模拟各种属性的特定车辆在路网中运行的状况,所以本文采用中观交通仿真模型。

交通仿真模块主要包括路段车辆行驶模块和交叉口处车辆行驶模块。在路段上,位置相近、交通流特性相似的车辆组成一个交通单位。计算交通单元内部的车辆速度时首先计算头车和尾车的速度,然后排列在中间的车辆分别根据其与头车尾车的位置采用线性加载的计算方法来计算各自的速度。

交通单元头车速度采用单元跟进计算公式来求得[13,14]:

公式中各参数含义如下所示:uij为向j方向行进的行车单元i的头车的单元跟进速度,即交通流ij头车速度;vj0为领导行车单元的尾车的速度;vmax为路段自由流速;λi=(dij/dupper);dij为头车ij距向方向j行进的领导行车单元尾车的距离;dupper预置极限距离。

交通单元尾车速度采用速度-密度函数来计算得到[13,14]:

$v{}_{i0}=V{}_{\min }+(V{}_{\max }-V{}_{\min })\left(1-\left[\frac{{\rm K}{}_i}{{\rm K}{}_{jam}}\right]{}^{\alpha }\right){}^{\beta }$ (2)

式(2)中各参数含义如下所示:vi0为交通单元尾车的速度;ki为交通单元的交通密度;kjam为路段的阻塞密度;vmax为路段的自由流速;vmin为路段的最小流速;α、β为待标定参数。

在每一个更新阶段中,仿真器依据路网中所有路段的通行能力计算平均车头时距。平均车头时距决定车辆被允许进入路段的时间,如下所示[13,14]:

tn=tn-1+1/Q (3)

式(3)中:tn表示下一辆车进入路段的最早时间;tn-1表示上一辆车进入路段的时间;Q表示交叉口的实际通行能力。

只有当系统的仿真时间大于等于式(3)中决定的tn时,车辆被允许进入此路段;否则,车辆在节点处形成排队。系统会在每一次更新中检查路网中的所有路段所含有的车辆数,如果路段上最后一个交通单元的尾部到达了此路段的边界,车辆也不被允许进入此路段。

当车辆到达中间停驻点时,车辆暂时驶离路网一段时间(等于车辆在中间停驻点的驻停时间),这段时间该车辆对路网中其他车辆不产生影响。当仿真时钟推进到停驻时间完成时,车辆重新驶入路网。

2.2 出行者行为模型

用一个有向图G(N,A)表示交通网络,N为所有节点集合,A为所有路段集合,I为所有出发节点的集合,h为每次出行对应的出行链,H为出行者可选择的出行链集合,h∈H,出行链由一系列中间停驻点表示:Qh={n1,n2,…,ns,…},其中,Qh为出行链h对应停驻点的集合;s为停驻点序号;令τ为出发时间间隔,l为一个出行链对应的一条路径,对于出行链h相应的路径l,C${}_{t,ihl}^{\tau }$为具有出行链h在时刻τ从i出发选择路径l的实际成本,总出行成本为:C${}_{t,ihl}^{\tau }$=∑C${}_{hl,p{}_k}^{\tau }$,Chl,pk为出行链h在时刻τ从i出发选择路径l中路径pk的实际成本。

每个出行方案由出发地点、出发时间、一系列活动停驻点及目的地构成,每次活动对应一个给定的活动持续时间。在该模型里,每个出发时间间隔,出行者选择路径以最小化他们整个出行链上的感知成本。

令C${}_{a,ihl}^{\tau }$为具有出行链h在时刻τ从i出发选择路径l的感知成本。则:

C${}_{a,ihl}^{\tau }$=C${}_{t,ihl}^{\tau }$+(1/θ)ε${}_{ihl}^{\tau }$∀i,j,τ (4)

式(4)中,ε${}_{ihl}^{\tau }$为出行链出行成本相关的误差项,假设Ε(ε${}_{ihl}^{\tau }$)=0或者E(C${}_{a,ihl}^{\tau }$)=σ${}_{ihl}^{\tau }$。换句话说,也就是平均感知成本等于实际的出行成本。θ为一常数,它起到将出行成本转换成效用的作用。

出行者在出发时刻τ选择路径l的概率为:

P${}_{ihl}^{\tau }$=P(C${}_{t,ihl}^{\tau *}$≤C${}_{t,ihl}^{\tau }$,∀l)∀i,j,τ (5)

换句话说,公式(5)表示在出发时刻τ某一路径被选择的概率等于该路径的交通时间被认为是最小值的概率。

根据ε${}_{ihl}^{\tau }$所服从分布的假设不同会产生不同的随机网络配流模型。当假设ε${}_{ihl}^{\tau }$服从正态分布时,可以得到probit模型;当假设ε${}_{ihl}^{\tau }$服从Gumbel分布时,可以得到logit模型。在确定了ε${}_{ihl}^{\tau }$的分布后就可以计算出路径选择的概率,从而可以计算出路径的分配流量:

f${}_{ihl}^{\tau }$=q${}_{ij}^{\tau }$P${}_{ihl}^{\tau }$,∀i,j,τ (6)

式(6)中:

q${}_{ij}^{\tau }$:从i出发具有出行链h的出行者数量;

f${}_{ihl}^{\tau }$:具有出行链h,在τ时刻从节点i出发选择路径l的出行者数量。

2.3 路径处理模块

基于从仿真器得到的路段出行时间,路径处理模块求解路径相关特性(如路径出行时间等)。每个出行链对应多条路径,由于出行者对路径成本感知的不同,他们并不都是选择最优的路径出行,也可能选择非最优的路径出行,因此,这涉及到出行链可选路径集的确定问题。出行链可选路径集的确定分两步,第一步计算两个停驻点之间的最短路径集,第二步组合第一步得到的子路径集从而得到该出行链对应的可选路径集。在进行路径选择时,路径集中每条路径分配给特定的选择概率,路径集之外的路径不被选择。第一步中两个停驻点之间的可选路径集的求解采用K最短路算法,K路算法[15]是在Dijkstra最短路算法的基础上进一步扩展得到的,其优点在于每次的计算都能够得到不止一条的最短路,并且能够根据用户不同需求得到不同的最短路个数。为提高模型计算效率,不是在每个仿真间隔重新计算K最短路路径,而是在预先设定的较长时段进行K最短路的计算。在设定的更新间隔内,K路径的出行时间通过每个仿真间隔的所得到的当前路段时间进行更新。

3 基于仿真的迭代算法

通过一个启发式迭代仿真程序来求解模型,该算法集成了连续平均法(MSA)和基于仿真的随机网络卸载方法。

算法主要步骤如下:

步骤1:初始化:设置迭代计数器n=1。基于初始的路段和节点出行特性,为每个出行方案找到一个初始的可行路径集,分配基于活动的初始需求到一个初始的可行路径集上。相应地,初始解由f${}_{ihl}^{\tau ,0}$表示。

步骤2:在给定路径分配模式下,运行交通/活动仿真器得到路段出行时间等相关信息。

步骤3:根据从仿真器得到的路段出行时间,调用路径处理模块分别计算每个出行方案的前K条最短路径集合。同时计算集合中每条路径的总出行成本。

步骤4:根据上一步计算的最短费用路径集合,计算每个选择肢的效用,基于多项logit模型计算每条路径的选择概率,得到每个分配间隔路段的辅助车辆数y${}_{ihl}^{\tau ,n+1}$。

步骤5:使用连续平均法更新路段流量:

$f{}_{ihl}^{\tau ,n+1}=f{}_{ihl}^{\tau ,n}+\frac{1}{n}(y{}_{ihl}^{\tau ,n}-f{}_{ihl}^{\tau ,n})$。

步骤6:判断f${}_{ihl}^{\tau ,n+1}$与f${}_{ihl}^{\tau ,n}$差值:$\left|f{}_{ihl}^{\tau ,n+1}-f{}_{ihl}^{\tau ,n}\right|\le \epsilon$,满足,停止循环,否则,执行步骤2。

4 数值算例

出行方案由每个出行者的出发时间、出发地点、一系列进行活动的中间停驻点、最终目的地构成。每个活动对应一个活动持续时间。在仿真实验中,对于每个出行者,每个活动持续时间是外生的并预先确定的。

出发节点为1和4,目的地节点为2和3,中间停驻点为6和10。

假设平均发车流率为2 000辆/小时,即平均每小时2 000辆车从节点1出发前往目的地2,有25%的出行者要在节点6处驻停5 min,另75%出行者直接前往目的地2;2 000出行者从节点1出发直接前往目的地3;2 000出行者从节点4前往节点3,25%出行者在节点10驻停5 min,其余75%出行者直接前往目的地3;2 000出行者从节点4直接前往节点2。

传统的基于出行的方法常忽略中间停驻点的行为或者认为出行链中的每次出行是独立的。为和基于出行链的方法对比起见,以出行链方法、传统基于出行的方法分别求出平均出行时间如表1所示。在以基于出行方法求解时,在进行交通分配时忽略中间停驻点的情况,即在进行交通分配时,仅考虑出行链中最终目的地对交通分配解结果的影响。举例说明,如果一个人从家出发,先送孩子去学校,然后前往工作单位,在分配时认为是一个从家到单位的单一出行。

分别以基于出行链方法和基于出行方法求出,平均发车流率为1 000、1 500、2 000、2 500辆/小时出行者的平均出行时间。从表1可以看出,当忽略停驻点仅考虑出行链中的最终目的地时,所求平均出行时间小于实际平均出行时间,这是因为,当忽略出行链中的中间停驻点时,减少了相应的总出行,路段变得更通畅。

5 结语

传统的基于出行的交通分配模型在进行交通分配时忽略了出行链中各出行之间的相互关系。本文提出的基于出行的动态随机交通分配模型考虑了出行链中各出行之间的相互关系,能更好的反映出行者的实际选择行为。基于所开发的仿真器,结合K最短路算法和MSA算法,设计了模型的求解算法,并通过算例比较了传统的基于出行的分配模型忽略停驻点时对分配结果的影响。

动态交通分配 篇2

3.1动态模型的约束条件

本模型服从先进先出规则，设一辆在ti时段进入路段a。路段a上的行驶时间近似认为ta（ea（ti））（因为行驶时间ta（q）是随q的变化而变化，若ti时段很小，则可以认为a上的交通量ea（ti）为不变的）[5]，则在ti+ta（ea（ti））时刻离开a路段。为简便起见，若取每个小时为单位时间（或相等时间），则

这里假设第ti时段的交通流量a在本时段内不流出，即

说明ti时段a路段上的流出量必为前面某时段ti的流入量。

在ti时段末，路段a上的交通流量不仅与前一时段的交通量有关，还与本时段的流出量有关，应为

即ti时段a路段上现有交通量等于前一段交通量加上该时段交通分配量减去该时段交通流出量，设ea（0）=0。

考虑任一O-D对r-d，在起点r，ti时段的交通分配量，应为该节点的生成量与其它节点经过该节点流向s的交通量之和，即

3.2 动态模型的目标函数

为简便起见将所考虑的时段（0，T）分为m个相等的时期t1，t2，t3，……tm，因为每个时段相等，可将小时段记为1，2，……，m，则第i个时段的.均衡模型为

3.3 模型的求解方法

Frank-Wolfe算法用线性回归逐步逼近非线性规划的方法来求解UE模型，该方法是迭代算法[6]。此方法的前提条件是模型的约束条件必须都是线性的。均衡分配法的步骤可归纳如下：

Step0：初始化。

按照织 tao=ta（0），va 实行一次0-1分配，得到{xa1}，令n=1

Stepl：更新时间

tan=ta（xan）.va

Step2：找方向。

按照{tan}实行一次0-1分配得到一组辅助变流{yan}：

Step3：确定步长

求下式∑a（yan-xan）ta（xan+λ（yan-xan））=0；

0QλQ1

Step4： 移动。

Xan1=Xan+λa（yan-xan），Va.

Step5 ：收敛检验。如果{Xan1}已满足规定的收敛准则，停止计算。

{Xn+1}即为解，否则令n=n+1. 返回Stepl 1.

3.4 模型的求解步骤

为了求解本模型，关键就是求解规划问题，与UE问题没有本质区别，也是用求解非线性规划的方法即可解决。求解本模型步骤如下：

步骤0 首先将所考虑的大段[0，T]分为m个相同的单位时段1，2，…M。已知每个小段的O-D：q～（t1），V k， r， sea（0）=0：

步骤1 利用一种非线性规划的方法（F-W算法）求解规划问题（p1）“

步骤2 若求出了（p1）的最优解，由上式就可算出ea（t1-1）及oa（t1）；

步骤3 按非线性规划方法（F-W算法）来求解规划问题（p1）直至（pm）为止；

显然，若能寻找一种有效的方法来求解非线性规划问题（p1）（i=1，2，....，m），则本模型就有有效的求解方法，这属于非线性规划问题求解方法的研究。

4 结论

本文动态模型考虑了路段上的原有交通量，对实时的路段交通量配流进行了优化，路网得到了较充分的利用，比静态的交通量分配的路径诱导结果优势明显。

参考文献：

[1]杨兆升.城市交通流诱导系统理论与模型[M].北京：人民交通出版社，2000.

[2]黄海军.城市交通网络平衡分析理论与实践[M].北京：人民交通出版社，1994.

[3]陆化普，史其信，殷亚峰.动态交通分配模型理论的回顾与展望[J].公路交通科技，1996，13（1）：78-81

[4]杨清华，贺国光.对动态交通分配的反思[J].系统工程，2000，97（1）：49-52.

[5]袁振洲，李巍屹，刘海东.动态交通分配理论与方法研究简介[J].综合运输，2008（9）：23-25.

动态交通分配 篇3

交通分配是城市交通规划的一个重要环节, 也是OD量推算的基础。所谓交通分配就是把各种出行方式的空间OD量分配到具体的交通网路上, 通过交通分配所得的路段、交叉口交通量资料是检验道路网络规划是否合理的主要依据之一[1]。

国际上通常把交通分配方法分为平衡分配模型和非平衡分配模型两大类, 并以Wardrop第1、2原理为划分依据, 提出了交通分配的时间比原则、等时间原则和总行驶时间最小3种分配原则的平衡模型。从理论上讲, 平衡模型较非平衡模型具有结构严谨, 思路明确, 结果合理, 适用于宏观研究的等特点。但是由于变量较多、维数太大以及约束条件太多, 使得对这类模型的求解显得较为困难, 从而影响实际的使用。

增量分配法是一种近似的平衡分配法。该方法具有简单可行, 有比较成熟的商用软件可供使用, 精确度可以根据N的大小来调整的特点, 容易在计算机上实现, 因而在实际的道路网交通分配中经常得以应用[2]。在以往的增量分配算法中, 常用的最优路径求解算法有标号法、Floyd法和Moorepape算法。本文对基本蚁群算法的信息素更新方程和启发信息变量ηij的取值方法进行适当的改进, 即考虑到实际路网中路段的通行时间受到交通量影响, 用车辆在路段的行驶时间tij代替原来的路段长度dij对信息素进行更新, 并将djE这一新的参数引入到启发信息ηij中以加强搜索方向性。后将经过适当改进的蚁群算法引入增量分配法中。

1蚁群算法

1.1蚁群算法基本原理

蚁群算法是由DorigoM、ManiezzoV和Colorni等于1991年首先提出来的, 它是对自然界蚂蚁的寻找食物的方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中, 能够在它所经过的路径上留下一种称之为外激素 (pheromone) 的物质进行信息传递, 而且蚂蚁在运动过程中能够感知这种物质, 并以此指导自己的运动方向, 它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素, 当它们碰到一个还没有走过的路口时, 就随机地挑选一条路径前行, 与此同时释放出与路径长度有关的信息素。路径越长, 释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候, 选择激素浓度较高路径概率就会相对较大, 这样形成一个正反馈, 最优路径上的激素的浓度越来越大, 而其它的路径上激素浓度却会随着时间的流逝而消减, 最终整个蚁群会找出最优路径。

1.2基本蚁群算法

采用基本蚁群算法求解最优路径的具体步骤为:

(1) 算法参数的初始化。迭代步数nc=0;τij (t) 为t时刻连接节点和路段上的信息素浓度, 初始时刻各条路段上的信息素浓度相等, τij (0) =C (常数) ;ηij为路段 (i, j) 的启发信息, 该启发信息是由所要求解的问题给出的, 在本问题中, 取。

(2) 将m只蚂蚁放置于出发点, 并将出发点置于当前解集中;对于每个蚂蚁k, 按概率Pkij (t) 移至下一个顶点j;将顶点j置于当前解集。

式 (1) 中, α表示信息素的相对重要性 (α≥0) ;β表示启发信息的相对重要性 (β≥0) 。

(3) 计算各蚂蚁的目标函数值Zk;记录当前最好解;

(4) 按信息素更新方程修改各路段上的信息素浓度值。路段 (i, j) 在t时刻的信息素更新方程为:

式 (2) 中:ρ表示信息素在路段 (i, j) 上的保留率, 则1-ρ表示信息素的挥发率;Δτkij (t-1) 为t-1时刻蚂蚁k于路段 (i, j) 上留下的单位长度轨迹的信息素数量, 蚁群算法中Δτkij (t-1) 有3种不同的取法, 可形成3种不同的类型的蚁群算法, 即蚁环模型 (Ant-Cycle) 、蚁密模型 (Ant-Density) 、蚁量模型 (Ant-Quantity) , 由于在蚁环模型和蚁密模型中蚂蚁释放的信息素浓度与路段 (i, j) 长度dij无关, 因此本文采用如下蚁量模型计算蚂蚁在路段 (i, j) 释放的信息素的浓度。Ant-Quantity模型:

式 (3) 中, Q为体现蚂蚁所留信息素浓度的一个常数。

(5) 在道路网络上的各路段 (i, j) , 置Δτkij (t) =0;nc=nc+1。

(6) 若n<预定的迭代次数且无退化行为 (即找到的都是相同解) , 则转步骤 (2) 。

(7) 输出所求得的最优路径。

2改进的蚁群算法[4,5]

当进行一次交通分配迭代后, 在道路网络中, 各路段的交通量会发生变化。此时, 路段 (i, j) 的路权评价参数也应该发生变化, 即由原来的路段 (i, j) 长度dij转为不同类型的车辆在路段 (i, j) 上的平均行驶时间tij。这是由于当路段上的交通量发生变化时, 有些路段长度比较短分配到该路段的交通量比较多, 会导致行驶在该路段上的车辆走行时间的增加, 而其它路段虽然比较长, 但由于车流量较小, 车辆在路段上的走行时间可能小于长度较短的路段, 因此有必要对原来的蚁群算法进行改进以适应这种变化。

对于车辆在路段上走行时间函数的研究, 被广泛应用的是由美国道路局 (BureauofPublicRoad, BPR) 开发的函数, 被称为BPR函数, 其形式为:

式 (4) 中, Cij为路段 (i, j) 的通行能力;α, β为参数;t0ij为车辆在路段 (i, j) 上的自由走行时间。

对上述基本蚁群算法进行改进, 主要是对信息素更新方程中的Δτkij (t) 进行改进, 算法的具体步骤

将公式 (4) 代入上式可得公式 (6) ,

同时, 在基本蚁群算法中, 路段 (i, j) 的启发信息ηij=1dij, 只反映当前节点和所连接节点的距离关系, 并没有反映下一节点和终点的距离关系, 即失去了选择下一节点趋于终点方向的方向性, 在此引入一个新的参数djE, 即节点j与终点 (食物源) E的直线距离, 令ηij=1dij+djE, 利用新的启发信息ηij能够加强搜索的方向性, 更快地找到最优解。

3基于改进蚁群算法的增量分配模型

结合改进的蚁群算法和原来的增量交通分配模型得到的基于改进蚁群算法的增量交通分配算法。该算法的具体步骤为:

Step 0:初始化。将每组OD交通量按一定的分配率λ分成N份, 每份为qnrs=qrs·λ。同时令n=1, q0ij=0, (i, j) ;同时对基本蚁群算法中的各个参数进行初始化。分配次数N与每次OD量分配率λ如表1所示:

Step 1:运用基本蚁群算法求出每一OD点对间的最短路径。在所求得的最短路径上加载交通量qnrs, 完成第一次增量分配计算, n=2。

Step 2:更新道路网络中各个路段的走行时间。tnij=tij (qn-1ij) , (i, j) , 此时采用改进蚁群算法计算各个OD点对间的最短路径。

Step 3:将交通量qnrs分配到道路网络中各个路段 (i, j) 上, 这样得到一组附加交通量enij。

Step 4:路段 (i, j) 上交通量累加, 即令qnij=qn-1ij+enij, (i, j) 。

Step 5:根据迭代次数n判断是否结束计算。如果n=N, 则停止计算, 当前路网的各路段上的交通量即为该算法交通分配的结果;如果n<N, 则令n=n+1, 返回Step2。

4算例分析

以图1所示的道路网络图为例, 道路网上节点间路段包含双向路段和单向路段。在双向路段上, 不同方向的通行能力均相等, 假设所有路段的通行能力大小都是1 750pcu/h, 路段的长度和车辆在路段上的自由行驶时间如表2所示。假设两个OD点对1—8和3—5的交通量分别为q18=2 625pcu/h, q35=3 500pcu/h, 现用上述交通分配方法对两OD点对的交通量进行分配得出各个路段上的交通量大小, 具体的求解过程如下。

在本算例中我们将OD交通量分成四份, 分配率λ分别为50%、30%、20%。蚁群算法参数的选取为:蚂蚁数量m=20, α=1, β=1, ρ=0.5, Q=1, BPR函数中取α=β=2。

先求1—8的OD点对, 将蚂蚁放置在节点1 (蚁穴) , 蚂蚁会通过不同的路径到达节点8 (食物源) , 可能通过的路径有:1—5—7—8;1—2—4—7—8;1—2—3—8;1—2—3—6—7—8;1—2—4—5—7—8;1—5—7—9—8;1—2—4—7—9—8;1—2—3—6—7—9—8。在所有通过的这些路径中, 通过基本蚁群算法的信息素更新方程, 最优路径的信息素将会得到不断地增强, 最终大多数蚂蚁都会选择该路径, 即求得最短路径。节点1—8的最短路径为1—2—4—7—8。同样可求得节点3—5的最短路径为3—4—5。将第一份交通量加载到所求得的最短路径上可得到各个路段分配的交通量如表3所示;此时, 由于路段上的交通量发生了变化, 车辆在路段上的行驶时间发生改变, 采用BPR函数对路段的行驶时间进行更新, 如表4所示。

进行第二次迭代, 将蚂蚁放置于节点1 (蚁穴) , 蚂蚁会通过不同的路径行走至节点8 (食物源) , 在所有路径中, 其中有一条路径上的信息素通过改进的信息素更新方程会得到不断地加强, 最终得出最优路径。同理可求得其他OD点对的最优路径;后将第二份交通量加载到新的最优路径上, 并对两次分配得到的各路段交通量进行累加求和。最后, 再对各路段的平均行驶时间进行修改, 并跟新变量Δτ${}_{ij}^k$ (t) , 后采用改进的蚁群算法进行最后一轮迭代得到新的最优路径, 对加载到新最优路径上的交通量进行累加求和得到最终的交通分配结果, 如表5所示。

若在道路网络中只采用基本蚁群算法求解最短路径, 后在最短路径上加载交通量, 由于没有考虑到车辆在路段上的行驶时间受到交通量大小的影响, 距离最短的路径不一定是最优路径, 则分配所得的结果不符合实际。

5 结语

本文尝试用蚁群算法来求解交通分配中的最优路径, 提出基于改进蚁群算法的增量分配模型, 得出如下结论:

(1) 由于在实际道路网络中, 路段的通行时间受到交通量影响, 本文对基本蚁群算法的信息素更新方程和启发信息进行适当的改进, 使得交通分配的结果能够更符合实际情况。

(2) 增量分配算法容易用计算机实现, 同时具有实用性, 本文将改进的蚁群算法融入其中, 只要将蚁群算法的代码移植到增量分配法的代码中, 也容易在计算机上得到实现。

(3) 本文只是对蚁群算法的信息素更新方程和启发信息ηij进行改进, 使其能够适合道路网络路权参数的变化, 要提高算法的效率还有待于对基本的蚁群算法进行进一步的改进。

摘要：将蚁群算法用于交通分配中最优路径求解, 考虑到实际路网中路段的通行时间受到交通量的影响, 提出了一种改进的蚁群算法。算法对基本蚁群算法的信息素更新方程和启发信息进行适当改进, 即用车辆在路段的行驶时间代替路段长度对信息素进行更新, 并在启发信息中引入新的参数以加强搜索方向性。将改进后的蚁群算法结合增量分配法进行应用。用一个算例对算法的有效性进行验证。

关键词：交通分配,蚁群算法,增量分配法,道路网络

参考文献

[1]王炜, 过秀成.交通工程学.南京:东南大学出版社, 2000:200

[2]陆化普.交通规划理论与方法 (第二版) .北京:清华大学出版社, 2006:174—175

[3]Dorigo M, Maniezzo V, Colorni A.Ant system:optimization by a colo-ny of cooperating agent.IEEE Transaction on Systems, Man, and Cy-bernetics, 1996;26 (1) :29—41

[4]王勇, 雷黎, 纪寿文, 等.基于改进蚁群算法的交通分配研究.公路交通技术, 2007;3:159—161

[5]黄贵玲, 高西全, 靳松杰, 等.基于蚁群算法的最短路径问题的研究与运用.计算机工程与运用, 2007;43 (13) :233—235

[6]靳凯文, 李春葆, 秦前清.基于蚁群算法的最短路径搜索方法研究.公路交通科技, 2006;23 (3) :128—130

[7]李文勇, 王炜, 陈学武.公交出行路径蚂蚁算法.交通运输工程学报, 2004;4 (4) :102—105

动态交通分配 篇4

GPON系统是基于GSR (Gigabit Service Requirements) 制定的, GSR规定了GPON所要达到的关键指标, 是系统设计的依据, 它确保GPON比其它的PON能更加贴近实际需求。GPON系统是由ONU、OLT和ODN组成, OLT位于局端, 是整个GPON系统的核心部件, 向上提供广域网接口, 具有集中带宽分配、控制光分配网 (ODN) 、实时监控、运行维护管理光网络系统的功能;ONU放在用户侧, 为用户提供10/100Base T、T1/E1和DS-3等应用接口, 适配功能在具体实现中可以集成于ONU中;ODN是一个连接OLT和ONU的光无源设备, 其功能是分发下行数据和集中上行数据。GPON中下行数据采用广播方式发送, 上行数据采用基于统计复用的时分多址方式接入方式。

2 多等级服务动态检测GPON动态带宽分配算法

2.1 宽带动态检测算法

假设在GPON系统中共有N个ONU, 在一个周期时间T内可用带宽为Wti, 经过时间k后, 传输的总宽带为Wt (k) , 则有:

根据定义1, 式 (2) 具有以下性质:

性质1:若带宽以尺度因子进行分解或伸缩, 则ΔW (k) 保持不变。

证明:设ΔW&apos; (k) 为以尺度因子s进行伸缩后的当前平均动态改变宽度, 因此:

同理可以证明以尺度因子s进行分解后ΔW (k) 保持不变。

性质2:由于ONU的对象不同, 从而对带宽的需求也就不同。假设在时间k时, ONU对带宽的需求发生改变, 则改变后GPON系统分给ONU带宽的剩余 (缺少) 部分可以用新的带宽信息进行补充, 此时, 当前平均动态改变宽度ΔW (k) 发生变化。

证明:设ΔW&apos; (k) 为包含ONU带宽需求改变的当前平均动态改变宽度, 则有:

因此, ΔW (k) 发生变化。

若在时间k时, ONU的带宽需求发生变化, 从带宽动态分配的角度分析, 也就是将剩余 (缺少) 带宽部分调制到原有带宽上, 即为:

其中a为调制因子, 且a≥1。根据式 (2) 可得:

其中Ec (k) 为时间k内, ONU需求带宽改变的总和。根据式 (5) 可知, 在动态宽带分配中, 只需要对当前周期需求带宽改变总和进行补偿, 且补偿变量为blaΔP (k) 就可以实现对原有带宽的调制。从另一个角度分析, blaΔP (k) 可以作为评判ONU带宽需求改变的判据。同样根据式 (5) 可知, blaΔP (k) 与ΔW&apos;p (k) 具有相关性, 因此, 可以利用blaΔP (k) 与ΔW&apos;p (k) 的互相关函数来表达ONU带宽需求的改变。假设相互关联函数为,

根据定义可知, ΔP (k) 、ΔW (k) 相互独立, 从而E[ΔP (k) ΔW (k) ]=0, 基于此, 可以根据a E[ΔP (k) ) 2]的大小判断ONU需求带宽改变的程度。假设在GPON动态宽带检测中, 系统的误差概率为a, 设定ONU需求带宽改变阈值a E[ΔP (k) ) 2]/2, 则有:

2.2 多等级服务动态检测GPON动态带宽分配算法

多等级服务就是根据各种业务 (语音、E-mail等) 需求的不同将接入业务分为高、中、低三个等级, 并且由OLT统一对三个等级进行带宽分配, 在初始时刻高等级业务分配为固定带宽, 中、低等级业务分别分配为确保带宽和普通带宽。在本文提出的多等级服务动态检测GPON动态带宽分配算法中结合了多等级服务原则和当前平均动态改变宽度的宽带动态检测, 从而带宽随着ONU需求而发生改变, 改善了GPON系统带宽分配不公平的问题, 同时, 通过动态带宽需求检测可以降低丢包率。具体算法步骤如下:

步骤1初始化, 假设GPON系统中共有N个ONU, 总宽带为Wj (k) , j=1, 2, 3…m为第j个高等级需求在时间k时的固定带宽, m为高等级需求的个数, Wi (k) , i=1, 2, 3…n为第i个中等级需求在时间k时的普通带宽, 则低等级需求的普通带宽可以表示如下:

式中Wl (k) 为第l个低等级需求的普通带宽, L为低等级需求的个数。

步骤2多等级服务带宽分配, 原则:确保高等级业务带宽的需求, 根据宽带动态检测算法式 (6) 、 (7) 判断ONU业务等级的变化, 根据式 (5) 对剩余带宽进行动态分配, 以响应ONU业务等级变化而需要的带宽改变。若ONU业务等级发生改变剩余带宽为ΔP (k) , 则Wj (k+1) , j=1, 2, 3…m为第j个高等级需求在时间k+1时的固定带宽可表示如下:

则Wi (k+1) , i=1, 2, 3…n为第i个中等级需求在时间k+1时的普通带宽可表示如下:

步骤3循环判断动态带宽分配, 根据式 (9) , (10) , 确定了下个周期的高、中等级业务带宽, 根据宽带动态检测算法检测多等级业务带宽需求, 若不发生带宽需求改变, 则保持式 (8) 、 (9) 、 (10) 对带宽的分配, 若发生需求改变则重新按照步骤2进行动态分配。

3 结论

本文针对GPON网络中带宽分配及传输延时的问题, 提出了一种多等级服务动态检测的GPON动态带宽分配算法。通过理论分析及推导, 给出了一种当前平均动态改变宽度的几何宽度变量, 结合面向多等级服务原则, 得到了基于当前平均动态改变宽度的多等级服务动态检测GPON动态带宽分配算法。

摘要：针对如何实现吉比特无源光网络 (GPON) 带宽分配公平性, 降低网络丢包率及传输延时的问题, 开展了多等级服务动态检测的GPON动态带宽分配算法研究。首先分析了GPON工作基本原理, 提出了一种针对带宽几何宽度的变量——当前平均动态改变宽度, 基于该变量推导了当前平均动态改变宽度的宽带动态检测算法, 其次将此算法与面向多等级服务原则相结合, 得到了基于当前平均动态改变宽度的多等级服务动态检测GPON动态带宽分配算法。

如何运用动态规划分配供货时间 篇5

动态规划是运筹学的一个分支, 它是解决多阶段决策过程最优化的一种数学方法。其中资源分配问题应用尤其广泛, 而问题中分配资源不分先后, 由已有的时间安排问题, 现举一例如下:某公司还有7天就要进行4种货物的供应, 想尽可能有效安排这7天时间, 每种货物至少1天准备, 而假设每天只准备一种货物, 每种货物准备时间不同获得利润如表1, 如何安排时间获得最高总利润?

一般动态规划解决问题都假设同时交货, 实际上交货时间是有先后的, 这又应该怎么解决呢?

2 实际的供货问题

供货时间安排如下:A在10日上午;B在12日上午;C在13日下午;D在15日上午。由于种种原因, 该公司在7日才开始准备。因为时间有限, 不可能每种货物都达到最高利润。通常来说上午供货后, 下午还是可以准备其他货物的, 为了研究方便我们认为准备一种货物只占去半天时间, 而时间是紧迫的, 所以将时间以半天为单位, 此处只为说明问题, 实际可以将一天分成很多份, 处理方法一样。分配不同时间时获得的利润如表2所示, 问如何安排各种货物的准备时间, 达到总利润最高 (即最满意)

续 表

一般来说, 准备时间越长利润越高, 空白的表格是因为不会发生此种情况, 故不用填写相应数据, 解释如下:

每种货物可以在供货前任何一天进行准备, 但实际上多数人都会尽量将准备时间靠近供货时间。比如D货, 若只有一天时间, 多数人会安排在14日, 而不会安排在7日, 原因一是间隔久了, 容易忘记;原因二是会占用前面货物的准备时间, 所以不合算, 这点对于该问题的研究很重要。表3中将7日上午定为序号1, 半天为一个单位进行标识, A、B、C、D分别在7、11、14、17上。因为A第一个供应, 所以只有7～9日三天时间, 共有6个半天;B还要加上10日下午和11日一天, 所以共有9个半天;C在此基础上还要加上12日下午和13日上午, 共有11个半天;D则不同, 14日全天都只会准备这一种, 共有13个半天。从以上分析中我们可以知道:1～6可能会进行A、B、C、D的准备;8～10进行B、C、D的准备;12～13会进行C、D准备;而15～16只会准备D, 由于时间比较紧迫, 最后不会有剩余。

该问题明显对4种货物的时间分配有先后顺序, 即不是同时的, 所以多阶段决策分配的顺序组合就不能任意排列。D是最后一个, 理论上将涉及资源时间最长的一个, 其次为C、B、A。资源总数为13个半天, 后面的备货可能占用前面的时间, 而前面的准备不能占用后面的时间, 故而我们先分配D, 再将分配的天数从13中去除, 剩下的时间才一定是包含C、B、A, 以次类推下去, 下一个分配的是C……这么处理需要重要的前提:时间比较紧迫;每种货物都尽量靠近各自的考试时间, 我们前面已经提到, 符合实际情况。所以该问题的分配顺序一定是D、C、B、A。

3 问题求解

求解步骤:

①N=4, k=1, 2, 3, 4, 依次为D、C、B、A (多阶段决策问题求解是逆序递推) ;

②Sk——k阶段初剩余的天数 (半天) ;

③xk——分配给k种货物的天数;

④状态转移方程Sk+1=Sk-xk;

⑤权函数wk为表1中利润;

⑥递推方程

undefined

k=4 Aundefined

中间过程省略掉, 读者可以自己完成!

k=1 D S1=13, 0≤S2-x2≤11

4 结论

该公司最后的时间安排应为:A——1.5天, B——1.5天, C——2天, D——1.5天。考虑实际情况时, 具体的安排不唯一, 这里列举一种方案:7日、9日下午准备A;8日、11日下午准备B;9日上午、10日下午、11日上午、13日上午准备C;12日下午、14日准备D。

参考文献

[1]郭耀煌, 李军.管理运筹学[M].西安:西安交通大学出版社, 2001:206.209.

动态交通分配 篇6

在优化网络中常常会发现这样的问题, 由于用户分布不平衡, 用户群的实际通信行为存在差异性, 导致实际话务分布不均。另外, 由于某些原因也可能使话务量较低小区的话务量突然增加, 甚至发生拥塞, 而此时其它小区又处于闲置状态。从日常的话务统计来分析, 不同类型的小区之间的话务函数存在着明显的“负相关性”, 例如在以天为周期的变化上, 写字楼区域的话务白天高, 晚上低, 而住宅则是白天低, 晚上高。如何改善网络拥塞, 调节话务的“负相关性”, 同时又提高设备利用率是要我们急需解决的问题。这就需要在优化网络时用各种方法均衡小区话务, 保证网络指标的同时, 使网络资源得到充分的利用, 获得最佳经济效益。由于用光纤直放站传送移动通信射频的技术成熟可靠、直放站集中监控系统已基本建成并逐渐完善, 自建光纤传输网逐渐完备, 目前实施无线资源动态调配的条件己经成熟。

2 动态网络资源分配系统实现原理

无线网络资源动态配置与优化系统的主要功能是将基站信号经过光电转换, 将射频信号转成光信号, 经光纤传输到远端 (资源需求点) , 经远端设备放大后将基站信号发射到所需覆盖的区域, 从而达到实现吸收远端话务的功能。

该系统主要能实现不同基站不同小区的资源调整。当某基站三扇区都拥塞时, 可引外围基站较闲小区设备资源, 在外围闲小区安装光纤直放站将无线信号引至话务拥塞区域。当热点区域出现话务拥塞时, 通过更换ET电路, 改变外围闲小区的属性来调整闲小区无线信号, 经光纤直放站传送到拥塞小区。拥塞时间过后, 再通过直放站控制系统将其关闭, 从而实现远端网络资源的调配。

3 系统现网运行效果评估

鹰潭师范校园附近白天话务量不高, 但由于移动通信市场发展, 对学校学生采取了优惠政策, 晚上21:00以后, 校园区域的话务量突然升高, 拥塞次数高达1000以上, 至23:00后话务高峰才会逐渐回落, 造成大量用户投诉。现选取该站点进行现网试运行。

3.1 鹰潭师范基站实施方案

3.1.1 前期准备

工作内容包括可用频点选择、施主基站选择。

可用频点选择目的是为鹰潭师范基站提供不存在频率干扰的载频。方法是:首先对校站周边基站使用的控制载频, 进行调查。经查, 它们的频点号为:67, 5, 11, 13, 19, 70, 15, 46/28, 78, 9, 33, 36, 23, 39, 48, 30, 41/88, 51, 57, 61, 53, 59, 65, 94等。显然这些频点以及它们的邻频, 都不宜作为输出频点。于是规划EGSM频点:1023, 1015, 1003, 1001, 1007, 1011, 1005, 1009, 1013, 10017。

通过统计分析, 每天晚上21:00-23:00, 学生活动较频繁, 鹰潭师范1/2小区拥塞次数分别达到270次/小时和256次/小时, 且鹰潭师范三个小区都是8/8/8的配置, 扩容能力有限, 故我们选取在基站处附近安装该系统。而鹰潭体育馆基站 (平时体育活动很少) , 存有大量空闲载频。为此, 选鹰潭体育馆1小区, 21:00至次日01:00向鹰潭师范1/2提供无限资源支持以提高它的网络容量。

3.1.2 工程实施

安装与调试工程包括主设备安装、天线安装、无源器件安装、电源等所有部件的安装, 并应按照中国移动通信工程施工标准进行施工。接地必须严格按照标准, 保证施工质量和防雷要求;电源设备安装应依照就近原则, 并采用经业主同意的标准电源。安装完成后, 还需进行测试, 以表明成效。

3.1.3 后续优化

本阶段的主要工作是调试新增小区和附近相关小区的参数, 强化动态网络资源分配系统的作用。

经过反复调试, 我们对以下参数做了修改:

(1) 将参数QUA (小区禁止限制) 和BAR (小区接入禁止) 打开, 禁止小区选择、小区重选、位置更新, 不让手机直接选到该小区, 不做鹰潭体育馆白天覆盖区域的邻区;

(2) 将功率降低, 防止近端手机小区频繁重选;同时通过直放站补偿降低的功率, 使远端发射功率与周边基站功率一致, 保证远端手机用户能正常切换进来, 也避免了小区频繁重选现象的发生;

(3) 将师范1到体育馆1的PMRG设为4, 师范2到体育馆1的PMRG设为6, 且打开伞状切换, 师范1到体育馆1AUCL值为-80, 师范2到体育馆1AUCL为-75, 体育馆1返回师范2、1的PMRG值为10, 便于师范的1/2两个小区的用户切换至体育馆1小区;

(4) 重新设置DRT (定向重试门限值) , 师范1到体育馆1的DRT值为-85, 其他的都设为-80。

3.2 方案实施效果评估

(1) 方案实施前后每天忙时 (21:00—24:00) 话务量分布对比情况如下图所示:

5月26日在鹰潭师范2小区新增了一套直放站系统后, 鹰潭师范1/2小区话务量明显下降, 而鹰潭体育馆1小区话务量明显升高。鹰潭师范1/2和鹰潭体育馆1小区总话务量之和在5月26日前后也明显升高。这说明鹰潭体育馆1小区有效吸收鹰潭师范1/2小区覆盖校园方向的拥塞话务量。使鹰潭师范1/2小区话务负荷减少, 而鹰潭体育馆1小区的设备利用率得到提高。

(2) 方案实施前后每天忙时 (21:00—24:00) 拥塞次数分布对比情况如下图所示。

由图5看出, 5月26日后鹰潭师范1/2小区拥塞次数随话务量的降低而下降, 小区拥塞现象得到极大的改善。同时, 鹰潭体育馆1小区吸收鹰潭师范1/2小区方向话务量后, 也没有拥塞现象出现。这说明在该区域闲小区有效分担了忙小区的话务量, 话务拥塞情况减少, 提高了此区域客户的满意度。

(3) 方案实施前后每天忙时 (21:00—24:00) 无线利用率分布对比情况如下图所示

由图6看出, 5月26日后鹰潭师范1/2小区无线利用率明显下降, 同时, 鹰潭体育馆1小区吸收鹰潭师范1/2小区方向话务量后, 无线利用率大幅提高。这不仅有效的解决了鹰潭师范1/2小区高拥塞的现象, 同时也充分发挥了体育馆1小区的闲置资源, 提高了设备利用率。

图4、图5、图6充分说明, 安装该系统后, 鹰潭师范1/2小区拥塞严重的现象得到改善, 并提高了鹰潭体育馆1小区的利用率。

3.3 方案投资对比

为解决单一基站拥塞问题, 使用了一套动态网络资源分配系统, 新建一套直放站设备, 总共约价值1万元人民币。如果用常规方法新加一个基站机柜, 若干载频, 约合人民币24万元。投资一套该系统, 可节省约人民币23万元。

4 结论

该系统经过一个阶段的现网成功运行, 可得出以下结论:

(1) 该系统对解决话务拥塞问题是可行的。经过详细的现网调查和合理规划, 可将移动通信网中的闲置资源引人繁忙区域, 且对无线网络质量没有显著的负面影响。

(2) 该系统可根据预想的时间动态的调配网络资源, 大大提高了网络优化的工作效率。

(3) 该系统能够完成移动通信网中不同站不同小区间的网络资源调整, 大大降低了网络优化的成本和工程建设投资。

经过现网验证, 与其他网络优化技术相比, 该系统是高性价比、动态的网络优化技术。这为解决目前GSM移动通信网的话务拥塞问题提供了较优的解决方案。该系统通过对局部热点区域的成功应用, 可进一步在全网推行, 针对全网各种话务热点区域, 提出整体系统方案, 可将移动通信无线网络打造成资源灵活分配的弹性网络。

摘要：随着移动通信业的发展, 运营企业之间竞争程度的提升, 话务拥塞现象越发突出, 影响了网络的正常运行和用户对移动服务的满意度。本文提出了利用动态网络资源分配的方法来解决部分拥塞小区话务函数“负相关性”的问题, 并具体阐述其实现的全过程。

动态交通分配 篇7

关键词：分类挖掘,资源动态分配,模型,算法

对于整个工程项目来说, 资源的合理分配是非常重要的一个环节。传统的分配方法是一种静态分配, 在一些情况下可能会出现因资源分配不合理而引起的严重损失现象。因此, 要想实现工程项目资源的合理分配, 必须在分类挖掘的基础上, 建立动态型的分配模型。在对基于分类挖掘的资源动态分配模型以及基于分类挖掘的资源动态分配算法这两个问题进行分析之前, 我们先来了解一下资源动态分配的必要性。

1 资源动态分配的必要性

从某种程度上来说, 资源动态分配的必要性主要是相对于传统的静态分配无法满足现代社会的需求而言的。传统的静态资源分配, 根本无法根据请求任务的特征及其动态变化来灵活地分配资源, 除此之外, 当有用户的任务请求或者是资源加入与退出现象时, 还无法实现资源分配的自行调节。长此以往, 就比较容易形成资源被长期占用、资源利用效率低下等问题。在这一背景之下, 基于分类挖掘的资源动态分配方法应运而生。它与传统的资源分配方法不同, 可以有效提高资源计算与分配的准确性、合理性等。通常来说, 衡量一种动态资源分配方法的好坏主要有三个指标, 即响应时间、资源利用率以及吞吐量。

2 基于分类挖掘的资源动态分配模型

所谓资源动态分配就是指根据资源池中的资源以及用户请求任务的情况, 对资源分配策略进行及时调整, 以更好地保证资源利用效率的提高。对资源进行动态分配主要是为了解决资源分配过程中所产生的资源碎片问题。一般来说, 基于分类挖掘的资源动态分配模型主要是由用户层、任务调度层以及资源层等几个部分构成的。通常情况下, 用户层是由用户层主要用来向任务调度层中的调度器发送资源请求, 任务调度层包括元调度器和本地调度器两种类型, 其中元调度器的主要职责在于将用户的请求发送至本地调度器中, 而本地调度器的主要职责则在于将用户的各种需求分发到各个集群中去, 以实现对闲置资源的合理配置。由基于分类挖掘的资源动态分布模型可知, 用户一般对资源已经进行了访问, 对各个集群中本地调度器的历史任务信息也已经有了较为详细的记录, 其中CDM代表的是分类数据挖掘, 主要对整个工程项目环境进行挖掘;UM代表的是用户管理, 主要负责对用户进行科学有效的管理;RM代表的是资源管理, 主要负责对资源管理层的所有资源进行管理;RA代表的是资源调度, 主要负责对闲置资源进行合理调度。

3 基于分类挖掘的资源动态分配算法

在探讨基于分类挖掘的资源动态分配算法之前, 我们需要作出如下假设:工程项目中共有n个用户, 分别为u1……un, 每个用户都有w个任务请求, 每个任务请求的时间长度均为T。在分类挖掘的基础上, 我们可以将访问同一集群的用户集合在一起, 并进而得出基于分类挖掘的资源动态分配算法。由以上阐述以及基于分类挖掘的资源动态分配的计算方法可知, 基于分类挖掘的资源动态分配算法将每个集群内的资源进行了合理高效的调度, 具体来说, 它是根据分类原则, 对每个用户的资源访问所集中的时间特征进行了判断, 并由此对请求任务进行了非常直接而又高效的调度。实践证明, 与传统的计算方法相比, 基于分类挖掘的资源动态分配算法可以对处理器资源、存储资源以及宽带资源等多种类型的资源进行协调处理, 以更好地保证这些资源的利用率达到整体的优化与提高, 与此同时对资源分配过程中可能引起的碎片问题进行有效克服与避免。

4 结语

随着我国建筑业的不断发展以及能源资源的日趋紧张, 如何才能在合理分配资源的基础上, 实现建筑工程项目的顺利有序开展, 降低其可能产生的损失就成为人们迫切关注与需要解决的问题。基于分类挖掘的资源动态分配就是一种有效地解决这一问题的方法。可以说, 在未来的发展中, 基于分类挖掘的资源动态分配将会具有非常广泛的应用范围与领域, 可以进行大规模推广应用。本文从资源动态分配的必要性、基于分类挖掘的资源动态分配模型以及基于分类挖掘的资源动态分配算法等几个方面进行了分析与阐述, 希望可以为以后的相关研究与实践提供某些有价值的参考与借鉴。在具体进行阐述的过程中, 可能由于各种各样的原因, 还存在着这样那样的问题, 在以后的研究与实践中要加以规避。

参考文献

[1]张卫红, 刘建民, 张玉洁.多项目施工资源动态分配模型[J].山东建筑大学学报, 2008, 23 (1) :11-14

[2]刘林东.基于分类挖掘的网格资源分配研究[J].计算机应用研究, 2013, 30 (2) :88-89

动态交通分配 篇8

随着数字多媒体技术的发展和普及,需要大量的多媒体服务器来支持实时多媒体流。一个实时多媒体流的编码比特率可以是固定的,也可以是可变的,如当今流行的视频点播、新闻点播等。为了避免内容传送的中断,即抖动,实时多媒体流磁盘请求必须在其截止时间前完成。一个多媒体服务器还将为如文字、图像等离散数据提供服务,这种离散数据没有实时性要求,称为非实时性磁盘请求。因此对于多媒体服务器来说,必须提出一个合理的实时磁盘调度策略,一方面要保证实时请求对于实时性的要求,另一方面也要为非实时磁盘请求提供合理的响应时间。

SCAN[1] 算法选择与当前磁头距离最短并且与磁头移动方向一致的任务作为下一个调度对象,已经被证明在减小磁盘寻道时间上是最优磁盘调度策略。但由于没有考虑实时磁盘请求,SCAN导致过多的截止时间被错过,不适合于实时多媒体服务器的磁盘调度算法。

EDF(Earliest Deadline First)[1]算法是一种基于任务截止时间的实时调度算法,在任务队列中具有最小截止时间的实时任务首先得到服务。这种算法能较好地满足任务的实时性,但它只考虑任务的截止时间因素而忽略了磁盘寻道时间,极大影响了系统的吞吐量。

许多实时磁盘调度算法如SCAN-EDF[1],SCAN-RT[2],DM-SCAN[3]都对SCAN算法进行改进,使其能够将实时性考虑在内。这些算法首先以EDF顺序来调度任务,对于截止时间相同的任务,如果不会引起错过其截止时间,则用SCAN算法来调度。最坏情况下,所有这些基于优先权的算法都将退化为EDF算法,并导致过多的磁盘寻道开销。由于这些算法都没有提供接纳控制来拒绝那些会错过其截止时刻的任务。结果导致不能保证处于服务中的流的质量。

由于多媒体服务器磁盘负载还包含了非实时任务请求,实时磁盘调度算法还必须让非时任务也具有合理的响应时间。一般的做法是每个磁盘周期都为非实时任务保留固定的权值。GSS(Group Sweeping Scheduling)[4]采用了分组策略的两级调度策略,对实时任务预留带宽。为了保证已经被接受的多媒体流的服务质量,QoS-Disk[5]引入了接纳控制机制来决定是否接受一个新到达的多媒体流。WRR-SCAN (Weighted-Round-Robin-SCAN)[6]算法对非实时任务采用固定预留带宽的方式。但是,当磁盘发生过载,或者实时任务和非实时任务请求比例突发变化时,磁盘性能将严重下降。

为此,提出了动态带宽分配扫描DBA-SCAN (Dynamic-Bandwidth-Assignment-SCAN ) 算法。该算法对非实时任务采用固定预留带宽的方式,并能够根据磁盘请求的负载变化动态调整磁盘带宽的分配比例,利用接纳控制拒绝一个不能在其截止时间前完成的请求,动态回收未用带宽来提高磁盘利用率。

1 DBA-SCAN磁盘调度框架

DBA-SCAN磁盘调度框架包括以下部分:质量协调部分,带宽预留计算部分,质量监测机制,接纳控制机制和动态带宽回收机制组成。一个磁盘作业由一个实时的连续多媒体任务或非周期任务发起。实时的连续多媒体任务是有时间限制,非周期任务没有时间限制,即非实时任务。实时磁盘调度策略不仅要考虑实时实时多媒体流请求,还要处理诸如图片、文字等离散的非实时磁盘请求。DBA-SCAN的总体运行框架如图1所示。

DBA-SCAN采用带宽预留机制,将可用的磁盘带宽预留给每个任务,预留的带宽是每个磁盘调度周期中,一个任务数据传送所需要的带宽,即一个磁盘调度周期中为其服务时的数据传输的最大时间。非实时任务则排成队列,由一个虚拟服务器服务,这个虚拟服务器也被预留了带宽。接纳控制决定是否接纳一个任务。质量协调器提供了自适应质量保证。核心调度器从每个队列中提取一轮作业,并将其排序成SCAN调度队列,同时完成动态回收未用带宽。实时任务分成保证性任务和可选性任务。保证性任务的请求必须要满足,可选性任务时在满足保证性任务后去满足的。

2 磁盘模型与任务模型

DBA-SCAN每次读或者写的最小单位为块,c表示块大小(单位:比特),V表示磁盘传输速率。磁头寻道时间为tseek(d) =a×d+tstart,其中,d表示磁头从一个磁道移动到另一个磁道所走过的磁道数,a是常数,表示磁头移动相邻两个磁道的时间,tstart为磁头启动时间。

实时磁盘调度策略的磁盘请求包括了周期性的实时请求和非周期到达的非实时请求。对于非实时请求来说,将其看成一个任务,由虚拟服务器来服务,每个磁盘调度周期都为其保留了一定的带宽。对于实时请求来说,每个磁盘调度周期都为每个实时请求预留固定的带宽。

实时请求 Ti可表示为 (Ai, Bi, Di),Ai表示到达时间,Bi表示请求磁盘块数,Di 表示截止时间。非实时请求Pi可表示为 (Ai, Bi)。

DBA-SCAN首先将磁盘带宽分成磁盘周期,磁盘周期划分如图2所示。

3 实时磁盘调度策略

一个磁盘周期的时间被分解为3个部分:磁盘寻道,磁盘旋转,磁盘数据传送。DBA-SCAN为每个任务分配一个权值来指示该任务在一个磁盘周期中所占有的最大传输时间。服务器在每个调度周期内轮流为每个任务服务。令L表示每个磁盘调度周期的时间,ts表示每个磁盘周期磁头寻道时间,tr 表示每个磁盘周期磁盘旋转时间,Wi表示实时任务Ti的权值,Wrt为所有实时任务权值之和,Wp表示非实时任务的权值,于是

对于非实时任务的权值Wp不是固定的,DBA-SCAN将利用负载监测机制来动态调整Wp的值。由于每个实时请求都带有固定的权值,通过调整权值,就能相应地控制QoS。

①权值的计算

对于实时任务Ti每个磁盘调度周期必须传输bi块数,Ti的权值是:

对于非实时任务每个磁盘调度周期保留磁盘块数ba,权值是:

没有非实时性任务时,DBA-SCAN将满足每个实时任务的截止时间。建立一个虚拟非实时服务器来为非实时任务服务。为其分配权值,为在每轮中保证其权值,为非实时任务提供小量数据传输率,以避免发生饥饿现象。非实时任务的权值越大,其作业的响应时间越短。

②接纳控制

DBA-SCAN提供了自适应质量保证,每个保证任务每一磁盘周期分配一个固定权值。剩余任务为可选任务。DBA-SCAN只有当其保证任务有足够带宽时才接纳可选任务。

当一个实时任务到达,利用公式 (1) 决定是否接纳该任务。对于tr 计算主要依赖文件系统如何组织数据块。当数据块在磁盘上随机存放时,一个磁盘周期所扫描的数据块可能不在同一个磁道上。每个磁盘周期传输的总数据块为:

其中,n为实时任务个数。最坏情况下所有数据块在不同磁道上,于是有:

其中,ta为磁盘旋转一圈与磁头启动之和。于是有:

为了完全利用带宽DBA-SCAN在磁盘周期前带宽分配,在磁盘周期后动态回收未用的带宽。前者通过每个调度周期尽可能调度更多的任务来降低磁盘开销,后者通过提前下一个磁盘周期的开始时间来动态回收未用带宽。

③负载监测机制

DBA-SCAN保证处于服务中的实时任务的质量。考虑最差情况下计算实时任务权值。然而,这些考虑也导致过多的磁盘调度时间保留,引起磁盘利用率的下降。

DBA-SCAN负载监测的方法是利用一个滑动窗口监测多媒体服务器磁盘负载的变化。自适应带宽分配调整的周期为滑动窗口大小ws。每隔ws时间进行一次带宽分配调整。监测的参数包括:实时请求的数目,非实时请求的数目,磁盘利用率。磁盘利用率定义为所有实时任务权值之和Wrt和非实时任务权值wp 与L的比值。多媒体服务器磁盘负载主要是实时多媒体请求,如果监测到实时请求和非实时请求变化较大,能够及时调整实时请求和非实时请求带宽分配。

为完全利用带宽,DBA-SCAN加入了动态调度策略,包括了磁盘周期前带宽分配和磁盘周期后带宽回收。前者通过每个磁盘周期尽可能调度更多的任务来降低磁盘开销,后者通过提前下一个磁盘周期的开始时间来动态回收未用带宽。

④带宽分配比例调整

磁盘工作是存在欠载和过载两种情况,需要针对不同情况来考虑如何调整带宽分配。

第一种,欠载情况。

欠载情况发生在为非实时任务保留带宽时,实时任务带宽是过载的,而实际磁盘是欠载的,即有剩余的磁盘带宽,还有实时请求得不到服务,降低了磁盘利用率。因此,DBA-SCAN利用监测参数来调整实时任务和非实时任务带宽的比例。此时,减小为非实时任务保留的带宽,尽量优先满足实时请求,因为非实时任务是欠载的。

由于权值W是按质量保证大小所预留的,因此实际应用中,一个流整个回放过程中,处于峰值的回放时间很短,又因为多个流的峰值出现在同一时间段内的概率较小。因此,当Wa调整为较小的值时,还有很大的概率利用动态回收的带宽来为非实时任务服务。DBA-SCAN对于Wa动态调整对非实时任务平均响应时间的影响不大。

第二种,过载情况。

采用磁盘利用率可以很好地表示各类应用请求所需的带宽,但是在过负的情况下,由于磁盘是饱和的,它的利用率是100%,因此不能反映出各类应用请求所需的带宽。在短暂过载的情况下,通常到达率高的请求应该分配高比例带宽。但是在过载的情况下,已经没有足够的带宽来满足实际请求的需要。在这种情况下,带宽调整主要任务是在服务器过载时反映出实时请求和非实时请求对带宽要求的相对差异,估计每类应用请求所需要的带宽。

所有实时任务权值之和为:

非实时任务分配的权值为:

其中,W’rt和W’p分别为监测到得实时任务和非实时任务实际需求带宽。

4 实验结果

模拟仿真实验的目的是研究新提出的DBA-SCAN算法的性能,为了对比,选用WRR-SCAN算法。固定任务总数,通过调整实时任务的百分比表示实时请求到达的频繁程度。而服务时间和磁道号随机生成。参考文献[6]设置模拟实验参数如表1所示。

图3显示不同实时任务请求率向对实时任务错过截止时间率的影响。DBA-SCAN调度算法性能要优于WRR-SCAN,主要原因是该算法利用接纳控制和动态回收未用带宽来提高它们的运行质量。一个在其截止时间以后完成的磁盘请求不仅降低了流的质量也浪费了宝贵的磁盘带宽。当服务器超载时,接受还是拒绝一个磁盘请求对于处于服务中的实时流以及非实时请求的服务质量都有很大影响。DBA-SCAN拒绝一个不能在其截止时间前完成的请求。这种接纳控制在处理频繁到达的实时流时是高效的。

5 结束语

一个实时磁盘调度算法对于多媒体服务器的性能来说是非常关键的因素。本文中提出了一个新的实时磁盘调度策略DBA-SCAN。与传统的磁盘调度算法以尽力的方式服务不同,DBA-SCAN为所有处于服务中的流提供质量保证,并限定了非实时作业的响应时间。

DBA-SCAN将磁盘服务时间分成轮次,并对服务请求一SCAN顺序进行服务。DBA-SCAN通过将一个磁盘作业分成保证作业和可选作业来提供质量保证。非实时任务和实时任务在每轮调度时都被分配一个固定的权值。为了使带宽浪费最小化,DBA-SCAN引入了积极的带宽回收策略来在运行中动态回收未用带宽。回收的带宽将被用于为可选任务提供更好的质量以及减小非实时请求的响应时间。另外,通过自适应质量保证,WRR-SCAN能够灵活的对服务中的流进行质量与数量的权衡。

通过模拟程序来对比DBA-SCAN与WRR-SCAN调度算法,通过实验结果可以看出, DBA-SCAN的性能明显好于WRR-SCAN算法,而非实时请求的响应时间也能得到一定的控制。

摘要：多媒体服务器需要一个实时磁盘调度算法为具有软实时要求的连续多媒体流服务。传统的磁盘调度算法不适应实时多媒体流。提出一个新的实时磁盘调度DBA-SCAN(Dynamic-Band-width-Assignment-SCAN)算法。DBA-SCAN算法通过带宽预留和接纳控制机制为处于服务中多媒体流提供质量保证。对于非实时任务也预留了带宽以保证非实时任务具有合理的响应时间。DBA-SCAN采用一种积极策略在运行时动态回收未用的带宽。被回收的带宽被用于为可选任务或者更多的非实时任务服务。通过模拟实验对DBA-SCAN算法和WRR-SCAN算法进行对比,实验结果显示,DBA-SCAN为实时多媒体流提供了更好的质量。

关键词：实时磁盘调度,接纳控制,动态带宽分配,负载监测,SCAN

参考文献

[1]Walid G Lbrahim Kamel,Shahram Ghandeharizadeh.Disk schedu-ling in video editing systems[J].IEEE Transactions on Knowledgeand Data Engineering,2001,13(6):933-950.

[2]Kanhere S S,Sethu H,Parekh A B.Fair and efficient packetscheduling using elastic round robin[J].IEEE Transactions on Par-allel and Distributed Systems,2002,13(3):324-336.

[3]Reddy A L N,Wyllie J,Wijayaratne K B R.Disk scheduling in amultimedia I/O system[J].ACMTransactions on Multimedia Com-puting,Communications and Applications,2005,1(1):37-59.

[4]Ketil Lund,Vera Goebel.Adaptive disk scheduling in a multimediaDBMS[C].Proceedings of the eleventh ACM international confer-ence on Multimedia,2003:65-74.

[5] Myung-Sub Lee, Kwang-Jung Kim, Chang-Hyeon Park. Real-time disk scheduling algorithms based on the two-way SCAN technique[C]. Proceedings of the 2009 International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded Computing, 2009:137-142.