（模式识别与智能系统专业论文）城市交通的并行微观仿真研究.pdf

摘要 摘要 微观交通仿真系统通过对交通流单个车辆的行为建模，模拟和再现现实世界 中交通流动态运行状况，从而为交通控制、管理和规划提供有效的分析手段。但 是，随着研究和应用的深入，交通研究和管理者们越来越期望利用微观交通仿真 对大规模路网的交通管理和规划进行分析和评估。由于大规模交通路网中的车辆 数目巨大，导致现有的串行微观交通仿真系统速度慢、效率低，难以满足实时的 仿真要求。 本文旨在研究和实现并行微观交通仿真系统，以期为大规模交通路网的控 制、管理和规划提供快速有效的评估和分析途径。本文的主要工作包括： 1 )深入研究了并行微观交通仿真的微观交通模型，提出建立基于最小二 乘支持向量机回归的微观跟驰模型，将最大熵样本精简策略引入至最 小二乘支持向量机回归，在保证预测精度的情况下，降低模型的预测 复杂度，并通过实验对该模型的预测精度和稳定性进行了分析。 2 )设计了基于空间域分解的并行微观交通仿真系统架构，并提出了基于 负载估计的k 路递归路网分割算法，并对该算法的负载均衡性能进行 分析和验证。 3 )设计了主从节点通信域以及从节点通信域两层并行微观交通仿真通信 架构，重点研究了区域间邻接车辆信息更新、跨区域车辆的信息交换 以及路径的重新分配，并详细分析了其通信开销。 4 )采用本文设计的并行微观交通仿真系统对合肥高新区路网进行了微观 交通仿真，仿真结果表明本系统具有良好的性能。 关键词：并行计算，微观交通仿真，跟驰模型，路网分割 a b s t r a c t a b s tr a c t m i c r o s c o p i ct r a f f i cs i m u l a t i o n ( m t s ) r e p l i c a t e st h er e a lt r a f f i cs i t u a t i o nt h r o u g h d e s c r i b i n ge a c hv e h i c l e ss t a t e i tp r o v i d e sa ne f f e c t i v ep l a t f o r mf o re v a l u a t i n gt h e i m p a c to fv a r i o u st r a f f i cc o n t r o l ，m a n a g e m e n ta n dp l a n n i n gs t r a t e g i e s r e c e n t l y , i th a s b e e nw i d e l ya c c e p t e dt h a tm t si sw o r t h yo ff u r t h e ri n v e s t i g a t i o n st oo b t a i nm o r e s y s t e m a t i ca n dc o m p r e h e n s i v ek n o w l e d g eo fr o a dn e t w o r kp l a n n i n ga n dt r a f f i c m a n a g e m e n te s p e c i a l l yf o rl a r g es c a l et r a f f i cs c e n a r i o s h o w e v e r , t h ec o m p u t a t i o n a l c o m p l e x i t yi n c r e a s e ds h a r p l y 、析t l lt h eg r o w t ho ft h er o a dn e t w o r ks c a l ea n dt h e s i m u l a t i o nt i m eb e c o m e su n a c c e p t a b l ef o rm t si nl a r g e s c a l et r a f f i cs c e n a r i o s t h i sd i s s e r t a t i o na i m st o s t u d ya n dd e v e l o p ap a r a l l e l m i c r o s c o p i ct r a f f i c s i m u l a t i o ni no r d e rt op r o v i d ea ne f f e c t i v eb u ta l s oh i g h l ye f f i c i e n ts o l u t i o nf o rm t s i nl a r g et r a f f i cs c e n a r i o s t h ec e n t r a lc o n t e n t so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 ) t h em i c r o s c o p i ct r a f f i cm o d e l sa r ei n v e s t i g a t e da tf i r s ta n dl e a s t s q u a r e s u p p o r tv e c t o rr e g r e s s i o nc a r - f o l l o w i n gm o d e li sp r o p o s e d i no r d e rt o r e d u c et h e c o m p u t a t i o n a lc o m p l e x i t y , t h em a x i m u me n t r o p yt h e o r yi s i n t r o d u c e dt os e l e c tt y p i c a ls a m p l e sf r o mt h et r a i n i n gd a t as e t t h i sm o d e l i st h e ne v a l u a t e da n da n a l y z e dt ot e s tt h ea c c u r a c ya n ds t a b i l i t y 2 ) t h ef r a m e w o r ko ft h ep a r a l l e lm t si sd e s i g n e db a s e do nt h ed o m a i n d e c o m p o s i t i o ns t r a t e g y t h el o a de s t i m a t i o nb a s e dk - w a yr e c u r s i v et r a f f i c n e t w o r kp a r t i t i o na l g o r i t h mi sp r o p o s e dt oa c h i e v eb e t t e rl o a db a l a n c e 3 1 1 1 1 eb i l e v e lc o m m u n i c a t i o nf r a m e w o r ko ft h ep a r a l l e lm t si s p r o p o s e d t h ev e h i c l ei n f o r m a t i o ne x c h a n g ea n dr o u t er e a s s i g n m e n ta r ed e s i g n e d t h ec o m m u n i c a t i o nc o s ti sa n a l y z e d 4 ) a p a r a l l e lm i c r o s c o p i ct r a f f i cs i m u l a t i o ns y s t e mi si m p l e m e n t e db a s e do n k d 一5 0 - il l i g hp e r f o r m a n c ec o m p u t e r a n di t sp e r f o r m a n c e sa l ee v a l u a t e d a n da n a l y z e d k e y w o r d s ：p a r a l l e lc o m p u t a t i o n ，m i c r o s c o p i ct r a f f i cs i m u l a t i o n ，c a r - f o l l o w i n gm o d e l ， r o a dn e t w o r kp a r t i t i o n i i 中国科学技术大学学位论文相关声明 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确 的说明。 作者签名：签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 作者签名： 签字日期： 口保密( 年) 爿7 0 内 耖以。s 氇 7 母 隧三一f “j 一n v ；1 图2 7样本数据一 j 一一一一一一一一一一胍。 l ；三豢举章 _ _ 。l e a d i n gs p e e d “。f o l l o w i n gs p e e d 1 一 f ，一 i 一一一一一一一弋f：习：彤；一一一一一一一l一一一一一一一一 ；，4 。寸( 一 t i m e ( s e c o n d ) 图2 8样本数据二 2 3 4 基于最大熵的样本精简算法 l s s v r 通过引入二次损失函数，一定程度上提高了支持向量机的求解速度， 但是却丧失了支持向量机原有的稀疏性，每一个训练样本都会成为支持向量，这 大大降低了模型预测中的运算速度。图2 9 展示了在不同样本数目下，最小二乘 支持向量机跟驰模型的预测运算时间，该时间是基于的c 抖仿真程序测试，测试 1 4 第2 章微观交通仿真模型 所用c p u 是龙芯2 f 。 _ 、 稔 瑚 v 留 耀 郦 骚 到 辎 图2 9不同支持向量个数下模型预测时间 从图中可以看出，在使用所有样本进行训练的情况下，模型预测时间为 2 9 9 6 9 2 m s ，若要使仿真时间小于实际运行物理系统运行时间，则仿真车辆数目 最多只能为2 0 0 2 9 9 6 9 2 = 6 7 辆( 0 2 s 为一仿真步长) 。并且，该试验中仅仅是对 车辆进行了跟驰模型的计算，没有进行其它仿真所必须的模型诸如车辆路径搜 索、换道模型、发车模型以及信号机的计算模型等等，若对每个车辆应用上述所 有模型的计算，仿真时间将更长，效率更低。 因此，使用训练样本集所有的1 2 7 8 个样本进行训练得到的模型预测运算量 较大，大大限制了仿真的运行规模和速度，有必要对训练样本集合进行精简，在 保证一定精度的前提下，选择少量典型的样本对模型进行训练，以期提高模型计 算速度。 s u k e y s 提出了一种l s s v r 稀疏化的策略，其方法是通过设定阈值口。，忽 略在训练后l 口，l o ，口1 ( 2 1 0 ) r e n y i 熵是s h a n n o n 信息熵的一般形式。当口= 2 时，r e n y i 熵被称作二次 r e n y i 熵，定义如下： 铱：( x ) = 一l o gi f x ( x ) 2 d x ( 2 1 1 ) 其中厶( x ) 是对随机变量x 的概率密度函数。对于获取的有限样本集合 = l ，2 ，) ，使用p a r z e n 窗来对x 的概率密度估计函数进行估计。 尸( x ) = 去喜k 亡) ( 2 - 1 2 ) 其中k 是窗函数，通常采用高斯函数如下： k ( t x - x a ) = 去e 掣 ( 2 1 3 ) 因此，式x 可以写成： 取：! 忉= - l o g 以( 妒出= 一1 0 9 ( 去兰羔k ( x ，- x t , 2 h 2 i ) ) ( 2 1 4 ) 下面给出一个启发式搜索方法，如图2 1 0 所示，从完整的样本集合找到具 有最大熵的子样本集合，即最大化式2 1 4 。 1 6 第2 章微观交通仿真模型 图2 1 0具有最大熵的子样本集合启发式搜索算法 为了验证基于最大熵的样本选择策略的有效性，我们选择不同的精简样本数 目对模型进行训练，图2 1 1 展示了基于最大熵选择策略的预测结果，可以看出 随着训练样本数目的增加，与实际数据的吻合程度逐渐增加。 表2 1 列出了在不同个数的训练样本下的训练误差，单个预测所消耗时间。 其中误差由式2 1 5 计算所得，可以将其理解为预测结果与实际结果间的平均速 度差。该表还列出了在仿真时间小于实际物理系统运行时间的前提下，仿真路网 最多能够容纳的车辆数目。 l “ ：a b s ( y ( t , ) - y ( t j ) ) m p e = 上l 一 ( 2 15 ) 力 从表中可以看出，当样本数目为3 0 0 时，误差也仅仅只有0 1 0 4 6 0 米秒， 比使用所有1 2 7 8 个样本训练时，精度降低了0 0 0 5 6 3 7 米秒，基本上可以忽略， 同时也表明选择出来的3 0 0 个典型样本已经足够可以代表车辆跟驰过程中驾驶 1 7 第2 章微观交通仿真模型 员的行为特征。从计算耗时上看，基于3 0 0 个样本得到的车辆的跟驰行为计算耗 时比使用所有样本进行训练整整缩短了7 7 0 ，路网最大车辆数目提高1 0 倍， 在精度基本不变的情况下大大提高了模型的计算速度。因此，本文将使用这精简 出来的3 0 0 个典型数据作为训练样本，并对基于该样本的跟驰模型进行全面的验 证和稳定性分析。 1 8 叁 爿 v 倒 瑙 抖 妲 图2 1 l不同样本数目下的对后车速度的预测结果 图2 1 2不同样本下的预测误差 表2 1 不同样本训练误差与预测耗时 样本个数预测误差( m s )单个车辆 最多容纳 跟驰模型计算耗时( m s )车辆数目 1 0 00 3 3 4 7 30 2 6 6 7 0 57 4 9 8 9 2 0 00 2 3 4 8 10 4 7 8 0 2 94 1 8 ，3 8 3 0 0 0 1 8 3 0 80 6 8 6 8 8 42 9 1 1 7 第2 章微观交通仿真模型 4 0 00 1 7 6 4 4 0 9 7 1 7 9 4 2 0 5 8 5 0 0 0 1 7 4 3 31 1 8 2 0 8 1 6 9 1 9 6 0 0o 1 6 4 4 41 4 1 0 9 61 4 1 7 5 7 0 0o 1 6 6 3 l 1 6 2 9 8 3 1 2 2 7 1 8 0 00 1 6 2 4 41 8 1 6 0 31 1 0 1 3 9 0 0 0 1 6 0 2 32 0 5 3 0 2 9 7 4 1 7 1 0 0 0o 1 5 1 2 12 3 2 6 0 18 5 9 8 4 1 1 0 00 1 4 6 5 42 6 7 2 9 17 4 8 2 5 1 2 0 00 1 4 6 5 32 8 2 7 8 87 0 7 2 4 1 2 7 80 1 4 6 9 72 9 9 6 9 26 6 7 3 5 2 3 5 模型微观轨迹验证 本节将对基于最小二乘支持向量机回归的微观跟驰模型从微观轨迹的角度 进行验证，并且同传统的g i p p s 模型、g h r 模型以及b p - n n 模型在精度上进行 对比。该实验的验证不同于前一节中的误差实验，在误差实验中，是将验证集合 中的样本依次输入到模型，并计算模型输出与实测数据之间的误差。而本实验中， 前车将按照验证数据集合中的速度进行行驶，而后车则只赋予其起始速度与初始 距离，后车速度的更新取决于上一仿真步长车辆的决策结果。实验中我们将记录 后车的速度以及与前车之间的距离，并与验证数据集合进行比较。 参与比较的模型如下： g h r 模型( c h a k r o b o r t ye ta 1 ，1 9 9 9 ) ： 啪钉) = 嘣m ) 器 ( 2 1 6 ) 其中c = 8 9 3 ，m = 0 ，= 1 ，t = 1 2 。 g i p p s 模型( w i l s o n e ta 1 ，2 0 0 1 ) ： 吁o + 乃= m ；m v z + 2 5 4 丁( 1 一v e m 。) ( o 0 2 5 + v i 吁一) n 5 ， 吗丁+ 哆胁一$ 一巩+ 谚钟 叩 其中彳，= 1 7 ，1 ，一= 3 0 ，曰，= 3 ，骞= 3 5 ，s = 4 ，t = 0 6 。 神经网络跟驰模型为包含1 个隐含层以及3 个神经元的反向传播神经网络模 型，训练样本也使用2 3 5 节中精简的3 0 0 个样本。 我们使用如下定义的误差以及2 1 5 式定义的误差来对预测结果进行比较： 1 9 第2 章微观交通仿真模型 嬲= ( 2 1 8 ) 各个模型对后车速度和轨迹的计算结果如图2 1 3 及图2 1 4 所示，从图中可 以看出无论是后车的速度预测还是后车的轨迹，本文提出的最小二乘支持向量机 跟驰模型都有着更高的精度。表2 2 与图2 1 5 列出了几种模型的误差对比，本文 提出的模型的速度误差和轨迹误差均小于其他比较的模型。 ， 狯 桨 、- 一 瑙 删 抽 崾 图2 1 3不同模型后车的速度 表6 2模型误差表 模型速度误差轨迹误差 口er m sm p er m s g i p p s 模型 0 9 7 6 4 79 0 3 6 21 2 0 0 21 0 8 2 4 g h r 模型 1 1 6 9 11 1 3 3 61 4 4 8 61 2 8 7 5 b p n n 模型 1 9 8 0 19 8 3 4 12 6 3 9 41 1 9 6 3 本文模型0 8 7 4 77 2 2 3 51 1 2 3 68 6 5 5 8 第2 章微观交通仿真模型 再一 譬! 一。 图2 1不同模型下后车的轨迹 l -i i”r - ll 2 3 6 模型稳定性分析 图2 1 5 不同模型误差 本节将对基于最小二乘支持向量机回归的微观跟驰模型进行稳定性分析，包 括渐进稳定性和局部稳定性。局部稳定性是指前车在突然减速的情况下，后车的 紧急反应情况；渐进稳定性是指在一个车队中，车辆的第一辆车突然减速的情况， 车队中后面车辆的反应情况( b h a me t a l ，2 0 0 4 ) 。 在该试验中，我们分别对渐进稳定性和局部稳定在两种不同剧烈程度的前车 扰动下进行： 荆嗤封蒜 l一 第2 章微观交通仿真模型 1 ) 在第一种情况下，局部稳定性实验初始状态为前后车相距2 0 米，速度均 为1 0 米秒，前车以2 m s 2 的加速度进行减速，观察后车的反应情况。渐进稳 定性实验的初始状态为一个含有1 0 辆车的队列，车辆的速度均为1 0 米秒，车 间距为2 0 米，队列中的第一辆车以以2 m s 2 的加速度进行减速，观察队列中后 面车辆的反应情况。 2 ) 在第二种情况下，局部稳定性实验和渐进稳定性实验的初始状态与第一 种情况完全一致，但是实验中前车或者车队中的第一辆车是以8 m s 2 进行突然 减速至速度为0 ，观察队列中后面车辆的反应情况。 两种情况下，局部稳定性的结果如图2 1 6 至2 1 8 所示，由图2 1 6 及图2 1 8 可以看到，在前车以2 m s 2 和8 m s 2 两种情况下，后车均能在经过一定的延时 后进行及时的减速，使两车的间距保持在2 5 米左右。 狯 桨 一 醚 蜊 l = 需辜薹震1 i 薛 、i i l i 。誊j ? i 。_ 、w i j 沙j 一 套 * v 倒 瑙 时间( 秒) 图2 1 6 后车速度变化( 前车以8 m s 2 减速) 时间( 秒) 图2 1 7 后车速度变化( 前车以2 m s 2 减速) 第2 章微观交通仿真模型 时间( 秒) 图2 1 8 前车后间距( 前车以2 m s 2 和8 m s 2 减速) 渐进稳定性的实验结果如图2 1 9 至2 2 2 所示，由图2 1 9 及图2 2 0 可以看到， 在队列中的第一辆车以2 m s 2 和8 m s 2 两种情况下，该制动会向后传播，队列 中的后车均在经过一定的延时后进行及时的减速，将自身的速度减至0 。从图 2 2 1 及图2 2 2 的车辆间距图可以看出，在在队列中的第一辆车以2m s 2 和 8 m s 2 两种情况下，后车相互之间的间距最近都保持在了2 5 米左右。 时间( 秒) 图2 1 9 后车速度( 车队第一辆车以2 m s 2 减速) 叁 * v 毯 捌 第2 章微观交通仿真模型 时间( 秒) 图2 2 0 后车速度( 车队第一辆车以8m s 2 减速) 时间( 秒) 图2 2 1 队列中车辆间距( 车队第一辆车以2 m s 2 减速) * v 职 重 排 时间( 秒) 图2 2 2队列中车辆间距( 车队第一辆车以2m s 2 减速) 第2 章微观交通仿真模型 2 3 本章小结 本章首先介绍了本文并行微观仿真系统中的交通路网模型，接着详细阐述提 出的基于最小二乘支持向量机回归的微观跟驰模型，并引入最大熵策略用于训练 样本的精简。通过基于现场数据的实验表明：1 ) 基于最大熵的样本精简策略能 够在保证一定预测精度的情况下，有效提高l s s v r 微观跟驰模型的预测计算速 度和效率；2 ) 本文的跟驰模型相比现有模型具有更高的精度和良好的稳定性。 2 5 第3 章微观交通仿真并行架构与路阿分割 第3 章微观交通仿真并行架构与路网分割 本章将阐述微观交通仿真系统并行架构与路网分割算法。首先简要介绍了并 行计算的基本概念和并行程序设计模式，接着给出了本文设计的并行微观交通仿 真中基于空间域分割的并行架构，并提出了基于负载估计的k 路递归路网分割 算法。 3l 微观交通仿真系统并行架构 311并行计算基本概念和并行设计模式 并行计算是指在并行机上，将一个应用分解成多个子任务，分配给不同的处 理器，各个处理器间相互协调，并行地执行子任务，从而加速问题求解速度。并 行机是并行计算基础条件之一，按照f l y m n 的分类方法，并行机可以分为s i s d ( s i n g l ei l l s h u c t i o as i n g l ed a t a ) 、s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 、s i m d ( m l i l t i p l ei n s h x l c t i o ns i n g l ed a t a ) 以及m i m d ( m u l t i p l e i n s t r u c t i o nm u l t i p l ed a t a ) 。 s i s d 是每个时钟周期只有一个指令被执行，同时只有一个数据流作为输入，实 际上是串行机。s i m d 类型的并行机是指每个时钟周期每个c p u 执行相同的指 令，但是针对不同的数据输入。m i m d 类型的并行机则是每个c p u 执行独立针 对不同的数据并且执行不同的指令( d o n g a r r a ，2 0 0 2 ) 。 另一种重要的分类方法是依据并行计算机的内存架构将并行计算机分为共 享内存、独立内存和混合内存三类。共享内存并行计算机如图3 1 所示，所有处 理器将可以独立的访问共享的内存资源，任何一个处理器对内存值的改变对其他 处理器都是可见的。 c p u i c p u 图3 1共享内存结构 第3 章微观交通仿真并行架构与路网分割 独立内存结构的并行计算机如图3 2 所示，各个处理器独立有拥有存储模块 处理器间并不能直接其他处理器的内存。处理器之间通过互联网络进行通信 n o d e l 圈墨蜀匝窭盔n o d e2 n o d e3 图3 2独立内存结构 n o d e4 混合内存并行机结构如图33 所示，通常各个计算节点由共享内存的多处理 器构成，每个计算节点间的内存通过互联网络进行访问。 n o d e1 n o d e3 图3 3混舍内存结构 n o d e2 n o d e4 并行程序设计根据并行机类型的不同，有着不同的实现方式，总的来说其设 计模式主要有以下几类( 陈国良，2 0 0 4 ) ： 1 ) 主从模式的基本思想是将一个带求解的问题分成主、从两个进程，主进 程负责将任务分配至子进程，子进程负责具体任务的计算； 2 ) 单程序多数据流的模式也叫数据并行策略，其基本的思想是多个计算节 点运行相同的代码，但是却执行在不同的数据上： 3 ) 数据流水线是一种最常用的并行处理技术，其思想是将各个计算进程组 织成条流水线，每个进程执行一个特定的计算任务，相应于流水线的一个阶段， 流水线上的前一个子任务完成，后继的子任务就可以立即开始。 4 ) 分治策略的基本思想是将大规模的问题分解成若干个子问题进行分治， 同时地递归求解各个子问题，最后归并各子问题的解成为原问题的解，分治策略 的并行方式比较适合递归程序的设计当中。 一般而言，设计一个并行程序可以分为四个阶段：任务划分、通信分析、任 务组合和处理器映射四个阶段口c a m ) ，如图3 4 所示。 量 生砉i 霉蓐 第3 章微观交通仿真并行架构与路网分割 。 划分ooo 叶o0n oo 图3 4并行算法的p c a m 过程 任务划分指的是将整个求解任务划分若干个子任务，其主要划分方法包括了 域分解和功能分解：1 ) 域分解的实质即是数据划分，将问题求解的数据分解成 小的数据片，并尽可能使这些小数据片大小一致，然后再在不同的计算节点对分 解后的小数据集上进行计算。2 ) 功能分解是不同于数据分解的另一种并行任务 划分方法，其分解重点集中在计算上，而不是计算的任务( 数据集) 上，通过将 计算分解成不同的部分来达到并行的目的。功能并行的发掘空间比较有限，其依 赖于计算问题本身，并且不会随着计算节点数目的扩大而增长。而数据并行一般 则具有更加良好的可扩张性，也更易于实现负载均衡。 通信分析将处理划分的各个子任务之间的数据交互，组合阶段将按性能要求 是实现的代价来考察前两个阶段结果，必要时可将一些小的任务合并，以提高性 能和减少通信开销。最后一个阶段映射的过程即是将任务分配到一个计算节点 上，其主要目标是减少算法的总执行时间。 3 1 2 并行微观交通仿真系统的并行架构与仿真流程 根据并行算法设计中的任务划分模式，并行微观交通仿真的并行化也存在两 中不同的并行化架构。其一是寻找微观交通仿真中的功能并发性，即在微观交通 仿真计算过程寻找可以同时执行的功能模块。d y n a m i t 微观交通仿真软件采用 的就是功能并行化的策略，其交通控制中心( t m c ) 、仿真模块( m i t s i m ) 以及交 2 9 第3 章微观交通仿真并行架构与路网分割 通控制中心协调i 器( t m c a ) 是并行执行的，但是这样方面其理想的虽大可并行 执行的模块数目为3 ，再增加计算节点数目，并不会提高其计算效率，因此其扩 展性很差。微观交通中仿真中，计算量最大的车辆行为模型的计算过程是一个包 含有若干个子行为模型的决策流程，这些子模型包括车辆的跟驰模型、换道模型 以及物理行为模型，尽管将这些不同的子模型进行功能并行化是可行，但是如前 所述，该并行化策略扩展性很弱，其能获得的最大效率即是词以同时执行的功能 模块数目，而这些可以并行的模块在仿真模型中又是非常有限的。因此，采用基 于空间域分解的并行策略也是并行微观交通仿真并行架构的更佳选择。纵观己有 的并行微观仿真系统，除了上述的d y n a m i t 外，其余系统均采用空间域分解的 架构，以期达到更加的扩展性和并行效率。 本文的并行微观交通仿真将采用基于空间域分解( 数据分解) 的并行架构， 如图3 6 所示，其基本思想是将整个仿真路网分割成不同的子区域，每个计算节 点将负责处理其中的一块子区域。并行程序设计采用主从模式，主节点即图中所 示的m a n a g e rc o m p u t i n gn o d e 将负责将整个路网进行分割，然后将不同子区域 分配给不同的子计算节点( w o r k e rc o m p u t i n g n o d e ) 进行仿真计算，具体包括各个 子区域所含路网中车辆的行为计算以及交叉口信号机的计算。 图3 5空间域分割并行架构示意图 基于上述并行架构的并行微观仿真交通流程如图3 6 所示，首先主节点和子 节点均载入全局的静态地图，然后主节点执行地图分割，将路网分割成与从节点 数目一致的子区域并将这些子区域信息发送给从节点。从节点接收到自身负责计 算的区域后，便开始对区域内的道路上的车辆行为以及所辖区域的交叉口信号机 进行计算，其具体的计算过程如图中仿真计算框内所示，调用的模型包括了发车 模型、跟驰模型、换道模型以及信号机模型等。子计算节点一步仿真计算完毕后， 第3 章微观交通仿真并行架构与路网分割 将计算完的车辆信息反馈至主节点主节点进行整个路网车辆信息的合并汇总。 此时，子节点之间再进行进入和驶出车辆的交互。最后，子节点向主节点反馈完 毕信息- 主节点再下发新一步的仿真命令，如此循环，直至仿真结束 主节点 从节点 叵囤 仿射算 i 巴龆 i 匝出厂 吨三 车il 零l 、 n 7 l = 二= 三j ! 竺竺i 罡卧 一目* 粘i t 一 广b 基圜圈p 爹口镯 l 匦m 宅i n 面嘉订 = = ： i 竺掣! | e 焉翻 匝至圃爿， 霎圈 图3 6基于空间域分割并行微观交通仿真流程 由上述流程可以看出基于空间域分割的微观交通仿真的计算耗时主要有三 部分组成：子区域内的车辆行为计算以及通信耗时。 对车辆行为计算耗时而言，每个子计算节点的计算负载应当尽可能地一致， 这就要求路网分割后各个子区域处理的车辆数目应当基本一致，达到负载均衡状 态，避免子节点间出现“快等慢”的现象，以提升并行效率。但是，太规模交通 路网是一个高度耦舍的系统，并且交通流在仿真过程是动态变化的，这对路网分 割算法提出了很大的挑战。下一节本文将提出基于路段负载估计的k 路递归路 第3 章微观交通仿真并行架构与路网分割 网分割算法以改善负载均衡提高仿真并行效率。 3 2 基于负载估计的k 路递归路网分割算法 3 2 1 并行微观交通仿真系统路网分割算法 在基于空间域分解的微观交通仿真并行架构下，路网分割的任务即是将大规 模交通路网分割成若干个子区域，每个子计算节点将负责一个区域内的车辆行为 和信号机的计算。理想的路网分割将使得仿真运行时各个子区域的车辆数目一 致，并且子区域间的车辆交互量最小，达到最佳的负载均衡效果。但是大规模交 通路网是一个高度耦合的复杂系统，其路段的车辆数目在仿真过程中是动态变化 的，并且车辆在分割后子区域间有驶入和驶出的交换行为，这给设计路网分割算 法带来了很大的挑战。 设计路网分割算法包括拓扑图转换以及图分割两个关键环节。拓扑图转换过 程是将仿真路网模型转换成由节点和边组成的拓扑图，需要确定的是将路网模型 中的哪些对象集合映射成拓扑中的节点和边；图分割则是基于拓扑图设计分割算 法，将拓扑图分割成的点和边组成的子区域，子区域中这些点和边所代表的路网 模型中的实体再交由子计算节点进行计算。 下面将简要介绍下已有的基于空间域分解并行架构的微观交通系统中路网 分割算法，并分析其优点和不足之处。 t r a n s i m s 并行版本中的分割是从路段的中间进行分割，如图3 7 所示， 将交叉口所连接的路段的一半结合成一个节点，节点的权重即为所连道路长度的 一半。n e g a l 等人在应用了正交递归二分法和多层次递归剖分( m e t i s ) 两种不同 的方法对转换得到的拓扑图进行分割。n e g a l 所采用的正交递归二分法基本思想 是重复进行水平方向和垂直方向的对称分割，因此没有考虑到参与的子计算节点 个数，因此该方法在子节点的数目是2 的整数次方的时候分割效果最优。同时， 在在该工作中，n e g a l 还引入根据上次迭代的时间为权重进行重新的路网分割的。 类似于t r a n s i m s 的工作，d c h a r p a r 在m a t s i m t 的并行化中，也使用了正 交递归二分法进行了路网的分割。 3 2 第3 章微观交通仿真并行架构与路网分割 、- 节点 ： 一 ! 交叉口 路段 ， 、 t 、f ( ： o 。一一j ，c 、_ lr 1 。- 一一和一 t0 一 i ， ，、 图3 7 t r a n s i m s 中的拓扑图节点示意图 k l e f s t a d 等在p a r a m i c s 的分布式开发研究中，使用的是基于面积的二 分法，即将路网图按照面积进行路网的均匀。同时，作者也指出尽管该方法在显 示上具有局部化、区域化的优势，但是会造成负载的不均衡。 a i m s u n 的并行化使用的则是另一种不同的划分方式，首先该方法将路 网划分成不同的块，如图3 8 所示：路段2 、路段1 以及交叉口a 称为块l ；路 段4 、路段5 、路段6 、路段9 以及交叉口b 为块2 ；路段3 为块3 ；路段7 为块 4 ；路段1 0 为块5 ；路段8 为块6 。简而言之，就是将交叉口的入v i 道路与交叉 口合并为一块。于是，将路网图转换成了以块为节点的拓扑图，然后作者使用染 色法将连通的块用不同的颜色表示，相同颜色的节点为一层，层与层之间是出串 行执行的，但是层间的块之间由于没有关联，因此是并行执行的。 图3 8 a i n s u m 中的拓扑图节点示意图 第3 章微观交通仿真并行架构与路网分割 t p s s 的并行微观交通仿真的拓扑图生成与a i m s u n 类似，如图3 9 所 示，将路口及其入口道路看作一个节点但是在分割时却不同与a i m s u n ，类 似于t r a n s i m s ，其采用了正交递归分割法与m e t i s ，但是同t r a n s l m s 一 样，其正交递归分割时没有考虑参与的子计算节点个数，导致只有参与子节点是 2 的整数次方时才能达到较好的负载均衡效果。 圈3 9t p s s 中的拓扑鹫节点示意图 可以看出，现有的并行微观交通仿真基本上以及路口为节点进行拓扑图的转 抉，并采用正交递归二分法进行地图的分割，但是此类分割方法具有阻下弊端： 1 ) 以路口为最小单位进行拓扑图的转换使得分割的粒度较大，难以达到理想的 负载均衡效果；2 ) 其次，采用正交递归二分法使得只有参与子节点是2 的整数 次方时才能达到较好的负载均街效果；3 ) 采用分割方法的权重采用的是以道路 长度或者区域面积，但是仿真运行的负载量事实上是道路上车辆数目，并不是仅 仅正比于道路长度，因此可能出现仿真运行时长度很长的路段车辆数目反而比较 少，导致出现负载不均衡的现象。针对上述问题，本文下面提出基于负载估计的 k 路交通路网剖分方法，以期达到更加的负载均衡效果。 3 , 2 2 拓扑图生成 结合微观交通仿真中的基础路网结构，对于拓扑图的转换基本，最直观的应 当有以下两个方法： 1 ) 以路口为最小单位的分割。该方法的并行粒度较大，一个路口可能包含 通常包含四个相应的进口路段，因此路口与路口之间车辆数目即负载情况可能差 异很大，难以达到理想的负载均衡效果；但是该方法的分割复杂较小，分割后子 区域问的通信也相对较小： 第3 章撇观交通仿真并行架构与路网分割 2 ) 以单个路段和弯道为最小单位的分割。该方法相比较以路口为单位的分 割而言，并行粒度很小，易于实现负载均衡，但是会增加分割的复杂度，并且导 致分割后子区域问更加频繁的通信。 鉴于以上两点，综合考虑分割的粒度和复杂度，本文提出如下的拓扑图转换 策略：以路段及其所连接的出口弯道作为虚拟的拓扑图节点，如图31 0 所示。该 方法相比较而言，有以下两个优点：1 ) 较以路口为单位的分割而言，分割粒度 要小，更易于实现负载均衡；2 ) 较以直道和弯道作为分割单位的方法而言，由 于弯道上的车辆数目较直道而言基本可以忽略，因此分割的粒度并不会有明显的 增加，同时，本方法的分割复杂度要小，分割后的子区域间通信量比以直道和弯 道单独作为节点的分割方法要小。 e m 日 图3 1 0 本文并行微观交通仿真系统拓扑节点示意图 323基于负载估计的k 路递归路网分割算法 如3 21 节中所述，正交递归对分法被广泛地使用在已有的并行微观交通仿 真系统中，但是该方法有明显的两个弊端：1 ) 只有参与子节点是2 的整数次方 时才能达到较好的负载均衡效果：2 ) 以道路长度或者区域面积为初始权重进行 分割会导致仿真运行时子区域间负载不均衡的现象。 针对上述问题，本文提出了基于负载估计的k 路递归路网分割算法。该算 法基于仿真o d 分布与驾驶员的路径选择模型，估计仿真运行时节点负载量，应 用k 路递归剖分法对拓扑图进行分割，进而实现对大路网仿真的任务分治。 第3 章微观交通仿真并行架构与路网分割 该算法较传统的正交递归剖分有两个明显特点： 1 ) 对路网中仿真运行时的路段负载进行估计，并以该估计值作为初始节点 的权重； 2 ) 其次在分割中采用k 路递归剖分策略取代正交对分策略，使得在计算节 点不是2 的整数次幂的情况下，仍然可以可到负载均衡的子区域。 下面将详细阐述本文提出的基于负载估计的k 路递归路网分割算法。 首先，我们对仿真运行时的路段负载进行估计。对于道路k 而言，其负载睨 ( 道路上的车辆数目) 可以由下式计算： 哌= 反如= 丛厶 ( 3 1 ) 其中以代表道路七的密度，疋代表的是道路的长度，以和唯分别代表道路 的流量和平均速度。从上式，可以看出，单个道路的负载是和道路的流量、长度 成正比和道路的平均速度成反比。 基于负载估计的k 路递归对分策略即是对通过对道路负载哌进行估计，并 使用该估计值作为递归对分的权重，如式3 2 所示： w e k = ( 3 2 ) 、， 对于式3 1 中的平均速度，我们假定在非饱和的情况下路段速度一致，因此， 我们有： 舾t = 触 ) 因此，我们需要对路段的流量进行估计，对路段流量的估计即是驾驶员路径 选择模型的逆过程。因此结合o d 矩阵，我们给出路段流量估计如下式： 以= a ( ，七) 厶尸( q 。) ”6 d 6 d 6 c 脚 ( 3 4 ) a c c 二，七，2 o ：茎乏； 。3 5 ， 其中，o 和d 分别代表出发地集合和目的地集合；- ，m 一是从始发地, 到目的 地m 的旅行量；c 幺代表整个路径集合中的第i 条路径，其由从始发地，z 到目的地 m 的k 最短路径构成；尸( ) 是驾驶员从c m 中选择路径f 作为其行驶路径的概率。 如果路径集合包含了道路k ，那么a ( 已，豇) 等于1 ，否则等于0 。 在式3 4 中，一是输入的o d 量，所以我们只需要根据驾驶员路径选择模 型计算p ( ) 即可。在本微观交通仿真模型中，我们采用的是由c a s c e t t a 等人 提出的c l o g i t 路径选择模型，其克服了传统的m u l t i n o m i a ll o g i t 模型在处理重 3 6 第3 章微观交通仿真并行架构与路网分割 复路径中的弊端( 1 9 9 6 ) 。在c l 0 醇模型中，选择道路f 作为行驶路径的概率由 下式给出： p ( 廿需 4 ( 3 6 ) 其中，l 是路径 的效用函数；q 是路径的公共因子，由下式给出： q 哪k 隅i 差 l j ( 3 n 其中是路径z 和路径，公用的道路的总长度；和，分别是路径。和路径 的长度。本文中，效用函数取为道路长度的倒数： = 了_ 1 ( 38 ) 因此我们给出道路i 的负载估计如下式： 呱2 。乏丕美峨帆差南 ，“ ( 39 ) 基于上式，我们可以给拓扑图中的节点赋予相应的权重。 下面将应用k 路剖分策略对该拓扑图进行分割。传统的对分蘸略，每次递 归分割时，将待分割的区域分割成两个权重一致的区域。图3 1 l 展示的是正交 递归对分法在将图中的拓扑图分割成3 个子路网时的分割情况，其中每个节点的 权重为1 。那么该方法首先进行垂直分割，得到权重一致的两个区域，再对其中 一个区域进行平均水平分割，于是得到3 个子区域。但是，显然在这种情况下， 区域2 的负载明显大于区域1 和区域3 。 固。 、j 二o 1 0 一j 陌n 0 团i 。幽 mo 、o 旺 图3 1 1 正交递归对分法 第3 章微观交通仿真并行架构与路网分割 不同于传统的对分策略，k 路递归剖分在每次剖分时，并不是进行对分，而 是根据分割子区域的个数需要，按照一定的权重比例进行分割。该方法在分割前， 首先根据需要分割的子区域的个数确定每个子区域的权重，令分割于区域数目为 州，那么该次分割的两个子区域的权重值比应为1 m 2 l ：l m 2 l ，同时该比值也 代表这两个次区域需要继续的递