EN中文

地球信息科学学报 >

2022 , Vol. 24 >Issue 5: 815 - 826

DOI: https://doi.org/10.12082/dqxxkx.2022.220001

地球信息科学理论与方法

面向大规模空间Agent建模的分布式地理模拟框架

  • 曾梦熊 ,
  • 华一新 , * ,
  • 张政 ,
  • 张江水 ,
  • 杨振凯 ,
  • 韦原原
展开
  • 信息工程大学地理空间信息学院,郑州 450052
* 华一新（1963— ）,男,江苏句容人,博士,教授,主要从事地理信息系统平台及其应用技术研究。 E-mail:

曾梦熊（1986— ）,男,湖南湘乡人,博士生,主要从事地理信息系统开发与应用研究。E-mail:

收稿日期: 2022-01-01

  要求修回日期: 2022-03-08

  网络出版日期: 2022-07-25

基金资助

国家重点研发计划项目(2021YFB3900900)

版权

版权所有,未经授权,不得转载、摘编本刊文章,不得使用本刊的版式设计。
收起

A Distributed Geospatial Simulation Framework for Massive Spatial Agent-Based Modeling

  • ZENG Mengxiong ,
  • HUA Yixin , * ,
  • ZHANG Zheng ,
  • ZHANG Jiangshui ,
  • YANG Zhenkai ,
  • WEI Yuanyuan
Expand
  • Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450052, China
* HUA Yixin, E-mail:

Received date: 2022-01-01

  Request revised date: 2022-03-08

  Online published: 2022-07-25

Supported by

National Key Research and Development Program of China(2021YFB3900900)

Copyright

Copyright reserved © 2022.
Fold

摘要

基于Agent建模的地理模拟是认识和理解动态地理现象的有效方法,但随着地理模拟的规模和复杂性不断增加,模型的计算问题开始凸显。分布式并行仿真是解决大规模Agent复杂模拟计算的途径,然而已有研究基于Agent建模/仿真软件构建并行仿真系统的方式并不适用于具有高移动与行为交互的空间Agent建模及其模拟过程的实时可视化。为解决这个问题, 本文提出了一个分布式地理模拟框架DGSimF,用于大规模动态空间Agent模拟,支持模拟过程的实时表示与分析。设计了一个简单但高效的时空数据模型建模空间Agent,支持直接基于Agent行为建模集成地学模型,采用了时间微分方法协同各计算节点行为的执行,实现以“任务并行”的方式进行分布式计算以提高仿真性能,构建了基于三维地球渲染引擎的虚拟地理环境,提供模拟过程的实时可视化。最后,以“红蓝对抗”案例进行了实验验证,对不同模拟计算量和不同客户端数量下的仿真性能进行了分析,结果表明DGSimF可以为具有时空特征变化与行为交互的大规模空间Agent模拟提供一个有效的平台。通过扩展计算节点,DGSimF可以有效地缓解复杂模拟计算的压力问题,并且仿真性能较高,在实验中并行效率保持在0.7以上。

关键词： 地理模拟; 空间Agent; 分布式计算; 并行仿真; 基于Agent建模; 行为建模; 虚拟地理环境; 实时可视化

本文引用格式

曾梦熊 , 华一新 , 张政 , 张江水 , 杨振凯 , 韦原原 . 面向大规模空间Agent建模的分布式地理模拟框架[J]. 地球信息科学学报, 2022 , 24(5) : 815 -826 . DOI: 10.12082/dqxxkx.2022.220001

Abstract

Geospatial simulation based on agent-based modeling is an effective method to recognize and understand dynamic geographic phenomena. As the scale and complexity of geospatial simulation continues to increase, the challenges in model computation increase. Distributed parallel simulation could be used to solve the complex simulation issue of large-scale agents. However, the existing research on building parallel simulation system based on agent modeling/simulation software is not suitable for modeling of spatial agent with high-mobility and behavioral interaction with others, and real-time visualization of simulation process. To solve this problem, this paper proposes a distributed geospatial simulation framework, namely DGSimF, for massive dynamic spatial agent modeling, which supports real-time representation and analysis of the simulation process. A simple but efficient spatial modeling agent for spatial-temporal data is designed, which supports the modeling of integrated geoscience models directly based on agent behavior, adopts the time differentiation method to coordinate the execution of the behavior of each computing node, supports distributed computation in the way of "task parallel" to improve the simulation performance, and constructs a Virtual Geographic Environment (VGE) based on three-dimensional earth rendering engine to support real-time visualization of intermediate simulation results. Finally, the experiments based on the "Red vs. Blue" case are carried out, and the simulation performance with different computation cost and different number of clients is analyzed. The results show that DGSimF can provide an effective platform for massive spatial agent simulation of spatio-temporal feature change and behavior interaction. By expanding the computing nodes, the pressure of complex simulation calculation can be effectively alleviated. Meanwhile, the simulation performance of the proposed framework is high, and the parallel efficiency remains above 0.7 in these experiments.

Key words： geospatial simulation; spatial agent; distributed computing; parallel simulation; Agent-based modeling; behavior modeling; virtual geographic environment; real-time visualization

1 引言

基于Agent建模（Agent-Based Modeling,ABM）的地理模拟通过表示大量个体Agent及其与环境之间的动态非线性交互反映真实世界地理现象的时空动态,被广泛应用于研究耦合的自然和人类系统[1,2,3]。然而,模拟Agent个体层面的行为交互往往需要大量的计算,尤其是面对大规模Agent建模时,导致计算能力受限的桌面计算机面临重大的计算挑战。为解决大规模ABM中的计算问题,先前的研究提出了一系列建模框架和系统[4,5,6,7],以增强地理模拟的仿真性能,但这些方法大多针对特定的研究问题或预先确定的场景,对Agent时空特征变化及行为交互的描述比较简单,不适用于Agent高移动[8]、Agent之间行为交互[9]的建模,如实体随位置和属性变化引发行为交互并改变自身及相关对象位置和属性的时空过程模拟。此外,已有的研究更关注于地理模拟的建模和性能改进,缺乏对模拟过程可视化的研究,多数情况下仅支持模拟结果的回放[10],对地理模拟过程的三维实时表示没有得到很好的解决。
因此,面向个体时空特征变化与行为交互的大规模动态空间Agent模拟,现有的研究方法不可避免地面临一系列建模与计算问题[11],如移动个体与位置有关的行为难以描述,个体之间交互影响的复杂行为难以分解、计算时间过长和计算资源消耗高。解决上述问题的途径一方面是提高模拟模型的能力以表达个体时空特征变化与行为交互,另一方面是提高计算效率以降低对运算所需资源和时长的要求。针对前者,通常面临2个选择：① 建立小而简单的模型,但Agent的行为必须在规则和参数形式上更加复杂才能获得更真实的输出[10];② 建立大而复杂的模型,但可能需要在超级计算机上才能运算。针对后者,分布式计算是有效的解决方案[12,13,14]。分布式计算以云、集群的形式提供重要的算力分配和共享,通过并行仿真分解原始地理模拟模型为多个子任务,分配到不同的计算单元并同时求解,达到子任务对运算所需资源需求小、并行计算缩短时长的目的,但需要搭建复杂的分布式系统分发和汇总各个节点的计算。因此,尽量以简单的模型支持Agent高移动与行为交互建模并提供分布式计算,是大规模空间Agent建模需要解决的问题之一。
目前已有的一些研究利用Agent建模/仿真软件集成地学模型构建地理模拟以支持分布式并行仿真[15,16,17],如李真强[10]等基于Repast HPC设计开发了大规模ABM的分布式模拟系统。但由于Repast并不支持GIS功能,需要在Repast数据模型的基础上根据模拟过程额外设计扩展的空间数据结构和过程模拟算法,模型实现比较复杂,缺乏对地理模拟的底层、通用支持。同时,局限于Repast的可视化功能仅支持基于地图的模拟结果回放,在三维、动态、实时、交互等方面存在不足,不能显式传达Agent的动态变化和行为发生过程,不适用于动态空间Agent模拟过程的实时表示。因此,有必要从设计上改进上述地理模拟的构建方式,为空间Agent建模的地理模拟提供通用支持,实现模拟过程的分布式计算与实时可视化。

2 空间Agent建模的地理模拟框架

2.1 总体结构设计

为解决动态空间Agent的建模与大规模复杂模拟的计算压力问题,实现面向应用的模拟过程三维实时可视化,本文提出了一个集成分布式计算与虚拟地理环境技术的分布式地理模拟框架（Distributed Geospatial Simulation Framework,DGSimF）,采用直接基于Agent行为建模集成地学模型的方式提供对地理模拟的底层支持,可以更好地融合GIS和ABM,同时利用虚拟地理环境技术集成GIS与可视化实现对中间模拟结果与地理数据的一体表达,为模拟过程的实时表示与分析提供了可能。总体结构如图1所示。
图1 DGSimF的总体结构

Fig. 1 The general architecture of the proposed DGSimF

DGSimF的体系结构主要由3个部分组成：时空数据库（Spatio-Temporal Database,STDB）、分布式仿真引擎（Distributed Simulation Engine,DSIME）、实时可视化模块。其中,时空数据库是基础,提供对地理数据和动态空间Agent的一体化描述与结构化存储。数据存储以时空数据模型为载体,通过模型支持位置移动与属性变化以及行为交互的表达,用于在底层描述空间Agent。该模型以版本管理和动态数据相结合的方式合并Agent基态变化和存储中间模拟结果,实时更新Agent上下文。为适应大规模ABM计算的高性能要求,时空数据库采用了服务器虚拟化集群的分布式存储方案。分布式仿真引擎构建在数据库基础上,负责大规模Agent复杂模拟的计算,具有多计算节点并行仿真,提供实时数据访问和协调、控制、分发仿真任务的能力,主要任务是将大量Agent个体的交互行为生成为以仿真步长为单位的仿真任务集,在一个仿真步长内通过分布式计算将仿真任务集分配至不同的计算节点并同时求解,达到运算资源需求小、缩短计算时长的目的。实时可视化模块是输出界面,基于三维地球渲染引擎Cesium实现,并与分布式仿真引擎分离,通过数据访问接口实时获取数据库中Agent时空特征变化和行为交互过程,用于在虚拟地理环境中对模拟过程实时可视化,主要功能是为地理数据和中间模拟结果的一体表达提供三维虚拟可视化环境,帮助用户直观、快速地理解模型的输出。
DGSimF总体结构的特点是：① 将数据与计算和可视化三者进行了分离,减少了数据建模与模拟计算和可视化表达之间的耦合关系,在大规模空间Agent建模时,便于数据与计算和可视化的单独或协同开发;② 数据存储、仿真引擎和可视化模块3个部分统一通过时空数据库引擎实现对Agent数据的实时访问,其优势主要有2个：① 仿真引擎通过中间模拟结果实时更新Agent状态,为可视化模块提供了仿真计算的实时数据,解决了模拟过程实时可视化的数据来源问题;② 数据库利用中间模拟结果合并Agent动态变化,实时更新Agent上下文,为仿真引擎的行为生成与具体执行准备了实时数据,解决了动态空间Agent交互行为对位置和属性变化的实时性敏感的问题。

2.2 空间Agent数据模型

现有研究对Agent特征的描述比较简单,更关注于过程模拟模型的实现而不是Agent本身,多数情况下将Agent个体作为行为交互过程作用的简单对象模型,通过行为改变对象的特定属性实现预先确定场景的地理模拟。然而,这种简单属性集合的Agent数据模型已经不能适用于个体时空特征变化与行为交互的动态空间Agent建模。
与简单对象Agent不同,动态空间Agent实质上是一个时空实体,不仅其位置和属性随时间和行为交互发生动态变化,而且对象本身也可能随时间和行为交互发生状态变化。因此,对动态空间Agent的抽象和描述应该包括时间、状态、位置、属性和行为5个方面,以支持Agent的时空特征变化和行为交互表达,如高移动汽车Agent的位置和速度属性随时间和加/减速行为持续发生变化直到状态变更为停止。本文设计了一个表征这些变化的空间Agent数据模型（Spatial Agent Data Model,SADM）,以支持大规模动态空间Agent的直接建模与数据快速开发。模型的类视图如图2所示。
图2 SADM的类视图

Fig. 2 The UML diagram of the proposed SADM

SObject类是模型的核心,表示具有内部状态和自主行为的动态空间Agent。该类由带有版本标记的SObjects类管理,以支持Agent的基态修正。SObject类自身包含分别代表位置和属性动态变化的Position类和Attribute类,以及代表行为交互建模的Model类。在此基础上,为实现对Agent的统一组织与管理,定义了OType类并位于顶层,负责管理场景中的Agent类型,通过类型聚合可以减少数据的建模需求。此外,OType类负责提供对Agent的统一检索,通过实现不同的Filter类可以构建时空数据库引擎。
SADM是一种简单而紧凑的时空数据模型,将动态空间Agent的时空特征变化表示为位置和属性2种动态数据,同时支持Agent行为交互的建模。

2.3 空间Agent行为建模

现有的研究方法对Agent行为的抽象侧重于描述环境对全部个体行为的约束,或个体行为对环境影响的适应性反应,如土地利用景观模拟的状态转换规则[18]、应急疏散模拟的个体逃生行为[19]等,过于简化行为的过程和影响,缺乏对个体随时空特征变化与个体之间相互影响和交互作用行为的表达,难以对动态空间Agent行为进行建模。
动态空间Agent由于存在位置和属性变化,大量Agent个体的集合将随各自位置和属性的变化持续产生大量的与其它个体之间的复杂交互行为。该行为与现有研究方法中的环境适应性行为不同,不仅与作为主体的Agent个体所处位置、属性和状态有关,而且与行为过程中的其它Agent个体的相对位置、属性和状态相关,行为的结果将改变作为行为影响对象的Agent个体的位置、属性和状态。因此,对动态空间Agent随时空特征变化的交互行为建模需要综合考虑行为主体、行为过程对象和行为影响对象的关系,其抽象定义可表示为：
Behavior : : < Self , Inputs , Outputs >
式中：Self代表行为的主体;Inputs代表行为过程对象集;Outputs代表行为影响对象集。
该定义将动态空间Agent的交互行为明确为作为主体的Agent个体在行为过程中的其它Agent个体的影响下改变作用对象Agent个体的过程,解决了个体之间交互影响的复杂行为难以分解的问题。同时,通过将动态空间Agent的位置和属性变化封装于SADM并作为对象参与行为的执行,移动个体与位置有关的行为描述与表达问题得到了解决。
在开展动态空间Agent交互行为的实际建模中,通过将式（1）作为SADM中Model类的标准接口规范,实现了ABM与GIS的融合,既统一了对Agent行为的抽象描述,提供对行为的标准化开发,又支持集成地学模型对行为过程的具体实现,为本文设计的直接基于Agent行为建模集成地学模型构建地理模拟提供了底层支持。基于空间Agent行为建模的地理模拟建模原型如图3所示。
图3 地理模拟建模流程

Fig. 3 The flow of geospatial simulation modeling

3 分布式并行仿真与实时可视化

3.1 大规模空间Agent模拟分布式并行仿真

分布式并行仿真是解决大规模ABM模拟计算的有效方法[20]。现有的研究方法通过将大量Agent划分为以个体为单位的“Agent并行”方式,或根据空间分布划分为以空间范围为单位的“区域并行”方式,将不同的“Agent”或“区域”分配至不同的计算节点并行计算,从而提高地理模拟的仿真性能[10]。然而,由于“Agent并行”的方式缺乏对个体之间交互行为的表达,而“区域并行”的方式不能描述高移动Agent,因此现有研究方法只适用于简单对象Agent的模拟,并不适用于动态空间Agent的并行仿真。
与简单对象Agent不同,动态空间Agent的行为不仅与时态变化有关,而且与Agent之间的空间分布特征相关,行为的结果将影响和改变Agent之间的空间分布,因此动态空间Agent的行为具有前后交替的空间连续性。但在实际模拟中,当采用分布式并行仿真时,由于不同行为的复杂性不同,各计算节点的执行时间也不一致,不同Agent个体的行为交替出现快慢差异,容易造成执行慢的计算节点与执行快的计算节点获取的Agent时空状态不一致,打破了动态空间Agent对行为交替的时空连续性依赖,导致模拟结果出现时序不正确而数据混乱的问题。
为解决上述问题,本文采取了时间微分的方法：① 对仿真时间进行微分,通过时间微分间隔协同各计算节点的行为执行快慢;② 在一个时间微分间隔内,将大量Agent个体的行为执行转化生成为仿真任务,通过“任务并行”的方式将仿真任务分配至不同的计算节点并行计算,以提高地理模拟的仿真性能;③ 通过2.1节的时空数据库引擎实现Agent数据的实时更新,确保行为执行时各计算节点中Agent数据的一致性。基于上述解决方案的分布式仿真引擎的工作流程如图4所示。
图4 DSIME的工作流

Fig. 4 The working mechanism of distributed simulation

时间微分方法将模拟的仿真步长确定为一个时间微分 Δ t,在时间微分间隔 [ t , t + Δ t )内,认为动态空间Agent的时空特征保持在t时刻不变,保证了所有行为执行时Agent数据的初始状态一致。同时,大量Agent个体根据t时刻的时空特征生成大量的与其它Agent个体t时刻的时空特征耦合的交互行为。为实现大量待执行行为的分布式计算,并提高待执行行为分发的效率, DSIME将行为进一步封装为仿真任务。仿真任务是对t时刻Agent个体交互行为的逻辑描述,其形式化定义为：
Task : : < t , Agent , Behavior >
通过将不同的仿真任务分配至不同的计算节点,DSIME实现了以仿真任务为单位的“任务并行”方式的分布式计算。与“Agent并行”或“区域并行”相比,“任务并行”不要求Agent位于特定区域或仅限于环境对个体的影响,并且由于仿真任务只是对待执行行为的逻辑描述而不涉及具体数据,更容易实现轻量级的任务分发与负载均衡,提高并行效率。
各计算节点的行为执行结果通过时空数据库引擎实时更新Agent的数据,但在时间微分间隔 [ t , t + Δ t )内的全部仿真任务执行完毕之前,DSIME将暂停因行为执行快而更新完毕的Agent个体的接续行为生成,直至全部Agent更新完毕、仿真时间前进下一个时间微分间隔 [ t + Δ t , t + 2 Δ t )为止,从而确保了动态空间Agent的时空连续性。
前后交替的时间微分间隔为大规模空间Agent模拟的分布式并行仿真结果的时序正确提供了重要保障。然而,由于串行的时间微分间隔不可并行计算,当时间微分 Δ t越小时,表示地理模拟过程越精细,但计算总时间越长。反之,当时间微分 Δ t越大,计算总时间相应地减少,但地理模拟过程越概略。

3.2 模拟过程实时可视化

大规模空间Agent模拟的实质是大量Agent个体的时空动态过程[21],因此对Agent个体的时空动态进行三维实时可视化可以有效地传达动态空间Agent的时空特征变化和行为发生过程,帮助用户直观、快速地理解模型的输出。然而,现有的ABM建模/仿真软件（如DMASON、FLAME,Repast等）并不支持模拟过程的实时可视化,绝大多数仅支持对模拟结果的回放,有的甚至没有可视化功能。因此,有必要为空间Agent建模的地理模拟开发一个支持三维实时表示的可视化模块,以便实时地表达Agent的活动及行为的交互过程。
虚拟地理环境技术融合了GIS与可视化,是地理模拟过程实时表示和分析的有效途径[22]。虚拟地理环境是基于地理模型的虚拟环境系统,可用于模拟和分析复杂地学过程与现象,支持可视与不可视的地学数据表达、未来场景预见和地理协同工作[23]。在虚拟地理环境中,动态空间Agent和地理环境可以表示为可视的地理特征（点、线、多边形、影像和模型）,并直观地展示在三维虚拟地理空间中[24],从而实现空间Agent模拟过程与地理数据的一体表达。同时,虚拟地理环境可以独立于地理模拟过程,强调对地理分析功能的支持,为发展面向应用的模拟过程实时表示与分析提供了可能。
基于上述虚拟地理环境技术,结合动态空间Agent的特点,为实现地理模拟过程的实时可视化,本文采用了三维地球渲染引擎结合仿真技术的实现方式：① 通过三维地球渲染引擎构建了一个虚拟地理环境,为地理模拟可视化提供了基础平台; ②以仿真步长为单位对模拟过程进行离散化采样,每一次仿真步长的采样均包含全部的Agent个体,而每一个Agent个体包含在仿真步长内的个体活动和行为过程数据,可以直接在虚拟地理环境中表示;③ 以仿真步长的间隔代表采样频率,如Agent高移动时可以缩小仿真步长的间隔来提高采样的频率,通过高频采样表现动态变化,当采样次数为1时,退化为以地图表示Agent的空间分布。基于上述解决方案的虚拟地理环境中的模拟过程实时可视化如图5所示。
图5 虚拟地理环境中的实时可视化

Fig. 5 Real time visualization in VGE

当模拟计算的分布式并行仿真的时间微分间隔与模拟过程实时可视化的仿真步长采样间隔重合时,通过2.1节的时空数据库引擎实时访问Agent数据,即可以将空间Agent模拟的时空特征变化和行为发生过程以时间微分间隔为单位在虚拟地理环境中实时地可视化,而现有的ABM建模/仿真软件均不支持这样的方式。同时,当用户观察到某一时间微分间隔的模拟结果与预期不符,可以暂停或者中止下一阶段的计算直至恢复而不会对模拟过程造成影响,增强了地理模拟的可交互性。
为适应大规模ABM的高性能要求,本文将实时可视化与分布式并行仿真进行了分离,两者统一通过时空数据库引擎实现各计算节点的中间模拟结果的合并和对Agent数据的实时访问,因此无论模拟计算与可视化是否在同一节点运行都不会影响模拟过程的计算,支持多节点并行仿真的实时可视化。

4 实验与分析

4.1 红蓝对抗实例研究

为验证DGSimF的适用性和有效性,本文设计开发了一个假想中沙漠里的“红蓝对抗”实验案例。案例中红蓝双方的作战实体均基于SADM建模为离散的空间Agent个体,空间Agent个体的位置和生命值属性均处于持续的动态变化中,并能与其它Agent个体发生行为交互。在DSIME的支持下,在基于Cesium构建的三维虚拟地理环境中对空间Agent个体的时空特征变化和行为发生过程进行了实时可视化,支持对模拟结果的回放。过程和结果如图6、图7所示。
图6 空间Agent分布式计算

Fig. 6 Distributed computing for spatial Agent simulation

图7 Agent高移动和行为交互的建模及其在虚拟地理环境中的实时可视化

Fig. 7 ABM with high-mobility and behavior interact and its real-time visualization in VGE

案例的开发表明,DGSimF对具有高移动、行为交互的动态空间Agent的建模与模拟是有效的,适用于构建离散Agent的地理模拟。

4.2 性能分析

为进一步检验DGSimF应对大规模空间Agent模拟的性能,本文从不同的模型计算量和不同的客户端数量（每个客户端即一个计算节点）2个方面分别进行了测试。为便于比较,以完成一定微分间隔数量的计算时长为指标进行性能分析。
测试中共开发了7种不同行为组件的预定义行为,每种预定义行为中均包括大量的空间查询与空间坐标转换计算。由于空间Agent模拟的计算量主要由Agent个体行为执行的计算量构成,因此分别为每种预定义行为设定了6个不同等级的计算量（通过控制空间查询条件和坐标转换的精度来设定,并以单独测试时大致所需的计算时长为指标来标记）。每次测试包含3类1026个动态空间Agent,观察了3个微分间隔共6132个仿真任务,所有测试均在高性能计算机集群上进行。集群由8台机器组成,配置如下：1台服务器用作分布式时空数据库,3台服务器用作DSIME,3台机器用作分布式并行仿真的计算节点,1台机器作为管理端并用于实时可视化。所有机器通过一个内部的1 Gbps局域网直接连接。集群的详细配置如表1所示。
表1 空间Agent模拟分布式并行仿真实验系统配置

Tab. 1 The detailed configuration of distributed parallel simulation experiment system for spatial agent

类型 STDB DSIME 客户端#1 客户端#2 客户端#3 管理端
数量 1 3 1 1 1 1
CPU Intel Xeon E5-2620(6×12 cores, 2.4GHz) Intel Xeon E5-2620(6×12 cores,2.4 GHz) Intel Core i7-6700(4×8 cores,3.4 GHz) Intel Core i7-7700HQ (4×8 cores, 2.8 GHz) Intel Core i7-6700(4×8 cores, 3.40 GHz) Intel Core i7-10750 (6×12 cores,2.6 GHz)
内存 32 GB
(2133 MHz)		 32 GB
(2133 MHz)		 8 GB
(2133 MHz)		 16 GB
(2400 MHz)		 16 GB
(2933 MHz)		 16 GB
(3200 MHz)
硬盘 12 TB
(10krpm,SAS)		 12 TB
(10krpm,SAS)		 1 TB
(7.5krpm,SAS)		 1 TB
(7.5krpm,SAS)		 2 TB
(7.5krpm,SAS)		 1 TB
(7.5krpm,SAS)
内核 3.10.0-327.el7.x86_64 3.10.0-327.el7.x86_64
操作系统 CentOS 7 CentOS 7 Windows 10 Windows 10 Windows 10 Windows 10
采用加速比和并行效率2个指标来评估并行仿真的性能。定义：
S ( n ) = T ( 1 ) T ( n ) E ( n ) = Sn n
式中： n表示计算节点的个数; T ( 1 )和 T ( n )分别代表并行仿真在1个计算节点和 n个计算节点上的运行时间; S ( n )表示 n个计算节点时并行仿真的相对加速比; E ( n )表示 n个计算节点时并行仿真的效率。实验结果如表2、表3所示。
表2 2个客户端并行仿真实验结果

Tab. 2 The results of parallel simulation by two clients

计算量/s T(1)/s T(2) /s S(2) E(2)
0.2 7083 4218 1.6792 0.8396
1 13 164 7461 1.7644 0.8822
3 24 912 12 711 1.9599 0.9799
5 37 470 19 101 1.9617 0.9808
7 49 932 25 629 1.9483 0.9741
9 61 488 31 473 1.9537 0.9768
表3 3个客户端并行仿真实验结果

Tab. 3 The results of parallel simulation by three clients

计算量/s T(1) /s T(3) /s S(3) E(3)
0.2 7083 3309 2.1405 0.7135
3 24 912 10215 2.4388 0.8129
7 37 470 17 352 2.8776 0.9592
9 61 488 21 702 2.8333 0.9444
如图8（a）所示,随着预定义行为的计算量增大,分布式并行仿真的相对加速比增大,并且3个计算节点的相对加速比明显高于2个计算节点。 图8（b）可以看出,并行效率同样随预定义行为的计算量增大而提高,并趋近于1,所不同的是3个计算节点的并行效率比2个计算节点略低。根据阿姆达尔定律（Amdahl's Law）[25]：
W = W s + W p α = W s W s + W p
图8 不同客户端数量分布式并行仿真性能变化

Fig. 8 Performance changes of distributed parallel simulation with different number of clients

式中： W s、 W p分别代表模拟计算中串行、并行部分的负载; W代表总负载（即模拟的计算量）; α代表串行部分负载占总负载的比例。当采用 n个计算节点并行仿真时：
speedup = W s + W p W s + W p n = 1 α + 1 - α n efficiency = speedup n = 1 1 + n - 1 α
式中： speedup表示相对加速比; efficiency表示并行效率。可以得出：
lim n → ∞ 1 α + 1 - α n = 1 α
由式（6）可知,分布式并行仿真系统的性能与串行部分负载 W s占总负载 W的比例 α有关。 W s在DGSimF中主要是指与数据存取有关的负载和分布式计算本身的额外开销,这部分负载相对固定并可能随模拟计算量的增大而有所增长,因此,为降低 α需大幅提高 W p所代表的并行部分的负载,从而提高系统的性能。
这与DGSimF面向大规模空间Agent模拟需要和希望解决的方向一致。一方面,随着空间Agent个体行为越复杂,并行部分负载 W p增大, α相对减少,系统性能得到提高,正如图8（a）所示。另一方面,随着空间Agent个体数量增多,总负载 W增大而 W s所代表的串行部分负载相对固定, α相应地减少,系统性能同样可以相应地提高。本文采用26个和1026个空间Agent分别进行了模拟,实验结果如表4所示。
表4 不同个体数量两个客户端并行仿真实验结果

Tab. 4 The results of parallel simulation by two clients with different number of agents

计算量/s 26 个空间Agent 1026 个空间Agent
S(2) E(2) S(2) E(2)
0.2 1.0858 0.5429 1.6792 0.8396
1 1.2926 0.6463 1.7644 0.8822
3 1.4210 0.7105 1.9599 0.9799
5 1.5623 0.7811 1.9617 0.9808
可以得出,DGSimF随空间Agent个体数量增多和个体行为复杂性增加,仿真性能更高。上述现象为DGSimF面向大规模空间Agent模拟提供了理论与实验印证,同时也为进一步改进和完善DGSimF指明了方向,如研究并行编绎[26],以减少串行部分负载 W s,从而降低 α的值。

4.3 讨论

4.3.1 方法讨论
实例研究中的红蓝双方作战实体的对抗代表了典型的空间Agent模拟,包含一组离散的、具有自主行为的、频繁移动和属性变化的Agent个体,个体之间随位置和属性变化持续产生大量的行为交互。实例在DGSimF中的开发表明：
（1）DGSimF可以为具有时空特征变化与行为交互的空间Agent模拟提供一个有效的平台。与现有基于ABM建模/仿真软件构建地理模拟方式相比：①DGSimF直接基于Agent行为建模集成地学模型,减少了额外的空间数据结构和过程模拟算法设计,为地理模拟提供了底层、通用支持;②利用虚拟地理环境技术集成GIS与可视化,克服了ABM建模/仿真软件仅支持模拟结果回放的局限,实现了对地理模拟过程的实时可视化。
（2）DGSimF解决了大规模空间Agent模拟的计算压力问题。与简单对象Agent模拟的分布式并行仿真方法相比：① DGSimF采用了时间微分方法协同不同计算节点的行为执行快慢,保证了地理模拟结果的时序正确;② 通过将待执行行为逻辑封装为仿真任务并以“任务并行”的方式进行分布式计算,解决了空间Agent的时空连续性问题,提高了大规模空间Agent模拟的仿真性能。
4.3.2 性能讨论
（1）DGSimF的仿真性能与模拟的规模、复杂程度和计算节点的数量有关。其中,加速比与Agent个体的数量（数量越多表示地理模拟规模越大）、预定义行为的计算量（计算量越大表示地理模拟越复杂）和计算节点数量均正相关,如图8（a）和表4所示。主要的原因是DGSimF统一通过时空数据库引擎访问和更新Agent的数据,当Agent个体数量和预定义行为的计算量均较少时,各计算节点可以很快完成行为执行的计算并将执行结果返回,与Agent个体的数据请求一并涌入时空数据库引擎从而造成拥塞,而随着Agent个体数量增多和预定义行为计算量增大,Agent个体的数据请求开始形成规模效应,可以减少很多不必要的数据库交互,并且各计算节点完成较大计算量的预定义行为的时长不同,可以依次返回行为执行的结果,因而时空数据库引擎可以有序处理和及时响应,将大大提高数据存取的效率。显然,当预定义行为的计算量增大到超过时空数据库引擎的响应时间后,加速比将不会再有提高。计算节点数量的增加对加速比的影响最直接,这可归因于计算节点对仿真任务的并行化分担,但由于分布式计算存在必要的数据分发和汇总的额外开销,因此加速比将无穷趋近于计算节点的数量值。
（2）DGSimF的并行效率和加速比是一对时间和效益的矛盾。并行效率与Agent个体的数量和预定义行为的计算量正相关,但与计算节点的数量负相关,如图8（b）和表4所示。这是因为并行效率是衡量达到一定加速比所付出代价的指标,随着Agent个体数量和预定义行为计算量的增大,加速比相应地增大,在相同计算节点数量的情况下,并行效率将逐渐提高。当计算节点数量增加,达到相同加速比的代价增大,并行效率将相应地降低。由于加速比无穷趋近于计算节点的数量值,由式（3）可知,并行效率将无穷趋近于1。
（3）多客户端的实验结果表明,面向大规模空间Agent模拟时,DGSimF通过扩展计算节点可以有效地压缩计算时长。如表3中当预定义行为的计算量为9 s时,单机计算时长达到了难以接受的 17 h,而通过增加计算节点,采用3个客户端分布式并行仿真的计算时长被压缩到了6 h,有效地缓解了大规模空间Agent复杂模拟的计算压力问题。同时,由于分布式并行仿真存在必要的额外开销,较大规模的Agent个体数量和较复杂的预定义行为计算量更有利于充分发挥DGSimF的仿真性能,如表2和表3中,并行效率都保持在0.7以上。

5 结论与展望

5.1 结论

与简单对象Agent不同,空间Agent具有高移动以及个体之间存在行为交互,现有大规模ABM模拟与计算的分布式并行仿真方法已不适用于空间Agent的模拟。本文面向大规模空间Agent建模,提出了一个分布式地理模拟框架DGSimF,采用了一个简单但高效的时空数据模型SADM支持动态空间Agent的直接建模与数据快速开发,提供对Agent高移动与行为交互的个体行为建模,通过将大量Agent个体的交互行为转化生成为以仿真步长为单位的仿真任务集,在不同计算节点之间以“任务并行”的方式进行分布式计算,解决了大规模空间Agent模拟的计算压力问题。对于模拟过程和结果,DGSimF基于三维地球渲染引擎实现了在虚拟地理环境中的实时可视化,可以帮助用户快速、高效地理解模型的输出。案例研究和性能测试表明,DGSimF可以为具有时空特征变化与行为交互的空间Agent模拟提供一个有效的平台。
DGSimF从设计上改进了现有研究基于仿真软件建模的方式,从底层支持直接基于Agent建模集成地学模型。为解决空间Agent模拟的分布式并行仿真问题,采用了时间微分和任务并行的创新技术：① 对空间Agent的交互行为生成采用了时间微分协同方法,解决了大量空间Agent个体模拟结果时序不正确的数据混乱问题;② 对行为的执行采用了任务并行的分布式并行仿真技术,将行为执行封装为行为任务,采用“任务并行”的方式进行分布式并行计算,解决了空间Agent模拟对时空连续性的依赖问题。

5.2 展望

DGSimF基于ABM与GIS,结合分布式计算与虚拟地理环境技术,是以自下而上的方式理解动态地理现象的一种有效方法,同时也是一种面向应用的仿真建模技术,可以用来在虚拟环境中表示真实世界地理现象的时空动态,如Agent个体具有高移动和自主行为的应急疏散演练、人群动态分布,抑或是Agent单元之间具有复杂动态交互的道路网交通流、城市土地利用景观模拟等。
由于动态地理现象是一个“复杂巨系统”,本文研究仍有很多不尽之处。例如,虽然通过空间Agent建模的微观个体可以表达多Agent之间的行为交互,但在Agent的群体和组织行为上尚未深入探讨,目前只适用于构建离散Agent的地理模拟。同时,在空间Agent的自我学习和进化方面尚有待进一步研究。在接下来的工作中,DGSimF将通过知识工程的方式集成特定领域的行为组件来扩展对相关领域应用场景的模型构建能力,以支持快速开发。为提高仿真效率满足更高性能计算需求,需要研究一种兼顾仿真任务顺序和空间邻近原则的调度算法[27,28],减少中间模拟结果的数据交互。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Wallentin G. Spatial simulation: A spatial perspective on individual-based ecology—a review[J]. Ecological Modelling, 2017, 350(4):30-41. DOI: 10.1016/j.ecolmodel.2017.01.017

DOI

[2]
余强毅, 吴文斌, 唐华俊, 等. 复杂系统理论与Agent模型在土地变化科学中的研究进展[J]. 地理学报, 2011, 66(11):1518-1530.

[ Yu Q Y, Wu W B, Tang H J, et al. Complex system theory and Agent-based modeling: progresses in land change science[J]. Acta Geographica Sinica, 2011, 66(11):1518-1530. ] DOI: 10.11821/xb201111008

DOI

[3]
翟瑞雪, 戴尔阜. 基于主体模型的人地系统复杂性研究[J]. 地理研究, 2017, 36(10):1925-1935.

DOI

[ Zhai R X, Dai E F. Research on the complexity of man-land system based on agent-based models[J]. Geographical Research, 2017, 36(10):1925-1935. ] DOI: 10.11821/dlyj201710009

DOI

[4]
Ding Y L, Zhu Q, Lin H. An integrated virtual geographic environmental simulation framework: A case study of flood disaster simulation[J]. Geo-spatial Information Science, 2014, 17(4):190-200. DOI: 10.1080/10095020.2014.988199

DOI

[5]
Arifin S M N, Madey G R, Collins F H. Spatial agent-based simulation modeling in public health: design, implementation, and applications for malaria epidemiology[M]. New Jersey: John Wiley & Sons Inc, 2016. DOI: 10.1002/9781118964385

DOI

[6]
潘茂林, 陶海燕. JAVA-SWARM与GIS集成研究——以城市地理模拟为例[J]. 系统仿真学报, 2009, 21(18):5704-5708.

[ Pan M L, Tao H Y. Integration technique between java-swarm and GIS on urban geo-simulation[J]. Journal of System Simulation, 2009, 21(18):5704-5708. ] DOI: CNKI:SUN:XTFZ.0.2009-18-025

DOI

[7]
黎夏, 李丹, 刘小平. 地理模拟优化系统(GeoSOS)及其在地理国情分析中的应用[J]. 测绘学报, 2017, 46(10):1598-1608.

[ Li X, Li D, Liu X P. Geographical simulation and optimization system(GeoSOS) and its appl ication in the analysis of geographic national conditions[J]. Acta Geodaetica et Cartographica Sinica, 2017,46(10):1598-1608. ]DOI: CNKI:SUN:DXJZ.0.2009-08-009

DOI

[8]
Vahidnia M H, Alesheikh A A, Alavipanah S K. A multi-agent architecture for geosimulation of moving agents[J]. Journal of Geographical Systems, 2015, 17(4):353-390.DOI: 10.1007/s10109-015-0218-2

DOI

[9]
Sauvage S, Filatova T, Horstman E, et al. Modelling adaptive behaviour in spatial agent-based models: coastal cities and climate change [C]// International Congress on Environmental Modelling and Software, Toulouse, 2016: 18.

[10]
Li Z Q, Guan X F, Li R, et al. 4D-SAS: A distributed dynamic-data driven simulation and analysis system for massive spatial Agent-based modeling[J]. ISPRS International Journal of Geo-Information, 2016, 42(5):1-21. DOI: 10.3390/ijgi5040042

DOI

[11]
Züfle A, Kavak H, Kim J S, et al. Towards large-scale Agent-based geospatial simulation [C]// Social Computing, Behavioral-Cultural Modeling and Prediction and Behavior Representation in Modeling and Simulation, Washington DC, 2021:1-10.

[12]
Lettieri N, Spagnuolo C, Vicidomini L. Distributed agent-based simulation and GIS: An experiment with the dynamics of social norms [C]// European Conference on Parallel Processing, Vienna, 2015:379-391. DOI: 10.1007/978-3-319-27308-231

DOI

[13]
Francisco B, Albert G-M, Emilio L, et al. Care HPS: a high performance simulation tool for parallel and distributed agent-based modeling[J]. Future Generation Computer Systems, 2017, 68(3):59-73. DOI: 10.1016/j.future.2016.08.015

DOI

[14]
Mastio M, Zargayouna M, Scémama G, et al. Distributed agent-based traffic simulations[J]. IEEE Intelligent Transportation Systems Magazine, 2018, 10(1):145-156. DOI: 10.1109/MITS.2017.2776162

DOI

[15]
Simon C, Marian G, Mike H, et al. Exploitation of high performance computing in the FLAME Agent-based simulation framework [C]// IEEE International Conference on High Performance Computing & Communication, Liverpool, 2012:538-545. DOI: 10.1109/HPCC.2012.79

DOI

[16]
Gennaro C, Carmine S, Vittorio S. Toward the new version of D-MASON: efficiency, effectiveness and correctness in parallel and distributed agent-based simulations [C]// IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Chicago, 2016:1803-1812. DOI: 10.1109/IPDPSW.2016.52

DOI

[17]
Marc J-R, Jan K, Martin B. A coupled simulation architecture for agent-based/geohydrological modelling with NetLogo and MODFLOW[J]. Environmental Modelling and Software, 2019, 115(3):19-37. DOI: 10.1016/j.envsoft.2019.01.020

DOI

[18]
赵耀龙, 张珂, 彭永俊, 等. 基于地理模拟方法的昆明市空间拓展情景分析[J]. 地理研究, 2014, 33(1):119-131.

DOI

[ Zhao Y L, Zhang K, Peng Y J, et al. Scenario analysis of urban growth in kunming based on geosimulation system[J]. Geographical Research, 2014, 33(1):119-131. ] DOI: 10.11821/dlyj201401011

DOI

[19]
Lyuba M, Carole A A, Julie D. Multi-agent geospatial simulation of human interactions and behaviour in bushfires [C]// 16th International Conference on Information Systems for Crisis Response and Management, València, 2019:1-15.

[20]
Hua T, Jiang T. Agent-based modeling and simulation of complex distributed systems [C]// World Congress on Intelligent Control & Automation, Chongqing, 2017:416-421. DOI: 10.1109/WCICA.2008.4592960

DOI

[21]
Andreas K. Geosimulation: modeling spatial processes[M]. Berlin: Springer, 2015. DOI: 10.1007/978-3-319-00008-4_5

DOI

[22]
林珲, 胡明远, 陈旻, 等. 从地理信息系统到虚拟地理环境的认知转变[J]. 地球信息科学学报, 2020, 22(4):662-672.

DOI

[ Lin H, Hu M Y, Chen M, et al. Cognitive transformation from geographic information system to virtual geographic environments[J]. Journal of Geo-information Science, 2020, 22(4):662-672. ] DOI: 10.12082/dqxxkx.2020.200048

DOI

[23]
林珲, 黄凤茹, 闾国年. 虚拟地理环境研究的兴起与实验地理学新方向[J]地理学报, 2009, 64(1):7-20.

[ Lin H, Huang F R, Lv G N. Development of virtual geographic environments and the new initiative in experimental geography[J]. Acta Geographica Sinica, 2009, 64(1):7-20. ] DOI: 10.3321/j.issn:0375-5444.2009.01.002

DOI

[24]
Mekni M. Integration of GIS data for visualization of virtual geospatial environments [C]// Second International Conference on Mathematics and Computers in Sciences and in Industry (MCSI), Sliema, 2015:273-282. DOI: 10.1109/MCSI.2015.39

DOI

[25]
Mark D H, Michael R M. Amdahl's Law in the multicore era[J]. Computer, 2008, 41(7):33-38. DOI: 10.1109/HPCA.2008.4658638

DOI

[26]
Dhananjai M R. Efficient parallel simulation of spatially-explicit agent-based epidemiological models[J]. Journal of Parallel and Distributed Computing, 2016, 93(C):102-119.DOI: 10.1016/j.jpdc.2016.04.004

DOI

[27]
Omar R, Yann S, Philippe M. Load-balancing for large scale situated Agent-based simulations[J]. Procedia Computer Science, 2015, 51:90-99. DOI: 10.1016/j.procs.2015.05.204

DOI

[28]
Petkova A, Hughes C, Deo N, et al. Accelerating the distributed simulations of agent-based models using community detection [C]// IEEE Rivf International Conference on Computing & Communication Technologies, Hanoi, 2016:25-30. DOI: 10.1109/RIVF.2016.7800264

DOI

Options
文章导航

/

〈 〉