CN105119837A - 基于仿真终端配置优化的分布式交通仿真负载均衡算法 - Google Patents

Abstract

本发明涉及了一种以分布式微观仿真系统的仿真终端配置优化、仿真时间模型以及基于仿真终端配置优化的负载均衡算法。针对仿真速度的需求和仿真终端配置优化问题，提出了自顶向下的微观仿真时间开销模型；从贪心生长的思想出发，提出了基于仿真终端配置优化的负载均衡算法；并对仿真速度的不同要求，给出不同的仿真终端配置方案。

Description

基于仿真终端配置优化的分布式交通仿真负载均衡算法

技术领域

本发明涉及了一种以分布式微观仿真系统的仿真终端配置优化、仿真时间模型以及基于仿真终端配置优化的负载均衡算法。针对对仿真速度的需求和仿真终端配置优化问题，提出了自顶向下的微观仿真时间开销模型；从贪心生长的思想出发，提出了基于仿真终端配置优化的负载均衡算法；并对仿真速度的不同要求，给出不同的仿真终端配置方案。

背景技术

交通拥堵会导致城市生活环境的大幅度恶化，从而阻碍了经济和社会的发展。为了解决交通拥堵问题，人们提出了许多应对方法，包括改扩建现有的道路网络和改进动态交通管控措施。所有措施在实施前均需要对其方案进行评估，以避免实施后改善效果不佳甚至于使得现有交通状况进一步恶化。例如，北京在探索设置潮汐车道时，进行了评估论证，而不是直接进行工程建设。据介绍，北京西外大街潮汐车道计划从车道沟到西四环，但与西延快速车道冲突。另外，对于南北方向的潮汐车道，刚开始计划在京藏高速和京开高速进行设置。但是初步的调研显示，目前还不具备合适的条件。所以在交通项目建设前和交通管控措施实施前，预先评估具有极强的现实意义。

为了达到事先评估和动态控制的目的，仿真技术越来越多地应用于交通领域。交通仿真使用时间驱动或者事件驱动的方法，描述一系列交通离散状态。事件驱动的方法在本质上属于串行仿真，不适合并行化。在使用时间驱动的方法时，其时钟推进机制是等步长时间推进。按照仿真对象的粒度从大到小，可以分为宏观交通仿真、中观交通仿真和微观交通仿真。其中微观交通仿真的仿真对象是单个交通实体，通过真实模拟单个交通实体在面对各种道路情况、交通管控措施和交通事件的决策行为以及各个交通实体间的相互影响，从而达到了模拟交通网络实际运行情况的目的。所以微观交通仿真被一致认为是现阶段分析解决交通拥堵问题的最准确有效的方法。

但是在仿真对象相同的情况下，微观交通仿真的计算量远超宏观交通仿真和中观交通仿真。在路网仅仅包括几十个路口时，串行微观仿真的计算时间尚在人们的接收范围内。但当路网规模扩大到上千路口后，其仿真速度就大大降低，仿真所花费的时间超过了被仿真交通系统时间。MITSIM在SGIIndigo2R4400工作站上进行仿真时，当道路网络的路口数目超过200个，路段数目超过300多条，高峰时段车辆数目超过5000时，仿真速度低于实时速度[1]。如果串行微观交通仿真系统不能很好地解决仿真效率问题，就不能用于在线实时预测。分布式并行计算在微观交通网络仿真中的应用提高了仿真速度和效率，可以满足交通管理与控制实时或者更高仿真速度的需求。

自上世纪九十年代以来，随着计算机科学的高速发展，欧美等西方国家的部分大学和研究所使用专用高性能并行计算机进行大规模交通网络仿真并行化的研究，并且得到了相当多的理论和实践成果。英国的Quadstone公司和加拿大的SOFTIMAGE公司在交通仿真领域进行合作，基于大型并行高性能计算机的硬件平台，研制了PARAMICS系统，并在智能交通运输系统中得到应用。由于专用高性能并行计算机价格昂贵，使用工作站集群进行交通网络分布式仿真对于实际应用来说更具有研究价值。基于通过局域网互联的个人计算机集群，Liu提出了一个分布式的微观交通仿真框架，通过使用多台PC机同时运行PARAMICS，每台PC仿真一个道路子网(路网分割后形成各个道路子网)中的交通流。但是在利用工作站集群进行交通网络分布式仿真的相关研究中，较多关注于理论探讨分析或系统框架设计及试验，关注于计算机并行仿真加速比，即采用多台计算机来计算某一问题比使用单台计算机计算能获得的加速倍数。但是在实际应用中，交通仿真系统的仿真速度，是一个至关重要的指标。如果仿真速度低于实时，那么该系统对于实际交通管理就不再具有实用价值，因为交通仿真的价值很大一部分在于预测，即预测拥堵从而服务于交通管理诱导，或者在新建道路或者更新交通管理方案时通过仿真来判断可行性。

为此，在分布式微观交通仿真系统中，分割道路网络、计算出需用的仿真终端数目、对仿真终端配置并且进行优化以确保仿真加速比(仿真速度是实时速度的多少倍)，是一个具有较高应用价值的问题，这个问题尚未有相关的文献研究。

发明内容

本发明在基于仿真终端配置优化的负载均衡算法下，提出了一个自顶向下的模型，该模型把通信时间消耗和计算时间消耗统一起来来衡量每个节点的仿真加速比。并通过实验测试，确保了仿真速度达到所需值的前提下，得到最小化终端数以节约成本。

在本模型中，对分布式交通仿真系统的静态负载均衡算法的研究不仅仅关注于道路网络的本身属性，而是与分布式交通仿真系统的架构与程序执行流程深入地结合在一起，同时也对仿真速度和需用仿真终端个数、车辆模型、仿真终端性能等之间关系做出了考虑。

定义了最少仿真终端数，并给出了公式，对仿真时间开销进行了分类，并构建了基于车辆的仿真时间模型，在本系统分解仿真任务时使用了功能分解与空间域分解相结合的方法。

构建了自顶向下的微观仿真时间开销模型，提出了基于仿真终端配置优化的负载均衡算法，并进行了时间复杂度分析

结合主控端与仿真计算终端各自的功能，将分布式微观交通仿真系统负载均衡模块的功能分为仿真时间开销测量、路网分割和路网分配三个部分，如图1所示。

附图说明

图1是分布式微观交通仿真系统负载均衡模块流程图。路网分配模块随后再从PC池中取出相应数目的仿真计算终端，并将相应的道路子网分配到各个仿真计算终端。

图2是仿真任务功能分解示意图。展示了本系统分解仿真任务时使用的功能分解与空间域分解相结合的方法。

图3是道路网络空间域分解示意图。展示了每个仿真计算终端仿真其中一个子网内的交通状态变化情况，具体包括车辆的状态更新、交通管控设施(如红绿灯)的设置、交通统计信息的收集等。当车辆行驶过子网边界的情况，会产生各个仿真终端间的通信。

图4是车辆的仿真逻辑流程图。图中单个仿真计算节点的仿真计算过程是完全的串行操作，即对非边界路段的状态进行更新可以和边界路段的“通信”操作完全串行。边界路段的状态更新分为两个部分，是车辆查询和迁移所对应的网络通信时间开销和车辆在查询与迁移间的计算时间开销。

图5是分布式微观仿真交通系统的仿真示意图。描述了分布式微观仿真交通的大致流程。

图6是与划分图对应的“相邻关系”图。该图描述了如何形成“相邻关系网”，即在每个子网生长完毕时，都应该检查未标记子网的连通性。如果未标记子网不连通，则子网生长完毕后可能会有两个或者两个以上的连通分支。相反，如果未标记子网连通，则子网生长完毕后必定为连通子网。若将当前子网中的每个连通分支对应为一个顶点，若两个连通分支相邻则其所代表的顶点间有边相邻，则可以形成一个新的网络“相邻关系网”。

图7是分布式微观交通仿真系统负载均衡模块流程图。该图描述了负载均衡模块的基本流程。

Claims (7)

1.一种对交通仿真终端配置优化的负载均衡算法，其特征在于：

基于仿真终端配置优化的负载均衡算法是指，在分布式微观交通仿真系统的仿真时间开销模型下，把通信时间消耗和计算时间消耗统一起来来衡量每个节点的仿真加速比，并设计实现了包括仿真时间开销测量、路网分割和路网分配三个部分在内的分布式微观交通仿真系统负载均衡模块，通过实验测试，该算法确保了仿真速度达到所需值的前提下，得到最小化终端数以节约成本。

2.如权利要求1所述的分布式微观交通仿真系统的仿真时间开销模型，系统的仿真时间开销取决于各终端的仿真时间开销，而终端的仿真时间开销取决于其仿真路网子网的各道路仿真时间开销，而各道路的仿真时间开销取决于路网结构、单个车辆的计算时间开销和通信时间开销，而单个车辆的计算时间开销和通信时间开销可以通过测量统计得到。

3.如权利要求1所述的仿真加速比，是指系统的仿真速度与实时仿真速度的比值，同时也是单步仿真周期对应的系统物理时间与系统完成单步仿真周期所花费的时间的比值。

4.如权利要求1所述的仿真时间开销测量，是指主控制端成功划分道路网络并分配给各终端后，仿真计算终端进行仿真计算和测量所需要的时间开销。

5.如权利要求1所述的路网分割，是指当所有参数都已经确定后，路网分割模块首先将地图映射为道路网络，将道路网络映射为路段耗时网络，使用基于仿真终端配置优化的负载均衡算法对路段耗时网络进行初始区域的选择和贪心生长，得到需要使用的终端个数和道路网络的分割结果。

6.如权利要求1所述的路网分配模块，是指在路网分割模块完成对需用机器数目的计算后，从终端池中取出相应数目的机器，并给各个终端发送相应的道路子网及相邻子网信息。

7.如权利要求1所述的最小化终端数，是指道路子网两两之间交集为空，个道路子网的并集等于道路网络，把个道路子网分配给个仿真计算终端，每个仿真计算终端上仿真且仅仿真一个道路子网内的交通状况，任意一个仿真计算终端的仿真时间开销必须小于等于单步仿真周期对应的系统物理时间与最小仿真加速比的比值。